Главная  Переработка нефти и газа 

Скачать эту книгу

0 1 2 3 4 5 6 7 [ 8 ] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

ПРОДОЛЖЕНИЕ ТАБЛ. 3.1

Характеристика местности

Болота

I типа, с лесом II » без леса II » с лесом III » без леса

Многолетнемерзлые участки

Категории грунтов по просадочпости: 1-2-й, без леса 1-2-й, с лесом 3-4-й, без леса

Водные преграды

Река шириной, „.

10-30, грунт I-III категории

10-30, ----------" "

30-100, 30-100, 100-300, 100-300, 300-500, 500-1500,

IV категории и выше I-III категорий IV категории и выше I-III категорий IV категории и выше 1 ПГ категорий I-III категорий

Горы (продольный уклон >11°)

Категории грунта:

I-III, с лесом Г-III, без леса IV-V, с лесом IV-V, без леса VI-VII, без леса VIII-IX, без леса

Косогор

Поперечный уклон, градусы:

До 12; грунт I-III категории

12-18; то же

18 и выше; »

До 12; грунт IV-V

12-18; то же

18 и выше; »

До 12; грунт VI-VII

12-18; то же

18 и выше; »

До 12; групт VIII-IX

12-18; то же

18 и выше; »

Категория

12 13 14 15

16 17 18

20 21 22 23 24 25 26

27 28 29 30 31 32

33 34 35 36 37 38 39 40 41 42 43 44

Принятые 48 категорий .мегтиостп охватывают практически все необходимые случаи при выборе опти.мальных трасс в различных районах страны. Для конкретных трасс, даже значительной протяженности, обычно используются до 20-30 категорий. Стремление отдельных специалистов сузить количество натегорип местности может привести к менее детальному расчету и неполному 1гспользованию возможностей современной вычислительной техники. В случае необходимости количество категорий может быть доведено до 80.

§ 3.5. Оптимизация трассы с помощью ЭВМ

Задача отыскания оптимальной трассы формируется следующим образом: имеются начальная точка А и конечная В проектируемого трубопровода, которые требуется соединить по такой траектории, чтобы свести к минимуму суммарные приведеппые затраты, являющиеся критерием оптимальности. 7 * Прпмепптельпо к Hauicii задаче оптимальной необходимо считать трассу, вдоль которой полное значецие кри- 6 терпя М1гнпмально.

Приведсмшые затраты (тысячи рублей на 1 км в год) обладают свой- 5 ством аддитивности. Ото позволяет ротать задачу поиска оптимальной трассы в соответствии с алгоритмом Лп fl, 2]. Если область поиска задана или известна, то на топографическую карту наносят сетку, дуги ко- J торой нумеруют в определенном порядке, т. о. создается цифровая модель местности (рис. 3.1). После этого 2 подготавливают исходную информацию и определяют зпаченпе критерия оптимальности для каждоГг дуги сетки.

Па каждом inare алгоритма просматривают все построенные к этому

""•"чту пробные пути (последовательность дуг сети, начинающихся в точке 1) устанавливают тот из них, которому соответствует наименьшее значение

Риторпя оптплгальности. .Этот njTb рассматр1гвается как наиболее порсиек-ипный в данный момент. Затем eio надстраивают па новый шаг. При этом

овь образуется несколько дополнительных путей, каждый пз которых пред- "яет гобой увеличенный на одну дугу путь, который только что считался

2 3 4 5 S 7 Рис. 3.1. Цифровая модель меотноотн.

3ai;a;i 156

наиболее перспективным. Далее среди всех построенных к этому моменту пробных путей выбирают новый, наиболее перспективный, которому соответствует наименьшее значение критерия оптимальности, и затем этот путь надстраивается еще на один шаг. Процесс поиска продолжается до тех пор, пока среди образовавшихся путей не окажется тот, который оканчивается конечной точкой трассы и имеет минимальное значение критерия оптимальности по сравнению со всеми другими построенными к этому времени цроб-ныдга путями. Полученная в результате расчетов трасса и являензя оптимальной. Реализация алгоритма поиска оптимальной трассы осуществляется по программе, составленной для ЭВМ «Минск-22». Ниже подробно описан процесс поиска оптимальной трассы между начальной точкой А и конечной В.

