Симплексный метод решения задач линейного программирования
При анализе графического метода было отмечено, что оптимальному решению соответствует одна из угловых точек области допустимых решений. Именно этот результат положен в основу симплексного метода. В его вычислительной схеме реализуется порядок, при котором, начиная с исходной допустимой угловой точки, осуществляются последовательные переходы от одной допустимой угловой точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Рассмотрим симплекс метод на примере 2.7.1 задачи о фирме, выпускающей краску.
За начальную угловую точку возьмем точку О, от точки О осуществляется переход к смежной угловой точке. В нашем случае этой смежной точкой может быть либо точка Е, либо точка А.
Рис. 19
Выбор точки (Е или А) зависит от коэффициентов целевой функции, которые определяют скорости ее прироста:
Так как в целевой функции коэффициент при хЕ больше коэффициента при хI, а целевая функция подлежит максимизации, то требуемое направление перехода подлежит увеличению хЕ, что приводит к точке Е.
Далее анализируется можно ли еще увеличить f0. Выбор каждой последующей экстремальной точки при использовании симплекс метода определяется двумя правилами.
Правило 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, 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.
|
|
перепишем целевую функцию в виде уравнения: 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 – уравнения и остальных ограничений.
|
|
Дата добавления: 2018-02-18; просмотров: 1790; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!