3.1 Метод штучного базису
В основному у задачах лінійного програмування можна безпосередньо знайти її опорний план, якщо серед векторів Аj є m одиничних, але так буває не завжди. Тоді для побудови першого опорного плану застосовують метод штучного базису. Ідея його полягає в тому, що відсутні одиничні вектори можна дістати, увівши до відповідних обмежень базисні змінні, які називають штучними. У цільовій функції задачі штучні змінні мають коефіцієнт +М (для задачі min ) або -М ( для задачі max), де М- досить велике додатне число. Одержану в результаті додавання штучного базису задачу називають розширеною.
Теорема 5. Якщо в оптимальному плані X=(x1, x2,..., xn, xn+1,..., xn+m) розширеної задачі значення штучних змінних xn+i=0 (i=1,m), то X=(x1,x2,...,xn) є оптимальним планом задачі.
Зауваження. Штучний вектор виключений з базису, в результаті ітерацій у подальшому не має сенсу вводити у жодний базис, тобто перетворення відповідних стовпчиків зайві.
Процес ітерацій проводять доти, поки:
всі штучні вектори будуть виключені з базису, тоді базис відповідає деякому опорному плану вихідної задачі та визначення її оптимального плану продовжують по m+1 рядку;
не всі штучні вектори виключені, але рядок оцінок не вміщує більш від’ємних елементів. Якщо елемент, що стоїть у рядку оцінок стовпчика bi від’ємний, то вихідна задача не має розв’язку; якщо він дорівнює 0, то знайдений опорний план вихідної задачі вироджений та базис вміщує хоча б один з векторів штучного базису.
Якщо задача вміщує декілька одиничних векторів, то їх слідує включити до штучного базису.
Етапи розв’язування задачі лінійного програмування методом штучного базису:
скласти розширену задачу;
знайти опорний план розширеної задачі;
за допомогою звичайних перетворень симплекс-методу виключити штучні вектори з базису. В результаті або знаходять опорний план вихідної задачі, або встановлюють її нерозв’язність;
використовуючи знайдений опорний план або знаходять симплекс-методом оптимальний план вихідної задачі, або встановлюють її нерозв’язність.
Наприклад
Zmax=5x1+2x2-6x3
Приведемо задачу до канонічного вигляду:
Zmax=5x1+2x2-6x3+0x4+0x5
В першого та другому обмеженнях є базисні змінні х3 та х4, в третьому базисної змінної немає, отже вводимо штучну змінну х6, яка включається до цільової функції з коефіцієнтом -М. Одержали розширену задачу: Zmax=5x1+2x2-6x3+0x4+0x5-Mx6
Далі розширену задачу розв'язуємо за алгоритмом симплекс-метода:
|
5 |
2 |
-6 |
0 |
0 |
-М |
|
|
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
bi |
хб |
-6 0 -М |
1 3 6 |
2 5 1 |
1 0 0 |
0 1 0 |
0 0 -1 |
0 0 1 |
8 15 12 |
х3 х4 х6 |
Z1 |
-6-6M |
-12-M |
-6 |
0 |
M |
-M |
-48-12M |
|
Z1 –C1 |
-11-6M |
-14M |
0 |
0 |
M |
0 |
|
|
-6 0 5 |
0 0 1 |
11/6 9/2 1/6 |
1 0 0 |
0 1 0 |
1/6 1/2 -1/6 |
|
6 9 2 |
х3 х4 х1 |
Z2 |
5 |
-61/6 |
-6 |
0 |
-11/6 |
|
-26 |
|
Z2 –C1 |
0 |
-73/6 |
0 |
0 |
-11/6 |
|
|
|
-6 0 5 |
0 0 1 |
1/3 9 5/3 |
1 0 0 |
-1/3 2 1/3 |
0 1 0 |
|
3 18 5 |
х3 х5 х1 |
Z3 |
5 |
19/3 |
-6 |
11/3 |
0 |
|
7 |
|
Z3-C1 |
0 |
13/3 |
0 |
11/3 |
0 |
|
|
|
Отже, оптимальний план початкової задачі: Zmax=7, *=(5;0;3).