Page 17 - 6449

min
Z  X 1 C 1  X 2 C 2  X 3 C 3  ......... X n C n  (1.12)
max
за умови x  :
0
i
 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.13)
 .......... .......... .......... .......... .......... ..........
 a  x  a  x .........  a  x  b
 m1 1 m2 2 mn n m
будь-яку ЗЛП можна звести до вигляду 1( . 12 ) . 1 ( 13 )
Алгебраїчний алгоритм симплекс-методу
1. Розв’яжемо систему (1.13) відносно деяких m змінних. Не
порушуючи узагальненості викладання, вважатимемо, що це – перші m
змінних.
При цьому система (1.13) записується в такому вигляді:
~
~
~
 x 1  a m , 1 1  x m 1 ....  a s , 1 x s ....  a n 1  x n  b ~ 1
 ~ ~ ~ ~
 x 2  a m , 2 1  x m 1 ....  a s , 2 x s ....  a 2 n  x n  b 2
 ~ ~ ~ ~
 x 3  a m , 3 1  x m 1 ....  a s , 3 x s ....  a 3 n  x n  b , x i  , 0 b j  , 0 j 1 ,......., m (1.14)
3
 .......... .......... .......... .......... .......... .......... .......... ...
 ~
~
~
~
x  a  x ....  a x ....  a  x  b
 m m, m 1 m 1 ms s mn n m
Важливим моментом є те, що система (1.14) завжди може бути
записана в указаному вигляді з дотриманням важливої для подальших
, 0
викладок умови x  b j  , 0 j 1 ,......., m .
i
У системі (1.14) змінні x , x ,......, x називаються базисними, а змінні
1 2 m
~
x ,......, x – небазисними або вільними. Знаки над елементами a
ij
m 1 n
~
означають, що елементи a зазнали перетворень.
ij
Базисні змінні x ,......, , виражені через небазисні в спосіб,
x
1 m
описаний системою (1.14), підставимо в цільову функцію (1.12) і
приведемо подібні доданки. В такому випадку функція (1.12) набуває
наступного вигляду:
z     x    x  .......    x   x  (1.15)
0 1 m1 2 m2 s s n m n
Побудуємо базисний розв’язок задачі, задаючи небазисним змінним
нульові значення.
В такому випадку одержуємо базисний розв’язок виду:
~
 x 1  b 1
 ~
 x 2  b 2

 .......... ... (1.16)
 ~
 x m  b m
x  x  ........  x  0
 m 1 m 2 n
Сформулюємо умови знаходження мінімуму та максимуму функції
Z (1.12):
3а) якщо в залежності (1.15) всі коефіцієнти  ,  ..........  . є
1 2 n m

17