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

РГБ ОД

2 2 МАЙ

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

До Лень Дат

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ДЛЯ ФОРМИРОВАНИЯ ПРОЕКТОВ СИСТЕМЫ ПЕРЕРАБОТКИ РЕСУРСОВ НЕФТЕГАЗОДОБЫВАЮЩИХ РАЙОНОВ ВЬЕТНАМА

05-13-18 - Теоретические основы математического моделирования, численные методы и комплексы программ

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1995

Работа выполнена в Вычислительном центре РАН. Научный руководитель: кандидат физико-математических наук

Федосеев A.B.

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

Хоботов E.H.

кандидат физико-математических наук Левиков A.A.

Ведущая организация: Всероссийский Научно-исследовательский

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

Защита диссертации состоится " /¿> " 1995 года в

часов на заседании специализированного совета Д 0002.32.05 по присуждению ученой степени доктора физико-математических наук при Вычислительной центре РАН (11796?, Москва, ул.Вавилова 40, конфен-ренцзал).

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан " IО " 1995 г.

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

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

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

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

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

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

Работа выполнялась в рамках международного научного сотрудничества между институтами НЦНИ СРВ и ВЦ РАН.

Целью работы являлось:

-Обосновать целесообразность построения автоматизированной системы проектирования для формирования вариантов проектов системы переработки нефтегазодобывающих районов Вьетнама ;

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

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

учетом ограничений на ресурсы;

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

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликованы 2 работы на

русском языке и 1 - на вьетнамском. Результаты диссертации докладывались на научных семинарах в ВЦ РАН и в институтах НЦНИ СРВ.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка цитированой литературы. Объем работы 103 страниц машинописного текста.

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

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

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

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

В §1.2 рассматриваются вопросы моделирования производственных процессов добычи и переработки ресурсов в регионах с добывающими и перерабатывающими отраслями. Описывается применяемый на предпроектной стадии подход к формированию моделей месторождений, а также моделей добывающих и перерабатывающих отраслей. Этот подход был разработан сотрудниками отдела МПРС ВЦ РАН для создания систем автоматизированного проектирования и планирования освоения природных ресурсов нефтегазодобывающих регионов и

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

Глава 2 посвящена разработке математических моделей и методов для решения задач, связанных с формированием проекта системы сбора и переработки ресурсов.

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

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

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

В §2.2 ставится задача определения вариантов структуры размещения перерабатывающих предприятий. Приводятся постановки задачи, в которых учитывается или не учитывается условие "непе-рекрепления" источников сырья к пунктам производства с течением времени.

Здесь и далее используются обозначения:

I = { 1,2,...,т } - множество мест возможного размещения предприятий;

ш <= I - произвольное подмножество множества I, П - множество всех возможных и ;

J = (1,2.....п) - множество источников сырья;

т = { 1,2,...,Т } - множество моментов планового периода;

О = (1,2,...,5) - множество видов продуктов переработки;

Ц - объемы добычи сырья в З-ом пункте;

х\ - количество сырья из 3-ого источника, направляемого на переработку в 1-й пункт в момент г;

с[ - затраты на транспортировку единицы ресурса из 3-ого источника в 1-ый пункт переработки в момент г;

А,^ - количество продукции д-ого вида, получаемое в момент 1; в 1-ом пункте при переработке единицы ресурса 3-ого источника ;

А?1- верхние ограничения на объемы производства продукции ц-ого вида в 1-ом пункте в момент г;

П - затраты на создание в 1-ом пункте перерабатывающего предприятия;

К, - затраты на получение продукции q-oro вида из единит ресурса, добытого в j-ом источнике и переработанного в 1-ом пункте в момент t;

Здесь le I, j f J, tet, qeQ.

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

í(ü»=2D + miní2 I 1 (clj+ I К?))*;.} (1)

ieU) X. ietO jeJ teX q<=Q i J

при условиях

Y Л,41 x\ «Aqt, (2); xl. = blz. (4)

Л IJ 4 <• LJ LVJ

j € J

У = tf , (3); s € t 0,1 }. (5)

