Тема: «Прикладные задачи динамического программирования: выбор оптимального маршрута перевозки грузов».

ПЛАН ЗАНЯТИЯ:

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

2. Решение задачи динамического программирования (ДП), используя принцип оптимальности Беллмана.

 Теоретическая часть

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

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

Практическая часть

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

Пусть транспортная сеть состоит из 10 узлов, часть из которых соединена магистралями. На рис.1 показана сеть дорог и стоимости перевозки ед. груза между отдельными пунктами сети, которые проставлены у соответствующих рёбер.

Рисунок 1. Модель транспортной сети

Необходимо определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие транспортные расходы (F_k (i)). После расчётов необходимо изобразить оптимальный маршрут графически.

В задаче имеется ограничения – двигаться по изображенным на схеме маршрутам можно только слева на право, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10, и не можем возвратиться обратно в 5-й или 6-й.

Эта особенность транспортной сети даёт право отнести каждый из 10-и пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него попасть в конечный пункт ровно за k шагов, т.е. с заездом ровно в (k -1)-й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 ко второму, 2, 3 и 4 к третьему и 1 к четвёртому.

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

Введём обозначения:

k - номер шага (k= 1, 2, 3, 4);

i - пункт, из которого осуществляются перевозки (i= 1,2,…,9)

j - пункт, в который доставляется груз (j= 2,3,…,10)

C_{i j}- стоимость перевозки груза из пункта i в пункт j.

F_k (i) - минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком пункте пояса мы оказались. Номер i пункта, принадлежащего k-му поясу, будет являться переменной состояния системы на k-м шаге.

Для первого шага управления (k=1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. F₁(i) = С _{i 10}.

Для последующих шагов затраты складываются из двух слагаемых – стоимости перевозки груза C_ij  из пункта i k-го пояса в пункт j (k-1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. F_{k 1} (j). Таким образом, функциональное уравнение Беллмана будет иметь вид

              F_k (i)= min { C_ij+ F_k-1 (j) }                              (1)

Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта i в конечный пункт.

На четвёртом шаге попадаем на 4-й пояс и состояние системы становится определённым i=1. Функция F ₄ (1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й.

Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k- м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определённым.

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

1 этап. Условная оптимизация.

1-й шаг. k =1

F₁ (i)= С_i10

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7,8 или 9.

Таблица 1.

i, j	10	F 1 (i)	j *
8	7	7	10
7	9	9	10
9	11	11	10

2-й шаг. k =2

Функциональное уравнение на втором шаге принимает вид

F₂ (i)= min { C _ij + F₁ (j) }

Все возможные перемещения груза на втором шаге и результаты расчета приведены в табл.2.

Таблица 2.

i, j	7	8	9	F 2 (i)	j *
5	6+9	8+7	-	15	7;8
6	-	5+7	4+11	12	8

 

3-й шаг. k =3

F₃ (i)= min { C _ij + F₂ (j) }

Таблица 3.

i, j	5	6	F 3 (i)	j *
2	4+15	-	19	5
3	-	3+12	15	6
4	-	9+12	21	6

 

4-й шаг. k =4

F₄ (i)= min { C _ij + F₃ (j) }

Таблица 4.

i, j	2	3	4	F 4 (i)	j *
1	7+19	5+15	6+21	20	3

2 этап. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F ₄ (1)= 20.

Данный результат достигается при движении груза из 1-го пункта в 3-й. По данным табл.3, из пункта 3 необходимо двигаться в пункт 6, затем в пункт 8 и из него в конечный пункт (см. табл.2 и табл.1). 

Таким образом, оптимальный маршрут доставки груза:

ВАРИАНТЫ ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ:

Определяются аналогично рассмотренному примеру преподавателем.

ВОПРОСЫ ДЛЯ КОНТРОЛЯ ПОЛУЧЕННЫХ ЗНАНИЙ:

1. На какой методологии основан математический аппарат ДП?

2. Кто впервые использовал словосочетание «динамическое программирование»?

3. Запишите функциональное уравнение Беллмана.

4. Охарактеризуйте алгоритм решения рассмотренной задачи, используя аппарат ДП.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №5