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



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

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

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

 


                                       

Рис. 19

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

 

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

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

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

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

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

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

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

 

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

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

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

 

Таблица14

Вершины Нулевые переменные Ненулевые переменные
0 х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:

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

.

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

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

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

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

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

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

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

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

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

перепишем целевую функцию в виде уравнения: f0 – 3xЕ- 2xI = 0

xE + 2xI + S1= 6

2xE + xI + S2= 8

-xE + xI + S3 = 1

xI + S4= 2

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

n-m =6–4=2.

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

Возьмем, например хE = хI = 0 это приведет к следующему базисному решению S1 = 6, S2 = 8, S3 = 1, S4 = 2 (этот начальный базис соответствует вершине O).

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

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

Таблица15

№ итерации базисн. перемен. xE xI S1 S2 S3 S4 значение отношение bi /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)

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

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

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

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

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

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

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

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

Применяя условие оптимальности к симплекс - таблице видим, что включаемой в базис переменной является хЕ (т.к. ½-3½>½-2½). Исключаемая переменная должна быть выбрана из совокупности переменных S1 , S2 , S3 , S4.

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

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

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

mах f0= 3xЕ+ 2xI® mах

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

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

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

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

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

Таким образом переменная хE  достигает максимально допустимого значения, равного 4, в точке Е. При этом переменная S2 станет равной 0 и подлежит исключению из базиса. В столбце “отношение“ будем рассчитывать значение новой переменной, равное bi/ai вед.столб>0, где i – номер уравнения ограничения;

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

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

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

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

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

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

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

 

 

 


                                                                 

 

 

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

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

 

 

 


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

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

 

Ведущий столбец
Ведущая строка
Таблица16


Дата добавления: 2018-02-18; просмотров: 1790; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!