Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 74
Текст из файла (страница 74)
Набор 2 Данный набор состоит из одной карты, которая указывает число узлов и число дуг в сети в формате (2НО). Набор 3. Число карт в данном наборе равно числу дуг в сетя. Для задач 1 — 5 с каждой карты считываются следующие величины: 1) номер на. чального узла дуги; 2) номер конечного узла дуги; 3) значение, приписанное дуге. Форма (4Х, 16, 110, Р10.2). Для задачи 6 с каждой карты этого набора считываются следующие величины: !) номер начального узла дуги; 2) номер конечного узла дуги; 3) пропускная способность дуги; 4) начальный ноток по дуге (должно быть 29' МУЬТЗН КЗНОИТ М1НЗРА МАХЕ 1.0 ТЕАБАЬ ОКА1.О МАХСАР ОЕНРАК Алгоритм Дейкстры решения задачи о кратчайшей цепи Алгоритм решения задачи о многополюсиой кратчайшей цепи Алгоритм нахождения К кратчайших путей между заданным источником и заданным стоком Алгоритм решения задачи о кратчайшем остовном дереве Алгоритм решения задачи о максимальном потоке Алгоритм ветвей н границ решения задачи коммивояжера Алгоритм дефекта Алгоритм нахождения цепи с максимальной пропускной способностью между всеми парами узлов Алгоритм йенсена и Бомика решения сетевых задач с выигрышамн и проигрышами Приложение выполнено условие сохранения потока).
Если поставлен знак пробела, то все начальные потоки полагаются равными нулю. Формат (4Х, !б, 110, 2Р!0.2). Для задач У вЂ” 11, при решении которых используется алгоритм дефекта, с каждой карты считываются следующие величины: 1) номер начального узла луги; 2) номер конечного узла дуги; 3) верхняя граница потока по дуге; 4) нижняя граница потока по дуге; 5) стоимость прохождения единицы потока. Формат (215, ЗР10.2). В задаче 12 данный набор состоит из трех разделов.
Раздел 1: 1) начальный узел дуги; 2) конечный узел дуги; 3) длина дуги, Формат (3!!0), Для каждой дуги сети набивается одна карта. Карты в этом разделе располагаются в порядке возрастания номеров конечных узлов. Раздел 2: 1) К, ХЬ, 1МАХ. Формат (4Х, 315). К вЂ” заданное число различных длин путей, !МАХ вЂ” максимально допустимое число итераций в алгоритме двойного поиска, НЗ вЂ” начальный узел всех К искомых путей. Раздел 3: 1) 14Р, РМАХ. Формат (4Х, 215).
НР— конечный узел всех К искомых путей. РМАХ вЂ” максимальное число искомых путей между узлами И5 и ИР. Замечание: если требуется последовательно решать задачу 12 для различных источников и(или) стоков, то надо заменять только разделы 2 н 3 набора 3. В задаче 13 данный набор состоит из двух разделов. Раздел 1: 1) начальный узел дуги; 2) конечный узел дуги; 3) нижняя граница потока по дуге; 4) верхняя граница потока по дуге; 5) стоимость прохождения единицы потока; 6) коэффициент выигрыша дуги.
Формат (2110, 4Р10.2). Для каждой дуги сети набивается одна карта. Раздел 2: 1) источник, сток, !РК!НТ, ОУТРЕ0%. Формат (315, Р10.2). 1РК1НТ вЂ” опция РК1ХТ (О для узкой печати, 1 для широкой печати, 2 для сверхширокой печати), 0()ТРАО% — требуемый выходной поток. Набор 4. Для всех задач данный набор состоит из одной карты, содержащей слово 'РЕ(411' в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец программы сетевой оптимизации (конец всех входных данных). Содержание пакета. Данный пакет содержит 9 подпрограмм, реализую. щих следующие алгоритмы: 1.
Алгоритм Дейкстры решения задачи о кратчайшей цепи из источника в любой другой узел сети. Приложение 2, Алгоритм решения задачи о многополюсной кратчайшей цепи. Позволяет находить кратчайшие цепи между всеми парами узлов сети. Основан на применении трехместной операции.
8. Алгоритм построения кратчайшего остовного дерева сети. 4. Алгоритм нахождения максимального потока в сети с ограниченной пропускной способностью, основанной на применении процедуры расстановки пометок. 6. Алгоритм ветвей и границ решения задачи коммивояжера. 6. Алгоритм дефекта нахождения оптимальных решений транспортной задачи, задачи о перевозках, задачи о назначениях и т. п. 7. Алгоритм нахождения К кратчайших путей между любыми двумя узлами сети. Циклы допустимы. 8.
Алгоритм нахождения цепи с максимальной пропускной способностью между всеми парами узлов сети (предложен Ху Т), основанный на применении модифицированной трехместной операции. В сети, каждая дуга которой имеет ограниченную пропускную способность (заданы верхние границы), цепью с максимальной пропускной способностью из узла А в узел В называется цепь, у которой минимальная величина пропускной способности дуги является максимальной для всех цепей на А в В. 9. Алгоритм йенсена и Бомика нахождения потока минимальной стоимости в обобщенных задах (в задачах на сетях с выигрышами и проигрышами). Генерирующие циклы допускаются.
Алгоритм является сходящимся за конечное число шагов. Литература: РИйз1га Е. ЪЧ., А ХО1е оп Тч«о РгоЫешз еп Соппес((оп ч«1133 С«гарйз, А«илх Ми(йе 1, 269 — 271 (1969); Нп Т. С. 1С1ейег Ргойгашш1пй апб 1»)е1могк г(оч«з, Абб(зоп-)(гез1еу, 1969. М31М РЮШЗАМ ПХИЖКЕХОМ ЖОРЖ(50»50)»А(50»50)»ЬАВ(50)»ЬР(50) ЖРВ(50),РЬ(50)» 1В1010 (50» 50) «СОАВ(50), ть(50) СОИМОВ В(50да) ПЬ0,50) »ЮНОЮ(50) »СОМА(50) е ЮЖЖ(50» 2) е 1ПР(50»50)»ВР(50)»1МРВЮ~50»5) МОРИВ 1ИР ° 1ВРЖЬ«М»В,ИЗХ ЖапттАХМЮЖ (МОРЖ»А»В)»»ЬА6»ЬР»ЮВПВП) е (ЖРВ»РЬ»СОЬСВП) е (3ПС1П»ПР) 1, (ВСАВ,ИЬВР) 1ЖВ(ЗВАЛ П12Х«'»012К'/,МРЮ/ГИРЮ'/,3ШИВ/'ИВХР'/,ИАХР/'МАХР~/~ВИРР/ 1»тВРВ»/,ОКП/»ОКАЬ»/,ЖХ12/'ЖХ12»/,ПЮ ХВЧМСВВ РВВП/»РЖЗШ»/,ВРЮ 1ИАИСЖВ Кызт/'Кант'/,ИСВР/'ИСВР»/,СВЖР/»Шат'/ 60 Ржап(5»5)трю 5 РОРМАР (Ач) 1Р(1РВО,ВС Вххт) ю та 90 1Р(ЬВРО ЖС П1ЗК 60 Ю 10 1Р(1РВО ВС мтбс 60 20 15 1Р(1рю ВС мптВ са 20 20 1Р(п»ю ВС.МЗЖР 60 20 25 1Р(1РЮ ВС РВРВ 60 то 50 1Р(1РРО Вс Окзь) 60 20 ио 1Р(1РВО КС.ХВВР) 60 ю Ф5 1Р(1РВО ЖС МСВР) 60 то 50 1Р(1РВО жй.окжт) 60 ю 55 НР1 Ж(6,2) 2 РОВМАт(»СМХПЖМИХРХЖП АХЙОВРРВМ» е* ЖХКСПР10М РЖРЗПВАИЖВ») са то 90 10 САЬЬ П12КА 60 20 60 15 сАьт мстиы 60 Ю 60 20 САЬЫПМЫ»А 60 '10 60 25 САЬЬ ИЗХР10 СОЮ 60 50 сзьь тпзпзь СОЮ 60 Приложение ФО САЬЬ ОНАШ ВИАР(5,5) БРНО 60 ТО 60 45 САЬЬ ХЗНОЕ2 ВОЮ 60 50 СА22> МАХСАР 60 '20 60 55 САЬЬ ЗЕБРАХ ВЕАО(5,5) БРНО ВОЮ 60 90 СОВУ(ЗОБ ВЮР ЗЮ С ВСБВОСТ1ЕБ В12ХА ВХМЗИВХОИ ИОВЕ(50 50) >А(50«50) > ЬАВ(50) е ЬР(50) «ЕРВ(50) «РЬ(50) в 1ИХСХО(50 50) >ЯСАМ~50),ТЬ(50) СОМЮИ 6(50«50)>В 50>50)>ЮИСВО(50)«СОШЮ(50)>ТЕБЕ(50«2)е 1СР(50«50)«ЕР(50)>1ИУБХС(50 5)«БОВЕН ХБУ«ЬВУИЬ«М«И«МАХ ЕВСХУАХВИСЕ (ИОВЕ>А>6) ° (ЬА4>ЬР«ВОУСЗВ)э(ЗРЗ«РЬ«СОШЗВ) ° (И1СХВ>ЪР) 1>(ВСАИ>ТЬ>Ю) 1БЗМСБВ РЕЮ/>РЕЗВ«/~БРНО Х061САЬ ЬР ВИАВ(5 >100)ЮВЗВ 100 ЮВМАТ(2110,210.0) С С 1И1ТХАЬХЖВ АВС ВХВТАИСЕ МАТВХХ С ВО 1 11 >ЮВМЗ ВО 1 Ю = 1,БОВЕН 1 В(1,2) 1,В10 С ВЕАО ТНВ ХИРСТ ВАТА С 2 ВИАР(5 120) ЗРВО«1«2>7АЬ 120 УОВМАТ(АН> 16, 110, У10.2) 1У(ВРИО БО РБЗВ) Ю Ю 10 5 В(1, 1) 7АЬ 60 Ю 2 10 ЬР(1),ТВОИ МВ1ТБ (6, 500) 500 ЮВМАТ(1Н1) ИВХТВ (6, 600) 600 УОВМАТ(25Х, «ЗНОВТЗЗТ ВОСТЕ РВОВШМ>//) РЬ(1) О.
ЬАВПР = 1 С С РВ1ИТЗ '2ЗБ ХЕРСТ ВАТА С ИЕ1ТЕ(б 101) 101 УОВМАТ() °,71, >ВХЛВТВА З АХВОВХТВМ тО УХЮ ТВЕ ВНОВТВЗТ ВОСТЗ //« В РВОМ АИ ОВ101И Ю АХЬ ТНБ ОТВЕЗ 201ИТЗ>//е УВОЗ ЮВ ВИ Ю ЮВЗ 16 А ВХЗТАИСВ ОУ '//) ВО 15 1 1>ИОВБЗ ВО 15 Т 1эЮВЕВ 1У(В(1,2) ИБ 1«В10) РВ1ИТ 200>1>2«В(1«2) 200 УОВМАТ(5Х>2110>210 2) 15 СО)УНИЗИ Приложение 457 С ОРНАТХИС ННИ ЮРИН Ой ННИ СНАХИВ МАННХХ С ИОНЕ(Х«Х) ЮНЕ(Х«2) 20 СОЕДИНИ НВХНИ(ХОР 800) 800 ВОВМАР(«1) «5Х««е ° НМСВЧМВЖ НХВТАЕСН ИАНВХХ ° ° «) САХА РНИНМХ инхнв (хон «900) 900 РОВНАЯ(«1««5Х««ММАХМХХ ВЕРНЕВНИНХЕО ННИ ЖНЖВ Ои Жвз ВЮВ1МНТ СВАХ ИЖ') САП РВЕ%ИХ ВННСНИ ЕЮ С ВСВВОСРХНИ РВИНВХ РХВнивхои спи(50 50) «А(50~50) «ВАВ(50) ехи(50) эеРН(50) «РИ(50) ° 1ИХСХВ(50 50) НСАЕ(50) «НН(50) СОММОИ Н(50«50) Н(50ДО)«ВОЕННО(50)«СОХИЯР(50)«НИИИ(50«2)е 10Р(50е50) «ЗР(50) «ХЕРЙНС(50> Я >МОРИН« ХИН«ХИНИ)««и«и ИАХ ЗНСХРАХМИСИ <ИСЙЕ, А, В), (ХАВ,И,ВОВСЮ), (ЕРВ,РХн СОХВЮ), (ЕХСХВ,ЕР) 1>(ВСАИ,П„ИР) И1 1 Игн5 45 хи(и2-и) 45>45>44 44 И2 И 45 РНХЕН 911,(Х,Х=И1,И2) 911 Р(МИАН(//,9Х,5(Х10«гх)) НВХНМ(6«912) 912 РОВИАНУ) Во 48 Хн1,М 48 РВхен 915,ъ«(э(х«м)«м М1«и2) хи(М2-й) 52~55«55 52 М1вй145 Ег И2+5 80 НО 45 915 хнешн(«««5х«хг«гх«5(Р10.2«гх)) 55 СОИ%ХИНИ ВЮ ВОВВСННХНЗ РВИНВХ ВХИИЮХОИ ИССИ(50«50)«А(50«50)«ХАН(50)«ХР(50)«ИРВ(50)«Р7«(50)е 1ЕХСХИ(50 5О) Воли~50),тх(5О) СОМ(ОИ В(50«50) Э 50«50)эВОНСЮ(50)«СОХОЮ(50)«ИННИ(50«2)« Е()НХРАХДИСЕ (ЕСИН А 8) (ХАИ ХР ВОВСЮ) (ЮНЫХ СОХОВВ) (ИХСП) СР) И1~1 йгэ«15 45 хи(иг-и) 45,45,44 44 Иг««й 45 Рихин 911,(х,х~е1 иг) 911 Вожи(//ф10х«15(х5)) ИВХНИ(6«912) 912 ИОВМАН(/) ВО 4В Х~1,Е 48 РВПРР 915,ь>ОНВ)з(ь«м)«и М1«ег) ХР(И2 й) 52,55>55 52 И1>И1+15 И2 Ив+15 НО НО 45 915 ЕОВЕАИ( ° «,4х,хг,)х,15(х5)) 46! Приложеиие 08 соиттиси М М+1 ха(то.ат.со) ао то 1овг тни соииистжв Авс тв п(ожхив итств(то „то)=г Итс РР(со,' хо)=г 1СОИ(М) 20 ао то 1071 саит!Бои 1овг 1085 1О81 с 1Р(И101Р(1~2)аа 2) БВ11И(10те7)1эс Р(1~2) 5ог соаттиси 7 РОВМАт(1НО 5Х 110з5Хз110~210'гю51эР10 2) Вжтсви жжс .с Ясввовтп и мехи(а РХМИИ810И Р10(50150) САР(50~50) Р1ИВБ810В ВОРЕ(50 503~А(50~50)~РАЯ(50)~ХР(50)>БРЯ(50)~РР(50) ° 131СХР(50ДО),ЯСАМ~50),тЬ(50) ссмиои 8(50,50) Р 50,50),воасЗР(50),ссъсвс(50),тнжж(50фг), 1СР(50в50)юиР(503этиивтс(50~5)эиссжвэ1иавтЯЪБЬвМзиэмАХ жас17Атжисж (БОРИ~А~8) ~ (тАВ~ТРэвоасво) э (БРЗэРР~ООРСЗР) ~ (Б101Р~РР5 1, (зсАБ тР,ВР) иастттАРжисж (Р10 8), (САР,Р) пттиажв зсеи,ихсЬ ' 1итжажв Риис/~Риис'/~ВРВО 11И=5 1отиа с С 1В1т1А11ЕАт10И с ВИАР(5 100) и 1оо РОВМАРЬ10) РО 1О1 1и1эи РАВ (1) =0 ВРЯД)=0 ЯСАИ(1)=0 РО 101 т 1,И САР(1,2) О О РХО (1, т)ио О 101 и!018(1,2)иО Ииио 102 ИВАР(11И,9) ВРВ0,1р УрА1,А2 9 РОВИАБ(АФ,18,110,2Р10 2) 1Р(БРВС жа.РВВР) ао то 104 105 И1С10(1,2)=1 с остгст Востптж гов мхитмАР ЗРАиитиа твжж с 5оо Битти(тот,551) 551 РСВМАт( 1т,гсх, мтипеАР ЗРАиипта твжа РВОЯРБМ~) витти(1от.451) ' 651 РОВИАт('0',5х, ' тни мтитмАР ЯРАиихиа тВжи соизтвтя ОР тни иовтоах эиа Ансв~) ' авттж(10т 54) Иа РоимАт('0(,5х,'зтевт1иа БОРЕ',2х,'ВБР1И6 Бови',2х,~втвтАтпж~) Рс 5ог 1-1',ии' Ро 5ог,т=1',ии 1Р(1 ат °,т) ао то 5с2 Приложение 1Р((В.ВП.ВОН).ВВП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
