Сделай Сам Свою Работу на 5

Постановка двойственных задач





Симметричные двойственные задачи

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

(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. Двойственная задача. Какую цену следует назначить единице каждого из ресурсов , чтобы при заданных величинах дохода от производства единицы каждого вида продукции минимизировать стоимость затрат?

Переменные называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.

Свойства двойственных задач

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

Теорема 1. Для пары двойственных задач верно соотношение

.

Доказательство.

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

Симметричная пара

Итак, пусть имеется симметричная пара двойственных задач, записанная в матричной форме:

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

получим, что

.

С другой стороны, из ограничений первой задачи, имеем

.

Поэтому

.

Но комбинация - это число, которое от транспонирования не меняется:

.

А теперь можно написать следующую цепочку неравенств

так что для любыхдопустимых планов и имеет место соотношение:

.

.

2. Несимметричная пара

Доказательство в этом случае почти дословно повторяет предыдущее.

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

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



получим, что

.

С другой стороны, из ограничений первой задачи, имеем

.

Поэтому

.

Как и в предыдущем случае верно соотношение , так что для

любых допустимых планов и имеем

Так как переменные и совершенно не зависят друг от друга, то, как и в предыдущем случае,

.

Теорема доказана.

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

Доказательство.

Действительно, пусть, например, . Но тогда получится,

что для любого допустимого плана , что бессмысленно. Это означает, что допустимых планов не существует вообще.

 

Следствие 2.Если для планов и исходной и двойственной задач выполняется соотношение

,

то они являются оптимальными планами соответствующих задач.

Доказательство.

Действительно, пусть - любой план исходной задачи. Тогда получается, что

,

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.