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

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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

518	ОГЛАВЛЕНИЕ
Г л а в а 6.	Метод одновременного решения прямой и двойственной задач	109
*6.1.	Взаимный метод решения прямой и двойственной задач (Ба-
	линский и Гомори [7] и Т р о лл [1 8 4 ] ) ..........................................	109
6.2.	Прямо-двойственный метод (Данциг, Форд и Ф алкерсон [40])	117
Г л а в а 7.	Принцип д ек о м п о зи ц и и ....................................................................	12»
7.1.	Принцип декомпозиции (Данциг и Вулф [46], [47]) . . . .	125
7.2.	П р и м е р .....................................................................................................	129

Упраж нения

........................................................................................

132’

Д о п о л н е н и е

.....................................................................................................

133

Г л а в а 8. Максимальный ........................................................................

п о т о к

134

8.1.

В в е д е н и .................................................................................................е

134

8.2.

Метод расстановки

пометок

для

нахождения

максимального

п о т о к а .....................................................................................................

142;

8.3.

П р и л о ж ........................................................................................е н и я

152.

8.4.

Линейное ..........................программирование и потоки в с е т я х

156'

8.5.

Свойство

абсолютной

унимодулярности

(Гофман,

Краскал

[103], Вейнотт ................................................... ...,

Данциг [1 9 9 ])

159

Упражнения ............................................................................................

162

Д о п о л н е н и е .....................................................................................................

163

Г л а в а 9.

Многополюсные .........................................

максимальныеп о т о к и

164

9.1.

Постановки ................................................................................

з а д а ч

164

9.2.

Условие .............................реализуемости (Гомори и Х у [ 8

] )

165

9.3.

А нали з сети ..................................................(Гомори

и Х у

[ 8 9 ] )

167

9.4.

Синтез сети .......................................................(Гомори и Х у

[ 8 9 ] )

180

Упраж нения .................................................................................................

188;

Д о п о л н е н и е .....................................................................................................

189

Нерешенные ....................................................................................

з а д а ч и

189

Г л а в а 10. Кратчайш ие

цепи

потоки минимальной

стоимости . . .

191

10.1.

Кратчайшие ..........................................

цепи

(Дийкстра

[ 4 9 ] )

191

10.2.

Многополюсные

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

(Ф лойд

[63],

Х у

[111],

Мерчленд ..................................................

[158],

У ор ш елл [ 2 0 9 ])

198

10.3.

Декомпозиционный .......................алгоритм (Х у

[111],[ 1 1 3 ] )

203

10.4.

Потоки

минимальной стоимости . . ..........................................

212

10.5.

Задачи

об

оптимальном

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

заданной

сети

(Ф алкерсон ...........................................................

[ 68],

Х у

[ 1 0 8 ] )

218-

Упраж нения .................................................................................................

221

Г л а в а И .

Многопродуктовые ...........................................................

п о т о к и

223

*11.1.

Двухпродуктовые ......................................

потоки

(Х у [1 0 6 ] )

223

11.2.

Многопродуктовые потоки (Ф орд и Ф алкерсон [66],

Томлин

[186]) .......................................... ...................................................

239

11.3.

Синтез коммуникационных сетей (Гомори и

Х у

[91]) . . .

248

Г л а в а 12.

Потоки ......................................................в непрерывной с р е д е

265

12.1. Л окально ..............................................минимальные разрезы

265

12.2. Сети с пропускными .............................способностями у з л о в

267

12.3.

Потоки .......................................................в непрерывной среде

272

12.4.

r-разделяющее ...............................................................м н ож еств о

278

Г л а в а 13.

Циклический

алгоритм

целочисленногопрограммирования

284

13.1. Введение (Гомори [79])

284

13.2.

Примеры ...................................................................(Гомори

[ 7 9 ] )

291

13.3.

Геометрическая ...................................................

и н т е р п р е т а ц и я

295

		ОГЛАВЛЕНИЕ				519
13.4.	Свойства	дополнительных		неравенств	( Гомори ж Баумоль
	[ 8 7 ] ) .........................................................................................................					296
Г л а в а 14.	Полностью	целочисленный		алгоритм	......................................	300
14.1.	Полностью	целочисленный		алгоритм (Гоморп [80]) . . . .		300
14.2.	П р и м е р .................................................................................................					308-
Глава 15.	Смешанный алгоритм целочисленного программирования .					310
15.1.	Введение (Гомори [ 8 1 ] ) ...................................................................					310
15.2.	Метод разбиения в смешанном целочисленном програм
	мировании	(Бендере	[ 1 8 ] ) ...........................................................			315
15.3.	П р и л о ж е н и я .........................................................................................					323
Г л а в а 16.	Целочисленное программирование с параболическими огра
	ничениями	............................................................................................				331
