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

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

при ограничениях

На основе тех же исходных данных может быть поставлена еще одна задача:

при ограничениях

Сопоставим обе задачи. Первая из них – задача на максимум, вторая – задача на минимум; в соответствии с этим изменился и характер ограничений (знак неравенств). В первой задаче n неизвестных и k ограничений, во второй – k неизвестных и n ограничений. Коэффициенты в целевых функциях и величины в правых частях неравенств при переходе от одной задачи к другой меняются местами. Кроме того, при этом переходе транспонируется матрица ограничений A.

Обе задачи образуют двойственную пару задач. Первую из них называют прямой задачей, а вторую – двойственной.

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

1) каждому ограничению исходной задачи соответствует двойственная переменная;

2) матрицы ограничений взаимно транспонированы;

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

4) каждому ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности соответствующей двойственной переменной, а равенству – произвольная двойственная переменная.

В ЛП доказывается следующая основная теорема двойственности.

Теорема 1.8. Если одна из двойственных задач линейного программирования имеет решение, то имеет решение и другая. При этом значения целевых функций совпадают, т. е. .

Дата добавления: 2015-11-14