Page 20 - 6449

Скажімо, якщо виконується нестрога умова наприклад 3а), і серед
коефіцієнтів  є нульові, то в такому випадку задача має безліч мінімумів
i
– величина (1.15) може приймати значення  не лише на розв’язку (1.16),
0
але і в будь-якому іншому варіанті розв’язку задачі, в якому ненульові
значення базисних змінних вибираються для тих змінних, при яких
коефіцієнти   0 отже, відповідна задача має безліч розв’язків.
i
Існують декілька способів подання системи (1.13) у вигляді (1.14),
тобто способів вибору початкового опорного плану (початкового опорного
розв’язку) (1.16). Розглянемо основні з них:
Метод Жордана – Гауса
При реалізації вказаного методу система (1.13) розв’язується
відносно деякого набору змінних x ,......... x . шляхом приведення матриці
1 m
системи (1.13) не до трикутного, як при реалізації методу Гауса, а до
діагонального виду (1.14). Основною проблемою при цьому є

гарантування умови b  0, оскільки для матриці, заданої в загальному
i
вигляді, досить складно вибрати такі базисні змінні x , x ,......... x , , при яких
1 2 m
b i  0. При цьому часто доводиться перебирати C m n варіантів комбінацій
базисних змінних, що приводить до суттєвого росту обсягу обчислень.
Метод додаткових змінних
При вирішенні деякого достатньо широкого класу економічних
задач в якості початкового опорного плану можна вибирати базисний
розв’язок, в якому базисними будуть додаткові змінні, введені в систему
обмежень для приведення задачі до канонічного виду.
Наприклад, задача:
Z  X C  X C  X C  ......... X C  max (1.22 )
1 1 2 2 3 3 n n
за умови:
 a 11  x 1  a 12  x 2  .........  a n 1  x n  b 1

 a 21  x 1  a 22  x 2  .........  a 2 n  x n  b 2
 (1.23)
 .......... .......... .......... .......... .......... ..........
 a  x  a  x  .........  a  x  b
 m1 1 m2 2 mn n m
x  , 0 i  ,.......,1 n  m , b  , 0
i i
приводиться до канонічного виду:
 a 11  x 1  a 12  x 2 .........  a n 1  x n  x n 1  b 1

 a 21  x 1  a 22  x 2 .........  a 2 n  x n  x n 2  b 2
 (1.24)
 .......... .......... .......... .......... .......... ..........
 a  x  a  x .........  a  x  x  b
 m1 1 m2 2 mn n n m m
x  , 0 i  ,.......,1 n  m , b  , 0
i i
із збереженням цільової функції у вигляді (1.22). В такому випадку

система (1.24) аналогічна системі (1.14), і змінні x x , ,..... x можуть бути
n1 n2 n m
вибраними як базисні.

20