% 3.6. Выбор оптимальной трассы газопровода с отводами с помощью ЭВМ

Алгоритм поиска. Задача поиска оптимальной трассы формулируется следующим образом: имеются начальная А и конечная В точки проектируемого магистрального газопровода, а также i промежуточных точек, к которым необходимо построить газопроводы-отводы. Требуется соединить между собой точки А и В трассой и подсоединить к ней отводы от i промежуточных точек таким образом, чтобы суммарные приведенные затраты были минимальны.

В качестве примера рассмотрим трассу с двумя отводами. Итак, имеется начальная, конечная и две промежуточные точки, которые, как и конечная, должны быть соединены с начальной. Особенность задачи состоит в том, что на каком-то участке трасса для конечной и промежуточных точек может быть общей.

Построим цифровую сеть местности и нанесем на нее упомянутые выше точки так, чтобы они располагались в узлах сети. Наша задача - найти на сети такой путь от начальной точки к конечной и промежуточным, для которого критерий качества пути, называемый нами стоимостью, достигнет наибольшого или наименьшего значения. Условимся, что требуется минимизировать критерий качества трассы. В простейшем случае этот критерий является аддитивным (например, приведенные затраты); в более общем он представляет собой монотонную функцию пути. Решение задачи поиска оити-мальной трассы между двумя точками в последнем случае считаем известным.

При решении нашей задачи лучше всего опираться на алгоритм Ли, основная идея которого заключается в следующем. На каждом шаге алгоритма анализируют все построенные к этому моменту пробные пути и устаиавлипагот тот из них, которому соответствует наименьший критерий качества пути. В рассматриваемый момент этот путь наиболее перспективен. Надстраивае,м этот путь на одну новую дугу во всех допустимых сетью направлениях. Получаем несколько вновь образованных путей, каждый из которых представляет собой увеличенный на одну новую дугу путь, который мы только что считали наиболее перспективным. Вновь анализируем все пройденные к настоящему моменту от начальной точки пути и определяем среди них новый, наиболее перспективный, которому соответствует наименьшая стоимость, и затем вновь надстрагтвасм его на одну новую дугу во всех допустимых направлениях. Продолжаем этот процесс до тех пор, цока среди образовавшихся посредством последовательной надстройки путей не окажется тот единственный, который приведет нас к коночной точке трассы и который имеет минимальную стоимость по сравнению со стоимостью всех образованных к этому моменту путей. Этот путь (а их может оказаться несколько) и будет оптимальным. Итак, оптимальный путь между начальной точкой А и конечной В найден.

Предположим, что этот путь единственный, а критерий качества трассы аддитивный. Обозначим cтoиtocть оптимальной трассы Z, между пачальяой А и конечно!! В точками через Si- С помощью аналогичного алгоритма можно найти оптимальный путь из промежуточных точек С п D к трассе 1 (назовем эти пути отводами). Отличие вновь поставленной задачи от предшествующей

«6

состоитв том, что процесс поиска закончится лишь после того, как в область пассмотреяия впервые попадет путь из промежуточной точки С или D к любой vaioBOH точке трассы 1, при этом стоимость этого пути будет минимальной посравнению со стоимостями других образовавшихся к этому моменту путей из промежуточных точек. Обозначим стоимость отвода из точки С через ii, я стоимость отвода из точки D через d.

Рассмотрим случай выбора трассы с одним отводом из точки С. Стоимость всей трассы Li из точки А в точку В с отводом в точку С равна S, df, при этом предполагаем, что стоимость трассы между точками А и В не зависит от стоимости отвода к точке С. Но, строго говоря, эта трасса не является оптимальной. Может существовать другая трасса с отводом, стоимость которой моя«ет быть представлена в виде S -f- d, где S - стоимость трассы меноду точками А а В; d - стоимость отвода, причем

S + d<St + di.

Однако в силу оптимальности li справедливо неравенство 5j <; S.

Исходя из этого можно утверждать, что если существует трасса с отводом Ь меньшей стоимости, чем трасса L, то стоимость ее отвода d должна быть меньше таковой dj.

Допустим, что есть оптимальная трасса L с отводом, отличная от трассы Li- Ее стоимость, равная S" + d", удовлетворяет неравенству

S" + d"<S,-i.d„

