Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 86
Текст из файла (страница 86)
190. Тис!«ег А. »Ч. !)иа1 Яугйешя о( Ношодопеоия 1,!пеаг Ве1апопв, !п Н. Су. КиЬп апй А. СУ. Тис!«ег (ейв], 1йпеаг !пе«)иа!!С!ев апд Ве!аге«! Яуягяпв, Лппа1в о! МасЬешасгсв Я!иду № 38, 1»г!псе!оп, Еп!чогя!су 1'гоев, 1'г!псе!оп» Н.)., 1056, 3 — 18. (Русский перевод: Танкер Л. У., Двойстпоиные систеиы однородных:«ииейпых соотношений. В сборнике «Линейные иерапеистпв и с»сежсгыо вопросы», ИЛ, Ы., 1959.) сннсотс литнннтуны 191. Тисйег А.
%. Ыпеаг апй )л)оп-Ыпеаг Ргодгашпнп9, Х. ОЛ8А, 5 (2), 244 — 257 (Лргб 1957). 192. Тис1сег Л. %. А СошЫпасог!а! Ес(и!ча!енсе о1 Ыасг!сеа, !и В. Ве!!план апй Мат»Ьа!1 На11, !г. (ейа), РгосессВпдк о1 Яушрокла лп Арр1, Мабл., чо!. Х, Сошйлпасопа1 Апа!ук!к, АМ8, РгочМенсе, В.!., 1960, 129 — 140. 193. Тпс1сег Л. %.
СошЫиатог!а! ТЬеогу ()пйег!у!пд 1.!иеаг Ргойташе, (п В. Ь. бтачеа апе! Р. %о1(е (ейа), Весен! Айчапсеа 1п Малйошак!са! Ргодташш!п8, 3!сбгаъ-Н!11, Мелч Ъ'ог!с, 1963, 1 — 18. 194. Тпые %. Т. 1птгойнсбоп Со СЬе ТЬеогу о( Макгогйк, ВАКО Верогк В-448-РВ, РеЬ. 1966. 195. Ь'кана Н. ТЬе Кийи-Тпсйег ТЬеогеш !и Сопсаче Ргойгашш!пд, 1п К. В Аттоле, 1.
НшчЛск апй 11. Скачка (ейк.), 8юсйек !и 1Апеаг апй Хоп-Ыпеаг Ргодгашш!ий, 8сап1огй Си!чегкНу Ргеаа, 8Сап1огй, СаИогп1а, 1958. 196. Уа!йа Я. МасЬетиабса1 Ргойташш!пц, Айй!коп-%ек!еу, Ксасйпй, Маш., 1961. (Русский перевод: Вайда С., Теория нгр н аинейпоо програлгмирование.
В сборнике »Линейные неравенства и смешные вопросы», ВЛ, М., 1159.) 197. л ап Ве 1'кипе С. апй %1ипетоп Л. ТЬе 8!ил!Йех аш1 Воа! МесЬойа 1ог Яиайгабс Ргодгашш!ид, 1ш. Ссикег (ог Мап. 8с1. Ворог! 6314 (1СМ8 )й 28), КоЫегйапл, ЛрП1 1963. 198. Уап 8(уйе В. анй %еС В. Оп В!айотла!!кас!отл Мебюйа ш 1псейег Ргойгаплш!пд» ОВС, ВВ 27, 1;и!чег»!Су о1 СаИогша, Вег1те1еу, 1962. 199. Типо% Л. Г., 1г. апй Вапкк!д б. В. !исейсг Ехсгеше Рошск, оуЛ М Лег!еш» 10 (3), 371 — 372 (1968).
200. Ъ'о!поЫ Л. Г., уг. аий %адпог Н, М. ОРС!пиип Сарасйу Зсйейн!!пй, 1 аий Н, У. ОВБА, 10 (4), 518 — 546 (1962). 201. ч от» .»ешпаип В Ои а Мах!ппкас1ои ГгоЫеш (шапиасг!рс), 1п»С!сисе 1ог Айчапсей 81нйлеа, Рг!псекоп, 1(елч !егееу, Уоч. 1947. 202. )топ Кешиапп !. апй Ми»депе!оси О. ТЬеогу о1 Сашек аий Есоиопис ВеЬач!ог, Рг!псе!оп Ьшчегайу Ргека, Ргшсекоп, В.!., 1944, 2 пй ейс 1947, Згй ей. 1953. (Русский перевод: Моргенпстерп О., Ненман Дж., фон, Теория нгр и экономическое поведение, нзд-во еНаука», М., 1970.) 203. %айе С. 8. апй боплогу В. Е.
!1'М 2, 8Ьаге РЛксг!Ьцбоп Л". 1191, Верс. 1961. 204. %айе С. Б. авй бошогу В. Е. 1РМ 1, 8Ьаге ВпйПЬикюн 96 1192, 8ерС. 1961. 205. %адиег 11. М. Л Тно-РЬаае ЫесЬой 1ог ейшр1ех ТаЫсан, У. ОВЯА, 4 (4), 443 — 447 (1956). 206. %адпег Н. Ы. А Сошраг!аоп о1 сЬе Оглд!иа1 апй сЬе ВечМей Яипр1ех МесЬойа, Х.
ОВБА, 5 (3), 361 — 369 (1957). 207. Счайпег 11. М. Оп а С!аш о1 Сарасйсй Тгапарогсш!оп РгоЫепл, Мапауеплепс Яп'., о, 304 †3 (1959). 511 СПИСОН ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ 224. г'оппй В. Р. А Рг1ша! (Л!1-!и!едег) !п«ейег Ргобгашш!пй А!богИЬш, Х. Нее«асей Вассала! Висеаи в/ Я!апдагдв! В, Ма!Ьеша!1сз апб МаРпешаПса1 РЬуз!сз, 69В, (3), 213 — 250 (Хп!у — БерС. 1965).
225. Уоппй В. П. А 8!шрРИ!«й Рппга! (АП-!и!ебег) !и!едет Ртсб«аппп!пб А!богИЬш, е'. ОВНА, !6 (4), 750 — 782 (дп!у — Апбпа! 1968). 226. Еоп«епоВ!Ь 6. Ме«Ьойа о! Реа«1Ые Р!тес!!опз, Е!«еч!ег РпЫ!зЫпй Со., Еечч Ъ"ог1«, 1960. (Русский перевод; Зойтендейк Г., Методы возмонсных направлений, ИЛ, М., 1969.) СПИСОК ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ 1«. Вотяков А. А. Некоторые вопросы целочисленного программирования, Эком«мика и математические методы, 4 (1968), вып. 4. 2«. Вотяков Л.
А. Целочислеппое программирование, сравнение отсечений, Экаквмика и математические методы, 8 (1972), выл. 1, 107 — 116. 3*. Гольштейн Е. Г., Юдин Д. Б. Новые направления в линейноы программировании, М., «Сов. радио», 1966. 4*. Гришухин В. Н. Оценка сложности алгоритма Балаша. Сб. «Математические методы решения экономических задаче, № 3, изд-во Наука, М., 1972. 5*. Диниц Е. А. Алгоритм решения задачи о ыаксиыальпом потоке в сети со степенной оценкой, ДАН ССС!', !94 (1970), № 4, 754 — 757. 6'.
Емеличев В. А. К теории дискретной оптимизации, НАН СССР, 198(1971),'№ 2, 273 — 276. 7«. Исследования по дискретной математике. Сборник под ред. А. А.„Фридмана, «Паука«, М., 1973. 8«. Карзанов А. В. Экономный алгоритм нахождения максимального потока в сети, Экакомика и математические методы, 1974 (в печати). 9". Корбут А. Л., Фиикельштейн Ю. Ю.
Дискретное программнровакие, М., «Наука», 1969. 10*. Литвак В. Г., Раппопорт А. М. Об условиях своднмостн задач лннейпого программировапиа к сетевым задачам, Экономика и математические методы, 6 (1970), вып. 6. 11«. Романовский И. В. Методы неявного перебора для решения задач целочисленного программирования с бивалентными переменными. Навестил ВУЗов, Математика, 4 (1970], 17 — 29. 12«. Трубки В. А. О методе реп!ения задач цело«ислен~ого линейного программирования специального вида, ЙАН СССР, 189 (!969), № 5, 552 — 554.
512 СПИСОК ДОНОЛНИТИЛЬНОЙ С!ИТВРАТУРЫ 13*. Фпнкессь«птсйп 10. Ю. Оценка числа итераций полностью целочисленного алгоритма Гомори, ДЛ П СССР, 193 (3) (1970), 543. 14*. Фрпдман А. Л. Задачи на конечных мвоьчоствах, Экономика и мат«мотическне мепсоды, 9 (1973), вып. 6. 15«.
Черкасский Б. В. Конечный алгоритм регпвппн задачи о двухпРодуктовом ПатОКО, Экокомика и есин««масс«с«чески« методы, 9 (1973), вып. 6. 16*. ОеоПпоп Л. М., Маге!еп В. Е. !и!едет Ргодгаптпз!пд Л!дог!1!«нтв: Л. Гга«пеиог!с апс( 8!а!е-о(-!)«е Агв Зигчеу, Монад«тес«1 Бе!енсе, 18 (19с2), Л! 9. 17«. Роив!е!и Т. Оп гйе Махина! Г! отг РгоЫеп» ъ415 11еа! Лгс Сарае!1!ев, Ма!денс. Ргодгатт1нд, 3 (1972), 59 2. 18*.
Заату Т. Ор!!Нива!!оп ьн !1«!еде«в апс) Зе!а1ед Кх!геша! РгоМепт, Несо уог)с,. 1970. (Русский перевод; Секти Т., !!елочпсленные методы оптимизации и связанные с ними зкстермальные проблемы. М,, «Мнр», 1973.! 19*. Забей К. ТйеогеИса1 Е(1!ссспсу о! ЕдгаопсМ вЂ” Катр Л19опйпп 1ог Со«при!1пи Мах!пса! Г1оУО «ЛОМ, 19 (1972), Л! 1.
УКАЗАТЕЛЬ Автоморфизмы главных многогранников 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 Базис 34 — допустиммй 34 — — начальный 53 Базисная дуга 198 Базисное 1п шение 33, 34, 39, 40 — — допустнчое 35 — — оптнмальноо 40 — — — существование 36 Базисные переменные 34, 45, 158 Балинский 323, 109 Гаумоль 296 Бендере 315 Беп-Исраел 345, 349, 357 Бил 89 Ведущая строка 50 Ведущий столбец 50 — злемепт 50 Войпотт 159 Вектор базисный 34 — направляющий выпуклого конуса 26 Вершина 134 — висячая 461 — многогранника 37 Взаимный метод решения прямой п двойственной задач 109 Витцгал 323, 331 Вогнутая функция 30 Вспомогательная задача 119 Вулф 125 Выпуклая линейная комбинация 26 — оболочка 28 — функция 28 — — строго 28 Выпуклое множество 26, 37 Выпуклый конус 25 — многогранник 28 Вырожденное решение 34 Выронздепность 53, 59 Гаусса метод исключения 46 Гейл 70 1 еометрнческая интерпретация двойственности 81 — — дополняющей пензесткости 75 — — задачи линейного программирования 40 514 унлзатпль Геометрическая интерпретация симплекс-метода 63 — — циклического алгоритма Гомори 295 Гиперплоскость 24 — опорная 33 Главный многогранлвк 435 Гловер 344, 349 Говори 81, 109, 133, 167, 180, 248, 284, 286, 291, 296, 300, 310 Гофман 159 Грани мвогограввиков гомоморфных групп 443 — — циклических групп 441 Грань р-мсрная 37 — целочислелпого мвогогралника 425 Граф 135 — ациклический 155 — дзудольный 154 — ориелтировавный 155 — разложение 155 — покрытие цепями 155 Группа характеров 446 Данциг 323, 75, 85, 100, 117, 125, 159 ,Двойствевлая задача 70 Двойственность 70 — геометрическал ивтерпретацил 81 — теорема 70, 73, 456 Декомпозиции принцип 125 Дерево 156 — доминирующих тробовавий 180 — связывающее 156 — — максимальное 156 — текущее 192 Диагоиальвал форма 45 ,Дийкстра 191 Длина пути кардинальная 150 — цепи 191 Дополняющая нежесткость 75 — — геометрическал интерпретация 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 — об удовлотворевии требуемого спроса заданным предложевиеи 152 — о ивоголродуктовых потоках 153 — — мвогололюслых максимальпых потоках 164 — — — — — алализ сети 164, 167 — — — — — синтез сети 164, 180 — — — — — условие реализуемости 164, 165 — цолочисленного програмиировапия 285 Зав 323 Звено 134 Избыточная система ураввевий 33, 56 Изменение потока 144 Ивтевсиввость процесса 14 Интуитивпый прямой алгоритм 345 Искусствеппые перемеввые 53 Источник 135 — дополиительвый 153 — искусственный 154 Каноническая форма задачи линейного программирования 44, 71 Кардинальное расстояние 150 Касательная плоскость ЗЗЗ Коммивояжера задача 328, 330 Композиция матриц 206 Копус 24 — выпуклый 25 — двойственный 25 — ковечкопорождонпый 25 Конусов пересечение 25 — сумма 25 Коррекцил 129 Крайняя точка 27 Краскал 159 Критическая тоиса 98 Куя 70 Купер 54 Латинские квадраты 328 Лексикографически воложительпый (отрицателькый) вектор 59 УКАЗА ТЮЛЬ 515 Лексвкографическое упорядочение 59 Лепке 86, 96 3[ввейная программа 15 — комбинация выпуклая 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 5!внимальное множество 225 Минпиальный разрез 225 Минимум функции 28 — — глобальный 28 — — локальный 28 — — — строгий 28 Минковского — Фаркаша лемма 21 Множество допустимых решений 37 — рассекающее 155 Модифицированная задача линейного программирования 285 Модифицированный симплекс-метод 100 11аправлепие дуги 134 Начальный допустимый базис 53 Небазисные переменные 34, 158 Невязка 117 Несовместнал система уравнений ЗЗ Неявный перебор 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 Покрытие графа цеплин 1о5 Полностью целочисленный алгорвтм 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 516 УКАЗАТЕЛЬ Раскраски задача 328, 329 Расстановка пометок 142 Расстояние карлвыальное между узлами 150 Ребро 134ь Решепве допустимое 35, 37, 462 — оптвмальвос 40 — следуьощее за 461 Свойства отсечений Гоьюри 296 Сеть 134 — допустимал 181 — пеориентировавпак 224 — плоская 196 — связнан 134 Сильная дополняющая нежесткость 77 Симплекс-моток 44, 142 — двойственный 87 — — геометрическая интерпретация 96 — двухфазовый 55 — модифицированный 100 Синтез дерева 182 — сети 249 Система различных представителей 155 Слабая лополвяющая нежесткость 76 — целочисловная перемонная Гоморп 288 Слабые переменные 16, 54 Смешапный алгоритм целочисленного програимированил 310 — — — — доказательство конечности 313 Совместная система уравнений 33, 56 Специальвал грань многогранника 444 Справочные строки 334 Спрос 152 Стапдартпал форма задачи линейного программирования 44, 71 Стаплартный вид таблицы 337 Стоимость пометки 415 Столбцовая таблица 89 Сток 135 — Лополььвтельвый 153 — искусственный 154 Таккер 70, 77 Теповая цена 67 Теорема Дььлворта 155 — двоиственностн 70, 73, 456 — Кепнга — Эгервари 155 — Ментора 155 Теорема о максимальном потоке и мвпималшюм разрезе 138 — о целочислеппости потока 144 — Холла 155 Терварная опорацкя 198, 205 Томлип 239 Травсвортпая залача 327 Узлы 134 — дополнительные 153 — искусственныо 153 — непомеченные 143 — несравнимые 155 — отношение порядка 155 — помеченные и непросмотренные 143 — соседние 143 Уоршелл 198 Условно кратчайшая цепь 204 Фалкорсон 218 Фтойд 198 Форд и Фалкерсоп 117, 137, 239 Характер группы 446 Характеристическая строка 113 Характеристический столбец 113 — злемепт 113 Хендерсоп 54 Ху 167, 180, 198, 218, 248 Целевая фуккцвя 15 Целочисленного программирование задача 285 Цопь 135 — кратчайшая 191, 198 — ориентированная 135 — потоковая 150 — простая 135 Цикл Г35 — ориентироваппый 135 — стационарньгй 349 — переходный 349, 357 Циклвческий алгоритм 284, 288 — — доказательство конечности 289 Цвркуляцин 214 Чарнес 54, 345, 349 Здььондс 323 Цквивалентность могола расстановки пометок и спьшлокс-метода 146 Зквььваььситвые преобразования задачи щшейиого програььььированим 15, 93 Злементарнос преобразование 379 Юпг 344, 349 ОГЛАВЛЕНИЕ 11редпсловио редактора перевода !!з предисловии автора .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
