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

Автоморфизмы главных многогранни­ ков 437

Алгоритм аддитивный булевого про­ граммирования 462

—асимптотический 387, 399

—групповой минимизации 414

—интуитивный прямой 345

—полностью целочисленный 300

—— — доказательство конечности

303

—построения двухпродуктовых по­ токов 231

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

— — кратчайших цепей между всеми парами узлов 198

----------------декомпозиционный 203

-------максимального потока 143

---------------- в плоской сети 197

---------------- в сети с пропускными способностями узлов 271

— — — — модификация для неори­ ентированной сети с действитель­ ными пропускными способностями

146

--------------- модификация Эдмондса — Карпа 148

—— максимальных потоков между

рузлам и сети 173

—— потока минимальной стоимо­ сти 213

—разбиения в смешанном целочис­

ленном программировании 318

—синтеза дерева разрезов 186

—— коммуникационных сетей 248

---------------- двойственный 253

---------------- прямой 258

------- сети 181

Алгоритмы типа дерева поиска 460 Анализ сети 249

Базисное решение 33, 34, 39, 40

----------- существование 36

Базисные переменные 34, 45, 158-

Ведущ ая строка 50 Ведущий столбец 50

—элемент 50 Вейнотт 159 Вектор базисный 34

—направляющий выпуклого конуса

26

Вершина 134

—висячая 461

—многогранника 37

Вы пуклая линейная комбинация 2&

—оболочка 28

—функция 28

------- строго 28

Вы пуклое множество 26, 37 Выпуклый конус 25

— многогранник 28 Вырожденное решение 34 Вырожденность 53, 59

Гаусса метод исключения 46

Гейл 70 Геометрическая интерпретация двой­

ственности 81

—— дополняющ ей нежесткости 75

—— задачи линейного программи­

рования 40

Геометрическая интерпретация сим­ плекс-метода 63

— — циклического алгоритма Гомо-

Грани многогранников гомоморфных групп 443

—— циклических групп 441 Грань р-мерная 37

—целочисленного многогранника

425

Граф 135

—ациклический 155

—двудольный 154

—ориентированный 155

—разложение 155

—покрытие цепями 155 Группа характеров 446

—геометрическая интерпретация 81

—теорема 70, 73, 456

Декомпозиции принцип 125 Дерево 156

—доминирующих требований 180

—связывающее 156

— — геометрическая интерпретация

81

Допустимое правило выбора произво­ дящей строки 351

— решение 35, 37, 462

Дуга 134

—вне дерева 192

—дерева 192

—направленная 134

—насыщенная потоком 146

—неориентированная 134

—обратная 139

—петля 135

—прямая 139

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

—двойственная 70

—коммивояжера 328, 330

—линейного программирования 14, 15, 17, 136

—------ модифицированная 285

—нахождения максимального пото­ ка в сети 136

—об удовлетворении требуемого спроса заданным предложением 152

—о многопродуктовых потоках 153

—— многополюсных максимальных потоках 164

Избыточная система уравнений 33, 56

Изменение потока 144 Интенсивность процесса 14 Интуитивный прямой алгоритм 345 Искусственные переменные 53 Источник 135

—дополнительный 153

—искусственный 154

Каноническая форма задачи линей­ ного программирования 44, 71

Кардинальное расстояние 150 Касательная плоскость 333 Коммивояжера задача 328, 330 Композиция матриц 206 К онус 24

—выпуклый 25

—двойственный 25

—конечнопорожденный 25 Конусов пересечение 25

—сумма 25

Коррекция 129 Крайняя точка 27 Краскал 159 Критическая точка 98

Кун 70

Купер 54

Латинские квадраты 328 Лексикографически положительный

(отрицательный) вектор 59

—комбинация выпуклая 26

—— — допустимых сетей 241 Линейного программирования зада­

ча 14, 15, 17, 136

Л окальная координатная система 66 Л окальны й минимум функции 28 Л у ч 23

Максимальный поток 138 Матрица абсолютно унимодулярная

157, 159

----------- условия 159

Матричная форма записи 61 М ерчленд 198 Метод ветвей и границ 461

—дерева поиска 460

—исключения Гаусса 46

—одновременного решения прямой

идвойственной задач 109

