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

20.1. В В Е Д Е Н И Е

429

Д оказательство. Предположим, что {у, 0) является

гранью

(п' —

1 )-мерное подпространство

и порождена элементами t £ Т,

то она должна содержать п' —

1 линейно независимых точек t £ Т .

Для каждого

из

этих

векторов

t1 (i =

1, . .

п' — 1 ) справед­

ливо’

=

0 - гДе

= l*‘(Ы.

t% (82)1

• • ■>

(#«-)]•

Так

как

Y (g) >

0 , f(g)

>

0

и

(ё) 1 (ё) = °>

т 0

либ° 7

(ё) >

0 влечет

t (g) =

0,

либо t (g) >

0 влечет у (g)^= 0. Это справедливо для

каждого из

векторов

t*. Если t1 (g) = 0 при

всех

i (i = 1, . . .

. . ., п' —

1 ) для более чем одного элемента g, то это будет про­

тиворечить

тому,

что

п' — 1

векторов

t*

имеют

ранг п' — 1 .

Н о если у вектора

t =

U Ы ,

t (g2), . . ., t (gw)1

все компоненты положительны, то, для того чтобы

2 7

(§) * (ё) =

.= 0, у (g) должно

быть равно 0 для всех g 6

Л- Таким образом,

кроме случая у (g) =

0

для всех g 6 т) единственной возможностью

является у (h) >

0

и

у (g) =

0 для всех g 6

г), g ф к .

Это

дает

7 (/t)t(h)+

2

7 (ё) t (ё) = 0

или 7 W

t W

=

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

что t (h) =

0 — грань, упоминаемая

в

теореме.

М ы

показали, что условие t (h) ^

0 дает единственно возмож­

ника Р

(G, т), ёо) тогда и только тогда, когда элемент g0 л е жи т

в подгруппе

_д, порожденной элементами

т]—

h.

Если

g0 (J

$ G'n-h,

то

грань задается условием t (К) ^

р >

0.

Здесь

р —

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

Е с л и

g0(£G^-h,

то

не

существует

решения

группового соотношения

2 t(g)-g=g0

■с

t(h) = 0.

Следовательно, t(h)^0

не

является гранью. Если

go £

то имеем

представление

2

Нё)-ё=ёо,

0 s^t(g)<s{g).

(8 )

g£r|-ft

К

вектору

t, удовлетворяющему соотношению (8 ), можно доба­

вить п’ —

1

единичных векторов s (g) u (g) для каждого g £ р — h,

чтобы образовать п’ — 1

независимых

решений с t (h) —

0. Сле­

довательно,

t (h)

0

является гранью.

Если

g0

$ G'^-h и

поскольку

G^-h

разбивает G на

смежные

классы,

если Р (G,

г|, g0) не пуст,

то

g0

принадлежит одному

430

ГЛ .

20. ГРА Н И Ц ЕЛ О Ч И С Л Е Н Н О ГО М Н ОГО ГРА Н Н И КА

из смежных

классов. Эти смежные

классы имеют вид ph +

и м ы

можем

выбрать для каждого

смежного класса наименьшее

единичных

векторов u (g),

g £ ц —

h. Поскольку не

существует

выражения

для g0 при t (К) < р,

неравенство t (h) ^

р выпол­

няется для всех t £ Т. а

В гл. 19 м ы ввели граф Н

(G, т), с), где с —

дуговые стоимости*

и стремились найти кратчайший путь от 0

до g0.

Сейчас мы

мизации

(3) с общей длиной у (g) t (g) = у0Если у (g) выбрано

так, что имеется п' линейно независимых кратчайших путей от 0

до g0l то

(у, уо) является гранью многогранника Р (G , ц, g0)-

Граф Н

(G, тр

go) для

циклической

группы из 4 элементов

0 , gi, g2 , g3 и

г| =

{gu g2} показан на

рис. 2 0 .1 .

Любой

из

стандартных

алгоритмов

поиска кратчайшей цепи

содержит

t (g)

дуг, соответствующих g, то имеем решение t =

= \.t(g)] (g G ц)

задачи групповой минимизации

с целевой

функ­

цией 2

у (g) t (g). Очевидно, каждое решение

определяет

много

гел

ведлив в графе Н

(G , т], у) и м ы сформулируем его в виде леммы.-

Лемма

20.1.

Пусть Р* — кратчайший

путь

от

0

до g0

и t— соответствующее ему

решение.

Если

V — любой

неотри­

цательный

целочисленный

