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

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

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

f(x) = ® max, (1)

£ b_i; (i = ), (2)

= b_i; (i = ). (3)

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

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

F(Y) = ® min, (5)

³ C_j; (j = ), (6)

= C_j; (j = ), (7)

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

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

1. Если функция исходной задачи 1 – 4 задается на максимум, то целевая функция двойственной к ней задачи 5 – 8 задается на минимум.

2. Матрица

А = ,

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

А = .

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

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