Математична модель задачі. Кафедра інформаційних технологій

Кафедра інформаційних технологій

Пояснювальна записка

До курсової роботи з дисципліни

«Методи оптимізації»

Виконав студент групи ІТЕП – 41

Факультет АІТ

Новодран М.

Перевірив:

Гайна Г.А.

Київ – 2013

Зміст

1. Вступ………………………………………………………………………..3

2. Математична модель задачі………………………………………………3

3. Обґрунтування вибору методу та алгоритм розв’язання задачі.….....4

4. Розв’язання задачі вручну……………………………………………….5

5. Розв’язання задачі на контрольному прикладі….……………………..9

6. Лістинг програми…………………………………………………………9

7. Список використаної літератури…………………………………….....17

Вступ

З метою закріплення знань і навичок по вирішенню задач оптимізаційного характеру в рамках даної курсової роботи мені була поставлена наступна задача:

«Знайти найкоротшу відстань і маршрут від заводу збірного залізобетону, що знаходиться в пункті 0 до будівельних майданчиків 1–8 при заданій схемі автомобільних шляхів. Знайти також найкоротший шлях холостого пробігу машин за умови, що частина доріг має односторонній напрямок руху (вказано стрілками на схемі).»

Рис. 1

Математична модель задачі

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

Перш ніж представляти алгоритми, необхідно ввести деякі позначення. Пронумеруємо вершини вихідного графа цілими числами від 1 до N. Позначимо через di, jm довжину найкоротшого шляху з вершіни i у вершину j, який у якості проміжних може містити тільки перші m вершин графа. Якщо між вершинами i та j не існує жодного шляху зазначеного типу, то умовно будемо вважати, що di, jm = ∞. З даного визначення величин di, jm випливає, що величина di, j0, представляє довжину найкоротшого шляху з вершини i у вершину j, що не має проміжних вершин, тобто довжину найкоротшої дуги, що з'єднує i з j (якщо такі дуги присутні в графі). для будь-якої вершини i покладемо di, im = 0. Відзначимо далі, що величина di, jm являє собою довжину найкоротшого шляху між вершинами i та j.

Позначимо через Dm матрицю розміру NxN, елемент (i, j) якої збігається з di, jm. Якщо у вихідному графі нам відома довжина кожної дуги, то ми можемо сформувати матрицю D0. Наша мета полягає у визначенні матриці DN, що представляє найкоротші шляхи між усіма вершинами розглянутого графа.
В алгоритмі Флойда в якості вихідної виступає матриця D0. Спочатку з цієї матриці обчислюється матриця D1. Потім по матриці D1 обчислюється матриця D2 і т. д. Процес повторюється до тих пір, поки по матриці DN-1 не буде обчислена матриця DN.