Проектирование крупномасштабных транспортных сетей в условиях неопределенности исходной информации тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

Челябинский государственный технический университет РГ6 Ой

На правах рукописи

ДЕМЧЕНКО Александр Иванович

ПРОЕКТИРОВАНИЕ КРУПНОМАСШТАБНЫХ ТРАНСПОРТНЫХ СЕТЕЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ ИСХОДНОЙ ИНФОРМАЦИИ

Специальность 01.01.11 - "Системный анализ и автоматическое управление'*'

Автореферат диссертации на соискание ученой степени кандидата технических наук

¿ЛЯЗяест1: -1993

Работа выполнена в Челябинском государственном техническом университете.

Научный руководитель - доктор технических наук, профессор

Щганков В.А.

Официальные оппоненты: доктор технических наук, профессор , Чапцов Р.П.,

кандидат технических наук Ахпателов Э.А.

Ведущая организация - Вычислительный центр Сибирского

отделения АН РФ (г.Красноярск).

Защита диссертации состоится 1993 г.,

в -/¿Ч на заседании специализированного совета Д.053.13.06 в Челябинском государственном техническом университете, аудитория £44 (454080, г.Челябинск, пр.им.В.И.Ленина, 76).

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " ЪС» 1993 г.

Ученый секретарь специализированного совета кандидат технических наук, доцент

Барыкин С.Г.

ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Задачи проектирования транспортных сетей возникают при проектировании различного рода коммуникаций. Примерами таких коммуникаций могут служить сети автомобильных и железных дорог, сети электроснабжения, продуктопроводы различного назначения и т.д. В частности, такая задача возникает при проектировании систем обустройства месторождений полезных ископаемых:, нефти, газа, угля и- т.д. Соответствующею отрасли промышленности являются наиболее динамичными. Ежегодно в стране вводятся в действие й обустраиваются сотни месторождений. Для районов освоения месторождений полезных ископаемых характерным - является не только ввод самих месторождений, но и создание региональных систем обслуживания месторождений. Для нефтедобывающих районов Западной Сибири сложность задачи возрастает в связи с особыми природными,, географическими и экономическими условиями. Особенностью таких регионов является • отсутствие инфраструктуры,, удаленность от экономически освоенных районов. Капитальные влозкения, требуемые для строительства транспортных сетей систем обустройства, составляют миллиарды рублей. Поэтому актуальной является задача их оптимального проектирования.

Каждая сеть связывает на местности множество источников фиксированного продукта со стоком. Мондаасти источников • определяются . по .принятой методике с учетом запасов и сроков эксплуатации месторождения. Стоимость сети складывается из диух составляющих:

Г) капитальной, куда входит-стоимость строительства коммуникаций сети и затраты на поддержание их в работоспособном состоянии, 2) эксплуатационной, равной стоимости затрат на транспортировку -продукта по сети.

При проектирования транспортных сетей привлекается- болызой объем информации. И уже на стадии птзозкттпзозания приходите.: сталкиваться с тек, что многие исходные аншэ, влаяшие на параметра транспортной сети, не могут сыть стоалелекы однозначно. В тзеальпых условиях имеет "естс ситуация нйоггаелолячнеетт! относительно параметров проектируемой еэти, что треоузт адекватной постановки, задачи оптимизации, зыботз математически^

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

Основной задачей при проектировании транспортных сетей является задача синтеза оптимальной структуры сети. Различные постановки задачи.синтеза оптимальной структура сети приведены в работах Финкельштейна Ю.Ю., Прима Р., Хачатурова В.Р., Злотова

A.B., Ахпателова З.А., Табакова Н.В., и 'других советских и зарубежных исследователей. Как правило, для рассматриваемых задач не существует алгоритмов полиномиальной трудоемкости. В существующих публикациях предлагаются приближенные алгоритмы без оценки точности и эффективности, ли£о алгоритмы с оценкой точности полученного решения, но без оценки трудоемкости. К тому же максимальная размерность решаемых задач оценивается величиной 30-50 вершин сети. Серьезную трудность таккне имеет обобщение этих алгоритмов на случай неопределенности исходных данных. Реальные сети имеют большую размерность, а 'имеющаяся неопределенность вызывает необходимость многократного их решения. Поэтому применение традиционных методов синтеза структуры транспортной сети не представляется возможным.

