Понятие о симплекс-методе

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит:

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана; 

ІІ РЕШЕНИЕ ЗЛП СИМПЛЕКСНЫМ МЕТОДОМ

2.1 Примеры использования симплекс-метода в экономике

 

Задачи ЛП нашли широкое применение в экономике. Рассмотрим это на примерах.

Пример 1. Рассматривается работа промышленного предприятия под углом зрения его рентабельности, причём приводится ряд мер с целью повышения этой рентабельности. Показатель эффективности - прибыль ( или средняя прибыль ), приносимая предприятием за хозяйственный год.

Пример 2. Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.

Пример 3. Ремонтная мастерская занимается обслуживанием машин; её рентабельность определяется количеством машин, обслуженных в течение дня. Показатель эффективности - среднее число машин, обслуженных за день.

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

Пример 5. Предпринимается ряд мер по повышения надёжности электронной цифровой вычислительной техники . Цель операции - уменьшить частоту появления неисправностей ( "сбоев" ) ЭЦВТ, или, что равносильно, увеличить средний промежуток времени между сдоями ( "наработку на отказ" ). Показатель эффективности - среднее время безотказной работы ЭЦВТ.

Пример 6. Проводится борьба за экономию средств при производстве определённого вида товара. Показатель эффективности - количество сэкономленных средств.

С помощью анализа  модели на чувствительность определить параметр, от которого результат зависит  больше и решить, каким способом возможно увеличение эффективности  и на сколько, а так же многое другое.

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

Симплекс-метод может  применяться на государственных  и частных предприятиях для улучшения эффективности производства.

 

 

 

 

2.2 Алгоритм решения ЗЛП симплексным методом

 

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

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

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

-x₁+x₃+x₄≤5; (2.5)

-3x₁+5x₄≤7.

 

Требуется минимизировать линейную функцию

 

Z=5x₁-2x₃

Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменныеy₁,y₂,y₃переходим к условиям-равенствам:

y₁=5x₁+x₂-2x₃+2

y₂=x₁-x₃-x₄+5 (2.5)

y₃=3x₁-5x₄+7

 

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пусть в качестве свободных  переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение:

 

x₁=x₂=x₃=x₄=0;

y₁=2, y₂=5, y₃=7.

 

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

Выбирается переменная у, и вводится в число свободных  вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменнойx₃:

 

x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

Это выражение подставляется  вместоx₃во второе уравнение:

 

x₃=5/2*x₁+1/2*x₂-1/2y₁+1;