Имитационное моделирование вероятностных транспортных потоков региона
Ставится задача исследования вероятностных транспортных потоков региона. Формулируются особенности формализациитранспортной сети со множеством входов и выходов для построения имитационной модели с целью поиска максимальногопотока. Сообщается о составе и назначении процедур имитационной модели, объед...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/768 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Имитационное моделирование вероятностных транспортных потоков региона / Гируц П.Л., Максимей И.В., Сукач Е.И.,Еськова О.И. // Математические машины и системы. – 2007. – № 1. – С. 99 – 104. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-768 |
|---|---|
| record_format |
dspace |
| spelling |
Гируц, П.Л. Максимей, И.В. Сукач, Е.И. Еськова, О.И. 2008-06-27T10:03:36Z 2008-06-27T10:03:36Z 2007 Имитационное моделирование вероятностных транспортных потоков региона / Гируц П.Л., Максимей И.В., Сукач Е.И.,Еськова О.И. // Математические машины и системы. – 2007. – № 1. – С. 99 – 104. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/768 681.3 Ставится задача исследования вероятностных транспортных потоков региона. Формулируются особенности формализациитранспортной сети со множеством входов и выходов для построения имитационной модели с целью поиска максимальногопотока. Сообщается о составе и назначении процедур имитационной модели, объединяющей алгоритм Форда-Фалкерсона иметод Монте-Карло. Библиогр.: 4 назв. Ставиться задача дослiдження ймовiрних транспортных потокiв регiону. Формулюються особливостi формалiзацiїтранспортної мережi з множиною входiв i виходiв для побудови iмiтацiйної моделi, яка має цiль знайти максимальний потiк.Повiдомляється про склад i призначення процедур iмiтацiйної моделi, яка об’єднує алгоритм Форда-Фалкерсона i методМонте-Карло. Бібліогр.: 4 назв. It is considered the task of the research of the probabilistic transport floods of region. There are formulated the peculiarities of theformalization of traffic network with the multitude of entrances and ways out for building of simulation model, with the purpose ofsearching maximal flood. It is informed about composition and assigning of the procedures of simulation model the algorithm ofFord-Falkerson and method Monte-Karlo. Refs.: 4 titles. ru Інститут проблем математичних машин і систем НАН України Моделювання і управління великими системами Имитационное моделирование вероятностных транспортных потоков региона Iмітаційне моделювання ймовірних транспортних потоків регіону Simulation modelling of the probabilistic transport floods of the region Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Имитационное моделирование вероятностных транспортных потоков региона |
| spellingShingle |
Имитационное моделирование вероятностных транспортных потоков региона Гируц, П.Л. Максимей, И.В. Сукач, Е.И. Еськова, О.И. Моделювання і управління великими системами |
| title_short |
Имитационное моделирование вероятностных транспортных потоков региона |
| title_full |
Имитационное моделирование вероятностных транспортных потоков региона |
| title_fullStr |
Имитационное моделирование вероятностных транспортных потоков региона |
| title_full_unstemmed |
Имитационное моделирование вероятностных транспортных потоков региона |
| title_sort |
имитационное моделирование вероятностных транспортных потоков региона |
| author |
Гируц, П.Л. Максимей, И.В. Сукач, Е.И. Еськова, О.И. |
| author_facet |
Гируц, П.Л. Максимей, И.В. Сукач, Е.И. Еськова, О.И. |
| topic |
Моделювання і управління великими системами |
| topic_facet |
Моделювання і управління великими системами |
| publishDate |
2007 |
| language |
Russian |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Iмітаційне моделювання ймовірних транспортних потоків регіону Simulation modelling of the probabilistic transport floods of the region |
| description |
Ставится задача исследования вероятностных транспортных потоков региона. Формулируются особенности формализациитранспортной сети со множеством входов и выходов для построения имитационной модели с целью поиска максимальногопотока. Сообщается о составе и назначении процедур имитационной модели, объединяющей алгоритм Форда-Фалкерсона иметод Монте-Карло. Библиогр.: 4 назв.
Ставиться задача дослiдження ймовiрних транспортных потокiв регiону. Формулюються особливостi формалiзацiїтранспортної мережi з множиною входiв i виходiв для побудови iмiтацiйної моделi, яка має цiль знайти максимальний потiк.Повiдомляється про склад i призначення процедур iмiтацiйної моделi, яка об’єднує алгоритм Форда-Фалкерсона i методМонте-Карло. Бібліогр.: 4 назв.
It is considered the task of the research of the probabilistic transport floods of region. There are formulated the peculiarities of theformalization of traffic network with the multitude of entrances and ways out for building of simulation model, with the purpose ofsearching maximal flood. It is informed about composition and assigning of the procedures of simulation model the algorithm ofFord-Falkerson and method Monte-Karlo. Refs.: 4 titles.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/768 |
| citation_txt |
Имитационное моделирование вероятностных транспортных потоков региона / Гируц П.Л., Максимей И.В., Сукач Е.И.,Еськова О.И. // Математические машины и системы. – 2007. – № 1. – С. 99 – 104. |
| work_keys_str_mv |
AT girucpl imitacionnoemodelirovanieveroâtnostnyhtransportnyhpotokovregiona AT maksimeiiv imitacionnoemodelirovanieveroâtnostnyhtransportnyhpotokovregiona AT sukačei imitacionnoemodelirovanieveroâtnostnyhtransportnyhpotokovregiona AT esʹkovaoi imitacionnoemodelirovanieveroâtnostnyhtransportnyhpotokovregiona AT girucpl imítacíinemodelûvannâimovírnihtransportnihpotokívregíonu AT maksimeiiv imítacíinemodelûvannâimovírnihtransportnihpotokívregíonu AT sukačei imítacíinemodelûvannâimovírnihtransportnihpotokívregíonu AT esʹkovaoi imítacíinemodelûvannâimovírnihtransportnihpotokívregíonu AT girucpl simulationmodellingoftheprobabilistictransportfloodsoftheregion AT maksimeiiv simulationmodellingoftheprobabilistictransportfloodsoftheregion AT sukačei simulationmodellingoftheprobabilistictransportfloodsoftheregion AT esʹkovaoi simulationmodellingoftheprobabilistictransportfloodsoftheregion |
| first_indexed |
2025-11-25T23:07:20Z |
| last_indexed |
2025-11-25T23:07:20Z |
| _version_ |
1850577946710900736 |
| fulltext |
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 99
УДК 681.3
П.Л. ГИРУЦ, И.В. МАКСИМЕЙ, Е.И. СУКАЧ, О.И. ЕСЬКОВА
ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ВЕРОЯТНОСТНЫХ ТРАНСПОРТНЫХ
ПОТОКОВ РЕГИОНА
Abstract: It is considered the task of the research of the probabilistic transport floods of region. There are formulated
the peculiarities of the formalization of traffic network with the multitude of entrances and ways out for building of
simulation model, with the purpose of searching maximal flood. It is informed about composition and assigning of the
procedures of simulation model the algorithm of Ford-Falkerson and method Monte-Karlo.
Key words: simulation modelling, рrobabilistic transport floods, the search of maximal flood, the algorithm of Ford-
Falkerson, method Monte-Kаrlo.
Анотація: Ставиться задача дослiдження ймовiрних транспортных потокiв регiону. Формулюються
особливостi формалiзацiї транспортної мережi з множиною входiв i виходiв для побудови iмiтацiйної моделi,
яка має цiль знайти максимальний потiк. Повiдомляється про склад i призначення процедур iмiтацiйної
моделi, яка об’єднує алгоритм Форда-Фалкерсона i метод Монте-Карло.
Ключові слова: iмiтацiйне моделювання, ймовiрнi транспортнi потoки, пошук максимального потоку,
алгоритм Форда-Фалкерсона, метод Монте-Карло.
Аннотация: Ставится задача исследования вероятностных транспортных потоков региона.
Формулируются особенности формализации транспортной сети со множеством входов и выходов для
построения имитационной модели с целью поиска максимального потока. Сообщается о составе и
назначении процедур имитационной модели, объединяющей алгоритм Форда-Фалкерсона и метод Монте-
Карло.
Ключевые слова: имитационное моделирование, вероятностные транспортные потоки, поиск
максимального потока, алгоритм Форда-Фалкерсона, метод Монте-Карло.
1. Введение
Объектом исследования является h -ый вариант системы транспортных потоков региона, имеющей
графовую структуру hG , определяемую матрицами
ijh cC = ; ijh lL = ; 00
ijxX = ; ijh qQ = , (1)
где ijc – пропускные способности ветвей графа hG , соединяющих узлы i и j ; / ij – расстояния
между узлами; 0
ijx – начальный поток по ветви ij (скорость движения транспортных средств); ijq –
стоимость единицы пути движения транспортного средства по ветви ij . Существует множество
входов в сеть ),1( mzZ == , где m – общее количество входов и выходов из сети ),1( nyY == ,
где n- общее количество выходов из сети. Максимальный поток между узлами zyϕ распределяется
по ветвям сети k
ijzy
k
zy xX = , где k – номер итерации алгоритма Форда-Фалкерсона [1] при
определении максимального значения потока zyϕ . В сети, кроме транзитных потоков, существуют
местные транспортные потоки внутри региона, которые назовём “противопотоками”. Естественно,
они снижают пропускные способности ветвей графа hG . Предполагается, что величина пропускных
способностей “противопотока” определяется функцией распределения )(υijH . Поэтому
пропускные способности ветвей ij графа hG из-за “противопотоков” представляют собой
случайную величину, определяемую с помощью функций распределения )()~( υijijij HccF −= .
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 100
Наличие “противопотоков” внутри hG обусловливает вероятностный характер пропускных
способностей на многих ветвях графа hG . Кроме того, в сети существует множество входов и
выходов. Необходимо отметить, что для случая, когда элементы матрицы пропускных
способностей hC являются детерминированными величинами, известны алгоритмы решения
задачи о максимальном потоке [2]. Но вероятностный характер пропускных способностей ветвей
графа hG не позволяет решить эту задачу с помощью данных алгоритмов и обусловливает
актуальность использования имитационной модели, основанной на сочетании процедуры Монте-
Карло и теоремы Форда-Фалкерсона.
Таким образом, ставятся задачи определения на имитационной модели (ИМ) множества
значений максимальных потоков }{ zyϕ , а также поиска узких мест в сети hG , устранение которых
позволит достичь максимальных потоков во всех четырёх направлениях: с запада (WE) на восток
(OS) и обратно, а также с севера (NO) на юг (ZD) и обратно.
2. Формализация объекта моделирования
Определим показатель затрат движения транспортных средств вдоль ветви ij графа hG :
*
33
*
21 )( ijij
ij
ij
ijij xq
x
f ⋅⋅+
⋅+⋅= δδδ
l
l , (2)
где ,10 1 ≤≤ δ ,10 2 ≤≤ δ 10 3 ≤≤ δ – весовые коэффициенты важности трёх составляющих
затрат соответственно (расстояния, времени движения, стоимости движения); ∑
=
=
3
1
1
k
kδ .
Звёздочка у составляющих выражения (2) означает нормированные значения соответствующих
затрат, изменяющихся на интервале [0,1]. Нормировка осуществляется максимальным значением
соответствующих затрат во всех ветвях ij графа hG . Поскольку при движении транспортных
средств по сети hG необходимо стремиться к минимизации этих затрат, то в качестве показателя
“выгоды” максимального потока берётся усреднённая характеристика затрат, которая вычисляется
по матрице распределений максимального потока по всем ветвям ij графа hG :
∑∑=
i j
ijzy fФ
* . (3)
Этот обобщённый показатель определяет величину затрат транспортных средств в сети
hG при максимальном потоке zyϕ . Как видим, с одной стороны zyϕ необходимо максимизировать,
а с другой стороны zyФ должно быть минимальным. Эти два противоречивых критерия определяют
область компромисса при заданном векторе важности ( 321 ,, δδδ ) для исследователя, которую
необходимо определить на ИМ.
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 101
Воспользуемся принципом суперпозиции: исследуем распределение потоков в одном из
направлений, а затем рассмотрим подобное распределение с помощью матрицы, в которой
строками являются номера-входы { Z } в графе hG , а столбцами – номера- выходы }{Y из сети.
Это означает, что zyϕ и zyФ есть соответственно величина потока и величина его интегральной
“выгоды“ между входом Z и выходом Y из графа hG , описываемого зависимостью (3). Величину
потока k
ij
k
zy xX = и его минимальное значение zyϕ находим как результат применения процедуры
Монте-Карло и последующего их усреднения по выборке объема N . С помощью ИМ эта задача
решается следующим образом. На l-ой итерации применения процедуры Монте-Карло
вероятностная задача превращается в классическую. При этом определяются компоненты
матрицы пропускных способностей путём вычисления ijlijij cc υ−=~ , где ijlυ определяется по
функции распределения )(υijH путём нахождения единичного жребия третьего типа [1].
В качестве начального потока выбирается матрица 00
ijxX = . Используется матрица
пропускных способностей ijlhl cC = , и с помощью алгоритма Форда-Фалкерсона определяется на
k-ой итерации само распределение потока по сети k
ijzyl
k
zyl xX = и его значение zylϕ . При
использовании (2) и (3) и k
zylX определяется обобщённый показатель “выгоды” этого потока zylФ .
Значения zylϕ и zylФ запоминаются в базе данных модели (БДМ). Модифицируется номер
итерации процедуры Монте-Карло ( )| | 1= + , и все расчёты повторяются сначала. По завершении
N итераций этих расчётов в БДМ модели сформированы следующие выборки: для каждого
элемента матрицы распределений потока имеется своя выборка Nlxijzyl ,1},{ = ; значения
максимального потока Nlzyl ,1},{ =ϕ ; интегральные показатели “выгоды” потока NlФzyl ,1},{ = .
По этим выборкам объема N формируются средние значения, выборочные дисперсии и
точности вычисления этих характеристик с помощью процедуры Монте-Карло по известным
функциям:
k
ijzy
k
zy xX = ; zyϕ ; zyФ . (4)
Применив эту процедуру для вычисления всех максимальных потоков при всех сочетаниях
входов ( )Z и выходов ( )Y , получим матрицы zyϕ и zyФ . Поскольку все матрицы k
zyX из (4)
распределены на одном и том же графе hG , то их можно покомпонентно сложить:
∑=
zy
k
ijzy
k
zy xX 0 (5)
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 102
и получить значение распределения по hG интегрального максимального потока. Для поиска узких
мест в hG проведём покомпонентное вычитание из этой матрицы матрицы пропускных
способностей hC :
∑−=∆
zy
k
ijzyijh xCX . (6)
В тех местах, где элемент данной матрицы будет иметь отрицательное значение,
находятся “узкие места” в hC . На величину этой разности пропускные способности ijC должны
быть увеличены для того, чтобы граф hG обеспечивал максимальные потоки транзитных
маршрутов в одном из направлений из всех точек Z во все точки Y .
Аналогичным образом можно использовать ИМ для нахождения в hG “узких мест”,
определения максимальных потоков и оценки их интегральной “выгоды” для остальных
направлений в сети.
3. Имитационная модель вероятностных транспортных потоков региона
На основе формализации транспортной сети hG была реализована имитационная модель, в
которой объединены алгоритм Форда-Фалкерсона, процедура Монте-Карло и использованы
принципы суперпозиции независимых транспортных потоков в одном и том же графе hG .
Имитационная модель реализуется на основе процессного способа имитации [3], и при этом
используются средства поддержки имитационного эксперимента [4]. Поэтому модель представляет
собой объединение десяти процедур, каждая из которых реализует один из шагов технологии
использования ИМ для решения поставленной задачи исследования вероятностных транспортных
потоков региона.
Рассмотрим динамику реализации десяти шагов технологии решения поставленной задачи.
На шаге 1 с помощью процедуры PR.ZAPIT осуществляется ввод исходной информации в БДМ. В
качестве начальной информации PR.ZAPIT вводит информацию, представленную зависимостью
(1). При этом в ходе “запитки” ИМ hG вводится множество входов { }Zr и выходов { }Yr для
каждого из r направлений: 1r = , запад-восток (WE→OS); 2r = , восток-запад (OS→WE); 3r =
север-юг (NO→ZD); 4r = юг-север (ZD→NO). Вводится также матрица, элементами которой
являются функции распределения “противопотоков” ijHH = внутри графовой структуры hG . На
шаге 2 с помощью процедуры PR.FOPROP производится корректировка матрицы пропускных
способностей hC , используя при этом матрицу H для определения пропускных способностей у
тех ветвей графа hG , для которых имеет место сочетание транзитных потоков, имеющих
постоянные пропускные способности ijC с вероятностными пропускными способностями
“противопотоков”, задаваемыми матрицей распределений ijH j. На шаге 3 с помощью процедуры
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 103
PR.FORFAL по алгоритму Форда-Фалкерсона для очередной l-ой реализации процедуры Монте-
Карло определяется значение максимального потока zylϕ и его распределение по ветвям
транспортной сети k
ijzyl
k
zyl xX = . Эти статистики запоминаются в БДМ в качестве элементов
выборок статистик имитации. Затем на шаге 4 с помощью процедуры PR.MONTEC реализуется
самый внутренний цикл из N реализаций, который начинается с повторения шага 3, но уже с (l+1)-
ой реализацией. По завершении N реализаций на шаге 4 PR.MONTEC считывает из БДМ выборки
статистик, по которым она вычисляет средние значения и выборочные дисперсии. В итоге эта
процедура формирует оценки средних значений статистик реализации максимального потока xyϕ и
k
ijxy
k
zy xX = , которые также запоминаются в БДМ. На шаге 5 с помощью процедуры PR.INTVIG,
используя матрицу k
zyX , с помощью формул (2) и (3) определяется интегральный показатель
“выгоды“ максимального потока zyФ , который также запоминается в БДМ. На шаге 6, реализуемом
процедурой PR.FOMATR во внешнем цикле, который равен количеству потоков в каждом из
направлений, целью является формирование следующих матриц. Во-первых, формируются две
матрицы максимальных потоков и “выгоды“ этих потоков xyϕ и xyФ . Во-вторых, поскольку все
потоки существуют внутри одной и той же сети hG , на шаге 7 формируется матрица интегральных
потоков ∑=
zy
k
ijzy
h
zy xX , которые появляются при наличии нескольких максимальных потоков от
узлов на входах { }Z до узлов на выходах { }Y из сети. На шаге 8 с помощью процедуры
PR.UZKMES производится покомпонентное вычитание двух матриц h
zy
zy
k
ijzyij XxC ∆=−∑ . В итоге
те величины этих разностей, которые являются отрицательными, они и будут “узкими местами” в
hG . Поскольку сами абсолютные значения этих разностей трудно оценить, то процедура
PR.UZKMEST формирует матрицу относительных превышений, компонентами которой являются
%100
~ ⋅
−
=∆
∑
ij
xy
k
ijxyij
h
zy c
xc
X .
При этом принимаются во внимание те элементы этой матрицы, которые имеют
отрицательное значение 0
~ ≤∆ h
zyX , поскольку именно они и будут “узкими местами” в графе hG
для обеспечения максимальных потоков от всех узлов входа { }Z ко всем узлам выхода { }Y из
hG . На шаге 9 процедурой PR.SMNAP начинается самый важный цикл моделирования графа hG
во всех четырёx направлениях. Результаты, полученные на шаге 8, запоминаются в БДМ, рабочие
массивы модели обнуляются, и весь процесс имитации вероятностного hG повторяется, но каждый
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 104
раз для следующего направления. Это означает, что в каждом цикле вычисляются статистики по
направлениям: WE→OS; OS→WE; NO→ZD; ZD→NO.
В итоге выполнения всех шагов имитации в БДМ находятся статистики в виде упомянутых
матриц по четырём направлениям транзитных потоков региональной транспортной сети. Поэтому
на шаге 10 с помощью процедуры PR.PESMEN исследователь принимает одно из возможных
решений, используя при этом известные критерии принятия решений. При этом он по каждому
направлению имеет в своём распоряжении две матрицы zyϕ и zyФ . В итоге исследователь по
первой матрице выбирает вариант, максимизирующий общий поток в сети, а по второй матрице он
оценивает затраты на реализацию этого максимального потока.
4. Выводы
С помощью предлагаемой имитационной модели вероятностных транспортных потоков региона
исследователи могут решить следующие задачи проектного моделирования:
– оценка различия существующей пропускной способности сети и суммарных затрат
транспортных средств на их передвижение по сети от найденных значений максимального потока и
минимальных затрат на их передвижение по сети при существующих характеристиках сети hC ,
hL , hQ ;
– определение узких мест в сети hG , устранение которых позволит увеличить величину
потока kX
при минимальном значении функционала (3);
– оценка ухудшения значений zylϕ и zylФ при появлении чрезвычайной ситуации, которая
приводит к тому, что пропускная способность некоторых ветвей региона окажется нулевой.
Таким образом, реализация алгоритма имитации вероятностных транспортных потоков на
основе процедуры Монте-Карло позволяет решать задачи проектного моделирования при наличии
“противопотоков” местного характера в транспортной сети регионов и обосновать величину ущерба
от появления чрезвычайных ситуаций в регионе.
СПИСОК ЛИТЕРАТУРЫ
1. Жогаль С.И., Максимей И.В. Задачи и модели исследования операций: Учебное пособие. – Гомель: БелГУТ,
1999. – Ч.1: Аналитические модели исследования операций. – 109 с.
2. Зайченко Ю.П. Исследование операций: Учебное пособие.– Киев: Издательский дом «Слово», 2002. – 320 с.
3. Максимей И.В. Имитационное моделирование на ЭВМ. – Москва: Радио и связь, 1983. – 232 с.
4. Максимей И.В., Сукач Е.И. Средства технологической поддержки имитационного эксперимента: Учебное
пособие. – Гомель: ГГУ им. Ф. Скорины, 2002. – 107 с.
|