Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 73
Текст из файла (страница 73)
е. любое допустимое решение одной из них является допустимым для другой. 19. Найти дезагрегированное решение задачи о распределении фруктов, исходные данные для которой приведены в табл. 5,1!. Показать, что его стоимость равна стоимости агрегированного решения. 20. Описанную ниже многопродуктовую задачу о перевозках сформулировать в виде задачи линейного программирования. Определить тнп этой задачи линейного программирования. 447 Новые вопросы 35 и» а!! = 50 Ь' = 3О Ь, = 30 Ь' =20 4 Ь =35 г 25 а„ = 35 г аг =30 21. Свести описанную ниже задачу к эквивалентной задаче об однопродуктивном потоке и решить ее с помощью алгоритма дефекта. Рассмотреть двз случая: когда заданы границы потоков по дугам и когда на потоки по дугам ограничения не накладываются.
а,' =гО а =40 ! Ь! =30 Ьг =50 аг =40 1 аг =30 г Ьг =30 Ьгг =20 22. Решить задачу о распределении фруктов, объединяя города а) Санта-Барбара н Бейкерсфилд; б) Санта-Барбара и Сакраменто, В каком случае получено лучшее решение? Объяснить, почему. 23. Решить описанную ниже задачу о многопродуктовом максимальном потоке. 25 Глава 5 448 24. Найти максимальный двухпродуктовый поток. 25. Предположим, что в сети из упр. 24 я, и гс соответственно источник н сток однопродуктового потока, а узел 5 вовонкообразный. Найти максимальный поток через воронкообразный узел. ЛИТЕРАТУРА . 1 ВЬашпйс б., ОрВспшп брега!!пн Ро!(осев о! а уча(ег О!в(г1Ьи!!оп Буз1еп! «чБЬ 1.аваев, ~lприЫ!вЬед РЬ. О.
б!ззег1ас!оп, ТЬе !)псчегвйу о1 Техав а1 АизНп, 1973. 2. СЬагпев А., КсгЬу Х., Еа!Ье сч'., СЬапсе-сопя(га!пей бепега!ьгес1 Не!мог)св, Орегамоня )(езеагсй, 14, 1113 — 1120 (1966). 3. СЬагпев А., Еа!Ье %. М., Опе-Разя А!бог! Ппп 1ог Боте бепега!!гед Несяог1с РгоЫепы, ОрегаЛоая )сезеагс)с, 14, 914 — 924 (1966). 4.
СЬагпев А., Соорег %., Мапайетеп! Мобе1з апд !пбиз!г!а! Арр1!са11опв о1 1Лпеаг Ргойгатт!пй, Чо!в. 1, 2, сч'1!еу, 1пс., Несч Уог)с, 1961. 5. Спин й., СавЬ Мапанетепс !п 1Ье Мй!!1па1юпа! Р!пп: А Сопя!та!пей бепега11геб НеЬчог)с Арргоасп, ЗУог)с)пд рарег, ТЬе Оп!четв!1у о! Р!огМа, ба!пев- чСВ, Р1а., 1977.
6. Папах!й б., (лпеаг Ргойтатт!пй апб Ех1епяопз, Рппсе1оп Оп!чегвйу Ргевз, Рг!псе1он, Н. 3., 1963. (Имеетсн перевод: Данциг Дж. Б. Линейное программирование и его применения. — Мл Прогресс, 1966.) 7. О1очег Р., К!!пйтап О„бп 1Ье Ес(и!ча!епсе о1 Боте бепсга!!геб Хе!«гогй РгоЫетв 1о Риге Хе!«ог)с РгоЫегпв, ЕезеагсЬ Вериг! СБ81, Сеп1ег 1ог СуЬегпейс Б!иб!ез, ТЬе Оп!чегзйу о1 Техав, Аизйп, Лапиагу 1972; МаМетайн са! Ргойгатттй, 4, 269 — 278 (1973) . 8.
б!очес Р., Ни11г Л, МсМ!Вап С., ТЬе ХеНопп Сопсер1, Ргосеес)сай о) сйе АСМ (1977), 9. О1очег Р., К1)пйтап О., Хе!счог(с Арр!!сайопз 1п бочегптеп1 апд !пбив(гу, АПЕ Ггапяасйопя, 9 (4) (ОесетЬег 1977). 1О. б!очес Р,, Кйпдгпап О., Нар!ег А., Ваяс Оиа! РеаяЫс Бо!ийоне 1ог а С!азз о1 бепега!ьгеб Не1«согйз, Орегайопз )сеяеас)с, 20 (1) (1972). 11. б!очег Р., К1!питап О., Б!и!г 3., Ех1епяопв о! 1Ье Аийтеп1еб Ргебесеззог 1пдех Мерной (АРБ) 1о бепега11геб Хе!«гог)с РгоЫепы, ГгааярогсаЕоа Зс!енсе, 7 (4), 377 — 384 (1973).
12. б!очес Р., К!спйтап О., Б!и!г 3. 1тр!етеп1аНоп апб Сотри(а1юпа! Б!иску 71овые вопросы о! а бепега!гвей ХеИчогЬ Сойе, Рарег рвевеп1ей а1 йе 441Ь ХаИопа! ОЙ8А Согйегепсе, 8ап О(ело, Са51., 1973. 13. О1очег Г., Ни!1х Л., КИп9тпап О., !тргочей Сотри1ег Ваяей Р!апп!п6 Хе1- счогКв, Лл(ег!асев, 8 (4) (Аидов( !978). 14. Оппо!й Е, С., Са!си!аИпд Махппа! Г!осев 1п а Хе(счог1с чИй РояИХе ба!пв, Орегас!оля йеяеагсгс, 21, 528 — 541 (1973).
15. Лвгчся Л. Л., Легйог А. М., Махала! Г!осч ъИЬ Оа(пз 1Ьгои85 а 8рес!а! Хе1- счогЬ, ОрегаИолв Еевеагсл, 20, 678 — 688 (!972). ° 16. Лепвеп Р. А., ВЬашпй б., А Согпри1аИопаИу ЕЬИс!еп1 А!2ог!!Ьт 1ог йе Хе(счог$с иг11Ь ба!пв РгоЫепс, Рарег ргевеп1ей а1 йе 451Ь ХаИопа! МееИпК о1 ОЙ8А, Воя1оп, АргИ 1974. 17. Лепвеп Р. А., Вагпев 97., Хе1счог1с Г!осч Рго8таппп!п2, %!!еу, 1пс., Хечг Уог1с, 1980. !8. ЛеъеИ Тсс, Л., Ор1ппа! Г!осев !Ьгои2Ь Хе!счог1св иг!1Ь Оаспв, ОрегаИоля !сеяеагс)с, 1О, 476 — 499 (1962).
19. Кип У., Ап Ор1ипа! СотрЫаИопа! АрргоасЬ 1о йе Апа!ув!в о1 а бепегаИ- хей Хе1счогЬ о1 Соррег КеИп(п2 Ргосеш, Ло!п1 ОЕ8А/Т1М8/А!!Е Соп1егепсе, АИапИс СИу, Х. Л., 1973. 20. Ьасч!ег Е. Ь., СоспЫпа1опа1 Ор(ипйаИоп: ХеИиог1св аий Ма1гоЫв, НоИ, РйпеЬаг1 апй!Тсспв(оп, Хеся Уог)с, 1976, рр. 134 — 138. 21. Маиггав Л. Г., Ор1!пигаИоп о( 1Ье Г!оиг йгоияЬ Хе(счог$сз сч!!Ь ба1пв, Ма!ЬетаИса! Ргоагатт!лй, 3, 135 — 144 (1972). 22. М1п!еЬа Е, Т., ОрИт!хаИоп А!6огИЬтя 1ог Хе1тчогЬз апй ОгарЬя, Магсе! ОеЫсег, 1пс., Хесе УогЬ, 1978, рр.
151 — 174. (Имеется перевод: Мак!ника Э. Алгоритмы оптимивапии на сетях и графах. — Мс Мир, 1981.! 23. М!п!е1са Е. Т., ОрИта1 Г!осч 1п а ХеЬчогЬ сч!й Оа!пв, Л!чсОЕ, 10, 17!в 178 (1972) . 24. ОеИИ1 Тсг., Ргабег %., Г!оиг ХеИчогЬз сч!й Агар!!ИсаИоп апй СоирИп6, (Лп(егпе1ипепМогзсЬип2, 10, 42 — 49 (1966) . 25. Тгиетрег К., Оп Мах Г!осев сл!!Ь Оаспв апй Риге М(п. Сов1 Г1осчв, 8!АМ волгла! о! Аррйей МайеглаИсв, 32, 450:— 456 (1973). 26.
Тгиетрег К., Ап ЕИ1с1еп1 8саИп2 Ргосейиге 1ог Оа1пз Хе!стог)св, Агегшогзв, 6, 151 — 160 (1976). 27. Тгиетрег К., Ор1ппа! Г!осчв 1п ХопИпеаг Оаспв, Аге!тогда, 8, !7 — 36 (1 978). 28. сча2пег Н., Рппс1р!ев о1 Орега(юпв ВевеагсЬ, РгепИсе-На11, 1пс., Епи!е~чоой С!И(в, Х. Л., 1979. 29. (Лий!еу Х.
А., 9(огЬ Т!те О!з!г!ЬиИоп, !ШеглаИола! Лоигла! о! РгойасИол )7евеагсЬ, 1 (2), (1963). 30. Каг2ег В. 9/., Вау(а Г. Н., Епб!пеег!п6 %ог(с Меаяигетеп1, ТЬе 1пйив(па! Ргеяв, Хеся Уог)с, 1966. 31. РЫ1Пря О. Т., 8т!1Ь О. Е., Ве1егпипаИоп о1 РгоЬаЫИяИс Тппе 81апйагйв 1ог ТазЬя Рег1огтей Ыпйег Ыпсег1аш1у, Ргосеей!п8я оп йе А!ЕЕ Ха(юпа( Соп1егепсе, 8ап Ггапс!зсо, Са., 1979. 32. РЫ!Ирв О. Т., )сач1пйгап А., 8о!Ьегд Л. Л., ОрегаИопв ЕевеагсЬ; Рппс!р!ез апй РгасИсе, \Ч!!еу, 1пс., Хеиг УогЬ, 1976.
33. РпЫсег апй Аввос!а!ей, %ея! Ьа1ауеИе, 1пй.— рпча1е сопки!Ипд Ипп, 34. РпЫсег А. А. В., Нарр Тсс. Тсг., ОЕ)сТ: ОгарЫса1 Еча1иаИоп апй Ееч!есч ТесЬп!с(ие, Раг( 1, Гипйатеп1а!в, Т)се Лоигла! о! !лйая!па! Ела!леег!ля (Мву 1966). 35. РпЫсег А. А. В., ссГЫ!еЬоиве О. Е., ОЕЕТ: ОгарЬсса! Еча!иаИоп апй )!еч!ечг ТесЬп!с!ие, РагС 11, Лоигла! о! (ш!аяггса! Елй!леегглй (Липе 1966). 36. РпЫсег А. А. В., ТАе РгойисИол Ел2глеег, рр. 499 — 506 (Ос1оЬег 1968).
37. Тч'Ы1еЬоиве О. Е., 8уйегп Апа!увся апй Оея!дп (Уя!па Хе!стог)с ТесЬп!с!иев, РгепИсе-НаИ, 1пс., Епд!емоой СПИз, Х. Л., 1973. 38. 9ГЫ(еЬоиве О. Е., РпЫсег А. А. В,, ОЕЕТ вЂ” ОепегаИп2 ГипсИопв, Сопй1- 29 — 1654 Глава Ю Иона! )тЫпйиИопв, Соип(егв, Кенси а1 Типез, апд Согге1аИопв, А!!Е ТтаивасИоав (МагсЬ 1969).
39. Кепи!п61оп Л. 1, А 8ючеу о1 1лпеаг Сов1 МиШсопнподИу ХеЬчог1с Р1оитв, Орвта!сопя Квзвагсй, 26, 206 — 236 (1978). 40. Аввад А. А., МиИ)сотитодИу Хе(втогй Р1осчз — А 8игчеу, Фв!атотйв, 8, 37— 91 (1978). 41. Ечапв Л. К., дагч|в Л. Л., Вийе К. А., бгарЫс Ма1гоЫв апд 1Ье МиИ!сотитос81у Тгапврог1аИоп РгоЫеп|, МатйвтаИса| Ртодтатт!ид, 13, 323 — 328 (1977).
42. Ечапз Л. К., дмч|ь Л. д., Хе(стог)с Торо!оиу апд 1п1едга! Ми!ИсопиподИу Р!осч РгоЫетз, Асвг|вотйз, 8, 107 — 119 (1978). 43. Ечапв д. К., А СотЬ|паИопа! Еци)ча!енсе Ье(счееп а С!азв о1 МиИ!союгиогИ1у Р!овт РгоЫеюв апд 1Ье Сарасна1ед Тгапврог(а1юп РгоЫет, Майетапса! Ртоататтсид, 1О, 401 — 404 (1976). 44. Ечапв д.
К., А 8!пд!е СоютподИу ТгапМопиаИоп 1ог Сег1а1п МиИкониподИу ХеЬттог1сз, Оретагтоаз Кезватсй, 26, 673 — 680 (!978). 45. Ечапв д. К., Оп Е9и)ча!еп! Раппа!а1юпв о1 Сег(а!п МиИ!сопнподИу Хе1- |чогйв ав 8|тп6!е Соппиой1у Р!сит РгоЫегиз, МагйетаИса! Ртодтатрйп~, 15, 92 — 99 (1978). 46. ОеоИпоп А., Сив(стет Аддгеда1юп 1и ОЫпЬЫ!оп МодеИпд, Втогй!п6 Раег Хо. 259, Втев(егп Мападетеп! 8с)енсе 1пвШи1е, 11п|чегвИу о1 Са1Иопиа, оя Апас!ев, 1976.
47. Е!рй!п Р. Н., АддгедаИоп 1п Ыпеаг Ргодгат|и!пд, РЬ. О. сИзвег1аИоп, Уа1е 1!п!чегвИу, Оесетпйег !977. 48. Ечапз д. К., 8о!чсп6 Ми1ИсопыподИу Тгапврог1аИоп РгоЫетв 1Ьгоиай А66геда1юи, ОК8А/Т1М8 ХаИопа! Соп1егепсе, Ьов Апбе1ев, ХочетЬег 1978. 49. Ечапв Л. К., Моде! 81|прИВсаИоп !и МиИ!сопниодИу ВЫг!ЬиИоп 8уз(етв 1йгоисгй Абдгеда1юп, Ргосеес1!пбв, Атепсап 1пзШи1е о1 Вес(вюп 8с!епсев, ХаИопа! МееИпа, Хеит Ог!еапв, Хочеи|Ьег 1979. 50. 8а1сагочИсЬ М., ТЬе МиИ1сопнподИу Махина! Р!осч РгоЫетв, ОКС 66.25, ()п!чегвИу о1 Са!Иогп!а, Вег1се1еу, 1966. 51. Ни Т. С., Ми!ИсопнподИу Хе(вто|1с Р)осчв, ОретаИоав Квяеатсй, 11, 344— 360 (1963).
52. дагч(з Л. Л., МИ1ег О. О., Мах)та! Риппе1-Ходе Р!осч 1п ап Бпд)гес1ед Хе1- счог1с, Оретайоиз Кевеатсй, 21, 365 — 369 (!973). 53. ВеПпюге М., Вени!па(оп б., 1иЬоге 8., А МиИ)чеЫс1е Тап1сег 8сЬедиИп6 РгоЫеп|, Ттаиярот|аИоа $с7еисез, 5, 36 — 47 (!97!).
Приложение ОПИСАНИЕ ПРОГРАММЫ СЕТЕВОЙ ОПТИМИЗАЦИИ ПАКЕТ СЕТЕВОЙ ОПТИМИЗАЦИИ Назначение: нахождение оптимальных решений различных задач на сетях с детерминированной структурой. Могут быть решены следующие сетевые задачи: 1) задача о кратчайшей цепи; 2) задача о многополюсной кратчайшей цепи; 3) задача о многополюсиой цепи с максимальной пропускной способностью; 4) задача о кратчайшем остовиом дереве; 5) задача коммивояжера; 6) задача о максимальном потоке; 7) транспортная задача; 8) задача о назначениях; 9) задача о дереве кратчайших цепей; 10) задача о перевозках; !1) задача о максимальном потоке минимальной стоимости; 12) задача о К кратчайших путях; !3) минимизация на обобщенной сети.
Ограничения: для задач ! — 6 и 12 программа позволяет обрабатывать сети, содержащие до 50 узлов и 50 дуг. В задачах 7 — 11 и 13 сети могут содержать не более 500 узлов и 500 дуг. Размеры сетей можно увеличить, изменив соответствующим образом границы массивов в операторах размерности, записанных в основной программе и подпрограммах.
Замечание; если в вычислительную машину можно ввести несколько программ, то все они могут быть выполнены за один прогон. Для этого в конце каждой задачи следует поместить карту 'РЕНО' (набор 4), а в качестве последней карты набора данных использовать карту 'ЕХ1Т' (набор 5). Ниже приводится список алгоритмов с нх именами вызова и именамн подпрограмм: Имя вызова Алгорятм П1ЛК О!ЯКА МТЗС КБИТ МЗТИ ТЯРД ОКА1. МОЙР ОНЕТ Входные даняые: Набор 1, Одна карта с нменем вызова в формате (А4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