Для решения поставленной 'задачи предлагается использовать подход, описанный в работах Пельцвергера Б.В. и Хавронина О.В., . который. заключается в выделении класса. 1УР-трудных задач комбинаторной оптимизации, эффективно решаемых на основе декомпозиционного, подхода. -Основная идея декомпозиционного подхода рассматривается в работах . Краснощекова П.С., Морозова

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

Работа по тематике диссертации выполнялась в соответствии с • техническим заданием по' разделу 03.02.06 целевой комплексной научно-технической программы 0.Ц.026 "Методы автоматизированного синтеза функциональных и алгоритмических .структур АСУ ТП", в рамках научно-исследовательских . работ Челябинского политехнического института "Разработка алгоритмов решения задач проектирования транспортных сетей" (тема 8GI23, * гос.регис.

01860041159), "Разработка системных моделей и процедур синтеза крупномасштабных транспортных и коммуникационных'систем с учетом экологических факторов и неойределенности исходной информации" (шифр проекта "Трансист" Л 730 ГКНТ СССР).

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

В соответствии с поставленной целью в диссертационной работе поставлены следующие задачи:

1. Провести анализ задачи проектирования крупномасштабных транспортных сетей в условиях неопределенности, методов решения, возможности учета неопределенности.

2. Пранализировать факторы, влияющие на неопределенность параметров транспортной сети; классифицировать их по способу влияния на параметры сети; рассмотреть способы формализации неопределенных параметров.

3. Разработать экономико-математические модели задачи синтеза структуры транспортной сети в условиях неопределенности.

4. Исследовать условия применения декомпозиционного подхода к решению поставленной задачи.

5. Разработать и проанализировать алгоритмы синтеза транспортной сети для различных типов неопределенности исходной информации.

6. Использовать разработанные метода синтеза транспортных сетей в условиях неопределенности на практике при решении задачи проектирования транспортных" сетей системы обустройства нефтяных месторождений. . • • .

Методы исследования. Для решения поставленных задач были использованы, .методы теории», систем, системного анализа,, теории графов, методы комбинаторной оптимизации, теория игр, нечеткое математическое программирование.- ;

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

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

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

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

Основные положения, выносимые на защиту. На защиту выносится методика проектирования крупномасштабных транспортных сетей в условиях различных типов неопределенности исходной информации. Методика включает в себя:

- способы формирования математических моделей местности с учетом недетерминированной информации;

- разработку акономико - математических моделей задачи синтеза структуры транспортной сети в условиях неопределенности исходной информации;

алгоритмы, реализующие схему решения, основанную на декомпозиционном подходе, учитывающие неопределенность исходных данных,' описываемую интервальными . числами или нечеткими множествами; - -

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

Апробация работы.' Научные я практические результаты работы докладывались и обсуждались на: Девятом и Десятом всесоюзных симпозиумах "Системы программного обеспечения решения задач оптимального планирования" (Минск, 1986 и Нарва-Иыэсуу, 1988), II Всесоюзном семинаре "Роботы и гибкие производственные системы" (Челябинск,- 1988), IV Всесоюзном совещании' "Методы и программы решения оптимизационных задач на графах" (Новосибирск, 1989)," конференциях и семинарах по интервальной математике (Красноярск-1988, Абакан-1939, Саратов-1989 и 1990), Международной конференции по интервальным и стохастическим методам (Москва, 1992), 6-ой Всемирной Конференции по Транспортным Исследованиям (Лион, Франция, 1992).

Публикации. Научные результаты, составляйте основное содержание диссертации, опубликованы в 15 работах.

Структура и объем работы. Диссертация состоит из- введения, пяти глав, заключения, списка литературы и приложений. Работа выполнена на 117 страницах, содержит 8 рисунков. Список использованной литературы содержит 49 наименований.

СОДЕРЖАНИЕ РАБОТЫ .

