2.4. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Структура и свойства двойственной задачи

Задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1,…,bm между различными потребителями, например между определенными технологическими процессами, которые представляются столбцами A1,…,A матрицы ограничений задачи.

Любое допустимое решение задачи ЛП x1,…,xn дает конкретное распределение, которое указывает ту долю каждого из ресурсов, которая должна быть  использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Предприятие производит три вида продукции x1, x2 и x3, каждый из которых проходит обработку на токарном, фрезеровальном и сверлильном станках. Общий фонд машинного времени для каждого из станков ограничен. Пусть c1, c2 и c3– прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество продукции каждого вида следует производить каждую неделю, чтобы обеспечить максимальную прибыль.

Эта задача имеет такой вид:

              максимизировать  c1x1+c2x2+c3x3                                         (2.4.1)

при ограничениях

a11x1 + a12x2 + … + a13x3 £ b1 ;

a21x1 + a22x2 + … + a23x3 £ b2 ;

a31x1 + a32x2 + … + a33x3 £ b3 .                        (2.4.2)

где a1j, a2j, a3j– время, необходимое для обработки единицы j –го вида продукции на токарном, фрезеровальном и сверлильном станках соответственно (j=1,2,3) b1, b2, b3 – недельный ресурс машинного времени для группы токарных, фрезеровальных и сверлильных станков соответственно.

Обозначим через y1, y2, y3 -цену единицы времени работы токарного, сверлильного и фрезеровального оборудования.

Тогда a11y1+ a21y2+ a31y3 можно трактовать как затраты на изготовление единицы продукции первого вида;

a12y1+ a22y2+ a23y3– затраты (стоимость) на изготовление единицы продукции второго вида и т.д.

Предположим, что цены ресурсов y1, y2, y3 выбраны так, что выполняются соотношения

a11y1 + a12y2 + … + a13y3 ³ c1 ;

a21y1 + a22y2 + … + a23y3 ³ c2 ;

a31y1 + a32y2 + … + a33y3 ³ c3 .                                              (2.4.3)

Поскольку b1, b2, b3 – общий использованный ресурс машинного времени для каждого из станков, то b1y1+b2y2+b3y3– общие затраты на производство (общая стоимость использованных ресурсов).

Тогда можно сформулировать следющую задачу.

Требуется определить цены y1, y2, y3 , удовлетворяющие условиям (2.4.3), при которых минимизируются суммарные затраты на производство, а именно:

               минимизировать  g(y1,y2,y3)= b1y1+b2y2+b3y3                         (2.4.4)

при ограничениях (2.4.3) и                        

                                                    y1³0, y2³0, y3³0.

Задачу (2.4.3), (2.4.4) называют двойственной относительно задачи (2.4.1), называемой прямой.

Запишем прямую и двойственную задачи в общем виде.

Прямая задача:

                                        максимизировать                                      (2.4.5)

при ограничениях

, i=1,2,…,m,                    (2.4.6)

xj ³ 0, j=1, 2,…,n.                               (2.4.7)

Двойственная задача:

                                       минимизировать                       (2.4.8)

при ограничениях

,                           (2.4.9)

yi ³ 0, i=1, 2,…, m .                          (2.4.10)

В матричном виде пара двойственных задач записывается следующим образом:

Прямая задача:

                                         максимизировать cTx                          (2.4.11)

при ограничениях

Ax£b;                                     (2.4.12)

x ³ 0.                                      (2.4.13)

Двойственная задача:

                                        минимизировать bTy                            (2.4.14)

при условиях

ATy ³ с;                                       (2.4.15)

y ³ 0.                                          (2.4.16)

Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи.

1. Если прямая задача является задачей максимизации, то двойственная будет задачей минимизаци, и наоборот.

2. Коэффициенты целевой функции прямой задачи c1, …,cn становятся свободными членами ограничений двойственной задачи.

3. Свободные члены ограничений прямой задачи b1, …,bm становятся коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи получается путем транспортирования матрицы ограничений прямой задачи.

5. Знаки неравенств в ограничениях изменяются на противоположные.

6. Число ограничений прямой задачи равно числу переменных двойственной задачи, и наоборот.

Переменные y1,…,ym двойственной задачи иногда называют теневыми ценами[23].

Двойственную задачу выгоднее решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений  (m > n).

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

