Методы решения физико-математических задач

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

Пример прямой и симметричной двойственной задачи линейного программирования
Представлены правила составления двойственных задач. Рассмотрены симметричные, несимметричные и смешанные пары. Разобраны примеры составления двойственных задач.
Содержание
См. также:

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

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

Рассмотрим задачу линейного программирования с n неотрицательными переменными x1 ,  x2 , ... , xn и m неравенствами системы ограничений следующего вида:
(1.1)   F(X ) = c1 x1  + c2 x2  +  ...  +  cn xn  → max ;
(1.2)  
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  ≤ b1 
a21 x1  + a22 x2  +  ...   + a2n xn  ≤ b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  ≤ bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 

Здесь ci , ajk , bl есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками ≤ .
Двойственная задача имеет вид:
(2.1)   Z(Y ) = b1 y1  + b2 y2  +  ...  +  bm ym  → min ;
(2.2)  
{ 
a11 y1  + a21 y2  +  ...   + am1 ym  ≥ c1 
a12 y1  + a22 y2  +  ...   + am2 ym  ≥ c2 
... 
a1n y1  + a2n y2  +  ...   + amn ym  ≥ cn 
y1  ≥ 0;  y2  ≥ 0; ... ; ym  ≥ 0
 

Здесь все строки системы (2.2) являются неравенствами со знаками ≥ . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит n строк и m столбцов. Двойственная задача имеет m переменных y1 ,  y2 , ... , ym . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) – двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) – двойственной. Задачи (1) и (2) называются симметричными двойственными задачами.

Таким образом, симметричную двойственную задачу можно составить только в том случае, если все переменные исходной задачи неотрицательные и система ограничений не содержит равенств. Если ищется максимум целевой функции, то неравенства нужно преобразовать к виду ≤ . Если ищется минимум, то неравенства нужно преобразовать к виду ≥ . Чтобы изменить знак, нужно обе части неравенства умножить на –1 .

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