16.1.	Введение (В итцгалл [215])					331
16.2. Т а б л и ц а .................................................................................................						334
16.3. Преобразование ...............................................................................						335
16.4. Алгоритм		.............................................................................................				337
16.5. П р и м е р ы .................................................................................................						338
16.6. Доказательство к о н е ч н о с т и ...........................................................						343
Г л а в а 17.	Прямой	алгоритм	целочисленного		программирования
	(Р . Д . Ю н г ) .........................................................................................					344
17.1. Введение и		а л г о р и т м ........................................................................				344
17.2.	П р и м е р .................................................................................................					357
17.3.	Доказательство конечности			.......................................................		369
17.4.	Вывод соотношений и пояснений ..............................................					365
Г л а в а 18.	Задача о рюкзаке ............................................................................					371
18.1.	Задача о рюкзаке (Гилмор,			Гомори [75],	Гомори [84]) . . .	371
Г л а в а 19.	О соотношении между линейным и целочисленным програм
	мированием .........................................................................................					378

19.1.Введение (Гомори [84], Кортанек и Ярослав [133]) . . . . 378

19.2.Асимптотический алгоритм (Гомори [84], [85], [86]) . . . . 387

19.3.	Алгоритм групповой минимизации (Х у					[1 1 2 ]) .........................	414
Г л а в а 20.	Грани		целочисленного		м н о г о г р а н н и к а ..................................		424
20.1. Введение .............................................................................................							424
20.2. Вычисление г р а н и ............................................................................							432
20.3. Многогранники Р (G, g 0) ................................................................							434
20.4. Автоморфизмы				главных многогранников ..............................			437
20.5. Грани			многогранников циклических			г р у п п .........................	441
20.6.	Грани		многогранников гомоморфных г р у п п ..............................				443
20.7.	Характеры и н ер а в ен ст в а ...............................................................						445
П р и л о ж е н и е		А .	Нормальная форма Смита (Х у [1 1 2 ])..................................				450
П р и л о ж е н и е		В.	Альтернативное		доказательство	двойственности . .	456
П р и л о ж е н и е		С.	Алгоритмы типа		дерева п о и с к а ......................................		460
П р и л о ж е н и е		D.	Грани,	вершины	и матрицы инциденций многогран
	ников		.....................................................................................................				465
Список л и т е р а т у р ы .............................................................................................							496
Список дополнительной				литературы ...........................................................			511
Указатель		...................................................					513

УВАЖАЕМЫЙ ЧИТАТЕЛЬ!

Ваши замечания о содержании книги,	ее оформлении, каче
стве перевода и другие просим присылать по адресу:
129820, Москва И-110, ГС П , 1-й Риж ский	пер., д. 2, издатель
ство «М и р ».

Т . Х у

Ц Е Л О Ч И С Л Е Н Н О Е П Р О Г Р А М М И Р О В А Н И Е И П О Т О К И В С Е Т Я Х

Р ед а к т о р И .

А . М а х о в а я .

Х у д о ж н и к Н .

С.

Х м ел ев ск ая .

Х у д о ж ест в ен н ы й

р ед а к т о р

В .

И .

Ш ап ов ал ов .

Т ехн и ч еск и й

р ед а к т о р

Г . Б .

А лю ли н а .

К ор р ек тор ы

К . Л . В о д я н и ц к а я

Н .

А .

Г и ря

С дан о в н а б о р

2 5 /X I I

1 9 7 3

г .

П о д п и са н о к

п еч ати

8 /V

1 9 7 4 г .

Б у м а г а к н . ж у р н .

6 0 x 9 0 l / i e = 1 6 ,2 5

б у м .

л .

3 2 ,5 0 п еч .

л .

У ч .-и з д .

л .

2 8 ,6 7

И зд .

М«

1 /7 1 5 6 .

Ц ен а 2 р . 14 к . З а к . 0 1 3 4 8

И З Д А Т Е Л Ь С Т В О «М И Р »,

М оск в а ,

1 -й

Р и ж ск и й п е р ., 2

О р ден а Т р у д о в о го

К р а сн о го

зн а м ен и М оск ов ск ая ти п о гр а ф и я А6 7 «И ск ра

револю ции »

С о ю зп ол и гр аф п р ом а п р и

Г о су д а р ст в ен н о м

ком и тете

С овета

М инистров СССР

п о дел ам

и здател ь ств , п ол и гр а ф и и

к н и ж н ой то р го в л и ,

г .

М оск ва,

К - 1 , Т р ех п р у д н ы й п е р ., 9

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

Циперович, М. В. Обогащение углей в тяжелых суспензиях.pdf

Чеботаревский, В. В. Лаки и краски - что это такое.pdf

Черкасов, Г. И. Введение в технологию бетона.pdf

Чупахин, В. М. Производство жестяной консервной тары учебник.pdf

Шамрай, Ф. И. Сплавы вольфрама, молибдена и ниобия с бором и углеродом.pdf

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

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

Информация

Списки файлов

Дополнительно