Графическое моделирование организации транспортных процессов. Задача Коммивояжера

Министерство образования и науки Российской Федерации                                    Казанский Государственный архитектурно-строительный университет

Институт транспортных сооружений

Кафедра: Дорожно-строительные                                                                   машины

Реферат

По дисциплине: «Теория транспортных процессов»    

Тема:

«Графическое моделирование организации транспортных процессов. Задача Коммивояжера»

                               Проверил:                                                                                                                          к.т.н. Загидуллин Р.Р.

                                                                                             Выполнил:                                                                                                                                  Ст. группы 5БД01                                                                                               Кучерова А.А.

Казань, 2018

Содержание

Введение        3

1.        Теория графов        4

1.1        История возникновения теории графов        4

1.2        Основные понятия теории графов        6

2.        Система сетевого планирования и управления при разработке планов выполнения комплексов работ по организации транспортного процесса        9

2.1        Сущность сетевого планирования        9

2.2        Методика расчета параметров сетевого графика        9

2.3        Теоретические аспекты решения транспортных задач        12

3.        Задача Коммивояжера        14

3.1        Сущность задачи        14

3.2        Постановка задачи коммивояжера как задачи на графе        15

3.3        Методы решения задачи        17

Заключение        19

Список литературы        20

Введение

Для решения любой задачи требуется создание специальных методов,  а для решения транспортной задачи этот аспект является очень важным. У классической транспортной задачи цель – минимизировать транспортные издержки при перевозках одинаковых грузов от нескольких поставщиков, расположенных в различных местах, к нескольким потребителям. В данном реферате будет рассмотрен метод графического моделирования решения задач линейного программирования. Графический метод применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств.

Таким образом, целью реферата является: освоить навыки использования графического метода для решения задач, связанных с организацией транспортного процесса на примере конкретного типа задачи (задачи коммивояжера). Для этого были поставлены следующие задачи:

1. Изучить теоретические сведения, необходимые для решения задач графического моделирования.
2. Разобрать основные понятия теории графов и историю из происхождения.
3. Рассмотреть формы графического отображения: сетевое планирование.
4. Решить задачу, используя рассмотренный метод решения задач линейного программирования.

1. Теория графов

1. История возникновения теории графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783) [3]. Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

Задача о Кенигсбергских мостах. На рисунке 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.