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

Решение двойственной задачи

Первая и вторая теоремы двойственности
Приводятся формулировки первой и второй теорем двойственности. Показано, как получить решение двойственной задачи из решения прямой, применяя эти теоремы. Подробно разобраны примеры решений задач.
Содержание
См. также:

Здесь мы рассмотрим вопрос, как из решения прямой задачи, получить решение двойственной задачи.

Теоремы двойственности

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

Если одна из пары двойственных задач имеет оптимальное решение,
то и двойственная задача имеет оптимальное решение. При этом значения целевых функций прямой и двойственной задачи, для оптимальных решений, равны друг другу.

Если одна из пары двойственных задач не имеет решения вследствие неограниченности целевой функции,
то двойственная задача не имеет решения вследствие несовместимости системы ограничений.

Вторая теорема двойственности

Пусть мы имеем симметричную пару двойственных задач (1) и (2):
(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
 
(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
 
Для того чтобы допустимые решения (x1 ,  x2 , ...,  xn ) и (y1 , y2 , ...,  ym ) являлись оптимальными решениями двойственных задач (1) и (2),
необходимо и достаточно, чтобы выполнялись следующие равенства:
(3)   yi ( nΣj = 1 aij xj  – bi ) = 0 ,   i = 1,  2, ...,  m ;
(4)   xj ( mΣi = 1 aij yi  – cj ) = 0 ,   j = 1,  2, ...,  n .

Для наглядности, выпишем равенства (3) и (4) в развернутом виде:
(3.1)   y1 (a11 x1  + a12 x2  +  ...  + a1n xn  – b1 ) = 0
(3.2)   y2 (a21 x1  + a22 x2  +  ...  + a2n xn  – b2 ) = 0
...
(3.m)   ym (am1 x1  + am2 x2  +  ...  + amn xn  – bm ) = 0

(4.1)   x1 (a11 y1  + a21 y2  +  ...  + am1 ym  – c1 ) = 0
(4.2)   x2 (a12 y1  + a22 y2  +  ...  + am2 ym  – c2 ) = 0
...
(4.n)   xn (a1n y1  + a2n y2  +  ...  + amn ym  = cn ) = 0

Метод решения двойственной задачи

Применяя теоремы двойственности, можно получить решение двойственной задачи из решения прямой. Опишем метод решения двойственной задачи.

Пусть мы нашли решение прямой задачи (1) с оптимальным значением целевой функции Fmax и с оптимальным планом x1 ,  x2 , ...,  xn . Подставим найденные значения x1 ,  x2 , ...,  xn в систему ограничений (1.2). Тогда если i-е неравенство не является равенством, то есть если
ai1 x1  + ai2 x2  +  ...   + ain xn  ≠ bi ,
то, согласно (3.i),
yi  = 0 .
Рассматривая все строки системы ограничений (1.2), мы найдем, что часть переменных Y двойственной задачи равна нулю.

Далее замечаем, что если xk  ≠ 0 , то, согласно (4.k), k-я строка системы ограничений (2.2) является равенством:
a1k y1  + a2k y2  +  ...   + amk ym  = ck .
Составив все строки системы ограничений (2.2), для которых xk  ≠ 0 , мы получим систему уравнений, из которой можно найти ненулевые значения переменных Y .

На основании первой теоремы двойственности, минимальное значение целевой функции
Zmin  = Fmax .

Если известно решение задачи (2), то аналогичным образом можно найти решение задачи (1).

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

Пример 1

Пусть дана задача линейного программирования:
F(X ) = 50x1  + 10x2  + 8x3 + 6x4  → max ;
{ 
40x1  + 2x2  + 2x3  + 3x4  ≤ 50
20x1  + 2x2  + 4x3  + 2x4  ≤ 30
15x1  + 4x2  + x3  ≤ 35
50x1  + 4x2  + 5x3  ≤ 120
x1  ≥ 0;  x2  ≥ 0;  x3  ≥ 0;  x4  ≥ 0
 

Известно решение этой задачи:
Fmax  = 125 ;   x1  = 0;  x2  = 35 / 4;  x3  = 0;  x4  = 25 / 4 .

Составить двойственную задачу и получить ее решение из решения прямой.

Решение

Составляем двойственную задачу.

Z(Y ) = 50y1  + 30y2  + 35y3 + 120y4  → min ;
{ 
40y1  + 20y2  + 15y3  + 50y4  ≥ 50
2y1  + 2y2  + 4y3  + 4y4  ≥ 10
2y1  + 4y2  + y3  + 5y4  ≥ 8
3y1  + 2y2  ≥ 6
y1  ≥ 0;  y2  ≥ 0;  y3  ≥ 0;  y4  ≥ 0
 

Согласно первой теореме двойственности, оптимальное значение целевой функции равно
Zmin  = Fmax  = 125 .

Применим вторую теорему двойственности. Подставим оптимальные значения переменных X в систему ограничений прямой задачи.
(П1.1.1)   40x1  + 2x2  + 2x3  + 3x4  = 40 ⋅ 0 + 2 ⋅ 354 + 2 ⋅ 0 + 3 ⋅ 254 = 36, 25 < 50 ;
(П1.1.2)   20x1  + 2x2  + 4x3  + 2x4  = 20 ⋅ 0 + 2 ⋅ 354 + 4 ⋅ 0 + 2 ⋅ 254 = 30 ;
(П1.1.3)   15x1  + 4x2  + x3  = 15 ⋅ 0 + 4 ⋅ 354 + 0 = 35 ;
(П1.1.4)   50x1  + 4x2  + 5x3  = 50 ⋅ 0 + 4 ⋅ 354 + 5 ⋅ 0 = 35 < 120 .
Поскольку первая и четвертая строки являются строгими неравенствами (не являются равенствами), то
y1  = 0   и   y4  = 0 .

Поскольку x2  ≠ 0   и   x4  ≠ 0 , то 2-я и 4-я строки двойственной задачи являются равенствами:
{ 
2y1  + 2y2  + 4y3  + 4y4  = 10
3y1  + 2y2  = 6
 

Подставим уже найденные значения   y1  = 0   и   y4  = 0 , имеем:
{ 
2y2  + 4y3  = 10
2y2  = 6
 

Отсюда
y2  = 6 / 2 = 3 ;
4y3  = 10 – 2y2  = 10 – 2 ⋅ 3 = 4 ;   y3  = 4 / 4 = 1 .

Ответ

Двойственная задача имеет вид:
Z(Y ) = 50y1  + 30y2  + 35y3 + 120y4  → min ;
{ 
40y1  + 20y2  + 15y3  + 50y4  ≥ 50
2y1  + 2y2  + 4y3  + 4y4  ≥ 10
2y1  + 4y2  + y3  + 5y4  ≥ 8
3y1  + 2y2  ≥ 6
y1  ≥ 0;  y2  ≥ 0;  y3  ≥ 0;  y4  ≥ 0
 

Ее решение
Zmin  = 125 ;   y1  = 0;  y2  = 3;  y3  = 1;  y4  = 0

Пример 2

Дана задача линейного программирования:
(П2.1.1)   F(X ) = 8x1  + 6x2  – 3x3  → max ;
(П2.1.2)  
{ 
3x1  + x2  – x3  ≤ 1
x1  + 2x2  + x3  ≤ 1
x1  ≥ 0;  x2  ≥ 0;  x3  ≥ 0
 

Найти решение этой задачи, решив двойственную задачу графическим методом.

Решение

Составляем двойственную задачу.

(П2.2.1)   Z(Y ) = y1  + y2  → min ;
(П2.2.2)  
{ 
3y1  + y2  ≥ 8
y1  + 2y2  ≥ 6
– y1  + y2  ≥ – 3
y1  ≥ 0;  y2  ≥ 0
 

Решение задачи (П2.2) приводится на странице “Решение задач линейного программирования графическим методом”. Решение задачи (П2.2) имеет вид:
Zmin  = 4 ;   y1  = 2;  y2  = 2 .

Согласно первой теореме двойственности, оптимальное значение целевой функции равно
Fmax  = Zmin  = 4 .

Применим вторую теорему двойственности. Подставим оптимальные значения переменных Y в систему ограничений прямой задачи (П2.2).
3y1  + y2  = 3 ⋅ 2 + 2 = 8 ;
y1  + 2y2  = 2 + 2 ⋅ 2 = 6 ;
– y1  + y2  = – 2 + 2 = 0 > – 3 .
Поскольку третья строка является строгим неравенством (не являются равенством), то
x3  = 0 .

Поскольку y1  ≠ 0   и   y2  ≠ 0 , то 1-я и 2-я строки двойственной задачи (П2.1) являются равенствами:
{ 
3x1  + x2  – x3  = 1
x1  + 2x2  + x3  = 1
 

Подставим найденное значение   x3  = 0 .
{ 
3x1  + x2  = 1
x1  + 2x2  = 1
 

Решаем систему уравнений.
x1  = 1 – 2x2 ;
3(1 – 2x2 ) + x2  = 1 ;
3 – 6x2  + x2  = 1 ;
5x2  = 2 ;   x2  = 2 / 5 ;
x1  = 1 – 2x2  = 55 – 2 ⋅ 25 = 15 .

Ответ

Решение исходной задачи (П2.1) имеет вид:
Fmax  = 4 ;   x1  = 1 / 5;  x2  = 2 / 5;  x3  = 0 .

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

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