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

РГ5 ОД

российская академия наук

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР 7- ДЗГ 2О0П

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

туев сергей вадимович

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

Специальность 05.13.18 -теоретические основы математического моделирования, численные методы и комплексы программ.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ч

Москва - 2000 год

Работа выполнена в Вычислительном Центре РАН

Научный руководитель:

доктор физико-математических наук, профессор В.Р. Хачатуров

Официальные оппоненты: доктор физико-матема-

тических наук, профессор В.К. Леонтьев

кандидат физико-математических наук, С.Н. Шибаев

Ведущая организация: Институт системного анализа РАН.

Защита состоится" " ¿4 ьонЖ 2000 г. в часов

на заседании диссертационного совета Вычислительного Центра РАН Д002.32.05 по адресу: 117967, Москва, ул. Вавилова, 40

С диссертацией можно ознакомиться в библиотеке Вычислительного Центра РАН

Автореферат разослан "

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

" 2000 г.

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

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

Приведем краткое описание некоторых работ по данной тематике:

В исследовании Г.Ф. Вороного рассматривались диаграммы разбиений в работе, посвященной примитивным полиэдрам. Разбиения рассматривались Л.В .Канторовичем в задаче планировки о перемещении земляных масс. К.Роджерс рассматривал диаграммы Вороного в работе, посвященной покрытиям и укладкам множеств.

Различные типы задач оптимального размещения рассматривались В.П.Черениным и В.Р. Хачатуровьш и его учениками.

Работы Е.М.Киселевой, Н.З.Шора, С.А.Ус посвящены решению многопродуктовых задач оптимального разбиения с размещением центров тяжести подмножеств, задач с нечеткими ограничениями. С.А.Пиявский рассматривал разбиения в задаче размещения орбит. В.З.Беленький - в моделях кристаллизации. И.А.Ушаков рассматривал размещение во времени моментов обработки заявок с минимизацией суммарного времени ожидания и ограничениями на число заявок единовременной обработки.

Задачам размещения объектов и зонирования территории с распределенным потребителем с оптимизации его обслуживания тосвяхцены работы Bela Bollabas, M.Freidman, H.W.Corley, S.D.Roberts, M-Fraasis. Обзор алгоритмов разбиения множеств приведен в книге ¿.Препараты и М.Шеймоса по вычислительной геометрии.

Цель работы. Настоящая работа посвящена:

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

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

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

Научная новизна.

В работе предлагается подход к построению и исследованию аппроксимирующих моделей описания и развития объектов с

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

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

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

Практическая значимость работы.

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

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

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

Внедрение работы. Разработаны системы математического обеспесения и выполнены расчеты по конкретным месторождениям, среди них, Усинское (Коми,1978 год), Одопту-море и Чайво (Сахалин,1979), Белый Тигр и Дракон (Вьетнам, 1980), Каражамбас (1982), ряд месторождений Черного и Азовского морей (1984), "28 апреля"(Каспий,1985), Тенгиз (1987), Сандивей (1990), Лебяжье (1992). Разработана система оценки стоимости миниэлеваторов с учетом коньюктуры рынка для Ставрополья (1991 год).

Аппробапия работы. Основные результаты докладывались на • V и VII Всесоюзных симпозиумах "Системы программного обеспечения решения задач планирования" в г.Нарва-Йыэсуу, 1978,1982 .

- VI Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" в г.Пушкино, 1980 г.

- Всесоюзной конференции "Экономика освоения океана" в г.Владивосток, 1985 г.

- IX Всесоюзном симпозиуме "Системы программного обеспечения решения задач планирования" в г.Минск, 1986 г.

- Международном симпозиуме по оптимизации в г.Иркутск, 1986 г.

- Международной выставке "SYSTEMS'96" в г.Мюнхен, ФРГ,1989 г.

- Международном симпозиуме VTT Infonnation technology and economics modelling, Technical research center of Finland, Helsinki, 1990 r.

XXI Международной конференции "САПР-94 - Новые информационные технологии в науке и бизнесе" в Гурзуфе,Крым , 1994 г.

