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

Введение

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

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

1. Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1
+ 5Х2
≤ 10, то, очевидно, 0 ≤ Х1
≤ 10/2 = 5 и 0 ≤ Х2
≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

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

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

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

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

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

f(x1
,x2
,…,xn
)=c1
x1
+c2
x2
+…+cn
xn
→ max (min)

Выделяют две формы задач линейного программирования:

1. стандартная форма

2. каноническая форма

Планом называется вектор x=(x1
,x2
,…,xn
) Rn
, удовлетворяющий условиям (1)-(3). Множество всех допустимых решений задачи будем обозначать через X .допустимое решение xX, при котором целевая функция достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решением задачи линейного программирования. Базисное неотрицательное решение x=(x1
,x2
,…,xr
,0,…,0) , где r- ранг системы ограничений, называется опорным решением.

1. Обыкновенные и модифицированные жордановы исключения

Для рассмотрения сути симплекс метода в задачах линейного программирования необходимо остановиться на понятии «обыкновенные и модифицированные жордановы исключения».

Пусть дана система из m линейных функций y1
,…,ym
от n неизвестных x1
,x2
,…,xn
: yi
=∑ aij
xj
(1.1), где aij
– постоянные величины( i=1,m; j=1,n).

Представим систему (1.1) в форме таблицы 1.3, которую в дальнейшем будем называть жордановой.

Таблица 1.3

x1 … xj … xs … xn
y1 = … yi = … yj = … ym =	a11 … a1j … a1s … a1n …………………………………. ai1 … aij … ais … ain ………………………………… ak1 … ak j … aks … akn ………………………………… am1 … amj … ams … amn

Перейдём к обычной записи системы путём умножения элементов aij
i-й строки на соответствующие неизвестные xj
, стоящие в верхней заглавной строке, затем полученные произведения складываем и приравниваем к yi
.

Выбираем из (1.1) k-е уравнение yk
=∑akj
xj
(1.2), и, положим, коэффициент при xs
отличен от нуля. Выразим xs
:

xs
=∑

Такая операция называется шагом жорданова исключения произведенным над табл.1.3 с разрешающим элементом aks
с k-й разрешающей строкой и s-м разрешающим столбцом. Далее для выяснения как изменятся остальные элементы в табл. 1.3. подставляем значение xs
из в остальные равенства системы

Система запишется в виде

yi
=∑ ( i=1,…,m)

Преобразованную систему переписываем в форме жордановой таблицы (табл. 1.4)

Таблица 1.4

x1 … yк … xn
y1 = … xs = … ym =	b11 … … b1n ……………………… … … ……………………… bm1 … … bmn

Сопоставляя табл. 1.3 и 1.4, необходимо обратить внимание, что шаг обыкновенного жорданова исключения с разрешающим элементом aks
переводит одну таблицу в другую по схеме из четырех правил:

1. разрешающий элемент (РЭ) заменяется обратной величиной;

2. остальные элементы разрешающей строки делятся на РЭ и меняют знаки;

3. остальные элементы разрешающего столбца делятся на РЭ;

4. прочие элементы вычисляются по формуле (1.5).

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

…………………….………

………aij
……… ais
………

……………………………

…….. akj
……… aks
………

……………………………

Тогда из формулы непосредственно следует, что преобразованный элемент bij
равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленной на РЭ.

2. Идея симплекс метода

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

Если задача линейного программирования записана в каноническом виде

f=∑ ci
xj
(max)

∑ aij
xj
= ai0
(i=1,…,m)

xj
>0 (j= 1,…,n)

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

Рассмотрим суть симплекс-метода. Если в системе m<n и все m уравнений линейно независимы, иначе ранг системы равен m. Тогда система имеет бесконечное множество решений. Систему можно разрешить относительно m переменных, которым в матрице системы соответствуют линейно независимые векторы-столбцы. Обозначив эти переменные через x1
,…,xm
,выразим их через свободные переменные xm
+1
,…,xn

xi
= bi0
-∑ bij
xm+1
(i=1,..,m)

Подставив значения xi
в целевую функцию, получаем:

f=b00
- ∑ b0
j
xm
+
j

Значения базисных переменных xi
и целевой функции f полностью определяются значениями свободных переменных xm
+
j
.

Положим, что все bi
0
>0. Тогда план x0
=(b10
;…;bm
0
;0…;0), полученный при нулевых значениях свободных переменных xm
+
j
, будет невырожденным опорным, а отвечающее ему значение функции f равно, как видно b00.

Опорный план x0
соответствует базису Б0
={x1
;…;xm
}.Для получения другого опорного плана преобразовывают базис Б0
в новый базис Б1
, удаляя из Б0
одну переменную и вводявместо нее другую из группы свободных. При этом в базисе Б1
опорному плану x1
соответствует значение f(x1
), не меньшееf(x0
).
Действуя таким образом, переходят к близкому к оптимальному плану. Ввиду того что опорных планов не более С ,через конечное число шагов либо приходят к оптимальному плану, либо устанавливают, что задача неразрешима.

