Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 100

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 100)

ТАНИЕ 358 — МАКСИМАЛЬНЫЙ РАЗРЕЗ 390 — МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО 358 — — ПОКРЫТИЕ 402 — МНОГОПРОДУКТОВЫЙ ПОТОК 390 — МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ 374 — МНО)КЕСТВО ВЕРШИН, РАЗРЕЗА!ОШИХ КОНТУРЫ 390 — — ДУГ РАЗРЕЗАЮШИХ КОНТУРЫ 390 — НЕЗАВИСИМОЕ МНОЖЕСТВО 373 — нелинейного программирования 9 Предлекчкый указатель НЕОПТИМАЛЬНОСТЪ В ЗК 495 0-|.РЮКЗАК 386 о бродячем торговце (ЗБТ) 312 — выполнимости 323 — гамильтоновом пути 302 — диете 30 — китайском почтальоне 276 — — — смешанный вариант 279, 390 — кратчайшем пути (ЗКП) 80, 113, 451 — — — веревочная модель 138 — лесе максимального веса (ЛМВ) 287 — линейных неравенствах (ЛН) 176 — максимальной клике 354 — максимальном потоке (ЗМП) 95 — — — индивидуальная 95 — — — расширение 232 — матроиде с соответствием 309 — многопродуктовом потоке минимальной стоимости 157 — моменте 23 — надежной сети минимальной стоимости (НСМС) 470 — назначениях 148, 159, 254, 317 — паросочетании 223 — — в ориентированном графе 251 — — с весами вершин 312 — — — узкич местом 251 — пересечении двух матроидов 300 — — трех матроидов 309 — подмножествах дискретная линейная (ДЛЗП) 486 — поставщике 156 — потоке минимальной стоимости 141 — — равномерном разбиении графа (РРГ) 478 — — разбиении относительно матроида 314 — расписании для чвух процессоров 250 — — — — заданий с директивными сроками (РЗДС) 490 — — — общая 319 — — реберном покрытии минимальной стоимости 277 — — строгих линейных неравенствах (СЛН) 178 — — сумме времен окончания заданий (ЗСВОЗ) 458 — — Ханойской башне 22 — — Ь-сочетании 251 — об остоаном дереве с пропускными способностями 157 - — упаковке контейнеров 252 — ограниченная прямая (ОП) 108, 109 — ОГРАНИЧЕННЫЙ ГАМИЛЬТОНОВ ЦИКЛ (ОГЦ) 492 — оптимизации 12 — — индивидуальная 12 — — комбинаторная 354 — — — для системы подмножеств 290 — — — вариант вычислительный 355 — — — — оптимизационный 355 — — — — распознавания 355 — ОПТИМИЗАЦИОННЫЙ 0-1-РЮКЗАК 433 — ПОСТРОЕНИЕ НАДЕЖНОЙ СЕТИ 403 — ПРОБЛЕМА ОСТАНОВКИ 357 — ПРОСТЪ|Е ЧИСЛА 414 — ПРОТЫКАЮЩЕЕ МНОЖЕСТВО 415 — прямая (П) 107 Задача ПУТЬ В ОРГРАФЕ 358 — РАЗБИЕНИЕ 387 — РАСКРАСКА ГРАФА 389 — распознавания 357 — СВ51ЗНОСТЬ ГРАФА 358 — ТОЧНОЕ |ТОКРЪ|ТИЕ 3-МНОЖЕСТВАМИ 385 — 3-ВЫПОЛНИМОСТЬ 369 — 3-МЕРНОЕ СОЧЕТАНИЕ 383 — 3-РАЗБИЕНИЕ 401 — ТРАНЗИТИВНОЕ СОКРАЩЕНИЕ ВЫБРАСЫВАНИЕМ 415 — Хичкока 148 — целочисленного линейного программирования (ЦЛП) 316 — — — — смешанная (СЦЛП) 319 — ЦЕЛОЧИСЛЕННЪ|Й РЮКЗАК 386 — 4.РАЗБИЕНИЕ 414 — К-е ПО ВЕСУ МНОЖЕСТВО 408 — и-ЦЛП 414 — )УР-полная 352, 363 — РЗРЯСЕ-полная 412 Задачи выпуклого программирования 2! — лвоичного линейного программи.

