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

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

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

Критерии второго класса не обладают таким свойством, и их можно назвать неаддитивными критериями. Рассмотрим несколько критериев, обладающих и не обладающих свойством аддитивности.

Капиталовложения К определяются затратами на осуществление строительства трубопровода. Отнесенные к единице длины, они называются удельными капиталовложениями, а для всей длины трубопровода -полными капиталовложениями.

Длина трубопровода и величина металловложений в качестве критерия оптимальности могут использоваться, например, при необходимости проложить трубопровод по участкам местности, обладающей определенными характеристиками; при этом требуется найти такой путь, длина которого была бы минимальной. Естественно, что таким путем не обязательно будет прямая между начальной и конечной точками.

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

(11.1)

где /С - капиталовложения; с - коэффициент эффективности капиталовложений; 5 -ежегодные средние эксплуатационные расходы.

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

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

При последовательном методе строительства общее время

(11.2)

где Ti - случайное время выполнения работ па i-m участке.

Задача поиска трассы заключается в отыскании такой трассы, для которой математическое ожидание времени строительства

M(T) = ZMi{Ti)

(11.3)

будет минимальным. В этом случае "время - аддитивный критерий.

При необходимости завершить строительство в заданный срок Го следует определить максимум вероятности

где F -функция Лапласа,

(11.4)

(11.5)

где D{Ti) - дисперсия Г,.

В этом случае время-неадднтивный критерий, поскольку параметр X- монотонно убывающая функция пути.

При параллельном методе строительства работа начинается сразу иа нескольких участках п.

Общее время будет

Г = тах(Г1, .....Г„). (11.6)

Если необходимо обеспечить выполнение условия ТТ, то следуе» определить максимум вероятности TiTo. В противном случае достаточно найти минимум математического ожидания случайной величины Т.

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

Каждому отрезку или участку трубопровода соответствует некоторая вероятность неразрушимости или мера надежности Лгеразр. Тогда всроятность нсразрушимости трубопровода па каком-либо участке в период времени Т будет

