Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 71
Текст из файла (страница 71)
Задача заключается в максимизации полезности путем составления оптимального маршрута и оптимального расписания движения судов. Данная задача может быть сформулирована в виде следующей сетевой задачи. Каждый узел 7' сети соответствует прибытию судна в порт назначения в один из допустимых сроков доставки. Каждый узел с соответствует исходному порту и моменту, равному разности срока доставки н времени транспортировки, которое по предположению является детерминированным. Дуга (й 7) соответствует перевозке груза, а дуга (7', () — перегону судна из порта доставки в исходный порт.
Суда й-го типа первоначально располагаются в источнике зе, и дуги (зе, (), таким образом, соответствуют началу их эксплуатации. Далее, вводятся фиктивный сток 7 и дуги (), с), соответствующие завершению эксплуатации судов. И наконец, суммарный поток перевозимого груза по всем дугам, соответствующим различным датам перевозки н типам судов, не должен превосходить некоторой заданной величины. Математически эта задача формулируется следующим образом: максимизировать г= ~~~~~ '«~~ '~~~ с'мх"м (5.76) е с 7 Глава б Таблица б.ле судно й-го типа или нет. В качестве примера рассмотрим задачу, описанную в табл. 5.14.
Число судов каждого типа равно 2. 2,2 Рис. 5АО. Сеть в задаче составдеиии расписании движении судов. Соответствующая сеть изображена на рис. 5.40. Отметим, что в рассмотренном классе задач узлы служат для обозначения места и времени. 5.25.2. ПРОЕКТИРОВАНИЕ ГОРОДСКОИ ТРАНСПОРТНОИ СЕТИ Многопродуктовые сетевые модели используются также при проектировании городских транспортных сетей. В этих моделях узлы соответствуют участкам или районам города, а дуги — улицам или дорогам других видов. Требования к транспортной сети задаются матрицей поездок зл, элементы Ау которой равны числу транспортных средств, движущихся из участка ) к участку ] в течение фиксированного интервала времени. Каждая дуга имеет заданную пропускную способность ип, которая может быть увеличена (например, в результате улучшения дорог).
Плата за увеличение пропускной способности дуги (~, )) на единицу равна сп. Общая сумма денежных средств, предназначен- 439 Новые воооосы ных на улучшение дорог, равна В. «Продуктамн» в данной модели являются потоки из каждого источника во все пункты назначения. Пусть хви — число транспортных средств, движу- щихсЯ по дУге (0 1) и начавших свой пУть в Узле й; Уп †Увеличение пропускной способности дуги (1, 1).
Предположим, что время проезда по дуге (1, /) является некоторой функцией потока: Задача проектирования сети заключается в определении дуг, пропускную способность которых следует увеличить, и вычислении потоков по каждой дуге, минимизирующих общее время поездки. Математически данная задача формулируется следующим образом: минимизировать ~~)') м ('~~~ хвц1 п,п Ф (5.80) при условии, что ~', х'и 2„'к'м = е(м / ! ~~)'„х" ы ~ ~им+ Ум, '«~ ~оцуо ~ ~В, п,п х"1л ум > О.
(5.81) (5.82) (5.83) (5.84) В задаче (5.80) — (5.84) было сделано одно важное допущение, касающееся поведения водителя. Это допущение основано на классическом принципе распределения транспортных средств, сформулированном Уодропом [39]: водители выбкрают маршруты таким образом, что суммарное время поездок для всей системы является минимальным. Как правило, целевая функция (5.80) является нелинейной и выпуклой. 3.23.3.
МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Очень похожи на только что рассмотренную нами модель городской транспортной сети многие модели вычислительных систем. В этих моделях дуги соответствуют каналам, а узлы— терминалам, системным и запоминающим устройствам и т. п. Каждая дуга имеет фиксированную пропускную способность ип, которая может быть увеличена на ун единиц вплоть до мак- Глава 5 симального значения Ь;/.
Стоимость увеличения пропускной способности на единицу равна сц. Роль продуктов вновь играют потоки (информация) из источника во все пункты назначения, а вместо матрицы поездок .0 вводится матрица, элементы ([// которой соответствуют объему информации, передаваемой из узла ( в узел ]. Стоимость передачи единицы информации по дуге ((, ]) равна ец. Математически эта задача может быть сформулирована следующим образом: минимизировать ~ ~ енхэ,/+ ~~~~~ с;/у,/ (5.85) э (со (/.
/> при условии, что ~~~~~ х"и — лу' хэ(, = ([ц, / / ~' хэ(/ < им+у(/. (5.86) (5.87) (5.88) (5.89) у( з Ь(/, Описанная модель может быть использована для определения пропускной способности каналов, при которой заданные требования удовлетворяются с минимальными затратами. В этом случае значения ец обычно полагаются равными О, иц=О, а величины Ьц выбираются достаточно большими. Другим примером использования этой модели является задача минимизации стоимости передачи информации при фиксированных пропускных способностях дуг.
В этом случае Ьц=О. 5.26. ЗАМЕЧАНИЯ Обзор задач о многопродуктовом потоке, описание различных методов их решения, а также исчерпывающий список литературы по данному вопросу содержатся в работах Кеннингтона [39] н Асада [40) Вопросы использования теории унимодулярности при решении задач о многопродуктовом потоке и преобразования последних к задачам об однопродуктовом потоке впервые были рассмотрены в работе Эванса, Джарвиса и Дюка [4(]. Более полное изложение этих вопросов содержится в работах Эванса и Джэрвиса [42] и Эванса [43 — 45].
Результаты, касающиеся агрегирования, были получены Джиоффрноном [46] и Зипкином [47] и обобщены в работах Эванса [43, 49]. Вполне плоские сети рассмотрены в работе Сакаровича [50]. Ху [51] был разработан алгоритм поиска максимального двухпродуктового потока в иеориентированных сетях. Вопросы, касающиеся приложения потоков в сетях с воронкообразным узлом, рассмотрены в работе Джэрвиса н Миллера [52]. Задача составления расписания движения судов решена в работе Беллмора, Беннингтона и Лубра [53]. Другие прикладные задачи, рассмотренные в настоящем разделе, содержатся в обзорной работе Кеннингтона.
Литературу по вопросам проектирования городской транспортной сети н вычнслительныт систем можно найти в работе (39]. 441 Новые вопросы УПРАЖНЕНИЯ 1. Классическим примером задачи о многопродуктовом потоке является задача проектирования транспортной сети с несколькими источниками. Заданы сеть б=(Г4, А) и величины предложения или спроса (обозначаемые через Ом, й=1, 2, ..., Ц для каждого нз Е продуктов в узле й Требуется для каждого звена (й 1) н каждого продукта й определить такой поток хо», что сумма затрат на строительство сети и транспортных затрат является минимальной. Предполагается, что стоимость строительства звена (й /) равна р», а стоимость прохождения единицы потока по дуге (й /) равна сп, 2. Для каждой из следующих общих задач дать физическую интерпретацию понятий узлов, дуг н потоков в терминах миогопродуктовых сетей; а.
Перевозка груза между городами, осуществляемая автомобильным, железнодорожным, воздушным н водным транспортом. б. Проектирование коммуникационной сети с несколькими центрами связи и несколькими линиями передачи информации. в. Распределение почты, включая письма и посылки, между несколькими почтовыми отделенинми. г. Управление производственным процессом н запасами при непрерывном предложении и спросе. д. Проектирование системы сбора, переработки и ликвидации твердых отходов.
е. Проектирование районной сети дорог для пассажирских и грузовых транспортных средств. ж. Проектирование городской транспортной сети. з. Плзнирование перевозки различных видов продукции по сети с несколькими станциями и несколькими путями транспортировки. 3. По изображенной ниже сети может протекать двухпродуктовый поток. Предполагается, что поток каждого из этих продуктов может протекать по каждой дуге в произвольном направлении. В узлах 1, 2, 3 находится неограниченное количество продукта 1, стоком которого является узел 4, а в узле 5 в неограниченное количество продукта 2, стоком которого является узел 1. Число, приписанное каждой дуге, равно максимально допустимому суммарному потоку обоих продуктов по ней.
Доход при прохождении единицы продукта 1 из его источника в сток равен 4, а соответствующая величина для продукта 2 равна 6. Задача заключается в нахождении допустимого двухпродуктового потока, максимизнрующего общий доход. 4. В стандартной транспортной задаче прн удонлетворении спроса не делается различий между пунктами снабжения, Однако большинство фирм, производящих многономенклатурную продукцию, нуждается в составлении полной системы распределения, в которой учитывается каждый внд изделия в отдельности. Показать, как может быть использована однопродуктовая транспортная модель для решения простой задачи о многопродуктовом пото- Глава б ке, в которой з каждый пункт потребления требуется доставлять различные виды продукции. Какие предположения делаются в этой задаче? 5.
Йайти поток минимальной стоимости в изображенной ниже сети с выигрышами и проигрышами, Каждой дуге (й () приписаны четыре параметра, Есь Оо, сл и Ая, обозначающих нижнюю границу потока, верхнюю границу потока, стоимость прохождения единицы потока и коэффициент выигРыша или проигрыша соответственно. Указание: каждая дуга, для которой (.л>0, эквивалентна двум дугам с параметрамн (О, Рл — Ен, сч) и (О, Его — оь). 8. Финансовый директор фирмы разрабатывает план осуществления денежных вкладов. Общая сумма вкладываемых денег составляет 1 млн. долл. Имеется шесть типов ценных бумаг, доход по которым составляет 3,5, 2,5, 3,0, 4,5, 5,0 я 4,07з соответственно. По существующему соглашению не менее Збфг общей суммы должны составлять вложения в 1 и 2 типы ценных бумаг и ие более 407з — в 3 и 4 или 5 и 5 типы.
Определить, каким образом следует вкладывать деньги, 7. Процесс производства некоторого язделия состоит из трех этапов. Операции первого этапа могут выполняться на любом из трех станков, А, В и С, операции второго этапа — на любом иа двух станков, Р и Е, и операции третьего этапа — на любом из трех станков, г", б и Н. Все детали, обрабатываемые на станке А, затем должны быть обработаны иа станке Р. Все детали, обрабатываемые на станке В, затем обрабатываются на станке Р или Е. Все детали, обрабатываемые иа станке С, затем должны быть обработаны на станке Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
