Симплексный метод решения ЗЛП

Проведем перебор точек параллелепипеда  с шагом 1/10ⁿ последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10ⁿ).

Направленный перебор.Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для  решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.

 

1.4 Общая характеристика симплекс-метода

 

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

 

Рисунок 1.1 – Переход от одной вершины к другой

 

Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала. 

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

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

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

-умение переходить к нехудшему опорному плану.

 

 

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

 

 

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.