Выпуклый анализ. Теория двойственности в линейном программировании. Лекция 29

1. ВЫПУКЛЫЙ АНАЛИЗ

ЛЕКЦИЯ 14
11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ

2.

11. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ (ПРОДОЛЖЕНИЕ)
11.5. Теоремы двойственности и равновесия.

3.

11.5. Теоремы двойственности и равновесия.
Справедлива следующая теорема,
которую обычно называют теоремой двойственности.
Теорема 1. Либо обе взаимнодвойственные задачи линейного программирования
Задача 3 и Задача 3д(а) не имеют решения, либо они обе имеют решение и при этом
справедливо равенство
где
u* -
решение прямой, а
I ( u* ) =- I Д ( l
*
l -
*
),
решение двойственной задачи.
Доказательство. Выпишем функцию Лагранжа для задачи 3.
Задача 3.
c, u ® inf,
Aw - b £ 0,
ˆ - bˆ = 0
Aw
ìï
üï
æ wö
u ÎU 0 = íu = ç ÷ Î R k ´ R n - k w ³ 0 ý .
è wø
ïî
ïþ
æ u1 ö
æ u k +1 ö
ç ÷
ç
÷
w = çL ÷, w = ç L ÷
ç uk ÷
ç un ÷
è ø
è
ø
L ( u , l ) = c, u +
+ m , Au - b + m , Aˆ u - bˆ =
= c + AT m + Aˆ T m , u - b, m - bˆ, m ,
æ lm +1 ö
æ l1 ö
ç
÷
s-m
ç ÷
m
m
=
L
Î
R
m = çL ÷Î R ,
ç
÷
ç l ÷
çl ÷
è s ø
è mø

4.

ìï
üï
æ wö
k
n-k
w ³ 0ý ,
U 0 = íu = ç ÷ Î R ´ R
è wø
ïî
ïþ
ìï
üï
æmö
m
s -m
m ³ 0ý.
L 0 = íl = ç m ÷ Î R ´ R
è ø
ïî
ïþ
Область ее определения
U 0 ´ L0 ,
где
Выпишем функцию Лагранжа для задачи 3д(а).
Задача 3д(а).
b, m + bˆ, m ® inf,
(
-c - A m - Aˆ T m £ 0, i Î { 1,L , k } ;
)
(
c + A m + Aˆ T m
T
T
k
)
(
i
i
j =1
ìï
üï
æmö
m
s -m
= íl = ç ÷ Î R ´ R
m ³ 0ý.
èmø
ïî
ïþ
= 0, i Î { k + 1,L , n} ;
L Д ( l , u ) = b, m + bˆ, m +
+ å u -c - A m - Aˆ m
j
l Î L0 =
T
T
) + å u ( -c - A m - Aˆ m )
j
n
j = k +1
T
j
T
= b, m + bˆ, m - c + A m + Aˆ T m , u .
T
j
=

5.

и область ее определения
U 0 Д ´ L 0Д ,
где
ìï
üï
æmö
m
s -m
m ³ 0ý .
U 0 Д = L = íl = ç ÷ Î R ´ R
èmø
ïî
ïþ
ìï
üï
æ wö
0
k
n-k
L Д = U 0 = íu = ç ÷ Î R ´ R
w ³ 0, i Î K ý ,
è wø
ïî
ïþ
0
Сравним функцию Лагранжа для двойственной задачи
LД ( l , u ) = b, m + bˆ, m - c + AT m + Aˆ T m , u
с функцией Лагранжа для основной задачи
L ( u , l ) = c + AT m + AT m , u - b, m - b , m .
Приходим к равенству
æmö
L ( u , l ) º - L Д ( l , u ) , u ÎU 0 , l = ç ÷ Î L 0 .
èmø

6.

