Xreferat.com » Рефераты по транспорту » Моделювання транспортної мережі

Моделювання транспортної мережі

/> дорівнює елементові Моделювання транспортної мережі в матриці Моделювання транспортної мережі.

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

При аналізі транспортних мереж часто виникає задача визначення максимального потоку, що може пропустити дана мережа, а також задача розподілу цього потоку по дугах мережі.

З математичної точки зору задача про максимальний потік формулюється в такий спосіб: при заданій конфігурації мережі і відомої пропускної здатності Моделювання транспортної мережі знайти ненегативні значення Моделювання транспортної мережі, що задовольняють умовам і, що максимізують функцію Моделювання транспортної мережі, тобто


Моделювання транспортної мережі


Алгоритм для знаходження максимального потоку був запропонований Фордом і Фалкерсоном і полягає в поступовому збільшенні потоку, що пропускається по мережі, доти, поки він не стане найбільшим. Алгоритм заснований на теоремі Форда-фалкерсона: у будь-якій транспортній мережі максимальний потік із джерела Моделювання транспортної мережі в стік Моделювання транспортної мережі, дорівнює мінімальній пропускній здатності розрізу, що відокремлює Моделювання транспортної мережі від Моделювання транспортної мережі.

Крок 0. Призначаємо вузлові 15 постійну мітку [0, -].

Крок 1. З вузла 15 можна досягти вузлів 21 2 12. Обчислюємо мітки для цих вузлів, у результаті одержуємо наступну таблицю міток:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

21 [512,15] Тимчасова
2 [237,15] Тимчасова

Серед вузлів 21, 2, 12, вузол 12 має найменше значення відстані (U12=172). Тому статус мітки цього вузла змінюється на «постійна».

Крок 2. З вузла 12 можна потрапити у вузли 2, 23, 22. Одержуємо наступний список вузлів.

Тимчасовий статус мітки [237,15] вузла 2 заміняється на постійний (U2=237).

Крок 3. З вузла 2 можна досягти вузлів 21, 22, 31. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15] Тимчасова
21 [370+512,2]=[882,2] Тимчасова
22 [1009,12] Тимчасова
22 [696+237,2]=[933,2] Тимчасова
23 [810,12] Тимчасова
31 [655+237,2]=[892,2] Тимчасова

Тимчасовий статус мітки [512,15] вузла 21 заміняється на постійний (U21=512).

Крок 4. З вузла 21 можна досягти вузлів 31. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

22 [933,2] Тимчасова
23 [810,12] Тимчасова
31 [892,2] Тимчасова
31 [512+289,21]= [801,21] Тимчасова




Тимчасовий статус мітки [801,21] вузла 31 заміняється на постійний (U31=801).

Крок 5. З вузла 31 можна досягти вузлів 22, 38. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

31 [801,21]

Постійна

22 [933,2] Тимчасова
22 [801+237,31]= [1038,31] Тимчасова
23 [810,12] Тимчасова
38 [801+197,31]= [992,31] Тимчасова




Тимчасовий статус мітки [810,12] вузла 23 заміняється на постійний (U23=810).

Крок 6. З вузла 23 можна досягти вузла 22, 38, 3. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

31 [801,21]

Постійна

23 [810,12]

Постійна

22 [933,2] Тимчасова
22 [810+535,23]= [1345,23] Тимчасова
38 [992,31] Тимчасова
38 [810+929,23]= [1739,23] Тимчасова
3 [810+1045,23]= [1855,23] Тимчасова

Тимчасовий статус мітки [933,2] вузла 22 заміняється на постійний (U22=933).

Крок 7. З вузла 22 можна досягти вузлів 38, 3. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

31 [801,21]

Постійна

23 [810,12]

Постійна

22 [933,2]

Постійна

38 [992,31] Тимчасова
38 [933+427,22]= [1360,22] Тимчасова
3 [1855,23] Тимчасова
3 [933+938,22]= [1871,22] Тимчасова

