Выбор оптимальных маршрутов методом динамического программирования

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

Ui - время перевода системы из начального состояния i в желаемое состояние N вдоль кратчайшего пути

i =1, 2, …,N. (6.14)

Положим UN = 0 (6.15) Применяя принцип оптимальности, получим основную систему нелинейных алгебраических уравнений

Выбор оптимальных маршрутов методом динамического программирования - student2.ru (6.16)

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

Пусть u1, u2, …, uN и U1, U2, …, UN – два различных решения системы (6.16). Пусть m есть индекс, для которого разность Uj – uj, j = 1,2, …,N, есть максимум. Нужно показать, что этот максимум разности равен нулю.

Пусть Um = tm,n+ Un ≤ tm,r + Ur, (6.17)

Um = tm,r + ur (6.18)

Из этого следует, что

Um – um ≤ Ur – ur , (6.19)

и так как m есть индекс, для которого разность Um – um есть максимум, то знак равенства должен быть удержан как в (6.19), так и в (6.17). Кроме того, ясно, что

m ≠ r. (6.20)

Подобным же образом мы можем найти узел s, где

s ≠ m,

(6.21)

s ≠ r,

для которого

Um – um = Ur – ur = Us – us, (6.22)

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

UN – uN = 0. (6.23)

Этим заканчивается доказательство единственности. Вернемся теперь к отысканию численного решения путем применения приближений в пространстве стратегий. Одновременно мы установим как существование решения системы (6.16), так и эффективный способ для вычисления решения.

В качестве исходного приближения Выбор оптимальных маршрутов методом динамического программирования - student2.ru положим

Выбор оптимальных маршрутов методом динамического программирования - student2.ru (6.24)

что соответствует стратегии перевода системы непосредственно из ее начального состояния в желаемое конечное состояние. Если не имеется никакого звена от i к N, так что ti,N = ∞, то можно положить ti,n = 1030 или какому-нибудь другому подходящему большому числу. Этот простой прием устраняет трудные топологические вопросы связности. Следующее приближение получим из формулы

Выбор оптимальных маршрутов методом динамического программирования - student2.ru (6.25)

Выбор оптимальных маршрутов методом динамического программирования - student2.ru (6.26)

Операции, указанные в формуле (6.25) быстро выполняются вычислительно. Значения одной строки матрицы (tij) требуются в качестве значений исходного приближения Выбор оптимальных маршрутов методом динамического программирования - student2.ru . Минимизация делается путем непосредственного сравнения встречающихся сумм, одной за другой. Таким образом, как время вычисления, так и требования к быстродействию памяти невелики. Мы переходим от k-го к (k+1)-му приближению при помощи соотношений

Выбор оптимальных маршрутов методом динамического программирования - student2.ru Выбор оптимальных маршрутов методом динамического программирования - student2.ru , (6.27)

Выбор оптимальных маршрутов методом динамического программирования - student2.ru . (6.28)

Формулы (6.25) – (6.28) имеют простую содержательную интерпретацию. Величина Выбор оптимальных маршрутов методом динамического программирования - student2.ru соответствует минимальному времени перехода от узла i к узлу N без промежуточных узлов. Величина Выбор оптимальных маршрутов методом динамического программирования - student2.ru есть минимальное время перехода от узла i к узлу N при наличии не более одного промежуточного узла. Аналогично Выбор оптимальных маршрутов методом динамического программирования - student2.ru есть минимальное время перехода от узла i к узлу N при наличии не более k промежуточных узлов. Из этой физической интерпретации мы видим, что последовательные приближения монотонно убывают, т.е.

Выбор оптимальных маршрутов методом динамического программирования - student2.ru . (6.29)

Это иллюстрация эффективности метода приближений в пространстве стратегий. Отметим, кроме того, что эта процедура аппроксимации конечна по своему существу. Так как оптимальный путь от i к N не может иметь никаких петель, он может содержать не более N-2 промежуточных узла. Из этого следует, что величины Выбор оптимальных маршрутов методом динамического программирования - student2.ru , должны удовлетворять уравнениям (6.16), что означает, что мы будем иметь не более N – 2 итераций.

Для определения оптимальной траектории из какого-нибудь начального состояния в любое конечное состояние можно применить только что рассмотренный метод N раз. Иначе говоря, мы можем ввести величины

Выбор оптимальных маршрутов методом динамического программирования - student2.ru - минимальное время перехода системы из состояние i в состояние j, используя путь с не более чем k-промежуточными состояниями.

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

Выбор оптимальных маршрутов методом динамического программирования - student2.ru . (6.30)

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

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

Введем понятие инцидентных цепей.

Связные цепи, обладающие свойством слияния последовательности звеньев, называются инцидентными.

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

Рассмотрим массив оптимальных маршрутов, полученных в результате решения функционального уравнения (6.30). Этот массив содержит i инцидентных цепей.

Выбор оптимальных маршрутов методом динамического программирования - student2.ru

