Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 164

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

 

3.2. ДОПОЛНЯЮЩАЯ НЕЖЕСТКОСТЬ

 

75

Тогда для любого

Я > 0,

х + к 0

также будет допустимым

реше­

нием, поскольку

 

 

 

 

 

 

 

 

 

 

 

А (х +

^х0) =

Ах + ЯАх0 >

Ь,

 

 

где Ах0^ О в силу

(1').

 

 

 

 

 

 

 

 

 

Используя условия (2 '), А х ^ Ь

и у о > 0 ,

х ^ О , получаем

 

 

 

 

0 > у 0А х > у 0Ь.

 

 

 

(13)

Из

условий (13) и (6) следует, что 0 ^

у0Ах ^ у0Ь >

сх0, т. е.

сх0

отрицательно.

Поскольку

сх0 — отрицательная

величина,

а

1

— любое положительное число, значение с (х + Кх0) =

сх +

+

Ясх0 может быть как угодно большим по абсолютной величине

отрицательным числом. Поскольку х +

Ях0 — допустимое

реше­

ние

прямой задачи, целевая функция

z

не ограничена

снизу.

Подобным же образом, если допустить существование у, удовле­

творяющего у А ^ с, можно доказать, что w не ограничена сверху. Итак, если t0 = 0 и одна из пары двойственных задач имеет допу­ стимое решение, то утверждение 2 теоремы доказано.

Случай 2в. В п. 2а было показано, что при t0 = 0 хотя бы одна из задач двойственной пары не имеет решения. Для завершения доказательства теоремы осталось показать, что возможен случай, когда каждая из пары двойственных задач не имеет допустимых решений. Предоставляем читателю возможность самому построить пример такой пары задач. ш

Доказательство теоремы двойственности было приведено для задачи в стандартном виде. Однако, используя преобразования, указанные в гл. 1, можно от стандартного вида перейти к канони­ ческому, и наоборот.

3.2.Дополняющая нежесткость (Данциг и Орден [44])

Вэтом параграфе будут изучены еще некоторые соотношения между решениями пары двойственных задач линейного програм­ мирования. Следующие две теоремы, называемые обычно теоремами о дополняющей нежесткости, устанавливают эти соотношения между прямой и двойственной задачами.

Прямая задача

Двойственная задача

min сх

max yb

А х ^ Ь

уА с

х > 0

у > 0

76

ГЛ. 3. ДВОЙСТВЕННОСТЬ

Т е о р е м а

о с лаб о й д о п о л н я ю щ е й н е ж е с т к о с т и 1). Пусть зада­

на пара двойственных задач линейного программирования в стан­

дартном виде. Для того чтобы допустимые решения х и у прямой и двойственной задач были оптимальными, необходимо и достаточ­ но, чтобы выполнялись следующие соотношения'.

У [Ах — Ь] = 0,

[с —уА]х = 0.

Д о к а з а т е л ь с т в о . Так как х

и у —допустимые решения,, то

а = у [Ах — Ь].^г0,

Р = [с —у А ]х ^ 0 ,

где а и р суть произведения неотрицательных сомножителей. Более того, a -j-P = —yb + cx ^ 0 .

По теореме двойственности, для того чтобы х и у были опти­ мальными решениями прямой и двойственной задач, необходимо и достаточно, чтобы

— yb + сх = 0.

Следовательно, a + Р = 0, и так как а ^ 0, Р ^ 0, то а = О и Р = 0. Теорема доказана. и

Сл е д с т в и е о д о п о л н я ю щ е й н е ж е с т к о с т и . Дана пара двойствен­

ных задач в стандартном виде. Для того чтобы х и у были решения­ ми прямой и двойственной задач, необходимо и достаточно выпол­ нение соотношений (1), (2), (3) и (4), приводимых ниже.

Перепишем матричное соотношение у [Ах — Ь] = 0 в следую­ щей эквивалентной форме:

Уг [агх — bi\ = 0

(£ = 1,

. . . » пг),

 

или, что то же самое,

 

 

 

 

если г/г>0,

то а;х =

Ьг,

(1)

если агх > Ь г, то г/г =

0. .

(2)

Подобным же образом условие

[с —уА] х = 0 равносильно

сле­

дующим:

 

 

 

 

если c;> yaj,

то Х }

—

0,

(3)

и

 

 

 

 

если x j ^ > 0,

то C j —

y & j .

(4))*

*) Иногда говорят: слабая форма теоремы о дополняющей нежесткости.—

П р и м . р е д .

3.3. ОРТОГОНАЛЬНОСТЬ РЕШЕНИЙ

77

Соотношения (1) — (4) должны быть справедливыми для любой пары оптимальных решений. Может случиться так, что y t = О

и агх = bt одновременно. Следующая теорема подчеркивает, что всегда существует по крайней мере одна пара оптимальных реше­

ний, для которых соотношения уг = 0 и агх = Ьг не могут выпол­ няться одновременно.

Т е о р е м а о с и л ь н о й д о п о л н я ю щ е й н е ж е с т к о с т и . Пусть для

прямой и двойственной задач существуют допустимые решения. Тогда найдется по крайней мере одна пара оптимальных решений х

и у, удовлетворяющая соотношениям

 

 

(Ах —Ь) +

уг >

0,

(5)

(с —уА) +

хг > 0 .

(6)

Д о к а з а т е л ь с т в о . Е с ли обе задачи

обладают

допустимыми

решениями, то параметр t0, фигурирующий в утверждении лем­

мы 3.2, положителен, t0 >

0. Разделив неравенства (4),

(5)

и (6)

из утверждения леммы 3.2

на

t0 и положив х = -^ и

у

*0

,

получим

 

 

tо

 

 

 

 

 

 

 

 

