Задачи математического программирования

курсовая работа

Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)

Задача

В предложенной из начального пункта (1) в конечный пункт (11). Стоимость проезда между отдельными пунктами транспортной сети придумать самостоятельно и транспортной сети имеется несколько маршрутов по проезду представить в соответствующей таблице (T(i,j)). Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.

Рисунок 2 - Транспортная сеть

Элементы матрицы маршрутов транспортной сети, а так же стоимость проезда из пункта i в пункт j (tij) представлена в таблице 19.

Таблица 19.

j

i

1

2

3

4

5

6

7

8

9

10

11

1

-

10

12

8

20

-

-

-

-

-

-

2

-

-

-

-

-

15

11

-

-

-

-

3

-

-

-

-

-

6

9

-

-

-

-

4

-

-

-

-

-

7

10

-

-

-

-

5

-

-

-

-

-

13

8

-

-

-

-

6

-

-

-

-

-

-

-

12

14

18

-

7

-

-

-

-

-

-

-

13

15

16

-

8

-

-

-

-

-

-

-

-

-

-

8

9

-

-

-

-

-

-

-

-

-

-

10

10

-

-

-

-

-

-

-

-

-

-

10

11

-

-

-

-

-

-

-

-

-

-

-

Решение

Этап I. Условная оптимизация.

Шаг 1. k = 1. F1(S) = ts10.

Таблица 18.

S

J=11

F(S)

J*

8

8

8

11

9

10

10

11

10

10

10

11

Шаг 2. k = 2. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 19.

S

J=8

J=9

J=10

F(S)

J*

6

12+8

14+10

18+10

20

8

7

13+8

15+10

16+10

21

8

Шаг 3. k = 3. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 20.

S

J=6

J=7

F(S)

J*

2

15+20

11+21

32

7

3

6+20

9+11

26

6

4

7+20

10+21

27

6

5

13+20

8+21

29

7

Шаг 4. k = 4. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 21.

S

J=2

J=3

J=4

J=5

F(S)

J*

1

10+32

12+26

8+27

20+29

35

4

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

На этапе условной оптимизации получено, что минимальные затраты на проезд из пункта 1 в пункт 11 составляют F4(1) = 35, что достигается следующим движением по магистралям. Из пункта 1 следует направиться в пункт 4, затем из него в пункт 6, затем в пункт 8 и из него в пункт 11. Таким образом, оптимальный маршрут будет J*(1;4;6;8;11)

Делись добром ;)