4 = -3,
О” 5 = <з Б , A 5 > - c 5 = 1 в€™ 0 + 0 в€™ 0 + 2 в€™ 1 - 2 = 0.
Так як оцінка О” 4 <0, то базисний план x 0 НЕ оптимальний. Зауважимо, що сімплексні оцінки, відповідають базисним змінним, завжди дорівнюють нулю, так що досить перевіряти тільки небазисні оцінки. p> 2.2 Реалізація симплекс-методу на прикладі
Продемонструємо застосування симплекс-методу на прикладі. Розглянемо канонічну задачу ЛП
f (x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 в†’ max
(2.2)
- x 1 + 2 x 2 + x 3 = 4,
(2.3)
3 x 1 + 2 x 2 + X 4 = 12,
(2.4)
x j ≥ 0 , j = 1,2,3,4.
(2.5)
Матриця умов A = ( A 1 , A 2 , A 3 , A 4 ), де
В
Цільовий вектор c = ( C 1 , c 2 , c 3 , c 4 ) = (1, 2, 0, 0); вектор правих частин b = ( b 1 , b 2 ) = (4, 12).
Крок 0. Знаходження початкової кутової точки (базисного плану). p> Задача має переважний вид, так як праві частини рівнянь позитивні, а стовпці матриці умов A 3 , A 4 утворюють одиничну підматрицю. Значить початкова базисна матриця = ( A 3 , A 4 ); x 3 і x 4 - базисні змінні, x 1 і x 2 - небазисні змінні, c Б = ( C 3, c 4 ) == (0 , 0).
Початковий базисний план має вид x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f ( x o ) = 0 .
Крок 1. Перевірка базисного плану на оптимальність. p> Підрахуємо сімплексні оцінки для небазисних змінних за формулою (5.1)
В
пЃ„ 1 = < c Б , A 1