при этом

S">S,- d"<d,. (3.1)

С jeToM неравенства (3.1) можно предложить следующую идею поиска оптимальной трассы с отводом. Найдем оптимальную трассу Zj между точками А я В, назвав l-a по оптимальности генеральной трассой, и оптимальный отвод от нее к точке С, подсчитаем стоимость всей трассы Li. После этого найдем BTopjTo по оптимальности генеральную трассу, т. е. такую трассу между начальной А и конечной В точками, стоимость которой больше таковой трассы L, но меньше стоимости любой из остальных генеральных трасс, затем последовательно третью, четвертую и т. д. генеральные трассы, проводя этот поиск до тех пор, пока стоимость любой из еще не найденных в порядке удорожания генеральных трасс превысит или будет равна стоимости лучшей из уже рас-емотреяных трасс с оптимальным отводом. Эта лучшая трасса и будет оптимальной.

Для точного описания алгоритма поиска введем следуюхцие обозначения:

Sk - стоимость к-й по оптимальности генеральной трассы;

(Lm) - множество минимальных по стоимости трасс с отводами, получающихся присоединением cobokjtihocth оптимальных отводов к каждой иа т-х по оптимальности генеральной трассы;

Ln - трасса - представитель множества (Lm);

йт - стоимость трассы Lmf

(Lm) - подмножество минимальных по стоимости трасс из множества и (L„);

Lm - трасса - представитель множества (Lm); ft<n - стоимость трассы Ьт.

Алгоритм поиска. 1-й: ищем 1-е по оптимальности генеральные трассы. Определяем Sk- Находим совокупность оптимальных отводов от каждой из эгих трасс ко всем промежуточным точкам. Находим Oi я (Li). Полагаем (Lj) = (ij) и ftj = е.

fc-й шаг: ищем fe-e по оптимальности генеральные трассы и определяем Sk- Если не существует ни одного варианта таких трасс (т. е. все генеральные трассы уже просмотрены) или если > то поиск прекращаем и делаем вывод, что (L».j) - множество оптимальных трасс.

5* 67

Если жв S/г h, то находим совокупность оптимальных отводов к каждой из этих трасс и определяем Ок-

При ail 6fc-i (если Lk больше по стоимости ij.i) полагаем

6fe = b4 ,; (L)=(ift-t);

при Oft = bk-i

