Нахождение оптимального пути

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ СТРУКТУРНОЙ МОДЕЛИ ТРАНСПОРТНОЙ СИСТЕМЫ

2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СИСТЕМЫ

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВЫЧИСЛЕНИЯ ОПТИМАЛЬНОГО ПУТИ

4. АНАЛИЗ РЕЗУЛЬТАТОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ А

транспортный математический модель задача



ВВЕДЕНИЕ

Структурное моделирование представляет собой особый аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов. Под «управляемыми» разумеются процессы, на ход которых мы можем в той или иной степени влиять. Общеизвестно пристальное внимание, уделяемое современной наукой вопросам планирования во всех областях человеческой деятельности. И это внимание абсолютно обоснованно, ведь детальное моделирование отдельных систем впоследствии дает Вам возможность извлечь максимальную выгоду из управления данной системой. И эффективность такой модели будет прямо пропорциональна количеству рассмотренных факторов, взятых из всего того множества условий, определяющих состояние этой системы.

Одним из математических аппаратов структурного моделирования является динамическое программирование - недавно возникший и интенсивно развивающийся раздел математики, дающий методы для решения важных практических задач. Динамическое программирование - это дальновидное планирование, планирование с учетом перспективы.

Целью данной работы является разработка модели транспортной системы, представляющей топологическую схему дорожных участков, перекрёстков и развязок с заданными среднестатистическими временами задержек или простоев, для вычисления оптимального пути между назначенными пунктами. Необходимость достижения указанной цели обусловила постановку и решение следующих задач:

- проведение анализа топологической схемы дорожных участков;

- разбиение топологической схемы на простые участки или подзадачи;

- сопоставление полученной схемы с конкретной структурной моделью;

- вычисление оптимального пути методом динамического программирования на основе составленной модели;

- составление итоговой схемы оптимального маршрута.

В качестве среды разработки была выбрана математическая среда программирования MathCAD.

Полное условие задачи данной работы предполагает анализ топологии дорог автомобильных грузоперевозок, изображенной на рисунке 1 и вычисление методом динамического программирования (динамического планирования) наименее затратного по времени пути из пункта S₀ в пункт S_кон.

Рисунок 1 Топология автомобильных дорог

Время проезда отрезка пути указано на рисунке рядом с интересующим отрезком, а время, затрачиваемое при простое на перекрёстке или в очереди к переправе или переезду, указано в кружке рядом с интересующим перекрёстком, переездом или переправой.



Таблица 1

Распределение времени (в минутах) проезда отрезков дорог, перекрёстков, переездов или переправ для заданной топологии

Номер шага, i Номер отрезка, j	1	2	3	4	5	6	7
1	7	2	6	6	5	10	8
2	3	4	1	1	6	7	1
3	6	1	5	5	1	6	4
4	1	5	8	8	5	1	6
5	5	9	4	4	8	5	1
6	8	7	4	4	4	8	5
7	4	2	1	1	4	4	8
8	4	6	2	2	1	4	4
9	1	1	9	9	2	1	4
10	2	5	10	10	9	2	1
11	9	8	12	12	10	9	2
12	10	4	1	6	12	10	9
13	12	4	5	9	17	12	10
14	17	1	10	8	6	17	12
15	9	2	7	1	1	6	17
16	7	9	12	5	5	1	6
17	2	10	1	9	8	5	1
18	6	12	6	6	4	8	5
19	1	17	1	1	4	4	8
20	5	6	5	5	1	5	4
21	8	1	8	8	2	9	9
22		5	4	4	9	7	1
23		8	4	4		2
24		4	1			3
25		4				6
26		1				9
27		5

Времена, затрачиваемые на каждом отрезке автомобильных дорог и при простое на перекрёстках или в очередях, обозначены как t_i,j, где i = 1, 2, …, 7 - номер шага или этапа планирования, j - номер обозначенного на топологии участка дороги для i-го шага. Числовые значения времён t_i,j (в минутах) были назначены преподавателем и занесены в вышеуказанную таблицу 1.



1. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ СТРУКТУРНОЙ МОДЕЛИ ТРАНСПОРТНОЙ СИСТЕМЫ

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

Динамическое программирование есть поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг.

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

Но принцип динамического программирования отнюдь не предполагает, что, выбирая управление на одном отдельном шаге, можно забыть обо всех остальных. Напротив, управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. Динамическое программирование -- это планирование дальновидное, с учетом перспективы. Это не близорукое планирование «вслепую» на один шаг. Напротив, управление на каждом шаге выбирается исходя из интересов операции в целом.

