Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 166
Скачиваний: 0
8 0 ГЛ. 3. ДВОЙСТВЕННОСТЬ
двойственности равенство z = w , |
или, |
учитывая (4), |
|
|
m-j-n |
|
|
z — w = |
2 |
xhyh = 0. |
|
|
/1=1 |
|
|
Но в силу того, что xt ^ |
0, |
г/г ^ |
0, это условие равносильно |
следующему: |
|
|
|
если yk > 0, то xh = |
0; |
если xk ;> 0, то yk = 0, |
|
что представляет собой теорему о слабой дополняющей неже-
сткости. |
|
|
|
|
|
|
|
|
Рассмотрим следующий пример: |
|
|
|
|||||
найти максимум х0 (минимум z) |
|
|
|
|||||
£„ = —Xi — хг — х3 |
(z = |
Xi + |
хг + |
х3) |
||||
при условиях |
|
|
|
|
|
|
|
|
|
X i |
= — 1 — X i — х 2 + Х з ^ 0, |
|
|||||
|
,а?5 |
= |
—7 |
-f- ajj Ц- х% -f- Зх3 /З5 0; |
|
|||
найти максимум у 0 (максимум w) |
|
|
|
|||||
при условиях |
Уо = |
Уь + Ь ь |
(^ = |
*/4 + |
7Уь) |
|
||
|
—г/i = |
—1 — г/4 + |
г/5 < |
0, |
|
|||
|
|
|
||||||
|
|
—Уг — —1 + |
г/4 + |
г/5 ^ |
0, |
|
||
|
|
—г/3 = |
—1 + |
г/4 + |
Зг/5 ^ |
0. |
|
|
В таблице приведены пять векторов, являющихся решениями |
||||||||
прямой и двойственной задач. |
|
|
|
|
||||
|
х<1> |
х(2) |
х<3> |
|
|
у<1> |
у<2) |
|
х0 |
—7 |
- 3 |
-7/3 |
|
1 |
1 |
1 |
|
Ч |
0 |
0 |
|
4/3 |
|
Vi |
0 |
- 1 /2 |
Ч |
0 |
0 |
|
0 |
|
Уь |
1/3 |
1/2 |
1 |
1 |
1 |
1 |
|
Уо |
7/3 |
3 |
|
Xi |
3 |
1 |
0 |
|
у1 |
2/3 |
0 |
|
Ч |
4 |
0 |
|
0 |
|
Уг |
2/3 |
1 |
х3 |
0 |
2 |
|
7/3 |
|
Уз |
0 |
0 |
3.4. Г ЕО М Е ТРИ Ч Е С К А Я И Н Т Е Р П Р Е Т А Ц И Я |
81 |
||
Нетрудно проверить, что любой вектор |
( / = 1 , 2 , 3 ) орто |
||
гонален каждому вектору у({) (i — 1, 2); х^>, х^2) и |
х(3>— допусти |
||
мые решения, в то время как |
допустимо, |
а |
у<2>—нет; х(3> |
и у^1) образуют пару оптимальных решений, поскольку z = —х0 = = + 7/3 = y0= w .
3.4. Геометрическая интерпретация двойственности и дополняю щей нежесткости (Гомори [83])
Рассмотрим |
задачу: |
|
|
|
|||||
найти |
минимум |
|
|
п |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z = |
2 C j X j |
|
при условиях |
|
|
|
J=1 |
|
||||
|
|
|
|
|
|
||||
|
|
|
|
|
'ZjdijXj^sbi |
( i = l , . . . , m ) , |
|
||
|
|
|
|
|
|
|
0 |
(/ = 1, . ..,ra), |
|
или, в другой форме записи: |
|
|
|||||||
минимизировать |
|
|
сх |
(1) |
|||||
при условиях |
|
|
|
|
|||||
|
|
|
|
|
|
||||
|
|
|
a*x ^ b i |
( i = l , |
. . . , иг-fra), |
(2) |
|||
где а* (Ь*) при г = |
1, |
. . . , т совпадают с a* (bi); aZ+i есть еди |
|||||||
ничный |
орт е;, |
а &,*+i = |
0 при |
|
|||||
i = l, |
■■■, |
п. |
|
|
|
|
|
|
|
Обычное условие наличия без |
|
||||||||
условного |
экстремума функции |
|
|||||||
во внутренней точке есть обраще |
|
||||||||
ние в 0 градиента |
функции в этой |
|
|||||||
точке. |
Если при этом должны вы |
|
|||||||
полняться некоторые ограничения |
|
||||||||
на переменные в виде равенств, |
|
||||||||
то условием наличия экстремума |
|
||||||||
в допустимой точке |
будет |
требо |
|
||||||
вание, чтобы в этой точке гра |
|
||||||||
диент |
|
функции |
и |
нормали |
к |
|
|||
поверхностям, |
соответствующим |
|
|||||||
ограничениям, |
были |
направлены |
|
||||||
в «одну |
сторону». Более |
точно, |
|
||||||
градиент функции в этой точке должен быть линейной комбинаци ей этих нормалей к поверхностям-ограничениям. В задаче линей ного программирования каждое неравенство определяет допу стимую область — полупространство. Для того чтобы допустимая точка х была оптимальной, необходимо, чтобы градиент в х 6 т. Ху
82 |
ГЛ. 3. ДВОЙСТВЕННОСТЬ |
выражался в виде неотрицательной линейной комбинации направ ляющих векторов тех (и только тех) ограничений, которые в точ
ке х обращаются в равенства (см. рис. 3.1).
Таким образом, если х — допустимая точка, в которой функция сх достигает минимума, то должна существовать неотрицательная линейная комбинация нормалей векторов а*, дающая вектор с — градиент функции сх:
m + n
с = 2 2/га?, |
(За) |
i = 1 |
|
£/г > 0 =£> а*х = Ъ*. |
(36) |
Покажем, что х является оптимальным решением задачи (1), (2). Умножим обе части равенства (За) на х:
|
|
7П+П |
|
777+71 |
|
|
|
с х = 2 #га?х= 2 УМ- |
(4а) |
||||
|
|
i=l |
|
i=l |
|
|
Для других y i ^ 0, |
удовлетворяющих равенству (За), |
|
||||
|
_ |
m + n |
_ |
m + n |
|
|
|
сх = |
j У & Н > Ъ |
У&?• |
(46) |
||
|
|
i=i |
|
i=i |
|
|
Из условий (4а) и (46) следует, |
что |
у —оптимальное |
решение |
|||
задачи: |
|
|
|
|
|
|
найти максимум |
|
|
|
|
|
|
|
|
|
У*>* |
|
|
(5) |
при условиях |
|
|
|
|
|
|
|
|
m + n |
|
|
|
|
|
С = |
2 2/;а?, |
У1 >0. |
(6) |
||
|
|
7 = 1 |
|
|
|
|
Поскольку последние п вектор-строк а* являются единичными |
||||||
777 |
|
|
|
|
|
|
ортами, a yb* = 2 |
y^i в силу Ьт+у = 0 (; = 1, .. ., п), то задача (5), |
|||||
7 = 1 |
|
|
|
|
|
|
(6) эквивалентна следующей: |
|
|
|
|
||
нацти максимум |
|
|
|
|
|
|
|
|
|
777 |
|
|
|
|
|
W= |
2 |
yfci |
|
(7) |
при условиях |
|
|
1=1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
(8) |
|
i=l |
|
|
|
|
|
|
У1>0 |
({ = 1, . . . , т ) . |
(9) |
3.4. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ |
83 |
Распишем векторное неравенство (8) по компонентам, учтя при
этом, что а* = а; |
при |
г = 1, . .., т. |
Получим |
|||
|
|
771 |
|
|
|
|
|
|
2 ytaij^Cj |
( / = |
1, |
( 8') |
|
|
|
i=i |
|
|
|
|
Итак, |
вектор |
[уи |
. . . , у т] |
является |
оптимальным решением |
|
задачи (7), |
(8), (9), двойственной к (1), |
(2). Так как х —допусти- |
||||
тга
мая точка, а сх = |
2 Уfit = 2 yfih то в силу теоремы двойствен- |
|||||
|
_ |
|
г=1 |
г=1 |
|
|
ности |
х — оптимальное |
решение |
задачи (1), |
(2), т. е. исходной |
||
задачи. |
о |
дополняющей |
пежесткости |
утверждалось, что |
||
В |
теоремах |
|||||
|
- |
Уг(а*х—b i ) = О1) |
(i= l, • •., т ) . |
|||
В слабой' форме теоремы о дополняющей нежесткости утвержда лось, что
если г/;> 0, то агх —Ьг = О,
и
если а*х— Ьг- > 0, то г/г = 0.
В сильной форме теоремы о дополняющей нежесткости утвержда лось:
если уг = 0, то а;х —Ьг> 0 ,
если агх —bi —0, то у* > 0.
Дадим геометрическую интерпретацию этим результатам. На рис. 3.2 изображены три гиперплоскости агх = Ьг = 0 (i = 1, 2, 3) и нормали к ним aj, а2, а3. Если вектор с — такой, как показано на рис. 3.2, то он может быть выражен в виде неотрицательной линейной комбинации векторов ai и а2, вершина в кружке дает
оптимальное |
решение. |
|
|
Пусть уи у2 и г/з—соответствующие -коэффициенты линейной |
|||
комбинации. Заметим, что здесь |
|
||
|
у1 > |
0 <=> а4х — Ъ{ = 0, |
|
|
Уг > |
0 <=> а2х —Ь2 = 0, |
|
|
Уз = 0 о а3х — Ь3 > 0. |
|
|
1У Другое |
утверждение этих теорем (cj — г/а,-) = |
0 симметрично рас |
|
смотренному и |
интерпретируется аналогично,— Прим. |
ред. |
|
6*