Аналогично стоимость всех затраченных ресурсов, идущих на изготовление единицы j-ой продукции, не может быть меньше стоимости окончательного продукта, т.Е.

, j=1,2,..,n.

Итак, двойственная задача формулируется следующим образом:

найти такой набор цен ресурсов Y=(y₁,y₂,…,y_m), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции, т.е. найти вектор Y=(y₁,y₂,…,y_m), доставляющий минимальное значение линейной функции

Z=b₁y₁+b₂y₂+…+b_my_m →min (4)

и удовлетворяющий ограничениям

(5)

y_i 0, (i=1,2,  ,m). (6)

Переменные y_i называются оценками или учетными, неявными ценами.

6.2. Взаимно двойственные задачи линейного программирования и их свойства

Разновидности двойственных задач – симметричные и несимметричные.

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

Исходная задача	Двойственная задача
Lmax=CX; AXB; X0.	Zmin=BY; AYC; Y0.
Lmin=CX; AXB; X0.	Zmax=BY; AYC; Y0.

В несимметричных двойственных задачах система ограничений исходной задачи задается равенствами, а двойственной - в виде неравенств, причем в последней переменные могут быть отрицательными.

Исходная задача	Двойственная задача
Lmax=CX; AX=B; X0.	Zmin=BY; AYC.
Lmin=CX; AX=B; X0.	Zmax=BY; AYC.

Исходная и двойственная задачи обладают следующими свойствами:

1. В одной ищут максимум, в другой – минимум.

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

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

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

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

5. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "", а в задаче минимизации - вида "".

6. Условия неотрицательности переменных имеются в обеих задачах.

Двойственная задача по отношению к двойственной совпадает с исходной. Такое свойство двойственной пары называется взаимностью.

Предложим следующий алгоритм составления двойственной задачи.

1. В случае симметричных задач все неравенства системы ограничений исходной задачи привести к одному смыслу: если в исходной задаче ищут max линейной функции, то все неравенства системы ограничений привести к виду "", а в задаче минимизации – к виду "".

2. Каждому ограничению исходной задачи соответствует одна переменная y_i, (i=1,2,..,m) в двойственной задаче. При этом переменная, отвечающая ограничению-неравенству, должна удовлетворять условию неотрицательности, а переменная, отвечающая ограничению-равенству, может быть любого знака.

3. Целевая функция двойственной задачи формируется из правых частей системы ограничений исходной задачи: Z(Y)=c₀+b₁y₁+b₂y₂+…+b_my_m, где c₀ – свободный член целевой функции исходной задачи L(X).

4. Целевая функция Z(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с L(X) образом, т.е. если L(X)max, то Z(Y)min и наоборот.

5. Каждой переменной x_j (j=1,2,…,n) исходной задачи соответствует ограничение в двойственной задаче.

6. Правые части системы ограничений двойственной задачи состоят из коэффициентов линейной функции исходной задачи.

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