В пэрвой главе проведен анализ*, задачи проектирования крупномасштабных транспортных сетей в' условиях неопределенности исходных данных. Задача проектирования .транспортных сетей шее? широкую область применения. Такая задача возникает при проектировании различного рода коммуникаций, в частности при проектировании системы обустройства месторождений полезных ископаемых. Система обустройства месторождения состоит из рядг. подсистем (сети соотэа добываемого продукта, сети поадвсяанкя пластового давления, сети электроснабжения, промысловых sopor, теплогазоснасжения к т.д.), многие аз которых представляют собоЛ транспортные сети различного назначения.

Стоимость трзпепортянх сетей. ахоляодх в систему обустройства местороздений составляет до • 80л стоимости обустройства месторождения и во многом определяет характеристики

других промышленных объектов, входящих в систему обустройства. Бопылая стоимость проектируемых транспортных сетей, неочевидность способов получения хороших проектных решений вызывают необходимость в применении оптимизационных моделей и методов для автоматизированного проектирования.

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

К основным, факторам, которые учитываются в современных методах автоматизированного проектирования относятся:

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

2¿ Различные конструктивно-технологические решения строительства конкретной трансгортно-коммуникационной ' сети. Ка выбор решения влияет появление новых материалов или способов строительства и т.д.

3, Эксплуатационные /характеристики дорожных конструкций, которые определяются затратами на содержание, текущий и средний ремонты. ■

■ 4: Затраты на транспортирование 'грузов, рассчитываемые на основе планируемых, объемов за период функционирования сети,-

5. Затраты,' связанные' с ущербом, который причиняется окружающей среде в процессе строительства и эксплуатации сети.

6. Ситуации, в которых учитывается . влияние природных или искусственных объектов на выбор оптимального решения.

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

• относительно параметров проектируемой сети. Это обстоятельство требует адекватной постановки задачи • оптимизации, выбор математической . модели, включающей неопределенность исходных ■данных, и, вообще говоря, не позволяет использовать алгоритмы,

• .предназначенные, для решения детерминированных задач.

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

1) факторы, которые являются внешними по отношению к модели и действуют одинаково на ее параметры. К ним относятся: срок эксплуатации сети, мощность запасов месторождения, способы строительства и т.д.

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

Будем говорить, что первая груша факторов обуславливает внешнюю неопределенность модели, а вторая - внутреннюю.

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

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

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

Размерность задачи определяется количеством вершин граФа (количеством узлов ЩГЭПТ) и числом грузообразующих пунктов. На практике число узлов ЦМТЭИГ для нефтяного месторождения составляет в среднем около 10 тысяч, поэтому существующая практика проектирования- основывается на декомпозиции задачи синтеза транспортной сети на три последовательно решаемые задачи: задачу синтеза структуры сети (задача о топологии сети), задачу размещения узлов ветвления при заданной структуре сети, задачу поиска магистрального хода трассы между каждой- парой смежных вершин.

Для задач размещения' узлов * ветвления и' построения магистрального хода трассы существуют эффективные алгоритмы решения.

Задача ' синтеза структуры сети -является основной в приведенной' схеме декомпозиции. Это связано с .тем, что оптимизация структуры сети приносит наибольший . эффект при

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

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