Теорема 2.4. Если x0 и y0 допустимые решения прямой и двойственной задач, то есть Ax0£b  и  ATy0³c   ,то

cTx0 £bTy0,                                        (2.4.17)

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

Доказательство. Умножим выражение (2.4.12) на y0T, получим

y0TAx0 £ yoTb.                                   (2.4.18)

Аналогично умножим (2.4.15) на x0T:

x0TAT y0 ³ x0Tc.                                 (2.4.19)

Но y0TAx0=( y0TAx0)T=x0TATy0  ,а кроме того x0Tc=cTx0.

Поэтому, сравнивая (2.4.19) и (2.4.18), получим

y0T b³ y0T Ax0³x0Tc или cTx0£bTy0.

Теорема доказана.

Теорема 2.5. (основная теорема двойственности). Если x0 и y0 допустимые решения прямой и двойственной задач и кроме того, если cTx0=bTy0, то x0 и y0 – оптимальные решения пары двойственных задач.

Доказательство.Согласно теореме 2.4 для всех допустимых решений х и у справедливо неравенство (2.4.17). В частности, для всех допустимых решений х справедливо cTx£bTy0. Однако из условия теоремы cTx0=bTy0  следует cTx£cTx0. Следовательно, x0 - оптимальное решение.

Вторая часть теоремы доказывается аналогично.

В силу теоремы 2.4. для всех допустимых у справедливо cTx0£bTy. Но из условия cTx0=bTy0 следует, что bTy³bTy0 для всех y³0. Таким образом, y0– оптимальное решение.

Теорема 2.6. Если в оптимальном решении прямой задачи (2.4.5) (2.4.7) i-тое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, то есть

если                  (2.4.20)

где Ai— i-я строка матрицы А.

Смысл теоремы 2.6 состоит в слдующем. Если некоторый ресурс bi имеется в избытке, и і-тое ограничение при оптимальном решении выполняется как строгое неравенство, то это ограничение становится несущественным, и оптимальная цена соответствующего ресурса равна нулю.

Теорему 2.6. дополняет теорема 2.7, устанавливающая взаимосвязь между оптимальным решением прямой задачи и ограничениями двойственной.

Теорема 2.7. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно  нулю, то есть

если ATjyопт–cj>0,   то xj опт =0.                      (2.4.21)

Дадим экономическую интерпретацию теоремы 2.7.

Поскольку величины yi (i=1, 2,…,m)представляют собой цены соответствующих ресурсов, то ATjy= -это затраты на j-й технологический процесс, а величина cj – прибыль от реализации единицы соответствующего продукта. Поэтому с экономической точки зрения теорема 2.7 означает следующее: если j-й технологический процесс оказывается строго невыгодным относительно оптимальных цен ресурсов yопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса должна быть равна нулю, и соответствующий вид продукции не выпускается как нерентабельный.

Таким образом, теорема 2.7 выражает принцип рентабельности для оптимально организованного производства.

Из этой теоремы вытекает также, что если xj опт>0, то

ATjyопт–cj =0                                (2.4.22)

Предположим, что среди переменных x1, x2, …, xn прямой задачи есть множество из m переменных, которые в оптимальном решении прямой задачи имеют ненулевые значения. Пусть, например, такими переменными оказались первые по порядку m переменных.

Тогда на основании уравнения (2.4.22) получаем m условий рентабельности:

AT1yопт c1 =0;

AT2yопт c2 =0;

. . . . . . .

ATmyопт cm =0,                                 (2.4.23)

где                                        AT1 = (a11, a21,…,am1);

... . . . . . . . . . .

ATm = (a1m, a2m,…,amm).

Доказательства теорем 2.6 и 2.7 проведем последовательно.

Пусть хопт и yопт – оптимальные решения прямой и двойственной задач. Поскольку эти решения допустимые, то

Axопт b £ 0;                                    (2.4.24)

ATyопт c ³ 0.                                   (2.4.25)

Умножив неравенство (2.4.24) на yТопт, а неравенство (2.4.25) – на хТопт, получим

yТоптAxопт yопт b £ 0;                                 (2.4.26)

xТопт ATyоптxTопт c ³ 0.                              (2.4.27)

Так как  в силу теоремы 2.5

       yTопт b= xоптc  и   yTоптA xопт = xTопт AT yопт,   то выражения (2.4.26), (2.4.27) строго равны нулю.

Расписав левую часть неравенства (2.4.26), получим

