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

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

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

3 Решаем задачу с конца. В точку B(S 4 ) можно прийти либо по горизонтали, либо по вертикали Условная оптимизация на последнем шаге: Условная оптимизация на 3 шаге (на 2 и 1): Минимальные затраты: 22= Оптимальное управление: U=(В, Ю, В, Ю) Z 4 (s 3 )=min(6,7) U 4 =(в, ю) Z 3 (S 2 )=min(9+6=15,5+7=12,8+7=15) U 3 =(в,в, ю) Z 1 (S 0 )=min(6+16=22, 10+22=32)=22 U 1 =(ю, ю) Z 2 (S 1 )=min(4+12=16, 7+15=22) U 2 =(ю, ю)

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

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

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

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

8 0 7 6

9

10

11

12

13

14

15

16

17 Минимальные затраты: 22= Оптимальное управление: U=(В, Ю, В, Ю)