Планируя многоэтапную операцию, мы должны выбирать управление на каждом шаге, исходя не из узких интересов именно этого шага, а из более широких интересов операции в целом, и далеко не всегда эти две точки зрения совпадают.

Как же строить такое управление? Уже было сформулировано общее правило: в процессе поэтапного планирования управление на каждом шаге должно приниматься с учетом будущего. Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться попросту, без «оглядки на будущее». Какой это шаг? Очевидно, последний. Этот последний шаг, единственный из всех, можно планировать так, чтобы он как таковой приносил наибольшую выгоду.

Спланировав оптимальным образом этот последний шаг, можно к нему «пристраивать» предпоследний, к этому в свою очередь предпредпоследний и т. д.

Поэтому процесс динамического программирования всегда разворачивается в обратном по времени направлении: не от начала к концу, а от конца к началу. Раньше всего планируется последний шаг. А как его спланировать, если неизвестно, чем кончился предпоследний? Очевидно, нужно сделать разные предположения о том, чем кончился предпоследний шаг, и для каждого из них выбрать управление на последнем.

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

Самая общая задача динамического программирования ставится следующим образом:

Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий (короче, «операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной, т. е. наилучшим образом удовлетворяла поставленным перед ней требованиям? Чтобы поставленная задача оптимального планирования приобрела количественный, математический характер, необходимо ввести в рассмотрение некоторый численный критерий W, которым мы будем характеризовать качество, успешность, эффективность операции. Величина W, в зависимости от характера решаемой задачи, может выбираться различными способами. Например, при планировании деятельности системы промышленных предприятий в качестве критерия W может быть (смотря по обстоятельствам) выбран общий годовой объем продукции или же чистый годовой доход; критерием эффективности работы транспортной системы может быть, например, общий грузооборот или же средняя стоимость перевозки тонны груза. Вообще критерий эффективности в каждом конкретном случае выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего). Задача рационального планирования -- выбрать такой способ организации данной системы действий, чтобы обратить в максимум, (или минимум) какой-то критерий W. Если в качестве критерия взята такая величина, увеличение которой нам выгодно (например, доход от группы предприятий), то ее стремятся обратить в максимум. Если, наоборот, величину W выгодно уменьшать, то ее стремятся обратить в минимум.

Продемонстрируем схему такой процедуры. Пусть планируется m-шаговая операция, и неизвестно, чем кончился (m-1)-й шаг. Сделаем об этом ряд «гипотез» или «предположений». Эти гипотезы мы обозначим:

S⁽¹⁾_m-1, S⁽²⁾_m-1, …, S^(f)_m-1, … (1)

Оговоримся, что буквой S^(f)_m-1 не обязательно обозначается одно число: это может быть и группа чисел, характеризующих исход (m-1)-го шага, а может быть и просто качественное состояние той физической системы, в которой протекает управляемый процесс.

Найдем для каждого из предположений (1) условное оптимальное управление на последнем (m-м) шаге. Это будет то из всех возможных управлений U_m, при котором достигается максимально возможное значение выигрыша на последнем шаге.

Предположим, что для каждого из предположений (1) условное оптимальное управление U*_m на последнем шаге найдено:

U*_m(S⁽¹⁾_m-1); U*_m(S⁽²⁾_m-1); …; U*_m(S^(f)_m-1); … (2)

Это означает, что последний шаг спланирован для любого исхода предпоследнего.

Перейдем к планированию следующего от конца, предпоследнего шага. Снова сделаем ряд гипотез о том, чем кончился предпредпоследний ((m- 2)-й) шаг:

S⁽¹⁾_m-2, S⁽²⁾_m-2, …, S^(k)_m-2, … (3)

Поставим вопрос: как нужно выбирать для каждой из этих гипотез условное оптимальное управление на (m-1)-м шаге?

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

Другими словами, для каждой из гипотез (3) нужно найти такое условное оптимальное управление на (m-1)-м шаге U*_m-1(S_m-2), чтобы оно, в совокупности с уже найденным условным оптимальным управлением U*_m(S_m-1), давало максимально возможный выигрыш на двух последних шагах.

Очевидно, к (m-1)-му шагу таким же точно способом может быть присоединен (m-2)-й и т. д. вплоть до самого последнего (от конца) 1-го шага, с которого процесс начинается.

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

Принцип, положенный в основу построения такого решения (искать всегда оптимальное продолжение процесса относительно того состояния, которое достигнуто в данный момент), часто называют принципом оптимальности.

Принято считать, что принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех
последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Р.Э. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

