Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

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

   5.1. Понятие двойственной задачи ЛП
   5.2. Общая схема построения двойственной задачи
   5.3. Пример построения двойственной задачи

5.1. Понятие двойственной задачи ЛП.

Пусть задана каноническая задача ЛП

    (5.1)

Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m-мерный вектор, то

cx = cx+u(-Ax+b) = (c-uA)x+bu

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х≥0 справедливо неравенство

сх≤bи                          (5.2)

Стремясь получить наилучшую оценку (5.2), мы приходим к формулировке некоторой новой экстремальной задачи, кото­рая в некотором смысле логически сопряжена с задачей (5.1) и называется двойственной. Оговоримся, что приведенные рас­суждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже фор­мальному определению двойственной задачи линейного про­граммирования.

Если задана каноническая задача ЛП

    (5.3)

то задача ЛП

       (5.4)

называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к  (D*, f*)  назы­вается прямой (или исходной).

5.2. Общая схема построения двойственной задачи.

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

Если задана общая задача ЛП

    (5.5)50

где D определяется системой уравнений и неравенств

то двойственной по отношению к ней называется общая задача ЛП

  (5.6)

где D* определяется системой уравнений и неравенств

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1.  Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2.  Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3.  Матрица ограничений задачи А транспонируется.

4.  Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj≥0 или ui≥0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (аjи≥сj или aixbi).

5.  Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aixbi или аjи≥сj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui≥0 или хj≥0).

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей:

((D*)*, (f*)*)≡(D, f),

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

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

    (5.3)

и

      (5.7)

 

5.3. Пример построения двойственной задачи

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП

fmax(x)= 5x1 -2x2 +7x3 +4x4 -3x5

D={xcR5 |

4x1 +x2 -x3 +x4                  ≤2,

       5x2 +x3 -6x4 +2x5 =4,

2x1 +3x2 +6x3 +x4 -3x5≤5,

x2, x5≥0 }

тогда двойственной к ней будет задача

f*min(u)= 2u1 +4u2 +5u3

D={ucR3 |

4u1          +2u3=5,

  u1 +5u2 +3u3≥ -2,

 -u1 +  u2 +6u3=7,

  u1 -6u2 +  u3=4,

        2u2  -3u3 -3,

u1, u3≥0 }

 

Источник:
Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс").
Раздел 1.6. Теория двойственности в линейном программировании

 


Далее: 6. Транспортная задача

Вернуться в Начало

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх