оділяють на симетричні і несиметричні. У симетричній парі двоїстих завдань обмеження (43) прямої задачі і співвідношення (46) двоїстої завдання є нерівностями виду "". Таким чином, змінні обох задач можуть брати тільки лише невід'ємні значення.
Теорема подвійності.
Існуючі залежності між рішеннями прямої і двоїстої задач характеризуються сформульованими нижче лемами і теоремами подвійності.
Лемма 1.
Якщо Х - деякий план вихідної задачі , a Y - довільний план двоїстої задачі , те значення цільової функції вихідної задачі при плані Х завжди вбирається значення цільової функції двоїстої задачі при плані Y, тобто
Лемма 2.
Якщо для деяких планів X * і Y * завдань , то X * - оптимальний план вихідної задачі, а Y * - оптимальний план двоїстої задачі.
Теорема 8
( перша теорема подвійності). Якщо одне із завдань двоїстої пари або , має оптимальний план, то й інша має оптимальний план і значення цільових функцій задач при їхніх оптимальних планах рівні між собою, тобто
Якщо ж цільова функція однієї задачі із двоїстої пари необмежена (для вихідної - зверху, для двоїстої - знизу), то інша задача взагалі не має планів.
Теорема 9
( друга теорема подвійності).
План завдання і план завдання , є оптимальними планами цих задач тоді і тільки тоді, коли для будь-якого виконується рівність
В В
Геометрична інтерпретація двоїстих задач. Якщо число змінних в прямій і двоїстої задачах, що утворять дану пару, дорівнює двом, то, використовуючи геометричну інтерпретацію задачі лінійного програмування, можна легко знайти рішення даної пари задач. При цьому має місце один з наступних трьох взаємно виключають один одного випадків:
1) обидві завдання мають плани;
2) плани має тільки одне завдання;
3) для кожного завдання двоїстої пари безліч планів порожньо.
а) Скласти задачу двоїсту до прикладу 2.
б) Знайти її рішення будь методом.
в) Знайти рішення задачі 2, використовуючи теорему подвійності.
а) Завдання має вигляд:
1
1
1
2
1
3
2
1
f = 9X1 + 14X2 + 15 X3 + 10X4 в†’ max
1
...
