МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ЭЛЕМЕНТЫ ТЕОРИИ ДВОЙСТВЕННОСТИ
Учебно-методическое пособие для вузов
Составители:
Г.Д.Чернышова,
И.Н.Булгакова
Издательско-полиграфический центр
Воронежского государственного университета
2011
Стр.1
1. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ
ПРОГРАММИРОВАНИИ
1.1. Правила построения двойственных задач
1. Рассмотрим задачу линейного программирования следующего вида:
T → max,
cx
A ≤ ,xb
x ≥ 0,
где == = (b1,..., ,
ccc x x x ) b11 ,
TT T
nn
(
,..., ,
)
(
,...,
Lx y c x y b Ax c x
,,0,≥ ≥ 0.
=+ − = +∑ ())
TT T
)
y b Ax x y
ii −(
i
max m≥in , ,
x≥0
y 0 L xy)
bn ) A= ( ), 1, , 1, .
a
ij
i =
n j = m
Функция Лагранжа для задачи (1) – (3) записывается в виде
() (
Задачу (1) – (3) можно эквивалентно переписать следующим образом:
(
так как для любого фиксированного x
ii ()i
mi ()n cx y b Ax cx приbAx .)i
⎡⎤ ,+−
⎢⎥=
⎣⎦
y≥0
∑
TT
min max , ,
x≥0
L xy)
(
≥ 0 имеет место равенство
i ≥
Двойственная задача по определению записывается в виде
(
где (,,) x y0,≥ ≥ 0 .
L x y b yx cA y
)=+ −TT T
(
Зафиксируем произвольное y ≥ 0. Тогда имеют место равенства
(
= ⎪
виде:
3
⎧+∞ ∃ −jc A y j >
T
⎨ ∀− ≤
⎩
⎪b y
TT T
j
j c Ay j
()
()
max , max
, если :0,
, если :0или
xx (00
≥≥⎣
L x y) = +− =)⎤
j
⎡b yx cA y ⎦
TT T
Ay c.
≥
Таким образом, двойственную задачу можно записать в следующем
(1)
(2)
(3)
Стр.3
Таким образом, под двойственной задачей (ДЗ) к исходной понимается
задача линейного программирования, которая строится по следующим правилам,
приведенным в таблице.
Исходная задача
n
∑ →
=
j 1
∑a x b≤
=1
c j x j
n
ij
j
∑a x b≥
=1
n
ij
j
∑a x b=
=1
n
ij
j
x j ≥ 0
x j ≤ 0
x j – любого знака
∑a y c≥
=1
m
ij
i
∑a y c≤
=1
m
ij
i
∑a y =
=1
m
ij
i
Примечание. Когда целевая функция в исходной задаче минимизируется,
таблица прочитывается справа налево.
Данная таблица позволяет формулировать несколько общих правил построения
двойственных задач:
• каждому i -му ограничению исходной задачи соответствует переменная
iy в ДЗ, и, наоборот, каждому k -му ограничению ДЗ соответствует
переменная kx исходной задачи;
• матрицы ограничений в исходной и двойственной задачах взаимно
транспонированы;
• правые части ограничений исходной задачи становятся коэффициентами
целевой функции в ДЗ, а коэффициенты целевой функции
исходной задачи – правыми частями ограничений в ДЗ;
• если целевая функция в исходной задаче максимизировалась (минимизировалась),
то в ДЗ целевая функция минимизируется (максимизируется).
6
i
c
j
i
j
i
j
j
i
y i – любого знака
j
i
yi ≤ 0
j
max
i
Двойственная задача
m
∑ →
=
bi yi
i 1
yi ≥ 0
min
Стр.6
1.2. Свойства пары двойственных задач
ходной задачи (1) – (3) и двойственной задачи (4) – (6):
{
Qy A y
задачу (4) – (6) в виде
−→ max,
T
by
− ≤−T
с x
T
A yc
y ≥ 0,
A xb ,
x ≥ 0,
или
,
двойственная к которой по определению имеет вид
−→ min,
− ≥−T
2. Для любых ∈Ωx
cx
T → max,
T
A xb
x 0.≥
ствительно, всегда справедливы соотношения
TT T
yQ
3. Если в одной из задач (исходной или двойственной) отсутствует
c x xc x A y y Ax yb b y .
∀∈
=≤ = ≤ = T
x∈Ω
T
T
T
решение из-за неограниченности целевой функции на допустимом множестве,
то в двойственной к ней допустимое множество пусто.
Например, если supc xT
Ω
= +∞, то ∅=Q .
Доказательство.
Предположим противное. Пусть ∅≠Q , тогда y Q∃ ∈
ной задачи, y
– решение двойственной задачи.
x
и ∃∈
Следовательно, x
– решение исходной задачи.
Из свойства 2 следует, что ∀ ∈ Ωx
yQ такие, что cx b y , то
TT
=
Используя свойство 2, запишем неравенство TT
cx b y≤ , ∀ ∈ Ωx
.
, что
противоречит неограниченности целевой функции xcT на множестве Ω.
4. Если ∃∈Ω
x – решение исходможно
записать TT T .
cx b y cx≤=
5. Возможна ситуация: ∅=Ω и ∅=Q .
Рассмотрим пример. Исходная задача задана в виде
7
≤ ,
и Qy∈ имеет место неравенство cx b y ДейTT
≤
.
=≥
≥
{ :, }0 .
T
xA ≤ ≥
c y
x b x
1. Задача, двойственная к двойственной, является исходной. Запишем
Обозначим через Ω и Q соответственно допустимые множества исΩ=
:, }0 ,
Стр.7
32 max,
4,
2.
⎧ +=
⎨ +=
⎩
xx
xx
xx
12
12
12
Допустимое множество ∅=Ω .
Двойственная к исходной запишется следующим образом:
+ →
42 min,
3,
2.
⎧ +=
⎨ +=
⎩
Допустимое множество ∅=Q .
6. Пусть ∅≠Ω
yy
yy
yy
12
12
12
и ∅=Q , тогда исходная задача не имеет решения изза
неограниченности целевой функции на допустимом множестве.
7. Если ∅≠Ω и ∅≠Q , то обе задачи имеют решение.
Первая теорема двойственности
Если одна из задач (исходная или двойственная) имеет решение, то и
вторая имеет решение, причем оптимальные значения целевых функций
совпадают.
Доказательство.
Пусть задана задача в каноническом виде
с x
T → max,
A = ,xb
x ≥ 0,
И пусть она имеет решение 0x , полученное, например, симплекс-методом.
Двойственная задача записывается в виде
by
Ay c
T
T
Точка 0x является базисной, x
Обозначим через y = BcT
0
b
тимая в двойственной задаче.
8
Δ = c B A c− ≥
− 1
j
T
b
−1
j
j
→
≥
min,
.
0 = ⎡xb ⎤
0
⎢
⎣
⎥
⎦
, где x B b
, ∀ =1, .
j
n
b = −1 . Пусть B – оптимальный
базис, тогда оптимальность означает выполнение условий
0
. Тогда A yT ≥0
c , то есть точка 0y – допус+
→
Стр.8