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

Содержание

1.    Двойственность в линейном программировании

2.   Несимметричные двойственные задачи. Теорема двойственности

3.   Симметричные двойственные задачи

4.   Виды математических моделей двойственных задач

5.   Двойственный симплексный метод

6.   Список используемой литературы

Двойственность в линейном программировании

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной

Решение двой­ственной задачи может быть получено из решения исходной и наоборот

Связующим фактом этих двух задач являются коэффици­енты C j   функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i систе­мы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограни­чений двойственной задачи

Рассмотрим задачу использования ресурсов

  У предприятия есть т видов ресурсов в количестве b i ( i = 1, 2, ..., m ) единиц, из которых выпускается n видов продукции. На изготовление1 ед. i -й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j =1,2, ..., n) количество ед. j -й продукций

Сформулируем исходную задачу. Определить вектор Х =( x 1 , x 2 , …, x n ), который удовлетворяет ограни­чениям

a 11 x 1 + a 12 x 2 + … + a 1n x n Ј b 1,

a 21 x 1 + a 22 x 2 + … + a 2n x n Ј b 2,                        x j і 0 (j =1,2, ..., n)

…………………………………

a m 1 x 1 + a m 2 x 2 + … + a mn x n Ј b m ,

и состовляет максимальное значение линейной функции

Z = C 1 x 1 + C 2 x 2 + … + C n x n ,

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j =1,2, ..., m) стоимость единицы i -го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j -й продукции, состовляет . Цена израсходованных ресурсов не должна превышать цены окончательного товара. Таким образом должно выполняться неравенство і C j , j =1,2, ..., n. Цена имеющихся ресурсов составляет

Сформулируем   двойственную задачу

Необходимо определить вектор Y =( y 1 , y 2 , …, y n ), удовлетворяющий ограни­чениям

a 11 y 1 + a 12 y 2 + … + a m1 y m Ј C 1,

a 12 y 1 + a 22 y 2 + … + a m2 y m Ј C 2,     y j і 0 (i =1,2, ..., m)

…………………………………

a 1n y 1 + a 2n y 2 + … + a mn y m Ј C m ,

Вектор   Y =( y 1 , y 2 , …, y n ) состовляет минимальное значение линейной функции

f   = b 1 y 1 + b 2 y 2 + … + b m y m

Переменные у i называются оценками или учетными, неявными ценами

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена еди­ницы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C i минимизировать общую стоимость затрат?

