 |
Розв’язування двоїстої задачі
|
|
|
|
Використовуючи перші дві теореми та при відомому розв’язку однієї із задач двоїстої пари, можна знайти розв’язок другої задачі з цієї пари. Таким чином, теореми двоїстості дають змогу на основі розв’язку однієї задачі лінійного програмування знайти розв’язок двоїстої до неї задачі..
Така необхідність виникає тоді, коли є деякі труднощі у розв’язуванні однієї з двоїстої пари задач. Крім того, обсяг обчислень при використанні симплекс-методу залежить від кількості обмежень, тому доцільно розв’язувати одну із задач двоїстої пари з меншою кількістю обмежень. Якщо задача має п обмежень, то практично доведено, що для знаходження розв’язку такої задачі буде потрібно зробити приблизно 
арифметичних операцій.
Згідно з теоремою 2 можна виконати аналіз на дефіцитність тих або інших ресурсів, які задані в задачі. Справді, якщо повністю використовується і -й ресурс, то відповідне обмеження стає строгим рівнянням, тобто
У цьому разі згідно з теоремою 2 відповідні змінні двоїстої задачі 
.
Тому змінні 
показують міру дефіцитності початкових ресурсів: ресурс, який використовується повністю, має невід’ємну оцінку, а ресурс, який використовується не повністю – нульову.
За допомогою теореми 3 можна проаналізувати вплив розміру початкових і- х ресурсів на значення 
без повторення розв’язування задачі в разі зміни значення 
.
Якщо відомий розв’язок однієї із задач двоїстої пари, то розв’язок другої задачі з цієї пари можна знайти без її розв’язування симплекс-методом. При цьому можливі такі випадки.
Першій випадок. Оптимальний розв’язок однієї задачі з двоїстої пари наведено у вигляді симплекс-таблиці. Згідно з теоремою 1 використовується така відповідність
|
|
|
та 
причому: якщо 
, то 
,
якщо 
, то 
.
Це означає, що кількість змінних 
дорівнює кількості основних змінних , а кількість змінних 
дорівнює кількості основних змінних 
.
Відповідність змінних симплекс-таблиці така:
– рядок змінних прямої задачі;
– рядок величин 
, тобто індексний ря-док симплекс-таблиці, який відображує змінні двоїстої задачі .
Така форма зручна для аналізу добутих розв’язків, коли відома оптимальна симплекс-таблиця.
Другий випадок. Відомі тільки значення змінних та цільова функція однієї із задач двоїстої пари. При цьому використовують теорему 2:
відомі змінні підставляють в обмеження розв’язаної задачі та за знаком „=” чи „ 
” встановлюють, які змінні нерозв’язаної задачі дорівнюють нулю; потім за значенням змінних (які дорівнюють або не дорівнюють нулю) розв’язаної задачі встановлюють, які обмеження другої задачі перетворюються на строгі рівняння; з цих рівнянь складають систему рівнянь, яку розв’язують відносно змінних нерозв’язаної задачі.
Розглянемо приклад.
Необхідно знайти оптимальний розв’язок наступної задачі лінійного програмування:
а потім згідно з теоремами двоїстості знайти оптимальний розв’язок двоїстої їй задачі
Розглянемо два випадки.
Перший випадок. Відомий оптимальний розв’язок прямої задачі у вигляді симплекс-таблиці:
| 
| 
| 
| 
| |||
|
| -2/3 | 7/3 | |||||
| 1/3 | -2/3 | |||||
|
| 1/3 | 1/3 | |||||
|
Згідно з цією симплекс-таблицею маємо
тобто 
та 
.
Другий випадок. Проаналізуємо значення 
:
підставимо значення та 
в обмеження, а потім з’ясуємо, які змінні стають нульовими:
Згідно зі значеннями з’ясуємо, які обмеження двоїстої задачі стають строгими рівняннями:
Унаслідок такого аналізу розв’язок двоїстої задачі такий:
|
|
|
та .
|
|
|
А) Метод Гаусса розв’язування систем лінійних рівнянь
Б) Метод Крамера розв’язування систем лінійних рівнянь
Блок – схема до розв’язування задач
Блок – схема до розв’язування задач.
Взаємно двоїсті задачі
ВЛАСТИВОСТІ ОСНОВНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ГЕОМЕТРИЧНЕ ТЛУМАЧЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
ВПРАВИ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗУВАННЯ
ВПРАВИ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗУВАННЯ
ВПРАВИ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗУВАННЯ
ВПРАВИ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗУВАННЯ
