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

19.2. АСИМПТОТИЧЕСКИЙ АЛГОРИТМ

391

Поэтому полагаем Xj = 0, если либо /

(аг)

= / (аj) Ф 0

< Cj\

либо / (аг) = / (а;) Ф 0", сг = с,-, a i <

/;

либо / (а,-) = 0.

Тогда

t( g ) = Xi,

если f (a i) =

g 1).

(8 6 )

Точка х = [хв, х^] c x j =

B -1 b, х^ =

0 соответствует началу

координат

в х^-пространстве

и началу

координат в тг'-мерном

t-пространстве. Часть х-пространства, в

которой

x N ^ 0, соот­

ветствует

первому (неотрицательному) ортанту в

t-пространстве

(рис. 19.1

(б)).

обведены

на рис. 19.1(6) кружками.

Точка х' из С дает точку

(хв, x N).

Точка х' — целочисленная

тогда и только тогда, когда

х) Соответствие между xjy и

t

более точно описывается

следующим

образом.

Пусть

Jg = {/ | / (а7-) = g},

a /(g ) —такой элемент из Jg, что если

i £ J g и i= £ /(g),

то либо с д ^ < с г,

либо

cj(g) = Cj и /(g) < i . Тогда:

(а) с каждым решением х.у задачи (5) сопоставим решение t

задачи (7),

П

полагая

t ( g ) =

2

хл

еслп £ Oi;

легко

видеть, что при этом

^

cjxj >

j £ J g

3 = 1

>

2 c* ( s ) - t (г);

_

__

_

g£ri

задачи

(5):

(б) с каждым решением t задачи (7)

сопоставим решение хдг (t)

полагая:

~

уtj ~

\

7(g),

если / = /(g )

при некотором g £ гр

Xj

S

0

в противном случае.

[

Очевидно,

п

2 ф } =

2 с (g)-'t(g)-

j=i

ген

2) Точнее,

подмножеству

из С, в котором часть переменных xj = 0

в соответствии

с (8).— Прим.

ред.

Р А В,

N,

Ь).

Соответствующий многогранник

в

t-пространстве обозначается

P(G,

У],

g0).

Многогранники Рх>(В, N, Ь) и

Р (G, т], g0) показаны на рис. 19.1(a)

и (б). Эти многогранники по

существу одинаковы, и мы будем

ника Р (G, т|, g0),

и если / (а;) = / (аг) = g (i ф

j), то либо x t =

= 0, либо хj = 0.

Из вершины в t-пространстве

можно получить

всех других небазисных переменных x t с / (аг)

=

/ (а^) =

g. Тем

самым устанавливается соответствие между

t (g)

и x N,

и тогда

хв однозначно определяется соотношением

хв

=

В -1 (Ь — Nxw).

Т еорема

19.5.

Каждая

вершина многогранника Р (G,

ц, gn)

неприводима.

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

Будем доказывать

эту теорему от против­

ного. Пусть v — вершина многогранника

Р (G, ц, gn);

предполо­

жим,

что v

= (t (g)), g

6 Т

приводима,

т. е. имеются целые числа

г (g)

и г'

(g),

такие, что

О < r ( g ) ^ t ( g ) ,

0 < г '(* )< * (* ),

г (g)

ф г' (g)

для некоторого g и

2

г (§■)£= 2

^' (g)g-

g£B

g£B

Так

как v —точка многогранника P(G,

г), g0), то

go= 2

H g ) g - 2

r(g)g + ^ r '

( g ) g =

2

(*(£) — r (g) +

r’ (g))-g

и

гев

££в

я£в

g£B

2 ( H i ) —r‘ (g)+r(g))-g.

go== 2 t ( g ) - g + 2 r(g) - g— 2 r ' { g ) - g=

g£n

e£B

g£B

g£B

По предположению

t (g) — r (g)

^

0 и

t (g) — r' (g) ^

0.

Следо­

вательно,

векторы

\±

= (t (g) — r

(g)

+

r' (g)),

g 6 t), и

v 2 =

= (t

(g) — r' (g) +

г (g)),

имеют

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

цело­

численные

компоненты

и

удовлетворяют системе (6 ). Поэтому

vt и v 2

принадлежат Р (G,

ц, g0). Но v

= (vt +

v a)/2.

Это про­

тиворечит предположению,

что v — вершина Р (G, ц,

ga).

Итак,

каждая вершина Р (G,

ц, g0) неприводима.