*
0
u
,
l
Î
U
´
L
( * ) 0 -
Пусть
седловая точка функции
L ( u, l ) .
Тогда
L ( u* , l ) £ L ( u* , l * ) £ L ( u , l * ) , u Î U 0 , l Î L 0 Þ
- L ( u* , l ) ³ - L ( u* , l * ) ³ - L ( u , l * ) , u Î U 0 , l Î L 0 Þ
- L ( u, l
*
LД
) £ -L ( u , l )
( l, u ) £ L ( l , u ) £ L ( l , u ) ,
Таким образом,
При этом
*
*
*
0
0
l
Î
L
=
U
,
u
Î
U
=
L
£ - L ( u* , l ) ,
0Д
0
Д Þ
*
Д
*
*
Д
*
0
l
,u
Î
L
( * ) ´U 0 -
l ÎU 0 Д , u Î L 0Д .
седловая точка функции
LД ( l , u ) .
L ( u* , l * ) = - L Д ( l * , u* ) .
( 1)
u* решение задачи 3. Тогда по теореме 9.3 существует седловая точка ( u , l * ) Î U ´ L 0
*
0
*
функции Лагранжа для этой задачи. При этом I ( u* ) = L ( u* , l ) .
Пусть одна из взаимно двойственных задач имеет решение. Например,

7.

Выше установлено, что
( l ,u ) Î L
*
Тогда по теореме 9.2 точка
(
В силу (1) L u* , l
*
*
0
´U 0 -
седловая точка функции
LД ( l , u ) .
l * является решением задачи 3д(а) и
L Д ( l * , u* ) = I Д ( l * ) .
) = - L ( l , u ) ( 1) справедливо равенство
I ( u* ) =- I Д ( l * ) .
*
Д
*
Аналогично устанавливается, что из существования решения двойственной задачи
следует существование решения основной задачи. Из приведенных рассуждений следует
также, что если одна из взаимно двойственных задач не имеет решения, то и другая не
может его иметь. Теорема доказана.
Установим условия разрешимости взаимно двойственных задач.
Теорема 2. Для существования решения взаимодвойственных задач достаточно,
чтобы обе взаимодвойственные задачи были допустимыми.
Доказательство. Достаточно установить ограниченность снизу
взаимно двойственных задач. Пусть
целевых функций
æ wö
æmö
u = ç ÷ ÎU , l = ç ÷ ÎU Д .
è wø
èmø
Тогда

8.

(
k
n
I ( u ) = c, u = å c j u = å
j
³
å(
j =1
n
c
)
n
å
(
)
c j = - AT m- Aˆ T m
cj
j
uj ³
j =k +1
j
- AT m- Aˆ T m u j +
(
u +
j =1
j =1
k
)
j
c j ³ - AT m- Aˆ T m ³ 0
j
j
)
n
å (
)
j
- A m- Aˆ T m u j =
T
j =k +1
j
= å - A m- Aˆ m u j = - AT m- Aˆ T m, u =
j =1
T
T
= - AT m, u + - Aˆ T m, u =
m³ 0 - Au³ - b
³ - m, b - m, bˆ =- I Д ( l ) Þ
Из (2) выводим
Таким образом, если
I ( u) ³ - I Д ( l ) ,
ˆ =- bˆ
- Au
ˆ
m, - Au + m, - Au
³
I ( u) ³ - I Д ( l ) .
( 2)
" u Î U0 , l Î L 0.
I Д ( l ) ³ - I ( u) ,
u - допустимая точка основной задачи,
( 3)
то целевая функция

9.

- I ( u) .
двойственной задачи ограничена снизу числом
l -
Наоборот, если
допустимая
точка двойственной задачи, то целевая функция основной задачи ограничена снизу
числом
- IД (l ) .
Ограниченность целевой функции (снизу при решении задачи
линейного программирования на минимум) является достаточным условием ее
разрешимости. Теорема доказана.
Теорема 3 (равновесия). Пусть
u* Î U
и
l *Î L-
ных задач 3 и 3Д(а) соответственно. Тогда для всех
(
решения взаимодвойствен-
j Î {1, L , k } выполнено
u > 0, j Î {1, L , k } Þ c j = - A m - A m
j
*
cj > ( -A m - A m
*
T
а для всех
i Î {1, L , m}
*
i
l >0 Þ
Доказательство.
i
T
*
)
j
T
*
T
*
)
j
,
j
Þ u* = 0,
выполнено
i
i
Au
<
b
Þ
Au
=
b
,
( *)
( *)
i
Из неравенства (2)
l i* = 0.
( 5)
( 4)

10.