yTопт (Axоптb) = y1 опт(A(1) xоптb1) + y2 опт(A(2) xоптb2) +…

+ymопт(A(m) xопт bm) = 0 .                           (2.4.28)

Поскольку yi опт ³0 и A(i)xопт – bi£0 для всех i = 1, 2, ..., m, то левая часть уравнения (2.4.28) может быть равна 0 только в том случае, если каждое слагаемое в отдельности равно нулю.

Таким образом, для каждого i, при котором A(i)xопт – bi<0, имеем

yi опт =0, что и требовалось доказать в теореме 2.6.

       Рассмотрим теперь левую часть неравенства (2.4.27), предварительно расписав ее

xTоптATyопт xTоптc = xTопт (ATyоптc) = x1опт (AT1 yоптc1) +

+ x2опт (AT2yоптc2) +…+xnопт (ATnyоптcn) = 0,       (2.4.29)

где                                             A=[A1, A2,..,An].

Так как все xj опт ³0 и AjTyоптcj ³0 для всех j=1,…,n, то уравнение (2.4.29) строго равно нулю, если для каждого j, при котором

(AjTy оптcj)>0 ,соответствующая переменная xj опт равна нулю.

Приведем еще две важные теоремы теории двойственности.

Теорема 2.8. (теорема существования). Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда обе они имеют допустимые решения.

Теорема 2.9. (теорема двойственности). Допустимый вектор x0 оптимальный тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение y0, что

cTx0 = bTy0.                                       (2.4.30)

Доказательство теорем 2.8 и 2.9 простое, поэтому предлагаем читателю выполнить их самостоятельно.

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

Dn+iпр = yi опт;

-Dm+jдв =xj опт,                                  (2.4.31)

i= 1, 2,..., m;    j= 1, 2,..., n,

где n - количество переменных прямой задачи; m – количество ее ограничений;

Dn+iпр , Dm+jдв - соответствующие элементы индексной строки симплекс-таблицы прямой и двойственной задач соответственно.

При этом, если n+i, где 1£ i£m, больше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы Dn+i , Dm+j находятся путем циклической перестановки, начиная с элемента D1.

Пример 2.6.

Рассмотрим задачу ЛП:

максимизировать f(x1,x2)=c1x1+c2x2=4x1+3x2

при ограничениях

1x1 + 0x2 £ 4000;

0 x 1 + 1 x 2 £ 6000;

x 1 +  x 2 £ 6000;

x 1, x 2 ³ 0.

Двойственная задача записывается так:

минимизировать g(y1, y 2, y 3)=4000 y 1+6000 y 2+6000 y 3

при ограничениях

1 y 1+0 y 2+1 y 3 ³ c1 =4;

0 y 1+1 y 2+ y 3 ³ c2 =3.

В примере 2.4 было найдено решение прямой задачи x1 опт= 2000, x2 опт =6000,

x3 опт = 2000,

max f= 26 000.

Для решения двойственной задачи симплекс-методом введем свободные переменные  u4, u5 и запишем ограничения в следующем виде:

1 y 1+0 y 2+1 y 3y 4 =4;

0 y 1+1 y 2+ y 3 y 5 =3.

Исходная двойственная задача записывается в табл. 2.12.

Таблица 2.12

cj

   

4000

6000

6000

0

0

 

Bx

A0

A1

A2

A3

A4

A5

4000

y1

4

1

0

1

-1

0

6000

y2

3

0

1

0

-1

 

D

34000

0

0

2000

-4000

-6000

В качестве направляющего столбца выбираем A3, так как D3=2000>0.

Выполнив первую итерацию симплекс-метода с направляющим элементом a13=1, получим табл. 2.13. Поскольку в индексной строке этой таблицы все оценки неположительны, то текущее базисное решение – оптимально.

Итак, мы нашли решение y1 опт=0, y2 опт =1/3, y3 опт =4. Очевидно,

min (4000y1+6000y2+6000y3)=26000.

Cледовательно   min g(y)= max f(x)= 26 000,

то есть теорема 2.5 выполняется.

Проверим, будут ли выполняться  теоремы 2.6, 2.7.

A1x опт=[1 0] [2000 6000]T=2000´1+6000´0=2000<b1=4000.

Откуда y1 опт=0, что совпадает с полученным результатом.

