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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

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

строками задаются матрицей1)

ЧГ

.3 4J ’

то при проверке получаем2)

_

«1 =

«5 =

а 7 =

Г1 1] в -1 =

1

г

1

- 0 ‘

_3

4_

“

_ 3 .

ч

Г

" 2 "

 

 

. =

_3

4_

_ 3 _

1

Г

_2 “

 

 

==

_3

4_

0

"1 г

Г 4

21

Ч

2"

 

_3 4

'со

0_1il

0 0

- 0 -

" 3 "

___

1

г - 0 "

,

аз =

L3

4

_ 0 _

0

0

 

~ 5 ~ ,

а 6 =

1

Г

“4" =

"1 "

0

 

_3 4_ _ 3 _

_ 0 _

’ 2 "

Ро =

ч

Г

" 0 1

“3 “

»

 

 

—

Ч )

0_

 

_3

4

_ 3 _

и мы снова приходим к (29). Следовательно,

элементы

группы

имеют вид

 

 

 

 

 

 

 

 

 

 

 

 

So

 

S i

Sz

S 3

 

S i

Sr>

 

 

 

 

a 3

 

a 6

a 7

cc4

 

 

a 5

 

 

Относительными стоимостями векторов сс7 являются

 

 

21,

с* = 30,

с*= 1,

ф

И ,

с* = 3.

 

Мы

хотим

минимизировать

2 cfxj

(7 =

1, 3,

5, 6 ,

7) при

условии

(29)

 

 

 

 

 

 

 

 

 

 

■3\

/ 0 \

 

/ 5 \

/1

*,+|о)*’”(о) Н и

к о ) Х '

+ [ о } Х

з +

[ о } Х л

+ \ 0

Воспользуемся рекуррентным соотношением

 

 

 

 

Ifs (У) =

mill {Aps-i (у), яре (у —сс8) + с?}.

 

 

Начинаем с а 5, поскольку его стоимость равна 1,

т. е. наимень­

шая, а порядок

равен 6 :

 

 

 

 

 

 

 

 

 

 

 

 

% (0 ) = о

 

 

 

 

 

 

% (a 8) =

i|3i( й ) = m in { o o ,

ip i(0) + 1 } =

1,

 

 

tyi (2 а 5) =

лр! (g-4) = m in {сю,

^

(g5) +

1} =

2,

 

О См. сноску

на

стр. 408.— Прим. ред.

 

 

 

 

2) Элементы всех фигурирующих здесь матриц взяты по mod 6 .— Прим,

перев.

19.2.

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

411

Ф1 (Зсе5) =

гр4 (g3) =

min { оо,

(g4)

+

1} == 3,

Ф1 (4а5) =

Ф1

Ы =

min {оо,

opj (g3)

+

1} =

4,

Ф1 (5сс5) =

гр4

(gi) =

min {оо,

гр4 (gz) +

1} =

5.

Затем мы начинаем с сс7, так

как его стоимость равна 3,

т. е.

наименьшая из оставшихся:

 

 

 

 

 

Фг (а7) =

гр2 (g2) —min {гр4 (g2),

ф2(0) +

3} = m in {4,

3}

= 3 ,

ip2(2ct7) =

ip2{g'4)= m m {ip 1(g-4),

гр2 (gz) +

3} = min {2,

3 +

3} =

2,

фг (3cc7) =

ф2 (0) = min {гр! (0),

ф2 (g4) +

3} = min {0,

2 +

3} =

0.

Поскольку порядок a 7 или g2 равен 3

и делит 6,

мы

должны

взять некоторую другую начальную точку, чтобы получить гр2' ( g )

для всех g .

Начнем с g

t :

 

 

 

 

 

 

 

<|iifei) =

t i (gi) = 5,

 

 

 

 

 

 

 

 

^ 2 ( £ 1 +

^ ) = гр2 (£з) = т т { 1р1 (£з),

1р;(^) +

3} = т т { 3 ,5 +

3} = 3,

Фг (#з +

gz) —Ф2 (gs) = min {гр! (g&),

ф;(Ы +

3} = m in{l, 3 +

3 }= 1 ,

Ф ^ з + ^ Н Ф г Ы ^ т п ^ ф Д ^ ),

Ф2 iSb) + 3} = min {5, 1 + 3 } = 4.

Заметим, что тр^ (ё'ь) не использует

g 2 .

Вычисляем ф ^^);

оно

не совпадает с ip'(gi), которое равно 5. Поэтому

 

 

Ф2 (gi +

gz) = Ф2 (gs) = min {ipi (g3),

ip" (gO +

3} = min {3, 4 + 3} =

3.

Заметим

теперь,

что ф2 (ё'з) = ф2 (g3) и вычисления заканчиваются.

В следующей

таблице приведены

результаты вычислений1):

 

 

 

 

go

gl

gi

g3

gi

g&

 

 

 

 

 

ip;

0

5

3

3

2

1

 

 

 

 

 

гр;

0

4

3

3

2

1

 

 

 

 

 

 

 

a 7

oc7

a 5

a 5

a5

 

 

Для любого gte{go, g1, • •

g5} получаем равенство фД#) =

Ф2 (g),

обусловленное относительно