n
k
I ( u ) = c, u = å c j u = å c j u +
j
j =1
n
+å
j =k +1
(
j
j =1
)
j
n
n
å
j
c ju ³
j =k +1
(
k
å(
)
j =1
)
j
- A m- Aˆ T m u j +
T
j
- A m- Aˆ T m u j = å - AT m- Aˆ T m u j = - AT m- Aˆ T m, u =
T
j =1
ˆ ³
= - AT m, u + - Aˆ T m, u = m, - Au + m, - Au
³ - m, b - m, bˆ =- I Д ( l ) .
( 2)
следует
ˆ ³
I ( u ) = c, u ³ - AT m- Aˆ T m, u = m, - Au + m, - Au
³ - m, b - m, bˆ =- I Д ( l ) .
В силу теоремы 1 справедливо равенство
I ( u* ) =- I Д ( l
Тогда при
u = u* , l = l
знаки равенства. Имеем
*
*
( 6)
).
все знаки неравенства в (6) следует заменить на

11.

ˆ
I ( u* ) = c, u* = - AT m* - Aˆ T m* , u* = m* , - Au* + m* , - Au
* =
=- m* , b - m* , bˆ =- I Д ( l
*
).
( 7)
Из (7) выводим
c, u* = - AT m* - Aˆ T m* , u* Þ
k
å(
)
j
- A m - Aˆ T m* - c u*j +
T
*
j =1
k
å(
- AT m* - Aˆ T m* - c, u* = 0 Þ
n
å (
=0 Задача 3 Д ( а )
j =k +1
)
В силу
(- A m*
Aˆ m - c
T
j
- A m - Aˆ T m* - c u*j = 0.
*
T
j =1
T
)
j
- A m - Aˆ T m* - c u*j = 0 Þ
*
T
*
)
j Задача 3 Д ( а )
£
j
*
0, u
Задача 3
³
( 8)
j = 1, L , k
0,
из (8) следует утверждение (4) теоремы
j
u > 0, j Î {1,L , k } Þ c j = ( - A m - A m ) ,
j
*
T
cj > ( -A m - A m
T
*
T
*
)
j
Þ u = 0,
j
*
*
T
*
j = 1,L , k
( 4)

12.

Аналогично из (7)
I ( u* ) = c, u* = - AT m* - Aˆ T m* , u* = m* , - Au* +
*
* ˆ
ˆ
+ m* , - Au
=m
,
b
m
, b =- I Д ( l
*
*
) . ( 7)
следует
*
* ˆ
ˆ
m, - Au* + m , - Au* =- m, b - m , b Þ
*
*
ˆ
0 =- m* , b + m* , Au* - m* , bˆ + m* , Au
* Þ
=0 Задача 3
*
*
ˆ - bˆ = 0 Þ
m, Au* - b + m , Au
*
m
ål
*
i
æ
l 1* ö
÷
ç
÷
ç
÷
* ç
ç
÷
m =çL ÷
÷
ç
÷
÷
ç
÷
ç
*
÷
ç
èl m ø
m* , Au* - b = 0 Þ
i
( Au* - b) = 0.
( 9)
i =1
В силу
i
Задача 3
( Au* - b) £ 0, l
i
*
утверждение (5) теоремы
Задача 3 Д ( а )
³
0, i = 1, L , m
i
l > 0 Þ ( Au* ) = bi ,
*
i
i
( Au* ) < b Þ l = 0
Теорема доказана.
из (9) следует
i
*
i
i = 1, L , m ( 5)

13.

Пример 1. Рассмотрим задачу линейного программирования
u1 + 2u 2 - 3u 3 + 5u 4 - 4u 5 ® min
u1 + 2u 2 - 3u 3 + 4u 4 + 6u 5 £ 8,
-2u1 + 3u 2 - 4u 3 + u 4 + 5u 5 £ 10,
-4u1 + 6u 2 + 2u 3 - 5u 4 + u 5 = -4,
3u1 - 5u 2 + 2u 3 + u 4 - 4u 5 = 8,
u1 ³ 0, u 2 ³ 0, u 3 ³ 0

14.

