Экономико-математические методы и модели

3. В качестве параметра  шагового управления  для каждого шага выберем номер города, через который нужно ехать из города S, обозначим его J.

4. Выигрыш  , который приносит на n шаге управление , будет − длина из S в J.

Пусть − минимальная продолжительность пути от города S до конечного города, если осталось n шагов.

5. Обозначим через  − состояние, в которое должна перейти система под влиянием управления J на n шаге.

6. Основное рекуррентное  уравнение для данной задачи  имеет вид

.        (1.1)

Выполняем первый этап −  оптимизацию в условном направлении. Оптимизация в условном направлении  выполняется с последнего шага . Рекуррентное уравнение для в соответствии с рисунком имеет вид .

Состояние системы S на данном шаге может иметь значение 7 или 8 (номера городов, из которых можно  выехать на данном шаге). Шаговое  управление J = 9 (номер города через который следует ехать из города S).

Выигрыш (затраты по перевозке из S в J) определяется по 
рис.1 для всех возможных на данном шаге значений S и J: = 20; =12. Значение . Путь в конечный город определяются суммами:

Оформим решение в виде табл. 1.1.               Таблица 1.1

S/J	9
7	20+0	20	20
8	12+0	12	12

В первом столбце табл. 1.1 расположены возможные значения состояния системы S на шаге n. В первой строке − возможные значения шагового управления J. В каждой клетке сумма для соответствующих значении S и J на данном шаге. Значения при берутся из предыдущей таблицы. Для . В предпоследнем столбце вычисляются минимальные затраты по перевозке груза из города S, если до конца маршрута  осталось n шагов − (наименьшее значение из сумм в строке). В последнем столбце фиксируется номер города , через который следует ехать, чтобы достичь минимальных затрат ,

  .

Результат оформим в виде табл. 1.2.

Таблица 1.2

S/J	7	8
4	8+9	-	17	7
5	6+9	5+8	13	8
6	-	5+8	13	8

Рекуррентное  соотношение для (n-3) имеет вид  .

Вычисления для третьего шага оформим в виде табл. 1.3.

Таблица 1.3

S/J	4	5	6
2	17+7	-	15+13	24	4
3	-	6+13	8+13	19	5

Для последнего шага − в табл. 1.4.

 

 

Таблица 1.4

S/J	2	3
1	10+42	10+32	52	10

Второй  этап − безусловная оптимизация.

В табл. 1.4 − искомое минимальное расстояние из города А в конечный город В. Из города должна поехать в город .

Находим новое состояние  системы на втором шаге

.

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

Находим (для ) номер города, в который нужно 
ехать из города , это из табл. 1.2. Состояние системы на четвертом шаге . В табл. 1.1 этому состоянию соответствует город . Двигаясь от последней таблицы к первой определяем, оптимальный маршрут , затраты на перевозку груза по которому составляют .