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

Скачать файл (16,20Мб)

Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

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

405

последовательно г|з8 (у -[- ras) при

разных г 1).

Как

только

одно

из

значений

т|/8 (у +

га8) совпадает с

соответствующим значением

■ф6'(у +

га5), вычисления прекращаются.

Эта процедура повторяется

для

{Did) — 1

начальных

точек

у,

чтобы

получить

все

(у),

У € {«}.

Мы покажем, что

(1 ) вычисления закончатся после

q шагов,

где d ^ .q ^ 2 d ;

(2 )

значения

(у + ras)

равны

точности

значениям

(У +

га8).

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

Полагая, что я|)8(у) = ips-i (У)> можно только

оценить i|5s (у) сверху. Возможны

два случая.

1 . ips (у +

ras) =

tys-i (у -(- ras) для некоторого г,

тогда

Vs{y + 9«s) = % (y + qas) 2)

( d > g > r ) ,

и далее

tys{y+qas) =

'tys{y +

qas)

(g =

. . . , г ) .

Если

ij>s (у +

rces) ^4= ifs-!(у +

ras)

для всех г =

. . . ,

d, это

влечет за собой

для всех г

tys (у + ras) = 1|>„ (у + ras—a s) +

с*.

Но

(у) =

(У + das) =

(У +

{d— 1) 0£s) + с* =

= 'фв (у + {d — 2 ) a s) + 2 c? =

= •

• • =tys{y) +

dcf.

Если cf Ф 0, получается противоречие. Если c* = 0, то предпо ложим, что у — элемент, который не может быть получен с использо

ванием только a s. Пусть yi-t-ras =						y, где
			_	s-i _
			У1 — S a jX j и
				i=l
!)	При	этом	предполагается,		что	г\|>£ (y) =	i\|)'(y-\|- das).—Прим, перев.
2)	Для	указанного г справедливо i\|)s(y + ras) =i\|)s(y+ ras);						поэтому для
последующих значений г				правая	часть (26) превращается в выражение для
\p8(y + ra s).		При	доказательстве		утверждения		о тр" имеется	в виду, что

№ { y + q a s) = mm BK(y + (g— l)o s).+ c*,^s_i(y + qas)}.

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

Тогда, поскольку			cj = 0, то
			Ы	= г\|з8 (yi + ras),
ИЛИ Ips-i (y0 =		ll3s (yi) ДЛЯ некоторого У! В группе, ИЛИ			(у + rcts) =
=	(У + r c £ s )	Д л я	некоторого	а это приводит к первому
случаю.

Определим элемент группы, который является образом данного небазисного столбца при отображении <j>B_1. Это можно сделать двумя способами. При первом способе мы хотим получить группу {А }/{В }, приводя В к нормальной форме Смита. Известно, что существуют невырожденные унимодулярные матрицы Р и Q, такие, что

PBQ = S,

где S — нормальная форма Смита. Матрицы Р и Q соответствуют операциям над строками и столбцами. Если группа G является прямой сумной к циклических групп, то нормальной формой Смита будет

	" 1 .		о "
	0	'	ek _
где е1 -8 а- . . . •	гк = D.	над строками действуют над В и N,
Заметим, что	операции	над строками действуют над В и N,

а операции над столбцами действуют только над В. Итак, когда В приводится к S, N переходит в PN. Факторгруппа {А }/{В } полу чается вычитанием столбцов S из PN.

Итак, первые т — к компонент каждого небазисного столбца будут равны 0 по модулю 1 * а г-я компонента (£ > т — к) может

принимать одно	из	следующих	значений:
0 ,	1 ,	. . . , г ^ т + к — 1	(mod ег_т+й).

Так мы находим образ каждого небазисного вектор-столбца. Второй способ состоит в нахождении группы {В -1 }/{1}. Так

как первая часть асимптотического целочисленного алгоритма предполагает решение задачи целочисленного программирования как задачи линейного программирования, то В - 1 А = [I, B _1 N]

при окончании симплексных вычислений. Если взять дробные части B -1 N, то они представляют собой элементы группы с опера

цией сложения по модулю 1 (если каждый элемент B _1N записы вается как h/D, то мы можем рассматривать лишь числители h, но с операцией сложения по модулю D). Обозначим матрицу,

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

407

обратную к S, через S

тогда

Отсюда следует, что существуют невырожденные унимодулярные матрицы Q- 1 и Р -1, такие, что Q_1 B _1 P _1 = S -1, где -Q- 1

соответствует операциям над строками, а Р -1— операциям над столбцами. При втором способе нахождения образов небазисных столбцов мы начинаем с [В-1, B -1 N]. Затем, применяя Q- 1 и Р '1,

получаем

[Q-iB-ip-i, Q-iB_1N] = [S'1,				Q_1B_1N].
Если взять дробную часть		Q_1 B _1 N, то элементы первых т — к
строк будут равны 0 , a		i-e компоненты ( i > т — к) столбцов
матрицы Q-1 B -1N будут принимать одно из следующих значений:
	ei-m+h '	ei-m+fc	’	Bi-m+h
Так мы находим образ каждого небазисного столбца.
Рассмотрим численный пример:
максимизировать
				1
	z = х1 -f- 2х%+ З.г3 + xk+ хъ-)- -g-x-j
при условии
X i	Т - 4 х % ~Ь 2^4 -f- Х с, - \ - х §				= 4 1 ,
					(27)
4^1	3^2 -(— Х з —■4 x i		— х §	х	j = 47,
	(целые)		( /= 1 ,	. . . ,	7).

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

"0 2 1

с | det В

| =

1! н•

-2

	.3 —4J
1 “	“ 2	1 -
3	3	3
,	свВ 1 — (2, 1) 1
° -	_~2

408

ГЛ . 19.

Л И Н Е Й Н О Е

И Ц Е Л О Ч И С Л Е Н Н О Е

ПРОГРАМ М ИРОВАН ИЕ

Вычислим (свВ

—cN):

' l l

/ 1

«■ -(t - t H D - 6 '

- -

( т .

4 )

( } ) - " .

_ / 1 1

’

2 \

/ 1 \ _11

z<3— I 6

з )

\ о ) ~ 7Г

