Двойственные задачи

Каждой линейной задаче соответствует другая задача, называемая двойственной.

Рассмотрим задачу об использовании ресурсов, где

S_i- вид ресурсов, используемых для производства продукции;

a_ij - норма расхода ресурса на производство единицы продукции (j=1,2…2);

b_i- запас ресурса;

C_j - прибыль от реализации единицы продукции .

Предположим, что у предприятия возможна альтернатива – производить продукцию или продать сырье. При этом нужно определить цены (y_m) на все m- виды ресурсов. Покупатель заинтересован в наименьших затратах на сырье, а предприятие – продавец заинтересовано в том, чтобы выручка от реализации сырья была бы не меньше выручки, полученной от реализации готовой продукции. Тогда затраты продавца на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее ее цены (C_j)

 

Задача исходная	Задача двойственная
При условии, что xj≥0, F=c1x1+c2x2+…+cnxn → max Найти оптимальный план производства, чтобы прибыль предприятия была max.	При условии, что yi≥0, Z=b1y1+b2y2+…+bnyn → min Найти набор цен на ресурсы, чтобы общие затраты на ресурсы были min

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

Взаимно двойственные задачи обладают следующими свойствами:

1. Если в одной задаче находят max, то в другой min

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

3. Каждая из задач задается в стандартной форме, где в задаче на max все неравенства должны быть вида «≤», в задаче на min все неравенства вида «≥».

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

Для исходной задачи:

 

Для двойственной задачи:

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Значения в обоих задачах должны быть ≥0.