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

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

Рассмотрим симплекс метод на примере 2.7.1 задачи о фирме, выпускающей краску.

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

Рис. 19

Выбор точки (Е или А) зависит от коэффициентов целевой функции, которые определяют скорости ее прироста:

Так как в целевой функции коэффициент при х_Е больше коэффициента при х_I, а целевая функция подлежит максимизации, то требуемое направление перехода подлежит увеличению х_Е, что приводит к точке Е.

Далее анализируется можно ли еще увеличить f₀. Выбор каждой последующей экстремальной точки при использовании симплекс метода определяется двумя правилами.

Правило 1. Каждая последующая точка должна быть смежной с предыдущей, то есть невозможен в нашем примере прямой переход из точки О в вершину Д. Этот переход осуществляется по границам (ребрам) симплекса ОДР: от точки О к вершинам Е, из точки Е в точку Д.

Правило 2. Обратный переход к предшествующей вершине невозможен. Перед переходом от точки к следующей смежной вершине проверяется каждая текущая вершина на оптимальность.

Приведем задачу фирмы, выпускающей краски I и E к канонической форме.

Стандартная форма Каноническая форма

f0=3хE+2хI® мах при ограничениях: хE+2хI £ 6 2хE+хI £ 8 хI -хE £ 1 хI £ 2 хI,хE³ 0

f0=3хE+2хI® мах при ограничениях: хE+ 2хI + S1=6 2хE+хI + S2=8 хI -хE+ S3=1 хI + S4= 2 хI,хE³0 Si³0 i=

 

Каждую точку ОДР можно определить с помощью переменных х_Е, х_I, S₁,..., S₄, которые фигурируют в модели в канонической форме.

Для идентификации нужной вершины воспользуемся тем, что при S_i = 0, i = 1,.., 4 ограничения модели эквивалентны равенствам, которые представляются отрезками соответствующих прямых. При S₁ = 0 первое ограничение примет вид х_E+2х_I= 6 (ребро СD). Увеличение переменных S_i (S_i> 0; i=1,..,4) будет соответствовать смещению допустимых точек с границ ОДР в ее внутреннюю область.

Анализируя рис.19 можно определить каждую вершину ОДР через переменные:

 

Таблица14

Вершины	Нулевые переменные	Ненулевые переменные
	хE, хI	S1=6, S2=8, S3=1, S4=2
А	S3, хE	S1=4, S2=7, S4=1 хI=1
В	S3, S4	xI=2, хE=1, S1=1, S2=4
С	S1, S4	xI=2, хE=2, S2=2, S3=1
Д	S1, S2	xI= , хE= , S3=3, S4=
Е	хI, S2	xE=4, S1=2, S3=5, S4=2

 

Анализируя таблицу легко заметить две закономерности:

1. Стандартная модель содержит четыре уравнения (m = 4) и шесть неизвестных (n=6), поэтому в каждой из вершин две (6-4=2) переменных должны иметь нулевые значения.

2. Смежные вершины отличаются только одной переменной в каждой группе (нулевых и не нулевых переменных).

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

В этом состоит сущность свойства однозначности вершины, каждой вершине соответствуют две нулевых переменные; на ребре - одна нулевая переменная, внутри ОДР вообще не имеется ни одной нулевой переменной. Линейная модель содержит m уравнений (ограничений) и n неизвестных (n ³ m), причем правые части уравнений неотрицательны, тогда все допустимые вершины определяются как все однозначные неотрицательные решения системы m уравнений, в каждой вершине n-m переменных равны нулю. Однозначные решения такой системы уравнений, получаемых путем приравнивания к нулю (n-m) переменных, называются базисными.

Если базисное решение удовлетворяет требованию неотрицательности правых частей, оно называется допустимым базисным решением. Переменные, которые имеют нулевое значение, называются небазисными (свободными) переменными, а остальные базисными переменными (зависимыми переменными).

Максимальное число итераций при использовании симплекс - метода равно максимальному числу базисных решений задачи линейного программирования, то есть числу сочетаний из n по m:

Для рассмотренной задачи:

.

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

