Економіка/математичні методи в економіці

К.ф.м.н. Корольов М.Є.,ст.Насонкін Д.О.

Горлівський Автомобільно-дорожній інститут,Україна

Моделювання оптимального пасажиропотоку в місті Донецьк під час проведення ЄВРО 2012

У нашому житті взаємодію і циркуляцію різних потоків ми представляємо у вигляді мережі. Мережне уявлення взаємодії і циркуляції потоків необхідно, щоб оцінити й обчислити різні характеристики, що описують умови існування і поведінки потоків в таких мережах. Більшість виникаючих завдань може бути вирішено за допомогою теорії потоків в мережах. Теорія потоків в мережах - одне з сучасних напрямків розвитку комп'ютерних наук в цілому та теорії графів зокрема. У цій теорії в якості основи розглядаються рух потоків у мережах від джерела до стоку.Розглянемо це на практиці.

В місто Донецьк, на залізничний вокзал (початковий пункт) для перегляду одного з матчів «EURO 2012», який повинен пройти на стадіоні «Донбас-Арена» (сток) прибули 6000 вболівальників. Спочатку вболівальники відправились у наступні міста відпочинку: готель «Великобританія» (пункт 2), «Мотель» (пункт 3) та торгово - розважальний комплекс «Донецьк - Сіті» (пункт 4). Для того щоб потрапити в указані місця, вболівальники використали міський пасажирський автотранспорт, зокрема маршрутами : 2, 38-Б, 83, 46-Б, 32, 37, 38, 36. Визначимо максимальний потік від початкового до кінцевого пункту, дати оцінку ступеню використання маршруту. Нижче приведено номера маршрутів, які обслуговують наступні пункти : маршрут №37 пункт 1-2, №32-1-3; №2-1-4; №38-2-5, №36-2-3; №46-Б-3-4, №83-3-5, №38-Б- 4-5.

Виділимо на карті пересування вболівальників у місті Донецьк. Отримуємо модель.(рис. 1)

Рисунок 1 - Остаточна модель пересування вболівальників у місті Донецьк

Ідея даного алгоритму полягає в знаходженні наскрізних шляхів з позитивними потоками від джерела до стоку.У процесі виконання алгоритму частини цих пропускних здатностей "забираються" потоками, що проходять через дане ребро, у результаті кожне ребро буде мати залишкову пропускну здатність,а мережа буде називатися залишкової.

В першій інтеграції наскрізний шлях(f₁) дорівнює 20,в останніх чотирьох інтеграціях f_2,3,4,5=10.

Розрахуємо максимальний обсяг потоку в мережі F=f₁ +f₂ + ... +f₅ = 20 + 10 + 10 + 10+ 10 = 60 одиниць. Значення потоків по різних ребрах обчислюються шляхом вирахування останніх значень залишкових пропускних здатностей з первісних значень пропускних здатностей. Результати обчислень наведені в таблиці 1.

Таблиця 1- Результати обчислень пропускних здатностей.

Ребро	( )-(cij, сji)	Величина потоку	Напрямок
(1,2)	(20, 0) - (0, 20) = (20. -20)	20	12
(1,3)	(30, 0) - (0, 30) = (30, -30)	30	1 3
(1,4)	(10, 0)-(0, 10) = (10,-10)	10	14
(2,3)	(40,0)-(40,0) = (0,0)	0	-
(2,5)	(30,0)-(10, 20) = (20,-20)	20	2 5
(3,4)	(10, 5)-(0, 15) = (10,-10)	10	3 4
(3,5)	(20,0)-(0,20) = (20,-20)	20	35
(4,5)	(20, 0) - (0, 20) = (20, -20)	20	4 5

Реалізувавши розроблену модель можно зробити висновок, що максимальна величина потоку(3000 вболівальників) буде між напрямком 1-3, тобто між залізничним вокзалом та мотелем. Тому треба уділити увагу маршруту 32, який перевозить пасажирів між пунктами 1-3. Прийняти ряд рішень по збільшенню кількості автобусів на час проведення Euro 2012. Маршрут 36 якій перевозить пасажирів між пунктами 2-3(між готелем «Великобританія» та мотелем) не буде користуватися попитом серед вболівальників. Величина цього потоку дорівнює 0, тому він буде не актуальний (не раціональним). Всі останні маршрути мають майже однакові величини,тому будуть користуватися майже однаковим попитом серед вболівальників.

Література:

1. Берж К. Теория графов и ее применения. М.: Иностранная литература, 1962. - 319с.

2. Кормен, Томас X., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. 324:Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. — М. : Издательский дом "Вильяме", 2005. — 1296 с. : ил. — Парал. тит. англ.

3. Косоруков О.А., Мищенко А.В. Исследование операций: Учебник / Косоруков О.А., Мищенко А.В. // Под общ. ред. д.э.н., проф. Н.П. Тихомирова. — М: Издательство «Экзамен», 2003. — 448 с.