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

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования (табл. 11.1).

Таблица 11.1

Исходная задача	Двойственная задача
1.	1'.
2.	2'.
3.	3'.
4.	4'.
5.	5'.

ПРАВИЛА СОСТАВЛЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

1. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи и, наоборот, каждому j-му ограничению двойственной задачи соответствует переменная исходной задачи.

2. Матрицы А ограничений 1 – 2 и А' ограничений 3' – 4' (см. табл. 11.1) взаимно транспонированы. Следовательно, строка коэффициентов в j-м ограничении двойственной задачи есть столбец коэффициентов при в ограничениях 1 – 2 исходной задачи, и наоборот.

3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи. При этом максимизация меняется на минимизацию, и наоборот.

4. В каждой задаче ограничения-неравенства следует записывать со знаком «≤» при максимизации и со знаком «≥» – при минимизации.

5. Каждому i-му ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности , а равенству – переменная без ограничения на знак. Наоборот, неотрицательной переменной соответствует в двойственной задаче j-е ограничение - неравенство, а произвольной переменной – равенство.

СВЯЗЬ МЕЖДУ РЕШЕНИЯМИ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ

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

Лемма 11.1 (основное неравенство теории двойственности). Если – некоторый план исходной задачи, а – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане всегда не превосходит значение целевой функции двойственной задачи при плане , т.е.

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

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

.

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

Из этой теоремы вытекают необходимые и достаточные условия:

a) разрешимости задач – существование хотя бы одного допустимого плана у каждой задачи;

б) оптимальности допустимых планов X и Y – выполнение равенства F(X) = T(Y).

Теорема 11.2. Вторая теорема двойственности (теорема о дополнительной нежесткости). Для того чтобы два допустимых решения и пары двойственных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений

(*)

(**)

Данная теорема позволяет:

a) установить оптимальность решения одной задачи по свойствам решения двойственной;

б) найти оптимальное решение одной задачи по решению двойственной.

Теорема верна для симметричной двойственной пары. Для задач в канонической и общей формах соотношения (*) и (**) верны только для ограничений в виде неравенств и для неотрицательных переменных.

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

1. В оптимуме

2. На любой итерации процесса решения прямой задачи

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

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

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

(Прибыль) < (Общая ценность ресурсов).

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

Чтобы дать представление о соответствующих обозначениях, часто встречающихся в литературе по линейному программированию, введем следующее определение:

– суммарная оценка ресурсов, используемых при производстве единицы продукции -го вида.

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

Условие оптимальности (в задаче максимизации), используемое в симплекс-методе, состоит в том, что вид производственной деятельности, не представленный в текущем решении (ему соответствует независимая переменная ) должен вводиться в последующее решение с отличным от нуля и положительным уровнем использования () только в том случае, когда -коэффициент при данной переменной отрицателен. Дадим экономическую интерпретацию этому условию. Неиспользованный вид производственной деятельности должен быть представлен в решении только в том случае, если , т.е. когда

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

Дата добавления: 2015-04-29