Li W J V J

¿ eu

Последнее условие означает, что ресурс из каждого источника доставляется только к единственному пункту переработки в течение всего планового периода. Задача состоит в нахождении to° е Q и Q(R), таких, что

Г(ш°) = rain Г(ш) и ñ(R) = Í ш € П| í(u) í(w°) + R }, Е > 0. weQ

Условие (5) для упрощения решения задачи можно заменить на

О $ z. . ^ 1. (б)

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

Помимо вышеописанных используются обозначения: Ъ. - объем запаса сырья в J-ом источнике; р^1 - объем производства продукции q-ro вида в 1-ом пункте в момент Ъ;

В - заданный план производства д-ого вида продукщш ; с'. - затраты на добычу единицы ресурса из З-ого источника; й?1 - затраты на получение единицы продукции q-гo вида в результате переработки ресурса в 1-ом пункте ;

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

I

эксплуатацию перерабатывающее предприятие, чг1 =

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

ш = I I ^ I I I +

tet ieü)

li^i l et i e J

+ У Cl X1. + У У d4t Aql X1.] ¿л i j ч L L t vj ч

leW

qeQ leW,

при условиях 2

isT L ч

= У.

(8); ^ l Bf

i<sWt j e J

(9); x1. £ 0 ,

ieW.

y) » 0

У A.qt xl < Aqt , (10);

L j ч i

jej

~ r» A

Задача (7)-(13) сводится к поиску w € fl , такого, что

(7)

(11) (12) (13)

Р (ш°) = min Р (ш)

Üefi

где П - множество всех со при условии однократного создания предприятия

и> П 0Jt = о ;vs,t€t , s^t.

К (8) - (13) часто добавляют условия

