Алгоритм симплекс-метода. Резюмируя изложенное в предыдущих разделах, опишем алгоритм симплекс-метода

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

Полная симплекс-таблица имеет следующую структуру.

Таблица l	C0	C 1	C 2	…	Cr	…	C	q
i	Csi	базис Asi	B=A0	A 1	A 2	…	Ar	…	A
	Cs 1	As 1	a 1 0 =xS 1	a 11	a 12	…	a 1 r	…	a 1
	Cs 2	As 2	a 2 0 =xS 2	a 21	a 22	…	a 2 r	…	a 2
…	…	…	…	…	…	…	…	…	…	…
k	Csk	Ask	ak0=xSk	ak 1	ak 2	…	akr	…	ak	q0
…	…	…	…	…	…	…	…	…	…	…
m	Csm	Asm	am0=xSm	am 1	am 2	…	amr	…	am
m +1	-am+ 1 ,j	L	Δ 1	Δ 2	…	Δr	…	Δ
m+2	zj	z0	z 1	z 2	…	zr	…	z

Здесь C_j – коэффициенты линейной формы L, C_si – коэффициенты в L при базисных переменных (подмножество C_j), A_si – базисные векторы, si – индекс базисного компонента на позиции i. Жирной линией выделена главная часть таблицы, все ее элементы подчиняются соотношениям (4.22). Первая и последняя строки и второй столбец таблицы являются вспомогательными, они обязательны только в начальной таблице.

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

Алгоритм состоит из предварительного и основного этапов.

На предварительном этапе сначала определяется начальное базисное решение одним из методов, рассмотренных выше. Исходя из него заполняется начальная симплекс-таблица. В третий столбец заносятся m базисных векторов, а во второй – соответствующие коэффициеты из L (или из верхней строки) в порядке следования условий в модели (на первую позицию ставится вектор при базисной переменной из первого условия и т.д.).

Так как начальный базис единичный, элементы главной части таблицы кроме последней строки не вычисляются, а берутся прямо из модели (в столбец A₀ заносятся правые части условий, в A_j – коэффициеты при ).

Для получения относительных оценок используются формулы (4.11) и (4.12). Значения z_j находятся как скалярное произведение векторов C_b =[ C_si ] и A_j (суммируются произведения одноименных компонент). Вычитая из нижней строки верхнюю, получаем L и оценки Δ _j.

Основной этап является итерационным.

Очередная итерация заканчивается заполнением симплекс-таблицы за исключением столбца q. Пусть завершилась l- я итерация. Цикл начинается с анализа оценок Δ_j в таблице l. Если нет отрицательных оценок, значит, выполнился признак оптимальности. В этом случае возможны два вывода:

1) если не вводились искусственные переменные или они равны нулю, получено оптимальное решение;

2) если хотя бы одна искусственная переменная не равна нулю, задача неразрешима из-за противоречивости условий.

При невыполнении признака оптимальности анализируются столбцы с отрицательными оценками. Если среди них обнаружится столбец, в котором все коэффициенты разложения неположительны, то есть a_ij £0, " i, то задача неразрешима по причине неограниченности критерия на допустимом множестве. В противном случае выбирается минимальная (отрицательная) оценка

Она определяет столбец A_r, называемый направляющим или разрешающим, или ведущим столбцом. Мы будем придерживаться первого термина.

Заполняется столбец q. Значения q вычисляются делением элементов столбца A₀ на положительные элементы направляющего столбца

По минимальному значению q определяется направляющая строка k:

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

Заполняется таблица l+1. В ней отражается смена базиса: вектор A_sk заменяется вектором A_r, соответственно вместо C_sk ставится C_r, остальные базисные элементы остаются на месте. Элементы главной части таблицы вычисляются согласно (4.22):

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

После заполнения главной части таблицы возвращаемся на начало основного этапа.

Для контроля вычислений можно проводить повторный счет оценок, используя вспомогательные строки z и C.

Наглядное представление алгоритма дает блок-схема, приведенная на рис. 4.8.

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

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

В строках с минимальным q находятся отношения q ¹ элементов 1-го столбца к элементам направляющего и выбирается строка с минимальным q ¹. Если же этот выбор снова неоднозначен, то вычисляются отношения q ¹¹ элементов 2-го и направляющего столбца в строках с минимальным q ¹, и т.д. до достижения однозначного выбора. Это правило гарантирует от зацикливания. Однако на реальных задачах сталкиваться с зацикливанием не приходилось, и поэтому изложенное правило представляет больше теоретический интерес.

4.9.7. Примеры

Пример 4.2. Для иллюстрации работы алгоритма применим его к задаче планирования, решенной графически в разд. 4.6.

Исходная модель L =7 x 1+5 x 2→max, 1) 2 x 1+3 x 2£19, 2) 2 x 1+ x 2£13, 3) 3 x 2£12, 4) 3 x 1£17, 5) x 1³0, 6) x 2³0.

Каноническая модель L =7 x 1+5 x 2→max, 2 x 1+3 x 2+ x 3=19, 2 x 1+ x 2+ x 4=13, 3 x 2+ x 5=12, 3 x 1+ x 6=17, " xj ³0.

Исходная модель соответствует первому случаю построения начального базисного решения (см. разд. 4.9.4). Следовательно, базисными переменными в начальном решении будут дополнительные переменные x ₃, x ₄, x ₅и x ₆, а базисными векторами - А ₃, А ₄, А ₅ и А ₆. Очевидно, что такое базисное решение является допустимым (опорным планом), а в геометрическом представлении это вершина в начале координат.