Дана задача линейного программирования:
F(X ) = 4x1  + 5x2  + 6x3  → min ;
{ 
2x1  + 3x2  ≤ 32
4x1  + x2  + 2x3  ≥ 40
x2  + 3x3  ≤ 50
x1  ≥ 0;  x2  ≥ 0;  x3  ≥ 0
 

Составить двойственную задачу.

Решение

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки ≥ . Первое и третье неравенства содержат знак ≤ . Умножим их на –1 :
{ 
– 2x1  – 3x2  ≥ – 32
4x1  + x2  + 2x3  ≥ 40
– x2  – 3x3  ≥ – 50
x1  ≥ 0;  x2  ≥ 0;  x3  ≥ 0
 
Перепишем систему ограничений, явно указывая коэффициенты при переменных:
{ 
– 2 ⋅ x1  – 3 ⋅ x2  + 0 ⋅ x3  ≥ – 32
4 ⋅ x1  + 1 ⋅ x2  + 2 ⋅ x3  ≥ 40
0 ⋅ x1  – 1 ⋅ x2  – 3 ⋅ x3  ≥ – 50
x1  ≥ 0;  x2  ≥ 0;  x3  ≥ 0
 

Матрица коэффициентов системы ограничений имеет вид:
( 
– 2– 30
412
0– 1– 3
 )

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, третью строку запишем как третий столбец.
( 
– 240
– 31– 1
02– 3
 )
Двойственная задача имеет вид:
Z(Y ) = – 32y1  + 40y2  – 50y3  → max ;
{ 
– 2 ⋅ y1  + 4 ⋅ y2  + 0 ⋅ y3  ≤ 4
– 3 ⋅ y1  + 1 ⋅ y2  – 1 ⋅ y3  ≤ 5
0 ⋅ y1  + 2 ⋅ y2  – 3 ⋅ y3  ≤ 6
y1  ≥ 0;  y2  ≥ 0;  y3  ≥ 0
 

Ответ

Z(Y ) = – 32y1  + 40y2  – 50y3  → max ;
{ 
– 2y1  + 4y2  ≤ 4
– 3y1  + y2  – y3  ≤ 5
2y2  – 3y3  ≤ 6
y1  ≥ 0;  y2  ≥ 0;  y3  ≥ 0
 

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

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с n неотрицательными переменными x1 ,  x2 , ... , xn и m равенствами системы ограничений:
(3.1)   F(X ) = c1 x1  + c2 x2  +  ...  +  cn xn  → max ;
(3.2)  
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  = b1 
a21 x1  + a22 x2  +  ...   + a2n xn  = b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  = bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 

Здесь ci , ajk , bl есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.
Двойственная задача имеет вид:
(4.1)   Z(Y ) = b1 y1  + b2 y2  +  ...  + bm ym  → min ;
(4.2)  
{ 
a11 y1  + a21 y2  +  ...   + am1 ym  ≥ c1 
a12 y1  + a22 y2  +  ...   + am2 ym  ≥ c2 
... 
a1n y1  + a2n y2  +  ...   + amn ym  ≥ cn 
 

Здесь все строки системы (4.2) являются неравенствами со знаками ≥ . Матрица коэффициентов системы ограничений (4.2) является транспонированной матрицей системы (3.2). Двойственная задача имеет m переменных y1 ,  y2 , ... , ym . Переменные могут быть как положительными, так и отрицательными.

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1)   F(X ) = c1 x1  + c2 x2  +  ...  +  cn xn  → min ;
(5.2)  
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  = b1 
a21 x1  + a22 x2  +  ...   + a2n xn  = b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  = bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 
Двойственная задача имеет вид:
(6.1)   Z(Y ) = b1 y1  + b2 y2  +  ...  + bm ym  → max ;
(6.2)  
{ 
a11 y1  + a21 y2  +  ...   + am1 ym  ≤ c1 
a12 y1  + a22 y2  +  ...   + am2 ym  ≤ c2 
... 
a1n y1  + a2n y2  +  ...   + amn ym  ≤ cn 
 

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки ≤ .

Связь с симметричной парой двойственных задач

Покажем, что несимметричную пару задач (3.1) – (4.2) можно получить из симметричной пары (1.1) – (2.2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)   F(X ) = c1 x1  + c2 x2  +  ...  +  cn xn  → max
и системой ограничений
(3.2)  
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  = b1 
a21 x1  + a22 x2  +  ...   + a2n xn  = b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  = bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 

Каждое равенство можно представить двумя неравенствами:
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  ≤ b1 
a11 x1  + a12 x2  +  ...   + a1n xn  ≥ b1 
a21 x1  + a22 x2  +  ...   + a2n xn  ≤ b2 
a21 x1  + a22 x2  +  ...   + a2n xn  ≥ b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  ≤ bm 
am1 x1  + am2 x2  +  ...   + amn xn  ≥ bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 

Неравенства со знаками ≥ умножим на –1 :
(7)  
{ 
a11 x1  + a12 x2  +  ...   + a1n xn  ≤ b1 
– a11 x1  – a12 x2  –  ...   – a1n xn  ≤ – b1 
a21 x1  + a22 x2  +  ...   + a2n xn  ≤ b2 
– a21 x1  – a22 x2  –  ...   – a2n xn  ≤ – b2 
... 
am1 x1  + am2 x2  +  ...   + amn xn  ≤ bm 
– am1 x1  – am2 x2  –  ...   – amn xn  ≤ – bm 
x1  ≥ 0;  x2  ≥ 0; ... ; xn  ≥ 0
 
Получаем симметричную задачу с целевой функцией
F(X ) = c1 x1  + c2 x2  +  ...  +  cn xn  → max
и системой ограничений (7), которая имеет 2m неравенств.
По формулам (1.1) – (2.2) получаем для нее двойственную задачу:
Z(Y ) = b1 y11  – b1 y12  + b2 y21  – b2 y22   +  ...  +  bm ym1  – bm ym2  → min ;
{ 
a11 y11  – a11 y12  + a21 y21  – a21 y22  +  ...   + am1 ym1  – am1 ym2  ≥ c1 
a12 y11  – a12 y12  + a22 y21  – a22 y22  +  ...   + am2 ym1  – am2 ym2  ≥ c2 
... 
a1n y11  – a1n y12  + a2n y21  – a2n y22  +  ...   + amn ym1  – amn ym2  ≥ cn 
y11  ≥ 0;  y12  ≥ 0; ... ; ym1  ≥ 0;  ym2  ≥ 0
 
Двойственная задача имеет 2m неотрицательных переменных:
y11 ,  y12 ,  y21 ,  y22 , ... ,  ym1 ,  ym2 .
Нетрудно видеть, что эти переменные входят в задачу в виде разностей
yi1  – yi2 .

Сделаем подстановки
y1  = y11  – y12 ,  y2  = y21  – y22 , ...,  ym  = ym1  – ym2 .
Поскольку yi1  ≥ 0 и yi2  ≥ 0 , то переменные yi могут быть как положительными, так и отрицательными.

Тем самым мы получили двойственную задачу, которая имеет вид (4.1) – (4.2):
(4.1)   Z(Y ) = b1 y1  + b2 y2  +  ...  + bm ym  → min ;
(4.2)  
{ 
a11 y1  + a21 y2  +  ...   + am1 ym  ≥ c1 
a12 y1  + a22 y2  +  ...   + am2 ym  ≥ c2 
... 
a1n y1  + a2n y2  +  ...   + amn ym  ≥ cn 
 

Если мы за исходную задачу возьмем (4.1) – (4.2), то, выполняя все действия в обратном порядке, получим двойственную задачу (3.1) – (3.2).

Тем же способом можно из задачи (5.1) – (5.2) получить двойственную задачу (6.1) – (6.2), а из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

Пусть мы имеем прямую задачу вида (1.1) на максимум, но в системе ограничений которой i-я строка является равенством. Тогда двойственная задача имеет вид (2.1) – (2.2) за одним исключением – переменная yi может быть как положительной, так и отрицательной. То есть отсутствует ограничение yi  ≥ 0 .

То же самое произойдет, если мы имеем прямую задачу (2.1) на минимум, в системе ограничений которой i-я строка является равенством. Двойственная задача имеет вид (1.1) – (1.2) за одним исключением – переменная xi может быть любого знака.

Теперь пусть мы имеем прямую задачу (1.1) на максимум, но отсутствует ограничение xi  ≥ 0 . То есть переменная xi может быть как положительной, так и отрицательной. Тогда двойственная задача имеет вид (2.1) – (2.2) за одним исключением – i-я строка системы ограничений является равенством.

И наконец, пусть мы имеем прямую задачу (2.1) на минимум, но отсутствует ограничение yi  ≥ 0 . Тогда двойственная задача имеет вид (1.1) – (1.2) за одним исключением – i-я строка системы ограничений является равенством.

Все это позволяет нам сформулировать правила составления двойственных задач.

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

1.   Для исходной задачи на максимум, все неравенства системы ограничений приводим к виду:
ai1 x1  + ai2 x2  +  ...   + ain xn  ≤ bi .
Для исходной задачи на минимум, все неравенства приводим к виду:
ai1 x1  + ai2 x2  +  ...   + ain xn  ≥ bi .
Если требуется поменять знак, то умножаем обе части неравенств на –1 .
2.   Составляем двойственную задачу тем же способом, как для симметричной пары задач.
3.   Если в исходной задаче, i–я строка системы ограничений является равенством, то вычеркиваем условие неотрицательности i–й переменной yi  ≥ 0 двойственной задачи.
4.   Если в исходной задаче, отсутствует условие неотрицательности для k–й переменной, xk  ≥ 0 , то в k–й строке двойственной задачи меняем знак неравенства на знак равенства.

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

Дана задача линейного программирования:
F(X ) = 5 + 3x1  + 2x2  – x3  → min ;
{ 
x1  + 2x2  – 3x3  = 4
4x1  – x2  = 7
2x1  – 3x2  + x3  ≤ 5
x1  ≥ 0;  x2  ≥ 0
 

Составить двойственную задачу.

Решение

Целевая функция имеет свободный член 5. Чтобы привести ее к виду (2.1), введем переменную x4 и добавим равенство x4  = 1 . Тогда задача примет вид:

F(X ) = 3x1  + 2x2  – x3  + 5x4  → min ;
{ 
x1  + 2x2  – 3x3  = 4
4x1  – x2  = 7
2x1  – 3x2  + x3  ≤ 5
x4  = 1
x1  ≥ 0;  x2  ≥ 0
 

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки ≥ . Третье неравенства содержат знак ≤ . Поэтому умножим его на –1 :
– 2x1  + 3x2  – x3  ≥ – 5

Перепишем систему ограничений, явно указывая коэффициенты при переменных:
{ 
1 ⋅ x1  + 2 ⋅ x2  – 3 ⋅ x3  + 0 ⋅ x4  = 4
4 ⋅ x1  – 1 ⋅ x2  + 0 ⋅ x3  + 0 ⋅ x4  = 7
– 2 ⋅ x1  + 3 ⋅ x2  – 1 ⋅ x3  + 0 ⋅ x4  ≥ – 5
0 ⋅ x1  + 0 ⋅ x2  + 0 ⋅ x3  + 1 ⋅ x4  = 1
x1  ≥ 0;  x2  ≥ 0
 

Матрица коэффициентов системы ограничений имеет вид:
( 
12– 30
4– 100
– 23– 10
0001
 )

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, и так далее.
( 
14– 20
2– 130
– 30– 10
0001
 )
Составим двойственную задачу как для симметричной пары.
Z(Y ) = 4y1  + 7y2  – 5y3  + y4  → max ;
{ 
y1  + 4y2  – 2y3  ≤ 3
2y1  – y2  + 3y3  ≤ 2
– 3y1  – y3  ≤ – 1
y4  ≤ 5
y1  ≥ 0;  y2  ≥ 0;  y3  ≥ 0;  y4  ≥ 0
 

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные y1 , y2 и y4 могут иметь любой знак. Неотрицательной переменной является только y3 . Поэтому условия неотрицательности переменных имеют вид:
y3  ≥ 0 .

Поскольку в исходной задаче переменные x3 и x4 могут иметь произвольные знаки, то 3-я и 4-я строки системы ограничений двойственной задачи являются равенствами.

Таким образом, двойственная задача имеет вид:
Z(Y ) = 4y1  + 7y2  – 5y3  + y4  → max ;
{ 
y1  + 4y2  – 2y3  ≤ 3
2y1  – y2  + 3y3  ≤ 2
– 3y1  – y3  = – 1
y4  = 5
y3  ≥ 0
 

Из четвертого уравнения y4  = 5 . Заменим переменную y4 ее значением и умножим третью строку на –1 .

Ответ

Z(Y ) = 5 + 4y1  + 7y2  – 5y3  → max ;
{ 
y1  + 4y2  – 2y3  ≤ 3
2y1  – y2  + 3y3  ≤ 2
3y1  + y3  = 1
y3  ≥ 0
 

Автор: Олег Одинцов.     Опубликовано:

См. также:
▲
Меню