вектор,

такой,

что

t'(g) ^

t(g)

20.1. В В Е Д Е Н И Е

431

u J t'(g) g — h, то

любой

путь, начинающийся

в N g и кончаю-

гев

t (g), является крат ­

щийся в N g+h, соответствующий решению

чайшим путем от N g к N g+h.

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

Поскольку t' (g) ^

t (g),

то путь, соот­

ветствующий [t' (g)], есть

подпуть кратчайшего

пути, соответ­

ствующего

[t (#)].

Если существует путь от N g к iVg+;i, соответ­

ствующий

[Е (#)],

который

короче, чем [t' (#)], то путь, соответ­

ствующий

\t" (g) +

t (g) —

t' (£)], должен

быть путем от 0 до g0

Когда

м ы рассматриваем грани многогранника Р

(G, р, g0),

которые могут быть записаны как 2

Y (§) t (8) ^

Yo или (y > Yo)r

веч

Н

(G, р,

у)-

Представим

удобно рассуждать в терминах графа

у (g)

как

длину дуги,

соответствующей

g. Используя

это, мы

можем

охарактеризовать

грань Р (G, р, g0) в графе

Н

(G, р у).

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

Поскольку (у, у0)— грань, такая, что

у0 >

> 0, существует п'

линейно независимых векторов И, для

кото­

рых

уС = YoДля всех других t, удовлетворяющих соотношению

2

t(g)‘g —

8oi имеем

y t ^ -Уо-

Итак, каждый

из

векторов

И

_

g0.

представляет

собой кратчайший

путь от 0 до

Если

все

t*(I = 1 , . . ., п') имеют

f (g) —

0 для некоторого g, то t* не бу­

* (g) >

20.4.

Если (у,

у0), Yo >

0, является гранью, то

Т е о р е м а

У (g) —

длина кратчайшего пути

от 0

до g0.

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

По лемме 20.2 существует кратчайший путь

от 0 до g0с t (g) ^

1.

Пусть t —

решение, соответствующее

крат­

чайшему пути из 0

к

и пусть

и (g) вектор

t' из леммы

2 0 .1 .

Тогда

этот

путь,

состоящий

из

одной

дуги

(соответствующей

u (g)),

является подпутем кратчайшего

пути

t; следовательно,

432

ГЛ . 20. ГРА Н И Ц ЕЛ О Ч И С Л Е Н Н О ГО М Н ОГОГРАННИКА

Следствие

20.1. Если

gi

и g 2 оба принадлежат г| и g = gi +

+ g t

, то у (#) <

у (

gi) +

у ( g z

) .

■

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

Решение t

(gi) —

1 и t (g2) = 1 обеспечивает

путь

к

g длины

у (gi) +

у (g2). Н о

у (g) —

‘длина кратчайшего

пути

к

g. Следовательно,

у (g) <

у (gt) +

у (g2).

Следствие

20.2. Если gi и g2 оба принадлежат т] и gi + g2 =

= go, то у (gi) +

у (g2) =

у0.

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

По лемме 20.2. существует кратчайший путь

от 0

к g0, такой, что t (gi) >

0. Пусть таким решением будет t.

Тогда

t (gi) = 1

—

подпуть

кратчайшего

пути

от 0 к gQ. Если

gi +

gi '= go, то

g2 = go —

gi-

Н о

м ы знаем,

что

или

Y-t =

Yo

Y [«

+

Y [t —

и Ы ]

=

yo,

или

при условии

2

g-t(g) = h •

(l)

Тогда ф 8 (h) удовлетворяет

рекуррентному соотношению

Фв(h) — min{tps-g(h), tys(h — g) + y(g)}..

(2 )

рекуррентным

алгоритмом,

чтобы

найти

у (g)

Для

всех

g 6 Т

Как и прежде,

определим ф 0 (g) = 0 0

>

1 =

Yo и

ф 0 (0)=

0.

Пред­

положим, что

м ы знаем y(g)

для всех g£S.

Тогда следующие

три шага дадут y(g) для gfr\VLg$S.

_

(1) Найдем

значения т г, для

которых ф« (go— m tg) <

1.

Если

таких значений нет, положим

y(g) = 0

и

перейдем

к

нахожде-1

нию у (g), где g <£S U S'* Если существуют значения m t(i=

1, ..., q),

для которых ф в(go— m tg) ■< 1 , то полагаем

у (g) = max [ 1

—

ф„ (gQ—

mig)]/mi.

( 3 )