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

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

Розглянемо кілька двоїстих задач, утворену основною задачею лінійного програмування і двоїстої до неї.

Вихідною задачею є: найти максимум функції

(1)

при умовах

(2)

(3)

Двоїста задача: знайти мінімум функції

(4)

при умовах

(5)

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

Існуючі залежності між рішеннями прямої і двоїстої задач характеризуються сформульованими нижче лемами і теоремами подвійності.

F*(Y)

Лемма 1.2. Якщо F(X*) = F*(Y*) для деяких планів X* і Y* задач (1) — (3) і (4), (5), те X* — оптимальний план вихідної задачі, a Y* — оптимальний план двоїстої задачі

.

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

виконується рівність



Геометрична інтерпретація двоїстих задач. Якщо число перемінних у прямій і двоїстої задачах, що утворять дану пару, дорівнює двом, то, використовуючи геометричну інтерпретацію задачі лінійного програмування, можна легко знайти рішення даної пари задач При цьому має місце один з наступних трьох взаємно виключають один одного випадків: 1) обидві задачі мають плани; 2) плани має тільки одна задача; 3) для кожної задачі двоїстої пари безліч планів порожньо

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

14,

8,

0,

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

Рішення. Двоїстою задачею стосовно вихідного є задача, що складається у визначенні мінімального значення функції F*=14y1 + 8y2 при умовах

2

7,

0.

Як у вихідної, так і в двоїстій задачі число невідомих дорівнює двом. Отже, їхнє рішення можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (рис. 1. і 2.)