Поиск оптимальной трассы с учетом расстановки перекачивающих станции

Поиск можно вести с использованием кратных трасс или не­посредственно по основному алгоритму (Ли или АУП).

Метод кратных трасс

Находим первую по оптимальности трассу и определяем число и места установки перекачивающих станций (ПС) вдоль этой трассы. Полная стоимость трубопровода с ПС w₁ = w_T1 + w_c1, где w _т1 — затраты на строительство линейной части и w_c1— на строительство ПС. Определяем вторую по оптимальности трассу и ее стоимость без ПС — w _{т 2} . Если w _т2>= w _т1 то поиск заканчи­ваем и наилучшей будет первая трасса с ПС. В противном слу­чае поиск продолжаем до тех пор, пока не будет выполнено условие

т. е. стоимость трубопровода вдоль какой-либо кратной трассы п без ПС w_т не окажется больше или равной стоимости трубо­провода вдоль трассы п—1 вместе со стоимостью ПС w_n-1.

Одновременный поиск трассы и расстановка ПС

Поиск будем осуществлять непосредственно по основному ал­горитму или алгоритму ускоренного поиска (3.8), используя в качестве оценивающего параметра (оптимальной оценки) функции стоимости строительства линейной части w_т(l) и про­межуточных перекачивающих станций w_c(n —1), где п — число ПС вдоль каждого пробного пути l. При достижении конечной точки будет найдена лучшая из всех трасс, вдоль которой уже распределены ПС, а стоимость ее будет