Имея начальное решение, заполняем начальную симплекс-таблицу. В столбцы A ₁- A ₆заносятся коэффициенты при переменных x ₁ -x ₆в канонической модели, а в A ₀– свободные члены. Так как C ₃, C ₄, C ₅ и C ₆равны нулю, то согласно (4.14) и все z_j =0. Следовательно, в этом случае Δ_j = z_j - C_j = - C_j.

Таблица 0								q
i	Csi	Баз.	A0	A 1	A 2	A 3	A 4	A 5	A 6
1		A 3								19/2
		A 4								13/2
		A 5								--
4		A 6								17/3
5	Δj		-7	-5
	zj

Анализируем таблицу. Признак оптимальности не выполняется и при этом в столбцах с отрицательными Δ _j есть положительные элементы, значит, решение можно улучшить. По минимальному значению Δ _j определяем направляющий столбец - A₁. Вычисляем q делением элементов столбца A₀ на положительные элементы направляющего столбца. По минимальному значению q находим направляющую строку – строка 2. Направляющий столбец и направляющая строка выделены в таблице серым цветом. Таким образом, из базиса выходит вектор A₆ и на его место встает A₁. Аналогичная смена происходит в базисном решении: x ₁ заменяет x ₆.

Переходим к вычислению элементов новой таблицы. Новые значения в строке 4 получаем делением элементов этой строки в начальной таблице на направляющий элемент. Остальные элементы в небазисных столбцах, столбце A₀ и новые значения Δ_j вычисляются по правилу прямоугольника. Для примера в начальной таблице показаны 2 прямоугольника, которые построены на элементах a ₁₆ и Δ₂. Они позволяют вычислить новые значения этих элементов:

a _{1 6} = 0 - (2*1)/3= -2/3; Δ₂= -5 - (-7*0)/3= -5.

В результате получаем симплекс-таблицу 1.

Таблица 1								q
i	Csi	Баз.	A0	A 1	A 2	A 3	A 4	A 5	A 6
		A 3	23/3						-2/3	23/9
		A 4	5/3						-2/3	5/3
		A 5
		A 1	17/3						1/3	--
	Δj	119/3		-5				7/3
	zj	119/3						7/3

В ней также показаны вспомогательные строки (верхняя и нижняя) и вспомогательный столбец C_si. Они предназначены для контроля вычислений оценок (непосредственно по формулам (4.14) и (4.15)), а значит, и всей таблицы. Легко проверить, что в нашем случае эти формулы дают те же значения оценок.

Следующая итерация начинается с проверок на оптимальность и разрешимость задачи, выбора направляющего элемента и заканчивается заполнением симплекс-таблицы 2.

Таблица 2								q
i	Csi	Баз.	A0	A 1	A 2	A 3	A 4	A 5	A 6
		A 3	8/3				-3		4/3
		A 2	5/3						-2/3	--
		A 5					-3			7/2
		A 1	17/3						1/3
	Δj							-1
	zj							-1

Так как оптимальное решение не достигнуто, проводим 3-ю итерацию, результаты которой представлены в табл. 3.

В этой таблице нет отрицательных оценок, что свидетельствует о достижении оптимального решения. Максимальная прибыль составляет L^* =50 при значениях переменных х^* ₁=5, х^* ₂=3, х^* ₃= х^* ₄=0, х^* ₅=3, х^* ₆=2, что полностью совпадает с результатами графического решения в разд. 4.6.

Таблица 3
i	Csi	Баз.	A0	A 1	A 2	A 3	A 4	A 5	A 6
		A 6				3/4	-9/4
		A 2				1/2	-1/2
		A 5				-3/2	3/2
		A 1				-1/4	3/4
	Δj				3/4	11/4
	zj				3/4	11/4

Пример 4.3. Рассмотрим задачу с разными видами ограничений и покажем только отличие от предыдущего примера.

Исходная модель L = 4 x 1- x 2→max, 1) 3 x 1+2 x 2£ 10, 2) 2 x 1+ x 2³ 8, 3) x 1 - 3 x 2=12, 4) x 1³0, 5) x 2³0.

Каноническая модель L = 4 x 1- x 2→max, 3 x 1+2 x 2+ x 3= 10, 2 x 1+ x 2- x 4= 8, x 1- 3 x 2= 12, " xj ³0.

Для построения начального базисного решения по 4-му варианту введем искусственные переменные x₅ и x₆. Тогда модель примет вид

L = 4 x ₁- x ₂→max,

3 x ₁+2 x ₂+ x ₃= 10,

2 x ₁+ x ₂- x ₄+ x ₅= 8,

x ₁- 3 x ₂ +x ₆= 12,

" x_j ³0.

Из нее получаем искусственное (недопустимое) базисное решение: x ₃ =10, x₅ = 8, x₆ = 12 (остальные переменные равны нулю). Соответственно базис состоит из одноименных векторов условий.

Далее можно выбрать один из способов решения:

1. решение в один этап;

2. решение в два этапа.

В первом случае критерий модифицируется введением искусственных переменных с большим весом: L^’ = 4 x ₁- x ₂ - M(x₅+x₆). Вместо символа большого числа M можно взять конкретное значение, например положить M = 100, что много больше С ₁= 4. Дальше решение проводится согласно описанному алгоритму.

При использовании второго варианта на первом этапе решается задача минимизации искусственного критерия: L_и = x₅ + x₆ →min. Если оптимальное значение этого критерия окажется отличным от нуля, исходная задача неразрешима из-за противоречивости условий. Нулевое значение будет свидетельствовать о достижении допустимого базисного решения, которое принимается за начальное для второго этапа. На нем решается задача по исходному критерию L. При этом в последней таблице первого этапа относительные оценки по критерию L_и заменяются оценками по критерию L. Они вычисляются так же, как в начальной таблице.