Початкові відомості

Використання теорії графів при дослідженні транспортних систем

Класифікація економіко - математичних методів, що використовуються при розв’язанні задач експлуатації транспортних систем

Математичні методи, які використовуються в дисципліні, тобто при розв'язанні задач експлуатації залізниць, можна класифікувати за наступними основними напрямками.

1 Задачі, які виражені аналітичною формулою, по якій визначається ряд часткових значень функції; функція може бути лінійною (наприклад, величина потрібного вагонного парку в залежності від роботи залізниці при заданому обороті вагона) чи нелінійною (наприклад, значення основного питомого опору вантажених чотирьох - і восьмиосних вагонів як функція швидкості), метод мінімальних квадратів, регресійний аналіз.

2 Задачі, у яких математична залежність між перемінними задається диференціальним рівнянням чи системою диференціальних рівнянь. Після їх рішення точним чи наближеним методом (наприклад Рунге – Кутта) знаходиться шукана форма у вигляді таблиці її значень. Це як правило рівняння руху (поїзда, вагонів при скочуванні з гірки і так далі).

3 Екстремум - задачі, при яких застосовуються методи лінійного і нелінійного програмування.

4 Різноманітні комбінаторні задачі і логічні задачі, що не мають загальних методів розв'язання. Вони вирішуються безпосереднім розрахунком усіх можливих варіантів або по спеціальних методиках, розроблених для конкретних задач (метод перебору), тобто для процедури послідовного наближення до шуканого результату. Наприклад: складання графіка руху і плану формування поїздів.

5 Імовірнісні задачі, розв'язувані з застосуванням загальних методів теорії ймовірностей, математичної статистики (визначення імовірності подій, функції розподілу, кореляційні залежності), теорія масового обслуговування, метод Монте – Карло (моделювання випадкових процесів). Ці методи використовуються при дослідженні характеру відхилення вагонопотоків від середніх значень, розрахунку пропускної спроможності складних станційних горловин.

6 Теорія графів і потоків у мережах.

7 Методи імітаційного моделювання. При розв'язанні задач методом імітаційного моделювання досліджуваного процесу за допомогою ЕОМ рішення аналітичної задачі заміняється відтворенням великого числа варіантів реалізації випадкового процесу, спеціально побудованого за умовами задачі (RND). Застосовується при рішенні складних задач.

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

За допомогою теорії графів, як розділу математики, вивчаються та досліджуються закономірності графічних об’єктів (звідки випливає й назва). Теорія графів як наука сформувалась в середині 30 – х років 20 століття.

Геометрично граф – це сукупність точок та з’єднуючих їх ліній.

Математично граф існує, якщо задано непусті множини , при цьому кожному елементу множини U поставлена у відповідність впорядкована пара елементів (i, j) з множини І. Елементи множини І називаються вершинами графа, а елементи множини U – ребрами графа. Як приклад маємо граф (рис.8.1).

Рис. 8.1. Приклад математичного графа

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

Теорія графів пов’язана з таким математичним апаратом як: теорія множин, теорія ймовірностей, теорія матриць, математична логіка.

Перше застосування теорії графів пов’язане із розв’язанням відомим математиком Леонардом Ейлером у 1736 році задачі про Кенігсбергські мости (рис. 8.2, а), яка формулювалась таким чином: чи можна, вийшовши з будь-якої частини міста та пройшовши всіма 7 мостами, повернутись на початкове місце, ідучи тільки один раз по кожному містку. Цю задачу можна розглядати як приклад оптимізації маршруту для екскурсійного бюро.

Рис. 8.2 План міста Кенігсберг (а) та відповідний йому граф (б).

Представивши план міста у вигляді графа (рис. 8.2, б), Л. Ейлер довів, що поставлена задача не має вирішення. Воно може існувати у тому випадку, коли кожна вершина зв’язана з парним числом ребер.

Дата добавления: 2014-01-07