Page 18 - 6449

невід’ємними, то розв’язок (1.16) є розв’язком задачі на мінімум, а якщо
всі вказані  є строго додатніми, то (1.16) – єдиний розв’язок задачі на
i
мінімум.
3б) якщо в залежності (1.15) всі коефіцієнти  ,  ..........  . є
1 2 n m

недодатними, (1.16) задає розв’язкок задачі на максимум; якщо ж всі є
i
строго від’ємними, то (1.16) – точка строгого і єдиного максимуму;
3в) якщо в залежності (1.15) коефіцієнти  ,  ..........  . мають
1 2 n m
різні знаки, то в такому випадку (1.16) не є оптимальним розв’язком, і
значення Z , що відповідає (1.16) може бути покращеним.
Пояснимо твердження 3а) (інші твердження доводяться
аналогічно): нехай в (1.15) всі коефіціенти  ,  ..........  . є строго
1 2 n m
додатніми. В такому випадку функція z в (1.15) набуває значення
z   (1.17)
0
Якщо в (1.16) хоча б одна із змінних x ,......, x набуде ненульового
m 1 n
(а отже, додатнього) значення, то через додатність коефіціентів i,
i  2,1 ,......., n  m значення (1.17) може тільки зрости. Таким чином, умови 3а);
3б); 3в); задають умови екстремуму задачі (умови (3а), (3б)), а також умову
необхідності подальшого покращення розв’язку (умова (3в)).
Таким чином, якщо виконується умова 3а), то розв’язок задачі
знаходження мінімуму знайдено. Якщо виконується умова 3б) – знайдено
розв’язок задачі на максимум, якщо ж виконується умова 3в) – розв’язок
продовжується.
Вибір змінної, що вводиться в число базисних
У даному пункті буває єдина відмінність в розв’язку задачі на
 i  2,1 ,......., n  m
мінімум та задачі на максимум. Серед коефіціентів i ,
вибираємо “найгірший”:
– у випадку пошуку мінімуму знаходимо найбільший за модулем
від’ємний коефіціент;
– у випадку пошуку максимуму знаходимо найбільший за
модулем додатній коефіціент.
Нехай знайдений “найгірший” коефіціент  відповідає змінній x .
S
S
Це означає, що змінна x буде вводитись у число базисних, і викликає
S
питання – замість якої із базисних змінних у базис буде введено змінну x .
S
Побудова нового базисного розв’язку
Виділивши змінну x , яку необхідно вводити в базис, необхідно
S
встановити, яку саме змінну необхідно вивести з числа базисних. Слід
зазначити, що всі подальші висновки стосуються як задачі на мінімум, так
і задачі на максимум.
Для відповіді на поставлене питання розглянемо в системі (1.14)
стовпчик, що відповідає змінній x . Розглянемо можливі варіанти:
S
~
– якщо серед коефіціентів a , що відповідають в системі (1.14)
is

18