Переход от прямой задачи к двойственной

Общая задача линейного программирования формулируется следующим образом максимизировать (минимизировать) целевую функцию Y вида:

Y= c_jx_j → max

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

a_ijx_j(< =, =, > =)b_i i=[1, m]; j=[1, n]; x_j> =0

Прямая задача линейного программирования:

Y=с₁*x₁+…+с_n*x_n → max

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

a₁₁*x₁+…a_1n*x_n< =b₁

a₂₁*x₁+…a_2n*x_n< =b₂

....

a_k1*x₁+…a_kn*x_n< =b_k

x_i> =0, i=[1, n]

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

S=b₁*y₁+…+b_m*y_m → min

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

a₁₁*y₁+…a_m1*y_m> =c₁

a₁₂*y₁+…a_m2*y_m> =c₂

....

a_1n*x₁+…a_mn*y_m> =c_n

y_i> =0, j=[1, m]

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

1. Целевая функция исходной задачи оптимизируется противоположно двойственной.

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

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

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

5. Если переменная x_j прямой задачи может принимать только положительное значение, то j-е условие в системе ограничений двойственной задачи является неравенством вида > =. Если переменная x_j может принимать любое значение, то j-е ограничение уравнение =. Аналогичное состояние имеется между ограничениями исходной задачи и переменными двойственной задачи.