А исходную задачу определим следующим образом: сколько и. какой продукции x j   (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j   (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b i   (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении

Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования

Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как нера­венство, причем переменные могут быть и отрицательными

  Чтобы проще понимать постановку задачи будем интерпретировать ее в матричной форме

Сформулируем   двойственную задачу

  Необходимо определить матрицу-строку Y = ( y 1 , y 2 , …, y m ), которая максимизирует линейную функцию f = YA 0   и удовлетворяет ограничениям (1.1) YA Ј С.

Сформулируем исходную задачу. Определить матрицу-столбец X = ( x 1 , x 2 , …, x n ), которая минимизирует линейную функцию Z = СХ и удовлетворяет ограничениям (1.2) AX = A 0 , Х і 0

Как в исходной так и в двойственной задачах А = ( a ij ) — матрица коэффициентов системы ограничений, A 0 = ( b 1 , b 2 , …, b m ) — матрица-столбец, C = ( c 1 , c 2 , …, c n ) - матрица-строка

Теорема двойственности устанавливает связь между оптимальными планами пары двой­ственных зада

Теорема двойственности гласит: если из пары двойствен­ных задач одна обладает оптимальным планом, то и другая имеет ре­шение, причем для экстремальных значений линейных функций выпол­няется соотношение min Z = max f . Если линейная функция одной из задач не ограничена, то другая не имеет решения

Доказательство. Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис со­стоит из т первых векторов A 1 , A 2 , ..., A m . Таким образом, симплекс­ная таблица примет вид, приведенный в табл. 1.1

Таблица 1.1

Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A 1 , A 2 , ..., A m .   Приведенная выше таблица состоит из коэффици­ентов разложения векторов A 1 , A 2 , ..., A n исходной системы по векто­рам базиса.   В этой таблице каждому вектору A j соответствует   вектор X j

Найдем оптимальный план:

(1.3)                    A 0 = DX*,

где X* = ( x * 1 , x * 2 , …, x * m )

Получим:

(1.4) A j = DX j ( j = 1,2, ,.., n)

  - это матрица, составленная из коэффициентов раз­ложения векторов А j ( j = 1, 2, ..., n ), представленных в приведенной выше таблице

Используя соотношения (1.3) и (1.4), получаем:

(1.5)                       A = D ,   D -1 A = ,

(1.6)                     A 0 =DX*;   D -1 A 0 = X*,

(1.7)                         min Z= C*X*,

(1.8)                         = C* —C Ј 0,

где С* = ( C * 1 , C * 2 , …, C * m ), С = ( C 1 , C 2 , …, C m , C m +1 , …, C n ), a   = (C*X 1 – C 1 ; С*Х 2   - С 2 , ..., C*X n – C n ) = (Z 1 – С 1 ; Z 2   - C 2 ; ..., Z n — C n ) — вектор, компоненты которого неположительны, так как они совпадают с Z j — C j   Ј 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*A 0 . Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10)                    f (Y*) = Y*A 0 = C * D -1 A 0 = C*X* = min Z(X)

Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA 0 = 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 = x 2 – x 4 – 3 x 5 при ограничениях

x 1 + 2x 2           - x 4 + x 5   = 1,

- 4x 2 + x 3 + 2x 4 – x 5 = 2,   x ij і 0 (j = 1, 2, …, 6)

   3x 2   + x 5 + x 6 = 5,

Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец

             1                                   1     2     0     -1     1     0

A 0 =       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 = y 1 + 2 y 2 +5 y 3 при ограничениях

  y 1 Ј 0,

2y 1 – 4y 2 + 3y 3 Ј 1,

           y 2            Ј 0,

-y 1 + 2y 2            Ј -1,

y 1 –    y 2 +     y 3   Ј -3,    y 3   Ј 0

Решение исходной задачи    находим    симплексным    методом (табл. 1.2)

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Z min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойствен­ной задачи находится из соотношения Y* = C*D -1 , где матрица D -1 - матрица, обратная матрице, составленной из компонент векторов, вхо­дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A 5 , A 4 , A 2 ; значит,

                                   1   -1     2

D = ( A 5 , A 4 , A 2 ) =       -1    2    -4

                                    1    0     3

Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A 1 , A 3 , A 6 четвертой итерации:

               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),

т. е. y i = С*Х i , где Х i — коэффициенты разложения последней ите­рации, стоящие в столбцах векторов первоначального единичного базиса

Итак, i -ю двойственную переменную можно получить из значения оценки ( m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный бази c , если к ней приба­вить соответствующее значение коэффициента линейной функции:

у 1 = — 19/3 + 0 = — 19/3;   y 2 = -11/3 + 0 = -11/3; у 3 = -1/3+0 = -1/3. При этом плане max f = -46/3

Разновидностью двойственных задач линейного , программирования    являются двойственные симметричные задачи, в ко­торых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойст­венные переменные налагается условие неотрицательности

Исходная задача. Найти матрицу-столбец Х = ( x 1 , x 2 , …, x n ), которая удовлетворяет системе ограничений

(1.12).    АХ>А 0 , Х>0 и минимизирует линейную функцию Z = СХ

Двойственная задача. Найти матрицу-строку Y = ( y 1 , y 2 , …, y n ), которая удовлетворяет системе ограничений YA Ј C, Y і 0 и максимизирует линейную функцию f = YA 0

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

Используя симметричность, можно выбрать задачу, более удоб­ную для решения. Объем задачи, решаемой с помощью ЭВМ, ограни­чен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формули­ровке. При вычислениях без помощи машин использование двойствен­ности упрощает вычисления

Исходная задача. Найти минимальное значение линейной функции Z = x 1 + 2 x 2 + 3 x 3 при ограничениях

  2x 1 + 2x 2 - x 3 і 2,

   x 1 - x 2 - 4x 3   Ј -3,             x i і 0 (i=1,2,3)

   x 1 + x 2 - 2x 3 і 6,

  2 x 1 + x 2 - 2 x 3 і 3,

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1

Двойственная задача. Найти максимум линейной функции f = 2 y 1 + 3 y 2 + 6 y 3 + 3 y 4 при ограничениях

2y 1   - y 2   + y 3 + 2y 4   Ј 1,

2y 1 + y 2   + y 3 +   y 4    і 2,

  -y 1 + 4y 2 - 2y 3 - 2y 4 і 3,

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

Для решения двойственной задачи необходимо ввести три допол­нительные переменные. Система ограничений не требует предваритель­ных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов

Двойственную задачу решаем симплексным методом (табл. 1.3)

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f max = 21/2

Оптимальный план исходной задачи находим, используя оценки ( m + 1)-й строки последней итерации, стоящие в столбцах A 5 , A 6 , A 7 : x 1 = 3/2 + 0 = 3/2; x 2 = 9/2 + 0 = 9/2; x 3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функ­ция достигает наименьшего значения: Z min =21/2

Т а б л и ц а 1.3

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

Симметричные задачи

(1) Исходная задача             Двойственная задача

           Z min = CX;                            f max = YA 0 ;

            AX і A 0 ;                             YA Ј С

             X і 0.                                  Y і 0

  (2) Исходная задача              Двойственная задача

           Z max = CX;                           f min = YA 0 ;

            AX Ј A 0 ;                             YA і С

             X і 0.                                  Y і 0

Несимметричные задачи

(3) Исходная задача             Двойственная задача

         Z min = CX ;                           f max = YA 0 ;

            AX = A 0 ;                            YA Ј С

             X і 0

(4) Исходная задача             Двойственная задача

           Z max = CX;                           f min = YA 0 ;

            AX = A 0 ;                             YA і С

             X і 0

Поэтому до того, как сформулировать двойственную задачу для данной исходной, необходимо систему ограничений исходной задачи преобразовать должным образом

Приведем пример математиче­ской модели двойственной задачи для следующей исходной

Следует определить минимальное значение линейной функции Z = 2 x 1 + x 2 + 5 x 3 при ограничениях:

x 1 –   x 2 –    x 3   Ј 4,

x 1 –   5 x 2 + x 3   і 5,    x j і 0 ( j = 1, 2, 3)

2 x 1 – x 2 + 3 x 3 і 6,

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

Прежде чем записать двойственную задачу, необходимо чтобы ее модель была представлена в   виде (1). Для этого следует сделать переход, который осуществляется умножением первого не­равенства на -1

Исходная задача:

Z min = 2 x 1 + x 2 + 5 x 3 при ограничениях

- x 1 +   x 2 +    x 3 і -4,

x 1 –   5 x 2 + x 3   і 5,                   x j і 0 ( j = 1, 2, 3)

2 x 1 – x 2 + 3 x 3 і 6,

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

f min = -4 x 1 + 5 x 2 + 6 x 3 при ограничениях

-y 1 +   y 2 +   2y 3 Ј 2,

y 1   – 5y 2   -   y 3   Ј 1,                   y i і 0 (i = 1, 2, 3)

2y 1 + y 2 + 3y 3 Ј 5,

Теорема: если при подстановке компонент оптимального пла­на в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.Если i-я компонента оптимального плана двойственной задачи по­ложительна, то    i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство

Для получения решения исходной задачи можно перейти к двой­ственной. А используя оценки ее опти­мального плана, можно определить оптимальное решение исходной задачи

Если рассмо­треть первую симплексную таблицу с единичным дополнительным ба­зисом, тогда переход к двойственной задаче не обязателен. Это связано с тем, что в столбцах определена исходная задача, а в строках - двойственная

b i являются оценками плана двойственной задачи. С j являются оценками плана исходной задачи

Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана ис­ходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи

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

Допустим   нужно определить исходную задачу линейного программиро­вания, которая поставлена в общем виде: минимизировать функцию Z =СХ при АХ = A 0 , Х і 0. Значит в двойственной задаче следует максимизировать функцию f = YA 0 при YA Ј С. Пусть определен следующий базис D = (A 1 , А 2 , ..., А i , ..., А m ),. Причем в нем хотя бы одна из компонент вектора Х = D -1 A 0 = (x 1 , x 2 , ..., x i , ..., x m ) отрицатель­ная. Для всех векторов A j используется следующее соотно­шение Z j – C j Ј 0 (i = 1,2, ..., n )

Пользуясь теоремой двойственности, Y = С баз D -1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двой­ственной задачи должны быть неотрицательными и выбранный бази­с X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны

Поэтому, следует исключить из базиса исходной задачи вектор А i , который соответствует компоненте x i < 0.   Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи

Просмат­риваем i -ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет   x ij < 0, тогда линейная функция двойственной задачи не ограничена на многограннике реше­ний. Поэтому нет решений исходной задачи

В противном случае для столбцов, имеющих отрицательные значения, определяем q 0 j = min ( x i / x ij ) і 0 . Также находим вектор, который соответствует min q 0 j (Z j — C j ) при решении исходной задачи на максимум, а также max q 0 j (Z j — C j ) при значении исходной задачи на минимум

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

Допустим, что q 0 j = min ( x i / x ij ) = 0, т. е. x i = 0, тогда x ij   выбирается как раз­решающий элемент, но лишь тогда, когда x ij > 0

Данный подход к решению задачи не приводит к росту коли­чества отрицательных компонент вектора X. Пока не будет получено Х і 0, процесс не прекращается

Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи

Используя при решении, алгоритм двойственного симплексного метода условие Z j – C j Ј 0 допускается не учитывать, пока не будут исключены все х i < 0

Обычным симплексным ме­тодом определяется оптимальный план. Этот метод обычно используется при условии, что все х i < 0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q 0 j = m ax ( x i / x ij ) > 0

Задачи линей­ного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положи­тельном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограниче­ний

Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. “Наука”, 1980 г

Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. “Финансы и статистика”, 1998 г