5 * 1 +0 = 43
План є оптимальним, говоримо про те, що найбільш вигідним є виробництво 2едініц 2 види продукції та 1 об'єкту 3 види продукції, причому сировину витрачається повністю.
6. Теореми подвійності і їх використання в задачах ЛП
Кожній задачі лінійного програмування можна певним чином зіставити деяку інше завдання (лінійного програмування), звану двоїстої або сполученої по відношенню до вихідної або прямій задачі. Дамо визначення двоїстої завдання по відношенню до загальної задачі лінійного програмування , що складається, як ми вже знаємо, в знаходженні максимального значення функції
(42)
за умов
(43)
(44)
Визначення.
Завдання, яка полягає у знаходженні мінімального значення функції
(45)
за умов
(46)
(47)
називається двоїстої по відношенню до задачі (42) - (44). Задачі (42) - (44) і (45) - (47) утворюють пару завдань, звану в лінійному програмуванні двоїстої парою. Порівнюючи дві сформульовані завдання, бачимо, що двоїста задача складається згідно з такими правилами:
1. Цільова функція вихідної задачі (42) - (44) задається на максимум, а цільова функція двоїстої (45) - (47) - на мінімум. p> 2. Матриця
(48)
складена з коефіцієнтів при невідомих у системі обмежень (43) вихідної задачі (42) - (44), і аналогічна матриця
(49)
в двоїстої задачі (45) - (47) виходять один з одного Транспонированием (тобто заміною рядків стовпцями, а стовпців - рядками).
3. Число змінних в двоїстої задачі (45) - (47) дорівнює числу обмежень у системі (43) вихідної задачі (42) - (44), а число обмежень в системі (46) двоїстої завдання - числу змінних у вихідній задачі.
4. Коефіцієнтами при невідомих у цільовій функції (45) двоїстої задачі (45) - (47) є вільні члени в системі (43) вихідної задачі (42) - (44), а правими частинами в співвідношеннях системи (46) двоїстої задачі - коефіцієнти при невідомих у цільовій функції (42) вихідної задачі.
5. Якщо мінлива x j вихідної завдання (42) - (44) може приймати тільки лише позитивні значення, то j -е умова в системі (46) двоїстої задачі (45) - (47) є нерівністю виду "пЂї". Якщо ж змінна x j може приймати як позитивні, так і негативні значення, то 1 - співвідношення в системі являє собою рівняння. Аналогічні зв'язки мають місце між обмеженнями (43) вихідної задачі (42) - (44) і змінними двоїстої задачі (45) - (47). Якщо i - співвідношення в системі (43) вихідної задачі є нерівністю, то i -я п еременная двоїстої завдання . В іншому випадку змінна у j може приймати як позитивні, так і негативні значення.
Двоїсті пари завдань зазвичай п...
