Page 14 - 4719

• Для нерівності типу < до лівої частини додається у,
якщо нерівність типу > від лівої частини віднімається у.
3. Z підлягає максимізації.
Пошук оптимального розв’язку виконується шляхом
переходу від якогось базового розв’язку до суміжної точки в
напрямку z ⇒ max.
Канонічний запис задачі ЛП:
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

13