Экономическая интерпретация двойственной задачи. Постановка задачи двойственной к задаче ЛП с ограничениями типа равенств и неравенств.

Для проведения содержательной интерпретации двойственной задачи (II) свяжем переменные двойственной задачи

Пусть L* - максимальное значение дохода в задаче (I). Если запасы ресурсов , i=1,...,m изменить, то может измениться и максимальный доход L*. Это означает, что L* является функцией от ресурсов , i=1,...,m, т.е.

Рассмотрим отношение приращения дохода к приращению i-го ресурса ;

Тогда по определению частной производной функции

Но по первой теореме двойственности оптимальное значение целевой функции прямой задачи совпадает с оптимальным значением целевой функции двойственной задачи

Таким образом, оптимальное значение двойственной переменной

числено равно дополнительному доходу при увеличении i-го ресурса на единицу, если величина является достаточно малой по сравнению с величиной Полученный вывод имеет очень важное практическое применение. Пусть L*- максимальное значение дохода в задаче (I),

Тогда, изменяя i-й ресурс на единицу, получим новое значение максимального дохода по формуле

или более общий вид

Двойственные переменные

называются оценками (теневыми ценами, ценностями) соответствующих ресурсов i=1,..., m, и характеризуют меру эффективности использования соответствующих ресурсов.

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

(1)

или, в матричной записи,

(2)

Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида

(3)

или, в матричной записи,

(4)

где .

Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

6. Основное неравенство двойственности.

Для любых допустимых планов прямой и двойственной задачи ЛП справедливо неравенство:

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

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