х1 . = у1г. . , (14); г. . € (0,1 >• (15)

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

Для каждого ребра (к,1) е в(.1,1), где к,1 с I и J затраты на ввод в эксплуатацию коммуникации (к,1) и транспортировку продукции в объеме х^ есть г 0. <1=0.

°к1+ • <1>0 • ( > ^ > 0 >• Требуется построить транспортную сеть состоящую из |ш| деревьев минимальной стоимости.

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

Здесь используются обозначения:

Н = {1,2.....Ы -множество типов огранизации развития производства на перерабатывающих предприятиях;

Ь={1,2,...,1> - множество видов ресурсов , необходимых для организации выпуска готовой продукции ;

план выпуска продукции на 1-ом предприятии ; - количество ресурса 1-го вида, необходимого для производства единицы продукции в 1-ом пункте при 11-ом типе организации производства в t-ыft момент после ввода предприятия в

эксплуатацию;

Mu - оценка общего объема потребления 1-го ресурса перерабатывающими предприятиями; i

A.h - верхнее ограничение на объем выпускаемой продукции в i-ом пункте при h-ом типе организации производства в t-й момент после ввода его в эксплуатацию;

c'h- затраты на производство единицы продукции в 1-ом пункте при h-ом типе организации производства в t-й момент после ввода предприятия в эксплуатацию ;

xih - распределение пунктов переработки по типам организа-

ieCd

ции производства, x=íx.h >heH , let ЬеН ieU)

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

^ а1;1"4'1 Ь1 x.h

g(x)= max max max (0, Y Y —--—— -1)

leL i^heH lílt

- оценка перерасхода ресурсов;

е - уровень перерасхода ресурсов , оцениваемый с помощью функции g(x) ;

X = { х I £xih= 1, хь 6 СОИ),

heH

ь1 « У a'TV^x.к . Íeu,te{t.+1.....T),heH},

i ¿j i h t n t

heH

X(£)={xeX | g(x) < £}, где 0 í s í s, при этом можно взять

jl , I - t +1

Q. , I

e = max max ( > max —1--— - 1 ),

leb ten t.. heH M

teO)

Xo(a) = ÍX€X(8) I f(x) = mln i(x') >.

x-eX(S)

Ставится задача нахождения е° € Ш,ё], что е° = min _ s

eeto.e]

при условии Xo(е) Ф & , а также задача нахождения Xo(8°)

или х° (е°) € Xo (е°).

В главе 3 рассматриваются алгоритмы решения оптимизационных задач, сформулированных в §§2.2 - 2.5.

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

Функция (1) представляется в виде f(ш) = D(co) + С(ш), где, D(co) = \ D. ,

le(ú

С (со) = min 2 1 Ct.zt. (16)

Zi j ie(J jej

при условиях

I K\ % « Af . (17); l Zlj = 1, (18)

jej ¡.<=C0

и (5), здесь с.. = У ( с. . + У Kql )bl , Л41 = Xqtbl, а пере-

ij ¿ ч L i j j ь j ij j г

leí qeQ

менная z.. определяет прикрепление J-oro источника к 1-ому предприятию: zí. = 1 означает, что 1 t 3 соединены, zi. = 0 -что несоединены.

Заменив условие (5) на (6) получим нижнюю оценку С (со) для С (со), то есть

С (со) ^ С (со), V со с Q .

Для задачи (16) - (18), (6) строится функция Лагранжа Ш, Zlj , ) = 1 I ( cijZii +

jej

+ 1 I <Ои-АГ>иГ(и>

tel qeQ

Затем осуществляется переход к двойственной задаче

С(ш) = max min L(u, z. . , u^'íw)) = тах L(u,u*1 (w)) u*l(u)£0 z 11 1 u*l(u)3£)

при условиях (6), (18). Находится приближенное решение u^l(I)

задачи max L(I , u*l(I)) с помощью алгоритма обобщенного u?1 (I) 0

градиентного спуска в сочетании с алгоритмом возможных направлений. На основе этого приближенного решения строится нижняя оценка для Г(ш) - ?(ш) обладающая свойством супермодулярности:

Г(0) + f(7) - í(6U7) - Г(бП7) ^ О, V б,7 € а .

Последнее позволяет находить минимум Г(ш) и Q(R) для этой функции с помощью метода последовательных расчетов В.П. Черени-на и в дальнейшем эффективно определять Q(R) для f(u).

В §3.2 аналогичный подход применяется для решения более сложной задачи формирования вариантов размещения и развития производственных мощностей перерабатывающих предприятий (7) -(15).

В §3.3 посвящено описанию модификации комбинаторного алгоритма построения древовидной сети с учетом фактора времени. Ранее этот алгоритм был предложен и использован А.В.Федосеевым и Чан Ван Хунт для решения задач в статической постановке. Так как согласно процедуре отыскания реального проекта системы переработки задача построения коммуникационной сети решается

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

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

После ряда преобразований задача приводится к виду min Ux) = min I J cth xih

ih ih ie(j) heH

при условиях

Кь = 1. Xih€i0,1},

heH

I J Olh<*lt(l+e). К*КъЪъ

heH ietO heH

0 < e « i.

Здесь cih, d^ - определяются через параметры исходной задачи.

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

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

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

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

Основное содержание диссертации отражено в следующих публикациях

1) Астахов Н.Д., Федосеев A.B., Чан Ван Хунт, До Лень Дат, Математические модели и методы для формирования проектов системы переработки ресурсов нефтегазодобывающих районов Вьетнама

// Сообщения по прикладной математике. М.: ВЦ РАН, 1995. (в печати).

2) Астахов Н.Д., До Лень Дат, Задача организации развития мощностей предприятий при ресурсных ограничениях // Сообщения по прикладной математике. М.: ВЦ РАН, 1995. (в печати).

3) До Лень Дат "Ve mot thuat toan giai bal toan phan bo cae xl nghlep che bien dau khi " Bao cao tal Hol nghl khoa hoc Vlen Tlnh toan va Dieu khlen -Vlen Khoa hoc Viet nam, 1989.( Об одном алгоритме решения задачи размещения нефтегазоперераба-тыващих предприятий - Сообщения на научной конференции Института информатики НЦНИ СРВ, 1939 ).

До Лень Дат

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

Подписано в печать 27.03.95. Формат бумаги 60x84 1/16. Тираж 100 экз. Заказ 18. Бесплатно

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