оптимальні маршрути з міст k-го поясу до кінцевого пункту.
Оптимізацію будемо виробляти з хвоста процесу, і тому, діставшись до k-го кроку, ми не можемо знати, в якій саме з міст k-го поясу ми потрапимо, рухаючись з пункту 1. Тому для кожного з цих міст ми повинні будемо знайти оптимальний маршрут до кінцевого пункту. Очевидно, що мінімально можлива вартість проїзду до пункту 11 буде залежати тільки від того, в якому з міст цього поясу ми опинилися. Номер S міста, що належить k-му поясу, і називатиметься змінної стану даної системи на k-м кроці. Потрібно пам'ятати, що, діставшись до k-го кроку, ми вже здійснили попередні кроки, в зокрема, знайшли оптимальні маршрути по переміщенню з будь-якого міста (k-1)-го поясу в кінцевий пункт. Таким чином, перебуваючи в деякому місті S k-го поясу, ми повинні прийняти рішення про те, в якій з міст (k-1)-го поясу слід відправитися, а напрямок подальшого руху вже відомо нам з попередніх кроків. Номер J міста (k-1)-го поясу буде бути змінної управління на k-му кроці.
Функція Беллмана на k-м кроці рішення задачі дає нам можливість розрахувати мінімальну вартість проїзду з міста S (k-го поясу) до кінцевого пункту. Для першого кроку (k = 1) цю величину відшукати не складно - це вартість проїзду з міст 1-го поясу безпосередньо до кінцевого пункту: F1 (i) = Ci11. Для наступних же кроків вартість проїзду складається з двох доданків - вартості проїзду з міста S k-го поясу в місто J (k-1)-го пояси і мінімально можливої вЂ‹вЂ‹вартості проїзду з міста J до кінцевого пункту, тобто Fk-1 (J). p> Таким чином, функціональне рівняння Беллмана на k-му кроці рішення буде мати вигляд:
В
Мінімум вартості досягається на деякому значенні J *, яке і є оптимальним напрямком руху з пункту S в бік кінцевого пункту.
Рішення:
Етап I. Умовна оптимізація. p> Крок 1. k = 1. F1 (S) = ts11. br/>
Таблиця 2.2
S
J = 11
F1 (S)
J *
8
10
10
11
9
8
8
11
10
10
10
11
Крок 2. k = 2. Функціональне рівняння на даному кроці приймає вигляд:
.
Результати розрахунку за наведеною формулою наведені в таблиці 2.3:
Таблиця 2.3
S
J = 8
J = 9
J = 10
F2 (S)
J *
6
4 + 10
5 + 8
4 + 10
13
9
7
5 + 10
12 + 8
6 + 10
15
8
Крок 3. k = 3. Функціональне рівняння на даному кроці приймає вигляд:
.
Результати розрахунку по наведеній формулі наведені в таблиці 2.4:
Таблиця 2.4
S
J = 6
J = 7
F3 (S)
J *
2
3 + 13
7 + 15
16
6
3
8 + 13
9 + 15
21
6/7
4
11 + 13
4 + 15
19
7
5
8 + 13
9 + 15
21
6/7
Крок 4. k = 4. Функціональне рівняння на даному кроці приймає вигляд:
.
Результати розрахунку за наведеною формулою наведені в таблиці 2.5:
Таблиця 2.5
S
J = 2
J = 3
J = 4
J = 5
F4 (S)
J *
1
5 + 16
7 + 21
6 + 19
10 + 21
21
2
Етап II. Безумовна оптимізація. p> На етапі умовної оптимізації отримано, що мінімальні витрати на проїзд з пунк...
