Задача о прокладке трубопровода

1. Задача о прокладке трубопровода

Требуется проложить трубопровод между двумя
пунктами A и B таким образом, чтобы суммарная
длина его была минимальной.

2. Задача о прокладке трубопровода

Разобьем участок на m горизонтальных и n
вертикальных
частей m=n=2
Путь – ломаная из горизонтальных и вертикальных
частей.
Количество частей (шагов) m + n= 2+2 =4
Известны длина каждой части.
Суммарная длина
Операция многошаговая (4 шага).
Z – аддитивная функция.
Процесс прокладки трубопровода без обратной связи.
Положение каждой узловой точки Sk зависит от предыдущей точки
Sk-1 и управления Uk (2 направления строительства).

3.

Решаем задачу с конца.
В точку B(S4) можно прийти либо по горизонтали, либо по вертикали
Условная оптимизация на последнем шаге:
Z4(s3)=min(6,7) U4=(в , ю)
Условная оптимизация на 3 шаге (на 2 и 1):
Z3(S2)=min(9+6=15,5+7=12,8+7=15)
U3=(в ,в, ю)
Z2(S1)=min(4+12=16, 7+15=22)
U2=(ю, ю)
Z1(S0)=min(6+16=22, 10+22=32)=22
U1=(ю, ю)
Минимальные затраты: 22=6+4+5+7
Оптимальное управление: U=(В, Ю, В, Ю)

4.

Решаем задачу с конца.
определим простые базовые случаи, шаг1
7
0

5.

Решаем задачу с конца.
определим простые базовые случаи, шаг1
15
7
0

6.

Решаем задачу с конца.
определим простые базовые случаи, шаг2
15
7
6
0

7.

Решаем задачу с конца.
определим простые базовые случаи, шаг2
15
7
15
6
0

8.

15
7
15
6
0

9.

15
12
7
16
15
6
0

10.

15
12
15
6
7
0

11.

15
23
12
7
22
15
6
0

12.

15
22
12
15
6
7
0

13.

25
15
16
22
12
15
6
7
0

14.

16
22
12
15
6
15
7
0

15.

22
16
15
32
22
12
15
6
7
0

16.

22
16
22
12
15
6
15
7
0

17.

Минимальные затраты: 22=6+4+5+7
Оптимальное управление: U=(В, Ю, В, Ю)
22
16
22
12
15
6
15
7
0