Симплексный метод решения ЗЛП (стр. 3 из 5)

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

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

Таблица 2.1 –Пример симплекс-таблицы

базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x1	x2	...	xl	...	xn
xn+1	b1	a11	a12	...	a1l	...	a1n
xn+2	b2	a21	a22	...	a2l	...	a2n
…	…	...	...	...	...	...	...
…	…	…	…	…	…	…	…
…	...	...	...	...	...	...	...
xn+r	b2	ar1	ar2	...	arl	...	arn
…	…	…	…	…	…	…	…
…	...	...	...	...	...	...	...
…	…	…	…	…	…	…	…
xn+m	bm	am1	am2	...	aml	...	amn
F(x)max	F0	-c1	-c2	...	-c1	...	-cn

Третий шаг. На третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам.

Четвертый шаг.Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то к пятому.

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

Шестой шаг.Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена сверху и F_max->∞. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

2.3 Решение задачи линейного программирования симплекс-методом

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется п переменных и т независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то к переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменныхx₁, x₂,…,x_k,а

остальные m выражены через них(формула 2.1):

x_k+1=α_k+1.1x₁+α_k+1.2x₂+ +α_k+1.kx_k+β_k+1;

x_k+2= α_k+2.1x₁+α_k+2.2x₂+ +α_k+2.kx_k+β_k+2;(2.1)

……………………………………

x_n= α_n1x₁+α_n2x₂+ +α_nkx_k+β_n.

Предположим, что все свободные переменныеx₁, x₂,…,x_kравны нулю.

При этом мы получим:

x_k+1=β_k+1;

x_k+2=β_k+2;

…….. (2.2)

X_n=β_n

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные членыβ_k+1, β_k+2,…,β_n(2.2)неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию Z через свободные переменныеx₁, x₂,…,x_k.

Z=γ₀+γ₁x₁+γ₂x₂+…+γ_kx_k(2.3)

Очевидно, что приx₁=x₂=…=x_k=0, Z=γ₀. Проверим, может ли быть улучшено решение, т. е. получено уменьшение функции Z c увеличением каких-нибудь из переменныхx₁, x₂,…, x_k(2.2) (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициентыγ₁,γ₂,…,γ_kв (2.3) положительны, то увеличение каких-либо из переменныхx₁,x₂,…,x_k(2.2) не может уменьшить Z; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентовγ₁,γ₂,…,γ_kесть отрицательные, то, увеличивая некоторые из переменныхx₁,x₂,…,x_k(те, коэффициенты при которых отрицательны), мы можем улучшить решение.

Пусть, например, коэффициентγ₁в (2.3) отрицателен. Значит, есть смысл увеличитьx₁, т. е. перейти от данного опорного решения к другому, где переменнаяx₁не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьx₁следует с осторожностью, так чтобы не стали отрицательными другие переменныеx_k+1, x_k+2,…,x_nвыраженные через свободные переменные, в частности черезx₁формулами (2.2).

Например, если коэффициент приx₁в соответствующемx_jуравнении (2.2) отрицателен, то увеличениеx₁может сделатьx_jотрицательным. Наоборот, если среди уравнений (2.2) нет уравнения с отрицательным коэффициентом приx₁то величинуx₁можно увеличивать беспредельно, а, значит, линейная функция Z не ограничена снизу и оптимального решения ОЗ не существует.

Допустим, что это не так и что среди уравнений (2.2) есть такие, в которых коэффициент приx₁отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличениеx₁опасно — оно может сделать их отрицательными.

Возьмем одну из таких переменныхx_lи посмотрим, до какой степени можно увеличитьx₁, пока переменнаяx_lне станет отрицательной. Выпишемl-eуравнение из системы (2.2):

x_l=α_l1x₁+α_l2x₂+…+α_lkx_k+β_l (2.4)

Здесь свободный членβ_l≥0, а коэффициентα_l1отрицателен.

Легко понять, что если мы оставимx₂=x₃=…=x_k=0, тоx_kможно увеличивать только до значения, равного–β_l/α_l1,а при дальнейшем увеличенииx₁переменнаяx₁станет отрицательной.

Выберем ту из переменныхx_k+1,x_k+2,…,x_n, которая раньше всех обратится в нуль при увеличении x₁, т. е. ту, для которой величина–β_l/α_l1 наименьшая. Пусть это будетx_r. Тогда имеет смысл разрешить систему уравнений (2.2) относительно других базисных переменных, исключаяиз числа свободных переменныхx₁и переводя вместо нее в группу свободных переменныхx_r. Действительно, мы хотим перейти от опорного решения, задаваемого равенствамиx₁=x₂=…=x_n=0 к опорному решению, в котором ужеx₁≠0, аx₂=…=x_k=x_r=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменныеx₁,x₂,…,x_kвторое мы получим, если обратим в нуль все новые свободные переменныеx₂,x₃,…,x_k,x_r.

Базисными переменными при этом будутx_l,x_k+1,x_k+2,…,x_r-1, x_r-1,…,x_r.

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

Пример 2. Пусть имеется задача линейного программирования с ограничениями-неравенствами:

-5x₁-x₂+2x₃≤2;