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

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

Двойственная задача – это вспомогательная задача линейного программирования, получаемая с помощью определённых правил непосредственно из условий исходной.

Сформулируем правила построения двойственных задач:

1. Если целевая функция f исходной задачи максимизируется, то целевая функция z двойственной – минимизируется и наоборот.

2. Количество ограничений (m) исходной задачи равно количеству переменных двойственной, а количество переменных (n) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через y_i (i = 1, m).

3. Поскольку переменные исходной задачи связаны с ограничениями двойственной, каждой переменной x_j > =0 соответствует в двойственной задаче ограничение вида «< =» (z→ max) или «> =» (z→ min), и наоборот.

4. Каждой переменной x_j, не ограниченной по знаку, соответствует ограничение вида «=» двойственной задачи, и наоборот.

5. Свободные члены ограничений исходной задачи b_i (I = 1, m) в двойственной являются коэффициентами при переменных y_i (I = 1, m) в целевой функции, а коэффициенты c_j (j = 1, n) при переменных x_j (j = 1, n) в целевой функции исходной задачи являются свободными членами ограничений двойственной.

6. Матрица A коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется (A^т ).

Рассмотрим в общем виде одну из частных задач линейного программирования, которую будем считать исходной:

f = c₁x₁ + c₂x₂ +…+ c_nx_n → max;

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n < = b₁,

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n < = b₂,

……………………………..

a_m1x₁ + a_m2x₂ +…+ a_mnx_n < = b_m,

x_j > = 0 (j= 1, n).

Двойственная к этой задаче будет иметь вид:

z = b₁y₁ + b₂y₂ +…+ b_my_m→ min;

a₁₁y₁ + a₂₁y₂ +…+ a_m1y_m > = c_1,

a₁₂y₁ + a₂₂y₂ +…+ a_m2y_m > =c₂,

……………………………..

a_1ny₁ + a_2ny₂ +…+ a_mny_m > = c_n,

y_i > = 0 (i = 1, m).

Если применить правила построения двойственных задач, то получим исходную задачу.

В таблице 5 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через Y = (y₁, y₂, …, y_m) обозначена матрица-строка неизвестных двойственной задачи. Матрица-строка Y умножается слева на матрицу-столбец B (в целевой функции) и матрицу A (в ограничениях) исходя из правил умножения двух матриц, а также правил построения двойственных задач (в частности, в двойственной задаче матрица коэффициентов при неизвестных в ограничениях должна быть транспонированной).

Таблица 5. Правила формирования двойственных задач

Первые две пары взаимно двойственных задач в таблице называются симметричными, вторые две – несимметричными из-за наличия ограничений вида «=».

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

Пример 1. Построить задачу, двойственную к данной:

f = x₁ –x₂ → max;

x₁ – x₂ < = 1,

x₁ – x₂ > = 0,

x₁ > = 0, x₂ > = 0.

Чтобы построить двойственную задачу, исходную необходимо привести к форме (1) путем умножения обеих частей второго ограничения на (-1). После этого преобразования исходная задача примет вид:

f = x₁ –x₂ → max;

x₁ – x₂ < = 1,

- x₁ + x₂ > = 0,

x₁ > = 0, x₂ > = 0.

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

z = y₁ → min;

y₁ – y₂ > = 1,

- y₁ + y₂ > = -1,

y₁ > = 0, y₂ > = 0.

Пример 2. Построить задачу, двойственную к данной:

f = 7x₁ + 6x₂ + 3x₃ – x₄ → min;

2x₁ – x₂ + 2x₃ – 3x₄ > = 12,

-x₁ + 2x₂ – x₃ + x₄ < = 10,

3x₁ + 5x₂ + 4x₄ = 7,

x₂ > = 0, x₃ > = 0.

Для построения двойственной задачи воспользуемся формулами (2), (4) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (-1). Тогда исходная задача будет иметь вид:

f = 7x₁ + 6x₂ + 3x₃ – x₄ → min;

2x₁ – x₂ + 2x₃ – 3x₄ > = 12,

x₁ - 2x₂ + x₃ - x₄ < = -10,

3x₁ + 5x₂ + 4x₄ = 7,

x₂ > = 0, x₃ > = 0.

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

z = 12y₁ – 10y₂ + 7y₃ → max;

2y₁ + y₂ + 3y₃ = 7,

-y₁ – 2y₂ + 5y₃ < = 6,

2y₁ + y₂ < = 3,

-3y₁ – y₂ + 4y₃ = -1,

y₁ > = 0, y₂ > = 0.

Используя пример 2, поясним некоторые правила построения двойственных задач. Поскольку количество ограничений исходной задачи m = 3, двойственная задача должна иметь три переменные: y₁, y₂, y₃. Количество переменных исходной задачи n = 4, поэтому двойственная должна иметь четыре ограничения. Переменные x₁ и x₄ исходной задачи не ограничены по знаку. В силу этого первое и четвертое ограничения двойственной задачи имеют вид равенств. Третье ограничение исходной задачи имеет вид равенства, следовательно, переменная y₃ двойственной задачи не ограниченна по знаку.