A2 x опт=a21 x 1 опт + a22 x 2 опт =0 x 1 опт + 1 x 2 опт = 0´2000+1´6000=b2,

поэтому y2опт ¹ 0.

Наконец,

A3 x опт=a31 x 1 опт + a32 x 2 опт =1x 1 опт + x 2 опт = 6000=b3,

поэтому y3опт ¹ 0.

Как видим, теорема 2.6 выполняется полностью.

Для проверки теоремы 2.7 выпишем ограничения двойственной задачи при оптимальных значениях переменных:

a11y1опт+a21y2опт+ a31y3опт-c1=1*0+0*1/3+1*4-4=0.

Поэтому в силу теоремы 2.7 x1 опт должно быть больше нуля. Следовательно, найдено решение (см. пример 2.4) x1 опт =2000 >0.

Аналогично для второго ограничения имеем

a12y1опт+a22y2опт+a32y3опт-c2=0+1*1/3+2/3*4-3=0.

В силу теоремы 2.7 x2опт должно быть больше нуля.

Раньше мы получили x2опт =6000.

Следовательно, теорема 2.7 полностью подтверждается.

Проверим справедливость соотношения (2.4.31) для рассмотренной пары двойственных задач (см. табл. 2.6, 2.13). Рассмотрим индексную строку табл.2.6. Учтем, что п=2, т=3.

y1опт=D(пр)n+1=D(пр)2+1=D3=0;

y2опт=D(пр)n+2=D(пр) 4=D4=1/3;

y3опт=D(пр)n+3=D(пр)5=D5=4;

Эти значения совпадают с найденным решением двойственной задачи в табл. 2.13. Рассмотрим теперь индексную строку табл. 2.13. Согласно соотношениям (2.4.31) имеем

Таблица 2.13

cj

   

4000

6000

6000

0

0

 

Bx

A0

A1

A2

A3

A4

A5

6000

y3

4

1

0

1

-1

0

6000

y2

-

1

0

-1

 

D

26000

-2000

0

0

-2000

-6000

x1 опт = -Dm+1дв=-D4дв =2000,

x2 опт = -Dm+2дв=-D5дв=6000.

x3 опт = -D6дв, и так как матрица ограничений табл. 2.13 состоит из 5 столбцов, то по правилу циклической перестановки x3 опт = -D6дв = -D1дв =2000. Это решение полностью совпадает с решением прямой задачи.

Таким образом, пользуясь соотношениями (2.4.31), решив прямую задачу, одновременно находим и решение двойственной задачи ,и наоборот. Этот вывод дает обоснование возможности перехода от прямой задачи к двойственной при т > п ,и наоборот.

Общий случай двойственности

В предыдущем разделе были установлены основные соотношения для пары двойственных задач ЛП при ограничениях в форме неравенств. Обобщим эти результаты на случай произвольных ограничений.

Пусть прямая задача ЛП задана в виде

                               максимизировать                            (2.4.32)

при условиях

;                               (2.4.33)

;                   (2.4.34)

 .                                         

Тогда двойственная задача по отношению к задаче (2.4.32)—(2.4.34) записывается так:

                                    минимизировать                              (2.4.35)   

при условиях

                       (2.4.36)

.                         (2.4.37)

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

1. Если переменная xj прямой задачи предполагается неотрицательной, то j-е условие системы (2.4.36) является неравенством.

2. Если на переменную xj не накладывается ограничение на знак, то j-е ограничение двойственной задачи (2.4.36) будет равенством.

Аналогично связаны знаки переменных двойственной задачи yi и соответствующие им ограничения прямой задачи.

Заметим, что если положить m1=m и n1=n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

Докажем справедливость соотношений (2.4.32) - (2.4.34) и (2.4.35) - (2.4.37), связывающих прямую и двойственную задачи.

Свяжем с каждой ЛП – задачей вида (2.4.32) - (2.4.34) следующую задачу с ограничениями в форме неравенств:

                           максимизировать         (2.4.38)

при условиях

;                     (2.4.39)

                      (2.4.40)

                                                                                    (2.4.41)

где n2=nn1 – число переменных задачи (2.4.32) - (2.4.34), на которые не наложено условие неотрицательности.

Установим соответствие между переменными задач (2.4.32) - (2.4.34) и (2.4.38) - (2.4.41). Сравнивая формы их записи, убеждаемся, что

