Eng | Rus | Ukr
Исследование операций
04.10.2008

<< prev | ^up^ | next >>

2.5. Метод ОБРАТНОЙ МАТРИЦЫ

Критерии оптимальности и разрешающие множители

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.

Метод обратной матрицы (L- метод )

Использование признака оптимальности в форме (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).

Основная таблица 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

  
Вспомогательная таблица 2.19

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, так как

Таблица 2.20

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
Таблица 2.21

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.

Таблица 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.

Таблица 2.23

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 .

<< prev | ^up^ | next >>

  
     
  Copyright © 2002-2004