Рнервэр(Л = 1-разр(Л. (П.Т)

где Ргразр - функция распредсления вероятности Pi на г-м участке в период времени Т..

Поскольку трасса представляет некоторую последовательность различных участков, то вероятность неразрушимости трубопровода в целом будет определяться по условию

неразр

(Г) = пр,„,р,зр(Г),

(11.8)

где П -знак произведения.

Задача сводится к отысканию такой последовательности участков, для которой функция (11.8) достигает максимума.

§ 11.2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

Задачи поиска оптимальных трасс магистральных трубопроводов решаются на различных сеточных моделях местности. Они могут быть упорядоченными и произвольными. Упорядоченные модели - это прямоугольные сетки (рис. 11.1) без диагоналей а и с диагоналями б и приводимые к ним модели произвольного очертания (рис. 11.2,а и б). Если изображенную на рис. 11.2, а сетку необходимо упорядочить, то сначала вводят фиктивные узлы (узлом называют точки пересечения двух и более дуг) 15, 16, 17, 18 (рис. 11.2,6), а затем условно дуги (так называют линии между узлами) выравнивают и получают сетку прямоугольной формы с диагоналями. Фиктивные узлы (обозначены кружочками) и дуги (пунктир) не несут никакой информации о местности и трубопроводе. Поэтому прохождение по ним трассы исключается. Такое представление сеточной модели позволяет четко фиксировать все дуги и узлы на области поиска оптимальной трассы в прямоугольной системе координат.

Выполненные рядом авторов (П. П. Бородавкин, В. В. Бес-хижко, О. А. Лысый, Б. И. Ким, В. П. Бескоровайный, А. С. Ти-щенко, А. Н. Коваленко, В. Г. Тропин и др.) исследования позволили получить решение большого числа задач поиска оптимальных трасс на упорядоченной сетке, а также разработать методы решения на сетке произвольной формы, пе упорядочивая ее.

Основные исследования на сетке проведены с использованием методов динамического программирования и принципа оптимальности Белмана, суть которого состоит в том, что «оптимальная стратегия (поведение) обладает тем свойством, что каковы бы ни были начальные состояния и начальное решение, последующие решения должны составлять оптимальную стратегию (поведение) относительно первоначального состояния».

Одним из сильнейших алгоритмов, позволяющих реализовать данный принцип, является алгоритм Ли (1962 г.), основная идея которого заключается в следующем.

На каждом шаге алгоритма происходят исследования всех пробных путей, построенных от начальной точки трассы, н установление пути с наименьшей стоимостью. Этот путь в данный момент является наиболее перспективным. Надстраиваем его на одну новую дугу во всех допустимых сеткой направлениях. Получаем несколько дополнительных путей, каждый из которых представляет собой увеличенный на одну дугу путь, который мы только что считали наиболее перспективным. Затем среди всех построенных к настоящему моменту путей ищем новый наиболее перспективный и надстраиваем его на одну новую дугу во всех допускаемых сеткой направлениях. Этот

-.248

Рис. 1I.I. Сетка прямоугольная:

а - без диагоналей; б - с диагоналями

15 6

Рис. 11.2. Сетка произвольной конфигурации:

а - нормальная; 6 -с фиктивными узлами; в - прямоугольная; г - вертикальная полоса

процесс продолжается до тех пор, пока среди сформированных последовательной надстройкой путей не окажется путь, оканчивающийся последней точкой трассы и имеющий минимальную стоимость по сравнению со стоимостями всех сформированных к этому моменту путей. Этот путь (их может оказаться несколько) и будет оптимальным.

Эта идея послужила основой для реализации алгоритмов поиска оптимальной трассы на сетках прямоугольной и произвольной конфигураций.

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

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

Для поиска Оптимальных трасс применен метод последовательного анализа вариантов. Исходная сетка в этом случае разбивается на группы узлов - уровни, отстоящие друг от друга не более чем на одну дугу (рис. 11.2,г). При этом строится сетка произвольной формы, но разбиение сетки на уровни накладывает существенные ограничения на подготовку информации. Хотя по сути этот метод мало отличается от метода, в котором используется сетка прямоугольной формы, однако он позволяет весьма эффективно реализовать его на ЭВМ.

Рядом авторов поиска оптимальных трасс рассматривалась задача поиска кратчайшего пути как на ориентированном, так и на неориентированном графах.

Более сложным как в математическом плане, так и в плане реализации в расчетах на ЭВМ, являются задачи поиска трасс с отводами и оптимизации конфигурации трубопроводных систем.

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

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

§ 11.3. ОСНОВНЫЕ АЛГОРИТМЫ

1. Алгоритм Ли

Основная идея алгоритма сформулирована в § 11.2. Она реализуется с помощью двух списков и к V. Каждый список содержит набор занумерованных строк стоимости дуги (под стоимостью дуги понимается величина критерия оценки трубопровода по данной дуге) и направления ее входа в узел.

х-1 x .т+1 +г +j + +5 н-е +7х

11.3. Дуги наибольшей стоимости

В список и в первую строку записывают данные о начальной точке, а в список v - данные о ее соседних точках. Выбирают из списка v точку с наименьшей стоимостью достижения и переносят ее в список и, вычеркивая одновременно из списка V. Таким образом. Рис. в списке и появляется вторая точка, для которой в списке и записываются данные о всех ее соседних точках. Опять выбирается из всех точек точка с наименьшей стоимостью и т. д. до тех пор, пока в список и ие попадет конечная точка. В заключение по направлениям входа восстанавливается путь наименьшей стоимости. Подробно этот алгоритм описан в работе [1].

2. Алгоритм ускоренного поиска (АУП) Одним из недостатков алгоритма Ли является необходимость исследования всех без исключения путей, даже тех, которые ведут в заведомо неоптимальные направления. Цель АУП [1] - отбраковка этих бесперспективных путей. Выполняется это, исходя из следующих соображений. Допустим, что в процессе поиска мы пришли в узел с координатами х, у (рис. 11.3) Оптимальным путем. Требуется в соответствии с принципом оптимальности Беллмана дойти до конечной точки К. Очевидно, что стоимость любого оптимального пути из X, г/ в /С не может быть меньше, чем стоимость суммы дуг по направлению х и у, имеющих наименьшие значения. Эти дуги выделены на рис. 11.3 жирной линией (по направлению х 1-7, по направлению у-8- ).

В качестве оценки пути на каждом шаге поиска нужно брать не истинную его стоимость wa,x,y от начальной точки до x, у, а сумму

(11.9)

где и есть так называемая оптимистическая оценка пути в случае аддитивного критерия.

Если стоимость исследуемого пути является монотонной функцией пути f(L), то АУП необходимо изменить следующим образом.

Каждый построенный пробный путь будет сравниваться с оптимистической оценкой !оЩ, содержащей путь L в качестве пути из А в К. При этом будут надстраиваться лишь те пути, для которых /о() =/(/опт), т. е. в АУП при /(L), являющейся монотонной функцией пути, условие ускорения процесса отбраковки пробных путей определяет неравенство