Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «
». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:max F = –5x1 + 2x2;
Тепер за відповідними правилами складемо двоїсту задачу:
;Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:
До заданої задачі лінійного програмування записати двоїсту.
Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду «
». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:Двоїста задача:
Оскільки перше обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі
може набувати як додатного, так і від’ємного значення.Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.
Якщо
та – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність або . (3.7)Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:
Підсумувавши праві і ліві частини нерівностей, отримаємо:
. (3.8)Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:
Підсумувавши після множення тут також ліві та праві частини, отримаємо нерівність:
(3.9)Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:
.Нерівність (3.7) доведено.
Якщо
та – допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність (3.10)то X*, Y* – оптимальні розв’язки відповідних задач.
Доведення. Нехай
– допустимий план прямої задачі (3.1) – (3.3). Тоді на підставі нерівності (3.7) маємо: . За умовою задачі , отже (3.11)Оскільки за допущенням
– довільний допустимий план прямої задачі, то нерівність (3.11) виконується для будь-якого з можливих розв’язків. Отже, маємо, що при цільова функція (3.1) набирає найбільшого значення, тобто є оптимальним розв’язком початкової задачі.В аналогічний спосіб доводиться, що
– оптимальний план двоїстої задачі.Теорема (перша теорема двоїстості). Якщо одна з пари спряжених задач має оптимальний план, то й друга задача також має розв’язок, причому для оптимальних розв’язків значення цільових функцій обох задач збігаються, тобто
.Якщо цільова функція однієї із задач необмежена, то спряжена задача також не має розв’язку.
Доведення. Допустимо, що початкова задача (3.1) – (3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з першихm векторів
. Остання симплексна таблиця має вигляд:і | Базис | Сб | План | с1 | с2 | … | сm | cm + 1 | … | cn |
x1 | x2 | … | xm | xm + 1 | … | xn | ||||
1 | x1 | 1 | 0 | … | 0 | … | ||||
2 | x2 | 0 | 1 | … | 0 | … | ||||
m | xm | 0 | 0 | … | 1 | … | ||||
m + 1 | F0 | 0 | 0 | … | 0 | … |
Позначимо через D матрицю, що утворена з компонент векторів А1, А2,…, Аm останнього базису в першій симплексній таблиці.
Для оптимального плану отримаємо:
(3.12)де
, В-вектор, що складається з вільних членів системи обмежень.Звідси:
(3.13)Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів
початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1) – (3.3) Аj відповідає в симплексній таблиці вектор , такий що (3.14)Позначимо через
матрицю, що складається з коефіцієнтів розкладу векторів . Тоді буде справджуватися рівність: , звідки . (3.15)Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді: