3. Теореми двоїстості.

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

Теорема 1. (теорема про існування): якщо пряма задача має оптимальний розв’язок, то має оптимальний розв’язок і її двоїста задача, при цьому має місце:

Це означає, що значення цільових функцій як прямої, так і двоїстої задач однакові.

Теорема 2. (теорема про рівновагу): допустимий розв’язок двоїстої пари задач оптимальний тоді і тільки тоді, коли виконуються умови:

Унаслідок цього, можна зробити висновок:

• якщо то

• якщо то ;

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

• якщо то

• якщо то

Це означає, що по відомим оптимальним значенням змінних (або відповідно) прямої (двоїстої) задачі, можна визначити знак обмеження двоїстої (прямої) задачі. А саме: якщо змінна прямої (двоїстої) задачі приймає нульове значення, то у відповідному обмеженні двоїстої (прямої) задачі знак нерівності зберігається, а якщо змінна ненульова, то у відповідному обмеженні ставиться знак “=”.

Теорема 3. (теорема про оцінки): значення змінних оптимального розв’язку двоїстої задачі оцінюють вплив зміни вільних членів обмежень на величину , тобто

,

або

.

4. Алгоритми відшукання оптимальних розв’язків двоїстої задачі.

1 випадок (застосовується у випадку, коли відомі тільки оптимальні значення змінних і значення цільової функції прямої задачі.)

1. Підставити оптимальні значення в обмеження прямої задачі і за допомогою 2 теореми двоїстості знайти ті змінні двоїстої задачі , які дорівнюють нулю (якщо в обмеженні виконується нерівність).

2. За оптимальними значеннями з’ясувати, який знак будуть мати обмеження двоїстої задачі, якщо в них підставити оптимальні значення (якщо =0, то в j – му обмеженні знак залишається, а якщо 0, то j – те обмеження – рівняння).

3. Поєднати в систему перетворені обмеження двоїстої задачі і розв’язати її. Розв’язок системи – оптимальні значення змінних двоїстої задачі.

4. За допомогою 1 теореми двоїстості, знайти оптимальне значення цільової функції.

2 випадок (застосовується тоді, коли відома остання симплекс таблиця з оптимальним розв’язком прямої задачі).

1. Між основними змінними прямої задачі і додатковими змінними двоїстої задачі виконується відповідність:

.

2. Між додатковими змінними прямої задачі і основними змінними двоїстої задачі виконується теж відповідність:

.

3. Якщо , то .

Якщо , то .

В симплекс – таблиці відповідність між змінними така:

	…			…		Рядок змінних прямої задачі.
	…			…
	…			…		Індексний рядок симплекс таблиці.

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

У цьому разі, згідно з теоремою 2, відповідні змінні 0. Тому змінні показують міру дефіцитності початкового і – го ресурсу: ресурс, який використовується повністю, має додатну оцінку , а ресурс, який використовується не повністю має нульову оцінку .

За допомогою теореми 3 можна проаналізувати вплив розміру початкових і – тих ресурсів на значення в разі зміни значень , не розв’язуючи її симплекс – методом заново.