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

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

Решаем задачу с конца. В точку 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 =(ю, ю)

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

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

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

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

0 7 6

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