Алгоритм симплекс-метода

Этот алгоритм целесообразно рассмотреть на конкретном примере.

Пример. Решить симплекс-методом следующую ЗЛП:

	(1)
	(2)
	(3)

Эта задача относится к задаче об использовании ресурсов. Здесь в качестве свободных членов в правой части нетривиальных ограничений стоят запасы сырья трех видов. Такая задача удобна тем, что каноническая форма совпадает с симплексной, и не нужно прибегать к специальным приемам для её получения. Исходная задача в каноническом виде выглядит так:

	(4)
	(5)
	(6)

Систему отграничений-равенств можно записать в векторной форме

+ + + + = ,

где = ; = ; = ; = ; = ; = .

Здесь векторы , и имеют предпочтительный вид, т.е. являются единичными в одном из компонентов и нулевыми во всех остальных компонентах. Вектор называется столбцом свободных членов системы ограничений.

Для решения задачи (4)-(6) симплекс - методом необходимо иметь опорный план, т.е. допустимое базисное решение системы (5). Для этого все векторы надо разделить на две группы – базисные и свободные. Сначала выбираем базисные. Поскольку нетривиальных ограничений всего три, то и базисных векторов будет тоже три. В качестве базисных выбирают вектора, имеющие предпочтительный вид, т.е. в данном случае , и . Им соответствуют базисные переменные х ₃, х ₄, х ₅ системы (5). Остальные переменные (х ₁ и х ₂) будут свободными. При получении базисного решения все свободные переменные приравниваются к нулю. Подставив в (5) х ₁= х ₂=0, легко получаем остальные компоненты опорного плана:

х ₃ = 400; х ₄ = 900; х ₅ = 600.

В векторном виде этот опорный план выглядит так:

= (0; 0; 400; 900; 600).

Подставив компоненты в целевую функцию (4), получим значение целевой функции для этого плана:

Z ()=0.

Теперь составим первоначальную симплексную таблицу:

Сб	Б
0								=200
								=300
								=600
z j - c j		- 60	- 40

В верхней строке, над обозначениями векторов, стоят коэффициенты целевой функции при соответствующих переменных. Нулевое значение над говорит о том, что свободный член в целевой функции отсутствует. Нижняя строка таблицы, которая называется индексной строкой, содержит взятые с обратным знаком значения коэффициентов из верхней строки.

Второй столбец таблицы состоит из обозначений базисных векторов. Порядок, в котором они записаны, не случаен. Каждый вектор поставлен в той строке, где в столбце коэффициентов этого вектора находится единица. Слева от базисных векторов, в первом столбце таблицы, поставлены соответствующие коэффициенты целевой функции (из верхней строки).

Последний столбец рассмотрим позже.

Теперь, когда начальная таблица построена, известен соответствующий опорный план и значения целевой функции, нужно сделать вывод о том, можно ли улучшить целевую функцию. Ответ на этот вопрос дает содержимое индексной строки: в случае отсутствия там отрицательных чисел делается вывод о том, что достигнутый опорный план является оптимальным и целевую функцию нельзя увеличить, т.е. сделать больше. В противном случае целевую функцию можно улучшить. Поскольку в данном случае в индексной строке есть отрицательные числа, план не является оптимальным, и его можно улучшить.

Переход к новому, лучшему опорному плану называется итерацией симплекс-метода. Она представляет собой преобразование однократного замещения, поскольку при этом происходит переход к новому базису: один из базисных векторов становится свободным, а в базис, наоборот, входит один из бывших свободных векторов.

Найдем эту пару векторов. Сначала определим вектор, который войдет в базис. Это должен быть один из свободных векторов, т.е. или . Выбираем тот вектор, которому в индексной строке соответствует самое отрицательное число (-60, обведено пунктиром). Значит, вектор становится базисным.

Теперь определим вектор, “покидающий” базис. Это делается с помощью симплексных отношений, обозначенных в последнем столбце симплекс–таблицы. Как видно из заголовка столбца, числителем симплексного отношения является свободный член ограничения, а знаменателем – положительные коэффициенты ведущего столбца, т.е. столбца (вектора, который теперь войдет в базис). Строка, в которой находится минимальное симплексное отношение, называется ведущей строкой. В той же строке находится вектор , покидающий наш первоначальный базис. Только при этом условии гарантируется неотрицательность свободных членов при пересчете таблицы. Отметим также, что при симплексные отношения являются недопустимыми или не существуют; их не следует рассматривать при определении минимального отношения.

Элемент таблицы, находящийся на пересечении ведущего столбца и ведущей строки, называется ведущим элементом таблицы (он обозначен сплошным квадратом).

Теперь приступим к пересчету таблицы. Это делается в три этапа. Сначала ведущая строка делится на ведущий элемент:

Сб	Б
z j - c j

 

Обратите внимание, что во втором столбце вместо уже стоит новый базисный вектор с коэффициентом 60 в столбце С_б.

Далее впишем в эту таблицу столбцы новых базисных векторов. При этом, поскольку и остались в базисе, их столбцы остаются без изменений, а столбец становится точно таким же, каким до этого был :

 

 

Сб	Б
z j - c j

 

Наконец, на третьем этапе определим значения в оставшихся девяти клетках таблицы. Их нужно пересчитать по правилу прямоугольника.

Чтобы сформулировать это правило, снова посмотрим на первоначальную симплекс-таблицу. Обратите внимание, что оставшиеся неизвестными элементы новой таблицы в первоначальной таблице соответствуют элементам, стоящим наискосок к ведущему элементу (поскольку ведущая строка и ведущий столбец уже построены).

Для любого элемента первоначальной таблицы можно определить прямоугольник

а ^* В

 

А а

Здесь - ведущий элемент, а - искомый элемент, А, В – элементы, находящиеся с ними на пересечении строк и столбцов.

Новое значение элемента а получается из формулы:

Это и есть правило прямоугольника.

Например, для прямоугольника, обозначенного в первоначальной таблице, в новой таблице получаем значение:

0 - = -

Все остальные значения пересчитываются аналогично. Получаем таблицу первой итерации симплекс-метода:

 

Сб	Б
								400
0					- 1,5			=120
					-			160
z j - c j			- 10

Произошел переход к новому базису: , , . При этом переменные х _2, х ₃ являются свободными, и в опорном плане их значения равны нулю. Значения остальных переменных получаем из нового столбца свободных членов:

х₁ = 200; х ₄ = 300; х ₅ = 400.

Запишем опорный план в векторной форме:

= (200; 0; 0; 300; 400).

Этому плану соответствует значение целевой функции, равное 12000 (проверьте подстановкой компонент в выражение (4)). В новой таблице это значение зафиксировано в индексной строке в столбце свободных членов.

Как видим, в индексной строке остался один отрицательный элемент, поэтому полученный план не является оптимальным. Значение -10 находится в столбце , поэтому войдет в новый базис. Минимальное симплексное отношение достигается в строке базисного вектора , который выходит из базиса.

Теперь пересчитываем таблицу первой итерации и получаем таблицу второй итерации:

Сб	Б
					4/5	- 1/5
					- 3/5	2/5
						- 1
z j - c j

Аналогично определяем новый опорный план:

= (140; 120; 0; 0; 100).

Ему соответствует значение целевой функции, равное 13200. Поскольку в индексной строке уже нет отрицательных элементов, план является оптимальным:

; =13200.

Итак, задача линейного программирования решена.