рования слс Задачи 0.|-линейного программирования — неразрешимые 160 — 0-1-линейного программирования (НОЛП) 324 — о матроидах 280 — — потоках и парссочетаниях 1Π— смешанного ЦЛП 333 — целочисленного линейного программирования (ЦЛП) 11 — Ь(Р-полные 11 — — частные случаи 413 Закорачивание 299 Предметный ухатипггь Замещение 48 Запрещение 485 Зацикливание 55 Игра в крестики и нолики л-мерная !93 Инцидентность 25 Исток 27 Источники 203 Клетка Лирихле 311 Клика планарная 404 Комментарии 29 Компонента сильно свизная 389 Контейнера вместимость 252 Конус 78 Коныонктивная нормальная форма 324 Куб 234 — д-мерный 171 — — возмущение 173 Лексикографически больше 344 — максимально 344 — меньше 344 — минимально 344 — равно 344 Лексикографические правила устранения зацикливания 347 Лемма Фархата 79 Лес 26 Лидер 299 Линия 139 Логические связки 323 Локально оптимальное допустимое решение 16 Маршрут 25 — гамильтонов 424 — замкнутый 25, 26 — ориентированный 25 — эйлеров 424 Матрица 24 — вполне унимодулярная (ВУМ) 325 — евклидова расстояния 422 — единичная квадратная 25 — замыкания 422 — инциденций дуг и цепей 96 — невырожденная 180 — положительно определенная 180 — расстояний 27 — смежностей 164 — Татта 250 — транспонированная 25 — унимодулярная (УМ) 325 — САРР)«92 Матроид 280, 294 — графический 294, 296 — матричный 294, 297 — разбиения 297 — — по концам дуг 297 Матроидов пересечение 298 Матроиды паросочетаиий 313 Машины Тьюринга !60 — — недетерминированные 410 Метод венгерский 254 Метод ветвей и границ 446 — градиента внебазисного 54 — — по всем переменным 54 — двухэтапный 60 — декомпозиции 101 — дефекта 157 — для сведения общий 275 — исключения Гаусса 197 — искусственных переменных см.