с весом Выбор оптимальных маршрутов методом динамического программирования - student2.ru

где вес Выбор оптимальных маршрутов методом динамического программирования - student2.ru можно интерпретировать как минимальное время l – той инцидентной цепи.

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

Пример.

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

Выбор оптимальных маршрутов методом динамического программирования - student2.ru

Рис. 6.1. Сеть коммуникаций

Пусть из любого i-го пункта в j-тый пункт передается управление за один шаг (минуя остальные), на что тратится время tij. Допустим, что для передачи управления в конечный пункт потребуется k шагов (этапов). В силу принципа оптимальности за k шагов нужно так организовать управление из j-го пункта в конечный пункт, чтобы потратить как можно меньше времени, которое обозначим через Выбор оптимальных маршрутов методом динамического программирования - student2.ru .

Всего же из любого i-го пункта в конечный N-й пункт потребуется время равное сумме Выбор оптимальных маршрутов методом динамического программирования - student2.ru .

При изменении i от 1 до N и j от 1 до N, необходимо найти наименьшую сумму, то есть Выбор оптимальных маршрутов методом динамического программирования - student2.ru . Это функциональное уравнение беллмановского типа можно использовать для моделирования любых оптимальных маршрутов коммуникаций, например, электросетей, маршрутов скорой помощи, вневедомственной охраны, автобусных маршрутов и т.д. Выбор оптимальных маршрутов методом динамического программирования - student2.ru .

Результаты вычислений удобно свести в таблицу (Табл.6.11)

Таблица 6.11

Расчетная таблица

j i f1(i) j1 f2(i) j2 f3(i) j3 f4(i) j4
-
1,3 1,3
- 5,7
1,2
- 3,8 3,8 3,8
-
3,4 3,4
- 5,8 5,8 5,8
-
3,6 3,6
- 7,8 7,8 7,8
- - - -

f1(i) – минимальное время передачи управления из любого i –го (i= Выбор оптимальных маршрутов методом динамического программирования - student2.ru ) пункта в конечный восьмой пункт за один шаг, минуя остальные. Поэтому в столбце j1 – промежуточный пункт, прочерки.

f2(i)= Выбор оптимальных маршрутов методом динамического программирования - student2.ru - минимальное время передачи управления из любого i-го пункта (i= Выбор оптимальных маршрутов методом динамического программирования - student2.ru ) в конечный восьмой пункт за два шага через промежуточный пункт j2(i).

f3(i)= Выбор оптимальных маршрутов методом динамического программирования - student2.ru - минимальное время передачи управления из любого i-го пункта (i= Выбор оптимальных маршрутов методом динамического программирования - student2.ru ) в конечный восьмой пункт за три шага через промежуточный пункт j3(i).

F4(i)= Выбор оптимальных маршрутов методом динамического программирования - student2.ru - минимальное время передачи управления из любого i-го пункта (i= Выбор оптимальных маршрутов методом динамического программирования - student2.ru ) в конечный восьмой пункт за четыре шага через промежуточный пункт j4(i).

Критерий прекращения счета – повторение значений функции fk(i), в данном примере значения функции f4(i) равны значениям функции f3(i), поэтому расчет закончен.

Выбор маршрутов управления осуществляем из расчетной таблицы 6.11. Согласно указанного критерия, ответы заключены в прямоугольники.

Так, минимальное время передачи управления из первого пункта в восьмой составит 7 ед. времени через третий промежуточный пункт за два шага. Действительно, Выбор оптимальных маршрутов методом динамического программирования - student2.ru .

Минимальное время передачи управления из второго пункта в восьмой составит 10 ед. времени через первый промежуточный пункт j3(2) = 1, а далее по таблице находим как из первого пункта осуществить передачу управления в восьмой и т.д. (определено ранее).

Выбор оптимальных маршрутов методом динамического программирования - student2.ru

min t18=7

Выбор оптимальных маршрутов методом динамического программирования - student2.ru

min t28=10

Выбор оптимальных маршрутов методом динамического программирования - student2.ru

min t48=7

Инцидентная цепь 1-3-8 повторена дважды, и цепь 3-8 несет большую нагрузку.

Вопросы для самоконтроля

1. Каков смысл функции Беллмана в задаче перспективного планирования минимальных затрат?

2. Какой принцип оптимальности использован при выводе функционального уравнения Беллмана?

3. Что значит i - ый вариант строительства объектов?

4. Что является исходной информацией для задачи перспективного планирования минимальных затрат?

5. Когда следует применять метод динамического программирования в задачах планирования?

6. Особенности задач, решаемых методом динамического программирования (ДП).

7. Каков смысл функции Беллмана?

8. Зачем составляется функциональное уравнение Беллмана?

9. Какова суть принципа оптимальности, положенного в основу вывода функционального уравнения Беллмана?

10. В чём разница между методом прямого и обратного хода в задачах ДП?

Наши рекомендации