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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

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

401

Следовательно, объединяя (18) и (19), получаем рекуррентное соотношение

■ф(5, й) = min {яр (S —

h ) , c*^') + ^ (5 . h ~ #')}•

(20)

Это рекуррентное соотношение позволяет вычислить of) (S , h) для всех S s p и каждого h £ G. Чтобы упростить вычисления, будем решать численные примеры, используя только переменные х}-. В гл. 20 мы изучим грани многогранника Р (G, rj, g0) и обсудим их в терминах t-пространства.

Пусть

 

S

 

ярз (у) = min 2

c1xi

при условии

1 = 1

 

 

 

2 ОijX j

= у (mod 1),

l=i

 

 

Xj == 0 (mod 1 ),

x j^ :0

(у = 1 , . .., s).

Иными словами, яр8 (у) —оптимальное

значение в

случае,

когда

только

первые s

столбцов

a j

могут

участвовать

в образовании

столбца

у. При

подсчете

яр3 (у)

либо

а 3 не используется,

либо

используется по меньшей мере один раз. Отсюда получаем рекур­ рентное соотношение, аналогичное соотношению (2 0 ):

'ts(y)==min{i|is_i(y),

яр8 (у —as)-f с?}.

(2 1 )

Это рекуррентное соотношение позволяет вычислить яр8 (у) для

всех s, i^Zs^Zn', и у, начиная с

ips (0 ) = 0 и яро (у) =

+ 00 > при

условии, что вся группа порождается as1). Если as порождает всю группу, то для любого у выполняется y = r a s, l^ r ^ /i',

иможно образовать разность у — as, требуемую в (2 $). Рассмотрим численный пример (см. [6 ]):

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

 

 

 

 

 

при условии

z — — 4х3 —5х4

 

 

 

 

 

 

 

 

Зх3— х4 -}-х8

 

= — 2,

 

— х3 —4х4

+ х 4

= — 5 ,

 

— Зх3 — 2х4

+ х2= - 7 ,

^ ;

XJ^

0 (целые)

(; = 1,

. . . ,

5).

 

я) То есть когда^

группа (а ) — циклическая;

случай когда

(а ) не

является циклической,

рассматривается далее.— Прим. ред.

 

26 т. Ху

402 ГЛ . 19. Л И Н Е Й Н О Е И Ц Е Л О Ч И С Л Е Н Н О Е ПРОГРАМ М ИРОВАН ИЕ

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

 

3

- 1

1

В =

1

- 4

0

 

3

- 2

0

с | de.t В | = 10. Применяя преобразование

2

4 “

10

10

3

1

10

10

3

И

10

10_

кограничениям задачи (2 2 ), получаем

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

при условии

0, 7 = 1, . .., 5.

Следовательно, мы стремимся минимизировать

при

условии

 

 

 

 

 

 

 

 

 

 

 

 

(mod 1 ).

(23)

 

 

 

£ i > 0

,

;r2 >

0 .

 

Так

как я(з3 (0) = 0,

то

по (21)

получаем:

 

 

i|?i(а1) =

с*,

т|11 (2 а 1) =

2с*,

% (ЭаО =

9с*

 

 

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

403

и для

каждого гщ (г =

1,

D — 1) получаем rctj = ta2 (mod 1).

Например,

otj = 7се2 (mod 1 ), 2 a t =

4a2 (mod 1 ) и т. д.

 

Чтобы воспользоваться соотношением

 

 

 

 

 

'M y) = m in{iM y),

Ы У ~ а2) +

4 ) ,

(24)

надо

знать

г[з2(у —се2).

Единственное

яр2 (у),

которое

известно

к настоящему моменту,

это

(0) = 0.

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

мы начи­

наем с

 

 

 

 

 

 

 

 

 

 

ifo (a2) =

min {тр! (а2),

ф2 (а2 —« 2) +

с*} =

 

 

 

=

min{T|)1 (3a1),

ф2 (0) + с|} х) =

 

 

 

 