Чтобы увеличить f₀ следует увеличить значение переменных х_Е от нуля, до значения х_Е в точке Е. При этом небазисная переменная х_Е переходит в разряд базисных, а соответствующая базисная переменная х₄ переходит в разряд небазисных. Таким образом, между множеством небазисных и базисных переменных происходит взаимообмен.

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

Алгоритм метода:

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

2) По условию оптимальности из числа текущих небазисных переменных (равных нулю) выбирается включаемая в новый базис переменная, увеличение которой обеспечит наибольшее увеличение целевой функции. Если такой переменной нет, то вычисления прекращаются и текущее базисное решение объявляется оптимальным. Иначе переходим к пункту 3.

3) Из числа переменных текущего базиса (по условию допустимости) выбирается исключаемая переменная, которая должна будет принять нулевое значение (стать небазисной) при введении в состав новой базисной переменной.

4) Находится новое базисное решение, соответствующее новому составу базисных и небазисных переменных, по правилам 1 и 2, затем переход к пункту 2.

Рассмотрим алгоритм на примере: 2.7.1

перепишем целевую функцию в виде уравнения: f₀ – 3x_Е- 2x_I = 0

x_E + 2x_I + S₁= 6

2x_E + x_I + S₂= 8

-x_E + x_I + S₃ = 1

x_I + S₄= 2

Число переменных, которое должно быть равным нулю, равно:

n-m =6–4=2.

Это обеспечит единственность и допустимость получаемого решения.

Возьмем, например х_E = х_I = 0 это приведет к следующему базисному решению S₁ = 6, S₂ = 8, S₃ = 1, S₄ = 2 (этот начальный базис соответствует вершине O).

Величина f₀ в вершине О равна нулю, так как х_E и х_I = 0, то есть в качестве начального базиса выбраны остаточные переменные.

Полученные результаты можно представить в виде симплекс - таблицы. Симплекс - таблица интерпретируется следующим образом.

Таблица15

№ итерации	базисн. перемен.	xE	xI	S1	S2	S3	S4	значение	отношение b i /ai
№=0 хЕ вводим, S2 исключ.	f0	-3	-2	0	0	0	0	0
S1	1	2	1	0	0	0	6	6:1=6
S2	2	1	0	1	0	0	8	8:2=4
S3	-1	1	0	0	1	0	1	не рассчит.
S4	0	1	0	0	0	1	2	не рассчит.

 

Второй столбец содержит базисные переменные, значения которых приведены в столбце “значение”. При этом подразумевается, что не базисные переменные х_E и х_I, которых нет в первом столбце равны нулю. (х_E=0 и х_I=0)

Значение целевой функции равно: f₀= 3x_E + 2x_I + 0×6 + 0×8 + 0×1 + 0×2 = 0 что и показано в столбце “значение”.

Как определить, является ли данное базисное решение оптимальным?

Анализируя первую строку f₀ – уравнения, видно, что обе не базисные переменные х_E и х_I имеют отрицательные коэффициенты. Это эквивалентно положительным коэффициентам в целевой функции. Так как мы решаем задачу максимизации, то значение f₀ может быть увеличено при увеличении как х_E, так и х_I.

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

Условие оптимальности при поиске максимума f.

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

Условие оптимальности при поиске минимума f

Если все небазисные переменные в f - уравнении имеют неположительные коэффициенты, то полученное решение является оптимальным. В противном случае, в качестве новой базисной переменной следует выбрать переменную с наибольшим положительным коэффициентом в f – уравнении.

Применяя условие оптимальности к симплекс - таблице видим, что включаемой в базис переменной является х_Е (т.к. ½ -3 ½>½ -2 ½). Исключаемая переменная должна быть выбрана из совокупности переменных S₁ , S₂ , S₃ , S₄.

Условие допустимости.

Столбец симплекс - таблицы определяющий вводимую в базис переменную называется ведущим столбцом.

В качестве исключаемой переменной выбирается та из переменных текущего базиса, которая первой обращается в нуль при увеличении включаемой переменной х_Е вплоть до значения, соответствующего смежной экстремальной вершине ОДР

mах f₀= 3x_Е+ 2x_I® mах

Максимальное допустимое значение переменной х_E соответствует той из точек пересечения оси х_E с прямыми, представляющими ограничения модели, которая имеет наименьшую положительную координату.

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

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