- II Школе-семинаре "Программное обеспечение проектных и геологических служб нефтегазовой промышленности", Москва, 1994 г.

- Выставке-конференции "Компью-Маркетинг'96", Москва, 1996. Публикации. Результаты диссертации опубликованы в работах 1-13. Объем и структура работы. Работа состоит из введения, пяти глав, заключения, списка литературы и приложения. Общий объем работы составляет 161 страницы машинописного текста (основное содержание -136) и включает 30 риунков, список литературы из 41 наименования.

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

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

В главе 1 "Содержательные постановки и основные математические модели размещения центров переработки (стоков) распределенного ресурса" приведены пять типовых постановок, описаны геометрические свойства их решений (разд. 1.1). Используются обозначения: f(x), х еХ - функция плотности ресурса, определенная на XdE' - измеримой плоской области распределения ресурса, М(Х') = ]Л„ f(x)dx- объем, сосредоточенный в подобласти Х'сХ, ZieE2, iel - {1,...,п} - стоки - центры сбора ресурса, Z=<2i,...,z„> или Z={z) - их наборы, 2п- вектор, или подмножество множества возможных точек плоскости Z0., так что Z <zZ /:'* или Z о? 27", t(z,x), z,x ei;? - функция стоимости транспортировки, FT(XI) = J t(z, x) f(x)(Lx - стоимость транспорта сосредоточенного в Х'сХ ресурса в сток г,

A=<Ai,...,An>- система подобластей А,сХ, A,rv\j 0Ь определяющая

разбиениеX, если U,eZ Л, = Х, или укладку, если V!eZ Л, сХ.

а «//,..,,й„> - ограничения на объемы ресурса в Л.

Задача зонирования. При заданных стоках Z требуется определить разбиение Я области X, минимизируя суммарные транспортные затраты с ограничениями на объемы ресурса в зонах FT(Z) = mmJ\FT(Z, Л)\М(А,) < а,!, при этом множество решений - UT(Z,a) = arg min {FT(Z, /1!|М (Л,) < ß,-),

Задача размещения. Определить размещение стоков Z, минимизируя суммарные транспортные затраты: /■'" = min е Я2"}.

Задача максимального покрытия. Требуется определить размещение системы кругов & радиуса Л; с центрами в стоках -„ максимизируя объем ресурса F" = М(А") = Jr j\x)dx, сосредоточенного в

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

Задача размещения с жестким прикреплением к ближайшему стоку имеет двухэтапную постановку. На первом этапе определяется разбиение А е Ur(Z) в условиях задачи зонирования без ограничений на объемы ресурса, Ограничения учитываются а втором этапе при размещении стоков Z _I" = mmz [l-T(Z}\M(,A,) < (¡„А, еДе O'CZ)}._

Представление f(x) определяется разбиением на зоны постоянства -а'\ задается ориентированным планарным графом Г1 =(Vf,!■:'), с ребрами e^Ef связываются значения /; и справа и слева по их ориентации.