Зкономико-математическая модель задачи синтеза структуры сети в детерминированном случае имеет следующий вид. Задан граф G=(V, Е), У= I и а0), Ъ={(1,Л\и е I и а0)), где I -множество источников продукта, которые требуется связать сетью со стоком Б - множество допустимых коммуникаций. Vi « I задана мощность источника 0, pt= - ]> р(. 4{l,j) е Е задана стоимость

строительства коммуникации - u>{J и удельная стоимость транспортировки продукта - vlJ . Задача синтеза в комбинаторной постановке имеет следующий вид:

F(T)= £ (wij + Vij'yij) _> min> т ! п (1)

где Т - стягивающее дерево графа G, ytj(T) ~ поток по ребру (l,J) в дереве Т, который определяется однозначно для заданного Т при выполнении условия полного перетока, Q - множество стягивающих деревьев графа G.

Для задачи синтеза сети в условиях внешней - и внутренней неопределенности постановка будет иметь следующий вид соответственно :

F(T)= 2 lâ-wtJ + -> min, Te 0 (2)

(3)

интервальными

F(T)= 2 ftü4J + v^-Уц) -> min, . T € fi

(l.JJ^T.

где а и ß - неопределенные параметры, моделируемые числами или нечеткими множествами.

Во второй главе описываются экономико-математические модели для задачи синтеза транспортной сети в условиях неопределенности.

ЦМТЗПТ полностью описывабтся парой <1,ср>, где И - матрица, имеющая размерность п*т, элементами которой являются элементарные области квадратной формы. Смежным элементам такой матрицы соответствуют смежные области местности; <р: отображение, ставящее в соответствие области MlJ удельную стоимость строительства коммуникации в пределах , определяемую технико-экономическими показателями территории. В качестве Р обычно выбирается И1- пространство действительных чисел.

В условиях неопределенности в качестве пространства Р выступает пространство интервальных чисел 1(Н) или пространство нечетких переменных вида (х, • (х (я)).

К возникновению неопределенности приводит тага® уменьшение размерности задачи путем агрегирования исходной модели местности. Под агрегированной моделью понимается пара <ЛГ,ф'>, где блочная матрица, элементами которой являются квадратные блоки матрицы М; <р'- отображение Р, где Р- пространство

интервальных чисел или нечетких множеств. Основная трудность при агрегировании состоит в построении отображения ф', т.к. каждая элементарная область М^ , полученная в результате агрегирования, уже не будет однородной. Кроме того, неясно, какой должна быть степень агрегирования модели. В главе рассматриваются различные способы формирования ф' (М^).

Рассматривается также вопрос нахождения оптимального коэффициента агрегирования на примере построения кратчайшего пути в графе. Трудоемкость' решения задачи - при . оптимальном агрегировании оценивается величиной 0(И 4/2), где N - количество элементарных областей исходной модели местности.

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

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

интервальными длинами ребер. Показано, что в таком графе может существовать не один кратчайший путь между двумя вершинами,■ а несколько несравнимых. Выбор к несравнимых решений задачи может быть сделан на основе привлечения дополнительных. критериев. В качестве дополнительных критериев могут быть предложены: ширина интервала длины найденного кратчайшего пути; середина такого интервала; 1фитерий, отражающий определенные технологические или другие особенности прокладки пути.

В работе описывается алгоритм нахождения к кратчайших несравнимых путей от одной до всех остальных вершин графа. Алгоритм работоспособен на ориентированном связном графе G, имеющем N вершин. Трудоемость алгоритма оценивается величиной 0(кг-N-log N).

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

Задачи (2) и (3) являются KP-трудными, т.к. являются обобщением задачи (I). Доказательство того, что задача (I) является .SP-трудной строится путем сведения известной ffP-трудной задачи о минимальном покрытии к данной задаче.

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

Пусть исходная задача оптимизации имеет вид

Р(х) ->mtn, х€Х. (4)

U(z)=(U1(x),...,Um(x)) - вектор частных 1фитериев. Частные критерии называются монотонно. соглаЬованными, если для любых х\хп € X из неравенств Ut(x') « U^x"), V А=1,т следует неравенство F(x')^P(x").

В соответствии с декомпозиционным подходом глобальный экстремум задачи (4) достигается на множестве эффективных решений задачи ü(x) - (V ^х),...^^)) -> min, х £ X.

Пусть Р и Р - множества эффективных решений' в пространстве критериев и пространстве решений соответственно. Тогда задача (4) сводится к задаче Т(х) -у min, х е Pz .'

Во многих случаях мощность 'множества Р„ существенно меньше, чем мощность ' исходного, множества X. Поэтому построение

аппроксимации F„ и последующий поиск экстремума Р(х) имеют меньшую трудоемкость по сравнению с исходной задачей. Кроме того, декомпозиционный подход позволяет свести исходную «VP-трудную задачу к последовательности задач класса Р. Решение каждой частной задачи позволяет построить верхние и- нижние оценки функции Т(х).

Для задачи (I) возможно выделять следующие частные критерии: и1(Т)= ^ ти -> min , Ted (5)

'(i.J)tT

Ü2(T)= 1 vtJ-iitJ(T) -> min , T € П (6)

fi.jjer

Задача (5) представляет собой задачу о минимальном стягивающем дереве (МСД) на множестве стягивающих деревьев Q, и принадлежит классу Р. Задача (6) - задача о построении дерева кратчайших путей, и также принадлекит классу Р.

Условие монотонности выполняется, так как P(T)=U1(T)+U2(T).

Для задачи (I) возможно построить разбиение X,'монотонное по одному из .частных критериев ПТ,. Указанное • разбиение позволяет осуществить быстрый равномерный проход вдоль одной из осей в пространстве критериев. ' *

Для решения задачи (I) предлагается следующая схема. Строится многопроходный алгоритм,' основанный на построении множеств которые, являются приближением, множества Ри(?х)

на й-том проходе'. Число эффективных точек з P^fP^J от прохода к проходу не убывает, что гарантирует построение' множества ?иСРх) ■ Множества Р^' и Р^ позволяют на каждом проходе строить верхнюю оценку и используются для нахождения приближенного решения задачи.

Как отмечалось выше, точное построение Рц ^ практически нереализуемо, поэтому строится его аппроксимация Р,;. Для этого предлагается использовать модифицированный алгоритм Габова генерации всех остовоз в порядка возрастания веса. На предварительном этапе строится множество СР^ , заведомо включающее в себя р . Для' этого определяются следующие величина:

U1.= min U.(T), Т = сг&гЛп UAT), vi = min ÜJ?},

