Теоремы двойственности

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

· Если целевая функция одной из пары двойственных задач не ограничена, то вторая задача вовсе не имеет решений.

· Пара двойственных задач не имеет решений.

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

· Если в результате подстановки оптимального плана исходной задачи в систему ограничений этой задачи i-е ограничение обращается в равенство, то соответствующая i-я компонента оптимального плана двойственной задачи равна нулю.

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

Пример 2.4.1.Записать двойственную задачу дляЗЛП(2.2.1), (2.2.2). Выписать решение двойственной задачи.

Решение. Поскольку исходная задача на максимум, то во всех ограничениях системы (2.2.1) должен быть знак “ ”. Для этого обе части третьего неравенства умножаем на (–1) и меняем знак неравенства на противоположный. Таким образом, получим:

(2.4.1)

max z = x₁ + 4x₂ (2.4.2)

Для задачи (2.4.1), (2.4.2) запишем двойственную. Для этого:

Выпишем матрицу коэффициентов при неизвестных в системе ограничений (2.4.1)

и транспонируем ее (т.е. поменяем местами строки и столбцы):

.

На основе транспонированной матрицы составим систему ограничений двойственной задачи, причем в неравенствах ограничений будет знак “ ” и в правой части этих неравенств будут стоять коэффициенты целевой функции (2.4.2), т.е. 1 и 4:

Коэффициентами целевой функции двойственной задачи будут числа, стоящие в правой части ограничений исходной задачи (2.4.1), причем целевая функция будет минимизироваться:

min f = – 5y₁ + 6y₂ – 7y₃ .

Итак, двойственная задача имеет вид (2.4.3), (2.4.4):

(2.4.3)

min f = – 5y₁ + 6y₂ – 7y₃ . (2.4.4)

Исходная и двойственная ЗЛП имеют разный экономический смысл. Решая одну задачу можно не решать другую, а сразу выписать ее решение. Решение двойственной задачи y₁, y₂, y₃ находится в z-строке последней симплексной таблицы в дополнительных столбцах (а именно, в столбцах р₃, р₄, р₅). Нужно помнить, что решение выписывается с учетом неотрицательности переменных. В нашем случае решение следующее:

y₁ = 0, y₂ = 9/2, y₃ = 1/2.

При подстановке этого решения в целевую функцию двойственной задачи (4.4) должно получится число, стоящее в z-строке последней симплексной таблицы в столбце р₀. Проверим:

min f = max z.

Пример 2.4.2.Записать двойственную задачу дляЗЛП

min z = -7 x₁ + 3x₂ .

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

Целевая функция при этом остается прежней, а именно: min z =-7 x₁+3x₂. Выпишем матрицу, состоящую из коэффициентов при неизвестных в системе ограничений и транспонируем: .

На основе составим систему ограничений для двойственной задачи, причем в ограничениях будет знак “ ” и в правой части неравенств будут стоять коэффициенты из целевой функции исходной задачи. Целевая функция будет максимизироваться и состоять из коэффициентов, стоящих в правой части неравенств исходной задачи. Таким образом, двойственная задача будет иметь вид:

max f = y₁ – 5y₂ + 6y₃ .