bk = b,.,; (L;)=(i.,)[;(i»);

при Oft <5 bk-i

6ft=«ft; (i;) = (ift).

Ha этом завершается k-ik шаг и начинается (к + 1)-й.

Необходимо заметить, что в описанных алгоритмах нигде не учитывается аддитивность показателя. Алгоритм может быть использован, если критерий качества пути представляет собой монотонную функцию пути.

Очевидно, проводить поиск оптимального варианта трассы с отводами при помощи различных по оптимальности генеральных трасс можно в том случае, когда существует много генеральных трасс, из которых стоимость отдельных превышает стоимость трассы L. Примерным ориентиром в случае аддитивности критерия может служить следующее условие:

lii « Si.

В случае, когда к генеральной трассе с помощью отводов должна быть подсоединена не одна, а i-e число точек, задача может решаться аналогично вышеописанному. Разница будет состоять лишь в том, что после отыскания очередной по оптимальности генеральной трассы будут найдены оптимальные пути к этой трассе от всех промежуточных точек и будет определена суммарная стоимость всех путей. Примерным ориентиром целесообразности такого поиска можно считать удаленность промежуточных точек друг от друга и малую Суммарную стоимость всех отводов по сравнению со стоимостью первой по оптимальности генеральной трассы

2 < 1-

(3.2)

Поиск трассы газопровода- с отводами. Процесс поиска оптимальной Генеральной трассы и трасс, кратных ей по оптимальности, подробно рассмотрен выше. Используем теперь алгоритм выбора оптимальной генеральной трассы для поиска трассы газопровода с отводами. Дли наглядности и четкости илложепия воспользуемся примеро.м цифровой сети местности (рис. 3.1).

Диаметры отводов, как правило, всегда меньше диаметра генерального направления, в связи с этим перед поиском оптимальных отводов стоимостные характеристики дуг сети должны быть пересчитаны с учетом фактических диаметров отводов. В пашем примере для простоты условимся считать, что стоимостные характеристики дуг отводов такие же, как и стоимостные характеристики дуг генерального направления.

Проведем процесс поиска оптимальной трассы газопровода с отводами в соответствии с алгоритмом, описанным в работе [41, когда отводы предполагается провести в точки С (4.1) и D (4.4).

7-й шаг. 1. Находим первые по оптимальности генеральные трассы и определяем их стоимость Si. В пашем частном примере - это одна генеральная трасса Zj со стоимостью Si - 5,5, проходящая по пути:

(6.5) (6.4) (6.3) (5.3) -* (5.2) (4.2) - (4.3) (3.3). 2. Определяем совокупность оптимальных отводов от заданных промежуточных точек С (4.1) и D (4,4) к трассе Zj. В соотвст-

ствии с алгоритмом поиска находим оптимальные пути от точек С п D. Для этого воспользуемся следующей формой записи. В первую строку левого столбца заносим точку D (4.4) со стоимостью достижения О, а в первую строку правого столбца - все соседние с ней точки со своими стоимостями достижения.

Минимальной стоимостью достижения, равной 2, в нравом столбце обладает точка (5.4). Переносим ее во вторую строку левого столбца, исключив все сведения о ней из правого. Рассматриваем все соседние с ней точки, определяем стоимости их достижения и записываем их во вторую строку правого столбц*, затем находим в пей новую точку с минимальной стои.мостью достижения, заносим все сведения о ней в третью строку левого столбца, анализируем все соседние с ней точки и т. д. В результате получим такую запись:

1. D (4.4) О (3.4)3; (4.3)5; (5.4)2; (4.5)4;

2. (5.4) 2 (1-я строка); (5.3) 4; (6.4) 3; (5.5) 4

3. (3.4) 3 (1-я строка); (2.4) 5; (3.3) 4; (3.5) 3,5 Минимальной стоимостью достижения, равной 3, обладает

точка (6.4) - одна из узловых точек первой по оптимальности генеральной трассы. Точки (5.3) и (3.3) также являются узловыми этой трассы. Однако стоимость их достижения, равная 4, выше стоимости достижения точки (6.4), поэтому пути, приводящие в точки (5.3) и (3.3) не могут быть оптимальными. Итак, оптимальный путь из точки D (4.4) к первой по оптимальности генеральной трассе проходит по точкам: (4.4) -v (5.4) ->- (6.4) и стоимость его d = 3. Подобным образом легко найти оптимальный путь из точки С (4.1) к первой генеральной трассе, стоимость которого = 1.

Трасса Zj с отводами d\ и образует полученную в результате расчета трассу L,. Стоимость ее aj = S, -j- й\ -j- = = 5,5-1-3,0 4-1,0=9,5.

3. Так как Li на первом таге - единственная минимальная но стоимости генеральная трасса с отводами, то полагаем, что (i,) = {W, (L[) = (i,) = i, и Ь, = «1 = 9,5.

2-й шаг. 1. Находим вторые по оитимальпости генеральные трассы и определяем их стоя.мость S. В пашем примере это будут генеральные трассы с 5j = 7,0.

Z - трасса, проходящая по пути: (5.3) (5.2) (4.2) (4.3) (3.3);

1\ у- трасса, проходящая по пути:

(6.5) (6.5).

- (6.4). (6.4).

- (5.4)

- (6.3).

(5.3) (5.2) ~* (4.2) (4.3) (3.3).

Но так как 52 = 7,0 <; bi = 9,5, то в соответствии с алгоритмом ко второй по оптимальности генеральной трассе (в пашем случае пх две) найдем оптимальные отводы от точек С и £>.

2. Определяем совокупность оптимальных отводов от заданных точек С и D к трассам и 1\. Легко увидеть, что оптимальные отводы к трассе Zj представляют собой пути от точки С: (4.1) -> (4.2) со стоимостью cf~ = 1 и от точки D: (4.4) -> (5.4) со стоимостью d" = 2. Полученную трассу, включающую трассу Z с отводами d] и d" обозначим через L. Стоимость последней L\ равна а\ = S-\- di-i -j- di = 7 -j- 1 -j- 2 = 10. Оптимальные отводы к трассе обозначим от точки С