n-мерный вектор х={x1,…,xn} и (n+n2)-мерный вектор х = {x1, x 2, …, } связаны соотношением

                (2.4.42)

Очевидно, каждому (n+n2)-мерному вектору x соответствует единственный n-мерный вектор x  , и вместе с тем произвольному

n-мерному вектору x соответствует целое семейство (n+n2)–мерных векторов х.

Таким образом, соответствие, устанавливаемое формулой (2.4.42), является однозначным только в одну сторону.

Вместе с тем среди семейства векторов х, соответствующих x, всегда существуют векторы с неотрицательными компонентами.

Пусть вектор x={x1, x2, …,}- план задачи (2.4.38) -(2.4.41). Используя соотношение (2.4.42), можно легко получить, что соответствующий вектор x является планом задачи. И наоборот, если x – план задачи

(2.4.32) - (2.4.34), то существует целое семейство планов x задачи (2.4.38) - (2.4.41), среди которых имеются заведомо неотрицательные.

Одним из них является вектор

где

j=1,2,…,n1,

j= n1+ 1, n1+ 2,…,n,

j=n+1,n+2,…,n+n2.

 
                                                                                  (2.4.43)

        Неотрицательность всех компонент очевидна, а соответствие векторов x и следуетет из равенства

 
 

где j=n1+1; n1+2,…,n...

Рассмотрим задачу (2.4.35) - (2.4.37), двойственную к задаче (2.4.32) - (2.4.34). Нетрудно показать, что она приводится к виду (2.4.32) - (2.4.34). Для этого достаточно положить j= -cj ; ij= -aij ; i= -bi. При этом задача (2.4.35) - (2.4.37) переходит в задачу

                                         минимизировать                      (2.4.44)

при условиях

 j=1, 2,…,n1;                      (2.4.45)

 j=n1+1; n1+2,…,n;                (2.4.46)

yi³0; i=1, 2, …, m1.                           (2.4.47)

Поэтому задаче (2.4.35) - (2.4.37) соответствует следующая задача с ограничениями в форме неравенств:

                        минимизировать          (2.4.48)

при условиях

 j=1, 2,…,n;              (2.4.49)

 j=n1+1; n1+2,…,n.        (2.4.50)

y¢i³0; i=1, 2, …, m+m2 ...                       (2.4.51)

где m2 = m – m1 – число переменных yi, на которые не наложено условие неотрицательности.

Вектор y={y1,…,ym}и соответствующий ему (m+m2) мерный вектор y={y1,…,}связанны соотношением

       (2.4.52)

Следовательно, каждому плану yзадачи (2.4.48) - (2.4.51) соответствует план у задачи (2.4.35) - (2.4.37), и наоборот: любой неотрицательный вектор, соответствующий плану (решению) задачи (2.4.35) - (2.4.37), является решением задачи (2.4.49) - (2.4.51). При этом, если уи у – два соответствующих друг другу решения, то из оптимальности одного из них непосредственно следует оптимальность  другого.

Запишем задачу, двойственную к (2.4.38) - (2.4.41). Непосредственной проверкой можно убедиться в том, что получим задачу в форме (2.4.48) - (2.4.51). Таким образом, задачи (2.4.38) - (2.4.41) и (2.4.48) -(2.4.51) с произвольными ограничениями(неравенства – равенства) также представляют собой двойственную пару.

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

Рассмотрим для примера теорему 2.5.

Если х и у допустимые решения прямой (2.4.32) - (2.4.34) и двойственной (2.4.35) - (2.4.37) задачи и если при этом = , то х и уоптимальные решения этих задач.

Доказательство. Допустим, что задача (2.4.32) - (2.4.34) разрешима и x–ее допустимое решение, а у – допустимое решение (план) задачи (2.4.35) - (2.4.37). Рассмотрим вектор х'={x1,…,},связанный с вектором х соотношениями (2.4.42), с неотрицательными компонентами. По доказанному выше х′ является решением задачи (2.4.38).

Воспользуемся тогда теоремой 2.5 для задач с ограничениями – неравенствами.

Согласно этой теореме, если х' и у'– допустимые решения пары двойственных задач и выполняется равенство

        (2.4.53)

то х' и у'– оптимальные решения  этой пары задач.

Используя соотношения (2.4.42), (2.4.52), связывающие соответствующие планы х' и х, у и у', получим

                   (2.4.54)

                       (2.4.55)

