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

1.5.1. Построение двойственной задачи

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

Рассмотрим задачу об использовании ресурсов: b_i - запас ресурса S_i; a_ij - число единиц i ресурса, потребляемое при производстве j продукции; c_j -прибыль от одной единицы j продукции. Предположим, что некая организация решила закупить ресурсы S_j (i = 1,m) и необходимо установить оптимальные цены y_i на эти ресурсы (цены ресурсов в экономической литературе называются учетными, неявными, теневыми). Покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b_i по ценам y_i _,, были наименьшими.

С другой стороны, предприятия продающее ресурсы, заинтересовано в том, чтобы полученная выручка была бы не менее той суммы, которую оно может получить при переработке ресурсов в готовую продукцию. На изготовление одной единицы продукции первого вида расходуется а₁₁ единиц S₁ ресурса по цене у₁ и а₂₁ единиц ресурса S₂ по цене у₂ и т.д. Поэтому для удовлетворения требований продавца затраты на ресурсы при изготовлении одной единицы продукции должны быть не менее цены. В результате получим двойственную задачу:

(9)

, j = 1,n (10)

любой у_i ≥ 0 (11)

Принцип построения двойственной задачи.

1) Если исходная задача имеет размер m×n,то двойственная задача имеет размер n×m, т.е. число переменных двойственной задачи ровно числу условий ограничений исходной задачи и наоборот (не считая условий не отрицательности переменных).

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

3) В правых частях ограничений каждой задачи стоят коэффициенты при неизвестных в целевой функции другой задачи.

4) Если исходная задача на max и ее неравенства вида «≤», двойственная задача на min и ее неравенства «≥».

5) Каждому i ограничению:

- неравенству исходной задачи соответствует в двойственной задаче условие не отрицательности (у_i ≥ 0);

- равенству соответствует переменная без ограничений и наоборот.

Пример 23. F = 3x₁+ x₂- 2x₄à min

2х₁+ х₂- x₃+ х₄≥ 7