В разд. 1.2 вводятся произвольные системы множеств А = {AJ, U = {Л}-множество раскладок и базовые критерии:

- объем стока - F.= J /(хук;

Аг

- транспорт стока - Ff = J i{z^)f(x)(h\

- отход стока - 1\ = Л, = max«^ t(z,x);

- остаток - Ff = М(X) - ., К ■

Формулируется универсальная задача (УЗ):

FV(Z,A) = 2, z + ¿„ , WFJ + v°F0° + .

«f(Z,Ä) = ¿£Z + 2„z И-К7 + vy°/ö0 + rtf S j 6 7 •

Показано, что описанные постановки являются модификациями УЗ.

Вводится 20 - фиктивный сток, i(z0,x)s0, F0TsO,F0ÄsO, ¿(20.х)<Л, ЛаО, далее Z=<zm2,,...,z„> - расширенные, СГ={/Г} - множество нерасширенных раскладок и = А/(X) - ¿!£Z- /'2'J = F° = /(*>& .

Формулируется расширенная УЗ:

F"(Z,A) = Z„z + l v'K + Z„ ,/'/;." > min ,

=Z2EZ +I!£Z +-ZzeZ 5*„

при этом ее решение - F(U) = mm ^„¿^{F0 (Z,A)\R" (Z, Л) < aj,j e J}, И множество решений - UF(U(Z)) = argmin,<,v^z {F"(Z,A)IR^ (Z, A) £ J).

В разд. 1.3 устанавливается связь между решениями УЗ на произвольных раскладках и на расширенных покрытиях и разбиениях. Уточняются и вводятся определения:

Un <zü - множество покрытий А = {АгJ, z е Z,т.ч. X = UkZ Л2, t/Y с U - множество укладок л = {иг},. Л2 пЛг. = 0, z,z' е Z, Ur = f/n сU - множество разбиений X = XJ^Z Лг, Ai = 0, С/Е -U\{U?-множествособственных раскладок,

= Un\Ur - множество собственных покрытий, U"" = Uy \ 17е- множество собственных укладок. U" с 6'" - множество приведенных покрытий, т.ч. Л0 -/V\U Z Лг. Раскладки могут быть расширенными - или нет U'(Z ),

решения и множества решений - F{U'), U'\U') или F(U'(Z')), Ü!\U'(Z')).

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

Отмечено, что множество решений УЗ на расширенных покрытиях U* (U"(Z)) может быть шире множества ее решений на расширенных UF(Ur(Z)) (пример - задача минимального радиуса покрытия) и включает множество решений на расширенных приведенных покрытиях Uh (Ug(Z)).

В разд. 1.3 для дальнейших исследований свойств решений УЗ вводятся наборы функции принадлежности (прикрепления) - g(x) =< > и базовые критерии, определенные на прикреплениях. Определяется расширенное множество функций принадлежности

G(Z) = =< >,г s Ztх g X\t^ JT20) = >0,z e Z] Для прикреплений формулируются УЗ и расширенная УЗ, вводятся:

n-.G-tU - g-покрытия, так что А, =suppg2(x) = {х е X\g!(x)>0} для А, еА= 7T(g), U" = 7i(6') сU- множество g-покрытий - образ G по л,

v.G -> U -отображение g-укладок, А, {х с- X\g,(x) - 1} для Аг е А = iXg),

И] = v(G) cU - множество g-укладок - образ G но отображению и, Uft■ = множество g-разбиений.

Ge = {ge G\n(z)= iKg) e i/Jj - множество разбивающих прикреплений, p:Gf U - отображение g-разбиений, p(g) - n(g) = iXg), geGp. Прикрепления g(x) e G(Z)\G?(Z) - покрывающие, их я(g) - покрытия.

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

В главе 2 "Методы исследования универсальной задачи" УЗ исследуется, методами исследования усредненной задачи (в терминологии Голыытейна), с использованием функции Лагранжа. В разд. 1.1 вводятся и =< иj >,j е / - двойственные переменные УЗ, l(z,x,u) = w"(u)t(z,x) + v'(u), где v'(u) = v' + Y,jt]UjV], w'-(u) = r+ HjsjUjW'i , = r' + H]eJ"//•

функция Лагранжа - UZ.g.u) = + z r*(u)R, +4!'(Z,g,u),

где V(Z,g,u) = £EJXg,{xiw\u)l{z,x) + v>(u)}f{x)dx

и формулируется максминная задача

minjeG max^o HZ, g, u) = maxct minJ6G IXZ, g, u) = max^0 UZ, u), Определения. Множества G°(Z,R,u) называются базовыми

решениями: -

G°(Z,R,u) = ig(x) e GlI^ww*,(*) = U,00 >0,z e Z*(x,R,u)} Z°(x,R,u) = argmin^z{l{z,x,u)\t(z,x) < R,,z e Z}cZ, здесь R, - maxIf, g,(.x)r(z,x),z e Z - ограничения.U

g e G"(Z,R,u) - базовые прикреплениям

