Page 24 - 4168

Канонічний запис задачі ЛП:
z=с 0-(с 1x 1+ с 2x 2+…+ с nx n) ⇒ min,
y 1=b 1-(a 11x 1+ a 12x 2+…+ a 1nx n),
y 2=b 2-(a 21x 1+ a 22x 2+…+ a 2nx n),
……………………………………
y m=b m-(a m1x 1+ a m2x 2+…+ a mnx n),
x i≥(0…n); y i≥0 (0…m); m<n.
Симплекс таблиця
Вільна
Параметр частина x 1 x 2 … x n
z c 0 c 1 c 2 … c n
y 1 b 1 a 11 a 21 … a 1n
y 2 b 2 a 21 a 22 … a 2n
… … … … … …
y m b m a m1 a m2 … a mn
Є базові і вільні змінні.
Пошук оптимального розв’язку виконується шляхом об-
міну базових і вільних змінних.
Алгоритм симплекс-методу:
1. Початковий розв’язок отримується шляхом прирівню-
вання до 0 n-m (базових) змінних.
2. Виділити ведучий стовпчик за найбільшим із додатніх
коефіцієнтів с i 1-ї стрічки (z).
3. Виділяється ведучий рядок, який відповідає най-
b
меншому додатному значенню i , a ij ≥ 0. з ведучого стовпчи-
a ij
ка.
4. Визначається ведучий елемент a ij і визначається
1
λ = , яке записується в нижній половині цієї клітинки.
a ij
5. Всі елементи ведучої стрічки (крім a ij) множаться на λ і
результат записується у нижню частину кліток.
6. Всі елементи ведучого стовпчика (крім a ij) множиться
на – λ і результат записується у нижню частину кліток.
7. У ведучій стрічці обвести всі верхні елементи, крім a ij,
а у ведучому стовпчику всі нижні.

24