Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 101
Текст из файла (страница 101)
1.1. Введение 1.2. Задачи оптимизации 1.3. Окрестности 1.4. Локальные и глобальные оптимумы 1.5. Выпуклые иножества и функции 1.6. Задачи выпуклого программирования Задачи , Комментарии и ссылки Приложение. Терминология и обозначения П.1. Линейная алгебра П.2. Теория графов . П.З. Упрощенный Алгол Глава 2. Симплекс-алгоритм 2.1. Формы задачи линейного программирования 2.2. Базисные допустимые решения 2.3. Геометрия задач линейного програимирования 2.4. Переход от одного бдр к другому 2.5. Организация таблицы 2.6.
Выбор выгодного столбца .. 2.7. Выбор ведущего элемента и алгоритм Блэнда, устраниющий цикливание 2.8. Начало симплекс-ал>оритма 2.9. Геометрические аспекты замещения Задачи Комментарии н ссылки Глава 3. Двойственность . 3.1, Двойственная задача линейного программирования в форме . 3.2. Дополняющая нежесткость 3.3. Лемма Фаркаша 3.4.
Задача о кра>чайшем пути н двойственная к ней задача 3.5, Двойственная информация в таблице 3.6. Двойственный симплекс-алгоритм 3.?. Интерпретация двойственного симплекс-алгоритма Задачи . Комментарии и ссылки,, 9 9 11 1'> 1ь 18 20 22 '>4 21 24 25 28 30 30 32 37 4Г> 48 50 54 60 63 68 70 72 72 ?6 78 80 83 85 86 89 90 Оглавление 92 92 Глава 94 5. Прямо-двойственный алгоритм Глава 107 108 1!2 1!3 !17 117 119 120 Глава 141 !41 142 145 147 153 155 156 157 8. Алгоритмы и сложность 160 Глав. 4. Вычнслнтельиме аспекты симплекс-алгоритма 4.1.
Модифицированный симплекс-алгоритм .. 4.2. Вычислительные эффекты модифицированного симплекс-алгоритма 4.3. Задача о максимальном потоке и ее решение модифицнрованньш методом. 4.4. Метод декомпозиции Данцига — Вулфа Задачи Комментарии и ссылки . 5.!. Введение 5.2. Прямо-двойственный алгоритм 5.3. Комментарии к прямо-двойственному алгоритму 5.4. Прямо-двойственный метод в применении к задаче о кратчайшем пути 5.5. Замечания по методологии 5.6. Прямо-двойственный метод в применении к задаче о максимальном потоке .. Задачи Комментарии н ссылки . Глана 6.
Примо-двойстаепиые алгормтмы для задач о максимальном потоке и кратчайшем пути: алгоритмы Форда — Фалкерсона н Дейкстры 6,1. Теорема о максимальном потоке и минимальном разрезе . 6.2. Алгоритм пометон Форда и Фалкерсона 6.3. Проблема конечности алгоритма пометок 6.4. Алгоритм Дейкстры 6.5. Алгоритм Флойда — Уоршелла Задачи Комментарии и ссылки 7. Прямо-двойственные алгоритмы для задачи о потоке минимальной стоимости 7.1.
Задача о потоке минимальной стоимости . 7.2. Комбинаториализация пропуснных способностей. Алгоритм ЦИКЛ 7.3. Комбинаториализация стоимости, Алгоритм ДОСТРОЙКА 7.4. Явный прямо-двойственный алгоритм для задачи Хичкока. Алгоритм АЛЬФАБЕТА . 7.5. Преобразование задачи о потоке минимальной стоимости в задачу Хичкока 7.6. Заключение . Задачи . Комментарии и ссылки .
Ш1. Вычислимость 8.2. Временнйе оценки .. 8.3. Размер индивидуальной задачи 8.4. Анализ а.чгоритмов 8.5. Полиномиальные алгоритмы . 8.6. Симплекс-алгоритм не является полнномиальным, 8.7. Алгоритм эллипсоидов Задачи Комментарии и ссылки . 95 100 105 106 107 121 12! 124 128 133 135 !38 140 160 16! 163 166 168 171 175 509 Оглавление 198 сложностью 223 графе . 254 255 275 276 278 280 Комментарии и ссылки 314 316 Глава 9. Зффектнвные алгоритмы для задачи о максимальном потоке .
9.1. Поиск по графу 9.2. Что нехорошо в алгоритме пометок? 9.3. Расстановка пометок на сети и поиск по орграфу 9.4. Алгоритм нахождения максимального потока со О !! !'!з) 9.5. Случай единичных пропускных способностей Задачи Комментарии и ссылки Глава 10. Алгоритмы для задачи о паросочетанни 1О.1. Задача о паросочетании .. 10.2.
Алгоритм построения паросочетания в двудольном 10.3. Паросочетание в двудольном графе и поток в сети . 10.4, Паросочетание в произвольном графе. Цветки 10.5. Паросочетание з произвольном графе. Алгоритм Задачи Комментарии и ссылки Глава 11. Взвешенное паросочетание 11.1. Введение . !1.2. Венгерский метод длн задачи о назначениях 11.3. Задача о взвешенном парссочетанин в произвольном графе !1.4. Выводы Задачи Комментарии и ссылки . Глава 12. Остовиые деревья н матроиды 12.!. Задача о миничалыюи остовнои дереве . 12.2. Алгоритм со сложностью 0 (!Е! !ой !'г'!1 для задачи о мини. кельном остовиом дереве 12.3.
Жадный алгоритм !2.4. Матроиды 12.5. Пересечение двух матроидов !2.6. О некоторых расширениях задачи о пересечении иатроидов .. Задачи Глава 13. Целочисленное линейное программирование 13.1. Введение 13.2. Вполне унимодулярность !3.3. Верхние опенки решений задач ЦЛП Задачи Комментарии и ссылки Глава 14. Алгоритм отсекзющей плоскости для задач целочисленного нейного программирования 14.!. Отсечение Гомори !4,2. Лексикографнческое упорядочение . 14.3.
Конечность дробного двойственного алгоритма 14.4. Другие алгоритмы отсекающей плоскости Задачи . Комментарии и ссылки 198 205 ?07 2П 217 220 22! 223 226 230 232 240 250 252 280 383 287 290 298 308 311 316 325 328 333 334 336 344 347 349 350 351 Озлаалеяие !0 раз- Аг Р-полнота 418 418 422 432 440 444 444 467 467 468 469 475 478 482 486 490 492 496 499 501 Глава 15. МР-полные задачи 15.1. Введение 15,2. Задача оптимизации — это три задачи . !5.3.
Классы Р и 11Р 15,4. Полиномнальные сведения 15.5. Теорема Кука . 15.6. Другие А'Р-полные задачи: КЛИКА и ЗК, !5.7. Еще несколько МР-полных задач сочетание, покрытие и биение . Задачи .. Комментарии а ссылки Глава 16. Еще об 57Р-полноте !6.1. Класс со-ХР !6.2. Псевдопачиномиальпые алгоритмы и «снльная» !6.3. Частные случаи и обобщенна А'Р-полных задач !6.4. Словарь родственных понятий !6.5. Эпилог Задачи Комментарии и ссылки . Глава 17.
Приближенные алгоритмы .. 17.1. Эвристики для задачи о вершинном покрытии. Пример !7.2. Приближенные алгоритмы для задачи коммивояжера 17,3. Приближенные схемы 17.4. Отрицательные реэулыгаты Задачи Комментарии и ссылки Глава 18, Метод ветвей и границ и динамическое программирование, И.1. Метод ветвей н границ для целочисленного линейного программирования 18.2.
Метод ветвей и границ в общем виде !8.3. Отношения доминирования . 18.4. Стратегии метода ветвей н границ 18.5. Применение н задаче о расписании для конвейера !8,6. Дннамичеснае программирование Задачи Комментарии н ссылки Глава 19. Локальный поиск !9.1. Введение 19.2. Задача 1: ЗК 19.3. Задача 2; надежные сети минимальной стоимости . 19.4. Задача 3: тапачогня прибрежной системы газопроводов 19.5. Задача 4: равномерное разбиение графа !9.6. Общие аспекты локального поиска !9.7.
Геометрия локального цаиска . !9.8. Пример больших минимальных точных окрестностей 19.9. Сложность точного локального поиска для ЗК . Задачи . Комментарии и ссылки . Дополнительные комментарии и ссылки . Предметный указатель 352 352 353 357 361 363 369 383 389 391 394 394 398 402 408 412 414 416 446 446 450 455 456 457 461 464 465 УВАЖАЕМЫЙ ЧИТАТЕЛЫ Ваши замечания о содержании книги, ее оформлении, качестве перевода н другие просим присылать по адресу: 129820, Москва, И-1!О, ГСП, 1-й Рижский пер., д. 2, издательство «Мири Христос Х Пяпяднмитрву, Кеннет Стяйглии «Комбннаторнзя оптимизации Алгоритмы и сложность» Ст.
науч. ред. И. А. Мазана» Мл, ред. О, И. Куэиецоаа Художник Г. М. Чеховской Художественный редактор В. И. Шаповалов Технический редзктор 3. И. Резина Корректор Н. В. Андреева ИБ 4007 Сдано в набор 28.04.34. Подписано к печати 20.! 1.84. Формат 60К90А«. Бумага типографснзи № 2. Обу Гз иитура литературная Печать аысоивя, ъем 16бум. л. Уел. печ.л. 32. Уел, кр отт 32. Уч.-изд. л 31,9!. Изд.
№ !!3054. Тираж 7500 экэ. Заказ № 3032. Пеи» 3 р. 10 к. ИЗДАТЕЛЬСТВО МИР Москва, 1 й Рижекнй пер., 2 Огпечетано с матриц Ордена Октибрьской Революцин и ордена Трудового Красного Знамени Первой Образповой типографии нм. А. А. Жданове Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии н книжной торговли. 113054, Москва, Валовая,28 в Лениаградакоя типографии № 6 ордена Тру. дового Красного Знамени Ленинградского объединении «Текиическая книга» им. Евгении Соколовой Союзполиграфпроме прв Государ. етвенном комитете СССР по делам издательств, олиграфни в книжной торговли. 93144« г. Ленин«рад, ул. Моисеенко, 10.
3. 67. .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