Частью динамического программирования также являются и транспортные задачи, которые играют особую роль в уменьшении транспортных издержек предприятия. Это является актуальным вопросом в условиях рыночной экономики, когда любые затраты должны быть минимизированы, ведь тогда издержки покрываются меньшей частью прибыли, а также позволяют снизить себестоимость продукции на рынке, что делает предприятие более конкурентоспособным.



2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СИСТЕМЫ

В ходе реализации задач данной работы целесообразно руководствоваться следующим алгоритмом:

1) Проанализировав предоставленную топологию автомобильных дорог, разбить участок S₀ - S_кон на оптимальное значение m шагов.

2) Исходя из принципа оптимальности, учесть, что путь из S₀ в S_кон разбит на m шагов, в каждом из которых машина перемещается с одной из опорных прямых (i) -- (i) на следующую по порядку. Выбрать “узловые точки” (точки положения машины по итогам прохождения каждого шага) на каждой из прямых (i) -- (i).

3) Опираясь на принципы динамического программирования, прокладывать маршрут из S_кон в S₀. Найти условное оптимальное управление для каждой точки на (6)-ом шаге, т.е. такой путь на предыдущий шаг, который, совместно с уже оптимизированным последним шагом, дает возможность достигнуть следующей опорной точки за минимальное время.

4) Проделать аналогичные операции для последующих шагов, кроме S₀.

5) Сравнивая полученные значения, выбрать оптимальный путь из точки S_кон в S₀ и нанести его на карту дорог (рисунок 4).

В соответствии с принципом оптимальности поставим задачу данной работы. Пусть нам нужно добраться на машине из пункта S₀ в пункт S_кон (рис.1). Вообще имеется целый ряд возможных вариантов пути. Они составлены из участков дорог, не равноценных по качеству. Среди них могут быть, например, участки первоклассных асфальтированных шоссе, а также менее благоустроенных и просто проселочных дорог. Кроме того, на пути нам могут встретиться перекрестки и переезды, на которых движение задерживается.

Задача состоит в том, чтобы выбрать такой путь из S₀ в S_кон, который машина пройдет за минимальное время. Несмотря на кажущуюся простоту, эта задача имеет некоторые особенности. Исходя из алгоритма решения, нам необходимо построить регулярную сетку узловых точек, через которые могла бы проходить траектория кратчайшего пути. Но в этой задаче роль такой сетки узловых точек могли бы играть естественно отмеченные «особые точки» сети дорог -- перекрестки и переезды, но они расположены слишком нерегулярно, и их затруднительно «упорядочить по шагам». Для того чтобы приближенно решить нашу задачу методом динамического программирования, можно ввести в нее искусственно некоторую «поэтапность». Например, можно разделить расстояние D от S₀ до S_кон на m равных частей длиной ?D = D/m (рис. 1) и считать, что за каждый «шаг» процесса перемещения из S₀ в S_кон преодолевается m-ю часть расстояния D (по направлению S₀ - S_кон). Другими словами, каждый «шаг» представляет собой перемещение с одной из опорных прямых, перпендикулярных S₀ - S_кон, на соседнюю, более близкую к S_кон.

Деля процесс на шаги таким образом, мы, естественно, должны условиться, что перемещение от шага к шагу допускается только в положительном направлении (т. е. от S₀ к S_кон, а не обратно); иными словами, после того как определенный шаг пройден, возвращение обратно, в ту же полосу между двумя опорными прямыми, не допускается. Такое ограничение представляется достаточно приемлемым для нашей задачи (в итоге каждого шага перемещаться только «туда», по направлению S₀ - S_кон, а не «обратно»), так как оно действует только от шага к шагу, не внутри шага, и к тому же только по одной оси (в случае надобности от этого ограничения можно освободиться, но при этом решение сильно усложняется).

Итак, предположим, что путь из S₀ в S_кон разбит на m шагов, в каждом из которых машина перемещается с одной из опорных прямых (i) -- (i) на следующую по порядку

(i+1) -( i+1) (i = 0,1,…m).

Проведенные нами опорные прямые пересекают дорожную сеть в каких-то точках, которые принято называть “узловыми”. На рисунке 2 представлено распределение “узловых” точек на карте дорожной системы.

Рисунок 2 Карта “узловых” точек транспортной системы

Для решения задачи нам должно быть известно время, требуемое для прохода каждого участка пути, а также время задержки на каждом перекрестке (переезде). На рис. 1 против каждого отрезка пути проставлено соответствующее время прохода (в минутах), а в кружке у каждого перекрестка (переезда) -- время ожидания машины в данном пункте.

