Page 19 - 6449
P. 19
змінній x немає додатних, тобто
S
~
a , 0 i 1 ,......., m, (1.18)
is
то відповідна задача знаходження екстремуму не має розв’язку, бо
неоптимальний план (1.16) не можна покращити, тому розв’язок задачі на
цьому закінчено;
~
– якщо серед коефіціентів a , що відповідають у системі (1.14)
is
змінній x є додатні величини, то розв’язок задачі можна покращити: в
S
~
цьому випадку для кожного додатного a шукаємо відношення:
is
~
b
~
i , i 1 ,......., m; a 0. (1.19)
~
a is
is
Знаходимо:
~
min i
b
~ 0 ~ (1.20)
a
is
is a
і встановлюємо номер рівняння K , якому відповідає виконання умови
(1.20). Фактично нас буде цікавити не власне величина (1.20), а саме номер
рівняння, в якому досягається цей мінімум. Знайшовши значення К,
робимо такий висновок: змінна x буде вводитись у число базисних
S
замість змінної x , яка є базисною в рівнянні номер К. Цей перехід буде
K
здійснюватися таким чином: стовпчик у перетвореній системі (1.14), який
відовідає змінній x , шляхом елементарних перетворень системи (1.14)
S
повинен бути перетворений до одиничного виду, причому одиниця буде
буде в рівнянні за номером K :
~
a 1 s 0
~
a 2 s 0
a ~ 0
3 s
. . (1.21)
. 0
a ~ 1 рівняння №K
ws
. 0
. .
~
a ms 0
Слід зазначити, що використання умови (1.20) дозволяє при
перетворенні системи (1.14) за законом (1.21) гарантувати виконання
основних вимог, при яких взагалі має зміст симплекс – метод, а саме:
x 0 b 0
i , i .
Таким чином, здійснено перехід від одного базисного розв’язку до
іншого, який відрізняється від попереднього лише однією базисною
змінною: замість x вводиться змінна x . Після цього алгоритм
4 3
повертається в точку, що визначається пунктом 2. За скінчену кількість
кроків вдається або встановити наявність єдиного розв’язку (виконується
строгі умови 3а) або 3б)); або відсутність розв’язку (умова (1.18)), або ж
встановити, що задача має безліч розв’язків (нестрогі умови 3а) або 3б)).
19