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

На практике часть условий задачи ЛП определяется неточно, поэтому актуальным является вопрос о том, как изменяется оптимальное решение в случае малых изменений параметров модели. Большую помощь в исследовании изменения оптимального решения оказывает двойственная задача. Рассмотрим двойственную задачу к задаче математического программирования

Здесь P – множество простой структуры. Например . Для нахождения условного минимуму составляется функция Лагранжа. В регулярном случае она будет иметь вид

.

Определим две функции

.

Тогда исходной будет задача

А двойственной

.

Для стандартной задачи на максимум

двойственная будет выглядеть следующим образом

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

- количество переменных в двойственной задаче равно количеству ограничений в исходной задаче (напомним, что двойственные переменные являются множителями Лагранжа для ограничений исходной задачи);

- правые части ограничений исходной задачи () являются коэффициентами целевой функции в двойственной задаче;

- количество ограничений в двойственной задаче равно количеству переменных в исходной задаче;

- коэффициенты целевой функции исходной задачи () являются правыми частями ограничений в двойственной задаче;

- если исходная задача на максимум, соответственно ограничения имеют знак , то двойственная задача на минимум, а знак ограничений ;

- матрица ограничений двойственной задачи является транспонированной к матрице ограничений исходной задачи (так строка ограничений исходной задачи является столбцом ограничений в двойственной задаче).

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

Экономическая интерпретация двойственной задачи.

Экономическую интерпретацию рассмотрим на примере задачи о наилучшем использовании ресурсов (пункт 1.3, задача (1.5)). К руководству предприятия, использующего m видов ресурсов для выпуска n видов продукции, пришли представители другой фирмы и предложили продать им все ресурсы. Пусть - цена единицы i – го вида ресурса . Тогда фирма заплатит за все ресурсы

.

Цель фирмы купить ресурсы как можно дешевле, т.е. минимизировать это выражение

.

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

.

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

(1.6)

Таким образом, двойственные переменные являются с одной стороны множителями Лагранжа, а с другой оценками «ценности» соответствующих ресурсов. Эти оценки показывают «ценность» соответствующего ресурса для выпускающего продукцию предприятия при заданных: технологических коэффициентах , ценах на продукцию , запасах ресурсов , i = , j = .

Пример. Записать двойственную задачу для задачи о красках (1.1). В задаче четыре ограничения значит, двойственных переменных будет четыре. Так как переменных в исходной задаче две, то ограничений в двойственной задаче будет два. Вектор =(8, 6, 6, 3) правых частей ограничений исходной задачи будет вектором коэффициентов целевой функции в двойственной задаче. Вектор =(2, 3) коэффициентов целевой функции исходной задачи будет вектором правых частей ограничений в двойственной задаче. Так как исходная задача на максимум, то двойственная будет на минимум. В исходной задаче в ограничениях знак , а в двойственной задаче . Получаем

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

Дата добавления: 2014-12-27