Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 91
Текст из файла (страница 91)
управление "без управления", когда потоки не пересекаются, а "вливаются" и "разливаются". Исходной информацией синтеза сети скоростного движения является граф корреспонденций О, = (у„(у,), каждая вершина которого взаимо однозначно соответствует транспортному району и вершины и;, о. связаны ребром (о;, иу) Е Гу„если плотность транспортного потока в "час пик" не меньше 3600 экипажей в одном направлении, Транспортные потоки прогнозируются на основе использования парной и множественной регрессии. Рассмотрим проектирование транспортной сети скоростного движения, представив транспортную сеть большого города как объединение сети, реализующей скоростные потоки и построенной на основе частичного квазиупорядочения, и сети, реализующей остальные потоки и построенной на основе кратчайших остовов.
При этом скоростное движение является свободным движением, скоростные потоки не пересекаются (друг с другом и с пешеходными потоками). Управление во второй сети осуществляется, как обычно, с помощью светофоров. Преобразование графа скоростных потоков Сс = (У„сУ,) в сеть скоростного движения 5, = (Ъ;, <) заключается в частичном квазиупорядочении графа С„С, -+ Я,. Ксли при частичном упорядочении некоторое подмножество преобразуется в путь, а все такие подмножества — в диаграмму Хассе, то при частичном квазиупорядочении они преобразуются соответственно в гамильтонов контур и цунг. При этом очевидно, что запрещенные фигуры относительно предиката частичного упорядочения Ро(ф„фв) являются запрещенными фигурами относительно предиката частичного кваэиуцорядочення Ро(С„Я,), и наоборот.
Поэтому методы частичного упорядочения с успехом могут быть использованы и при транспортной интерпретации. Временные затраты, отведенные в данном городе в "час пик" (обычно это время равно 45 мин) определяют ограничения, которые рассматриваемое преобразование Ос -+ 5, сводят к преобразованию вида ф, ->,эс: ф, = (М, Яэ,..., Я„), М = Ъ;. Сигнатура модели Ф, представляет собой полные подграфы Р = (К, Ц) графа 1 „удовлетворяющие следующему условию: время езды от произвольной вершины о Е Ъ< до середины каждого гамильтонова контура любого иэ этих подграфов 1;. не превышает предельных временных затрат, отведенных в "час пик".
Семантика этого преобразования также определяется предикатом частичного упорядочения. Для проектирования сетей скоростного движения предложим следующую стратегию. 1. В графе корреспонденций О, = (К (сУ, Р)), матрица смежности которого имеет вид (а;~]у~„щ, с, если Р(и;, и ) > 3600 эк./ч, в;, = 1, еспи 150 эк./ч < Р(и;, и,) < 3600 эк./ч, О, если Р(и;, и ) < 150 эк./ч, Р(ич и ) — плотность транспортного потока между е-м и у-м транспортными районами. 2.
Формируем сигнатуру модели ф, выделением всех полных подграфов Р; = (Ъ";, Ц) графа С„удовлетворяющих временному Гл.б. Прикладная теория алгоритмов 520 ограничению (время езды от произвольной вершины и б Ч( до середины каждого гамильтонова контура подграфа Р; не превышает времени, отведенного на езду в "час пик"). 3. Упрощением модели Фя Ф, — > Ф, (Ро(Ф„, Ф>) = 1), определяются запрещаемые потоки, которые реализуются транзнтно через другие транспортные районы.
В результате упрощения модели Ф, ее функциональная связность уменьшается настолько, что возможно частичное квазиупорядочение модели Ф,. 4. Частично квазиупорядочпваем модель Ф,. Удаляем все замыкающие дуги. Полученные тамильтоновы контуры, соответствующие словам модели Ф„сопоставляем скоростному кольцу, на котором не стоит ни один светофор п который не пересекает ни один поток.
Полученная модель Фб определяет сеть скоростного движения Я. Маршрут нз одной вершины в другую вершину сети Я, реализуется набором соответствующих отрезков полученных колец непрерывного движения. Съезд с одного кольца на другое осуществляется стандартным образом. Проиллюстрируем предложенную методику построением транспортной сети крупного города. Пусть в транспортном разделе генерального плана города имеется граф корреспонденций, ребра которого взвешены плотностью транспортных потоков. Матрица смежности этого графа имеет вид графа (', имеет вид ! 2 3 7 8 1 1 1 1 0 0 1 1 0 0 0 0 — 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 0 1 1 1 0 О 0 1 1 1 — 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 ! 2 3 5 6 7 8 >п,>>,н>,ч> 86 7(!И, Ч> з((, >ч> б(п, 5(П,(>(.
Ю Рис. 5ЛОО Рис. 5.99 Согласно предложенной стратегии выделяем частичный подграф, соответствующий скоростным потокам. Матрица смежности г з с с с с — с с с с — с с с с с 0 с О с 1 0 0 с 1 1 0 0 0 с 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 О 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 5 6 7 8 9 с с с 0 0 0 1 1 0 0 с 0 1 с 0 00000 с с с 0 с — с 1 0 с с — 1 0 с 1 1 — 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 0 1 0 0 00100 0 0 0 0 0 00001 >О и >г >з ьа >5 и >7 00000000 01100000 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 00000000 10000000 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 00000001 — 1000000 1 — 0 0 0 О 0 0 0 0 — 1 0 0 0 0 0 0 1 — 0 0 0 0 0 О 0 0 — 1 0 0 0 0 0 0 1 — 1 0 0 0 0 0 0 1 — 0 0 0 0 0 0 0 0 1 г з 4 5 6 7 8 9 щ 1! >г >з !4 15 !6 17 З 5.12. Семантическое проектирование скоростноп 521 Граф корреспонденций, задающий транспорткые потоки рассматриваемого города, приведен на рпс.
5.99. Дуги, соответствующие скоростным потокам, отмечены толстыми линиями. В графе выделяем полные подграфы, удовлетворяющие временным ограничениям. В результате получаем модель Фя = (М, Яз, 54) М = (1, 2,..., 8), 54 = ((1,2,~3,4 ), Яз —— ((1,5,8),(1,5,7), (3,5,8), (1,5,7ф 1 и ш ги >( соответствующий ей мограф представлен на рис. 5.100.
Отсюда получаем, что модель Ф, содержит запрещенные фигуры Ф!. вида: 0 Ф'(2, 1) = (1(1, П), 3(1, 1Ч), 5(П, 1Ч)), Ф (2, 1) = (Ц1,Ч), 3(1,1Ч), 5(1Ч,Ч)), Фз (2 1) = (5(П,Ч), 7(П11Ч), 0(П,П1)), Ф4~(2, 1) = (1(1, Ч), 3(1, 1Ч)1 5(П,1Ч), б(П1 1П), 7(П1, Ч) ). Гл,б. Прикладная гпеория алгоригамов В результате выделения запрещенных фигур формируется решетчатая таблица (табл. 5.69), столбцы которой взаимно однозначно соответствуют запрещенным фигурам, строки — соответственно их компонентам 1(1, Ч), 1(1, П), 3(1, 1Ч), 5(П, 1Ч), 5(1, У), 7(Ш, Ч), 6(П, П1). Покрытие рассматриваемой таблицы образуют строки 3 и 7.
Оно является минимальным. Эти строки Таблица Ь.бз 15.12. Семакпгииеское ороекигировамие скоросабиоб 523 В моделях Ф„ и Ф„ слово (1, 6), а в моделях Ф„ и Ф„ слово (1, 5) поглощается словом (1, 5, 6). Каждый способ упрощения порождает запрешаемые транспортные потоки, которые соответствуют удаляемым дугам в графе корреспонденций при соответствующем упрощении модели Ф,. Например, вычеркивание 3 из 1 и 7 из П1 означает запрещение потоков между следующими парами транспортных районов: (2, 3), (1, 3), (3, 4), (6, 7). Модель корреспонденций Ф, после удаления дуг, соответствующих этим потокам, преобразуется в частично квазиупорядочиваемую модель Ф,„мограф которой представлен на рис.
5.101,а. Этому мографу соответствует цунг (рис. 5.101,6). При этом обратное направление движения реализуется цунгом, полученным обратной ориентацией дуг. Цунгу (рис. 5.101,6) соответствует транспортная сеть, представленная на рис. 5.102). соответствуют компонентам 3(1,1Ч) и 7(Ш,У). Для упрощения модели Ф необходимо вычеркнуть букву 3 из слова 1 или 1У и букву 7 из слова П1 или У. Соответственно этим вычерки- ваниям имеем четыре способа упрощения модели Ф„а следо- вательно, и четыре частично квазиупорядочиваемых модели Ф, (Ро(Фа;г Ф6) = 1)- Фа, = (М,Яз), Яз = ((1,2,4), (1,5,6), (3,5,8), (1,5,7)) И 1Ч Ч при вычеркивании буквы 3 из слова 1 и буквы 7 из слова 1П; Ф„=ги,Я,Я,Я~~, е =((г,г,г,41), 1 Яз = ((1, 5, 6), (1 6, 7Ц) Яэ = ((5, 8)) 11 111 1Ч при вычеркивании буквы 3 из слова ГЧ и буквы 7 из слова П!; Ф„= (М,Яз), Яз = ((1,2,4),(1,5,6), (1,6,7), (3,5,8)) И Ш 1Ч при вычеркивании буквы 3 из слова 1 и буквы 7 из слова Ч; Фа, =(МгЯэгЯзгЯе)г Яв = ((1г2г3г4))г 1 Яз = ((1,5,6), (1 6 7)) Яэ = ((5 8)) и 111 гч при вычеркивании буквы 3 из слова 1Ч и буквы 7 из слова Ч.
71Ч1 а б Рис. 5.101 Рис. $.102 Каждый способ упрощения оценим величиной капитальных затрат, необходимых для реализации этого способа при проектировании транспортной скоростной сети. Расчеты сведем в табл. 5.70. Кроме рассмотренного минимального покрытия имеем еше одно минимальное покрытие (3(1, 1Ч), 6(П, П1)); этому покрытию соответствуют четыре варианта скоростной сети (табл. 5.71), Минимальные капитальные затраты соответствуют первому варианту скоростной сети (рис.
5.102). 524 Таблица 5.70 Таблица 5.71 Рис. 5.105 Рис. 5.105 Рис. 5.104 Рис. 5.103 Рис. 5.107 Гл.5. Прикладная теория алгоритмов Реализация скоростной сети непосредственно по графу корреспонденций (см. Рис. 5.99), без запрешения транспортных потоков, оценивалась бы в 686 млн. долл. При проведении расчета, согласно Б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
