Построение наиболее экономного маршрута перевозки грузов по сети

Задача№1

Задание: Решить задачу построения наиболее экономного маршрута перевозки грузов по сети.

Требуется:

1.  Записать постановку задачи.

2.  Разбить пункты сети на группы.

3.  Методом динамического программирования найти наиболее экономичный маршрут доставки груза.

4.  Проанализировать решение, сделать вывод.

1. На данной сети дорог (рис. 1) указаны стоимости доставки единицы груза из пункта в пункт. Найти наиболее экономный маршрут перевозки груза из первого пункта в двенадцатый.

Рисунок 1.1 – Сеть дорог доставки груза.

                                                                                 2                                          

                                    4

                                                                                           4

                                              2                                                                                       2       

                                                                                       8                                                    

  3                                                                                           

                                                    7                                                                 

                                                                                                                                         3

      1                                             5

                                                                                                   6

     5                                                        3

                                              9

3                                    7

                                        8                                                                                   

1

2. Разбиваем пункты сети на группы.

Состояние - факт нахождения груза в пункте.

Управление – выбор направления движения .

Физическая система S – сеть дорого и транспорт с грузом.

Целевая функция  - минимальные затраты.

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

3. Находим наиболее экономичный маршрут доставки груза.

I. Этап условной оптимизации

i=4

i=3

i=2

i=1

II. Этап безусловной оптимизации.

1-3-5-9-12

Подсчитаем минимальные затраты на перевозку груза по данному маршруту:

1+2+2+2=7 д.е.

4. Вывод: С помощью метода динамического программирования определили маршрут доставки груза из пункта 1 в пункт 12, при этом минимальные затраты составят 7 д.е.