линейное программирование симплекс задача

3. Построение начального опорного решения

Решение задач линейного программирования вручную наиболее рационально можно выполнять именно в табличной форме. В таблицу вписывают систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относите льно начального базиса Бо
= {х1
; ...; хт
} (табл. 2.). Левый столбец занимают базисные переменные и целевая функция, а верхнюю строку — свободные переменные . Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f- строкой или строкой целевой функции.. За столбцом базисных переменных следует столбец свободных членов. Иногда f-строку помещают сразу же за заглавной строкой, а столбец свободных членов в конце; таблицы. Таблицы описанного вида называются симплексными.

Таблица 2

базисные переменные	1	свободные переменные -xm +1 … -xm + s … -xn
x1 = … xk = … xm =	b10 … bk0 … bm0	b11 … b1s … b1,n-m …………………………………… bk1 … bks … bk,n-m …………………………………… bm1 … bms … bm,n-m
f=	b00	b01 …b0 s …b0,n-m

Используются и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все bi
0
>0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана xо
= (b10
;…;bm
0
;0; ... 0) и соответствующее значение b00
целевой функции: f(х0
) = b00
.

От табличной записи легко перейти к обычной записи уравнений. Для этого надо умножить элементы bkj
k-й строки на соответствующие переменные, стоящие в заглавной строке (-xm
+
i
), полученные произведения сложить и сумму приравнять xk
Тогда

bko
*1 + bk1
(—xm+l
)+ … +bks
{—xm+s
)+ ... + bk
,n-m
(—xn
) =xk
илиxi
= bi0
-∑ bij
xm+1 .

4. Критерии оптимальности

Рассмотрим последовательность решения задач линейного программирования симплекс-методом и изложим ее применительно к задаче максимизации.

1. По условию задачи составляется ее математическая модель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.

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

5. Найденный начальный опорный план исследуется на оптимальность:

а) если в f-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в f-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то f→ ;

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

Важно заметить, что поскольку minf= — max( —f), задачу минимизации f можно формально заменить задачей максимизации функции (—f). Но можно этого и не делать. Признаком оптимальности опорного плана задачи минимизации является отсутствие положительных элементов в f-строке симплекс-таблицы, содержащей опорный план. В остальном вычислительная процедура не меняется.

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

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

2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;

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

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

4.1 Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b0
j
> (i=1, ..., nm). В опорном плане х0
, содержащемся в этой таблице, значения всех свободных переменных xm
+
j
равны нулю и f(х0
) =b00
. Если же увеличивать какую-либо из свободных переменных xm
+
j, то, как видно из равенства (2.5), в силу неотрицательности b0
j
значение f(х) начнет уменьшаться. Следовательно, при xо
функция f(х) достигает наибольшей величины, а значит, х0
действительно является оптимальным опорным планом.

4.2 Возможность переход от одного опорного плана к другому

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Бо
с опорным планом х0
в новый базис Б1
с опорным планом х1
при котором; значение функции f увеличивается, т. е. f(xi
)>f(x0
). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b0
s
<0, а среди элементов bis
s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные хm
+
j
кроме xm
+
s
, равными нулю, получаем f = boo
— bos
xm
+
s
. Из этого равенства видно, что при увеличении xm
+
s
значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых xm
+
s
принимает положительные значения, а все остальные компоненты xm
+
j
по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Бо
в новый базис Б1
. В самом деле, если переменная xm
+
s
принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане xо
она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной xm
+
s
. Но здесь предстоит решить два вопроса:

1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной xm
+
s
;

2) какое значение должна принимать новая базисная переменная xm
+
s
в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2.4) все xm
+
j
, кроме xm
+
s
, равны нулю. Тогда

xi
= bio
-bis
xm
+
s
(i=l, ..., m)

Из этих равенств видно, что с возрастанием xm
+
s
значения тех базисных переменных хi
для которых коэффициенты bis
<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты bis
можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых bis
>0. С увеличением xm
+
s
значения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать xm
+
s
, не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых bis
>0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:

xd
=bdo
— bds
xm+s
,

…………………..

xk
=bk0
- bks
xm+s
,

………………….

xp
=bp0
– bps
xm+s
.

Базисные переменные хd
, ..., xk
, ..., xp
будут оставаться неотрицательными до тех пор, пока xm
+
s
удовлетворяет системе неравенств

bdo
- bds
xm+s
>0, xm+s
<bdo
/bds

……………… ………………

bk0
- bks
xm +s
>0 илиxm+s
< bko
/bks

……………… ………………

bp0
– bps
xm+s
>0 xm+s
< bpo
/bps

т. е. приxm+s
<min {bdo
/bds
; ...; bk0
/bks
; ...; bp0
/bpS
}.

Пусть наименьшая из дробей bio
/bis
соответствует i = k, т.е.

min { bio
/bis
}= bk0
/bks
.

