9.3.2. Пример выполнения задачи 2

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

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

1-й шаг. K=1.

F1(I)=Ci10

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

Таблица 57

J

I

10

F1(i)

J*

7

7

7

10

8

8

8

10

9

10

10

10

 2-й шаг. K=2.

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

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

Таблица 58

J

I

7

8

9

F2(i)

J*

5

14+7

6+8

-

14

8

6

-

12+8

9+10

19

9

3-й шаг. K=3.

Таблица 59

J

I

5

6

F3(i)

J*

2

12+14

-

26

5

3

-

6+19

25

6

4

-

11+19

30

6

 4-й шаг. K=4.

Таблица 60

J

I

2

3

4

F3(i)

J*

1

11+26

10+25

3+30

33

4

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

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F4(1)=33. Данный результат достигается при движении груза из 1-го пункта в 4-й. По данным таблицы четвертого шага необходимо двигаться в пункт 6, затем – в пункт 9 (см. таблицу второго шага) и из него – в конечный пункт (см. таблицу первого шага). Таким образом, оптимальный маршрут доставки груза: 1 4  6  9  10. На графе жирными стрелками показан оптимальный путь.

Яндекс.Метрика