Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 33
Текст из файла (страница 33)
8. Могут лн в алгоритме Флойда н методе двойного поиска параметры дуг принимать отрицательные значения? й. Могут лн быть получены циклы в путях прн понске К кратчайшнх путей с помощью метода двойного поиска? Что нужно сделать в том случае, когда определяются только путя, не содержащие циклов? 10. Объяснить, почему эффективность алгорнтма Флойда н метода двойного поиска может зависеть от порядка нумерацяя узлов. Рассмотреть каждый из алгоритмов в отдельности.
11. Показать, что метод двойного поиска, примененный' к ориентированной бесконтурной сети с дугамк (1, 1), где 1</, сводятся к однократному поиску, Какой попок прн этом исключается? Рассмотреть аналогичную задачу для случая, когда дуги (й /) такне, что )<й 12. (а) Как',ппределнть, являются лн два нлн более решений задачи коммивояжера оптнмальнымн? (б) В каком случае заданное звено яе включается в оптимальный маршрут? 13. Объяснять, почему общую задачу коммнвояжера нельзя решать непосредственно как задачу о назначениях.
14, В чем заключается роль начальных граннц в алгорнтме решения задача коммивояжера? 13. Прн каких условиях яеорнентнрованная дуга, соединяющая узлы 1 н А может быть заменена двумя ориентированными дугами (1, 1) н (), 1) с той Глава 2 же пропускной способностью, что и у исходкой дуги? В каких случаях такая замена ыевозможна? Привести соответствующие примеры. 16. Почему начальное решение транспортной задачи, полученное с помощью ПМФ, как правило, лучше начального решения, полученного с помощью метода «северо-западного угла»? 17.
Покааать, каким образом обычная транспортная задача может быть сведена к задаче о назыачениях (большей размерности). 13. Показать, каким образом задача о кратчайшем пути может быть сведена к задаче о перевозках. 19. Почему задачу со штрафом за выполнение поворота нельзя решать с помощью обычного алгоритма поиска кратчайшего пути, сложив предварительно параметр каждой дуги с величиной штрафа? 20. Дать математические постановки задач о кратчайшем пути со штрафом за выполнение поворота и беэ штрафов. Сравнить зти две постановки.
21. На изображенкой ниже сети параметр каждой дуги соответствует стоимости единицы потока по этой дуге, Выполняя все вычислении вручную, найти следующые пути: а) путь мынимальыой стоимости нз узла 1 в узел 13 (используя алгоритм Дейкстры); б) путй минимальной стоимости между всеми парами узлов; в) К 3 путей мынимальной стоимости из узла 2 в узел 13. 22. На изображенной ниже сети параметр каждой дуги соответствует верхней граннце потока по этой дуге. Выполняя все вычисления вручную, найти: а) максимальный поток яз узла 2 в узел 10: б) цепь с максимальной пропускной способностью из узла 2 в узел !О; в) максимальный поток между всеми парами узлов. 207 Дегерминирозанные потоки в сетях 23.
В упражнении 22(а) проверить правильность найденной величины максимального потока с помощью теоремы о максимальном потоке я минимальном разрезе. 24. Решить задачи из упражнения 21 с помощью соответствующих машинных программ. 26. Предположим, что в упражнении 21 стоимость единицы потока по дуге (12, 13) уменьшена вдвое. Можно ли найти путь минимальной стоимости, используя полученные ранее результаты? 26. Предположим, что в упражнении 21 дуга (4, б) должна быть включена в путь минимальной стоимости.
Найти решейне данной задачи. Как изменится процедура поиска решения, если знать о данном ограничении заранее? 27. В ХХЧ в. Бэк Роджерс отправлиется в космическое путешествие. Он хочет побывать на пяти астероидах, причем на каждом из них только один раз. Ло каждого астероида можно долететь только по определенным космическим трассам.
В приводимой ниже таблице даны расстояния (в млн. миль) между всеми астероидами, вычисленные по заданным космическим трассам. Черный Форт Замок неожи. Астероид Земля спутник Судьбы данностей Ужасое 29 62 35 29 21 44 50 27 Земля Черный спутник Фортбудьбы Замокнеожиданностей Астероид Ужасое 46 29 37 24 Я 23 44 50 27 №трица расстояний не является сямметричиой, поскольку возможны отклонения от курса. Найти кратчайший маршрут для Бэкз, если он начинает свой путь с Земли н благополучно возвращается домой.
28. В изображенной виже сети параметр каждой дуги соответствует стоимости едншщы потока по данной дуге. Выполняя все вычисления вручную, найти: а) путь минимальной стоимости нз узла 1 в узел 10; б) пути минимальной стоимости из узлов 1 н 2 в узлы 10, 11 и 12; в) К=2 кратчайших путей нз узла 1 в узел 11. Глава 2 29. В изображенной ниже сети параметры дуг соответствуют верхним границам потоков по ним. Выполняя все вычисления вручную, найти: а) максимальный поток из узла 1 в узел 9; б) цепь с максимальной пропускной способностью из узла 1 в узел 8; в) максимальный поток между всемв парами узлов.
14 30. Построять мянимальные остозные деревья изображенных ниже сетей. б 31. Построять древовидный остов сетя из упражнения 29. 32. Крупваи фирма, производящая конвейеры, пРоектирует систему конвейеров, иоторая соедянит пункт В с пунктом С. Ниже дается возможная конфигурация системы. Числа, приписанные дугам, соответствуют стоимостям сооружения соответствуюпщх участков конвейера. Если в яекоторой узловой точке должен выполняться поворот, то для сооружения соответствующего узла требуются дополнительные расходы.
Для узвов 1, 2, 6, 10 в 9 Детерминированные иотоки в сетях зти расходы составляют 1 ед., а для узлов 3, 5, 8, 7 и 4 — 2 ед. Найти мар- шрут нз пункта В в пункт С, ямекпций минимальную стоимость. Пункт В Пункт С 27 33. 1(ез1о Мапп(зс1ог(пя Согпрапу производит обеденные столы и продает нх Техасскому университету. Можно выделить следующие три основные этапа изготовления столов; сборка, окраска и сушка. Сборка может производиться в двух различных цехах — А и В. Поскольку цеха оснащены различным оборудованием, то общее время сборки в них не одинаковое. Аналогично окраска может производиться в трех различных цехах — С, Р и Е, которые оснащены различным красильным оборудованием.
Планировка предприятия такова, что ни один нз столов, собранных в цехе А, не поступаетдля окраски в цех Е и ни один из столов, собранных в цехе В, не поступает для окраски в цех С. Средняя продолжительность (в минутах) выполнения каждой операции приводится в таблице. Требуется найти оптимальную последовательность расположения цехов, т.
е. такую последовательность, при которой время изготовления одного стола будет минимальным. (Продолжительность сушки равна 60 мин.'Г Цеха Операции А В С Р Е 120 140 50 50 20 Сворка Скрасна 34. АВС Тах( 5еге1се Сощрапу нужно составить план замены оборудования на ближайшие 4 года. На данный период ожндаются следующие расходы н амортизационные стоимости. Существующая цена автомобиля составляет 7000 долл.
Ожидается ежеголное увеличение цен на автомобили на 10Те. В первые два года автомобили язнашиваются на 25$, а в последующие два года — на 157з. Издержки на техническое обслуживание я текущий ремонт в ближайшие 4 года составят 1200, 1500, 1900 н 2400 долл. соответственно. Автомобиль можно заменять каждйй год или каждые 2, 3 или 4 года. Составить план замены автомобилей, при котором общие издержки иа ближайшие 4 года были бы минимальными. 35. Используя алгоритм Дейкстры, найти кратчайший путь из узла 1 в узел 5 изображенной ниже сети. Глава 2 Л10 38.
Устройство состоит из восьми узлов. Вероятность выхода нз строя каждого узла показана на рисунке. Устройство работает правнльно, еслн нормально функционирует каждый узел некоторого пути, ведущего нз з в й 'Предположим, что если после работы блока 1 используется блок 2, то блок 1 не может быть снова использован. Сформулировать задачу мнннмизацнн ,вероятности выхода устройства нз строя как задачу о кратчайшем путя.
1 Блок 2 БЛОХ ! 37. Промышленная компания планирует производство кондиционеров, состоящих нз трех основных частей: корпуса, вентилятора и мотора. Латраты (в долл.) на оборудование предприятия станкамн, пронзводящнмн корпуса, вентиляторы н моторы, составляют 20 000, 50000 н 80000 соответственно.
Однако если вначале наладить выпуск вентиляторов, то затраты на оборудованне предпрнятия ставками, пронзводящямн корпуса н моторы, будут уменьшены на бааз. Еслн вначале пустить в производство моторы, то затраты на оснащение предпрнятня станками двух других типов уменьшатся на 10%. Если же в первую очередь будет налажен выпуск корпусов, то остальные латраты уменьшатся на 5$. После того как будет налажей выпуск двух компонентов, затраты на производство третьего компонента дополнительно уменьшатся на Бтг.
Построить сеть с одним нсточннком н одним стоком. 'Указать, чему соответствуют узлы, дуга н параметры дуг. Сформулнровать я йзешнть соответствующую задачу о кратчайшем пути. 38. Найти вратчайшнй путь между каждой парой узлов приведенной анже сетя. 211 Детерминированные потоки э сетях 39. Почтовому ведомству США требуется определить наиболее экономные маршруты доставки писем из заданного города в каждый другой город, отмеченный на изображенной ниже карте. Числа, приписанные звеньям сети, указывают приближенные транспортные затраты на выполнение соответствующих рейсов. Найти пути минимальной стоимости. НьюийорК фис Сан- 17 10 0 дорого О ферма 10 6, Элеватор 1 20 20 42.
Пять небольших городов одного округа соединены между собой дорогами, нуждающимися в ремонте и реконструкции. Расстояния между гоодами (в милях) приводятся в таблице. ачальнику окружного отдела автомобильных дорог надо определять, какие три дороги следует отремонтировать а первую очередь. В текущий момент состояние всех дорог приблизительно одинаковое. Наиболее интенсивное дввжение наблюдается на дорогах между городами 1 и 6, 2 и б, 3 и 4.
Общее 14Я 40. В сети из упражнения Зв найти кратчайший путь, начинающийся и заканчивающийся в Хьюстоне, шт. Техас, и проходящий через каждый из остальных городов ровно один раз. 41. На изображенном ниже графе указано размещение ферм и элеваторов в одном иэ сельских районов. Население данного района занято главным образом в сельском хозяйстве. Поскольку на вес груза, перевозимый через мосты, накладываются ограничения, то некоторые пользователи системы не имеют возможности подъехать к элеватору кратчайшим путем. Числа, приписанные дугам, соответствуют длинам дорог.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
