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

Для каждой задачи линейного программирования можно составить двойственную задачу линейного программирования.

Допустим, прямая задача состоит в нахождении максимального значения функции:

f(x) = ® max, (4.17)

£ b_i; (i = ), (4.18)

= b_i; (i = ), (4.19)

Х_j ³ 0; (j = ; S £ n). (4.20)

 

Тогда двойственная задача по отношению к задаче 4.17 – 4.20 состоит в нахождении минимального значения функции:

F(Y) = ® min, (4.21)

³ C_j; (j = ), (4.22)

= C_j; (j = ), (4.23)

y_i ³ 0; (i = ; k £ m). (4.24)

 

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

1. Если функция исходной задачи 4.17 – 4.20 задается на максимум, то целевая функция двойственной к ней задачи 4.21 – 4.24 задается на минимум.

2. Матрица

А = ,

составленная из коэффициентов при неизвестных в системе ограничений 4.18 и 4.19, и матрица, составленная из коэффициентов при неизвестных в системе ограничений 4.22 и 4.23, являются транспонированными по отношению друг к другу (то есть столбцы в этих матрицах меняются местами со строками):

А = .

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

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