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 или u_i≥0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (а^jи≥с_j или a_ix≤b_i).

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

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

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

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

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

    (5.3)

и

      (5.7)

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

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

f_max(x)= 5x₁ -2x₂ +7x₃ +4x₄ -3x₅

D={xcR⁵ |

4x₁ +x₂ -x₃ +x₄                  ≤2,

       5x₂ +x₃ -6x₄ +2x₅ =4,

2x₁ +3x₂ +6x₃ +x₄ -3x₅≤5,

x_2, x₅≥0 }

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

f*_min(u)= 2u₁ +4u₂ +5u₃

D={ucR³ |

4u₁          +2u₃=5,

  u₁ +5u₂ +3u₃≥ -2,

 -u₁ +  u₂ +6u₃=7,

  u₁ -6u₂ +  u₃=4,

        2u₂  -3u₃≥ -3,

u_1, u₃≥0 }

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