Симплекс-метод
Симплекс-метод
1. Идея симплекс-метода
Рассмотрим универсальный метод решения канонической задачи ЛП.
, , ,
известный как симплекс-метод.
Как было установлено в главе 2, множество планов канонической задачи - выпуклое многогранное множество, имеющее конечное число угловых точек. И если эта задача имеет оптимальное решение, то оно достигается хотя бы в одной угловой точке.
С любой угловой точкой связан базисный план задачи, в котором переменных равны нулю, а оставшимся переменным соответствуют линейно независимые столбцы матрицы условий . Эти линейно независимые столбцы образуют невырожденную базисную матрицу .
Перебор всех угловых точек сопряжен с большими вычислительными затратами и поэтому не эффективен. В 1944 году Дж. Данциг предложил упорядоченную процедуру перебора угловых точек, при которой для нахождения оптимального решения достаточно исследовать лишь небольшую их часть. Эта процедура называется симплекс-методом.
Дж. Данциг предложил при переходе от одной крайней точки к другой заменять в базисной матрице всего один вектор. Это означает, что при таком переходе мы должны одну из базисных переменных исключить - сделать ее небазисной (равной нулю), а на ее место ввести новую переменную из числа небазисных (нулевых) - сделать ее базисной (положительной).
Оказывается, геометрически такая замена приводит к переходу от одной угловой точки к смежной (соседней), связанной с предыдущей точкой общим ребром.
Из всех соседних точек выбирается та, в которой целевая функция возрастает более всего. Поскольку число угловых точек конечно, через конечное число переходов будет найдена вершина с наибольшим значением целевой функции, либо будет установлена неограниченность целевой функции на неограниченном множестве планов.
Общая схема симплекс-метода состоит из следующих основных шагов.
·0 шаг. Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана) .
·1 шаг. Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.
·2 шаг. Нахождение переменной, вводимой в состав базисных. (Из условия увеличения целевой функции).
·3 шаг. Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).
·4 шаг. Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.
Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.
Из этой схемы следует, что, во-первых, для начала работы симплекс-метода надо иметь какую-то угловую точку - начальный базисный план, а во-вторых, надо уметь исследовать текущую угловую точку на оптимальность, не вычисляя всех смежных вершин. Эти проблемы легко решаются, если каноническая задача ЛП имеет некий специальный вид.
Определение. Будем говорить, что каноническая задача ЛП имеет «предпочтительный вид», если
1.правые части уравнений , .
.матрица условий содержит единичную подматрицу размера
.
Другими словами, в любом уравнении есть переменная с коэффициентом равным единице, отсутствующая в остальных уравнениях. Условие 1 не является обременительным, так как в случае отрицательной правой части некоторого уравнения, достаточно умножить его на (-1). В задаче предпочтительного вида начальный базисный план находится очень просто.
Пример.
Матрица условий и вектор правых частей ограничений имеют вид
, .
Сразу очевидна одна базисная матрица: с единичными векторами
.
Следовательно , , - базисные переменные, а x2, x4 - небазисные. Полагая в системе уравнений x2=x4 =0, немедленно находим x1 =10, x3 =20, x5 =8. Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей bi.
В дальнейшем, базисные переменные будем объединять в вектор xБ.
Таким образом, в канонической задаче предпочтительного вида в качестве начальной базисной матрицы берется единичная подматрица AБ =E, а соответствующие ей базисные переменные равны правым частям ограничений: xБ =b.
. Простейшая реализация симплекс-метода
Простейшая реализация симплекс-метода («простой С-метод») применяется к канонической задаче ЛП, имеющей «предпочтительный вид». Не умаляя общности, будем считать, что единичная подматрица содержится в первых m столбцах. Тогда каноническая задача запишется следующим образом
f(x) = c1x1 + c2x2 +… + cmxm + cm+1xm+1 +… + cnxn max(3.1)x1 + a1m+1 xm+1 + … + a1n xn = b1(3.2)x2 + a2m+1 xm+1 + … + a2n xn = b2………………………………………………………….xm + amm+1 xm+1 + … + amn xn = bmxj ³ 0, j=1,2,…, n.(3.3)
Матрица условий
содержит единичную подматрицу размера m x m в первых m столбцах, следовательно AБ ={A1, A2,…, Am}=E.
Основные шаги симплекс-метода (теория)
Поскольку единичная базисная матрица находится в первых m столбцах матрицы условий, то первые m координат начального базисного плана являются базисными, а последние n - m координат являются небазисными, то есть равны нулю:
o = (x1, x2,…, xm, 0,…, 0).
Подставляя координаты точки xo в ограничения (3.2) и учитывая, чтоm+1 =… = xn = 0, получаем: x1 = b1, x2 = b2,…, xm = bm, то есть xoБ = b.
Значит начальный базисный план имеет вид:
xo = (b1,…, bm, 0,…, 0),
где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных.
1 шаг. Проверка базисного плана на оптимальность.
Из системы ограничений (3.2) выразим базисные переменные через небазисные:
x1= b1 - a1m+1xm+1 - … - a1nxn, x2 = b2 - a2m+1xm+1 - … - a2nxn, ………………………………………… xm = bm - amm+1xm+1 - … - amnxn,(3.4)
Подставим эти выражения в целевую функцию (3.1).
f (x) = c1 (b1 - a1m+1xm+1 - … - a1nxn) + c2 (b2 - a2m+1xm+1 - … - a2nxn) +
………………………………………………..
+ cm (bm - amm+1xm+1 - … - amnxn) + cm+1xm+1 +… + cnxn.
Сгруппируем слагаемые при одинаковых небазисных переменных:
f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1). xm+1 - …-
- (c1 a1n + c2 a2n + … + cm amn - cn). xn.(3.5)
Заметим, что выражения в круглых скобках можно записать в виде
c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1 = < cБ, Am+1 > - cm+1 = Dm+1,
…………………………………………………………………………………………………………………………1 a1n + c2 a2n + … + cm amn - cn = < cБ, An > - cn = Dn,
где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных, Am+1,…, An - столбцы матрицы условий А при небазисных переменных xm+1,…, xn.
Выражения
D j = < сБ, Aj > - cj, j = m+1,…, n,(3.6)
называются симплексными разностями или симплексными оценками базисного плана.
С учетом (3.6), формулу (3.5) для целевой функции можно переписать в виде
.
Эта формула позволяет получить признак оптимальности базисного плана. Если все симплексные оценки с небазисными номерами D j ³ 0, то текущий базисный план - оптимален.
Действительно, если хотя бы одна оценка, например, k строго отрицательна, то придавая соответствующей небазисной переменной xk положительное значение, а остальные небазисные переменные плана x полагая равными нулю, получим
f (x) = f (xo) - Dk xk = f (xo) + | D k | xk > f (x