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

Вернуться в Математика

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


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

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

(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,

x1 + x2 8,

x1, x20,

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

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

- 2y1 + y2 2

3y1 + y2 7,

y1, y2 0.

Як у вихідної, так і в двоїстій задачі число невідомих дорівнює двом

Добавить в Одноклассники    

 

Rambler's Top100