.

г 21

 

 

11

 

 

 

 

=

m m

{ т о

 

 

10 •

 

 

Вычислив т^2 (ос2), получаем

 

 

 

 

 

 

 

Фг(2 ое2) =

min {alij (2 a2),

я|?2 (2 a 2 —a2) + c|} =

 

 

 

= m in{\|31(6 a 1),

ф2 (a 2) + c*} =

 

 

 

 

.

r 42

11 ,

11 a

22

 

 

 

 

— nun j 10,

10 +

10j — 10-

 

 

Этот процесс можно продолжать до тех пор, пока не будет вычис­ лено ф2 ((D — 1) ос2). Чтобы восстановить значения Xj, образующие текущее ф8 (у), необходимо помнить индекс г, указывающий послед­

нюю переменную, получившую значение единица:

i { s — 1 , у),

если

a|is- i( y ) <

a|is (у —a s) +

c?,

4 s , У) =

если

a|3s_! (у) >

% (у —а $) +

(25)

s,

с%.

Вычисления сведены в табл. 19.1, где ф3 (у) выписаны для

всех 1 < s < 2 h у ( {а}. Заметим, что в строке ф! (у) мы произ­

водим вычисления слева направо, а в строке ф2 (у) сначала вычис­

ляется элемент в третьем столбце, а затем — в шестом столбце. Заметим, что после того, как последние две строки вычислены, первые две строки можно отбросить. Это сэкономит большой объем памяти вычислительной машины.

Преимущество этого алгоритма состоит в том, что, построив один раз таблицу, аналогичную табл. 19.1, можно решать задачу целочисленного программирования (2 2 ) с любым вектором правой части Ь. Например, если правая часть равна [—6 , —7, —8 ], то

В - 1 [ - 6 , - 7 , - 8 ] = [Н , 1013

’ й]!

 

 

Г 18 13 _7ч _

Г 8_ _3_

= 3a2

= Octj (mod 1 ).

L1 0 ’

1 0 ’ 10.1 ~

L10 ’

10

 

 

!) Ведь « 2 =

3a! (mod 1).— Прим. ред.

 

 

26*

404 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

 

Таблица 19.1

нулевой столбец 1

| третий столбец

V

1

s

0

а4= 7а2

2а1 = 4а2

3ai = a2

4а! = 8а2

 

 

 

 

 

тр1 (у)

0

+7/10

+14/10

+21/10

+28/10

i

—

1

1

1

1

1р2 (У)

0

+7/10

+14/10

+11/10

+18/10

i

 

1

1

2

2

S

5а4 = 5а2

6ai = 2а2

7а4 = 9а2

8ai = 6a2

9at = 3a2

 

 

 

 

 

ti(y )

+35/10

+42/10

+49/10

+56/10

+63/10

i

1

1

1

1

1

l|>2 (У)

+25/10

+22/10

' +29/10

i

2 .

2

2

+

О

+33/10

2

| шестой столбец

Это означает,

что #t = 0,

х2 = 3 и оптимальным решением является

#з = 3, £ 4 = 1, # 5 = 4, #1 = 0 , #2 = 3.

 

 

 

 

Рассмотрим теперь случай, когда a s

имеет порядок d, который

делит D

( й ф Б ) . В

этом случае ctocs = 0

и не все элементы груп­

пы {а}

будут

получены.

Пусть у —элемент,

не полученный при

вычислениях.

Тогда

(у)

не известно.

Предположим,

предвари­

тельно,

что тр; (у) =

тр3- 1

(у). Тогда мы

получим i^(y)

как пред­

варительное значение i|is (у):

 

 

 

 

^

(У + ras) = min

 

(у + ras—ots) + cf,

(у + ros)}

(26)

 

 

 

 

{r = 1 , • • •, d).

 

 

 

 

После d шагов -das= 0, так_что мы получим +s (у ■- das), которое может отличаться от i^-iCy)- Используем это, чтобы вычислить

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