Постановка двойственных задач
Симметричные двойственные задачи
Рассмотрим задачу линейного программирования в стандартной форме
| (1)
| ,
или, в матричной форме,
| (2)
| Рассмотрим теперь следующую задачу
| (3)
| ,
или, в матричной форме,
| (4)
| Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4) ) называются двойственнымидруг другу задачами в симметричной форме.
Несимметричная двойственная задача
Исходная задачаимеет вид:
| (5)
| ,
или, в матричной форме,
| (6)
| Двойственная задача в несимметричной форме имеет вид
| (7)
| или, в матричной форме,
| (8)
| Обратите внимание на то, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных.
Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу. При желании, получившуюся двойственную задачу также можно привести к какой-либо нестандартной форме.
Экономическая интерпретация двойственной задачи в симметричной форме
Исходная задача:
Обычно эта задача связывается с задачей максимизации дохода при производстве некоторой продукции при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа. Что же представляет двойственная задача по своему смыслу?
Целевая функция двойственной задачи: ,
а ограничения: , где (1) — затраты i-го ресурса на производство единицы продукции j-го типа, а (2) — доход от продажи единицы продукта i-го типа. Поэтому в целевой функции на месте (?)получаем смысл стоимости всех ресурсов, т. е. Задача приобретает смысл: , при ограничениях: , где
· (3) — запасы i-го ресурса;
· (4) — стоимость единицы i-го ресурса;
· (5) — общая стоимость всех ресурсов;
· (6) — запасы i-го ресурса на производство единицы продукции j-го типа;
· (7) — цена единицы i-го ресурса;
- (8) — доход от продажи единицы продукции i-го вида.
Таким образом, задачи симметричной двойственной пары могут быть сформулированы так.
1. Исходная задача. Сколько единиц продукции каждого вида надо выпустить при доходе от продукции единицы j-го типа при имеющихся запасах каждого из ресурсов , чтобы получить максимальный доход?
- Двойственная задача. Какую цену следует назначить единице каждого из ресурсов , чтобы при заданных величинах дохода от производства единицы каждого вида продукции минимизировать стоимость затрат?
Переменные называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.
Свойства двойственных задач
Полная теория двойственных задач очень сложна. Мы докажем часть соответствующих теорем в упрощенном варианте.
Теорема 1. Для пары двойственных задач верно соотношение
.
Доказательство.
Мы дадим доказательство в двух вариантах - для симметричной и для несимметричной пар двойственных задач.
Симметричная пара
Итак, пусть имеется симметричная пара двойственных задач, записанная в матричной форме:
Транспонируя систему ограничений второй задачи
получим, что
.
С другой стороны, из ограничений первой задачи, имеем
.
Поэтому
.
Но комбинация - это число, которое от транспонирования не меняется:
.
А теперь можно написать следующую цепочку неравенств
так что для любыхдопустимых планов и
| имеет место соотношение:
| .
.
2. Несимметричная пара
Доказательство в этом случае почти дословно повторяет предыдущее.
Итак, пусть имеется несимметричная пара двойственных задач в матричной записи
Транспонируя систему ограничений второй задачи
получим, что
.
С другой стороны, из ограничений первой задачи, имеем
.
Поэтому
.
Как и в предыдущем случае верно соотношение , так что для
любых допустимых планов и
| имеем
|
Так как переменные и совершенно не зависят друг от друга, то, как и в предыдущем случае,
.
Теорема доказана.
Следствие 1. Если в одной задаче из пары двойственных задач целевая функция неограничена, то во второй задаче допустимая область пуста.
Доказательство.
Действительно, пусть, например, .
| Но тогда получится,
| что для любого допустимого плана , что бессмысленно. Это означает, что допустимых планов не существует вообще.
Следствие 2.Если для планов и исходной и двойственной задач выполняется соотношение
,
то они являются оптимальными планами соответствующих задач.
Доказательство.
Действительно, пусть - любой план исходной задачи. Тогда получается, что
,
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|