60. Теорія двоїстості

Будь-якому завданню лінійного програмування можна зіставити пов'язане чи двоїсте їй завдання. Причому спільне дослідження цих завдань дає, як правило, значно більше інформації, ніж дослідження кожної з них окремо.

Будь-яке завдання лінійного програмування можна записати у вигляді:

Початкова задача називаєтьсяВихідноюабоПрямою.

Модель двоїстої задачі має вигляд:

Змінні двоїстої задачі називають об'єктивно обумовленими оцінками або двоїстими оцінками.

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

Подвійне завдання стосовно вихідної складається відповідно до таких правил:

1.Цільова функція вихідної задачі формулюється на максимум, а цільова функція двоїстої задачі - на мінімум, при цьому в задачі на максимум всі нерівності у функціональних обмеженнях мають вигляд, а в задачі на мінімум - вид;

2.Матриця

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

у двоїстої задачі виходять один з одного транспонуванням;

3.Число змінних у двоїстій задачі дорівнює числу функціональних обмежень вихідної задачі, а число обмежень у системі двоїстої задачі - числу змінних у вихідному завданні;

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

5.Кожному обмеженню одного завдання відповідає змінна іншого завдання: номер змінної збігається з номером обмеження; у своїй обмеженню, записаному як нерівності , відповідає змінна, пов'язана умовою неотрицательности. Якщо функціональне обмеження вихідної задачі є рівністю, то відповідна змінна двоїстої задачі може набувати як позитивних, так і негативних значень.

Математичні моделі пари двоїстих завдань можуть бути симетричними та несиметричними. У несиметричних двоїстих завданнях система обмежень вихідної задачі задається у вигляді рівностей, а двоїстої – у вигляді нерівностей, причому змінні у подвійному завданні можуть бути і негативними. У симетричних двоїстих завданнях система обмежень як вихідної, так і двоїстої задачі задається у вигляді нерівностей, причому на подвійні змінні накладається умова невід'ємності.