Page 21 - 6197

Sp 2. Перейти від першого допустимого базисного
розв’язку до наступного таким чином, щоб відбулося
зменшення (збільшення) цільової функції.
Sp 3. Продовжити такий перехід до досягнення
найменшого (найбільшого) значення цільової функції або
виявиться, що задача лінійного програмування немає
розв’язку.
Для реалізації запропонованого алгоритму необхідно:
а) визначити перший допустимий базисний розв’язок;
б) перейти від одного до другого базисного розв’язку;
в) визначити критерій зупинки алгоритму.
Аналіз (1.15) показує, що розв’язок

x  x   x  0, x  b , i  1,m
1 2 n n i i
є допустимим базисним розв’язком. Справді, коефіцієнти при
базисних змінних x , i  1,m утворюють у матриці A
n i
одиничну підматрицю розміром m m , яка є неособливою.
З рівняння (1.18) визначимо базисні змінні
n
i 
x  b  a x , i  1,m . (1.20)
n i ij j
j 1 
Цільову функцію (1.17) запишемо у такому вигляді:
n m
j 
R   x   c x  c x  . (1.21)
n i n i
j
j 1  i 1
Величини c , i  1,m вибирають так, щоб та частина
n i
функції мети, яка залежить від доповнюючи змінних,
дорівнювала нулеві. Очевидно, що для початкового базису
c  0 , i  1,m .
n i
Значення x , i  1,m із (1.20) підставимо у вираз для
n i
цільової функції (1.21). Внаслідок отримаємо

21