Зв’язок між розв’язками прямої і двоїстої задач. Геометрична інтерпретація двоїстих задач, Детальна інформація

\x00B2

ju

\x1600\xA668\xE704\x4300\x1C4A\x5500\x0108\x4A61 \x486DТ\x4873Т\x0323\xB56A

\x2403\x1103\xC584\x1202\x6864\x0101\x3100$\x2437\x3800$\x2448\x6000\xC584\x6102\x0324\x1900їста задача містять по двох перемінні. Тому їхнє рішення знаходимо, використовуючи геометричну інтерпретацію задачі лінійного програмування (мал. 3. і 4.). З мал. 3. видно, що вихідна задача не має оптимального плану через необмеженість знизу її цільової функції на безлічі припустимих рішень.

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

Перебування рішення двоїстих задач. Розглянемо пари двоїстих задач — основну задачу лінійного програмування (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).

0.

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

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

12,

17,

2x1 – x2 + 2x3 = 4,

0.

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

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

1,

2,

- 1,

0.

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

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



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

i

Базис

C6