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

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

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

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

(1)

при умовах

(2)

(3)

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

(4)

при умовах

(5)

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

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

Лемма 1.1. Якщо X - деякий план вихідної задачі (1) - (3), а В - довільний план двоїстої задачі (4), (5), те значення цільової функції вихідної задачі при плані X завжди не перевершує значення цільової функції двоїстої задачі при плані Y, тобто F(X)F*(Y)

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

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

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

Теорема 2. (друга теорема подвійності). План задачі (1) - (3) і план задачі (4), (5) є оптимальними планами цих задач тоді і тільки тоді, коли для будь-якого виконується рівність

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

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

- 2 x1 + 3x214,