Page 36 - 6197

x  0 , j  1,n ; x  0 , i   1,m k ; w  , i  1,r . (1.35)
k
0
j n i i
Із рівнянь (1.32) і (1.33) визначимо
n
i 
w  b  a x , i  1,k ,
i ij j
j 1
n
w  b  x n i  a x , i   1,r

k
i i ij j
j 1
і, підставивши їх в (1.31), отримуємо цільову функцію, яка
підлягає мінімізації.
За умови невід’ємності штучних змінних мінімальне
значення цільової функції (1.31) можливе лише у тому
випадку, коли всі штучні змінні дорівнюватимуть нулеві. Тоді
мінімальне значення цільової функції (1.31) також
дорівнюватиме нулю. У тому випадку, коли мінімум функції
(1.31) відмінний від нуля, початкова задача лінійного
програмування не має розв’язку.
Другий етап. Базисний розв’язок, отриманий на першому
етапі, використовується як початковий базисний розв’язок
задачі.
Реалізацію двоетапного методу проілюструємо
конкретним прикладом.
Приклад 1.3. Знайти
min : R   2x  x  x
1
2
за умови, що
4x  x  4 ,
1 2
x  x  2,
1 2
2x  5x  10 ,
1 2
0
x  0 , x  .
1 2
Перший етап. Приведемо обмеження задачі до
канонічного вигляду та введемо штучні змінні у першу та
другу умови. Тоді

36