Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 41
Текст из файла (страница 41)
Для нее определяются такие же харак- 25! Алгоритм дефекта теристики, как и для всех остальных дуг, а именно ей приписываются тройка пропускная способность-стоимость (У, 1., с) и двойственные переменные нз и пгп. Конфигурация полной сети, образованной после введения возвратной дуги, дана на рис. 3.10.
Рис. 3.9. Сеть с одним источником и одним стоком, Рнс. 3.10. Структура и изображение сети. Физический или экономический смысл величин У, Ь, с, нз и ззг для специальных примеров, решаемых с помощью алгоритма дефекта, будет пояснен ниже. ЗА1. ТРАНСПОРТНАЯ ЗАДАЧА Предположим, что имеется пг складов и и магазинов. Из складов в магазины должен быть доставлен некоторый товар.
Предложение, каждого склада и спрос каждого магазина известны. Задача заключается в нахождении такой схемы перевозки товара из складов в магазины, при которой общие затраты на транспортировку минимальны и спрос каждого магазина удовлетворяется. Пусть 1н †количест единиц товара, транспортируемого из г-го склада в /-й магазин, аз †предложен 1-го склада, Ь| †спр 1чго магазина, сп †затра на транспортировку единицы товара из г-го склада в 1чй магазин. о В действительности переменные и, и мг являются не характеристиками дуг, а единственными характеристикамя узлов.
Онн были введены здесь только для ясности н полноты изложения. Глава 3 Задача формулируется следующим образом: ю и минимизировать '~'„~~)' С,.Д! ! ! / ! при условии, что а ~~~~~1!1< а„(= 1,2,..., т, 1 ! ~~~ 1!1 ~~ Ь,, 1= 1,2,..., а, ! ! 7!1ЪО для всех ! и 1. Для того чтобы решить транспортную задачу, используя алгоритм дефекта, нужно выполнить следующие процедуры. 1. Существует ровно т источников и а стоков, или т начальных узлов и и пунктов назначения. Из каждого источника Сток ИстОчНИК Рнс. 3.1!. Открытая транспортная сеть, во все стоки может быть доставлено в общей сложности не более а! единиц потока.
Конфигурация сети для данной задачп изображена на рнс. 3.11. Такая сеть называется двусторонней. 2. Для каждой дуги в качестве тройки пропускная способность-стоимость (К Е, с) взять тройку (оо, О, сн). 3. Ввести главный источник з и главный сток 1 и завершить построение сети согласно следующим правилам: а. Для каждого источника ! построить дугу, ведущую из главного источника в !.
Определить для этой дуги тройку пропускная способность-стоимость (У, Е, с) = (а!, О, О). 233' Алгоритм деФекта б. Для каждого пункта назначения 1 построить дугу, ведущую из 1 в главный сток. Определить для этой дуги тройку (У, Е, с) = (оо, Ьь О) 4. Построить дугу (1, 3) и определить для нее тройку л л (У, Е, с)=( Е Ьы Е Ьь О).
У-1 У-1 5. В качестве начальных значений всех потоков и двойственных переменных взять ~и=О и ил=О (А=1, 2, ..., (лт+и+2)). Отметим, что возвратная дуга (1, 3) находится в состоянии рь так как сы=О и поток по ней меньше нижней границы. Следовательно, в начале работы алгоритма возвратная дуга всегда является дефектной. 3,11.1. ПРИМЕР ПОСТАНОВКИ ТРАНСПОРТНОИ ЗАДАЧИ Предположим, что задана следующая матрица условий Пункт назначения 4 5 6 т .ч — Спрос с, Г = 1, 2, 3; «1 1=4,5,6, T Источник 2 3.12.
ЗАДАЧА О НАЗНАЧЕНИЯХ Задача о назначениях возникает в том случае, когда имеется д пунктов назначения, в каждый из которых требуется доставить по 1 единице продукта из источников, число которых также равно д. Из каждого источника в некоторый пункт назначения можно послать только 1 единицу продукта. Стоимость транспортировки единицы продукта из каждого источника в каждый пункт назначения известна. Задача заключается в минимизации общих затрат на транспортировку. Пусть ~п — число единиц продукта, транспортируемых из источника 1 в пункт назначения 1, 3; — предложение 1-го нсточни- На рис.
3.12 изображена сеть для поставленной задачи. Значе- ния искомых переменных 1п могут быть найдены с помощью ал- горитма дефекта. Глава 3 ка, Ьт — спРос 1сго пУнкта назначениЯ, сп — затРаты на тРанс- портировку 1 единицы продукта из 1-го источника в чй пункт назначения. Сеть с ограниченной пропускной способностью Источник < о ~л~ Пункт назначения Гпавн источ вный ок Рнс. 3.12. Полная транспортная сеть. Задача линейного программирования в данном случае выглядит следующим образом: минимизировать ~~~~ ~~1' ~,усм т-з у-т цри условии, что ~м(з;=1, 1=1,2,...,д, Х т' 1 Х ~» ) Ьу = 1, 1= 1,2,..., д, з ~о~ ~0 длЯ всех 1,1. Фактически задача о назначениях является специальной транспортной задачей, в которой лт=п=г1 и ат=Ьу= 1 для всех источников н всех пунктов назначения. В данной задаче матрица условий всегда является квадратной, а общий спрос равен общему предложению.
Следовательно, всегда существует максимальный поток. Правила построения сети такке же, как и для транспортной задачк при данных огранкчениях. Алгоритм дгректи 3.12.1. ПРИМЕР ПОСТАНОВКИ ЗАДАЧИ О НАЗНАЧЕНИЯХ Рассмотрим задачу о назначениях со следующей матрицей условий: Сток 4 5 б ч — Спрос тЬ ( ' Источник Предложение На рис. 3.13 изображена сеть для данной задачи.
Искомые переменные )н могут быть найдены с помощью алгоритма дефекта. Сеть с ограниченной пропускной способностью еныи к Глаан источ <З,З,О1 Рнс. 3.13. Сеть н задаче о назначениях. 3.13. МАКСИМАЛЬНЫЙ ПОТОК В СЕТЯХ С ОГРАНИЧЕННОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ Предположим, что для сети с ограниченной пропускной способностью требуется определить максимально возможный поток из источника з в сток Е Верхняя и нижняя границы потока по каждой дуге заданы. Для решения этой задачи с помощью алгоритма дефекта необходимо выполнить следующие процедуры: 1.
Построить дугу (1, з), для которой (У, Е, с) = (оо, Π— оо). 266 Глава 8 2. Нижние границы для всех оставшихся дуг положить равными нулю, а верхние границы — максимальным пропускным способностям дуг: х,ц=О для всех 1~1 и всех 1Фз; Уц равна максимальной пропускной способности дуги (1, 1) для всех )~з, 3. Стоимости всех оставшихся дуг положить равными нулю: сц=О для всех ЕФ1, (чьа 4. Потоки по всем дугам н значения всех двойственных переменных положить равными нулю: 1ц=О для всех й 1'; из=О для всех и. Отметим, что поскольку потоки по всем дугам нулевые, то каждая дуга, кроме (1, з), находится в состоянии Р (является бездефектной).
Дуга (1, з) находится в состоянии б~ 4является дефектной). 5. Выполнять алгоритм обычным образом. ЛЛ4. ЗАДАЧА О КРАТЧАЙШЕЙ ЦЕПИ Иногда требуется найти кратчайшую цепь из источника з в сток Е При этом «стоимость» дуги соответствует времени или расстоянию. Эта задача может быть решена следующим обра- зом. Пусть А~ — расстояние от узла 1 до узла 1 (или соответст- вующее время). 1.
Построить новую дугу (1, з), для которой (У, 1., с)= =(1, 1, О). 2. Для всех остальных дуг положить (У, 1,, с) = (1, О, А~) 3. ДлЯ всех 1, 1 и А положить Гц=О, пь=О. КРатчайшаЯ цепь мз з в г определяется по окончаний работы алгоритма дефекта. Она состоит нз всех дуг, поток по которым равен 1. Возможна также другая формулировка задачи о кратчайшей цепи в виде задачи о потоке минимальной стоимости.
Для этого нужно: 1. Ввести дугу (1, з), для которой положить (У, 1., с)=(1, О, — оо), 2. Для всех остальных дуг положить (У, Ь, с) = (1, О, А;). 3. Для всех й 1 и А положить ~ц=О, пь=О. В результате ра- боты алгоритма через сеть будет проходить только 1 единица. потока. Кратчайшая сеть будет состоять из дуг, поток по кото- рым равен !. ВЛЗ. ЗАДАЧА О ДЕРЕВЕ КРАТЧАЙШИХ ЦЕПЕЙ В этой задаче определяются кратчайшие цепи из произвольного узла А во все остальные узлы сети или в некоторое заданное множество узлов.
Задача может быть решена с помощью следующих процедур: 25т Лггоритге де екта 1. Для каждово узла, отличного от й, построить дугу, ведущую из этого узла в узел Й. 2. Для каждой такой дуги положить (У, Е, с) = (1, 1, 0). 3. Для каждой дуги (г, 1) сети положить (У, Е., с) =(оо, О, А~), где г(п — расстояние от узла 1 до узла 1. 4. Положить ~и=0 для всех дуг и пл=О для всех узлов. 5. Построить возвратную дугу, для которой (У, 1„с) =(Ф, тз, О), где Ф вЂ” число дуг, добавленных к узлу й. Данный метод позволяет находить дерево кратчайших цепей.
Цепь из узла й в произвольный узел (ФЙ, принадлежащая этомудереву, короче любой другой цепи из А в г. Дугами этого дерева являются все дуги, по которым поток, полученный в результате работы алгоритма дефекта, положителен. Данная задача отличается от задачи о кратчайшем остове, в которой мннимпзнруется сумма длин дуг дерева. Следует отметить, что описанная, процедура позволяет находить дерево кратчайших цепей, но, вообще говоря, не позволяет минимизировать общую стоимость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
