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

 

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

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

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

 

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

(6.16)

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

Пусть u₁, u₂, …, u_N и U₁, U₂, …, U_N – два различных решения системы (6.16). Пусть m есть индекс, для которого разность U_j – u_j, j = 1,2, …,N, есть максимум. Нужно показать, что этот максимум разности равен нулю.

Пусть U_m = t_m,n+ U_n ≤ t_m,r + U_r, (6.17)

U_m = t_m,r + u_r (6.18)

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

 

U_m – u_m ≤ U_r – u_r, (6.19)

 

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

m ≠ r. (6.20)

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

s ≠ m,

(6.21)

s ≠ r,

 

для которого

U_m – u_m = U_r – u_r = U_s – u_s, (6.22)

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

U_N – u_N = 0. (6.23)

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

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

(6.24)

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

(6.25)

(6.26)

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

, (6.27)

. (6.28)

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

. (6.29)

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

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

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

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

. (6.30)

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

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

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

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

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

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

с весом

где вес можно интерпретировать как минимальное время l – той инцидентной цепи.

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

Пример.

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

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

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

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

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

Результаты вычислений удобно свести в таблицу (Табл.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

∞

∞

∞

-

-

-

-

 

f₁(i) – минимальное время передачи управления из любого i –го (i= ) пункта в конечный восьмой пункт за один шаг, минуя остальные. Поэтому в столбце j₁ – промежуточный пункт, прочерки.

f₂(i)= - минимальное время передачи управления из любого i-го пункта (i= ) в конечный восьмой пункт за два шага через промежуточный пункт j₂(i).

f₃(i)= - минимальное время передачи управления из любого i-го пункта (i= ) в конечный восьмой пункт за три шага через промежуточный пункт j₃(i).

 

F₄(i)= - минимальное время передачи управления из любого i-го пункта (i= ) в конечный восьмой пункт за четыре шага через промежуточный пункт j₄(i).

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

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

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

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

 

 

min t₁₈=7

min t₂₈=10

min t₄₈=7

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

 

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

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

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

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

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

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

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

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

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

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

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