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

Рассмотрим прямую задачу планирования производства (об использовании ресурсов): найти вектор при ограничениях

	(1)
	(2)

который обеспечивает максимум целевой функции

(3)

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

Цель продавца здесь: выручка за сырьё, идущее на производство единицы продукции каждого вида, должна быть не меньше цены единицы этой продукции (иначе выгоднее самому организовать производство).

Рассмотрим себестоимость единицы продукции первого вида в этих учетных ценах. Стоимость ресурса первого вида в этой продукции равна , стоимость ресурса второго вида равна , и т.д., стоимость m-го ресурса в первом изделии составляет . Просуммируем эти величины, получим себестоимость первого изделия, которая должна быть не меньше цены реализации этого изделия С₁.. Аналогичные неравенства составим и для всех остальных видов продукции, получаем ограничения двойственной задачи:

(4)

Ограничения на переменные традиционны (поскольку цены на ресурсы не могут быть отрицательными):

(5)

Целью покупателя является минимизация затрат на приобретение ресурсов:

(6)

Итак, задача (4)-(6) – двойственная к задаче (1)-(3). Получили пару симметричных двойственных задач.

Общие правила составления двойственной задачи такие:

1. Матрица системы ограничений транспонируется.

2. Ограничения вида «меньше или равно» заменяются на ограничения «больше или равно».

3. Свободные члены исходной задачи становятся коэффициентами целевой функции задачи двойственной.

4. Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной.

5. Исходная задача на максимум преобразуется в двойственную к ней на минимум.

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

Двойственная задача будет записана в такой форме:

Исследование пары двойственных задач

Поскольку двойственная задача также является ЗЛП, то её можно решить симплекс-методом. Однако двойственная задача и экономически, и математически тесно связана с прямой задачей, поэтому есть более простые способы её решения, если известно решение прямой задачи. Поэтому рассмотрим некоторые результаты, связывающие обе эти задачи.

Теорема. Пусть есть допустимое решение задачи (1)-(3), есть допустимое решение задачи (4)-(6). Тогда выполняется неравенство:

(7)

Теорема (достаточный признак оптимальности пары двойственных ЗЛП, или критерий оптимальности Канторовича). Если - такие допустимые решения (1)-(3) и (4)-(6) соответственно, что , то являются оптимальными решениями своих задач.

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

(8)

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

Вторая теорема двойственности (теорема о дополняющей нежесткости). Оптимальные решения пары двойственных задач связаны между собой следующими равенствами:

	(9)
	(10)

Формулы (9) и (10) можно применять следующим образом:

• если при оптимальном решении одной из пары двойственных задач какое-либо неравенство выполняется как строгое, то соответствующая ему двойственная переменная в оптимальном решении другой задачи равна нулю;

• если какая-нибудь переменная в оптимальном решении одной из задач не равна нулю, то соответствующее ей ограничение другой задачи выполняется как равенство.