теп ' тш 1 11 гШ 2

T*= argnlTi U9(T). I/f = atn и.(Г), al = и2(Тш),

гШ ■ i(Q '

CP£ = lu], up « rof, Up. Pu= W(T9), U(T*)}.

В процессе генерации для эффективных точек вычисляется значение критерия F(T). Алгоритм завершается лисЗо после выполнения заданного числа проходов И, либо после того, как будут сгенерированы все-остовы, не превосходящие по весу Т*. При M -> со будет получено точное решение задачи (I).

Для алгоритма генерации стягивающих деревьев доказана оценка трудоемкости 0(k-E-a(E,V) + E-log Е), где к - число сгенерированнынх деревьев, Е - число ребер графа G, V - число вершин G, a(E,V) - функция Тарьяна.

В четвертой главе разрабатываются алгоритмы решения задачи синтеза транспортной сети в условиях внешней и внутренней неопределенности;

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

Условие согласованности . ОП является обобщением условия монотонности критериев в'детерминированном случае, а именно: ОП т) согласовано с отношениями тогда и только тогда, когда

из того, что. Vi х' доминирует х* по ОП г>{ следует,что х' доминирует х" по ОП Т}. В случае согласованных ОП множество не доминируемых решений по ОП т| содержится во множестве недоминируемих решений по векторному ОП (г>;,..., v ).

Для интервальных оценок ОП вводится естественным образом: два интервала If=la}, bf] и I2 =[а2. Ь21- являются несравнимыми тогда и только тогда, когда (bf-a2)-(af-b2) < О. Интервал I ■доминирует интервал I2 < 12) тогда и только тогда, когда а2 > .Ь, - Решением задачи является множество недомшшруемых интервалов.

Векторное отношение предпочтения для многокритериальной

задачи (U^x), U2(x).....-> min , x € X с интервальными

параметрами задается ■ еледузащим' образом: каадой альтернативе х в

пространстве критериев соответствует m-мерный параллелепипед

D(x)=Ca;,bí3 х 1а2,Ъ2] х ... х £аот,Ьт'] , где 1а{,Ь4] - интервал

