ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ, ДВОЙСТВЕННОЙ К ИСХОДНОЙ ЗАДАЧЕ

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

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

Пусть задана каноническая задача линейного программирования:

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

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

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

сх ≤ bu                                   

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

Если задана каноническая задача линейного программирования

то задача линейного программирования

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

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

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

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

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

то двойственной по отношению к ней называется общая задача линейного программирования

где 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),

Поэтому говорят о паре взаимно двойственных задач.

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

и

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

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана общая задача линейного программирования:

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

D={ xcR ⁵ |

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

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

2 x₁ +3 x₂ +6 x₃ + x₄ -3 x₅≤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,

2 u₂ -3 u₃≥ -3,

u_1, u₃≥0 }