Тимчасовий статус мітки [992,31] вузла 38 заміняється на постійний (U38=992).

Крок 8. З вузла 38 можна досягти вузла 3. Після обчислення міток одержимо наступний їх список:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

31 [801,21]

Постійна

23 [810,12]

Постійна

22 [933,2]

Постійна

38 [992,31]

Постійна

3 [1855,23] Тимчасова
3 [992+116,38]= [1108,38] Тимчасова




На останньому кроці знайдено найкоротшу відстань для вузла 3 – [1108.38]. Таким чином статус мітки вузла 3 змінюється на постійний.

Кінцевий результат міток має такий вигляд:


Вузол Мітка Статус мітки
15

Моделювання транспортної мережі

Постійна

12 [172,15]

Постійна

2 [237,15]

Постійна

21 [512,15]

Постійна

31 [801,21]

Постійна

23 [810,12]

Постійна

22 [933,2]

Постійна

38 [992,31]

Постійна

3 [1108,38]

Постійна





Найкоротший шлях між вузлом 15 і будь-яким іншим вузлом визначається починаючи з вузла призначення шляхом проходження їх у зворотному напрямку за допомогою інформації, представленої в постійних мітках. Найкоротший маршрут між вузлами 15 і 3 має таку послідовність вузлів: (3)→ [1108.38] →(38)→ [992.31] →(31)→ [801.21] →(21)→ (15).

Таким чином, одержуємо шлях загальною довжиною 1108 км.

4. Задача про максимальний потік (алгоритм Форда-Фалкерсона)


Рішення задачі складається з підготовчого етапу і кінцевого числа кроків, на кожнім з яких відбувається припустиме збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.


Таблиця 4.1. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 10 10 10-




12

7 - 7

7 7

2

13 13 - 13 13
13

21

18+
18 - 18-



31



22 22+ -
22 22-

23


22


- 22 22 22

22


21 21
21 21 - 21 21

38





28+ 28 28 - 28-

3






7 7 7+ -

По табл. 4.1. знаходимо шлях l1=(15,21,31,38) зі станції 15 у 3 з позитивною пропускною здатністю. Елементи цього шляху Моделювання транспортної мережі позначаємо знаком «мінус», а симетричні Моделювання транспортної мережі – знаком «плюс». Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг: C1= min {10,18,22,28}=10.

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


Таблиця 4.2. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 10 10- 0




12

7 - 7

7 7

2

13+ 13 - 13 13
13-

21

28
18 - 8



31



22 32 -
22 12

23


22


- 22 22 22

22


21 21+
21 21 - 21 21-

38





38 28 28 - 18

3






7 7+ 17 -

Позначаємо стовпці табл. 4.2, знаходимо другий шлях l2=(15,2,22) зі станції 15 у 3, і розставляємо знаки. Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг:

C2= min {10,13,21}=10.

Змінимо пропускні здатності позначених дуг на Моделювання транспортної мережі (табл. 4.3).


Таблиця 4.3. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 10- 0 0




12

7+ - 7

7- 7

2

23 13 - 13 13
3

21

28
18 - 8



31



22 32 -
22 12

23


22+


- 22 22 22-

22


21 31
21 21 - 21 11

38





38 28 28 - 18

3






7+ 17 17 -

Позначивши стовпці знаходимоl3=(15,12,23).

Величина потоку по шляху Моделювання транспортної мережі: C3= min {10,7,22,}=7.

Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.4.


Таблиця 4.4. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 3- 0 0




12

14+ - 7

0 7-

2

23 13 - 13 13
3

21

28
18 - 8



31



22 32 -
22 12

23


29


- 22 22 15

22


21+ 31
21 21 - 21 11-

38





38 28 28 - 18

3






14 17+ 17 -

Позначивши стовпці знаходимоl4=(15,12,22).

Величина потоку по шляхуl4: C4= min {3,7,11}=3.

Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.5


