Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 31
Текст из файла (страница 31)
б. Одновременно с заменами элементов в матрице пропускных способностей выполнить замены элементов в матрице Глава 2 м аршрутов по следующему правилу: 1, если г(га а. ш(п(г(п,г(ТА], гга остается неизменным, если г(,А ~~ ппп (г(», г(та(. В заключение отметим, что если узлы 1 и 1 не соединены дугой (или связь между ними недопустима), то значение соответствующего элемента г(п матрицы пропускных способностей полагается равным — со. Для иллюстрации данного алгоритма рассмотрим следую'- щую задачу. 2.16.1. ОПТИМАЛЬНЫЙ МАРШРУТ ПЕРЕВОЗКИ НЕУПАКОВАННОГО ГРУЗА Еаз1 Техаз Рге1дЫ Сошрапу (ЕТРС) управляет фирмой, производящей перевозки автотранспортом крупногабаритного оборудования.
ЕТРС предлагают заключить специальный контракт о перевозке неупакованного груза между семью предприятиями НАСА, расположенными в Хьюстоне, шт. Техас. По этому контракту требуется перевозить несколько видов оборудования с очень большим вертикальным габаритом. ЕТРС должна перевозить это оборудование только по семи утвержденным маршрутам. Задача заключается в выборе маршрутов с максимально допустимыми подмостовыми зазорами. ЕТРС определила высоты проездов под мостами и для всех маршрутов, соединяющих пункты погрузки и разгрузки, нашла максимально допустимые вертикальные габариты груза. Таблица 2.87.
Транспортировка неупакованного груза В 1 2 3 4 5 б 7 Из 4 189 Детерминированные потони в сетях .Матрица марврутое 1 2 3 Я 5 б 7 Матрица пропускных спосооностея 1 2 3 4 5 б 7 Итерация 1: Матрица марврутое 1 2 3 4 5 б 7 Матриид пропускных способностей 1 2 3 4 5 б 7 Каждый элемент матрицы, приведенной в табл. 2.37, равен высоте проезда под мостом (в фут.), уменьшенной на 30 фут. ЕТРС требуется информация о максимально допустимых вертикальных габаритах грузов, которые могут транспортироваться с каждого пункта погрузки в каждый пункт выгрузки.
Данную задачу можно решить следующим образом: для каждой пары узлов определяется соединяющий их маршрут с максимальной пропускной способностью. Ниже приводятся результаты вычислений. Итерация О: Исходные матрицы Детерыыныроеыннае нотоны в оетн» Для каждой пары узлов максимально допустимый вертикальный габарит перевозимого груза можно определить непосредственно нз последней матрицы пропускных способностей. Оптимальный маршрут также может быть построен с помощью последней матрицы маршрутов. Например, максимальная пропускная способность цепи из пункта 1 в пункт 4 задается значением элемента деы= 19 (подмостовой зазор равен 49 фут.).
Соответствующий маршрут строится следующим образом: те14=3, двигаться из узла 1 в узел 4 через узел 3; твое=4, двигаться из узла 3 непосредственно в узел 4; т'„=3, двигаться из узла 1 непосредственно в узел 3. й~ы=ппп (30, 191=19. о оз в4 Отметим, что дуги, соединяющей узлы 1 н 4, не существует. 2пб.2. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮШЕИ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О МНОГОПОЛЮСНОИ ЦЕПИ С МАКСИМАЛЬНОИ ПРОПУСКНОИ СПОСОБНОСТЬЮ Назначение: нахождение цепи с максимальной пропускной способностью для каждой пары узлов источник — сток в ориентированной сети. Локализация: подпрограмма МАХСАР в пакете сетевой опткмизацни.
Ограничения: программа позволяет обрабатывать сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме МАХСАР и в основной программе. Входные данные: Набор 1. Одна карта с именем алгоритма МССР в формате (А4). Набор 2.
Одна карта с числом узлов и числом дуг в сети в формате (2110). Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие величины: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) пропускная способность дуги. Формат (4Х, 15, 110, Р10.2).
Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕ511У в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4)„которая указывает конец входных данных. 13 — 1зо4 Составные части программы. Программа состоит из следующих подпрограмм: МАХСАР (ввод и вычисления); РЯ)ЧТцХ (печать исходной матрицы); РК)ЧТКУ (печать оптимального решения). Используемые переменные: 1 — начальный узел дуги, Х— конечный узел дуги, К вЂ” промежуточный узел, А — пропуксная способность дуги.
Используемый метод: в данном алгоритме пропускная способность ориентированной дуги между узлами ! и К принимается за начальную оценку максимальной пропускной способности цепи нз ! в К. На Х-й итерации производится сравнение максимальной пропускной способности цепи из ! в К, содержащей промежуточные узлы из множества (1, 2', ..., Х), с максимальной пропускной способностью цепи, проходящей через узел Х, с промежуточными узлами из множества (1, 2, ..., Х вЂ” 1). Если использование узла Х позволяет получить цепь с большей пропускной способностью, то данная величина принимается зв новую оценку.
Литература: [31). ЯЛ 6.3. ТРАНСПОРТИРОВКА КОСМИЧЕСКОГО КОРАБЛЯ «ШАТТЛ» Недавно в Калифорнии был построен космический корабль «Шаттл», который затем был перевезен на подходящее место для запуска. До начала строительства группе инженеров, работающих в НАСА, поручили определить место для строительства корпуса корабля н маршрут его транспортировки к месту запуска. Изучив данную проблему, инженеры нашли трн подходящих места для строительства корабля и три участка для его возможного запуска. В связи с техническими трудностями транспортировки корабля было решено выполнять перевозку только на грузовом автомобиле с безбортовой платформой. Инженеров НАСА волновал вопрос о том, какой вес груза является максимально допустимым для транспортировки с мест возможного строительства корабля к местам его возможного запуска.
Было установлено, что между всеми выбранными пунктами расположено 28 мостов, максимально допустимая нагрузка для которых недостаточно высокая. После проверки данных в отделении автомобильных дорог, была составлена сеть (рис. 2.60), представляющая собой схему расположения мостов. Каждая дуга сети соответствует мосту, а число, приписанное этой дуге,— максимально допустимой нагрузке (в тоннах) для соответствующего моста. Требуется определить, какой вес груза является максимально допустимым для транспортирования с мест строи- 19о Детерминированные потоки в сетях тельства корабля (пункты А, В и С) к местам его запуска (пункты .О, Е и р). Решение данной задачи, полученное с помощью ЭВМ, выглядит следующим образом, Значения элементов исходной матрицы равны максимально допустимым нагрузкам для соответ- Рнс.
2.60. Допустимые нагруакн на мосты. ствующих мостов (дуг). Отметим, что запрещенным звеньям с пропускной способностью, равной — оо, приписано число 9999999,00. Элементы матрицы пропускных способностей дуг определяют максимальную пропускную способность маршрутов между всеми парами узлов. С помощью элементов последней матрицы, называемой матрицей узлов, определяются пути с максимальнымн пропускными способностями. Таблица 2.88. Маршруты с максимальной пропускной способностью 197 Детерминированнае нотоки в сетнн 15 13 МАТРИЦА ПРОПУСКНЫХ СПОСОБНОСТЕЙ ДУГ 3 4 1 2 9999999.00 45.00 47.00 9999999.00 53.00 50.00 0.00 49.00 41.00 9999999.00 0.00 9999999.00 9999999.00 9999999.00 0.00 9999999.00 53.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00, 9999999.00 .
9999999.00 9999999.00 9999999.00 9999999.00 9999999,00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 0.00 9999999.00 9999999.00 0.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 9999999.00 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 1 2 3 4 5 б 7 8 10 11 12 13 14 15 47.00 48.00 47.00 47.00 48.00 47.00 47.00 47.00 ' 52.00 9999999.00 0.00 9999999.00 9999999.00 9999999.00.
9999999.00 39.00 39.00 39.00 39.00 9999999.00 39.00 9999999.00 9999999.00 9999999.00 48.00 9999999.00 0.00 9999999.00 9999999.00 9999999.00 47.00 49.00 49.00 49.00 47.00 49.00 50.00 50.00 47.00 9999999. 00 47.00 9999999.00 0.00 9999999.00 9999999.00 47.00 48.00 47.00 47.00 48.00 47.00 47.00 47.00 52.00 48 00 57.00 53.00 9999999.00 0.00 9999999.00 47.00 48.00 47.00 47.00 48.00 47.00 47.00 47.00 49.00 43.00 9999999.00 43.00 9999999.00 9999999.00 0,00 Детерминированные потоки в сетях МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ УЗЛОВ В ПУТЯХ С МАКСИМАЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 Интерпретация выхода программы построения многополюсной цепи с максимальной пропускной способностью. Решения, пред- ставляющие для нас интерес, приводятся в табл.
2.38, а опти- мальные решения — в табл. 2.39. Таблица ЕЗУ. Оптимальные решения Следует отметить два момента. Во-первых, нами былополучено два оптимальных решения, каждое из которых представляет путь, по которому можно перевозить груз весом 49 т. Вовторых, численный метод нахождения этих путей такой„что матрица узлов может задавать узлы оптимального пути не последовательно. Это происходит по той причине, что длина пути из узла 1 в некоторый другой узел я сравнивается с длиной пути, содержащего промежуточный узел / (выполнение трехместной операции). Следовательно, при трассировке пути мы должны получить промежуточный узел 1, который либо следует не- 1 1 2 3 4 5 2 1 2 3 4 5 3 1 2 3 б 5 4 1 2 3 4 5 5 1 2 3 4 5 б 1 2 3 4 5 7 1 2 314 5 8 1 2 3 4 5 9 1 2. 3 4 5 10 1 2 3 4 5 11 1 2 3 4 5 12 1 2 3 4 5 13 1 2 3 4 5 14 1 2 3 4 5 151 2 3 4 5 4 9 9 5 б 4 4 7 5 б б 6 7 8 б б 7 7 8 б б 9 9 9 '10 б 4 7 8 1О 6 7 8 8 10 6 7 8 9 10 6 8 8 9 10 б 7 8 9 10 6 7 8 9 10 6 7 8 9 10 6 7 8 9 1О б 7 8 9 10 б 7 8 9 10 9 10 9 9 10 7 9 10 7 9 10 7 9 12 9 9 10 7 9 12 13 9 12 7 11 12 8 11 12 13 11 12 13 11 12 13 11 12 13 11 12 13 11 12 13 11 9 11 9 11 9 11 9 11 9 11 9 11 9 11 9 11 15 12 12 14 15 14 15 14 15 14 15 14 15 Глава 2 Таблица 2.тО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
