w відбувається не більше ніж за O (v 2 e 2) операцій (e - кількість ребер, v - кількість вершин.) При випадково підібраних даних зазвичай потрібно набагато менше - порядку O (ve) операцій.
Але, подібні постановки транспортної задачі і, відповідно, методи їх вирішення не кращим чином в явному вигляді підходять для проблематики, що розглядається в рамках курсового проекту, оскільки в них:
. Не розглядається можливість наявності кількох транспортних мереж.
. Чи не формалізуються витрати на пересадки між транспортними мережами.
. На оптимальність маршруту впливає не тільки вартість перевезення, але і кількість перевезеного вантажу.
. Формулювання завдання більше підходить для задач, в яких відбуваються не разові перевезення, а регулярні поставки і відвантаження логістичних одиниць.
Все це призводить до ідеї пошуку рішення задачі не в рамках лінійного програмування, а в області теорії графів.
2. ПОБУДОВА МОДЕЛІ
.1 Основні поняття і обмеження
У математичній теорії графів та інформатики граф - це сукупність об'єктів зі зв'язками між ними.
Об'єкти представляються як вершини, або вузли графа, а зв'язки - як дуги, або ребра. Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребрах (1).
Граф або неорієнтовані граф G - це впорядкована пара G=(V, E) для якої виконані наступні умови:
· V це безліч вершин або вузлів,
· E це безліч пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами.
Будемо вважати, що в рамках розв'язуваної задачі будуть розглядатися тільки неорієнтовані графи, тобто якщо між двома вершинами (A і B) існує ребро, то шлях від вершини A до вершини B матиме таку ж вартість що й шлях від вершини B до вершини A. Це обмеження не є жорстким і може бути легко обійдено на рівні алгоритмів роботи з графом.
Граф не повинен містити кратних ребер. Будемо вважати, що пару вершин завжди пов'язує тільки єдине ребро. Це обмеження також не є жорстким.
Граф не повинен містити петель, тому петля не має сенсу з точки зору транспортної мережі.
Граф не повинен містити ізольованих вершин, т.к з вершини завжди повинно виходити хоча б одне ребро.
Граф не обов'язково повинен бути зв'язковим, тому пошук може здійснюватися тільки всередині відокремленої області зв'язності.
Граф є зваженим, тобто кожне ребро має певну вагу. В якості вагових коефіцієнтів будуть використовуватися цілі невід'ємні числа. Речові числа не є зручними у зв'язку з тим, що речові числа в машинному поданні завжди зберігаються з втратою точності, що ускладнює виконання операції порівняння і призводить до необхідності закладу спеціальної константи, визначальною точність обчислень.
Негативні числа не використовуватимуться по тому, що негативна вартість у рамках транспортної задачі не має сенсу.
Допускається наявність ребра, що має нульову вагу, в тому випадку якщо деяка вершина одночасно належить кільком графам. У цьому випадку, обігрується ситуація в якій деяка вузлова точка одночасно належить кільком транспортним системам і зміна виду транспорту віднімає нульове кількість ресурсів.
Малюнок 1.1 - Приклад випадку ребра нульової довжини
2.2 Внутрішнє подання даних
Проведемо аналіз способів внутрішнього представлення графів (13) (14):
2.3 Матриця суміжності
Матриця суміжності - таблиця, де як стовпці, так і рядки відповідають вершинам графа. У кожній клітинці цієї матриці записується число, що визначає наявність зв'язку від вершини-рядка до вершині-стовпцю (або навпаки).
Безсумнівним плюсом цього способу подання є можливість швидко відповідати на питання виду «А чи належить ребро (i, j) графу G?». Ще одним плюсом є можливість швидкого оновлення графа. у разі вставки і видалення ребер.
Недоліком є ??вимога до пам'яті - квадрат кількості вершин. Особливо яскраво цей недолік виражається при роботі з транспортними мережами, тому в цьому випадку матриця виходить дуже високого ступеня розрідженості.
2.4 Матриця інцидентності
Кожен рядок відповідає певній вершині графа, а стовпці відповідають зв'язкам графа. У осередок на перетин...