Таблиця 4.5. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 0 0 0




12

17 - 7

0 4

2

23 13 - 13 13
3

21

28
18 - 8



31



22 32 -
22 12

23


29


- 22 22 15

22


24 31
21 21 - 21 8

38





38 28 28 - 18

3






14 20 17 -

Переглядаючи рядки і позначаючи стовпці переконуємося в тім, що рядок 15 позначити неможливо. Отже, більше не існує жодного шляху з позитивною пропускною здатністю з вершини 15 у вершину 3.

Заключний крок. Віднімаючи з елементів табл. 4.1 відповідні елементи табл. 4.6, одержимо табл. 4.6.


Таблиця 4.6. Матриця пропускних здатностей дуг мережі


15

12

2

21

31

23

22

38

3

15

- 10 10 10




12

-10 -


7 3

2

-10
-


10

21

-10

- 10



31




-10 -

10

23


-7


-

7

22


-3 -10


-
13

38





-10

- 10

3






-7 -13 -10 -

Позитивні елементи цієї таблиці характеризують величини дугових потоків. Величина максимального потоку дорівнює сумі елементів 15-го рядка табл. 4.1 або сумі елементів 3-го стовпця. Усі дуги розрізу Моделювання транспортної мережі є насиченими.

Транспортну мережу загалом можна розглядати як систему, що складається з неоднорідних пристроїв або елементів різної складності, що взаємодіють з транспортними потоками потягів, автомобілів, літаків і т.д.

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

Деякі способи посилення пропускної здатності в той або інший конкретний плановий період виявляються найбільш ефективними на значному числі ліній. Найчастіше це ті способи, що безпосередньо зв'язані з реалізацією основних напрямків технічного прогресу на транспорті. Здійснення їх жадає від народного господарства значної витрати тих або інших ресурсів, від чого різко зростає дефіцит останніх. Таким чином, плануючи терміни посилення ліній, необхідно враховувати обмеженість матеріальних і грошових ресурсів, виділюваних на переоснащення залізничного транспорту. Це ставить на чергу задачу оптимізації розвитку пропускної здатності сукупності декількох ліній або навіть мережі в цілому. Вирішити неї в першому наближенні можна оптимізацією розвитку окремих локалізованих систем – груп ліній з однотипними найбільш ймовірними способами посилення пропускної здатності, а також ліній, зв'язаних загальним вантажопотоком, що розподіляється по них у залежності від рівня технічного оснащення.

Як видно, деякі ділянки мережі завантажені цілком, а деякі не задіяні в перевізному процесі взагалі. Виходом зі сформованої ситуації, для даної транспортної системи, є підвищення пропускних здатностей таких ліній: 10–7 і 10–15. Ще одним способом зменшення навантаження на дані ділянки може стати розподіл загального обсягу перевезень між залізничним і автомобільним транспортом у місцевому повідомленні (якщо сумарні приведені витрати на транспортування автомобільним транспортом не перевищують витрати на транспортування залізничним транспортом). Дані заходи до деякої міри «розвантажать» напружені ділянки і ділянки, що лімітують, транспортної мережі.


Література


Моделирование транспортных систем. Персианов В.А., Скалов К.Ю., Усков Н.С., М-изд-во «Транспорт» 1992 г., – 209 с.

Нелинейные сетевые транспортные задачи. Левит Б.Ю., Лившиц В.Н. Институт комплексных транспортных проблем. Изд-во «Транспорт», 2002 – 257 с.

Левин Д.Ю. Оптимизация потоков поездов. – М.: Транспорт, 1988. – 175 с.

Хорафас Д.Н. Системы и моделирование. Перевод с англ. Изд-во «Мир», М., 1967.

Хейт Ф. Математическая теория транспортных потоков. Перевод с англ. Изд-во «Мир», М., 1966.

Нестеров Е.П. Транспортные задачи линейного программирования. М.: Изд-во «Транспорт», – 1971.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: