Выбор оптимального пути

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего образования «Тверской государственный технический университет» (ФГБОУВПО «ТвГТУ»)

Курсовая работа по дисциплине: «Математическое программирование» ТЕМА: «Выбор оптимального пути»

Выполнил:

студент 2 курса

ФИТ, группы Б.ПИ.ЭК-17.08

Гордеев Е.

Проверил: Дзюба С.М.

Тверь

2019

Содержание

1. Постановка, условие задания…………………………………………… 3
2. Теоретические основы задачи выбора оптимального пути…………… 4
3. Программное обеспечение и алгоритм…………………………………  9
4. Расчетные таблицы……………………………………………………… 11
5. Результаты вычислений…………………………………………………. 13
6. Вывод. Заключение……………………………………………………… 13
7. Список используемой литературы…………………………………….. 14

Постановка задания курсовой работы.

В рамках данной курсовой работы будет рассмотрена задача нахождения наиболее оптимального пути на примере графа, где каждая дуга имеет определенный вес.

Дальнейшие расчеты будут проводиться по данным, показанных на графе 1.

[pic 1]

Граф 1.

Теоретические основы задачи выбора оптимального пути.

       Рассмотрим сеть, состоящую из N узлов, занумерованных 1, 2, . . . , N, и взаимосвязанных звеньев. Пусть время, которое занимает прохождение звена (i. J), будет t i j > 0. В частности, отметим, что t i j не обязательно должно быть равным t j i . Мы желаем определить путь через сеть, который соединяет два заданных узла, полное время прохождения по которому по крайней мере не больше, чем для любого другого пути, соединяющего заданные узлы. Ясно, что эта задача имеет важное значение при выборе маршрутов самолетов и автомобилей по транспортным сетям и при передаче сообщений по сетям связи. Помимо того, эти вопросы важны при изучении оптимальных по быстродействию систем управления с обратной связью.

 Чтобы показать это, мы интерпретируем N узлов как возможные состояния системы, а звенья – как преобразования от одного состояния к другому. Часто мы хотим перевести систему из заданного начального состояния в желаемое состояние за минимальное время. Эта задача может быть также рассмотрена как дискретная версия оптической задачи, содержащей принцип Ферма, рассмотренной в разделе 19. Наконец, интерпретируя числа t i j как топливо или любые другие расходуемые ресурсы, можно рассматривать нашу задачу как задачу перевода системы из заданного начального состояния в требуемое конечное состояние наиболее эффективным образом, в смысле затрат ресурсов.

Будем рассматривать узел N как желаемый для конца заданного интервала времени узел, и введем величины

U i = время перевода системы из начального состояния i в желаемое состояние N вдоль кратчайшего пути i = 1, 2, . . . , N .                             (20.1)

Мы положим

                                                         U N = 0.                                               (20.2)

  Применяя принцип оптимальности, получим основную систему нелинейных алгебраических уравнений

U i = min (t i j + u i),     i=1, 2, . . , N – 1,                                                         (20.3)

         j ≠ i

U N = 0.

  Одни могут рассматривать как дискретная форма управления эйконала (см. раздел 19). В противоположность многим другим системам уравнений, полученным из принципа оптимальности, никакой последовательный метод определения неизвестных здесь непосредственно не усматривается. Следовательно, мы должны применить метод последовательных приближений. Сначала установим единственность решения уравнений (20.3) для того, чтобы получить уверенность, что последовательность, которая сходится к решению, сходится к искомому нами решению, т.е. определяет желаемый минимальный промежуток времени. Заметим, однако, что, в то время как величины u1, u2, . . . , u N   определяют однозначно, пути, при  прохождении вдоль которых эти значения достигаются, могут быть не единственными.