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

Общая задача линейного программирования формулируется следующим образом максимизировать (минимизировать) целевую функцию 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-е ограничение уравнение =. Аналогичное состояние имеется между ограничениями исходной задачи и переменными двойственной задачи.

Дата добавления: 2015-09-07