Метод двухэтапный — Кгрнигана и Лина 480 — кругового поиска 484 — «масштабирования» 158 — наибольшего приращения 54 — наиснорейшего спуска 483 — обратной матрицы см. Симплекс- метод модифицированный — первого улучшения 483 — сужения 4!5 — Хачияна 391 Метрическая ЗК см. Задача коммивоя. жера с неравенством треугольника Минимальное остовное дерево (МОЛ) 12 Многогранник 38 Множеств симметрическая разность 224 Множества медиана 31! — оболочка 296, 297 — ранг 296 Множество 24 — важных ячеек независимое 139 — вершинно непересекающихся путей 470 — выпунлое 18 — допустимых нечетных множеств 265 — — переменных 264 — — ребер 265 — — решений 353 — — столбцов 109 — индексов допустимое 149 Момент 23 Мультиграф 3!4, 424 — эйлеров 424 Набор заданий 319 — значений истинности 323 Напарник 224 Нелинейные ограничения 32! — стоимости 321 Неопределенность,371 Неравенства активные 275 Неравенство треугольника 422 Предмеглныд указатель Обход вложенный 426 Ограничения предшествевания 373 Окрестность относительно обмена 480 Оператор присваивания 28 — перехода 28 — условный 28 — 1ог 28 — мй)!е 28 Операция злемеитариые над строками 49 Операция треугольника 135 Оптимальности критерий 51 Оптимизация комбииаторная 11 — непрерывная 11 Орграф 25, 201 — вспомогательный 205 — динамический 302 — сильно связный 220 — статический 303 Ордерево 299 — кратчайшее 315 Основание системы счисления 163 Остовное дерево 13 Отказ 485 Отношение предшествования 319 Отсечение 338 — Гамора 339 Отсутствие прорыва 150, 257 Очередь 200 Ошибка совокупная 190 Паросочетаиие 223 — максимальное 223 — полное (совершенное) 223 — правильное 266 Переменная избытка 32 — недостатка 32 Переменные базисные ЗЗ вЂ” дискретные 323 — исходные 350 Переобращеиие 95 Плоскость отсекающая см, Отсечение 338 Подзадачи 102 Подмножество зависимое 295 Подобходы 317 Подпрограмма УЛУЧШЕНИЕ 467 Подпростраиство аффииное 38 — линейное 37 Поиск бинарный 176, 178, 356 — в глубину (ПГ) 201 — — ширину (ПШ) 201 — локальный 413 — неудачный 311 — успешный 311 Полииомиальная приближенная схема (ППС) 438 — — — полностью (ПППС) 439 Последовательность правильная ЗОЗ вЂ” — увеличивающая 303 — череду!ощаяся 301 Построение оптимальных объектов 361 Поток 27, 250 — величина 27, 250 — тупиковый 211 Предложение 104 Преобразование аффиииое 180 — полииомиальиое 363 — — сохраняющее 4!4 Прибрежная система газопроводов 475 Принцип оптимальности 461 Приоритет 414 Проблема остановки 160, 191 — соответствия Поста 192 Производящая строка 339 Пропускная способность 27 — — дополиительиан 208 — — сквозная (СПС) 213 Просмотр вершины х 126 Пространство виебазисиых переменных 54 — всех переменных 54 Процедура МАКСКЛИКА 356 — МОДИФИЦИРОВАТЬ 257, 258 — ПРОТОЛКНУТЬ 215 — ПРОТЯНУТЬ 215 — ПУТЬ 307 — РАЗМЕР КЛИ КИ 356 — рекурсивная 193 — УВЕЛИЧЕНИЕ 243 — ЦВЕТОК 241 — ЭЙЛЕР 425 Процесс пуассоновский 497 Процессоры 319 Псеадовершииа 268 — внешняя 268 — внутренняя 268 Пути 292 Путь кратчайший 203 — обратный 237 — прямой 211 — увеличивающий 117, 124, 224 — чередующийся 224 — — увеличивающий 224 Разбиение равномерное 478 Размер входа 163 — графа 164 — задачи ЛП 164 Размерность 38 Разрез 121 — минимальный 208 Ранг подматрицы 298 Реберное покрытие 250 Предмгтныд укаеатель Ребра вес 254 — паросочетания 224 — свободные 224 Ребро 25, 40 Реоптимизация 348 Ресурсы 319 Решение базисное ЗЗ вЂ” — допустимое (бдр) 34 Решения й-оптимальные 15 Сведения 485 — полиномиальные 362 Связность графа 199 Сеть 27 — биориентированная 250 — вспомогательная 2!Π— приращения 142 — простая 219 — разреженная 222 — слоистая 2!О Сильно )Ур.полная задача 400 Симплекс-алгоритм 9, 52 — двойственный 85 — прямой 85 Симплекс-метод модифицированный 92 Система чинейных неравенств противоречивая 11 — окрестностей !5 — — точная !7 — подмножеств 290 — туннелей 193 Сквозная пропускная способность (СПС) 2!3 Скорость роста !63 Слово !65 Слой 210 Совместимость 371 Сортировка массива 193 Соседи по Дирихлг 312 Списки смежностей 164, 198 СПИСОК !2о Способ восточно-западный 493 — северо-южный 493 Стоимость 423, 478 — внешняя 478 — внутренняя 478 — единичная 362 — относительная 50 Сток 27 Стягивание 235 Теорема Кенига — Эггреари 139 — Кука 366 — о максимальном потоке и миннмальном разрезе !23 Теория двойственности 175 Трансверсаль 3!3 3-саязность 4?О Уравнения сцепляющие 102 Условие дополняющей нежесткости 76, 107 Фраза 192 Функция вогнутая 20 — выпуклая !9 — окрестностная гм.

Система окрестностей — стоимости 353 Хорда 4!4 Цветки 234 Целая часть числа 338 Цели 203 Цепь 25 — длина 25 — кратчайшая 97 — ориентированная 25 Цикл 25, 296, 297 — длина 25 — ориентированный 25 Циркуляция 142 Черепицы 192 Шаг 271 — насыщающий 2!7 — частичный 217 Шар единичный 180 Штраф 490 Эвристики 413 Эквивалентность полиномиальная 333 Эллипсоид 180 Этап 257, 271, 288 Ячейка важная 139 Ы-гиперкуб см. Куб д-мерный Рперешеек 220 й-замена 15, 468 М-цикл 303 а-мерное действительное векторное пространство 24 )УР-полнота 325 Ир.трудность 408 р-квантили 311 РЗРАСЕ 4!1 гФразрез 12! — пропускная способность !2) гФсвязносгь ! 39, 221 Х-замена 473 — выгодная 473 — окрестность 473 Ь-замена 476 Оглавление Предисловие переводчика Предисловие за- Глава 1. Задачи оптнмизация .

Характеристики

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