z, = (т-4 )(П-

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

целевая функция m inc*^ в задаче (7)

прини

мает

вид

m in z= -f- (21/6)

-f- (30/6) x %

(1/6) ж5

(11/6) ж6 -j- (3/6) x-t.

(28)

Существуют два пути получения отношения сравнения 2

a ixi =

= Po(modl). Выпишем матрицу

[В, N,

b, I]

задачи (27),

где

единичная матрица справа служит только для проверки1):

1 4

1 1

41“ " 1

0 "

.3 - 4 4 1 — 1 0

1 47. . 0

.1 .

ь1? Ь' =

Ь4+ Ь2. Получаем

“О

1 4 -

1 1

41'

" 1

0 "

3 - 1

4 1 - 1 0

1 47_ . 0

1 .

Пусть Ь" = Ь' + ЗЬ', Ь" = Ъ'2. Получаем

2 1

1 0

41 " " 1 0 "

О - 1

4 1

- 1

47 _ . 0

1 _

Пусть е( = е!,

е2 =

—2ei +

e2,

т. е. добавим дважды 2-ю строку

к 1-й строке,

и пусть Ь"' =

—Ь2. Тогда получаем

' 6

— 1

135"

" 1

2 "

О 1 4 1

- 1

47 . . 0

1 -

Теперь

мы имеем

базис В'

диагональной форме

все

взять

по

mod ( ! )

•

Например,

(I)-

векторы

надо

( o ) ( mo d ( i ) )

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

мы должны решить

(оЬМо)МоЬЧоЬЧоЬНШтоаШЬ

(29)

х) При такой форме записи преобразования над единичной матрицей соответствуют преобразованиям над строками из А в процессе приведения В к нормальной форме Смита.— Прим. ред.

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

409

Заметим для проверки:

Итак, мы должны решить задачу целочисленного программирова ния (28), (29).

Заметим, что операции над строками соответствуют изменению базиса в пространстве всех вектор-столбцов, а операции над столбцами соответствуют изменению в базисе, порожденном цело численными комбинациями столбцов из В.

Другой путь состоит в том, что мы начинаем с оптимальной таблицы задачи линейного программирования. В конце симплек сных вычислений получаем

	I			B_1N			В^Ь
- 1	0	2	3	2/6' 4/6		2/6		43	'
0	1	3/6	2	3/6	3/6	0	123/6
							В 1			В	1 4	N		Ь
						’4/6		2 /6 " ’ 0		2	1 4	1	1 0	4Г
						_3/6		0	_ 3	- 4	4 1	- 1	0	1 47.

После вычитания целых частей и отбрасывания 6 в знамена

теле таблица принимает вид (слева добавлена единичная матрица)

’1	0	0	0	2
..о	1	СО	0	СО

4	2	--О1
3	0	3 .

Пусть е( = е4 и е'2= —е! + е2, т. е. добавим строку 2 к стро

ке 1. Получаем

" 1	1	со
о	1	со

со

1 2

СО

3 0 3.

	Заметим,	что все	числа берутся по модулю 6 . Пусть е/' =
=	— +	и е2 = е2,	т. е. добавим 3 раза 1 -ю строку ко 2 -й стро
ке.	Получаем