Page 20 - 6197

n
 a x  x n i  b , i  1,m , (1.18)
ij
j
i
j 1 
x  0 , j  1,m , b  , i  1,m (1.19)
0
j i
або у матричній формі
Ax  b ,
де
 a a  a 1 0 0  0 
11 12 1n
 a a  a 0 1 0  0 
A   21 22 2n  - матриця
         
 
 a m 1 a m 2  a mn 0 0 0  1 
 b 
1
 b 
складена із коефіцієнтів при змінних x , j  1,n m ; b   2 
j
 
 
 b m
- вектор, компоненти якого величини b , i  1,m .
i
У симплекс-методі є особлива форма допустимого плану,
названа допустимим базисним розв’язком. Змінні, які
відповідають базисному розв’язку, утворюють базис.
Базисом називається такий набір із m змінних, при якому
матриця складена із коефіцієнтів при цих змінних, неособлива
(регулярна).
В основі симплекс-методу розв’язання задач лінійного
програмування лежить теорема 3, зміст якої у тому, що
кожний допустимий базисний розв’язок системи рівнянь
(1.18) – це крайня точка множини X і, навпаки, кожна крайня
точка множини X - це допустимий базисний розв’язок.
Згідно з цим симплекс-метод допускає такі кроки:
Sp 1. Знайти допустимий базисний розв’язок обмежуючих
рівнянь (1.18).

20