- •Дослідження операцій
- •Загальна задача лп. Допустима область та її властивості. Поняття вершини допустимої області, базисного (опорного) плану задачі.
- •Стандартна задача лп. Зведення загальної задачі до стандартної. Канонічна задача лп. Зведення стандартної задачі до канонічної.
- •1. Алгоритм симплекс-методу.
- •Симплексні перетворення. Відносні оцінки змінних. Критерій оптимальності базисного плану. Ознака необмеженості цільової функції. Алгоритм симплексного методу.
- •Побудова початкового базисного плану. Метод штучної бази. М-метод.
- •Двоїстість в лп. Несиметрична та симетрична пари двоїстих задач. Теореми двоїстості. Двоїстий симплекс-метод.
Побудова початкового базисного плану. Метод штучної бази. М-метод.
Побудова початкового базисного розв’язку.
1. Розглянемо задачу лінійного програмування:
В кожному з непрямих обмежень стоїть “ ”. Задача легко зводиться до канонічної задачі, шляхом введення в розгляд нових змінних . Тоді отримаємо нові вектори . Отже, наша задача набуде вигляду:
2. Розглянемо задачу лінійного програмування:
В кожному з непрямих обмежень стоїть “ ”. Задача зводиться до канонічної задачі, шляхом введення в розгляд нових змінних . Тоді . Отже, наша задача набуде вигляду:
Отриману задачу можна канонізувати, наприклад, таким чином: , де l-те рівняння переписуємо без зміни, а i-те рівняння ( )замінюємо різницею між l-тим та i-тим рівнянням
Задача майже канонізується (не вистачає l-го стовпчика, що відповідає уl). Пробуємо ввести в число базисних змінних змінну хк, таку що , в k-ому стовпчику робимо нулі крім l-ого місця. Навіть якщо існує таке k, що , система може не канонізуватися, бо при виключенні із рівнянь деякі праві частини можуть стати від’ємними. Отже, потрібно додати ще таку умову: . В іншому випадку канонізувати не можна.
2.1. Метод штучної бази – це універсальний метод, який застосовується до стандартної задачі лінійного програмування:
Для розв’язання даної задачі розглянемо нову задачу лінійного програмування (допоміжну):
При розв’язанні такої задачі маємо, що . Функція яка мінімізується – обмежена знизу.
Маємо такі випадки:
де – оптимальний план допоміжної задачі.
Теорема. Якщо , то – опорний план (базисний розв’язок). Якщо хоча б одна із компонент відмінна від нуля, наприклад , то множина допустимих значень в початковій задачі порожня, тобто не існує розв’язків.
Недолік методу штучної бази в тому, що для знаходження базисного плану задачі потрібно повністю розв’язати нову задачу.
2.2. М-метод побудови базисного плану. Розглянемо разом із задачею лінійного програмування допоміжну задачу (М-задачу):
умова є неістотною.
В цій задачі число М – невід’ємне і достатньо велике, більше ніж будь-які числа, які будуть зустрічатися в даній задачі.
Теорема. Якщо оптимальний розв’язок М-задачі має вигляд: , то є оптимальним розв’язком початкової задачі.
Наслідок. 1. Якщо в оптимальному розв’язку М-задачі хоча б одна компонента , то множина допустимих планів початкової задачі порожня.
2. Якщо допоміжна задача не має розв’язку, в тому розумінні, що , то початкова задача теж не має розв’язку, в тому розумінні, що .
Приклад. Нехай задано деяку задачу лінійного програмування:
Допоміжна М-задача буде мати вигляд:
Ця задача тепер в канонічній формі, тому можна розв’язати її за допомогою симплекс-методу. Побудуємо симплекс-таблицю.
№ ітерації |
базисні змінні |
|
1 |
-3 |
2 |
М |
М |
|
|
Примітки |
|
|
|
|
|
||||||
0 |
|
М |
1 |
2 |
3 |
1 |
0 |
4 |
4/3 |
– ввести – вивести |
|
М |
-1 |
-4 |
10 |
0 |
1 |
7 |
7/10 |
||
|
11М |
1 |
-3+2М |
2-13М |
0 |
0 |
|
|
||
1 |
|
М |
13/10 |
32/10 |
0 |
1 |
-3/10 |
19/10 |
19/32 |
– ввести – вивести |
|
2 |
-1/10 |
-4/10 |
1 |
0 |
1/10 |
7/10 |
- |
||
|
|
|
|
0 |
0 |
|
|
|
||
2 |
|
-3 |
13/32 |
1 |
0 |
10/32 |
-3/32 |
19/32 |
|
|
|
2 |
2/32 |
0 |
1 |
4/32 |
2/32 |
30/32 |
|
||
|
3/32 |
7/32 |
0 |
0 |
|
|
|
|
Всі відносні оцінки невід’ємні. Отже, знайдений розв’язок є оптимальним. . Оскільки введені, допоміжні, змінні рівні нулю, то оптимальний розв’язок заданої (початкової) задачі буде: .