8. Двойственность в линейном программировании

Рассмотрим пару задач ЛП вида:

Задачу I называют прямой задачей ЛП, а задачу II  двойственной. Однако задача, двойственная к задаче II, есть исходная прямая задача I, поэтому можно считать любую из такой пары задач прямой, а другую  двойственной. Неравенства задач I и II, соответствующие друг другу, называются сопряженными (отмечены стрелками). Множества допустимых решений задач I и II будем обозначать соответственно.

Пример 10. Составить задачу ЛП, двойственную к следующей:

(49)

Поскольку задача (49)  задача на максимум, то двойственная к ней задача будет на минимум. Однако, прежде чем ее строить, необходимо согласовать знаки неравенств в ограничениях задачи (49) с целевой функцией, умножив второе неравенство на 1. Затем каждому неравенству прямой задачи ставим в соответствие неотрицательную переменную двойственной задачи, а равенству  переменную любого знака. И наоборот, каждой неотрицательной переменной прямой задачи будет соответствовать неравенство двойственной задачи, а переменной любого знака  равенство. Получим пару двойственных задач ЛП:

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

Теорема 9 (первая теорема двойственности). Если одна из пары двойственных задач I, II разрешима, то разрешима и другая задача, причем , где оптимальные планы задач I, II соответственно. Если одна из пары задач I, II не имеет решения из-за неограниченности целевой функции, то у другой задачи множество допустимых решений пусто.

Говорят, что планы удовлетворяютусловиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач I, II хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

Теорема 10 (вторая теорема двойственности). Планы ,оптимальны в задачахI, II тогда и только тогда, когда они удовлетворяют условиям дополняющей нежесткости.

Пример 11. Решить задачу, двойственную к задаче о распределении ресурсов (см. пример 1), используя теоремы двойственности.

Решение задачи I известно (см. пример 8):  оптимальный план, . По первой теореме двойственности задачаII также разрешима, причем . Найдем оптимальный планзадачиII, используя вторую теорему двойственности. Подставим координаты векторов ,в ограничения задачI, II. Имеем:

(50)

Следовательно, в силу УДН неравенство должно выполняться как равенство, т. е.. Далее, так каки, то в силу УДНи.

Получаем систему линейных уравнений и решаем ее:

(51)

Планы ,удовлетворяют УДН и, следовательно, в силу второй теоремы двойственности являются оптимальными в задачахI и II соответственно.

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

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

Рассмотрим задачу о распределении ресурсов и двойственную к ней задачу ЛП (пример 11). Каждому линейному ограничению задачи I (т. е. каждому ресурсу) ставится в соответствие неотрицательная переменная . Эти переменные удовлетворяют трем линейным неравенствам задачиII, каждое из которых связывает затраты всех ресурсов на производство единицы продукции с величиной получаемого при этом дохода. Так как правые части указанных ограничений измеряются в единицах стоимости, то и левые части должны измеряться в тех же единицах. Следовательно, переменные , можно рассматривать как некоторыеусловные цены ресурсов. Эти цены можно понимать следующим образом. Предположим, что предприятие решило не производить продукцию, а продать свое сырье, желая при этом получить выручку, не меньшую максимальной прибыли от реализации продукции. Цены, по которым в этом случае нужно продавать каждый вид ресурсов, и определяются переменными .

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

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

В силу второй теоремы двойственности оптимальный план и оптимальный вектор условных цендолжны удовлетворять УДН. Это означает:

1) если при производстве продукции в соответствии с оптимальным планом какой-то ресурс не расходуется полностью (в нашем примере − ресурс), то его оптимальная условная цена равна нулю (). И наоборот, ресурсы, имеющие ненулевую оптимальную условную цену, используются полностью;

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

З а м е ч а н и е. Может показаться странным, что оптимальные условные цены некоторых ресурсов равны нулю. Однако ничего удивительного в этом нет, если учесть, что можно рассматривать еще и как цены, по которым производителю продукции выгодно приобретать ресурсы в дополнение к тем, которыми он уже располагает, имея в виду максимальное увеличение дохода. В приведенном примере ресурси так в избытке, следовательно, увеличение запасов одного только ресурсане позволит произвести дополнительную продукцию и получить доход больший, чем, поэтому приобретать ресурсдополнительно не выгодно и.

10. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 1. Решить задачу линейного программирования графически. Составить эквивалентную ей каноническую задачу. Указать планы КЗЛП, соответствующие вершинам допустимого множества исходной задачи.

1.1.

1.2.

1.3.

1.4.

1.5.

1.6.

1.7.

1.8.

1.9.

1.10.

1.11.

1.12.

1.13.

1.14.

1.15.

1.16.

1.17.

1.18.

1.19.

1.20.

1.21.

1.22.

1.23.

1.24.

1.25.

Задача 2. Решить задачу ЛП симплекс−методом.

2.1.

2.2.

2.3.

2.4.

2.5.

2.6.

2.7.

2.8.

2.9.

2.10.

2.11.

2.12.

2.13.

2.14.

2.15.

2.16.

2.17.

2.18.

2.19.

2.20.

2.21.

2.22.

2.23.

2.24.

2.25.

Задача 3. Решить задачу ЛП, найдя начальный опорный план методом искусственного базиса.

3.1.

3.2.

3.3.

3.4.

3.5.

3.6.

3.7.

3.8.

3.9.

3.10.

3.11.

3.12.

3.13.

3.14.

3.15.

3.16.

3.17.

3.18.

3.19.

3.20.

3.21.

3.22.

3.23.

3.24.

3.25.

Задача 4. Записать задачу ЛП, двойственную данной, решить одну из пары двойственных задач и найти оптимальное решение второйс помощью теорем двойственности.

4.1.

4.2.

4.3.

4.4.

4.5.

4.6.

4.7.

4.8.

4.9.

4.10.

4.11.

4.12.

4.13.

4.14.

4.15.

4.16.

4.17.

4.18.

4.19.

4.20.

4.21.

4.22.

4.23.

4.24.

4.25.