Page 24 - 6197

розв’язок – оптимальний (кінець алгоритму). Справді, із (1.22)

0
випливає, що при виконанні умови s  , j  1,n функція
j
R   x не може бути зменшена шляхом збільшення жодної
 n 
 
змінної x , оскільки доданок  s x j  більший від нуля.
j j
 j 1 
Нехай серед коефіцієнтів s є додатні. Якщо їх декілька,
j
тоді вибираємо найбільший із них:
s  max : s . (1.23)
0 l j j
Умова (1.23) забезпечує максимальний приріст цільової
R
функції   x . Стовпчик l назвемо провідним. Наступний
0
крок полягає у тому, щоб визначити, яку з базисних змінних
потрібно вилучити із базису і помістити її в число небазисних
змінних (замість x , де l набуває значень із множини
0 l 0
l  1,m ).
0
0
Оскільки s  , то спробуємо, не змінюючи нульових
0 l
значень всіх інших небазисних змінних, крім x , зменшити
0 l
цільову функцію за рахунок збільшення x . Головне при
0 l
цьому, щоб новий розв’язок був допустимим, тобто не
порушувались обмеження задачі лінійного програмування.

0
Оскільки x  , j  1,n , j  і x  , то із (1.20) випливає,
0
l
j 0 0 l
що x  b  a x . Останню формулу подамо у такому
n i i 0 il 0 l
 b 
0
вигляді: a  a  i  x . Нехай a  . Тоді x можна
n i 0 il  a 0 l  0 il 0 l
 0 il 
збільшувати до тих пір, поки одна із базисних змінних x
n i
першою досягне нульового значення. Очевидно, що такою
змінною буде та, для якої перший доданок, що знаходиться у

24