1.3. Симплекс-метод розв’язання задачі лінійного програмування

Графічний метод розв’язання ЗЛП доцільно використовувати тільки для задач з двома змінними. У разі більшого числа змінних використовують універсальний метод розв’язання ЗЛП – симплекс-метод.

У основі симплекс-метода лежить алгоритм симплексних перетворень системи лінійних рівнянь, доповнений правилом, яке забезпечує перехід до кращого опорного плану.

Алгоритм симплекс-метода розв’язання злп

1. Побудова симплексної таблиці.

2. Визначення початкового опорного плану ЗЛП.

3. Перевірка опорного плану на оптимальність за допомогою оцінок оптимальності. Якщо всі оцінки задовольняють умові оптимальності, то опорний план є оптимальним. Якщо хоч би одна з оцінок не задовольняє умові оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задача не має.

4. Перехід до нового опорного плану задачі здійснюється шляхом визначення розв’язувального елементу і побудовою наступної симплексної таблиці.

5. Повторення дій, починаючи з п.3.

Розглянемо алгоритм симплекс-метода на прикладі.

Приклад 1.3.1. Розв’язати ЗЛП (1.2.1), (1.2.2) симплекс-методом;

(1.2.1)

max z = x₁ + 4x₂ (1.2.2)

Розв’язання.

Для розв’язання ЗЛП необхідно, щоб всі вільні члени системи обмежень (1.2.1) були невід’ємними. Для цього першу нерівність системи помножимо на (–1):

(1.3.1)

Зауваження. Якщо потрібно максимізувати цільову функцію, то зручніше перейти до знаходження мінімуму max z = – min(– z).

Перейдемо до мінімуму в наший задачі:

min(– z) = – x₁ – 4x₂

Приведемо задачу до канонічної форми, вводячи додаткові змінні x₃, x₄, x₅ в систему обмежень (1.3.1).

Зауваження. Якщо нерівність системи обмежень ЗЛП має знак “ ”, то додаткову змінну вводять із знаком “+”; якщо нерівність має знак “ ”, то додаткову змінну вводять із знаком “– ”.

ЗЛП (1.3.1) в канонічній формі має наступний вигляд:

min(– z)= – x₁ – 4x₂

Для отримання одиничної матриці, складеної з векторів при базисних змінних, введемо штучні змінні в систему обмежень: якщо додаткова змінна має знак мінус, то в це рівняння вводять штучну змінну із знаком плюс; якщо додаткова змінна має знак плюс, то в це рівняння штучну змінну вводити не потрібно. Штучні змінні одночасно вводять в цільову функцію z з невідомим додатним коефіцієнтом М.

(1.3.2)

min(– z)= – x₁ – 4x₂ + Мx₆ + Мx₇.

У векторній формі система обмежень (1.3.2) має вигляд

р₁x₁ + р₂x₂ + р₃x₃ + р₄x₄ + р₅x₅ + р₆x₆ + р₇x₇ = р₀,

де р₁ = , р₂ = , р₃ = , р₄ = , р₅ = , р₆ = , р₇ = , р₀ =

Змінні x₁ і x₂ є основними, x₃, x₄, x₅ – додатковими, x₆, x₇ – штучними. Вектори р_6, р₄, р₇ утворюють одиничний базис, причому р₆ – перший базисний вектор.

Заповнимо першу симплекс-таблицю. Початкова симплекс-таблиця заповнюється таким чином. У першому рядку записують коефіцієнти цільової функції. У стовпець “Базис” записують базисні вектори. У стовпці “С” записують коефіцієнти цільової функції при базисних векторах. У стовпцях “р₀”, “р₁”, “р₂”, “р₃”, “р₄”, “р₅”, “р₆”, “р₇” записують компоненти відповідних векторів.

Для заповнення кліток таблиці, які знаходяться в двох останніх рядках потрібно елементи стовпця “С” помножити на відповідні елементи стовпця, що розраховується, і відняти число, що стоїть в першому рядку (за винятком стовпця “р₀”). Наприклад, для заповнення кліток стовпця “р₂” помножимо елементи стовпця “С” на відповідні елементи стовпця “р₂” і віднімемо число – 4: М·5 + 0·1 + М·1 – (– 4) = 4 + 6М. У клітку на перетині стовпця “р₂” і z-рядка записують 4, а в клітку на перетині стовпця “р₂” і М-рядка записують 6.

Таблиця 1.3.1

Перша симплексна таблиця

Базис	С	р0	– 1	– 4	0	0	0	М	М
			р1	р2	р3	р4	р5	р6	р7
р6	М	5	1	5	–1	0	0	1	0	5/1
р4	0	6	1	1	0	1	0	0	0	6/1
р7	М	7	7	1	0	0	–1	0	1	7/7
z-рядок		0	1	4	0	0	0	0	0
М-рядок		12	8	6	–1	0	–1	0	0

Останні два рядки симплекс-таблицы називають індексними. У них, починаючи зі стовпця “р₁”, містяться оцінки оптимальності, за допомогою яких перевіряють оптимальність опорного плану, відповідного даній таблиці. Значення складових опорного плану розташоване в стовпці “р₀”, причому небазисним змінним відповідають нульові значення.

Першій симплекс-таблиці 1.3.1 відповідає опорний план:

x₁ = 0, x₂ = 0, x₃ = 0, х₄ = 6, x₅ = 0, x₆ = 5, x₇ = 7.

Критерій оптимальності перевіряють за М-рядком, а якщо він відсутній, то за z-рядком.