G" = {G"(Z,R,u}) - множество базовых решений (множеств прикреплений). □ Базовые решения зависят отЛим, как от независимых переменных. Доказан ряд теорем, в которых показано, что решения, оптимальные значения функционалов УЗ на расширенных разбиениях и на разбивающих прикреплениях равны, при этом множества их решений эквивалентны, что решения УЗ на раскладках и расширенных УЗ на прикреплениях и на разбивающих базовых прикреплениях равны, при этом множество решений расширенной УЗ на прикреплениях принадлежит множеству базовых решений GT{G) gGb. На основании доказанных теорем, утверждается, что решение УЗ на раскладках достаточно искать, как решение расширенной УЗ на базовых разбивающих разбиениях.

В разд. 2.2 вводятся понятия ядра и перекрытия раскладки. Для подмножеств множества раскладок вводятся понятия накрытия, ядра и

перекрытия (границы). На множестве раскладок вводится частичный порядок, мажорирование и интервал, для этого определяются:

<х11 иу- отображение, определяющее ядро раскладки А-<Аг > -укладку Аг = а(А), т.ч. А; = А, Ш2.б7Л,г1 Д,,

у: С/ ->£/- отображение, определяющее перекрытие (границ}') раскладки А =< Аг > - А' = у(Л), т.ч. /I,1 = А2 \А?, где А 2 = о(Л). □ П = {(/'}, (/'с £/" - множество подмножеств покрытий. Р - {1/'},(/'с£/р - множество подмножеств разбиений. т{П->С/п - отображение, определяющее А* ~т|(Сг') £ ип- накрытие подмножества покрытий (/'<= П, Л! = и^.^,,. Л'2.

£П-»£/ - отображение, определяющее А'= 1(1Г) е 1/п - ядро подмножества покрытий Л е V е П, л; = г^. А.

Г:П->{7 - отображение, определяющее А1 - Г(и') - перекрытие (границу) подмножества покрытий 6" е П, А' = А* \ Аг.

Отмечается, что в рамках принятых определений компоненты перекрытия разбиения (границы зон) пусты. Способом описания границ решений УЗ на разбиениях будет описание границ множества ее решение-Ядро подмножества покрытий V может быть собственной раскладкой, ядро и накрытие подмножества покрытий II' могу г ему не принадлежать, а перекрытие подмножества V является собственной раскладкой - Аг е 0'1к.

>- мажорирование (частичный порядок) на Г/хС/, для Л1 >А2, если имеет место покомпонентное включение - А[ э 4г,гег.

т:С/х[/->Р - интервал [А',А+], для А+>Л~ - отображение, определяющее максимальное множество разбиений С/'=т(А+,А')с1/? с Ядром А~ = 2(!7') и накрытием А+ = г\(Ь").

Интервал между ядром и накрытием - способ описания множеств решений УЗ на покрытиях и разбиениях.

В разд. 2.3 устанавливается структура множеств решений УЗ на разбиениях и покрытиях, их ядер и накрытий.

Определения Множества разбиений и°(2,К, и) будем называть базовыми или базовыми (допустимыми) решениями, если их накрытие Аа*(г,Яи) = п(1'с) и ядро А' С/.Ли) = пи0) имеют следующую структуру А? (2, /г, и) = е Х\/(г, лг, и) < ¡{у, х, и), у е 7:* (.х, Я) \ {г}}, А^ (2, к и) = {хе ХЩг, х, и) < Ку. х, и), у е Т (х.Ю\ {г}}, 2*{х,К) = {ге2\1(2,х)<Яг}с2, Дг =тахк^ г(г,х),г е 2 В и"(2Л,и) = т(А"* ) = [Л'\/Г 1Д А е и°(2,Я,и) - базовые разбиения.□ и" = ¡и"(>с,Ни)} - множество базовых решений.□

Отмечается, что базовые решения зависят от R и и, как от независимых переменных. Доказан ряд теорем, в которых утверждается, что решение УЗ на расширенных разбиениях достаточно искать в классе базовых решений, что ядро A" (ZJtu) = КС/') базового решения u"(Z,R,u) являться ядром его накрытия A°'(Z,R,u) = а(А°*) и базовое решение U"('/,j{,u\ е и" вполне определяется своим накрытием A'"(Z,R,u) = rjic/").

Отмечается, что накрытие Л:" (Z,R,u) = т(и,г) является собственным покрытием, его перекрытие (граница) имеет непустые компоненты и совпадает с перекрытием (границей) базового решения U°(Z,R,u) -Аот = у (А1") = Г(и°), что на границах (компонентах этого перекрытия) принадлежность точек той или иной зоне стоков не влияет на значение целевого функционала. Накрытие A^iZ.R.tti-vf.U0) базового решения U°(Z,R,u) е Uв является максимальным покрытие, а ядро A ' (Z,R,u) = Ц(/с) -минимальной укладкой. Они определяют верхнюю и нижнюю границу для базовых разбиений из U°(Z,R,u)eUB. Таким образом, анализ решения - это описание его ядра и накрытия.

Доказана теорема, утвеждающая, что дня базового прикрепления g е G"(Z, R,u), ^-покрытие и(g) мажорируется накрытием базового решения А0" - A°'(Z,/<,u) = rj(l/'J)> g-укладка a(g) мажорирует ядро базового решения

А0- = А(Z, К,и) = ') и ji(g) мажорируют <Xg) -

----

Отмечается, что множество решений на прикреплениях, в определенном смысле, шире множества решений на раскладках:

Во-первых, для каждого покрытия А е 6'п- решения на раскладках, Gr'(A) может содержать неединствезшое решение на прикреплениях.

Во-вторыХ, для покрывающего прикрепления geG"(Z,R,u) покрытие А = n(g) не всегда является решением задачи на раскладках.

Множество решений расширенной УЗ может содержать собственные покрытия (задача минимального радиуса покрытия).

Сформулированные результаты позволяют:

- сузить поиск решений УЗ на раскладках или на расширенных покрытиях до множества расширенных разбиений;

- перенести метод решения УЗ с использованием функции Лагранжа с прикреплений на разбиения и покрытия;

- описать решения УЗ на нерасширенных раскладках в терминах прикреплений совместно с расширенными покрытиями.

В разд. 2,4 для исследования геометрических свойств решений УЗ вводятся определения параметрических и радиальных, собственных и свободных, внешних и внутренних (участков) границ. Введем обозначения:

S(z,R,) = {.v е X\t(z,x) <R,\- шар радиуса /<„

= {х е Х\Пг,х) = К,)- сфера радиуса К,, = S{z,R,)r^S^z,R)l) = {х б Х\1(г,х) < < К,} - гу-бисегмент.

В базовом решении и" е и" рассматриваются:

Г* = дХ и Г? = Гх пД5'- внешние границы областиXи зоны г е X, Гг = \А'г',П, еГ - внутренняя фаница зоны стока ге2 в О'0, так что Т,г = Г, оГ,- граница зон стоков г, у е Ъ и Гг = Г^,

Л/, = {>' е г\Г2Г * 0}- множество соседей стока г б г, Мг = Л/г \ {г,,}, Гг; = г„ - параметрическая граница стоков г, >' е /, г; = Гг? \ Г^ - радиальная фаница стоков 2,^62, при этом г;;, если г; с Р{2, щ, г;у , если г; с Г(У,я) и т;; = г;-, Г2,о = Г,ц - граница стока г е 7 с фиктивным стоком г0- свободная, Т.у = Г, пГ; - фаница с нефиктивным стоком у е - собственная. Граница Г^ = Г2/ о5гг определяется уравнением 1(2.х,и) = 1(у,х,и) (**) и зависит от параметров и, поэтому она называется параметрической.

Свободная параметрическая фаница так же имеет радиальный характер, поскольку уравнение (**), в силу е(г0,л) = 0, сводится к 1(1, х) = К, (и).

Доказана теорема, утверждающая, что в накрытии и ядре базового решения зоны нефиктивных стоков принадлежат замкнутым шарам $"{г,Ят), внутренние границы нефиктивных стоков (компоненты перекрытия решения) принадлежат замкнутым гу-бисегментам 8г1 = 8(г,Я2)г^8(2,Ят), внутри открытого 2^-бисегмента 5,г определяются

уравнением (**), а вне - лежат на одной из сфер Д г, К.) или Р(гЛу). В любом базовом разбиении зоны нефиктивных стоков так же принадлежат замкнутым шарам Л'и, ).

Собственная фаница является суммой параметрической и радиальной Г,г = Г'у а свободная является, либо параметрической Гг0 = Гу,, либо радиальной Г.0 = Г^ и принадлежит сфере Р(2,1<.\, если (**) определяет линию. Компонентами накрытия базового решения являются замкнутые шары ,?(г,Лг), компонентами ядра - а

накрытия - замкнутые гу-бисетменты Г7)1 = если уравнения (**) не определяют линий. При этом решение УЗ содержит собственные покрытия.

Приводятся примеры конкретных функций транспортных затрат. В реальных задачах их вид вместе с типом офаничений определяет конфигурацию зон стоков и вычислительную сложность алгоритмов. Глава 3 "Методы исследования задачи зонирования при фиксированных стоках" посвящена методам исследования задачи зонирования при фиксированных стоках. В разд. 3.1. дана ее формулировка, доказаны три

леммы для исследования ее решений и построения алгоритмов.

Задача зонирования рассматривается, как редукция УЗ к задаче минимизации по разбиениям (покрытиям) при фиксированных г

А)=л?+«п+гч? -