—разбиения в смешанном целочис­ ленном программировании 315

—расстановки пометок 142

—— — модифицированный 163

—циклического потока 231

—штрафа 54, 130

М инимальное множество 225 Минимальный разрез 225 Минимум функции 28

-------глобальны й 28

------- локальны й 28

----------- строгий 28

М инковского — Фаркаша лемма 21 Множество допустимых решений 37

— рассекающее 155 Модифицированная задача линейного

программирования 285 Модифицированный симплекс-метод

100

Направление дуги 134 Н ачальный допустимый базис 53

Небазисные переменные 34, 158 Невязка 117 Несовместная система уравнений 33 Неявный перебор 462

Н ормальная форма Смита 384, 450

Обращение базиса 100, 128 Ограничения 15 Операция оценивания 67

О порная гиперплоскость 33

Оптимальное решение 40 Орден 75 Ориентация дуги 134

Ортогональность решений задачи ли ­ нейного программирования 77

Орчард — Х ейс 100 Относительные оценки 62 Отрезок 23

Отсечение Гомори 289, 302, 303, 337, 345

Параболическое ограничение 331 Переменные базисные 34, 45, 158

—искусственные 53

—слабые 16, 54

Петля 135

Покрытие графа цепями 155 Полностью целочисленный алгоритм

300

— — — доказательство конечности

303

Полож ительно определенная (полуонределенная) квадратичная форма

332

Полупространство 24 П оляра 333 Пометка 142, 415

—временная 415 •— постоянная 415 Поток в сети 135

—величина 136

—дуговой 136

Правило выбора производящей стро­ ки 350

Предшествующее решение 461 Проверка отношения 50, 60 Производящая строка 289, 302, 344 Пропускная способность 225

------- дуги 135

------- остаточная 228

------- разреза 137

Пространство ресурсов 40

— условий 40 Процесс расстановки пометок 143

— — — модифицированное опреде­ ление 149

Прямая 23

— задача 70 Прямой алгоритм 344

— — доказательство конечности 360

Размерность выпуклого множества 28 Разрез 137

—величина 137

—локально минимальный 269

—минимальный 137

Раскраски задача 328, 329 Расстановка пометок 142 Расстояние кардинальное между у з­

лами 150 Ребро 134

Решение допустимое 35, 37, 462

—оптимальное 40

—следующее за 461

Свойства отсечений Гомори 296 Сеть 134

—допустимая 181

—неориентированная 224

—плоская 196

—связная 134

Сильная дополняю щ ая нежесткость

77

Симплекс-метод 44, 142

—двойственный 87

—— геометрическая интерпретация

96

—двухфазовый 55

—модифицированный 100

155

Слабая дополняю щ ая нежесткость 76

— целочисленная переменная Гомо­ ри 288

Слабые переменные 16, 54 Смешанный алгоритм целочисленно­

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

— — — — доказательство конечно­

Стандартная форма задачи линей­ ного программирования 44, 71

Стандартный вид таблицы 337 Стоимость пометки 415 Столбцовая таблица 89 Сток 135

—дополнительный 153

—искусственный 154

Таккер 70, 77 Теневая цена 67

Теорема Дилворта 155

— двойственности 70, 73, 456

—Кёнига — Эгервари 155

—Менгера 155

Теорема о максимальном потоке и минимальном разрезе 138

Узлы 134

—дополнительные 153

—искусственные 153

—непомеченные 143

—несравнимые 155

—отношение порядка 155

—помеченные и непросмотренные

143

—соседние 143

Уор ш елл 198

Условно кратчайшая цепь 204

Фалкерсон 218

Флойд 198

Форд и Ф алкерсон 117, 137, 239

Целевая функция 15

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

задача 285 Цепь 135

—кратчайшая 191, 198

—ориентированная 135

—потоковая 150

—простая 135

Цикл 135

—ориентированный 135

—стационарный 349

—переходный 349, 357 Циклический алгоритм 284, 288

—— доказательство конечности 289

Циркуляция 214

Чарнес 54, 345, 349

Эдмондс 323 Эквивалентность метода расстановки

пометок и симплекс-метода 146 Эквивалентные преобразования зада­ чи линейного программирования

15, 93

Элементарное преобразование 379

Ю нг 344, 349