Согласно количеству опорных прямых на рис. 1 процесс перемещения машины из S₀ в S_кон мы разделим на семь шагов (т. е. примем m = 7) и начнем построение оптимального пути с последнего (m - 1)-го шага.

Наметим на опорной прямой (m-1) -- (m-1) все возможные положения машины в момент окончания предпоследнего ((m-1)-го) шага. Это будут гипотезы о состоянии машины после (m-1)-го шага, для каждой из которых мы должны найти условное оптимальное управление на m-м шаге. На рис. 1 эти возможные положения отмечены кружком с точкой внутри. Из каждого такого положения мы должны выбрать оптимальный (кратчайший по времени) путь в точку S_кон.

Рассмотрим сначала первую (сверху) из отмеченных точек -- точку А на прямой (m - 1) -- (m-1). Из нее в точку S_кон (в пределах полосы m-го шага) ведет один-единственный путь, занимающий по времени:

(минуты).

Выбор этого пути представляет собой условное оптимальное управление при условии, что предыдущий шаг привел нас в точку А. Отметим на рисунке 2 этот оптимальный путь черной жирной линией, а у точки А выставим «флажок» с записанным на нем обозначением A₆.

Жирная линия вместе с флажком означают следующее: если, перемещаясь из S₀ в S_кон, мы какими-то судьбами оказались в точке А, то из нее мы должны двигаться дальше по отмеченному черной линией маршруту и на достижение точки S_кон затратим A₆ минут.

Переходим к следующей точке (В) на прямой (m- 1) -- (m- 1). Из нее в точку S_кон ведет один-единственный путь, на который требуется:

(минут).

Индекс B₆ также записываем на флажке рядом с точкой В.

Для точки С путь снова единственный и продолжается:

(минут).

Решение, полученное нами на данном этапе, изобразим на рисунке 3.

Рисунок 3 Расчет оптимального управления на первом шаге

Из точки D в S_кон есть два пути. Скорейший из них отмечаем жирной линией и записываем минимальное время на флажке у точки D.

Продолжая таким же образом, находим для каждой точки на прямой (m-1) -- (m-1) оптимальное продолжение пути -- условное оптимальное управление на m-м шаге.

После того как это выполнено, переходим к планированию (m - 1)-го шага. Гипотезы о том, где может находиться машина после предпредпоследнего (m - 2)-го шага, отмечены треугольниками на прямой (m - 2) -- (m - 2).

Для каждой из отмеченных точек мы должны найти условное оптимальное управление, т. е. такой путь с прямой (m-2) -- (m- 2) на прямую (m-1) -- (m-1), который, совместно с уже оптимизированным последним шагом, дает возможность достигнуть S_кон за минимальное время. Чтобы найти это условное оптимальное управление, мы должны для каждой точки на прямой (m-2) -- (m-2) перебрать все возможные способы перехода на прямую (m-1) -- (m-1) и время, потребное на этот переход, сложить с минимальным временем последнего шага, записанным на флажке. Из всех возможных путей выбирается тот, для которого это суммарное время минимально; путь отмечается черной линией, а время записывается на флажке у соответствующей точки.

В результате цепочки таких построений, перемещаясь шаг за шагом с одной опорной прямой на другую, мы, наконец, дойдем до исходной точки S₀. Для нее мы определим оптимальный путь на прямую (1) -- (1) и запишем соответствующее минимальное время на флажке у точки S₀. Таким образом, все данные для построения оптимального пути есть, так как для каждой из намеченных точек (какими бы судьбами мы в ней ни оказались) известно оптимальное продолжение пути. Чтобы построить оптимальный путь из S₀ в S_кон, нужно просто перемещаться по участкам дорог, отмеченным жирными линиями. На рисунке 4 оптимальная траектория из S₀ в S_кон отмечена жирной линией.

Важным моментом при решении задач методом динамического программирования является выбор числа шагов. Кажется, что для простоты решения, желательно было бы разбить дорогу на меньшее число шагов. Однако это не совсем так. Чем крупнее шаг, тем труднее находить оптимальное решение на этом шаге, тем больше существует вариантов перемещения с прямой на прямую. В предельном случае, если бы мы рассмотрели только один шаг (m= 1), перед нами встала бы исходная задача перебора всех возможных путей из S₀ в S_кон во всей ее сложности. Однако это не значит, что требуется увеличение числа шагов. Выведение его за какие-то разумные пределы только усложнило бы процедуру построения решения.

Рисунок 4 Оптимальный путь из S₀ в S_кон