В разд. 3.2 и 3.3 доказаны теоремы с формулами градиентов и вторых производных ргу по двойственным переменным и для определения параметров границ. Сформулирована УЗ с индивидуальными ограничениями - + <«„ге2.

В разд. 3.4 показана применимость метода Ньютона для определения параметров границ в задачах рассматриваемого класса с индивидуальными ограничениями. Приведена общая схема алгоритмов и описаны алгоритмы вычисления необходимых функционалов. Отмечено: первая производная является невязкой ограничения, для ее вычисления достаточно определить взвешенную с учетом Дх) площади зон стоков.

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

Р,у = /(7)^7), для 2, у 6 АС, р,0 = £ ЛуЫЩ) , для 2бМ;,

1г1у ху гО

здесь г,г = К2,у) - расстояние между соседними нефиктивными стоками г и у, а интеграл является взвешенной длиной параметрической границы.

Приведена общая схема алгоритмов:

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

Определяется наложение (пересечение) временно оптимального решения - разбиения А с разбиением А1 (картой Гг), определяющим плотность ресурса. В результате генерируется разбиение карты г' на подграфы Г/, принадлежащие подобластям А,- разбиения А.

На пересечении разбиения А с картой Гг вычисляются лагранжиан Цг,и)> его градиент, первые и вторые производные по и. Значения Необходимых функционалов определяются в процессе последовательной обработки ребер подграфов Г/ и границ зон Л, - вычислением некоторых функций координат вершин Г{, стоков 2 с2 и параметров границ и.

В главе 4 "Размещение центров переработки распределенного ресурса" рассматриваются задачи размещения сток]в в двух постановках -на плоскости Z с Е1" и в комбинаторной постановке - на множестве