[Ах — Ь ] + У г > 0

И

[с —уА] + х ^>0 .

 

 

 

•Запишем первое неравенство более подробно:

 

 

 

если а;Х—Ьг—0, то у, > 0;

 

 

 

если г/г=0,

то

агх —£>г > 0.

 

 

 

Аналогично для второго неравенства:

 

 

 

если cj = y&j,

то ;г; > 0 ;

 

 

 

если xj = 0,

 

то Cj^>yaj.

 

 

 

Эти соотношения должны выполняться по крайней мере для одной пары оптимальных решений.

3.3. Ортогональность решений (Таккер [193])

Запишем стандартный вид прямой и двойственной задач несколько иным способом. Пусть прямой задачей является следую­ щая:

найти максимум

х0 = aolx1 + а02х2 + . . . + а0пхп (х0 = —z)

78

ГЛ.

3. ДВОЙСТВЕННОСТЬ

 

 

при условиях

 

Ч-filial Ч- •■• 4“ O l n X n

0,

 

Х п\ 1— 0 - ю

 

■Z-n+m=®nj04“ ®ml^l4“ •• • 4“®тп^п^0)

 

 

X i

 

>0.

 

 

 

 

 

 

Тогда двойственной задачей будет такая:

 

 

максимизировать

 

 

 

 

Уо —

— ^loj/n+i — • • • — &тоУп+тп

{Уо —

w )

при условиях

 

 

 

 

 

 

 

У п + i

 

>

0,

 

 

 

Уп+т~^0)

—У \ — aoi ~\~ а п У п + 1 +

• • • Ч~ omiyn+m^Z0,

—

У п — Ооп Ч~ &1пУп+1 Ч-

• • • 4“ а т п У п + т ^~ : 0.

Такую форму записи можно представить таблицей, подобной табл. 3.1, где aoj = —Cj, ai0 = —bt (см. табл. 3.2). В .табл. 3.2

Таблица 3.2

 

1

X i

х 2

 

 

 

1

0

а 01

а 02

■ •.

а 0п

= х0

Уп+1

а 10

а и

а 12

■

а т

“ хп+1

Уп +2

а 20

Й21

 

 

 

—х п+2

Уп+ т

а т 0

ат1

 

•

а т п

—•сп+т

 

— Уо

— г/i

 

 

— Уп

 

на все переменные х и у, кроме х0 и у0, наложено требование неотрицательности.

Пусть

А =

(O-ij)

 

1 ? • • • 1оъ, j 0? Т> • • • >О-),

у (?n+ ti) —_ (1 ,

у п+ j,

у п+ 2 ,

. . ., У п + т )>

у(п+1 ) =

( у 0,

г/!, .

. у

п),

 

3.3.

ОРТОГОНАЛЬНОСТЬ РЕШЕНИЙ

79

Х (™ +1) =

[;Г0,

Xn+i,

. . . , Х п + т \,

 

 

 

Х ( " + 1) = [ 1 , Хь . . . , Хп],

 

 

 

У(т+п+2) =

(1,

г/п+1,

■ ■ ■ , У п + т , У о ,

У и

• • •» У п ) ,

 

•£(т + п + 2) —[x q :

Х п+ \,

• • ■, x n+mi

х и

• • • i х п \'

 

Отсюда следует,

что

 

 

 

 

 

 

 

' Ax<n+1) = x(m+1),

 

(1)

 

 

y(m+l)y^__ —y(n+l)^

(2)

И

y(m+n+2)x(m+n+2) _ y(m+l)x(m+1) _|_ y(n+ 1)х<п+^ =

— y(w+ ОАхОг-ь^ —y C m + ^ = 0.

(3)

Любой вектор x(m+n+2) представляет собой решение прямой задачи, если только компоненты удовлетворяют условию (1); если, кроме того, все его компоненты, за исключением, быть может, х0, неотрицательны, то x<m+”+2> является допустимым решением. Подобным же образом, -y(m+n+2 ) представляет собой

решение двойственной задачи, если только его компоненты удов­ летворяют условию (2); это решение является допустимым, если все компоненты, кроме y oi, неотрицательны. Условие (3) показы­ вает, что каждый вектор х(т+"+2), представляющий собой решение (допустимое или нет) прямой задачи, ортогонален любому вектору у(т+п4-2)^ являющемуся решением (допустимым или нет) двойствен­

ной задачи. Распишем условие (3) более подробно:

y(m+n+2)x(7n+n+2) ~

£0_| х п + \ у п + 1 ~\-

. . . + Х п + т У п + т +

 

 

 

 

 

 

 

 

т-\-п

 

 

 

+

Уо + % iV \ +

• • - + ЭСпУп =

х 0 + Уо + 2

х к У к —

 

 

 

 

т-\-п

 

k = 1

 

 

 

= —Z + W +

 

 

 

 

 

2

xhyh = 0.

 

(4 )

 

 

 

 

h=i

 

 

 

Если

у(т +«+2)

и

х(т+п+2) — допустимые

решения,

то г/ь^О

(& = 1, . . . , п + т)

и xk^s 0 {к =

1,

. . . , п +

т). Поскольку сумма

произведений неотрицательных величин есть величина

неотрица-

 

n-j-m

 

 

 

 

 

 

 

тельная,

2 xhyh^ 0 . Отсюда,

используя (4), получаем

 

 

й = 1

 

m-f-n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Z — W = 2 х к У к ^ 0

и ли Z ^ W ,

(5 )

 

 

 

й = 1

 

 

 

 

 

что является утверждением леммы 3.1.

Пусть теперь у(™+п+2) и x(m+n+2) — оптимальные решения. Не­ обходимым и достаточным условием этого является по теореме

Смотрите также файлы