В том, что выбранное нами число шагов (m = 7) довольно разумно, можно убедиться по тому, что нам нигде не приходилось перебирать большого числа вариантов перехода с прямой на прямую -- этих вариантов оказывалось один, два, редко три, и найти среди них оптимальный было не слишком трудно. Если бы мы сильно увеличили число шагов, т. е. чрезмерно измельчили участки перехода, то в подавляющем большинстве случаев с прямой на прямую вел бы один-единственный путь, и никакой оптимизации не было бы. В конечном итоге мы построили бы ту же оптимальную траекторию, но путем более сложных расчетов.

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВЫЧИСЛЕНИЯ ОПТИМАЛЬНОГО ПУТИ

Реализация алгоритма вычисления оптимального пути для операционных систем Windows XP / 7 / 8 / 10 была организована с помощью математического пакета MathCAD.

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

Важным инструментом в решении задания была возможность создания таблиц в среде MathCAD и последующее обращение к отдельным ее элементам. Таким образом, мы программно реализовали предложенную нам таблицу 1.

Таблица 1

Временные задержки, заданные в таблице среды MathCAD

Используя временную таблицу и схему дорог вычисляется время, затрачиваемое на прохождение каждого участка. Суммируются представленные в таблице значения для каждого из участков пути на каждом шаге.

При помощи функции min находятся минимальные значения для каждого последующего шага, путем складывания значения минимального пути, приводящего в данную точку с предыдущего шага и непосредственно времени, затрачиваемого на прохождение данного пути.

Из полученных в нулевом шаге результатов осуществляется выбор наименьшего, используя функцию «min» среды MathCAD.

Прохождение в прямом порядке от пункта S₀ в пункт S_кон.. Нахождение получившегося минимального пути, при помощи выбора минимального значения на каждом последующем шаге. Сопоставление топологической схемы и результатов вычислений.

Нанесение найденного пути на карту.

В результате решения задачи было выявлено, что оптимальный путь для данных условий - S₀A₁A₂A₃B₄A₅B₆S_кон и затрачиваемое на прохождение его время - 101 минуту. Сам путь представлен на рисунке 4, в то время как полный код программы - в приложении Б.

4. АНАЛИЗ РЕЗУЛЬТАТОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

Итогом реализации программы по нахождению оптимального пути из точки S₀ в S_кон является приведенная ниже строка кода:

Исходя из этого, начинаем разворачивать процесс в обратную сторону. На данном этапе получаем, что условное оптимальное управление для отрезка (0) - (1) будет путь A₁S₀. Так как в точку A₁ из S₀ ведут два пути, с помощью функции min определяем кратчайший из них. Переходим к точке A₁, единственный путь к которой лежит из точки A₂.

В точку A₂ также следует одна-единственная дорога - через A₃. Однако, в А₃ уже можно попасть из двух точек B₄ и С₄. Находим кратчайший из этих путей.

Условное оптимальное управление на данном этапе - переход в точку B₄. На данный момент наш оптимальный путь - S₀A₁A₂A₃B₄.

Опять-таки, в точку B₄ ведут дороги из A₅ и B₅.

Очевидно, что оптимален переход в точку A₅. Осуществляем дальнейшие переходы, основываясь на следующих строках кода.

Таким образом, получаем итоговый оптимальный путь - S₀A₁A₂A₃B₄A₅B₆S_кон, и затрачиваемое на его прохождение время - 101 минуту. Опираясь на основные догмы динамического программирования, мы можем быть абсолютно уверены в том, что найденный путь действительно является кратчайшим при переходе из точки S₀ в S_кон. Помимо того, решение данной задачи было произведено в достаточно короткие сроки, что позволяет говорить об однозначной эффективности рассматриваемого метода.

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



ЗАКЛЮЧЕНИЕ

Был исследован метод динамического программирования в контексте решения простейшей транспортной задачи по критерию времени с единственными начальным и конечным пунктами.

При помощи метода динамического программирования был реализован алгоритм решения простейшей транспортной задачи для заданных условий.

В результате анализа предоставленных топологии дорог и временных промежутков был найден оптимальный путь, проходящий через точки S₀D₁D₂D₃D₄C₅C₆S_кон и требующий 101 минуту на его прохождение.



ПРИЛОЖЕНИЕ А



ПРИЛОЖЕНИЕ Б

Полный код программы, реализующей алгоритм нахождения оптимального пути между точками S₀ и S_кон.

6 ш а г

5 ш а г

4 ш а г

3 ш а г

2 ш а г

1 ш а г

0 ш а г

Размещено на Allbest.ru

...