подмножеств некоторого конечного множества

В разд. 4.1 рассматриваются две задачи размещения заданного числа стоков на плоскости. В качестве первой рассматривается сама УЗ, в качестве второй - редукция к минимизации только по стокам X е Е7" при фиксированных А е(/

Л) = +П + «гГ1 + Е2е2 г%* -> тт^.

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

Выведены формулы градиентов лагранжианов для определения размещения стоков гсТ. на плоскости. Приведены их выражения в конкретных постановках задач размещения. Полученные результаты позволяют искать локальные экстремумы градиентными методами.

В разд. 4.2 рассматривается УЗ размещения в комбинаторной постановке - на множестве подмножеств некоторого конечного множества 2. Набор ограничений редуцирован к индивидуальным блокам стоков, а в функционалах задачи нет отходов. Доказана супермодулярность целевого функционала и применимость алгоритмов метода последовательных расчетов, описанных в работах В.Р.Хачатурова и В.П.Черснина.

Отмечено, что присутствие отходов нарушает супермодулярность. Показано, что комбинаторная постановка ФЯ(>Г) = ттгг0 гтпгс2,

даже простейшей задачи минимизации сумм радиуса полного покрытия -= ]£2е2 Л, тш1(5, не удовлетворяет критерию супермодулярности. В главе 5 "Применение разработанных методов для решения конкретных задач проектирования. Компьютерная система оценки вариантов освоения месторождений на ранних стадиях изученности." описаны основные принципы разработки систем, структура системы и концептуальные модели проблемных областей для отдельных подсистем.

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

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

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

модель месторождения (контуры и глубины объектов, извлекаемые запасы, плотности распределения ресурса и начального дебита);

модель кустования для оценки вариантов используемых сеток скважин и стоимости освоения месторождения;

модель функционирования резервуара и очередности ввода объектов

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

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

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

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

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

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

скважин в кусте от числа кустов, суммарной стоимости бурения и сооружения кустов от числа кустов или отхода.

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

1. Скважины не интерферируют во времени - закон падения дебита зависит от момента ее ввода, но не соседних.

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

3. Скважины не интерферируют в пространстве (двумерном): ресурс, сосредоточенный в зоне скважины, извлекается только через нее.

4. Фильтрационные характеристика пласта, применяемые способы извлечения ресурса и воздействия на пласт описываются параметрическим законом падения дебита скважин по времени ц(г/т).

Предлагается процедура формирования динамики ввода скважин в кусте и динамики ввода кустов с учётом следующих критериев:

- максимизации извлекаемого с куста ресурса;

- минимизации длины бурения с куста;

- минимизации длины коммуникаций до текущего ядра;

- минимизации длины коммуникаций до введенного на предыдущей итерации куста.

Также учитывается критерий равномерного продвижения по фронту освоения, штрафует ожидание "в очереди" - выполненное число итераций после попадания куста в окрестность текущего ядра.

Таким образом, определяется динамика ввода скважин - ковер бурения и динамика добычи по месторождению.

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

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

- коалиционный критерий ¥7К = I ] 1(гх)/(:),Г(х)с1гс1х и

