Доказательства теоремы двойственности

Двойственный симплекс-метод и доказательство
теоремы двойственности.
Содержание
1.   Двойственность в линейном программировании 3
2.  Несимметричные двойственные задачи. Теорема двойственности. 4
3.  Симметричные двойственные задачи 9
4.  Виды математических моделей двойственных задач 11
5.  Двойственный симплексный метод 12
6.  Список используемой литературы 14

1.   Двойственность в линейном программировании
Понятие двойственности. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной.
Связь исходной и двойственной задач состоит в том, что коэффици¬енты Cj  функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены Bi систе¬мы ограничений исходной задачи служат коэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограни¬чений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двой¬ственной задачи может быть получено из решения исходной и наоборот.
В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ..., m) единиц, из которых производится n видов продукций. Для производ¬ства 1 ед. i-й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ..., n) количество ед. j-й продукций, Тогда исходную задачу сформулируем так.
Найти вектор Х =(x1, x2, …, xn), который удовлетворяет ограни¬чениям
a11x1 + a12x2 + … + a1nxn  b1,
a21x1 + a22x2 + … + a2nxn  b2,                       xj  0 (j =1,2, ..., n)
…………………………………
am1x1 + am2x2 + … + amnxn  bm,
и доставляет максимальное значение линейной функции
Z = C1x1 + C2x2 + … + Cnxn,
Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через уi (j =1,2, ..., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна  . Стоимость затрачен¬ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство   Cj, j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится величиной  . Итак, двойственную задачу  можно сформулировать следующим образом.
Найти вектор Y =(y1, y2, …, yn), который удовлетворяет ограни¬чениям
a11y1 + a12y2 + … + am1ym  C1,
a12y1 + a22y2 + … + am2ym  C2,                       yj  0 (i =1,2, ..., m)
…………………………………
a1ny1 + a2ny2 + … + amnym  Cm,
и доставляет минимальное значение линейной функции
f  = b1y1 + b2y2 + … + bmym.
Рассмотренные исходная и двойственная задачи могут быть эко¬номически интерпретированы следующим образом.
Исходная задача. Сколько и. какой продукции xj  (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях Cj  (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi  (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.
Д в о й с т в е н н а я  з а д а ч а. Какова должна быть цена еди¬ницы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Ci минимизировать общую стоимость затрат?
Переменные уi называются оценками или учетными, неявными ценами.
Многие задачи линейного программирования первоначально ста¬вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.
 2.  Несимметричные двойственные задачи. Теорема двойственности.
В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде нера¬венств, причем в последней переменные могут быть и отрицательными. Для простоты доказательств постановку задачи условимся записывать в матричной форме.
Исходная задача. Найти матрицу-столбец X = (x1, x2, …, xn), которая удовлетворяет ограничениям
(1.1)                        AX = A0, Х  0
и минимизирует линейную функцию Z = СХ.
Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, ym), которая удовлетворяет ограничениям
(1.2)                         YA  С
и максимизирует линейную функцию f = YA0
В обеих задачах C = (c1, c2, …, cn) - матрица-строка, A0 = (b1, b2, …, bm) — матрица-столбец, А = (aij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двой¬ственных задач устанавливает следующая теорема.
Теорема (теорема двойственности). Если из пары двойствен¬ных задач одна обладает оптимальным планом, то и другая имеет ре¬шение, причем для экстремальных значений линейных функций выпол¬няется соотношение
min Z = max f.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
Д о к а з а т е л ь с т в о. Предположим, что исходная задача об¬ладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис со¬стоит из т первых векторов A1, A2, ..., Am. Тогда последняя симплекс¬ная таблица имеет вид табл. 1.1.
Т а б л и ц а 1.1
 
i Базис С базиса A0 C1 C2 … Cm Cm+1 … cn
    A1 A2 … Am Am+1 … An
1
2
.
.
.
m A1
A2
.
.
.
Am C1
C2
.
.
.
Cm x1
x2
.
.
.
xm 1
0
.
.
.
0 0
1
.
.
.
0 ...
...
.
.
.
. 0
0
.
.
.
1 x1, m+1
x2, m+1
.
.
.
xm, m+1 …
…
.
.
.
… x1n
x2n
.
.
.
xmn
m+1 Zi - Cj Z0 Z1 – C1 Z2 – C2 ... Zm – Cm Zm+1 – Cm+1 … Zn – Cn

Пусть D — матрица, составленная из компонент векторов оконча¬тельного базиса A1, A2, ..., Am; тогда табл. 1.1 состоит из коэффици¬ентов разложения векторов A1, A2, ..., An исходной системы по векто¬рам базиса, т. е. каждому вектору Aj в этой таблице соответствует та¬кой вектор Xj что
(1.3)                   Aj = DXj (j= 1,2, ,.., n).
Для оптимального плана получаем
(1.4)                   A0 = DX*,
где X* = (x*1, x*2, …, x*m).
Обозначим через   матрицу, составленную из коэффициентов раз¬ложения векторов Аj (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:
(1.5)                      A = D ,  D-1A =  ,
(1.6)                    A0=DX*;  D-1A0 = X*,
(1.7)                        min Z= C*X*,
(1.8)                         = C* —C  0,
где С* = (C*1, C*2, …, C*m), С = (C1, C2, …, Cm, Cm+1, …, Cn), a   = (C*X1 – C1; С*Х2  - С2, ..., C*Xn – Cn) = (Z1 – С1; Z2  - C2; ..., Zn — Cn) — вектор, компоненты которого неположительны, так как они совпадают с Zj — Cj   0, соответствующими оптимальному плану.
Оптимальный план исходной задачи имеет вид X* = D-1 А0, поэтому оптимальный план двойственной задачи ищем в виде
(1.9)                           Y* = C*D-1.
Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA — С  0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим
Y* А – С = С* D-1А – С = С*   - С  0,
откуда находим Y*A  С.
Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двой¬ственной задачи f (Y*) = Y*A0. Учитывая соотношения (1.9), (1.6) и (1.7), имеем
(1.10)                   f (Y*) = Y*A0 = C*D-1 A0 = C*X* = min Z(X).
Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи.
Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA0=f (Y), YAX  СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство
(1.11)                    f (Y)  Z (X).
Этим же соотношением связаны и экстремальные значения max f (Y)   min Z (Х). Из последнего неравенства заключаем, что максималь¬ное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение [см. (1.10)] f (Y) достигает при плане Y*, следовательно, план Y* — оптимальный план двойственной задачи.
Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотно¬шение max f (Y) = min Z (X).
Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следу¬ет, что f (Y)  - . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.
Аналогично предположим, что линейная функция двойственной за¬дачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X)  +. Это выражение также лишено смысла, поэтому исходная задача не име¬ет решений.
Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой.
Исходная задача. Найти минимальное значение линейной функ¬ции Z = x2 – x4 – 3x5 при ограничениях
x1 + 2x2          - x4 + x5         = 1,
    - 4x2 + x3 + 2x4 – x5         = 2,               xij  0 (j = 1, 2, …, 6)
      3x2                  + x5 + x6 = 5,
Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец
             1                                  1    2    0    -1    1    0
A0 =      2                     A =       0   -4    1     2   -1    0
             3                                  0    3    0     0    1    1
              1     0     0
              2    -4     3
A’’ =       0     1     0
             -1     2     0
              1    -1     0
              0     0     1
Двойственная задача. Найти максимальное значение линейной функции f = y1 + 2y2 +5y3 при ограничениях
 y1                      0,
2y1 – 4y2 + 3y3  1,
           y2            0,
-y1 + 2y2            -1,
y1 –   y2 +    y3   -3,
                    y3   0.
Решение исходной задачи   находим   симплексным   методом (табл. 1.2).
i Базис С базиса A0 0 1 0 -1 -3 0
    A1 A2 A3 A4 A5 A6
1
2
3 A1
A3
A6 0
0
0 1
2
5 1
0
0 2
-4
3 0
1
0 -1
2
0 1
-1
1 0
0
1
m + 1 Zi - Cj 0 0 -1 0 1 3 0
1
2
3 A5
A3
A6 -3
0
0 1
3
4 1
1
-1 2
-2
1 0
1
0 -1
1
1 1
0
0 0
0
1
m + 1 Zi - Cj -3 -3 -7 0 4 0 0
1
2
3 A5
A4
A6 -3
-1
0 4
3
1 2
1
-2 0
-2
3 1
1
-1 0
1
0 1
0
0 0
0
1
m + 1 Zi - Cj -15 -7 1 -4 0 0 0
1
2
3 A5
A4
A2 -3
-1
1 4
11/3
1/3 3
-1/3
-2/3 0
0
1 1
1/3
-1/3 0
1
0 1
0
0 0
2/3
1/3
m + 1 Zi - Cj -46/3 -19/3 0 -11/3 0 0 -1/3

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Zmin = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойствен¬ной задачи находится из соотношения Y* = C*D-1, где матрица D-1 - матрица, обратная матрице, составленной из компонент векторов, вхо¬дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5, A4, A2; значит,
                                   1  -1    2
D = (A5, A4, A2) =      -1   2   -4
                                   1   0    3
Обратная матрица D-1 образована из коэффициентов, стоящих в столбцах A1, A3, A6 четвертой итерации:
                2       1       0
D-1 =     -1/3    1/3    2/3
             -2/3   -1/3    1/3
Из этой же итерации следует С* = (— 3; —1; 1). Таким образом
                                                                  2       1       0
                     Y = С*D-1 = (-3; -1; 1) •     -1/3    1/3    2/3
                                                               -2/3   -1/3    1/3
Y*=(-19/3; -11/3; -1/3),
т. е. yi = С*Хi, где Хi — коэффициенты разложения последней ите¬рации, стоящие в столбцах векторов первоначального единичного базиса.
Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней приба¬вить соответствующее значение коэффициента линейной функции:
у1 = — 19/3 + 0 = — 19/3;  y2 = -11/3 + 0 = -11/3; у3 = -1/3+0 = -1/3. При этом плане max f = -46/3.
3.  Симметричные двойственные задачи
Разновидностью двойственных задач линейного , программирования   являются двойственные симметричные задачи, в ко¬торых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойст¬венные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений
(1.12).                     АХ>А0, Х>0
и минимизирует линейную функцию Z = СХ.
Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA  C, Y  0 и максимизирует линейную функцию f = YA0.
Систему неравенств с помощью дополнительных переменных мож¬но преобразовать в систему уравнений, поэтому всякую пару симмет¬ричных двойственных задач можно преобразовать в пару несимметрич¬ных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удоб¬ную для решения. Объем задачи, решаемой с помощью ЭВМ, ограни¬чен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формули¬ровке. При вычислениях без помощи машин использование двойствен¬ности упрощает вычисления.
Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях
 2x1 + 2x2 - x3  2,
   x1 - x2 - 4x3   -3,            xi  0 (i=1,2,3)
   x1 + x2 - 2x3  6,
 2x1 + x2 - 2x3  3,
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.
Двойственная задача. Найти максимум линейной функции f = 2y1+ 3y2 + 6y3 + 3y4 при ограничениях
2y1  - y2  + y3 + 2y4   1,
2y1 + y2  + y3 +  y4    2,
 -y1+ 4y2 - 2y3 - 2y4  3,
Для решения исходной задачи необходимо ввести четыре дополни¬тельные переменные и после преобразования системы - одну искус¬ственную. Таким образом, исходная симплексная таблица будет состо¬ять из шести строк и девяти столбцов, элементы которых подлежат преобразованию.
Для решения двойственной задачи необходимо ввести три допол¬нительные переменные. Система ограничений не требует предваритель¬ных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.
Двойственную задачу решаем симплексным методом (табл. 1.3).
Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2.
Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функ¬ция достигает наименьшего значения: Zmin =21/2.
Т а б л и ц а 1.3
i Базис С базиса A0 2 3 6 3 0 0 0
    A1 A2 A3 A4 A5 A6 A7
1
2
3 A5
A3
A7 0
0
0 1
2
3 2
2
-1 -1
1
4 1
1
-2 2
-1
-2 1
0
0 0
1
0 0
0
1
m + 1 Zi - Cj 0 -2 -3 -6 -3 0 0 0
1
2
3 A3
A6
A7 6
0
0 1
1
5 2
0
3 -1
2
6 1
0
0 2
-1
2 1
-1
2 0
1
0 0
0
1
m + 1 Zi - Cj 6 10 -9 0 9 6 0 0
1
2
3 A3
A2
A7 6
3
0 3/2
½
2 2
0
3 0
1
0 1
0
0 3/2
-1/2
4 ½
-1/2
5 ½
½
3 0
0
1
m + 1 Zi - Cj 21/2 10 0 0 9/2 3/2 9/2 0

4.  Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.
Н е с и м м е т р и ч н ы е   з а д а ч и
(1) Исходная задача            Двойственная задача
         Zmin = CX;                          fmax = YA0;
            AX = A0;                          YA  С.
             X  0.
(2) Исходная задача            Двойственная задача
           Zmax = CX;                          fmin = YA0;
            AX = A0;                            YA  С.
             X  0.
С и м м е т р и ч н ы е   з а д а ч и
(3) Исходная задача            Двойственная задача
           Zmin = CX;                          fmax = YA0;
            AX  A0;                            YA  С.
             X  0.                                 Y  0.
 (4) Исходная задача             Двойственная задача
           Zmax = CX;                          fmin = YA0;
            AX  A0;                            YA  С.
             X  0.                                 Y  0.
Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Запишем, например, математиче¬скую модель двойственной задачи для следующей исходной.
Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях
x1 –  x2 –   x3   4,
x1 –  5x2 + x3   5,                  xj  0 (j = 1, 2, 3).
2x1 – x2 + 3x3 6,
Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель долж¬на иметь вид (3). Переход осуществляется умножением первого не¬равенства на -1.
Исходная задача:
Zmin = 2x1 + x2 + 5x3 при ограничениях
-x1 +  x2 +   x3  -4,
x1 –  5x2 + x3   5,                  xj  0 (j = 1, 2, 3).
2x1 – x2 + 3x3 6,
Двойственная задача:
fmin = -4x1 + 5x2 + 6x3 при ограничениях
-y1 +  y2 +  2y3  2,
y1  – 5y2  -  y3   1,                  yi  0 (i = 1, 2, 3).
2y1 + y2 + 3y3  5,
Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального пла¬на в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
Если i-я компонента оптимального плана двойственной задачи по¬ложительна, то   i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.
5.  Двойственный симплексный метод
В п. 2 и п. 3 настоящего параграфа было показано, что для получения решения исходной задачи можно перейти к двой¬ственной и используя оценки ее опти¬мального плана, определить оптимальное решение исходной задачи.
Переход к двойственной задаче не обязателен, так как если рассмо¬треть первую симплексную таблицу с единичным дополнительным ба¬зисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана ис¬ходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит на¬звание двойственного симплексного метода,
Пусть необходимо решить исходную задачу линейного программиро¬вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х  0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA  С. Допустим, что выбран такой базис D = (A1, А2, ..., Аi, ..., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ..., xi, ..., xm) отрицатель¬ная (например, xi < 0), но для всех векторов Aj выполняется соотно¬шение Zj – Cj  0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази¬се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой¬ственной задачи должны быть неотрицательными.
Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствую¬щий отрицательной оценке,— включить в базис двойственной задачи.
Для выбора вектора, включаемого в базис исходной задачи, просмат¬риваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше¬ний, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля¬ем 0j= min (xi/xij)  0 и определяем вектор, соответствующий max 0j(Zj — Cj) при решении исходной задачи на минимум и min 0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ¬ходимо исключить из базиса исходной задачи, определяется направ¬ляющей строкой.
Если 0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за раз¬решающий элемент только в том случае, если xij > 0. Такой выбор раз¬решающего элемента на данном этапе не приводит к увеличению коли¬чества отрицательных компонент вектора X. Процесс продолжаем до получения Х  0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.
В процессе вычислений по алгоритму двойственного симплексного метода условие Zj – Cj  0 можно не учитывать до исключения всех хi < 0, затем оптимальный план находится обычным симплексным ме¬тодом. Это удобно использовать, если все хi 0.
Двойственным симплексным методом можно решать задачи линей¬ного программирования, системы ограничений которых при положи¬тельном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограниче¬ний, а также размеры симплексной таблицы.
6. Список используемой литературы
1. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.
2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.