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

Двойственные задачи

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

(Связь исходной и двойственной задач состоит в том, что коэффициенты сj целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены bi системы ограничений исходной задачи служат коэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двойственной задачи может быть получено из решения исходной и наоборот.)

Так, если прямая задача заключается в нахождении вектора X=(x1, x2, ..., xn)

То, сопряженная задача сводится к нахождению вектора

Y = (y1, y2, ..., ym)

Замечание 1. Двойственные переменные  yi  могут нести условие неотрицательности, могут и не иметь его.

Определение. Парой  двойственных условий (или соответствующих ограничений) называются ограничения вида

Замечание 2. Если какая-то переменная прямой задачи не несет условие неотрицательности, то соответствующее ей ограничение сопряженной задачи выполняется как строгое равенство.

Из вышесказанного ясно, что для того, чтобы правильно записать сопряженную задачу, достаточно ограничения по ресурсам прямой задачи записать в виде равенств (с помощью так называемых ослабляющих переменных). Размерность матрицы A равна m x n. Это определяет размерность сопряженной задачи, так как в ней AТ, то будет n ограничений и m неизвестных.

Примеры записи сопряженных задач

1. Дана прямая задача:

min L(x) = 2x1 + 3x2
  x1 -  2x2 ≥ 5
-3x1 + 5x2 ≤ 7
x1 ≥ 0,  x2 ≥ 0[pic 7]

Вводим ослабляющие переменные и получаем:

min L(x) = 2x1 + 3x2
  x1 -  2x2 - x3         = 5
-3x1 + 5x2        + x4 = 7
xj ≥0,  j = 1, ..., 4[pic 8]

Так как в прямой задаче 2 ограничения и 4 неизвестных, то в сопряженной задаче будет 4 ограничения и 2 неизвестных.

max L(y) = 5y1 + 7y2
  y1 -  3y2 ≤ 2
-2y1 + 5y2 ≤ 3
 -y1 ≤ 0
           y2 ≤ 0[pic 9]

Пары двойственных условий:

x1 ≥ 0        x2 ≥ 0[pic 10][pic 11]

y1 - 3y2 ≤ 2        -2y1 + 5y2 ≤ 3

x1 - 2x2 ≥ 5        -3x1 + 5x2 ≤ 7[pic 12][pic 13]

-y1 ≤ 0        y2 ≤ 0

2. Прямая задача:

max L(x) = x1 - 2x2
 x1 + 3x2 ≥ 5
2x1  -  x2 = 3
x1 ≥ 0, x2 ≥ 0[pic 14]

В первое ограничение введём ослабляющую переменную x3 с коэффициентом -1. Размерность матрицы A будет 2 x 3. В сопряженной задаче будет 2 неизвестных и 3 ограничения.

min L(y) = 5y1 + 3y2
  y1 + 2y2 ≥  1
3y1  -   y2  ≥  -2
 -y1 ≥  0[pic 15]

Пары двойственных условий:[pic 16][pic 17]

x1 ≥ 0        x2 ≥  0

y1 + 2y2 ≥ 1        3y1 - y2 ≥ -2