х_E = =-1< 0 (вершина М вне ОДР); х_E = = 4 (вершина Е в ОДР);

х_E = = 6 (вершина N вне ОДР) (рис.16.)

Таким образом переменная х_E достигает максимально допустимого значения, равного 4, в точке Е. При этом переменная S₂ станет равной 0 и подлежит исключению из базиса. В столбце “отношение“ будем рассчитывать значение новой переменной, равное b_i/a_{i вед.столб} >0, где i – номер уравнения ограничения;

a_{i вед.столб} – коэффициент, стоящий в ведущем столбце i -го ограничения, причем отношение рассчитывается только для положительных коэффициентов а_{iвед.столб}.

Строку, соответствующую исключаемой переменной называют ведущей строкой.

Исключаемой переменной будет та переменная текущего базиса, для которой отношение b_i/a_{i вед.столб.} минимально:

min ()=min (6;4)= 4.

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

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

1. Получение коэффициентов новой ведущей строки по правилу:

 

 

 

Термин "соответствующий коэффициент" следует понимать как коэффициент при той же переменной.

2. Формирование всех остальных строк симплекс - таблицы, включая и f – уравнение (кроме “новой” ведущей строки).

 

 

Выполнение процедуры 1 приводит к тому, что в новой ведущей строке ведущий элемент становится равный 1, а в столбце "значение" в симплекс-таблице будет стоять значение введенной в базис переменной (см. табл.16).

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

 

Ведущий столбец

Ведущая строка

Таблица16

№ итер.	Базис	хЕ	хI	S1	S2	S3	S4	Значение	Отношение	Формула
N=0 хE ввод., S2 искл.	fур	-3	-2	0	0	0	0	0
S1	1	2	1	0	0	0	6	6:1=6
S2	2	1	0	1	0	0	8	8:2=4
S3	-1	1	0	0	1	0	1	не рассчит.
S4	0	1	0	0	0	1	2	не рассчит.
N=1 xI ввод., S1 искл.	fур	0	-	0		0	0	12		fур= fур+3хЕ
S1	0		1	-	0	0	2	2: =	S1= S1 -хЕ
хE	1		0		0	0	4	4: =8	хЕ= S2:2
S3	0		0		1	0	5	5: =	S3= S3+хЕ
S4	0	1	0	0	0	1	2	2:1=2	S4= S4
N=2 оптим план	fур	0	0			0	0	12		fур= fур+ хI
xI	0	1		-	0	0			хI= S1:
хE	1	0	-		0	0			хЕ=хE - хI
S3	0	0	-1	1	1	0	3		S3= S3 - хI
S4	0	0	-		0	1			S4= S4-хI

Оптимальный суточный план производства краски Е в количестве , краски I – , максимизирующий прибыль mах f = тыс. дол., причем S₁=0; S₂=0, т.е. продукты А и В расходуются полностью, остаточные переменные спроса S₃=3; S₄=2/3.

Пример 2. 8. 1.

Два механизма могут выполнить два вида земляных работ. В таблице 17 указаны ресурсы рабочего времени t_i каждого из механизмов в машино-часах и их производительности λ_ij в м³/ машино-час.

Таблица17

Механизмы	Производительность i -го механизма λij при выполнении j -ой работы.	ti
1 вид работы	2 вид работы
I	20 (х11)	10 (х12)
II	40 (х21)	30 (х22)

 

Требуется распределить временные ресурсы так, чтобы механизмы смогли выполнить максимальный объем работ, соблюдая при этом следующее соотношение объемов проделанной работы 1-го и 2-го вида: 2/4.

При данных условиях выгодно ли увеличение производительности I механизма при выполнении 2 вида работ до 20 м³/ машино-час?

Составим целевую функцию:

f = 20×х₁₁+10×х₁₂+40×х₂₁+30×х₂₂→mах

Ограничения по времени:

х₁₁+х₁₂ ≤ 330

х₂₁+х₂₂ ≤ 440

Решим симплексным методом:

Распишем пропорцию и выразим х₁₁:

80 х₁₁+160 х₂₁= 20 х₁₂+60 х₂₂ (:80)

х₁₁= х₁₂+ х₂₂ -2 х₂₁

