Элементы теории двойственности (110
..pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ЭЛЕМЕНТЫ ТЕОРИИ ДВОЙСТВЕННОСТИ
Учебно-методическое пособие для вузов
Составители: Г.Д.Чернышова, И.Н.Булгакова
Издательско-полиграфический центр Воронежского государственного университета
2011
Утверждено научно-методическим советом факультета ПММ 30 ноября 2011 года, протокол № 3
Рецензент канд. физ.-мат. наук, доц. Т.К. Кацаран
Учебно-методическое пособие подготовлено на кафедре математических методов исследования операций факультета ПММ Воронежского государственного университета.
Рекомендуется для студентов 2-го курса дневного и вечернего отделений и магистров факультета ПММ.
Для направлений: 010500 – Прикладная математика и информатика, 080700 – Бизнес-информатика; для специальности 010501 – Прикладная математика и информатика
2
1. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1.1.Правила построения двойственных задач
1.Рассмотрим задачу линейного программирования следующего вида:
cT x → max, |
(1) |
Ax ≤ b, |
(2) |
x ≥ 0, |
(3) |
где cT =(c1, ..., cn ), xT =( x1, ..., xn ), bT =(b1, ..., bn ), A = (aij ), i =1, n, j =1,m.
Функция Лагранжа для задачи (1) – (3) записывается в виде
L( x, y) = cT x + yT (b − Ax) = cT x + ∑ yi (bi −( Ax)i ), x ≥ 0, y ≥ 0 .
Задачу (1) – (3) можно эквивалентно переписать следующим образом:
max min L( x, y),
x≥0 y≥0
так как для любого фиксированного x ≥ 0 имеет место равенство
|
|
= cT x, при bi ≥( Ax )i . |
min cT x |
+ ∑ yi (bi −( Ax )i ) |
|
|
|
|
Двойственная задача по определению записывается в виде
min max L( x, y),
y≥0 x≥0
где L( x, y) =bT y + xT (c − AT y), x ≥ 0, y ≥ 0 .
Зафиксируем произвольное y ≥ 0 . Тогда имеют место равенства
x≥0 |
( |
x, y |
) |
x≥0 |
+ xT |
( |
c − AT y |
) |
|
max L |
|
|
= max bT y |
|
= |
||||
+∞, если j : cj −( AT y) |
j |
> 0, |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
|
≤ 0 или AT y ≥ c. |
|||
bT y, если j : cj −( AT y) |
|||||||||
|
|
|
|
|
|
j |
|
|
|
Таким образом, двойственную задачу можно записать в следующем виде:
3
bT y → min, |
(4) |
AT y ≥ c, |
(5) |
y ≥ 0. |
(6) |
2. Аналогичные рассуждения проведем для задачи, записанной в канонической форме:
сT x → max,
Ax =b, x ≥ 0.
Перепишем задачу в виде (1) – (3):
сT x → max,
Ax ≤b,
−Ax ≤ −b,
x≥ 0.
Функция Лагранжа в этом случае будет выглядеть следующим обра-
зом:
L( x,u,v) = cT x +uT (b − Ax) + vT (−b + Ax) = cT x +(u −v)T (b − Ax), x ≥ 0, u ≥ 0, v ≥ 0.
Обозначим переменную u −v через переменную y . Тогда функцию Лагранжа можно записать так: L( x, y) = cT x + yT (b − Ax) , x ≥ 0 , y – любого знака.
По определению двойственная задача к канонической записывается в
виде
min max bT y + xT |
( |
c − AT y |
|
= min bT y. |
|
y− |
x≥0 |
|
) |
AT y≥с |
Таким образом, двойственную задачу к канонической можно записать в следующем виде:
bT y → min,
AT y ≥ с,
y− знака.
3.Рассмотрим далее задачу линейного программирования (1) – (2)
4
cT x → max, |
|
(1) |
|
Ax ≤ b. |
|
|
(2) |
′ |
′′ ′ |
′′ |
≥ 0 . Задача эквивалент- |
Введем замену переменных x = x |
− x , x |
≥ 0, x |
но перепишется следующим образом:
cT ( x′− x′′) → max,
A( x′− x′′) ≤b, x′≥ 0, x′′≥ 0.
Функция Лагранжа для задачи имеет вид
L( x′, x′′, y) = cT ( x′− x′′) + yT (b − A( x′− x′′)), x′≥ 0, x′′≥ 0, y ≥ 0.
Исходную задачу перепишем в виде:
max min L( x′, x′′, y).
x′,x′′≥0 y≥0
По определению двойственная задача запишется в виде
min max L( x′, x′′, y),
y≥0 x′,x′′≥0
L( x′, x′′, y) = bT y +( x′− x′′)T (c − AT y).
Зафиксируем произвольное y ≥ 0 . Тогда справедливы равенства
x− |
( |
x, y |
) |
|
x− |
|
|
|
( |
c − AT y |
) |
max L |
|
|
= max bT y + xT |
|
= |
||||||
+∞, если j : cj −( AT y) |
j |
≠ 0, |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
|
|
|
= 0 или AT y = c, |
|||
bT y, если j : cj −( AT y) |
|||||||||||
|
|
|
|
|
|
|
|
j |
|
|
|
min max bT y |
+ xT |
( |
c − AT y |
= min bT y, если AT y = c. |
|||||||
y≥0 x− |
|
|
|
|
) |
|
y≥0 |
|
|
|
Двойственную задачу можно записать следующим образом:
bT y → min,
AT y = c, y ≥ 0.
5
Таким образом, под двойственной задачей (ДЗ) к исходной понимается задача линейного программирования, которая строится по следующим правилам, приведенным в таблице.
Исходная задача |
Двойственная задача |
|
n |
m |
|
∑c j x j → max |
∑bi yi → min |
|
j=1 |
i=1 |
|
n |
yi ≥ 0 |
|
∑aij x j ≤ bi |
||
|
||
j=1 |
|
|
n |
yi ≤ 0 |
|
∑aij x j ≥ bi |
||
|
||
j=1 |
|
|
n |
yi – любого знака |
|
∑aij x j = bi |
||
|
||
j=1 |
|
|
x j ≥ 0 |
m |
|
∑aij yi ≥ c j |
||
|
||
|
i=1 |
|
x j ≤ 0 |
m |
|
∑aij yi ≤ c j |
||
|
||
|
i=1 |
|
x j – любого знака |
m |
|
∑aij yi = c j |
||
|
||
|
i=1 |
Примечание. Когда целевая функция в исходной задаче минимизируется, таблица прочитывается справа налево.
Данная таблица позволяет формулировать несколько общих правил построения двойственных задач:
•каждому i -му ограничению исходной задачи соответствует переменная yi в ДЗ, и, наоборот, каждому k -му ограничению ДЗ соответствует переменная xk исходной задачи;
•матрицы ограничений в исходной и двойственной задачах взаимно транспонированы;
•правые части ограничений исходной задачи становятся коэффициентами целевой функции в ДЗ, а коэффициенты целевой функции исходной задачи – правыми частями ограничений в ДЗ;
•если целевая функция в исходной задаче максимизировалась (минимизировалась), то в ДЗ целевая функция минимизируется (максимизируется).
6
1.2. Свойства пары двойственных задач
Обозначим через Ω и Q соответственно допустимые множества ис-
ходной задачи (1) – (3) и двойственной задачи (4) – (6):
Ω ={ x : Ax ≤ b, x ≥ 0} ,
Q={ y : AT y ≥ c, y ≥ 0}.
1.Задача, двойственная к двойственной, является исходной. Запишем задачу (4) – (6) в виде
−bT y → max,
−AT y ≤ −c, y ≥ 0,
двойственная к которой по определению имеет вид
|
−сT x → min, |
или |
cT x → max, |
|
−AT x ≥ −b, |
AT x ≤ b, |
|
|
x ≥ 0, |
|
x ≥ 0. |
2. |
Для любых x Ω и y Q имеет место неравенство cT x ≤ bT y. Дей- |
||
ствительно, всегда справедливы соотношения |
|||
|
cT x = xT c ≤ xT AT y = yT Ax ≤ yT b = bT y. |
||
3. |
|
y Q |
xΩ |
Если в одной из задач (исходной |
или двойственной) отсутствует |
решение из-за неограниченности целевой функции на допустимом множестве, то в двойственной к ней допустимое множество пусто.
Например, если sup cT x = +∞, то Q = .
Ω
Доказательство.
Предположим противное. Пусть Q ≠ , тогда y Q .
Используя свойство 2, запишем неравенство cT x ≤ bT y , x Ω, что противоречит неограниченности целевой функции cT x на множестве Ω.
4. Если x Ω и y Q такие, что cT x =bT y , то x – решение исходной задачи, y – решение двойственной задачи.
Из свойства 2 следует, что x Ω можно записать cT x ≤ bT y = cT x . Следовательно, x – решение исходной задачи.
5. Возможна ситуация: Ω = и Q = . Рассмотрим пример. Исходная задача задана в виде
7
3x1 + 2x2 → max,
x1 + x2 = 4,
x1 + x2 = 2.
Допустимое множество Ω = .
Двойственная к исходной запишется следующим образом: 4 y1 + 2 y2 → min,
y1 + y2 = 3,
y1 + y2 = 2.
Допустимое множество Q = .
6. Пусть Ω ≠ и Q = , тогда исходная задача не имеет решения из-
за неограниченности целевой функции на допустимом множестве. 7. Если Ω ≠ и Q ≠ , то обе задачи имеют решение.
Первая теорема двойственности
Если одна из задач (исходная или двойственная) имеет решение, то и вторая имеет решение, причем оптимальные значения целевых функций совпадают.
Доказательство.
Пусть задана задача в каноническом виде
сT x → max,
Ax = b, x ≥ 0,
И пусть она имеет решение x0 , полученное, например, симплекс-методом. Двойственная задача записывается в виде
bT y → min,
AT y ≥ c.
Точка x |
0 |
является базисной, |
x |
0 |
xb |
, где |
xb = B |
−1 |
||
|
|
= |
0 |
|
b . Пусть B |
|||||
|
|
|
|
|
|
|
|
|
|
мальный базис, тогда оптимальность означает выполнение условий j = cbT B−1 Aj − c j ≥ 0 , j =1, n .
Обозначим через y0 = cbT B−1 . Тогда AT y0 ≥ c , то есть точка y0
тимая в двойственной задаче.
–опти-
–допус-
8
Покажем теперь, что y0 – оптимальная точка в двойственной задаче. Действительно, имеет место равенство
cT x0 = cbT xb = cbT B−1b = (y0 )T b = bT y0 .
По свойству 4 точка y0 = cbT B−1 является оптимальной.
Теорема доказана.
Следствие
Совместность системы ( ) является необходимым и достаточным условием для решения исходной и двойственной задачи (если исходная записана в каноническом виде):
Ax = b, |
|
||||
|
|
|
|
|
|
x ≥ 0, |
|
( ) |
|||
AT y ≥ c, |
|||||
|
|||||
|
T |
x = b |
T |
y. |
|
c |
|
|
|||
Для задачи (1) – (3) аналогичная система имеет вид |
|||||
Ax ≤ b, |
|
x Ω, |
|||
|
|
||||
x ≥ 0, |
|
|
|
|
|
AT y ≥ c, |
|
|
|
|
|
|
|
y Q. |
|||
y ≥ 0, |
|
|
|
|
cT x = bT y,
Вторая теорема двойственности
Пусть решается задача (1) – (3). Для того, чтобы x0 Ω, y0 Q были
решениями исходной и двойственной задач, необходимо и достаточно выполнение условий дополняющей нежесткости:
|
0T |
T |
0 |
) = 0, |
|
|
0 |
|
T |
0 |
|
|
|
|
|
|
|
|
|
(ci |
) |
) = 0, i = 1,n, |
|||||||||||||||
x |
|
(c − A y |
|
|
|
xi |
− ( A y |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
y0T (b − AT x0 ) = 0, |
или |
|
0 |
|
T |
|
0 |
|
|
|
|
|
|
|
||||
(bj |
|
) |
|
)= 0, j = 1,m. |
||||||||||||||
|
|
|
|
|
|
y j |
− ( A x |
|
j |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Доказательство.
1. Необходимость.
Пусть x0 Ω – решение исходной задачи, y0 Q – решение двойственной задачи. Тогда по первой теореме двойственности
9
cT x0 =bT y0 = y0T b ≥ y0T Ax0 , x0T (c − AT y0 ) ≥ 0.
С другой стороны, x0 ≥ 0, c − AT y0 ≤ 0 . Значит, x0T (c − AT y0 ) ≤ 0 . Получаем, что x0T (c − AT y0 ) = 0 .
Аналогичные рассуждения проводятся для второго равенства. 2. Достаточность.
Пусть в некоторых точках x0 Ω, y0 Q выполняются условия допол-
няющей нежесткости; покажем, что они являются оптимальными точками. |
|||||||||
Заметим, что x0T |
(c − AT y0 ) = y0T (b − Ax0 ) . |
||||||||
Тогда |
cT x0 − (AT y0 )T x0 |
= bT y0 |
− (AT y0 )T x0 . Откуда следует равен- |
||||||
ство cT x 0 |
= bT y 0 . |
|
|
|
|
|
|
|
|
Из свойства 3 следует, что x0 |
– решение исходной задачи, а y0 – ре- |
||||||||
шение двойственной задачи. |
|
|
|
|
|
|
|
||
Теорема доказана. |
Следствие |
|
|
||||||
|
|
|
|
|
|||||
Совместимость системы ( ) |
является необходимым и достаточным |
||||||||
условием того, что x0 |
– решение исходной задачи, а y0 – решение двойст- |
||||||||
венной задачи. |
|
(x |
|
) |
|
|
|
)) = 0, |
|
|
|
T |
0 |
T |
T |
0 |
|||
|
Ax ≤b, A y ≥ c, |
|
|
(c −( A y |
|
||||
|
|
|
( y0 )T (b −( Ax0 )) |
( ) |
|||||
|
x ≥ 0, |
y ≥ 0, |
= 0. |
||||||
|
|
|
|
|
|
|
|
|
|
2. ЭКОНОМИЧЕСКИЙ СМЫСЛ ДВОЙСТВЕННЫХ ПЕРЕМЕННЫХ
Пусть исходная задача планирования производства фирмы имеет вид
CΤx → max,
Ax ≤b, x ≥ 0.
В приведенной модели b = (b1, ..., bm ) , где bi (i = 1, ..., m) обозначает за-
пас ресурса вида i, элементы матрицы A = {aij } обозначают число единиц ресурса вида i, потребляемого при производстве единицы продукции вида j,
10