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

1. Заповнюємо симплексну таблицю, знаходимо оцінки , значення .

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

3. Серед від’ємних значень знаходимо найбільше по модулю число і відповідний йому стовпчик вибираємо за провідний. Нехай це буде стовпчик з номером . Якщо в провідному стовпчику всі елементи ( ), то маємо випадок 2: цільова функція необмежена і розв’язування закінчене. Якщо не всі , то перейти до п.4.

4. Для кожного додатного елемента -го (провідного) стовпчика знаходимо відношення , вибираємо найменше (тобто знаходимо симплексне відношення ), і називаємо рядок, де воно досягається, провідним. Нехай це буде рядок з номером . Елемент на перетині провідного рядка і провідного стовпця буде провідним.

5. Виконуємо жорданове перетворення таблиці від стовпця В до A_n, від 1-го рядка до ( +1)-го з провідним елементом і переходимо до кроку 2.

Послідовність операцій 2-5 називається ітерацієюсимплекс-методу.

Зауваження 1. У другій і далі таблицях і можна шукати за правилом прямокутника як і інші елементи.

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

Точнішим є таке правило: якщо не виконується умова оптимальності , , то в базис включають той вектор, якому відповідає min ∆_j, при ∆_j<0.

Якщо ж мінімальних оцінок декілька, то беруть вектор , якому відповідає максимальне .

Зауваження 3. Якщо в (1) , то умовою оптимальності плану є ∆_j≤0, j=1,…,n.

Приклад 5.1. Розв’язати задачу лінійного програмування

,

Складаємо симплекс-таблицю

		Сб					-3
					-1
		-3			-1
		-18	-5
		-3
		-3
		-3

Всі , тому базисний розв’язок є оптимальний .

Відповідь: .

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

;

, , ; .

Зведемо задачу до канонічного вигляду

;

, .

Складемо симплекс-таблицю

i				-1
					-1
				-4		-1
m + 1	∆			-1	-3
					-1
				-2
							-1
				-4
				-2
							-2	-1
			-1
			11
		-1	1

, , .

Зауваження 4. Як відзначалося, при переході від виродженого опорного плану до нового опорного плану цільова функція не збільшується. Можливий випадок, коли новий опорний план також вироджений і т.д., тоді можливе зациклення (коли вироджені плани повторюються). Для усунення зациклення і покращення розв’язку використовують таке правило. Якщо на кроці 4 алгоритму симплекс-методу досягається у декількох рядках, то треба вибрати той рядок, для якого буде найменшим відношення елементів наступного стовпчика до провідного. Якщо при цьому відношення виявляється рівним, то беруть відношення іншого стовпчика до провідного і т.д., поки не виявиться однозначно провідний елемент.

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

;

, .

Задача записана в канонічному базисному вигляді.

Складаємо симплексну таблицю

i
				-2
				-1
				-1
			-2	-4
				-2
						-5
						-1
			-10
	∆

,

Відповідь: – невироджений оптимальний план, .