Построим двойственную к ней задачу:
8l1 + 10l2 - 4l3 + 8l4 ® min
-l1 + 2l2 + 4l3 - 3l4 £ 1,
-2l1 - 3l2 - 6l3 + 5l4 £ 2,
3l1 + 4l2 - 2l3 - 2l4 £ -3,
-4l1 - l2 + 5l3 - l4 = 5,
-6l1 - 5l2 - l3 + 4l4 = -4,
l1 ³ 0, l2 ³ 0.
Точка u Î R
5
с координатами
u1 = 0, u 2 = 0, u 3 = 0, u 4 =
8 5
36
,u =19
19
является допустимой для прямой задачи, так как выполняются соотношения

15.

8
36
184
0 + 2 × 0 + 3× 0 + 4 × - 6 × = < 8,
19
19
19
-2 × 0 + 3 × 0 - 4 × 0 +
Аналогично точка
8
36
172
- 5× = < 10,
19
19
19
8 36
-4 × 0 + 6 × 0 + 2 × 0 - 5 × = -4,
19 19
,
8
36
3 × 0 - 5 × 0 + 2 × 0 + + 4 × = 8.
,
19
19
4
l Î R с координатами
,
l1 = 5, l2 = 9, l3 =
207
389
, l4 =
19
19
,
является допустимой для двойственной задачи,
так как выполняются соотношения
207
389
+ 5×
= 0 < 2,
19
19
207
389
223
3×5 + 4 ×9 - 2 ×
- 2×
=< -3,
19
19
19
207
389
92
-5 + 2 × 9 + 4 ×
- 3×
= - < 1,
19
19
19
,
207
389
-6 × 5 - 5 × 9 + 4×
= -4,
19
19
-2 × 5 - 3 × 9 - 6 ×
207 389
-4 × 5 - 9 + 5 ×
= 5.
19
19

16.

По теореме 2 обе взаимодвойственные задачи имеют решение.
Выпишем эти решения.
Решение прямой задачи:
112 2
72 5
424
3
4
u =
, u* = 0, u* = 0, u* = - , u* = 4, I ( u* ) = 11
11
11
1
*
Решение двойственной задачи:
l1* =
30 *
45
424
, l2 = 0, l3* = 4, l4* = , I Д ( l * ) =
11
11
11
В соответствии с теоремой 1 здесь выполнено
равенство
,
I ( u* ) =- I Д ( l
*
).
В силу теоремы 3 первое ограничение прямой задачи на оптимальном векторе
u*
и первое ограничение двойственной задачи на оптимальном векторе l * должны
выполняться со знаком «=».
Действительно,
æ 72 ö
30
45
112
÷
ç
+ 2 ×0 + 4 ×4 - 3× = 1.
+ 2 ×0 - 3×0 + 4 ç+ 6 ×4 = 8, ÷
÷
ç
è 11 ø
11
11
11

17.

Вычислим второе ограничение основной задачи, а также второе и третье ограничения
двойственной задачи на оптимальных значениях переменных. Имеем
( -2u
1
+ 3u - 4u + u + 5u - 10 )
2
3
4
5
( -2l1 - 3l2 - 6l3 + 5l4 - 2 )
æ 112 ö
æ u1 ö ç
÷
ç ÷ ç 11 ÷
ç u2 ÷ ç 0 ÷
ç 3÷ ç
÷
ç u ÷ =ç 0 ÷
ç 4 ÷ ç 72 ÷
çu ÷ ç- ÷
çç 5 ÷÷ ç 11 ÷
èu ø ç 4 ÷
è
ø
æ 30 ö
æ l1 ö ç 11 ÷
ç ÷ ç ÷
ç l2 ÷ =ç 0 ÷
ç l3 ÷ ç 4 ÷
çç ÷÷ ç ÷
è l4 ø ç 45 ÷
ç ÷
è 11 ø
( 3l1 + 4l2 - 2l3 - 2l4 + 3)
186
=< 0,
11
125
=< 0,
11
æ 30 ö
æ l1 ö ç 11 ÷
ç ÷ ç ÷
ç l2 ÷ =ç 0 ÷
ç l3 ÷ ç 4 ÷
çç ÷÷ ç ÷
è l4 ø ç 45 ÷
ç ÷
è 11 ø
В полном соответствие с теоремой 3 выше было получено
49
= - < 0.
11
l2* = 0, u*2 = 0, u*3 = 0.