значений критерия Ut(x). Параллелепипед Л(х' ) доминирует

параллелешшед D{x") тогда и только тогда, когда V i b't < aj.

В работе предлагается-выразить ОП для нечетких оценок через

ОП для интервальных оценок. .4 именно, нечеткое множество v

доминирует нечеткое множество ц на уровне a тогда и только тогда,

v ц vu.

когда Ха доминирует Ха, где Ха и Ха - множества a-уровня

соответствующих нечетких множеств. Множества v и ц несравнимы

тогда и только тогда, когда несравнимы соответствующие интервалы.

Аналогично вводится векторное ОП на уровне а.

v

В случае,если оценки являются невыпуклыми ( Хп не является

V u

непрерывным ), вместо Ха берется апроксимируиций интервал, нижняя

граница которого совпадает с минимальной нижней границей, а

верхняя с максимальной верхней границей интервалов, составлящих v

Ха. При этом множество недомшшруемых решений может лишь увеличиваться.

Задача (2) с нечеткими значениями аир классифицируется как задача математического . программирования с нечетко описанными параметра;® и сводится к общей задаче нечеткого математического программирования. Традиционный метод ее решения является неприемлемым из-за большой размерности множества допустимых альтернатив и сложности целевой функции.

Пусть ®fs,y,a,pj= + ~ стоимость сети s 0

(i.J)ta

потоком у. Тогда выполняются следующие -Леша и Утверждение ::

Лемма. Пусть a и р-нормальные выпуклые нечеткие подмножества-R\, v= а-и + р-и, где ,u,v € r\, тогда Vl>f, v¿, v = a-u1 + p-u,, v2= a-u2 + p-u2, таких что и^ u2, vv2, v1 t v2 по Н0П 17^, индуцированному естественным порядком ($) на числовой оси, где ь означает "эквивалентно либо строго предпочтительнее".

Утверждение. V s £ S, ^сеть-дерево t с е, такая что V' у €

$(t,y(t),a,ßj ь Ф(а,у,arß), где y(t) - поток по дереву t, Уе-потоковый многогранник, задаваемый условиями полного перетока'.

Следуя общей схеме решения, для задачи (2) с нечеткими оценками выделяются частные критерии (5) и (6) и далее, в ходе генерации остовов в порядке возрастания веса, строится множество недоминируемых оценок альтернатив Р в пространстве критериев V-, и Ug.

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

Для решения задачи (3) выделяются частные задачи :

_ А»

V1(T}=ZWiJ -> JBlft , Г € Q , (7)

(I.JKT

i

Ü2(T)= I "tj'VijW ->min,T€Cl. (8)

(t.J)iT

В работе приводится алгоритм решения задачи (3). В ходе генерации эффективных остовов формируется множество решений, несравнимых по стоимости строительства и" эксплуатации транспортной сети. Приводятся также алгоритмы решения частных задач (7) и (8).

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

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

Приводится описание и условия, применения следующих программных модулей: . .

- построения множества \ несравнимых _ кратчайших путей . на интервальной модели местности;, '

- агрегирования цифровой модели местности;

- построения множества несравнимых транспортных сетей в условиях неохфеделешости исходной информации;

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Научные и практические результаты состоят в следущем:

1. Анализ задачи проектирования транспортной сети в условиях неопределенности исходной информации показал:

- использование существующих методов синтеза транспортных сетей затруднено из-за большой размерности решаемых задач. Увеличение трудоемкости в случае учета неопределенности накладывает

- дополнительные ограничения на использование традиционных методов;

- в настоящее время отсутствует методика синтеза транспортных сетей, позволяющая учитывать неопределенные факторы, начиная с этапа создания моделей;

2. Проанализированы факторы, влияадие на неопределенность ' параметров транспортной сети;' проведена -классификация

неопределенных факторов по способу их влияния на параметры сети;

3. Предложен подход к агрегированию (снтшиы размерности) модели местности и 'получению" адекватной недетерминированной модели . местности, ■ вычисляется оптимальный коэффициент агрегирования;

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

интервальные и нечёткие оценки;

5. Разработана методика проектирования транспортных сетей большой размерности в условиях неопределенности исходной информации; включающая следующие компоненты:

- формирование экономико-математических моделей задачи синтеза структуры транспортных сетей з условиях' различных тгягсз непределенности исходной информации;

обобщение на случая кеоггоеделенности схемы рзог! недетерминированной задачи. основанной на использовании декомпозиционного подхода. Указанная схема позволяет своста исходную АТ-труднуо задачу к решению последовательности задач полиномиальной трудоемкости и учесть • чеопрэделенностъ исходной информации практически без увеличения тоудосжсстя:

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

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

7. Осуществлена программная реализация разработанных алгоритмов, реализующая методику проектирования транспортных сетей большой размерности в условиях неопределенности исходной информации.

По теме диссертации опубликованы следующие работы:

1. Демченко А.И., Пельцвергер Б.В. Применение интервального анализа для построения магистрального хода трассы: Тезисы докладов девятого Всесоюзного симпозиума "Системы программного обеспечения решения задач оптимального планирования", M., 1986.-с.134-135 •

2. Демченко А.И., Пельцвергер Б.В. Построение магистрального хода трбООЫ ЗЗхОмиСйЛЬной дороги с учетом имеющейся неопределенности цифровой модели местности // Известия . ВУЗов. Строительство и архитектура.- 1987.- MI

3. Демченко А.И., Пашков A.B.,' Пельцвергер Б.В. Цифровые модели анизатропной среды для задачи оптимального планирования траекторий: Тезисы докладов II Всесоюзного семинара "'Роботы и гибкие производственные системы", Челябинск, 1988.- с.46-47

4. Демченко А.И., 'Пашков A.B., Пельцвергер Б.В. Оптимальное агрегирование в задаче планирования трассы на цифровой модели местности: .Тезисы докладов десятого Всесоюзного симпозиума "Системы программного обеспечения решения задач оптимального планирования", M., 1988.;- с.145

5. Демченко А.И. . Использование интервальной математики при агрегировании цифровой модели местности: Тезисы докладов конференции по интервальной математике, Саратов, 1989.- c.S-IC

6. Демченко А.И., Пельцвергер Б.В., Хавронин О.В. Методы синтеза транспортных 'сетей с учетом различных типов неопределенности исходных моделей: Тезисы докладов четвертого Всесоюзного

совещания "Методы и программы решения оптимизационных задач на графах и сетях", Новосибирск, 1989.- с.55-57

7. Цыганков В.А., Пельцвергер Б.В., Демченко А.И. Построение магистрального хода трассы с интервальными значениями стоимости элементаной коммуникации // Алгоритмы и программы.- 1989.- М2, Ж60890000236

8. Цыганков В.А., Пельцвергер Б.В., Демченко A.M. Построение сети минимальной стоимости в условиях неопределенности исходных данных // Алгоритмы И программы.- 1989,- J6I2, .№0890000238

9. Демченко А.И., Пельцвергер Б.В., Хавронин О.В. Синтез транспортных сетей с учетом неопределенности исходных моделей. Препринт ВЦ СО АН СССР, Красноярск, 1990.- Ш7

10. Демченко А.И., Пельцвергер Б.В., Хавронин О.В. Отношения предпочтения в многокритериальных задачах с неопределенностью. Управление и микропроцессорная техника автоматических систем: Сборник научных трудов.- Челябинск: ЧПИ, 1990.- с.9-11

11. Демченко А.И. Синтез транспортных сетей в условиях неопределенности исходной информации: Труда семинара по интервальной математике, Саратов, 1990.- с.10-16

12. Демченко А.И., Пельцвергер Б.В., Хавронин О.В. Синтез структур транспортных сетей в условиях неопределенности исходной информации на основе декомпозиционного подхода // Известия АН СССР. Техническая кибернетика.- 1990.- ЛЗ.

13. Demchenko A.I., Khavronln O.V., Pelzwerger B.V. Models oi transport networks under conditions of. Indeterminate Initial information: Сборник научных трудов "Многокритериальные динамические задачи при неопределенности", Орехово-Зуево, 1991 14* Demchenko A.I., Panyukov A.V., Pelzwerger B.V. The fuzzy models for the transport networks structure .synthesis problem. The 6-th World Conference on Transport Research, Lyon, France, 1992 ;■ '

15. Demchenko A.I., Khavronln O.V., Pelzwerger B.V. Synthesis of Transport Network Structures under * Uncertainty in Initial Information. Proceedings of International Conference on interval and stochastic methods in science and engineering, Moscow, Russia, 1992 • • .

Демченко Александр Иванович

ПРОЕКТИРОВАНИЕ КРУШШСЩТАЕНУХ ТРАНСПОРШЕ СЕТЕЙ В УСЛОВИЯХ. НЕОПРЕДЕЛЕННОСТИ ИСХОДНОЙ ИНФОРМАЦИИ

■ Специальность. 01.01. II -"Системный анализ и автоматическое управление"

• Автореферат.диссертации_на соискание ученой степени канд. техн. наук

Подписано к печати 20.04.93. Формат 60X90 1/16. Печ. л. I. 7ч.-изд. л. I. Тираж 100 экз. Заказ 93/236.

ГСП издательства ЧГГУ.45408СчгЛелябинск, пп.иы.В.ПЛенина, 76.