Исходя из нового значения х₁₁, запишем выражение для целевой функции:

f=20×( _×х₁₂+ _×х₂₂ -2×х₂₁ )+ 10×х₁₂ +40×х₂₁+30×х₂₂ = 15×х₁₂ + 45×х₂₂→мах

Ограничения примут вид:

х₁₂ + х₂₂ - 2х₂₁ + х₁=330

х₂₁ + х₂₂ + х₂=440

Таблица 18

№ итер.	Базис	х 12	х 21	х 22	х1	х2	Значе-ние	Отнош	Формула
№ = 0 х2 -искл. х22 -ввод.	f ур	-15	0	-45	0	0	0
х1	5/4	-2	¾	1	0	330	440
х2	0	1	1	0	1	440	440
№ =1 х1 –искл. х12 -ввод.	f ур	-15	45	0	0	45	19800		fур= fур+45.х22
х1	5/4	-11/4	0	1	-3/4	0	0	х1=х1 – х22 .3/4
х22	0	1	1	0	1	440	440	х22 = х2: 1
№ = 2 оптимум	f ур	0	12	0	12	36	19800		fур=fур+ 15.х22
х12	1	-11/5	0	4/5	-3/5	0		х12 = х1:5/4
х22	0	1	1	0	1	440

Симплекс-таблица оптимальна, т.к. все коэффициенты при fур неотрицательны. х₁₁= ^. 0+ 440 -2×0=330

х₁₂=0; х₂₁=0; х₂₂=440,

т.е. механизм I в течение 330 часов выполняет 1-ю работу, а механизм II в течение 440 часов выполняет 2-ю работу.

Если увеличить производительность механизма I при выполнении 2-го вида работ до 20 м³/машино-час, то оптимальный план был бы таков:

х₁₁=0, х₁₂=330, х₂₁=440 и х₂₂=0

max f =20^.0+20 ^.330+40 ^.440+30^.0=23200 (м³),

т.е. был бы выполнен больший объем работ, чем в исходной задаче.

Пример 2. 8. 2.

Стальные прутья длиной 110 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 штук. Возможные варианты разреза и величина отходов при каждом из них приведены в табл.19.

Таблица 19

Длина заготовки, (см)	Варианты разреза
				‑	‑	‑
	‑		‑			‑
	‑	‑		‑
Величина отходов (см)

Определить, сколько прутьев по каждому из возможных вариантов следует разрезать, чтобы получить не менее нужного количества заготовок каждого вида при минимальных отходах.

Математическая модель

Обозначим: х_j (j=1, 2,..,6) – количество прутьев разрезаемых по j варианту

z_i (i=1,..,3) – количество лишних заготовок длиной 45, 35 и 50 см соответственно.

f =20×х₁+30×х₂+15×х₃+5×х₄+25×х₅+10×х₆+45×z₁+35×z₂+50×z₃®min

при ограничениях:

2х₁+х₂+х₃ -z₁=40

х₂+3х₄+х₅ -z₂=30

х₃+х₅+2х₆-z₃=20

х_j³ 0; z_i³0; j=1, 2,...,6; i=1,...,3

Так как переменные х₁, х₄ и х₆ входят только в одно ограничение, то их можно взять за базисные, выразив их через небазисные переменные, подставим в f, получим:

х₁=20 - х₂ - х₃+ z₁

х₄=10 - х₂ - х₅+ z₂

х₆=10 - х₃- х₅+ z₃

f =400 -10×х₂ -10×х₃ + 10×z₁ + 30×х₂ +15×х₃+50 - х₂ - х₅ + z₂ + 25×х₅+100 -5х₃ -5x₅ + 5×z₃ + 45×z₁ + 35×z₂ + 50×z₃® min

f =550+ х₂+ х₅+55z₁+ z₂+55z₃® min

Все коэффициенты при небазисных переменных х₂, х₅, z₁, z₂ и z₃ (равных нулю) положительны, и решается задача минимизации, следовательно переменные х₂, х₅, z₁, z₂ и z₃ увеличивать не стоит.

min f =550 при плане Х*=(20; 0; 0; 10; 0; 10) при этом потерь за счет лишних заготовок не будет, т.е. z_i=0 (i=1,..,3).