высокими

стоимостями оц, а 3

и сс6.

Так как

 

 

 

 

 

 

 

 

 

 

и совпадает с g 3,

мы долж ны использовать а 5 по

меньш ей

мере

оди н раз. Д елая

обратное построение, получаем

я 5 = 3,

а все

г) Последняя строка здесь заполняется аналогично строкам г в табл. 19.1, т. е. в соответствии с (25), с той разницей, что вместо номеров i указываются соответствующие векторы а г,— Прим, перев.

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

другие небазисные переменные равны О,

 

 

 

 

хв = В-1 (b —Nx_v) =

 

 

 

 

 

 

 

“ 4

2“

/ "41‘

'

г

“ 4

2~

’38’

"42~

6

6

6

6

 

 

 

— О

1_ Г

 

 

50

 

—

0

47

-

1

0

.19.

_ 6

U_

 

 

 

_6

 

 

 

Следовательно, оптимальным целочисленным решением

является

х2 = 42,

а:4 =

19, х5 — 3,

 

 

 

 

 

 

 

а остальные переменные равны 0.

При решении задачи групповой минимизации полезно рас­

смотреть граф Н (G, г|,

с).

Граф имеет | G | вершин, по одной вер­

 

 

 

 

шине N (g) для каждого g d G. Если

 

 

 

 

g' £ т], то существует

ориентирован­

 

 

 

 

ная

дуга

из

N (g)

к

N (g + g')-

 

 

 

 

Стоимость

этой

направленной

дуги

 

 

 

 

равна с (g'). На рис.

19.3

изображен

 

 

 

 

граф Н (G, т], с)

для-

случая,

когда

 

 

 

 

G — циклическая группа порядка 6Г

 

 

 

 

11 =

(§U # 2 ,

ёз),

С =

(П/6, 4/6,

21/ в)~

 

 

 

 

Некоторые дуги,

соответствующие g 3r

 

 

 

 

не изображены.

 

 

 

 

 

 

 

 

Задачу групповой минимизации (7}

 

 

 

 

можно

интерпретировать как задачу

 

 

 

 

нахождения пути минимальной стои­

 

 

 

 

мости

или

кратчайшего

пути

от О

 

 

 

 

к N

(g0) в графе Н (G, т),

с). Рассмот­

 

 

 

 

рим численный пример:

 

 

 

 

 

 

 

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

 

 

 

z

= 2xi

+

х2 + х3 +

Зхь +

х5

 

 

 

при условии

 

 

 

 

 

 

 

 

 

 

 

 

2х2 -\г

хз +

Axi

-f- 2х 5 +

ха =

41,

 

 

 

(30^

3a:i — Ах 2 + Ах3 +

 

xt

—

х5

х-,

=

47,

 

 

 

 

хj

0

(целые)

(/ =

1,

. .

.,

7).

 

 

 

Заметим, что эта задача почти такая же, как (27).

Оптимальным базисом соответствующей задачи линейного программирования является

'0 2“

3 - 4

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

413

а оптимальной таблицей соответствующей задачи линейного про­

граммирования

является табл. 19.2.

 

 

 

 

 

 

 

 

Таблица Ь.9.2

 

 

 

 

1

 

хг

*3

Ч

Ч

хв

х7

константы

Z

1

0

0

21/6

5

2

11/6

4/6

639/6

Ч

0

1

0

2

3

1

4/6

2/6

43

 

х г

0

0

1

3/6

2

1

3/6

0

123/6

 

 

 

 

Таблица 19.3

 

 

 

 

 

От 0 до g0

Стоимость

Решение

 

 

 

пути

 

 

t

 

 

 

 

 

 

 

 

 

 

 

 

б

 

 

0

 

 

 

0

 

 

 

 

1

 

 

11/6

<1 =

1

 

 

 

 

 

2

 

 

4/6

£l =

l

^2 == 1

 

 

 

 

3

 

 

15/6

t%= l

 

 

 

 

4

 

 

8/6

 

 

=== 2

 

 

 

 

5

 

 

19/6

t l ~

1

^2 “ ^

 

Ясно, что / (а4) =

/

(а5)

= 0 ,

поскольку все

компоненты век­

торов aj и а5 целочисленные.

 

 

 

 

 

 

Вычисления,

подобные

проведенным для задачи (27), дадут

/

(а3) =

gz,

/

(а6)

=

gi

и

/

(а7) =

g2.

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

Решением

задачи

целочисленного

программирования

является

( х в, Хд-) с

х в =

В _1Ь — B^Nxjy.

Мы показали, что

решение

•состоит из двух частей и что вторая часть является периодической

поправкой. Из соответствия

=

хв, t2 =

х7 получаем периодиче­

ские поправки для всех возможных Ь.

 

 

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

 

 

 

 

 

 

0 0 0 0

0, если / (Ь) =

0;

 

 

0 0 0 1

0,если / (b) =

gt;

Хлг = (*з. ж4, х5, х6, х7) =

•

0 0 0 0

1,если / (b) =

g2;

0 0 0 1

1,если / (Ь) = g3;

 

 

0 0 0 0

2,если / (b) =

g4;

 

 

0 0 0 1

2, если /

(b)g5.

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