Зв'язок між розв'язками прямої і двоїстої задач. Геометрична інтерпретація двоїстих задач

Перебування рішення двоїстих задач. Розглянемо пари двоїстих задач - основну задачу лінійного програмування (1) - (3) і двоїсту до неї задачу (4), (5).

Припустимо, що за допомогою симплексного методу знайдений оптимальний план X* задачі (1) - (3) і цей план визначається базисом, утвореним векторами Рi1, Рi2,…,Pim.

Позначимо через С6=(ci1,ci2,…,cim) вектор-рядок, складений з коефіцієнтів при невідомих у цільовій функції (1) задачі (1) - (3), а через Р-1- матрицю, зворотну матриці Р, складеної з компонентів векторів Рi1, Рi2,...,Рim базисa. Тоді має місце наступне твердження.Теорема 3. Якщо основна задача лінійного програмування має оптимальний план X*, тo Y* = С6Р-1 є оптимальним планом двоїстої задачі.

Таким чином, якщо знайти симплексним методом оптимальний план задачі (1) - (3), те, використовуючи останню симплекс-таблицю, можна визначити С6 і Р-1 і за допомогою співвідношення Y*=С6Р-1 знайти оптимальний план двоїстої задачі (4), (5).

У тому випадку, коли серед векторів Р1, P2,…,Рn, складених з коефіцієнтів при невідомих у системі рівнянь (2), мається m одиничних, зазначену матрицю Р-1 утворять числа перших m рядків останньої симплекса-таблиці, що коштують у стовпцях даних векторів Тоді немає необхідності визначати оптимальний план двоїстої задачі множенням C6 на Р-1, оскільки компоненти цього плану збігаються з відповідними елементами (m+1)-й рядка стовпців одиничних векторів, якщо даний коефіцієнт cj=0, і дорівнюють сумі відповідного елемента цього рядка і cj якщо cj 0.

Сказане вище має місце і для симетричної пари двоїстих задач При цьому тому що система обмежень вихідної задачі містить нерівності виду «», те компоненти оптимального плану двоїстої задачі збігаються з відповідними числами (m+1)-й рядка останньої симплекса-таблиці рішення вихідної задачі Зазначені числа коштують у стовпцях векторів, що відповідають додатковим перемінної

3. Для задачі, що складає у визначенні максимального значення функції F=x1 + 2x2-x2 при умовах

-x1 + 4x2 - 2x3 12,

x1 + x2 + 2x3 17,

2x1 - x2 + 2x3 = 4,

x1, x2, x3 0.

скласти двоїсту задачу і знайти її рішення.

Рішення. Двоїста задача стосовно вихідного складається в перебуванні мінімуму функції F*= 12y1 + 17y2 + 4y3 при умовах:

- y1 + y2 + 2y3 1,

4y1 + y2 - y3 2,

- 2y1 + 2y2 + 2y3 - 1,

y1, y2 0.

Щоб знайти рішення двоїстої задачі, спочатку знаходимо рішення вихідної задачі методом штучного базису. Воно приведено в табл 1.

З останньої симплекс таблиці видно, що двоїста задача має рішення

Оптимальні двоїсті оцінки задовольняють усім уело виям двоїстої задачі При цьому мінімальне значення цільової функції двоїстої задачі, рівне 12•(5/7)+17•0+4•(6/7)=12, збігається з максимальним значенням цільової функції Fmax вихідної задачі.