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

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

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

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

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

 

Исходная задача	Двойственная задача
	f = CX →max AX<= B X>= 0	z = YB →min YA>= C Y>= 0	Симметричные задачи
	f = CX →min AX>= B X>= 0	z = YB →max YA<= C Y>= 0
	f = CX →max AX= B X>= 0	z = YB →min YA>= C	Несимметричные задачи
	f = CX →min AX= B X>= 0	z = YB →max YA<= C

Таблица 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₃ двойственной задачи не ограниченна по знаку.