Таким образом, соотношения (2.4.53) и (2.4.54) – (2.4.55) – эквивалентны, поэтому планы хи у′– оптимальны.

Но по доказанному выше каждому оптимальному х соответствует единственный оптимальный план х, а каждому оптимальному плану усоответствует единственный план у.  Теорема доказана.

Аналогичным образом могут быть доказаны остальные теоремы двойственности для произвольных ограничений.

Пример 2.7. Рассмотрим задачу ЛП при произвольных ограничениях:

                                                    максимизировать 5x1+3x2+6x3                                          (1)

при условиях

x1 + 2x2 + x3 £ 18;

2x1 + 1x2 + x3 £ 16;

x1 + x2 + x3 = 10;                                                        (2)

x1, x2 ³ 0.                                                               (3)

Составляем задачу, двойственную к (1) - (3),  согласно общим правилам:

минимизировать 18y1+16 y 2+10 y 3

при условиях

y 1 + 2 y 2 + y 3 ³ 5;

2 y 1 + 1 y 2 + y 3 ³ 3;

y 1 + y 2 + y 3 = 6;                                                     (5)

y 1, y 2 ³ 0 .                                                             (6)

Найдем решение задачи (1) - (3). Поскольку на x3 не наложено условие неотрицательности, то заменим x 3 на пару переменных x 4, x 5, так что

x3= x4 - x5                                                               (7)

Подставляя (7) в (1) – (3), приходим к эквивалентной задаче:

                                                       максимизировать 5x1+3x2+6x4-6x5                                                                  (8)

при условиях

x1 + 2x2 + x4x5 £ 18;

2x1 + 1x2 + 3x4 –3x5 £ 16;                                             (9)

x1 + x2 + x4x5 = 10;

x1, x2, x4, x5 ³ 0.                                                    (10)

Решим задачу (8) - (10) симплекс-методом. Для этого введем свободные переменные x6, x7 в первое и второе ограничения и искусственную переменную x8 в третье ограничение (10) и целевую функцию.

Заполним начальную симплекс-таблицу 2.14.

Таблица 2.14

cj

   

5

3

6

-6

   

-М

 

Bx

A0

A1

A2

A4

A5

A6

A7

A8

0

х6

18

1

2

1

-1

1

0

0

0

x7

16

2

1

3

-3

0

1

0

-M

x5

10

1

1

1

-1

0

0

1

 

D

 

-M-5

-M-3

-M-6

6+M

0

0

0

Результаты последовательных итераций приводятся в табл. 3.15 – 2.17 соответственно.

Таблица 2.15

cj

   

5

3

6

-6

   

-M

 

Bx

A0

A1

A2

A 4

A 5

A 6

A 7

A 8

0

x6

10

0

-

1

-

0

5

x 1

8

1

-

0

0

-M

x 8

2

0

-

0

-

1

 

D

 

0

--

+

--

0

0

 
 
Таблица 2.16

cj

   

5

3

6

-6

   

-M

 

Bx

A0

A1

A2

A4

A5

A6

A7

A8

0

x 6

4

0

0

1

-1

1

1

-3

5

x 1

6

1

0

2

-2

0

1

-1

3

x 2

4

0

1

-1

1

0

-1

2

 

D

42

0

0

1

-1

0

2

M+1

Таблица 2.17

cj

   

5

3

6

-6

   

-M

 

Bx

A0

A1

A2

A4

A5

A6

A7

A8

0

х6

8

0

1

0

0

1

0

-1

5

x1

14

1

2

0

0

0

-1

3

-6

x5

4

0

1

-1

1

0

-1

2

 

D

46

0

1

0

0

0

1

M+3

Поскольку в индексной строке таблицы 2.17 нет отрицательных членов, то найдено оптимальное решение x1*=14; x5*=4; x6*=8; x2*=0= x4*= x7*=0;

С учетом, что x3= x4 - x5

x1*=14; x2*=0; x3*=-4; Lmax=46.              

Используя соотношения (2.4.31) найдем по индексной строке табл. 2.17 оптимальное решение двойственной задачи. Учтем, что т = п = 3, а столбцы A4 и A5 нужно рассматривать как один столбец. Тогда

y1 опт = D1+3=Dпр6=0;

y2 опт = D7=1;

y3 опт =3;

При этом решении все ограничения (5) - (6) выполняются, кроме того,

min (18y1+16y2+10y3)=46=L*max