Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 46
Текст из файла (страница 46)
Решим рассмотренный выше пример прямым методом. Прямой метод имеет то преимущество, что оп в процессе вычислений все время дает допустимые сети, и можно остановиться на одной из них, если поиск оптимального решения окааывается слишком длительным. Прямую допустимую сеть легко получить, положив ум —.— = шах гы (с) для всех с, 1. В пашем примере условие г, =. 3 с принимает вид г, = 3 и г, =. 3. Следовательно, исходная допустимая сеть имеет вид уа = [5, 4, 3, 4, 21.
Для получения исходного бависа введем переменные ис (с = 1,..., 5), которые пе ограничены по величине и определяются следующилс обрааом: у,=5 — ис, уз= 4 — ию уз=3 — из, ус = 4 — и„у, =- 2 — из. Это преобрааование дает исходную таблицу П1 для основной части. Ясно, что если любая из переменных ис возрастает от нуля, 11.5. СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТЕЙ Табаииа П1 1 — и1 — и5 — из — и5 — иа У1 У5 Уз У5 У5 то стоимость улучшается. Пометим из стрелкой для обозначения, что выбрана именно эта переменная. Следовательно, нам нужно решить задачу (12), где уа = [5, 4, 3, 4, 2[, у, =- [О, О, 1, О, 0).
Будем пог1ьзоваться вектором [уа, +1[ вместо [уа, — 1]. Тогда в столбце под переменной за будет стоять — 1, и мы получим табл. ВП1 (кроне самого правого столбца). В таблице ВП1 все относительные оценки равны 0 и мы получим сеть [3, 4, 3, 4, 1[ в качестве самой дешевой сети в 1-и периоде. Зтот вектор расширяется до [О, 3, 4, 3, 4, 1, 1[ и добавляется в табл.
ВП1. Так как в табл. ВП1 стоит — 1 в столбце нод га, то эта таблица не является начальной. Выберем ведущий элемент, помеченный звездочкой, и выполним итерацию симплекс-метода. Тогда получим начальную табл. ВП2. В табл. ВП2 столбец под 8 является улучшающим, так как оп обладает отрицательной стоимостью. Применяя итерацию симплекс-метода (ведущий элемент табл. ВП2 помечен звездочкой), получаем табл. ВПЗ (кроме самого правого столбца). Испольауя относительные оценки из табл.
ВПЗ, т. е. (О, О, 1, О, 0), найдем самую дешеву1о сеть, удовлетворя1ощую потоковым требованиям в 1-м периоде: [3, 4, О, 7, 4[. Расширим этот вектор до [О, 3, 4, О, 7, 4, 1) и скорректируем его перед записью в самый правый столбец табл. ВПЗ. Итерация симплекс-метода по отнон1епию к табл. ВПЗ приводит к табл. ВП4. Используя относительные оценки из табл. ВП4, можно заключить, что пе найдется сети у, для которой (О, О, 1, 1, О, 7) ° [у1— — 1) ( О. Отсюда, связывающее неравенство имеет вид уз + уа— — 7 = У1 ) О, и 8',„,„= О.
Действуя обычным образом, для нахождения связывающего неравенства и 8,'„„во 2-и периоде можно было бы снова провести вычисления, ьак в табл. ВП1 — ВП4. Затем можно было бы выбрать 8555„=пип(85 5„, О~мах) и соответствующее ему связывающее неравенство. Однако в нашем примере 8;иа„= О, и поэтому не надо повторять вычисления. Запишем неравенство уз + у, — 7 =- у1 ) 0 Таблица ВП4 л', 1 О 8! 82 83 84 85 Х1 3 8! 82 0 84 85 14! 1 Таблица ПЗ Таблица П2 1 — и ! — и2 — из — и4 — и5 81 82 33 84 85 1 У! У2 Уз У4 У5 81 Таблица ВП1 1 О 8! 12 зз 84 85 88 Таблица ВПЗ 1 0 8! 82 3 84 85 8! 82 зз 84 85 у 1 8! 82 0 М 2 1,1 1 У! Уз Уз У4 Уз 82 Таблица ВПЗ О 81 82 88 84 35,18 1 1 — и! — из — с! — и4 — из 11.5.
СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТЕЙ 263 в низкнюю строку табл. П1. Получаем табл. П2. Применяя к ней итерацию симплекс-метода, получим табл. ПЗ (за исключением ниннтей строки). Теперь улучша1ощим столбцом является столбец под переменной ню т. е. [О, 1, О, О, 0). Чтобы найти О„„„и связывающее неравенство, повторим вспомогательную часть, решая задачу (12) с уа — — [5, 4, 3, 4, 2] н у, = [О, 1, О, О, 0[.
Здесь учитываются оба периода, и связывающее неравенство, которое оказывается вытекающим из требований в 1-м периоде, имеет вид гг = — 8+ уг+ уз+ уз) 0 а Огааа '=- 1 Полученное неравенство иг ) 0 корректируется и записывается в нин1нюю строку табл. ПЗ. Применяя итерацию прямого симплекс-метода, получим новую сеть [5, 3, 3, 4, 2). Она представлена в табл.
П4. Таблица П4 Таблица Пб 1 — и1 — иг — и1 — из — из 1 — и — иг — 51 — и4 — из У1 Уг Уз У4 У5 из Уг Уг Уз У4 У5 и4 Затем переходим к вспомогательной части, где получается неравенство гз = — 9 + Уз + Уз + Уз ~ ~Ог которое после корректировки записывается в нижнюю строку таблицы П4. После итерации симплекс-метода табл. П4 превращается в табл.
П5. Вспомогательная часть формирует неравенство У4= =- — 10 + у, + у, + у, ) О, которое после корректировки записывается в ниншюю строку табл. П5. Применяя итерацию симплекс-метода к табл. П5, получим табл. ПО. Вспомогательная часть дает неравенство уз = — — 7+ + уг + уг )~ О, которое после корректировки записывается в нижнюю строку табл.' Пб.
Прн переходе от табл. П5 к табл. Пб переменная — из изменяется на из (так как переменные и1 не ограничены по знаку). Гл. и. многопгодуктовые потоки После итерации симплекс-метода табл. Пб превращается в табл. П7, в которой нет улучшающего столбца. Следовательно, найдена оптимальная сеть. Таааица ПТ вЂ” зз — аз — ш — зз — зз Уз Рз Уз Уз Уз из Табаица'Па — — зз — зз — аз +из Рз Уз Уз Уз Уз зз ГЛАВА 12 ПОТОКИ В НЕПРЕРЫВНОИ СРЕДЕ Содержание этой главы является результатом совместном работы д-ра Р. Е. Гомори и автора; изложение осуществлено автором.
Все результаты получены впервые, поэтому они излагаются здесь в предварительной форме. Положительные отзывы па эту работу (если они будут) следует адресовать как д-ру Гомори, так и автору, но ответственность за все ошибки и опечатки должна быть целиком возложена на автора. Читателям, интересующимся функциональным анализом, рекомендуется предварительно ознакомиться с з 12.3, а затем читать 5 12А и $12.2. 12А.
Локально минимальные разрезы В этой главе будет введено несколько новых понятий, ранее не встречавшихся в литературе. Они имеют важное значение для аппроксимации непрерывной среды конечной сетью, что составит содержание з 12.3. В этой главе будем рассматривать только леориептированные сети.
Две дуги будем называть соседними дугами, если они имеют общин узел. Два разреза (Х, Х) и (У, У) будем называть соседними разрезами, если а) каждая дуга разреза (Х, Х) либо принадлежит разрезу (У, У), либо является соседней с некоторой дугой из (У, 1'); б) такое же отношение выполняется для каждой дуги разреза (У, У). Рассмотрим сеть, изображенную на рис. 12.1, где разрезы обозначены пунктирными линиями: (Х, Х) = (Ам Аа, Азз, Азз) (1' 1 ) = (Азм Азз А,з), (Е 2) = (Азз Азз) (И', И')=(Азз Азз Ам). Будем использовать символ для обоаначения соседства двух дуг. ГЛ.
12. ПОТОКИ В НВПРЕРЫВНОЙ СРВДЕ 266 Разрезы (Х, Х) и (1', У) явля!отся соседними, так как 1) Лы и А,;, принадле»кат обоим разрезам; 2) Л,г- Л„и А,г- Лге где Ам и А„принадлежат (Х, Х), Агг принадлежит ()', У). Разрезы (1', )') и (И', И') не являются соседними, так как дуга Аы из (1', т') не является соседней пи с одной из дуг разреза' (И!, И'). Аналогично можно убедиться, что разрезь1 (1', У) и (7, 2) являются соседними, а разрезы (Х, Х) н (А, У) таковыми пе яв( ! ! ! (У, У] (й( 1У] Р и с. 12А.
ляются. Не нвляются соседними также и разрезы (Х, Х) и (И!, Й), (А, 8) и (И', й). В дальнейшем нас будут интересовать разрезы, разделяющие !»'» и !»'1; такие разрезы, как (И', Й), рассматриваться не будут. Под термином «разрез» будем подразумевать разрез, разделяющий 1"»", и Л'1. Будем называть разрез локально минилильным, если его пропускная способность меньше или равна пропускной способности всех соседних разрезов. Например, пусть все дуги сети, нзобран.енной на рис.
12.1, имеют одинаковые пропускные способности. Тогда (Я, Е) является локально минимальным разрезом. Разрез, состоящий из одной дуги Лг», также является локально минимальным. Минимальный разрез, определенный в гл. 8, является, конечно, локально минимальным разрезом, но обратное неверно. Например, ясно, что А㫠— минимальный разрез, разделяющий Л", и !»'1, а разрез (2', А) — локально минимальный разрез, но не минимальный. Следовательно, по нашей терминологии минимальный разрез 12.2, сети с пРОпускными спОсОБнОстями узлов 267 является в некотором смысле абсолютно минималытым разрезом. Чтобы разрез был минимальным, необходимо, но но достаточно, чтобы отт был локально минимальным.
Рассмотрим все разрезы, разделяющие узлы тт', и Атт. Отношение соседства меткду разрезами аналогично попятито расстояния между точками плоскости. Для заданной точки а можно указать то точки, которые находятся па расстоянии е от точтти а, эти точки назоееч е-соседними для а. Аналогично, для заданного разреза. можно указать те разрезы, которые являются для него соседними. Как известно, для того чтобы функция ~ (х) достигала абсолютного минимума в точке а, необходимо, чтобы ~ (х) — т' (а) ~ О для ~ х — а ~ ( е.
Аналогично, для того чтобы разрез был мннилтальным, необходимо, чтобы он был локально минимальным. В функциональном анализе имеется понятие локального минимувта. Чтобы ттайти абсолютный минимум функции, надо сравнить все локальные минимумы. В теории сетевых потоков ищутся минимальные разрезы, отделяющие источник от стока. Метод расстановки пометок для нахождения максимального потока (а следовательно, и минимального разреза) позволяет находить абсолютный минимум, не используя понятия локального минимума. В последующих параграфах этот факт будет изучаться более подробно. 12.2. Сети с пропускными способностями узлов В гл.
8 каждой дуге была поставлена в соответствие пропускная способность; это число указывало максимальную величину потока, который мотттно пропустить по этой дуге, В узлах никаких ограничений па поток пе накладывалось, за исклточонием условий сохранения. Теперь будем считать, что узлы имеют пропускные способности, а дуги их не имеют.
Эта модель нам понадобится в $ 12.3. Рассмотрим сеть, состоящую иа узлов Атт н дуг А;;, связывающих тт'т и Х;. Каждому узлу тттт поставлена в соответствие его пропускная способность нтт — действительное число, указывающее максимальную величину потока, который можно пропустить через этот узел. Пусть хы — поток по дуге Атт из узла Атт в узел ттт,. В силу условия сохранения потока в каждом узле величина потока, пРоходЯщего чеРез Узел Атть Равна ~ хы, обозначим ее хть Тогда задача о максимальном потоке в сети с ограничениями па.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
