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

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

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

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

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

Отже, для того, щоб звести вищесформульовану задачу (1) — (3) до задачі лінійного програмування, введемо додаткове позначення  та нових змінних .

Після того, скориставшись введеними позначення, початкову завдау (1) — (3) зведемо до наступної:

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

Задача (5) — (8) є задачею лінійного програмування, а отже, її рішення можна знайти скориставшись будь-яким, в залежності від вхідних даних, методом. Знаючи оптимальний план цієї задачі, на основі співвідношення (4) отримуємо оптимальний план вихідної задачі (1) — (3).

Таким чином, процес знаходження рішення задачі дробово-лінійного програмування включає наступні етапи:

  1. Задачу (1) — (3) зводять до задачі лінійного програмування (5) — (8).
  2. Знаходять розв'язок отриманої в пункті один задачі.
  3. Використовуючи співвідношення (4), визначають оптимальний план задачі (1) — (3) і знаходять мінімальне чи максимальне значення функції (1).

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

Знайти максимальне значення функції:

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

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

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

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

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

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

drobovo-linijne_programuvannja_lp53

Початкова симплекс таблиця розширеної задачі

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

Щоб визначити вектор, який будемо виключати з базису, знаходимо . Тобто, в результаті виконання даного кроку, ми отримали три значення, які можна вважати мінімальними. Зновутаки, вибравши довільним чином будь-яке з них, наприклад, друге значення, переходимо до виключення вектора з базису. Відмітимо, що даний вектор являється штучним, тому його не будемо в подальшому вводити ні до одного з наступних базисів. Тобто надалі, стовпчик даного вектора не заповнюється.

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

drobovo-linijne_programuvannja_lp54

Перехід до нового опрного плану розширеної задачі лінійного програмування

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

drobovo-linijne_programuvannja_lp55

Побудова оптимального плану розширеної задачі лінійного програмування

Як видно з останньої таблиці, опорним планом для початкової задачі лінійного програмування (12) — (14) є вектор , а виходячи з того, що п'ятий рядок таблиці не містить від'ємних значень, можна зробити висновок, що даний опорний план являється оптимальним.

Тому, скориставшись формулою (4), знаходимо оптимальний план задачі дробово-лінійного програмування (9) — (11) та максимальне значення функції мети (9):

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

Розв'язок задачі дврбово-лінійного програмування блок-схема

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

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

Розв'язок задачі дврбово-лінійного програмування блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар