Page 22 - 6449

потрібно знайти розв’язок задачі на мінімум. У такому випадку функція
(1.25) записується у вигляді:

Z  X C  X C  X C  ......... X C  Mx  Mx  ....... Mx  min,(1.28)
1 1 2 2 3 3 n n n 1  n  2 n m
причому коефіцієнти M вибираються таким чином, що M  C , i 1 ,....., n
i
(ця умова практично рівносильна умові M  ). В такому випадку
очевидно, що розв’язок задачі (1.28) з умовами (1.27) співпадатиме з
розв’язком (1.25) при умовах (1.26) – дійсно, можна очікувати, що
елементи штучного базису x x , ,..... x не будуть входити в базисний
n1 n2 n m
оптимальний розв’язок (1.28) – (1.27), оскільки в (1.28) змінні

x x , ,..... x не можуть набувати додатних значень – в такому випадку
n1 n2 n m
значення функції Z в (1.28) прямуватимуть до  , і ні про який мінімум

не може бути мови. Якщо ж ненульові значення прийматимуть лише
змінні x , x ,.... x , які входитимуть в базис оптимального розв’язку, то в
1 2 n
такому випадку очевидно, що розв’язки (1.25) – (1.26) та (1.28) з умовами
(1.27) співпадатимуть.
Очевидно, що якщо задачі (1.25) та (1.28) будуть задачами
знаходження максимуму, то при загальному збереженні форми запису
функції (1.28) коефіціенти М будуть мати такий вигляд:
M   ; M  C ;i 1 ,....., n, (1.29)
i
при цьому пояснення такої структури функції Z є аналогічним (з
точністю до знаку) до випадку задачі пошуку мімімуму.
Недоліком методу штучного базису є те, що використання його
пов’язано з суттєвим збільшенням об’єму обчислень, оскільки
збільшується кількість невідомих задачі. В той же час, ця обставина стає
несуттєвою, якщо алгоритм розв’язку реалізовано у вигляді програми для
проведення розрахунків на ЕОМ.

1.4 Метод симплекс-таблиць
З метою практичної реалізації методики знаходження розв’язку
ЗЛП симплекс-методом була розроблена методика компактного запису
розв’язку ЗЛП. Цей метод дістав назву методу симплекс-таблиць.
Розглянемо методику на конкретному прикладі:
Приклад 3: Знайти розв’язок задачі лінійного програмування:
z  2x  5x  x  x  8x  min ,
1 2 3 4 5
 x 1  x 2  2x 3 3x 4  4x 5  40
при умовах:  , x i  0
x  2x  3x  4x  5x  48
 1 2 3 4 5
На першому кроці розв’яжемо систему обмежень відносно деяких
двох змінних з дотриманням умови b  0. У даному випадку розв’яжемо
i
систему відносно змінних x та x :
1 2
1 1 2 3 4 40  1 1 2 3 4 40  1 0 1 2 3 32 
       
 1 2 3 4 5 48   0 1 1 1 1 8   0 1 1 1 1 8 
     

22