Ас А-^

- периметрический Г' = /(у)<й(7).

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

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

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

Модификации, обобщения и редукции моделей:

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

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

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

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

Меэкщентровые модели объединяют задачи с наличием связей между стоками, аналогичные дискретным постановкам типа задачи Штейнера-Вебера, в которых между стоками существует инфраструктура.

Мпожествеппоцсптровые модели характеризуются тем, что вместо

наборов стоков X = {г} рассматриваются наборы множеств стоков 7. = {х\. Множествами могут быть, сегменты прямых, ломаные, многоугольники, дуги окружностей а также конечные точечные множества.

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

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

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

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

- Система представления и многокритериальной оценки информации о территории с целью определения мест возможного строительства кустовых сооружений для Самотлора (1978 год).

- Система кустования в условиях малой изученности и учетом технологических ограничений на основе многовариантных расчетов и многокритериального анализа вариантов. Расчеты проведены для месторождений: Уса (Коми,1978), Белый Тигр и Дракон (Вьетнам 1980).

- Система кустования и размещения кустов на дамбах для подтапливаемых месторождения Каражамбас (Казахстан, 1982).

- Система кустования с учетом стоимости платформ, зависящей от глубины моря, для месторождения "28 апреля" (,Каспий, 1985).

- Система многовариантных расчетов для размещения ледостойких буровых платформ в условиях малой изученности (при незаданной сетке скважин с учетом неоднородности пластов) для Сахалинских шельфовых месторождений Одопту-море и Чайво (1979).

- Система размещения ледостойких буровых платформ в условиях малой изученности и возможно неполного освоения для Чайво (1981).

- Система совместного размещения платформ и скважин на газо-конденсатных шельфовых месторождениях в условиях малой изученности для ряда месторождений Черного и Азовского морей (1984).

- Система размещения складов продовольствия и оценки стратегий его завоза в ряде стран Африки для распределенного потребителя (1985).

- Система кустования с учетом технологических ограничений.

Расчеты проводились для месторождений; Белый Тигр (IVôo), Тенгиз (Казахстан, 1987), Сандивей (Коми, 1990), Лебяжье (Зап. Сибирь, 1992).

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

- Система для определения очередности ввода кустов и скважин (вариантов стратегий освоения) с учетом схемы кустования (1994).

- Система для определения очередности ввода расчетных элементов (с учетом очередности ввода кустов) для гидродинамических расчетов(1993).

- Система оценки вариантов строительства и стоимости мини-элеваторов с учетом коньюктуры рынка для Ставрополья (1991 год).

Публикации по теме диссертации:

1 Туев C.B. Задача размещения на прямой и плоскости при

размещении пунктов сбора" // Тезисы докладов, III Всесоюзная конференция по исследованию операций, Горький, 1978, cc.IlQ-111.

2. Туев C.B. Одномерная задача размещения пунктов сбора распределенного ресурса" // Техн. кибернетика, 1980,No.2, сс. 17-24.

3. Туев C.B. Оптимизация сбора и переработки распределенного ресурса // "Оптимизация и стабильность", ВЦ РАН,1980, сс.21-31.

4. Туев C.B. Алгоритмы разбиения территории для оптимизации сбора и переработки распределенного ресурса // VI Всесоюзный симпозиум "Системы программного обеспечения решения задач оптимального планирования" в г.Пушкино, М., 1980, с.169-170.

5. Хачатуров В.Р., Астахов Н.Д., Веселовский В.Е., Туев C.B.

О решении задач размещения пунктов сбора распределенного ресурса // Тезисы докладов, VII Всесоюзный симпозиум "Системы программного обеспечения решения задач планирования" в г.Нарва-Йыэсуу, Москва, ЦЭМИ РАН, 1982, сс,107-108.

6. Хачатуров В.Р., Веселовский В.Е., Туев C.B. Система проектирования на ЭВМ генеральных схем комплексного освоения акваторий континентального шельфа при поиске и разработке морских месторождений нефти и газа // Всесоюзная конференция "Экономика освоения океана", Владивосток, 1985, сс.52-53.

7. Туев C.B. Задача сбора распределенного ресурса на множество линейных сегментов" // Тезисы докладов, IX Всесоюзный симпозиум "Системы программного обеспечения решения задач планирования"

в г.Минск, М„ ЦЭМИ РАН, 1986, сс.108-109.

8. Туев С.В. Принципы организации в планарных задачах размещения распределенного ресурса // Международный симпозиум по методам оптимизации, СЭИРАН, Иркутск, 1989 , сс. 196-197.

9. Tuev S.V. Computer-Aided Design System for Objects Location and Reservoir with Dispersed Resourse Evolution Investigation // VTT Symp.135, Information technology and economics modelling, Helsinki, Technical research center of Finland, 1990, pp. 76-84.

10. Николаев Е.И., Хачатуров B.P., Злотов A.B., Туев С.В. Математические модели и методы выбора эффективных вариантов малых форм производства // "Экология и экономика", Международная неправительственная организация -Международный центр научной культуры - Всемирная лаборатория, Калининград, Моск.обл!,1992, сс. 123-134.

11.. Туев С.В. и др. "Системы планирования и проектирования комплексного освоения территорий" // Тезисы докладов, XXI Международная конференция "САПР-94"Новые информационные технологии в науке образовании, медицине и бизнесе",Крым,Гурзуф, 1994, сс. 61-62.

12. Туев С.В. и др. Пакеты программ для системного комплексного планирования и проектирования безопасного освоения нефтегазовых регионов. // Тезисы докладов. Выставка-конференция "Компью-Маркетинг'96", ГАНГ, М., 1996.

13. Туев С.В. и др. Комплекс программ на ПЭВМ для освоения нефтегазовых регионов // ВЦ РАН,М.,1999, 35 с.

С.В. Туев

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

Подписано в печать 18.04.2000 Уч.-иод.л. 0,9. Усл.-печ.л. 1 Тираж 100 экз. ¡Заказ 25. Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117333, Москва, ул. Вавилова, 40