85607 (612523), страница 5
Текст из файла (страница 5)
Таблица 18.
| C1 | X1 | F1(C1) | X* | |||||
| 0 | 20 | 40 | 60 | 80 | 100 | |||
| 0 | 0+0 | - | - | - | - | - | 0 | 0 |
| 20 | 0+48 | 14+0 | - | - | - | - | 22 | 0 |
| 40 | 0+93 | 14+48 | 26+0 | - | - | - | 42 | 0 |
| 60 | 0+135 | 14+93 | 26+48 | 35+0 | - | - | 59 | 0 |
| 80 | 0+149 | 14+135 | 26+93 | 35+48 | 52+0 | - | 72 | 0 |
| 100 | 0+160 | 14+149 | 26+135 | 35+93 | 52+48 | 61+0 | 87 | 0 |
По данным последней таблицы максимальных доход с четырех предприятий составил 87 д.ед. При этом первое и второе предприятия не принесут никакого дохода, в них нецелесообразно вкладывать инвестиции. В 3-е предприятие нужно вложить 80 д.ед. В 4-е предприятие нужно вложить 20 д.ед. В итоге останется 20-Получается, что оптимальный план Х*(0;0;80;20)
Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)
Задача
В предложенной из начального пункта (1) в конечный пункт (11). Стоимость проезда между отдельными пунктами транспортной сети придумать самостоятельно и транспортной сети имеется несколько маршрутов по проезду представить в соответствующей таблице (T(i,j)). Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.
8
14
8
6
10
20
9
12
12
8
13
11
7
10
15
13
16
15
18
Рисунок 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)
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
