Критерии оптимальности и разрешающие множители
1. Использование идей двойственности позволяет по-новому сформулировать критерий оптимальности решения задачи ЛП. Этот критерий использует разрешающие множители Канторовича [18,58].
Пусть задана задача ЛП общего вида со смешанными условиями:
максимизировать L (х) = (2.5.1)
при условиях
i=1, 2,…,m1£m; (2.5.2)
i=m1+ 1, m1+ 2,…,m; (2.5.3)
j=1, 2,…,n1 £n. (2.5.4)
Переменные l1,…,lmназывают разрешающими множителями, если
а) j=1, 2,…,n1(2...5.5)
б) j= n1 +1, n1 + 2,…,n;(2...5.6)
в) i=1, 2,…,m1... (2.5.7)
г) для некоторого плана x=(x1,…,xn)задачи выполняются условия
если xj>0, (1£ j £n1) ; (2.5.8)
li=0, если (1£ i £m1). (2.5.9)
Вектор L = (l1,…,lm)называют разрешающим вектором задачи.
Покажем, що отыскание разрешающего вектора эквивалентно решению задачи, двойственной к задаче (2.5.1) - (2.5.3), для чего рассмотрим следующую теорему.
Теорема 2.10. Совокупность разрешающих векторов задачи (2.5.1) - (2.5.4) совпадает с множеством оптимальных решений задачи (2.4.35) - (2.4.37), двойственной к ней.
Доказательство. Пусть L = (l1,…,lm)–произвольный разрешающий вектор задачи (2.5.1) - (2.5.4), связанный с решением х условиями (2.5.8), (2.5.9).
В силу условий (2.5.5) - (2.5.7) вектор L = (l1,…,lm)-решение двойственной задачи. Остается доказать, что он является оптимальным.
Обозначим через Е совокупность индексов j (j=1,…,n1)для которых xj>0. Тогда
(2.5.10)
Учитывая равенство (2.5.8), а также условия (2.5.6) при j=n1+1,…,nполучим
.
Но, по предположению, xj=0 если jÏE и 1£j£n1, и поэтому
. (2.5.11)
Принимая во внимание равенство (2.5.3) при i=m1+1,…,m и условия (2.5.9) при i=1,…,m1 получим
. (2.5.12)
Сравнив (2.5.11) и (2.5.12), приходим окончательно к соотношению
. (2.5.13)
Но, согласно теореме 2.5 двойственности, соотношение (2.5.13) указывает на оптимальность решений L. Теорема доказана. Используя понятия разрешающих множителей, можно сформулировать признак оптимальности решения задачи ЛП .
Теорема 2.11. Для оптимальности решения х=(x1,…,xn)задачи (2.5.1) – (2.5.4) необходимо и достаточно существование решающего вектора L = (l1,…,lm),связанного с этим решением условиями (2.5.8), (2.5.9).
Доказательство. Необходимость. Предположим, что х=(x1,…,xn)–решение задачи (2.5.1) – (2.5.4). Тогда двойственная задача (2.4.35) – (2.4.37) разрешима. Пусть L = (l1,…,lm)–один из ее оптимальных планов. В таком случае согласно теореме 2.10 вектор L является разрешающим вектором задачи (2.5.1) – (2.5.4), причем, как показано при доказательстве второй части теоремы, он связан соотношениями (2.5.8), (2.5.9) с любым решением задачи (2.5.1) – (2.5.4), а следовательно, и с расматриваемым.
Достаточность. Допустим, что существует разрешающий вектор
L = (l1,…,lm),связанный с данным решением х задачи (2.5.1) – (2.5.4) условиями (2.5.8), (2.5.9).
В процессе доказательства теоремы 2.10 было получено равенство (2.5.13). Из этого равенства, если учесть, что x и L являются решениями задач (2.5.1) – (2.5.4) и (2.4.35) – (2.4.37) соответственно, и вытекает оптимальность решения х ( см. теорему 2.5).
Установленный критерий позволяет легко проверить, является ли данный план оптимальным решением задачи ЛП или нет. С этой целью составляют систему из уравнений ( 2.5.6 ), ( 2.5.8 ), ( 2.5.9 ), из которой определяют соответствующий вектор
L = (l1,…,lm),после чего подстановкой проверяют, удовлетворяет ли этот вектор условия (2.5.5), (2.5.7) или нет. Если да, то вектор х – оптимальный план, в противном случае – неоптимальный план.
Следует заметить, что определение разрешающих множителей эквивалентно решению двойственной задачи, что в общем случае оно отнюдь не проще отыскания решения прямой задачи.
Главная роль разрешающих множителей состоит в том, что их использование позволяет формулировать новый признак критерия оптимальности и построить новый метод линейного программирования.
2. Рассмотрим задачу ЛП в канонической форме (2.5.14) – (2.5.16), которая является частным случаем задачи (2.5.1) – (2.5.4) при m1=0, n1=n
максимизировать (2.5.14)
при условиях
i=1, 2,…,m; (2.5.15)
j=1, 2,…,n. (2 5.16)
Для задачи (2.5.4) – (2.5.16) вектор L = (l1,…,lm) называется разрешающим вектором, если
а) j=1, 2,…,n; (2...5.17)
б) для некоторого плана х (решения) задачи (2.5.14) – (2.5.16) выполняется условие
если xj>0 . (2.5.18)
Критерий оптимальности в этом случае формируется так. Для оптимальности плана x необходимо и достаточно существование разрешающего вектора L=(l1,…,lm),связанного с x условием (2.5.17).
Итак, допустим, что задача ЛП задана в канонической форме и векторы {As1,…,Asm}={Asi}образуют базис для некоторого опорного плана x*. Обозначим через Ix множество индексов базисных векторов. Определим вектор L* =(l*1,…,l*m)из системы уравнений
, (2.5.19)
Тогда план x*– оптимален , если
. (2.5.20)
При рассмотрении симплекс-метода мы получили достаточный признак оптимальности в виде
. (2.5.21)
Покажем теперь эквивалентность форм (2.5.20), (2.5.21) для всех
j=1, 2, …, n...
Справедливая следующая цепочка равенств:
(2.5.22)
Равенство (1) вытекает из (2.5.19), равенство (2) получено переменой порядка суммирования, а равенство (3) следует из разложения небазисного вектора Aj, через базисные:
.
Таким образом, из (2.5.22) следует, что условие
для всех j=1, 2, ...,n эквивалентно условию Dj ³ 0, j= 1, 2, ...,n.
Использование признака оптимальности в форме (2.5.20) позволяет сконструировать второй алгоритм симплекс-метода – метод обратной матрицы (в иностранной литературе этот метод называется модифицированным симплекс-методом). Этот метод разработал Л.В.Канторович для решения одной из специальных задач ЛП еще 1939 г., а позднее (1951) и для общей задачи ЛП (58, 79).
Пусть задача ЛП задана в канонической форме, x – ее допустимое базисное решение для базиса {Ai} iÎIx , где Ix множество индексов базисных векторов. Составим из векторов базиса квадратную матрицу. Очевидно, определитель матрицы Ax отличен от нуля и существует обратная матрица Ax -1.
Покажем, как, используя Ax -1, можно построить компактную схему для вычисления параметров, необходимых для реализации симплекс-метода.
Действительно, базисные компоненты текущего ДБР x определяются из условия
х= Ax–1 b или
.
Оценки векторов D определяются по формулам
(2.5.23)
где параметры li удовлетворяют уравнениям
, (2.5.24)
или в векторной форме LTAx=CTx, где CTx– вектор-строка коэффициентов целевой функции, отвечающих базисным переменным.
Следовательно,
LT=CTx Ax-1 (2.5.25)
Формулы (2.5.23) – (2.5.25) позволяют вычислить оценки Dj векторов, если известны элементы обратной матрицы Ax –1 и условия задачи. Коэффициенты xik разложения небазисного вектора Ak по векторам текущего базиса вычисляются как элементы произведения (Ax -1 Ak) матрицы Ax -1на вектор Ak. Коэффициенты xik вместе с базисными составляющми ДБР определяют вектор, подлежащий выводу из базиса.
Итак, для реализации метода достаточно уметь вычислять на каждом шаге матрицу Ax -1. Элементы столбцов матрицы Ax -1удобно рассматривать как коэффициенты разложения eij единичных векторов ej (j=1,…,m) по векторами базиса, где
При этом пересчет элементов {eij} матрицы Ax –1 при вводе в базис нового вектора Ak выполняется по следующим рекуррентным формулам метода исключения Жордана-Гаусса:
(2.5.26)
где
а) xrk — направляющий элемент преобразования;
б) ei0=xi0 базисные компоненти ДБР х0=||xi0|| i=1,…,m;
в) em+1,0 = lj — разрешающие множители j=1,…,m
г) em+1 ,0=L(x0) — значение ц.ф. при базисном решении x0 ; Ak – вектор, вводимый в базис; Ar – вектор, выводимый из базиса.
Для реализации метода обратной матрицы на каждой итерации используется основная и вспомогательная таблицы.
Основная таблица состоит из (m + 3) столбцов и (m + 1)- й строк (табл.2.18).
N |
Cx |
Bx |
e0 |
e1 |
e2 |
… |
em |
Ak |
q |
1 |
C1 |
A1 |
e10(l) |
e11(l) |
e12(l) |
… |
e1m(l) |
X1k |
q1 |
2 |
C2 |
A2 |
e20(l) |
e21(l) |
e22(l) |
… |
e2m(l) |
X2k |
q2 |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
R |
Cr |
Ar |
er0(l) |
er1(l) |
er2(l) |
… |
erm(l) |
Xrk |
qr |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
m |
Cm |
Am |
em0(l) |
em1(l) |
em2(l) |
… |
emm(l) |
Xmk |
qm |
m+1 |
L |
l1 |
l2 |
… |
lm |
Dk |
N |
b=A0 |
A1 |
A2 |
… |
Ak |
… |
An-1 |
An |
1 |
… |
… |
||||||
2 |
… |
… |
||||||
… |
… |
… |
… |
… |
… |
… |
… |
… |
m |
… |
… |
||||||
m+1 |
c1 |
c2 |
… |
ck |
… |
cn-1 |
cn |
|
0 |
D(0) |
D1(0) |
D2(0) |
… |
Dk(0) |
… |
Dn-1(0) |
Dn(0) |
1 |
D(1) |
D1(1) |
D2(1) |
… |
Dk(1) |
… |
Dn-1(1) |
Dn(1) |
2 |
D(2) |
D1(2) |
D2(2) |
… |
Dk(2) |
… |
Dn-1(2) |
Dn(2) |
… |
… |
… |
… |
… |
… |
… |
… |
… |
l |
D(l) |
D1(l) |
D2(l) |
… |
Dk(l) |
… |
Dn-1(l) |
Dn(l) |
В столбце e0 записываются базисные компоненты текущего решения, столбцы e1, e2 ,…,em-это столбцы обратной матрицы Ax-1 текущего базиса; в столбце Ak записываются коэффициенты xik разложения небазисного вектора Ak по векторам базиса; столбец q – вспомогательный, он содержит величины q = ei0 / xik , xik³0. Столбцы e0, e1 ,…,em составляют главную часть таблицы, в (m+1) – й строке основной таблицы записывают величины {li} iÎIx.
Вспомогательная таблица (табл.2.19) содержит векторы {A1,…,An},i=1,…,n исходной задачи, а также вектор c. В строке 0 записывают значения оценок Dj, отвечающие начальному ДБР.
В процессе каждой очередной итерации (l) во вспомогательную таблицу дописывают очередную строку (l+1), содержащую величины Dj.
Опишем (l+1) итерацию алгоритма обратной матрицы. Пусть уже проведено l итераций алгоритма, в ходе которых вычислены матрица
Ax-1(l) и оценки Dj но еще не найдено оптимальное решение.
1. Определяем вектор Ak, вводимый в базис из условия . (2.5.27)
2. Из вспомогательной таблицы выбираем компоненты небазисного вектора Ak. Определяем его коэффициенты разложения xik через базисные векторы, используя обратную матрицу Ax-1.
. (2.5.28)
Записываем величины xik в столбец Ak. В позицию столбца (m+1) записываем оценку Dj этого вектора.
Просматриваем столбец Ak. Если все xik£0, то задача не разрешима. Допустим, что имеется хотя бы один xik>0. Переходим на п.3.
3. Вычисляем отношения eio / xik и определяем направляющую строку r из условия
.
4. Выполняем одну итерацию симплекс-метода с направляющим элементом xrk
5. Получим новую обратную матрицу Ax-1, а также новые оценки Dj. Заполняем элементами Ax-1 главную часть таблицы (l+1) итерации, при этом заменим индекс r вектора, выведеного из базиса на k в столбце Bx. Одновременно заменяем cr на ck в столбце cx. Заметим, что для контроля значения lj(l+1) можно вычислить также и по формулам
. (2.5.29)
6. Для всех небазисных векторов вычисляем оценки согласно соотношениям
. (2.5.30)
Проверяем условие Dj(l+1) ³ 0 для всех j = 1, 2,…,n...
Если это выполняется, то конец , иначе переходим к (l+2) итерации. Все таблицы алгоритма заполняются по одним и тем же правилам. Некоторые особенности возникают лишь при составлении начальной основной таблицы. Здесь в столбец e0 записывают базисные компоненты исходного ДБР. Первые m позиций столбцов e0, e1 ,…,em получаются путем обращения матрицы векторов базиса начального допустимого базисного решения. Последняя строка главной части таблицы 0 заполняется произведениями столбца cx и столбцов ej этой таблицы, т.е.
j=0, 1,…,m... (2.5.31)
Для контроля вычислений можно использовать две возможности для определения этих величин.
В любой итерации эти параметры могут быть вычислены как по рекуррентным формулами (2.5.26), так и непосредственно по формуле (2.5.29).
В рассмотренной выше вычислительной схеме метода обратной матрицы необходимо запоминать всю обратную матрицу Ax-1= ||eij ||.
В так называемой мультипликативной форме алгоритма требуется регистрировать значительно меньший объем данных.
Рассмотрим ее идею. Пусть х и х'– два последовательных ДБР задачи ЛП. Обозначим соответствующие матрицы векторов базиса через Ax и Ax' :
;
.
Легко проверить, что обратные матрицы -1x и
-1x' связаны соотношением
, (2.5.32)
где
i=1, 2,…,m, i¹r;
.
Соотношение (2.5.32) эквивалентно применению рекуррентных формул (2.5.26) при i = 1, 2,..,m и j = 1, 2, ..., m.
Обычно решение задачи ЛП начинается с единичного базиса. Ему соответствует единичная матрица E. Поэтому после первой итерации, когда вместо вектора {Asr} в базис вводится Ak, обратная матрица базиса для допустимого базисного решения x' может быть вычислена по формуле
,
а после l –й итерации
. (2.5.33)
Матрица Er определяется (m+1)–м числом (r, y1k, y2k, …, ymk)... Следовательно, при l<m запись матрицы Ax-1 в форме (2.5.32) меньше загружает память, чем обычная форма записи, где на каждой итерации треба помнить m2 чисел eij.
Опишем кратко схему вычислений в отдельной итерации мультипликативной формы алгоритма обратной матрицы. Пусть уже проведено l итераций в результате которых установлено, что x(l) – неоптимальный план (ДБР). Определение вектора, подлежащего вводу в базис и выводу из него, производится по общим правилам симплекс-метода, а компоненты очередного базисного решения вычисляются по рекуррентным формулам (2.5.32). Вектор относительных оценок условий задачи (решающий вектор) L на j-й итерации вычисляется по соотношению
.
Вектор оценок Dl определяется обычным способом:
.
Наконец, коэффициенты xih разложения вектора Ak , подлежащего включению в базис по векторам базиса, определяются из соотношения
. (2.5.34)
Как видим, мультипликативная форма алгоритма дает позволяет не только экономить память ЭВМ, но и сокращает объем вычислений на начальных итерациях алгоритма обратной матрицы.
Пример 2.8. Решить методом обратной матрицы такую задачу ЛП:
максимизировать 4x1+2 x2 (1)
при условиях
-x1 + 2x2 £ 6;
x1 + x2 £ 9;
3x1 - x2 £ 15;
x1, x2 ³ 0. (2)
Приводим ее к расширенной форме. Получаем
максимизировать 4x1+2x2
при условиях
-x1 + 2x2 + 1x3 = 6;
x1 + x2 + 1x4 = 9;
3x1 - x2 + 1x5 = 15;
В качестве начального базиса выберем единичный базис
.
Заполняем вспомогательную таблицу 2.20 (начальную часть) и основную таблицу первой итерации (табл. 2.21).
Первая итерация. Заполнив главную часть табл. 2.21 вычисляем ее индексную строку согласно соотношениям lj0 = åcieij0. Так как ci=0 при i=3,4,5, то l1(0)=l2(0)=l3(0)=0. Используя строку D0j табл.2.20, выбираем вектор A1, так как
N |
B |
A1 |
A2 |
A3 |
A4 |
A5 |
1 2 3 |
6 9 15 |
-1 1 3 |
2 1 -1 |
1 0 0 |
0 1 0 |
0 0 1 |
Итераци |
сj |
4 |
2 |
0 |
0 |
0 |
0 1 2 |
Dj(0) Dj(1) Dj(2) |
-4 0 0 |
-2 -10/3 0 |
0 0 0 |
0 0 |
0 4/3 1/2 |
N |
cx |
Bx |
e0 |
e1 |
e2 |
e3 |
Ak |
1 2 3 |
0 0 0 |
A3 A4 A5 |
6 9 15 |
1 0 0 |
0 1 0 |
0 0 1 |
-1 1 3 |
Λ |
0 |
0 |
0 |
0 |
-4 |
Записываем вектор A1 в столбец Ak справа от главной части табл. 2.21 и его оценку в индексную строку.
Столбец Ak – направляющий. Находим направляющий элемент согласно общим правилам симплекса-метода и, выполнив итерацию, заполняем главную часть табл.2.22.
N |
cx |
Bx |
e0 |
e1 |
e2 |
e3 |
Ak |
1 |
0 |
A3 |
11 |
1 |
1 |
|
|
2 |
0 |
A4 |
4 |
0 |
1 |
- |
1 |
3 |
4 |
A1 |
5 |
0 |
0 |
|
- |
Λ |
20 |
0 |
0 |
|
- |
Итак, найден вектор решающих множителей L(1)=[0, 0, 4/3]. Найдем оценки L(1)j для всех небазисных векторов, используя соотношение (2.5.30):
и результаты записываем в строку Lj(1) табл. 2.22. Например,
D2 = 2l(1)1 + 1l(1)2-1l(1)3 – C = -1-2 = -
.
Вторая итерация. Из индексной строки Dj1 выбираем вектор A2 с наибольшей отрицательной оценкой D21<-10/3 <0.
Умножив матрицу {e1, e2, e3} табл.2.20 на A2 получим A21 , который записываем в столбец Ak табл. 2.22.
N |
cx |
Bx |
e0 |
e1 |
e2 |
e3 |
1 |
0 |
A3 |
3 |
1 |
-1 |
1 |
2 |
2 |
A2 |
3 |
0 |
|
- |
3 |
4 |
A1 |
6 |
0 |
|
|
Λ |
20 |
0 |
|
|
Определив направляющий элемент в столбце Ak и выполнив очередную итерацию симплекс-метода, придем к табл. 2.23. Находим вектор оценки по формуле (2.5.30), заносим их в табл. 2.20. Последнее базисное решение в табл. 2.23 оптимально, так как все Dj(2)³0 .