2.1.3 Постановка двойственной задачи

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

Прямая задача ЛП Двойственная задача ЛП

(3) , (6)

, (4) _, (7)

(5) , (8)

Каждой задаче вида (3)–(5) соответствует двойственная ей задача: (6)–(8).

Правила составления задачи, двойственной к исходной задаче.

Переменные двойственной задачи y_i называют объективно обусловленными оценками или теневыми ценами.

1. Привести все неравенства системы ограничений исходной задачи к одному виду: если в исходной задаче требуется найти максимум линейной формы, то все неравенства системы ограничений необходимо привести к виду ““. Поэтому неравенства, в которых данное требование не выполняется, следует умножить на (-1).

2. Выписать матрицу А коэффициентов при переменных исходной задачи и транспонировать её.

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

4. Указать, что необходимо найти при решении задачи: минимум целевой функции, если в исходной задаче ищется максимум.

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

6. Записать условие неотрицательности переменных двойственной задачи.

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

Из первой теоремы двойственности следует, что при оптимальных производственной программе и векторе оценок ресурсов производственные потери равны нулю.

Согласно второй теореме двойственности к оптимальной производственной программе = (x₁,x₂,...,x_n) и оптимальному вектору оценок = (y₁,y₂,...,y_m) предъявляются следующие требования:

если y_i  0, то i = 1,..., m; (9)

если то y_i=0, i = 1,..., m;

если x_j > 0, тo j = 1,..., n; (10)

если то x_j = 0, j = 1,...,n.

Условия (9) можно интерпретировать так: если оценка y_i единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (10) следует, если j-й вид продукции убыточен, то он не войдёт в оптимальный план, не будет выпускаться.

Аналогично продукция, которая производилась в минимально необходимом количестве (условия обращаются в равенства), получает положительную оценку y_i^* > 0, а недефицитная продукция, которая при заданных ресурсах может быть произведена сверх необходимого количества (условия обращаются в неравенства) получает оценку y_i^*= 0.

Согласно соотношениям (9)–(10) для положительных значений неизвестных в оптимальном плане (x_j > 0) соответствующие сопряженные условия в системе ограничений двойственной задачи обращаются в равенства, а для нулевых значений неизвестных (x_j = 0), не вошедших в оптимальный план, сопряженные с ними двойственные условия, обращаются в неравенства.

Из третьей теоремы двойственности следует, что величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего свободного члена ограничений на единицу.

F(x) = b_iy_i, при b_i = 1 F(x) = y_i.