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

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

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

наной смысл в вашем решении имеют луги. б) Решите эту задачу при А»=3, г;=3, г>-— -'2, «а=4, т=! (салфетки, послан- ные в срочную прачечную, готовы па следую!ций день), л=2, р=(6, 7=6 и л=-З, . 157 Комментарии и ссылки используя любой метод. Докажите, однако, что ваш ответ оптимален. Какова его стоимость? 10 (задача о многопродуктовом потоке минимальной стоимости [То|).

Дана потоковая сеть, в которой выделены д пар источник — сток (зс, Г?) вместо одной такой пары. Из зз в (з должен проходить поток величины гз, )с=!... д, рассмзт. риваемый как поток продукта й. Для каждой дуги (1, /) задана пропускная способность Ьг, которая является границей суммарного потока всех продуктов по ориентированной дуге (сц 1), н стоимость сгг единицы суммарного потока по этой дуге. Все потоки по ориеспнрованньш дугам положительны.

Залача состоит в нахождении допустимага потока минимальной стоимости. а) Сформулируйте эту задачу в терминах вершин и дуг. Сколько получится строк и столбцов? Что будут представлять собой подзадачи, если использовать метод декомпозиции Данцига — Вулфа? б) Сформулируйте зту задачу в форме дуг и цепей. Сколько получится строк и столбцов? В чем будет состоя гь задача выбора столбца, если используетси модифицированньсй симплекс-алгоритм? н) Покажите, что формулировки а) и б) эквивалентны. 11 (чадача об остовнам дереве с пропускными способностями [О)[).

Даны пол. иый неориентированный граф 6=(У, Е), симметричная матрица расстояний [дсу[, целочисленная «скорость порождения транспортного потока> А; для каждой вершины с ~ У, целочисленная пропускная способность В и вылелениая вершина з, называемая центральной.

Требуется найти остовное дерево минимальной стоимости " суммарным траиспортныч патоном па каждому ребру, не превышающим В, в тредположении, что из каждой вершины ! в с движется поток Аь Покажите, как ?сшить частный случай этой задачи, в котором все А г равны 0 или 1 и В=1, используя алгоритм решения задачи о потоке минимальной стоимости. Комментарии и ссылки г[апустимый отиосигельпо залечи алгоритм ЦИКЛ лля задачи о потоке мннимальсой стонмо:тп взят из работы К![ К1есп М. А Ргспш) Ме(!соб (ог Мспнпа! Сои Г!осчз, Мапайегпеп! 5ссепсе, 14, ?(а. 3 (сыочешЬег 1967), 205 — 220. (хорд и Фалкерсон прнписывз от теорему 7.2, из которой следует алгоритм ДО.ТРОЙКА, У. Джуеллу, Р. Басакеру и П. Гоуэну и М.

Айри, опубликовавшим :е в технических отчетах в 1958 — 196! годах. ГГ[ Гогд Е. 9., Лг, ГиРкегзап О. 9. Г!осчз !п Ме1магйз. Рппсе1оп, (и'. Л: Рпп. се!оп Юьбчегьйу Ргсзж 1962. [Имеется перевод' Фарп Л. Р., Фалксрсон Д. Р. Потоки в сетях.— Мл Мир, !963.1 =ели в задаче о циркуляции минимальной стоимости с верхними и нижними раницамн дуговых потоков используется прямо-двойственный алгоритм для сомбинаториализацин стоимости, то в результате получается метод дефекта Гн| Га!йегзоп О. К.

Ап Осью(-К)Вег МеГпод 1ог М)п!ша! Сом Г(осч Ргоыешз, 3. 5!АМ, 9, Мо. ! (!96!), 18 — 27. )тот алгоритм полностью рассматривается нак в [ГГ|, так и в следующей иниге 1оулерж Еа| $.асч!ег Е. 1.. СогпЬспа1опа| ОрИгпызИоп: Хе1«чагйз апй Ма1гоЫз. Нои, КшеЬаг( 8 н?(пз(осс, Меж Уаг(с: 1976. 7казанную задачу о циркуляции минимальной стоимости можно свести к задаче г потоке минимальной стоимости и решить ее, используя алгоритм ЦИКЛ или ТОСТРОЙКА (см, задачу 8). Этот метод предложен в нелавией работе Заде: Ха![ Хайей И, А сйшр!е Айегпа1)че 1о !Ье ОеРо1- Ксйег А!йаг!!Ьш, Тесйсс!са! Верог! (чо, 35, Пер!. о( ОрегаВопз (? езеагсЬ, 8(асбагб 1)п счегзйу, Мау 31, 1979 Гл. 7.

Задача о потоке минимальной стоимости В следующем отчее приведена множество взаимосвязей между симплекс-алга. ритмом, двойственным симплекс-алгоритмом ч методом дефекта для задачи о патоне минимальной стоимости )Ха2) Хадей ЬЬ Ь)еаг-Ей»с!ча)есссе о| «(е(счогй Р)ов А|йопйпп, Тес|!исса! Веро«( )цо 26, Пер! о1 Орега|соп«резеагсй, 51ап!ог6 Цпйегзцу, ОесешЬес 1, !979 Вопр«к а времени рабаты алгоритмов, решающих задачу о патоне чннимальной стоимскти, проблематичен С теоретической гочки зрения Эдм снзсач н Карпом показано, что существует полиномиальный алгарсюч длн этой задачи, т е алга.

ритм, число шагов которого не превсккодит полинома от числа авоичных разрн. дов в описании задачи (Более строга это паннтие будет определена в следующей главйд (ЕК) Едгпопбз 3., Кагр В. М. ТЬеоге1|са11гпргочешеп(з )ст А|йопВппсс ЕНксепсу !аг Мс1»сагй Р!ос» РгоЫешз. 3 ЛСсИ, 19, Мо. 2 (Лргй 1972), 248 — 264. Они модифицировали вариант алгоритма «ЗОСТРОЙКЛ, используя четод «мас- штабирования», который можно осень грубо описать следующим образам Вна. чапе решаетсн приближение нулевого порядка длн исходной залачи, а катаром пропускные способности прийлижаются |.разрядными дваичнычи числамн О нли 1 Полученный поток умножается на 2, и решается более хорошее прибли- жение исхолной задачи, в котором для представления пропускных спскобносгей используются 2-разрядные лваичные числа, и т.

д. В следующей главе йудсс по- казано, что лсобусо задачу ЛП можно реши»с за полнпомнзльное врем н, так что теоретическое солержание метода масштапиравания Эдмаидса и Карпа перекры. вается этим резулшатом, С практической точки зрения ни месил машитайирааа- нин, нн более апщнй полиномиальный алгоритм для ЛП (метод эллипсаидов) не нвляются серс езными претендеспами на роль плноолее эффективных алсарит. мов для зада и о псстоке минимальной стоимости, пс крайней мере в насшящее время. При сравнении эффективности различных разливаний алгоритмов ЦИКЛ, ЛОСТРОЙКА, сии~лене.алгоритма, двойственного симплекс-алгоритма, алго- ритма дефекта и даже АЛЬФАБЕТА в применении к разлн сным трансформациям задачи Хичкока нам приходится полагаться на практические резсльтаты С'ч., например, )ВОК! Вагс В.

5., О)очес Р., К||пйгпап О. Ап |шргаче6 'сгегз)осс а1 йе Ои|-о|- КсВег Мейой ап6 а СогпрагаЦче сйпбу о| Согпри|ег Соде», Май. Ргой., 7, Гйо 1 (Апйиз( 1974), 60 — 86 (ОКК) 01очег Р., Кагпеу О., К!спдшап О. |гпр!егпеп|а1соп ап6 Согпри|аИопа| Сагпрапзопз о1 Ргнпа|, Она|. ап6 Рпгпа| Она| Согпра|ес Собес 1ог М!псгпигп Соз1 Ь|е1вогй Р1ов РгаЫешь, "4е)ссосйз, 4, Ко. 3 (!974), 19! — 2!2. )Ми) Мийеу Л Ч. Тез1!пй о! а Ьагйе-Зснсе с|е(счссгй Ор|ппсга1соп Ргойгагп, Май.

Ргой., 15, Ь!о 3 (Ь~ачесссЬег 1978), 291 — 314. Поиск такого варианта алгоритмов ЦИКЛ. ЛОСТРОЙКЛ ли АЛЪФЛБЕТА, касорый имел бы ссалиссамссальссую оценку числа итераций, не зависянсуса ат стоимостей с пропускных спскабностей астаегся важной агкрслтай проблемой в мочент написания этой книги (Эсат вопрск нано поставлен в (ЕК).) Мы у»кс достигли подобной пели лля алгортча Лейкстры и получили аналогичный результат для алгоритча Форда — Фалкерсанл. 1'о что зля обеспечения хорошеса поведения алгоритмов нужно ограничиваю их выбор, показывают патологические примеры Заде (Ха31 2адеЬ !4 Л Вад Б)е(ваг1с РгаЫегп |ос йе сВгпр!ех Мейоб ап6 Ойег Мспс, пшш Соз1 Р1ов А|йагййпз й(ай Ргой., 5, !4о.

3 (ОасегпЬег 1973), 255 — 266. В зсой райоте Заде приводит примеры чоднйнцираванных задач Хичкока, сребующих экспоненциального числа итераций прн применении определенных вариан сов алгоритмов ЦИКЛ, ЛОСТРОЙКА и ЛЛ|»ФАБЕТЛ В работе, ука. ванной ниже, Заде приводит пример залачи о посоке минимальной стоимостщ Коммгнтаргт и ссылки для кторой некоторый варишп «лгоритма ЦИКЛ может потребовать сколь угодно болыиого числа итераций, аналогично примеру Форда и Фалкерсона, в котором алгоритм пометок не останавиивзегся (2а4! Хабей л( Маге Ра(йо(орса( Ехатр!ел (ог Ке1вогй Г(олч РгоЬ(егпз, Ма1Ь Ргой., 5, Но 2 (Ос1оЬег !973) 2!7 — 224 Форд н Фалкерсон приггисываю~ йюрмулнронкч тдачн Хичкока нескольким лю.

днм, включан естесгвенно, Хн ~кока (Н() Нйспсасй 1' Ь ТЬе О~з(пвп(~ап о( а Ргоаис( 1гоги Бечега( Ьоигсез 1о л((ппе. тот ЬосаВНез, 3 Май РЬуь. 20, ((о 2 (Арп! 1941), 224 — 230 и Т. Купмансз. А Н Толстого, Л. В Канторовича и М. К. Гавурина, сформулировавших эту задачу примерно в'адно и ю же время Если все запасы и по. требности в задаче Хичкока равны единице, получаем тадггчу а назначениях Лл. горитм ЛЛЪФАБЕТА, часто называемый проста прямо. двойственным методом для задачи Хичкока, является обобщением венгерского метода Куна, названного гак в связи с тем, что он опирается на один резулыат Эгервари (см, задачу 6 в гл 6). (Ки) КиЬп Н.

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

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