Содержание к диссертации
Введение
Глава 1. Теоретические и методологические основы подходов к моделированию сетей транспортного типа (ТС) 9
1.1. Основные направления моделирования ТС 9
1.2. Сравнительный анализ существующих подходов к моделированию ТС 27
1.3. Базовые модельные свойства транспортных систем 30
Выводы главы 1 31
Глава 2. Разработка модели транспортной системы 33
2.1. Общая модель транспортной системы 33
2.2. Рабочая модель (T,U,P) 41
2.3. Свойства показателей параметров модели (ТДР) 42
2.4. Границы применимости выделенных целевых функций 49
2.5. О траекториях развития тс 51
2.6. Сравнение пространственного размещения станций ТС (артефакт модели). 52
Выводы главы 2 56
Глава 3. Транспортная сеть (ТС): анализ закономерностей формирования и развития 58
3.1. Исследование общих закономерностей изменения показателей (T,U,P) при изменении конфигурации ТС 58
3.2. Иллюстрация применения модели на примере сравнения вариантов развития метрополитена СПБ 73
Заключение 76
1. Общие выводы 76
2. Возможные постановки задач 78
3. Вопросы, оставшиеся за пределами рассмотрения настоящей работы 79
Литература 79
Приложения 84
- Сравнительный анализ существующих подходов к моделированию ТС
- Свойства показателей параметров модели (ТДР)
- Сравнение пространственного размещения станций ТС (артефакт модели).
- Иллюстрация применения модели на примере сравнения вариантов развития метрополитена СПБ
Введение к работе
В современном мире сложность и связность экономических процессов постоянно растёт. Одновременно, возрастает регулярность экономических связей и происходит интеграция ряда однородных объектов в сетевые системы с возникновением эмерджентных свойств. Данный факт находит отражение, прежде всего, в к управлению потоками. Так как, в свою очередь, динамика потоков в существенной мере определяется структурой связей, исследование свойств последних подтолкнуло развитие новых направлений исследований в области управления организационными и логистическими структурами.
В таких сетевых системах, на степень реализации функции хозяйственного объекта всё большее влияние оказывает не связи данного объекта с непосредственным окружением, а структура его связей с объектами внутри системы. Это означает определяющую роль инфраструктуры в обеспечении эффективности функционирования хозяйственных систем. Отсюда вытекает необходимость планирования размещения и развития сети объектов, например, транспортных, торгово-сбытовых, банковских, почтовых сетей. Впрочем, спектр задач довольно широк; от разделения рабочих мест на «поле» рабочих функций до размещения новых городов на вновь осваиваемой территории.
Хотя определённые свойства сетевых систем должны быть сходны, практическая значимость учёта этих свойств различна. Чем выше в системе затраты на сооружение и поддержание инфраструктуры по сравнению с аналогичными затратами на наполняющие сеть объекты, тем важнее означенный учёт. Наиболее ярко это проявляется в транспортных системах, поэтому дальнейший анализ производится на примере транспортных сетей (ТС).
Следует отметить, что практически важным становится организационный момент. Так как подобные сети обладают чертами естественных монополий, реализация преимуществ требует единства управления.
Проблема комплексного развития ТС, предопределяющая обеспечение эффективности решения задач их (ТС) функционирования и развития .является не просто одной из основных в экономической теории и практике, но и проблемой с растущей актуальностью. Можно назвать несколько причин роста актуальности исследований в данной области. Прежде всего, в условиях перехода к рынку,
5 закономерности формирования инфраструктуры, переход к системам логистического типа, требуют разработки специальных моделей согласования материальных, финансовых и информационных потоков. Разработка подобных моделей отстаёт от ускоренного развития сетей инфраструктуры. Это связано с тем, что динамика сетевых потоков намного выше скорости изменения конфигурации сети, представляющей материальную основу движения потоков. Возникает потребность выявления закономерностей развития сети, сохраняющих оптимальность сети в некотором, строго определённом значении, при значительных изменениях транспортных корреспонденции. Именно эти проблемы выступают предметом анализа в соответствующих разделах настоящей работы.
Отметим также, что если рассматривать современную экономическую ситуацию в целом (при этом речь идёт не только о России, но о глобальных тенденциях), то для неё характерны высокая цена ошибок проектирования и дефицит времени принятия решений. Одновременно, дополнительные трудности при моделировании процессов развития сетей создаёт принадлежность их к системам естественных монополий, что обуславливает необходимость учёта резкости столкновения общественных интересов.
Указанные свойства не только определяют актуальность, но и позволяют выделить центральную задачу исследования и анализа сетей транспортного типа, а именно разработку метода формализации процедуры предварительного отбора вариантов для сравнения с учетом конкретно-экономической обстановки, т.е. разработку процедуры быстрого получения предварительной оценки варианта развития ТС в условиях неопределённости данных (дефицита информации) об изменении сетевых потоков.
Переход к рыночной экономике, с одной стороны предоставляет благоприятные условия для роста сетей инфраструктуры, но с другой стороны, обостряет проблемы оптимизации проектирования этого роста на базе противоречия между общественной ролью инфраструктуры и частным подходом к её развитию. Кроме социальных, существуют, однако, другие глубокие причины обострения негативных явлений в сетях, суть которых представляется следующей.
На первоначальном этапе полного^ транспортного освоения новой территории данные о транспортных потоках либо ненадёжны, либо отсутствуют (иногда вместе с самими потоками), либо являются несущественными в силу предполагаемых значительных изменений грузопотоков, либо являются прогнозными величинами. Поэтому первоначальное транспортное освоение в значительной степени определяется физическими свойствами местности! Раз реализованная конфигурация транспортной сети (ТС) практически не поддаётся изменению!, в то время как величины грузопотоков более динамичны. По мере освоения местности, экономическое давление на местность и плотность её транспортного обслуживания, как правило, сглаживаются, а пространственное распределение грузопотоков стабилизируется. Вследствие этого дальнейшее развитие ТС определяется сложившимися грузопотоками. Т.о., первоначальное транспортное решение может содержать в себе противоречие по отношению к дальнейшему развитию транспортной сети. С учётом этой проблемы целесообразно проектировать расположение первой очереди ТС исходя не только (а может быть и не сколько) из непосредственного эффекта от ваедения участка первой очереди в эксплуатацию, но и с учётом влияния возможных последующих очередей ТС,
Сложность данной проблемы объективно подтверждается неадекватностью существующих методов моделирования развития ТС. Субъективно это выражается в наличии различных подходов к определению понятия ТС и различных направлений их моделирования.
Для разрешения проблемы необходимо определить закономерности оптимального построения и развития ТС. Учёт этих закономерностей в проектировании ТС даёт возможность экономии общественных затрат.
В данной работе предлагается подход, который предполагает априорное составление конечной ТС, оптимальной в заданном смысле, и разбиение ее на участки очередей строительства, такие, что по мере ввода в эксплуатацию
'Например, строительство нового города на границе ойкумены.
гНапример, порядок учёта свойств местности при прокладке автодорог приведён в
[22].
3Изменение конфигурации ТС требует колоссальных затрат. Кроме того,
нормативный срок службы магистралей на много превышает таковой прочих
сооружений. (Например, для метро - 500 лет, для жилых домов - 50-150 лет.)
7 очередного участка, получившаяся ТС, с одной стороны, оптимальна в том же смысле, что и конечная ТС, а с другой стороны, приносит положительный экономический эффект в сложившейся конкретной ситуации.
Данная постановка задачи требует разрешения следующих принципиальных проблем:
Во-первых, каковы критерии оптимальности конечной! (идеальной) ТС и какова форма этих оптимальных ТС?
Во-вторых, существуют ли такие последовательности ввода в эксплуатацию очередей ТС (траектории развития ТС), чтобы построенная на каждом этапе ТС была бы оптимальной?
Данные проблемы конкретизируются, в свою очередь, следующими вопросами:
Чем определяется ТС, каковы её свойства? (2.1.1)
В чём причина неадекватности существующих методов планирования развития ТС? (2.1.2)
Чем определяется развитие ТС? (Гл.1, 2.2, 2.6)
Каковы критерии оптимальности ТС? (2.3.2)
Существуют ли оптимальные ТС (непротиворечивы ли критерии оптимальности)? (2.3-2.5)
Если оптимальные ТС существуют, то можно ли построить оптимальную ТС развитием оптимальной же ТС меньшего размера? (Или, в общем случае, соединяют ли оптимальные траектории развития ТС оптимальные состояния оной?) (2.5, 3.3)
Как изменяется спектр решаемых проблем с развитием ТС? (3.3.3)
При разработке данных вопросов, были определены критерии оптимальности ТС, составлен алгоритм выделения оптимальных классов и траекторий развития ТС. Разработанный алгоритм был применён для изучения характера развития конфигурации ТС* и его применение проиллюстрировано на примере анализа вариантов развития метрополитена Санкт-Петербурга (на период до 2030 года).
"Т.к. любую конечную ТС всегда можно «развить и углубить», имеет смысл опустить слово «конечный» и говорить о показателе оптимальности сети, индифферентном к изменению состояния среды.
Нормирование исследуемых групп производилось методом имитационного моделирования, суть которого состоит в «имитации правильного ответа». Поэтому
8 Суть проведённого исследования.
Первоначально работа отталкивалась от проблемы оценки адекватности прогнозирования пассажиропотоков при проектировании трасс метро на основе внедрённых в практику моделей. Причина выявленной неадекватности состояла в том, что кроме выполнения своей непосредственной задачи - перевозки пассажиров - ТС изменяла свойства местности, обуславливающие эти перевозки (изменение пространственного распределения пар «отправление - прибытие»), что в применяемых моделях не учитывалось. В данной работе показано, что данное влияние ТС на свойства местности разделяется на влияние пространственного размещения сети станций и конфигурации (графа) ТС. Влияние конфигурации ТС исследовано на основе сформированной группы показателей. Показано, что не существует (в рамках исследованной области) ТС, наилучших с точки зрения всей совокупности показателей. Выявлено, что характер влияния ТС различен на этапах её интенсивного и экстенсивного развития. Показана несовместимость оптимального развития ТС при переходе с этапа на этап,
Показано изменение предпочтительности вариантов развития метрополитена С.Петербурга при изменении критерия оптимальности с учётом вышесказанного.
В работе также рассмотрен ряд вопросов из смежных по теме и применённому инструментарию областей исследования {2}.
соответствующая часть результатов диссертации имеет вероятностную достоверность.
Сравнительный анализ существующих подходов к моделированию ТС
Множество определений транспорта в литературе, а зачастую и отсутствие определения транспорта в явном виде, наводит на мысль о глобальности этого понятия.
Как правило, словесные определения дают понятие либо формально более широкое по смыслу, чем интуитивно-общепринятое, либо задают понятие транспорта перечислением его элементов. Например, определение ТС как «сферы общественного производства, обеспечивающей перемещение людей и грузов» позволяет отнести к ТС буквально всю экономику, начиная с добычи руды и кончая подготовкой кадров. Определение ТС «совокупностью транспортных средств, транспортных путей, пересадочных пунктов, обслуживающих и ремонтных станций» и т.п. является типично «ведомственным» и не позволяет ничего сказать о внутренних свойствах ТС кроме, разве что, наличия МПСЦ.
Такая же неопределённость наблюдается и по отношению к понятиям, определяющим части транспортной системы. В 60-70 годах дискутировался вопрос о том, что считать узлом ТС. (точнее: можно ли считать узлом пересечение двух железных дорог, или же узел - обязательно пересечение путей различных видов транспорта.) При этом считалось очевидным, что развилка узлом не является. (Это противоречит представлению узла вершиной графа.) Одновременно, несмотря на В качестве разрешения существующей неопределённости в понятиях. предлагается следующее дерево определений от наиболее общего до наиболее конкретного. Данная цепочка определений позволяет вводить в рассмотрение свойства ТС по мере падения их общности, т.е. по мере роста актуальности, 1. Предельный уровень рассмотрения. Информация. Движение, как атрибут материи, разлагается в понятия пространства и времени. Данная пара характеризует траекторию движения, оставляя в стороне вопрос «почему» движение происходит именно так. С другой стороны, движение можно разложить в понятия энергии (способность совершить работу, т.е. двигать(ся)) и информации ( нечто, с необходимостью переводящее систему из одного состояния в другое). Энергия определяет причину конкретного вида движения. Различные тела получают энергию в результате наличия неоднородностейЦ Появление неоднородностей является причиной и следствием движения (атрибутом его). Неоднородное состояние энергетически невыгодно, следовательно существуют механизм возвращения системы в исходное состояние, т.е. информационный механизм. Информация устраняет неоднородность за счёт создания неоднородности другого типа. 2. Пространственно-структурный уровень. Стабильность источников неоднородности. КвантыЦ. Любая неоднородность (энтропия) имеет источники) и свой носитель (квант). Квант есть тело, которому неоднородность придаёт энергию, определённую только в рамках этой неоднородности. Неоднородность может быть устранена двумя результаты неоднократных исследований системного влияния пассажирского поведения, большинство авторов относятся к пассажиру как к счётной единице. Только один известный автору специалист [34] декларировал пассажира в качестве системообразующего элемента ТС. (Правда на декларации дело и кончилось.) "Рассмотрение некоторых других неопределённостей в понятиях сведено в приложение {1}. гвБудем иметь в виду только неоднородности в пространстве. Философически можно представить неоднородность во времени (например, историческом или этическом времени), придающую телу энергию при его существовании в двух временах одновременно (например при раскопке памятников древности). способами. Во-первых, совмещением неоднородных участков в пространстве -рекомбинацией источников возмущения неоднородности. (Например: соединение двух тел устраняет силу притяжения между ними; строительство перерабатывающего завода у месторождения сырья снимает пространственную разделенность истока и пункта назначения груза). Если данный способ на определённом временном отрезке неосуществим, неоднородность может быть устранена переносом квантов неоднородности. 3. Графологический уровень. Система сообщения. Каналы. Перенос квантов может осуществляться равномерно в пространстве (поле) и преимущественно по к.-л. направлениям. Эти направления назовём каналами сообщения, а их совокупность системой сообщения. 4. Технический уровень. Транспортная система и система связи. Экипажи. Система связи - система сообщения, в которой по каналам движутся непосредственно кванты. Система транспорта - система сообщения, по каналам сообщения которой кванты переносятся порциями. Данные порции назовём экипажамиЦ.Ц 5. Общехозяйственный уровень. Сфера производства. Институты. Транспорт - сфера общественного производства, создающая товары путём перемещения исходных товаров в пространстве . 6- Конкретно экономический уровень. Предприятие. Капиталистическое транспортное предприятие - учреждение в сфере транспорта, максимизирующее свою частную прибыль . Эту цепочку можно продолжить далее. Свойства транспорта, вводимые в рассмотрение на каждом шаге этой цепочки, будут являться тем средним (каркасом), отклонения от которого будут определяться свойствами, вводимыми позднее. Неверно, конечно, что для конечного пользователя безразличны "Подобного рода рассмотрение упомянуто в ([26]). заПод экипажем будем понимать любое транспортное средство (самолёт, автомобиль, пароход и т.п.). 29В данных терминах нефтепроводы и ижв не транспортные сети, но сети связи. 30Отнесение транспорта к той или иной сфере экономики общества весьма дискуссионно, и на мой взгляд, казуистично. Подробнее этот вопрос рассмотрен в {1} 36 возмущения, вносимые «поверхностными» свойствами. Однако степень изменения этих свойств лежит в границах глобальных закономерностей развития, определяемых более «глубокими» свойствами. В данной работе основной акцент делался на изучении свойств 2-4 уровней, которые определяют экономический успех транспортных институтов в долгосрочном плане.
Т.о., главным фактором;определяющим свойства транспортной системы является вмещающая её местность. Вторым фактором (и элементом) является пассажир (!), как носитель свойств местности, и лишь на третьем уровне лежит конфигурация ТС.
В заключение можно привести следующие косвенные подтверждения!! в обоснование сведения элементов транспортной системы к столь глубоким уровням рассмотрения материи :
1. Большой популярностью у исследователей пользуется перенесение на объекты транспортных моделей законов физики по методу аналогии. Например, очень широко применялось использование закона тяготения при расчёте величины транспортных корреспонденции.
Наличие в транспортных системах явлений, гомологичных явлениям в других областях. Например, распространение транспортных волн (пиковой волны пассажиропотока) аналогично свечению Вавилова-Черенкова и следу корабля в море.([19]).
Опираясь на разработанное определение ТС, построим её общую модель с целью выявления возможностей нивелирования недостатков, описанных в 1.1.1. 1.Дана некоторая местность (пространство ЕІІ), для любой точки і которой задана функция отправлений J ](J) в другую точку j этого пространства. При этом, Ft(j) представима в виде /1,/0), где /-0) -структура отправлений (например в %), а Аг объём.
Свойства показателей параметров модели (ТДР)
В этом случае рассматриваемую местность можно ограничить множеством точек, лежащих от вершин ТС на расстоянии меньшем, чем. Расстояния между точками(Лу). Встречаются разные измерения расстояния. В своё время [17] пришли к заключению о предпочтительности измерения расстояния временем пути по сравнению с километражем. Сейчас временному критерию часто противопоставляют стоимостной, измеряющий расстояние транспортными затратами на тонно-(пассажиро-) километр. Автору представляется это противопоставление несущественным, т.к.: 1. Если тариф пропорционален затратам, легко получить интегральный показатель, увеличив тариф на величину потерь от омертвления капитала на время транспортировки, приведённых по действующему дисконту. (При долгосрочном планировании, правда, очень трудно определить дисконт, т.к. последний весьма подвижен. Впрочем, как и номинальную величину самих транспортных расходов.) 2. В больших городах скорость сообщения приблизительно одинакова по всем направлениям. Поэтому можно считать расходы пропорциональными географическому расстоянию. 3. Само исчисление затрат на тонно-километр скорее бухгалтерского происхождения, ведь единицей транспортной системы, порождающей расходы, является не тонна груза, а экипаж, если не маршрут (поэтому количество экипажей на маршруте определяется предельной тонной критического участка). Кроме этого, существенная часть расходов приходится на косвенные затраты. Это допускает произвол в оценке стоимости конкретного тонно-километра, т.е. неоднозначность модели. Расстояния зависят от: технического оснащения (вид транспорта, скорость экипажа и т.п.); конфигурации сети. Все виды современного транспорта предполагают наличие каналов сообщения. (Можно конечно представить себе гипотетический город, где у каждого личный вертолёт. Но и в авиации есть «коридоры».) объёмов транзитных потоков на перегонах (7 „?). При росте потока от малого до нормального, расстояние может сократиться за счёт уменьшения межэкипажных интервалов. Дальнейший рост сверх пропускной способности приводит к росту расстояния (измеряемого временем) за счёт спонтанного пробкообразования. Величина транзитных потоков, в свою очередь, есть функция отправлений, конфигурации сети, а следовательно и расстояния между точками. Имеем цикл обратной связи. между параметрами {общей] модели, что представлено на рис. 6. На нём отражено то, что ТС может развиваться как за счёт внешнего воздействия (капитальное строительство), так и за счёт взаимной адаптации среды и ТС. В больших городах
Величина транзитного потока на перегоне Ттп (между станциями тип) равна сумме всех корреспонденции, пути следования которых содержат перегон mn. 8 дальнейшем будут использоваться величины транзитного потока через станцию j, называемых транзитностью (Т). Транзитность вершины k (1\) равна сумме всех корреспонденции, пути следования которых проходят через вершину эта взаимная адаптация весьма существенна, и требует учёта. Для осуществления этого перейдём к построению рабочей модели, которую назовём списком её пареметров - моделью (T,U,P).
В механизме адаптации было выделено два дополнительных параметра -удалённость (точки от всех других - J7,) и транзитный поток на перегонах ТС (7 ). Если оба эти параметра будут стремиться к минимуму, изменения в ТС, вызванные адаптацией будут наименьшими, а значит для проектирования ТС достаточно будет учитывать лишь непосредственный эффект от капитального строительства. Поэтому встаёт вопрос: как ведут себя эти показатели на множестве возможных вариантов ТС и какого рода минимум можно достичь?
При этом надо учитывать, что зависимость объёмов отправлений от удаленности (Ai -{/,) двояка. Объём зависит как от абсолютной величины удалённости (чем меньше Ut, тем меньше среднее время / расстояние поездки, - тем больше количество желающих куда-либо ехать А,), так и от относительной по сравнению с другими а данной ТС величины удаленности. От относительной удаленности (назовём её периферийностью: J] = f/ -f/mLl) зависит перераспределение объёмов между точками, т.к. минимальный уровень удалённости в ТС (U ) будет расцениваться прузоисточниками как общественно-необходимый.
Для решения указанных задач рассмотрим модель, построенную на идеальных свойствах местности и ТС. Изложим условия и цели [рабочей] модели: На гомогенной [по распределению пар «отправлений - прибытий»] территории создана треугольная сеть станций ТС. Следовательно, зоны притяжения всех станций равны. Следовательно, объёмы отправлений всех станций равны. А} = сот/. Следовательно, структура отправлений равномерна по всем станциям {ftj = const). Местность заведомо цельноевязна, т.е. максимально-возможное расстояние между станциями (диаметр сети - г=гпах и) не превышает критический уровень (11Гааи(). Другими словами, с одного конца города реально добраться до другого за общественно-приемлемый промежуток времени. Сообщение осуществляется по кратчайшим путям. Требуется (целевая фукция Z): 1. (в статике) задать такой граф путей сообщения между станциями {с заданным числом перегонов), чтобы обеспечить оптимальное значение показателей удалённости, транзитности и периферийности; 2. (в динамике) определить оптимальную траекторию развития ТС, т.е. такую последовательность приращений перегонов (этапов), чтобы на каждом этапе обеспечивалось оптимальное значение показателей. Т.о., целью моделирования является изучение закономерностей влияния конфигурации ТС на свойства местности, отвечающие, в свою очередь, за формирование транспортных потоков, определяющих эффективность ТС, и изученеие закономерностей изменения этого влияния по мере развития ТС.
Свойства показателей параметров модели (ТДР)
Т.к. количество возможных траекторий выражается запредельным для сравнения «каждая с каждой» числом, необходим предварительный отбор траекторий. Реализованная процедура отбора (см. {5}) не гарантирует от ошибки отбросить Парето- оптимальную траекторию. Однако в некоторых случаях можно утверждать, что этого не произошло. Эти случаи оговорены в комментариях результатов.
Пусть дан некоторый граф и соответствующая матрица смежности {Av}. 2. Поделив каждый элемент матрицы на сумму элементов соответствующей строки, перейдём к матрице вероятностей переходов {Дуг}= {-=;—}, задающей І Марковскую цепь. Элемент Bv матрицы {BtJ} равен вероятности перехода из одного состояния Марковской цепи «Пассажир находится на станции і» в другое «Пассажир находится на станции j». Т.о., HS - есть неопределённость станции нахождения пассажира, если он передвигается случайным образом. С другой стороны, HV - есть мера неопределённости, которую в среднем испытывает данный пассажир при выборе направления дальнейшего следования со станции своего нахождения. Вольно выражаясь, HS - мера неопределённости ТС при взгляде «сверху», a HV -«изнутри».). Схема итоговых результатов {6} Итоговые данные по Частям исследования сведены в перечисленные ниже таблицы. 1. Распределение графов по классам четырёх классификаций. В таблицах представлено распределение графов с определённым числом дуг (группы) по классам. В строке «Итого» проставлено количество анализированных вариантов, в столбце «Итого» представлена сумма распределений графов. Внизу приведены частные распределения. 2. Таблицы исследовавшихся статистик по классам. Столбцы слева означают: в скобках + соседнее двузначное число - класс; второй столбец - количество графов в классе; третий столбец - в т.ч. графов с одинаковым упорядочением вершин по возрастанию удалённости и убыванию транзитности. Далее приведены минимальные (min), средние (М[]) и максимальные (max) значения статистик, 3. Таблицы статистики изменения класса графа при добавлении к нему одной дуги. (Столбец KL1 - класс первоначального графа, столбец KL2 - класс расширенного графа.) Т.к. данные таблицы плохо читаемы, они сведены в итоговую таблицу переходов. Элементы таблиц означают: . (одна точка) - данный переход встретился между 1 парой групп графов; .. (две точки) - данный переход встретился между 2-3 парами групп графов; R - данный переход характерен для всех пар групп (не более одного исключения); г - данный переход характерен. (2-4 исключения); :. (три точки) - остальные случаи. 4. Таблицы Парето - оптимальных траекторий развития графа ТС. 3.1.3. Интерпретация результатов Интерпретация результатов, полученных в соответствии с планом исследования (3.1.1) и приведённых в приложении {6}, производится в порядке схемы, описанной в (3.1.2). 3.1.3.1. Часть 1. Графы с 18-30 дугами (и 19 вершинами]. 1. Таблицы распределения по классам. Распределение по классам внутри групп сходны, за исключением группы с 18 связями (группа деревьев). Её отличает: заполненность высших классов (14-18) классификаций-3 , незначительные удельные веса худших классов (32,33/52,53). При этом класс 53 классификации ЗР пуст. доминирование графами высших классов классификаций-3 остальных графов по лексиминному порядку удалённости. Данный факт послужил одним из оснований необходимости второй части исследования - развития деревьев отдельно. В классификациях много классов с нулевым наполнением. В Классификациях 2 - 20,21,22 ,25,26,29,30,31 Щ (если не считать запредельно хороших классов 1-4,7,8,11-13,15,16). Данный факт можно расценивать как подтверждение некоторой коррелированное критериев классификации. Во всех группах графов (кроме как с 26 дугами) существует граф[ы], оптимальный 693нак при номере класса означает: 1. - возможно случайное наполнение класса. 2. - класс не заполнен только в классификации L. 3. " - класс не заполнен только в классификации Р. по утилитарной Z. В Классификациях-3 пустых классов сравнительно меньше - 25-27,28 ,30,ЗГ,37-38 ,51 . Почти полное вырождение классов 25-28 (недоминируемость по частным показателям Р и U) свидетельствует о сильной разнонаправленности критериев удалённости и периферийности.
Если в группе есть один лучший вариант (или несколько равнолучших), то это граф(ы), который(е) по всем критериям не хуже других, а при классификациях 2 превосходит(ят) остальные по PS.
Заполнение классов резко неравномерное. Классы с одновременным доминированием по эгалитарной и утилитарной Z объединяют « 99% графов (по любой классификации). Однако для классификаций Р наиболее заполнен, как ни странно, не худший класс, а класс 28/43. Это можно объяснить «нерешительностью» а отвержении вариантов на основании критерия транзитности.
Надо отметить, что удельные веса худших классов в приведённых таблицах существенно занижены (по отношению к случайной выборке) процедурой целенаправленного перебора лучших вариантов. Для примера: С точки зрения мощности частных критериев, минимизация по Парето [лексиминных порядков] и Лоренцу удалённости даёт более определённый результат, чем для транзитности. Это вдвойне отрадно, ибо транзитность считать сложнее. Еще более мощна частная минимизация для периферийности?!. Совместные Парето - минимизации «нерешительны», т.к. отвергают всего лишь треть (28%) вариантов (при двух критериях) или даже 16% (три критерия). Совместная Лоренц-минимизация более мощна и отвергает около 90% вариантов. Совокупные утилитарный и эгалитарный критерии ещё мощнее: минимизация сумм даёт множество Парето из 17 (170) Как уже отмечалось, периферииность является родом эгалитарной производной от удалённости. Эгалитарные же критерии сравнительно более сильные. элементов, а минимакс - из 161(226) для двух и трёх критериев соответственно. При этом, как уже отмечалось, минимизация сумм при двух параметрах выделяет, как правило, единственный оптимум. 2. Таблицы статистик по классам. ? Закономерностей изменения статистик между классами выявить не удалось. ? С ростом числа дуг в графе все показатели суммарных удалённости, транзитности, периферийности и диаметра не растут; энтропии вершин -растут; энтропии U.T.P - колеблются и/ипи изменяются незначительно (не исключено, что вследствие недостаточной разрядности вычислений). Некоторый интерес представляет динамика энтропии связей. Хотя ее среднее и максимум колеблются, минимум падает с ростом числа дуг до 24, а затем растет практически до исходного значения.
Иллюстрация применения модели на примере сравнения вариантов развития метрополитена СПБ
Генерация графов и расчёт их статистик производилось программами PR#1_P и PR#2_P для Частей 1 и 2 соответственно. В результате формируются групповые файлы структур графов GN18 - GN30, GTN1 -GTN18 и файлы статистик графов GR18 - GR30, GTR1 - GTR18 соответственно для Частей 1 и 2. Принципы, положенные в основу.
В выбранном способе представления местности граф однозначно идентифицируется перечнем входящих в него дуг. Формирование перечня дуг является первой половиной вышеуказанных программ. Графы с одинаковым числом дуг объединялись в группы. Вторая половина программы (процедура result) рассчитывает статистики фафов на основании сформированного перечня дуг. 1. Первая половина программ, а) Формирование перечня дуг. і) Часть 1. (PR#1_P). Использовались 4 схемы формирования. a) Генерация дерева [(19,18)] (vybor=1 или 2) Последовательно включаем в список 19 дуг так, чтобы очередная присоединяемая дуга не образовывала разрывного графа и не образовывала цикла. Нахождение множества дуг, удовлетворяющих данному условию, завязан на расчёте переменной M.KOLD. Выбор дуги из данного множества производится случайно или оператором (выбор в BROWSE - окне). b) Случайное развитие дерева. (vybor=3 или 4) Графы сформированного выше списка деревьев (группа 18) развивались приращением дуг случайным образом или по выбору оператора {3}. Так образовывались списки групп 19-30. c) Перебор вариантов развития / редукции графа. (vybor=5 или 6) Вышеуказанные действия сформировали предварительные списки фупп. После проведения сравнения в них (программой PARETY_P, см. ниже), некоторые графы оказались «не хуже» других. Для данных графов (их классы зафиксированы в переменной KLMAX) производился анализ всех возможных вариантов развития / редукции [на одну дугу). Моделирование развития аналогично моделированию этапа развития дерева. При моделировании редукции, на выбор дуги к отсоединению накладывалось ограничения сохранения 19 вершин графа (переменная may процедуры LINE LESS); целостности графа (проверка на «бесконечность» расстояния между вершинами - r(i,j)=99 - в процедуре result) ii) Часть 2. (PR#2_P). Использовались две схемы. а) Генерация развития дерева от 1 дуги до 18. (ууЬог=1или 2) Аналогично 1.1.1.1, только образовывавшиеся при каждом присоединении дуги графы записывались в списки соответствующих групп (1-18). b) Перебор вариантов развития / редукции графа. (vybor=5 или 6) Моделирование развития аналогично этапу моделирования развития дерева. При моделировании редукции, на выбор дуги к отсоединению накладывалось ограничения сохранения целостности графа, о) Проверка на симметрию. Полученный перечень дуг проверялся на уникальность среди ранее сформированных перечней (структур графов соответствующей группы) относительно симметричности отображения. Уникальный записывался, неуникальный отбрасывался. 2. Вторая половина программ. Расчёт статистик. Для расчёта некоторых статистик необходимо отыскание кратчайших путей между вершинами. Был применён следующий итерационный алгоритм"; ? Инициация (шаг 0). Для каждой вершины считаем, что список кратчайших путей из неё длины О (TR) состоит только из неё самой, ? Итерация. На каждом шаге N рассматриваем все возможные продолжения путей из списка кратчайших для шага N-1 (TR). Если данное продолжение является кратчайшим путём, заносим его в новый список (TRN). ? Итерационный переход. Запоминаем кратчайшие пути шага N (TR) в накопителе (TRS). Считаем новый список основным (TRN- TR). ? Выход из алгоритма. Прекращаем работу, если вновь сформированный список (TRN) оказывается пустым. Сравнение графов одной группы. (Определение значений целевых функций). Программная реализация. Программа PARETY_P (пробегает файлы статистик GR , GTR ) Принципы, положенные в основу. Вначале сравнения предполагаем, что все Z имеют наивысшие значения. Если в процессе сравнения выясняется иное - понижаем оценку значения Z. Процесс сравнения организован следующим образом. Пробегаем весь список файлов группы сверху вниз. Сравниваем каждый граф со всеми графами ниже его "Разработано множество способов отыскания кратчайших путей. Реализованный ниже схож (насколько автор понял) с методом «метлы», приведённом в [62. Гл. 6]. по списку. Если в результате парного сравнения оценка значений некоторых Z к.-л. [из двух] графов уменьшается - фиксируем это. Если один из графов хуже другого по всем Z (Р1_3=3) - исключаем его из дальнейшего рассмотрения. По результатам сравнения разносим графы по классам (процедура CLASSIF). Создание таблиц переходов между графами соседних групп. Программная реализациям Программа LINKP создаёт файлы таблиц переходов LINK (Часть 1), LNKT (Часть 2). ( - Номера групп. Например, LINK1819 - таблица переходов между графами групп 18 и 19 Части 1.) Принципы, положенные в основу. Создание таблиц переходов необходимо в качестве базы для выделения трендов. Для каждой группы (кроме последней) пробегаем список графов. Для каждого графа рассматриваем все возможные варианты развития (аналогично программам PR# _P в части формирования перечня дуг при моделировании развития сети). Если очередной вариант развития (т.е. граф соседней группы) присутствует в списке соседней группы - заносим запись об этом в таблицу. Противный случай означает, что данный вариант не рассматривался. Формирование списков трендов. Программная реализация. Программа TRENDS_P создаёт файлы списков трендов TREN[D/T]S[L][3] (название в зависимости от номера Части: 1 - D; 2 Т, и от используемой классификации. Например, TRENTS - список трендов по классификации 2Р для Части 2.) Принципы, положенные в основу. Сформированные ранее таблицы переходов между графами соседних групп дают теоретическую возможность сформировать списки трендов. Практически составить полный список не представляется возможным, ввиду его необъятности . Поэтому Если предположить, что каждый граф имеет всего 2 варианта развития (т.е. 2 графа в соседней группе, отличающихся от него только наличием одной лишней дуги) то количество трендов длины L, исходящих из этого графа є [2, 2L] пришлось априорно ограничить область поиска оптимальных трендов. Алгоритм был таков.
