Знаходження розв'язку задачі дробово-лінійного програмування шляхом зведення її до задачі лінійного програмування

Нехай, зновутаки, розглядається задача математичного програмування, яка полягає у відшуканні екстремального (мінімального чи максимального) значення функції мети:

при наступних обмеженнях:

Крім того, передбачається, що в області невід'ємних розв'язків системи рівнянь (2) має місце нерівність .

Відмітимо, що розглядуваний тип задач відноситься до класу задач дробово-лінійного програмування і які ми вже навчилися розв'язувати з допомогою графічного методу. Проте, графічний спосіб рішення задач такого типу (як і будь-якого іншого типу задач математичного програмування) являється не дуже універсальним, тобто використовується в тому випадку, коли кількість невідомих задачі не перевищує число два. Сьогодні розглянемо дещо інший спосіб, який можна вважати більш універсальним, і який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування і, в подальшому, розв'язку її будь-яким з відомих методів (симплекс методу, двоїстий симплекс метод, метод штучного базису).

Читати повністю

Розв'язок задачі лінійного програмування графічним методом в середовищі Delphi

Графічний метод розв'язання задач лінійного програмування має обмежену область застосування, бо зазвичай використовується для задач з двома змінними. Тобто, кожна з нерівностей в системі обмежень задач такого типу, визначає на координатній площині Графічний метод на Delphi деяку півплощину, а система нерівностей в цілому — перетин відповідних півплощин. Сукупність точок перетину даних півплощин називається областю допустимих рішень або багатокутником розв'язків. Даний багатокутник завжди являє собою опуклу фігуру, тобто має наступну властивість: якщо дві точки Графічний метод на Delphi і Графічний метод на Delphi належать цій фігурі, то і весь відрізок Графічний метод на Delphi належить їй.

Розглянемо задачу лінійного програмування та спробуємо розв'язати її використовуючи delphi-програму, яка реалізує даний метод. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару а також загальна кількість сировини наведені в наступній таблиці:

Графічний метод на Delphi

Читати повністю

Лінійне програмування. Постановка задачі лінійного програмування

Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:

  1. Функції мети для якої знаходимо оптимальне значення

    Задача лінійного програмування

    де Задача лінійного програмування — апибуток від реалізації однієї i-ї продукції, а Задача лінійного програмування — кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів Задача лінійного програмуванняна протилежні, то функція Задача лінійного програмування змінюється на Задача лінійного програмування і навпаки.

  2. Обмеження по запасу ресурсів:

    Задача лінійного програмування

    де Задача лінійного програмування — нориа витрат i-го ресурсу; Задача лінійного програмування — кількість продукції j-го виду, випуск одиниці якої потребує Задача лінійного програмування витрат, також слід зазначити, що виличина Задача лінійного програмування не повинна бути від'ємною; Задача лінійного програмування — запаси i-го ресурсу; i=1,...,m — порядковий номер ресурсу; j=1,...,n — порядковий номер продукції.

  3. Читати повністю

Двоїста задача лінійного програмування

Кожній задачі лінійного програмування певним чином можна поставити у відповідність деяку іншу задачу, яка називається двоїстою задачею лінійного програмування. Запишемо пряму (вихідну) задачу лінійного програмування, яка полягає у визначенні максимуму цільової функції:

120

при обмеженнях:

216

39

Читати повністю