Тогда можно сказать, что пока xm
+
s
не превышает величины bk
0
/bks
, т. е. xm
+
s
<bko
/bks
, все базисные переменные xi
остаются неотрицательными. Если же xm
+
s
положить равной bk
0
/bks
>0, то переменная хk
станет равной пулю: xk
= bk
0
— bks
bko
/bks
=0, и тем самым будет произведено преобразование базиса Бо
= {х1
; ...; xk
; ...; хm
} в новый базис, при котором переменная xm
+
s
из группы свободных переходит в базисные, а переменная хk
занимает место xm
+
s
в группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х1
в новом базисе Б1
={х1
; ...; xm
+
s
; ...; xm
} будет иметь mположительных компонент и m-n нулевых. В плане x1
некоторые базисные переменные могут принять нулевые значения в двух случаях:

1) когда в плане х0
имеются базисные переменные, равные нулю;

2) когда наименьшая из дробей bio
/bis
будет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =boo
– bos
xm
+
s
ясно, что при b0
s
<0 и фиксированном xm
+
s
>0, значение f(х) зависит от абсолютной величины коэффициента b0
s
: чем больше |b0
s
|, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной xm
+
s
. Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную xm
+
j
,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

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

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

Отметим, что нам уже известно значение новой базисной переменной xm
+
s
в новом опорном плане: оно равно bko
/bks
. Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х1
;..., xm
+
s
; ...,хm
будет выражена через измененную систему свободных переменных xm
+1
,…,xk
,…, хn
. Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

Коэффициент bks
= 0 при xm
+
s
в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная xm
+
s
выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная хk
. Таким образом, переменные xm
+
s
и xk
поменялись ролями.

Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение xm
+
s
из подставим в остальные равенств (обозначим fчерез x0
,тогда равенство будет входить в систему при i= 0)

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

4.3 Признак неограниченности целевой функции на множестве планов

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

Докажем это утверждение. Пусть в табл. 2, например, b0
s
<0, и все элементы s-го столбца неположительны, т.е. bis
<0 (i=1, ..., m). Тогда, положив в уравнениях (2.4) и (2.5) все свободные переменные, кроме xm
+
s
, равными нулю, получим

xi
= bio
- bis
xm+s
(i=1, ..., m)

f=boo
- b0
s
xm
+
s
.

Из равенств видно, что переменную xm
+
s
можно произвольно увеличивать, не опасаясь нарушить условие неотрицательности базисных переменных xi
ибо bi
0
>0, ( - bis
)>0, а значит, и xi
>0 при любых xm
+
s
>0. В то же время, как видно, где (- b0
s
)>0, значение f(х) будет монотонно возрастать, и если

xm
+.
s
→ , то и f→ .

4.4 Признак бесконечности множества оптимальных планов

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

Докажем это утверждение. Допустим, что содержащийся в табл. 2 опорный план является оптимальным. Обозначим его через х1
*. Пусть при этом элемент bos
f-строки равен нулю, а все остальные элементы этой строки положительны. Тогда, подвергнув табл. 2 симплексному преобразованию с s-м разрешающим столбцом, мы придем к другой таблице с новым опорным планом, который также будет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент bos
f-строки расположен в разрешающем столбце). Обозначим этот новый опорный оптимальный план через х2
*. В соответствии с основной теоремой линейного программирования утверждаем, что любой план х*, являющийся выпуклой линейной комбинацией планов х1
* и х2
*, тоже будет оптимальным.

Если в f-строке будет t(t< n - m) нулевых элементов, то описанным способом можно получить, кроме х1
*, еще t оптимальных опорных планов х2
*; …;хt
+1
*, и тогда все бесконечное множество оптимальных планов запишем так:

x*=λ1
x1
*+…+λt
+1
xt
+1
*, где λl
>0 (l=1,…,t+1) и λ1
+…+λt
+1
=1

Все множество оптимальных планов можно записать в виде

х*=λх1
* + (1- λ) х2
*

4.5 Понятие о проблеме вырождения. Зацикливание

Рассматривая преобразование одного базиса в другой , мы предполагали, что среди симплексных отношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной, исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающем столбце minbi
0
/bis
достигается для нескольких индексов, например для i = l и i = t, т. е.

blo
bts
= bto
bls

и разрешающей выбрана l-я строка. Тогда в новом опорном плане базисная переменная xt
в соответствии с формулой (2.8) будет равна

b'to
=(bto
bls
— blo
bts
): bis

Отсюда получаем xt
= b't
0
= 0. Таким образом, новый опорный план будет вырожденным. Задача линейного программирования, имеющая хотя бы один вырожденный опорный план, называется вырожденной.

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

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

Заключение

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

Список литературы

1 Ашманов С.А., Линейное программирование. М.: Наука 1981.

2. Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 1984

3. Кузнецов А.В., Холод Н.И., Костевич Л.С., Руководство к решению задач по математическому программированию. Мн.: 2001

4. Кузнецов А.В., Холод Н.И., Новикова Т.И. сборник задач по математическому программированию. Мн.: Высшая школа 1994

5. Кузнецов А.В., Холод Н.И., Сокович В.А.., Высшая математика. Математическое программирование. Мн.: Высшая школа 1987