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

Введение . ^

Глава 1. Содержательные постановки и основные математические модели размещения центров переработки (стоков) распределенного ресурса .!.

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

1.2. Формулировка универсальной общей задачи.

1.3. Эквивалентность постановок универсальной задачи на произвольных раскладках, расширенных покрытиях и расширенных разбиениях.<?

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

Глава 2. Методы исследования универсальной задачи.

2.1. Постановка усредненной задачи для исследования универсальной задачи.Я?

2.2. Ядро и накрытие решения, перекрытия, граничные множества.

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

2.4. Структура граничных множеств зон стоков, конкретные метрики и виды границ.

Глава 3. Методы исследования задачи зонирования при фиксированных стоках.г.

3.1. Постановка задачи зонирования и ее основные свойства.г!

3.2. Вывод общих формул градиентов для определения параметров нимость метода Ньютона для определения параметров ещение центров переработки (стоков) распределенного щение заданного числа центров переработки (стоков) еделенного ресурса. деление оптимального варианта размещения центров аботки (стоков) распределенного ресурса.г^.'

-126-Заключение.

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

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

Напомним базовые критерии (1.2.1)- (1.2.4):

- объем стока - = ] /(ху1х;

- транспорт стока - Р2Г = ] 1{2гх)/(х)с1х;

- отход стока - Р2К = 112 = тахх, /(г, х);

- остаток - = М(Х) - Р2°.

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

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

Коалиционные разбиения А={А{}, 1е1={1,.,п} - принцип организации объектов в коалиции А, без центров, на основе взаимодействия объектов между собой. Для формализации следует ввести коалиционные критерии

А А ■

Отметим, что для функций стоимости транспортировки г,хеЕ2, а, именно, функций, пропорционально зависящих от квадратичной функции расстояния

Кг,х) = к-[рЕ(г,х)]2 =А:-[(2(1) -х(1))2 +(г(2) -х(2))2], для коалиций Аг- существует псевдосток г,, относительно которого транспорт стока - ух)Дх)£х пропорционален коалиционному д критерию.

Периметрические разбиения А={А,}, 1е1={1,.,п} - принцип организации объектов в коалиции А,- без центров, на основе взаимодействия между соседними объектами, а, именно, на основе минимизации разрыва локальных связей. Для формализации следует ввести периметрические критерии определяющие взвешенные длины границ коалиции Д- и соответствующие мере (одномерных) областей разрыва локальных связей. Минимизация периметрических критериев соответствует физической модели поверхностного натяжения.

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

-128

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

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

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

Межцентровые модели объединяют постановки задач с наличием связей между стоками, аналогичные некоторым дискретным постанивкам задачи Штейнера-Вебера, в которых между стоками существует собственная инфраструктура (обширный список литература приведен в обзоре [5]). Примерами могут служить также двухэтапные и двухуровневые постановки, в которых вводятся центры второго уровня.

Множественноцентровые модели характеризуются тем, что вместо наборов стоков 2 ={г} рассматриваются наборы множеств стоков 2 = {?}. Множествами стоков могут быть, во первых, сегменты прямых, ломаные, многоугольники, дуги окружностей, в том числе, сами окружности, а, во-вторых, конечные точечные множества. К первым сводятся задачи сбора распределенного ресурса на протяженные объекты - дороги, коммуникации или, когда объекты сбора имеют существенные размеры, не могут быть представлены точками и расстояние до них целесообразно определять, как растояние до их периметров. Структура решений задачи сбора распределенного ресурса на сегменты прямых и дуги окружностей проанализирована в [24]. Задачи второго типа имеют сходную структуру с совместным зонированием с разными центрами в многоресурсных моделях, но их не следует путать.

Одномерные и квазиодномерные модели. К ним относятся задачи размещения объектов на протяженных объектах линейной или сетевой структуры. Ресурс может быть распределен как на этих протяженных объектах, так и на плоской области. Алгоритмы решения таких задач описаны в [19]. В качестве одномерного параметра может фигурировать время, в качестве ресурса - заявки, а стоков - моменты обработки заявок. Транспортный критерий трактуется, как суммарное время ожидания, а объемы, как число заявок единовременной обработки [31]. Помимо прочего, модели такого типа являются удобным модельным примером для исследования сложности задачи размещения с распределенным ресурсом.

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

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

- Средства представления, манипулирования и обработки данных географического типа о распределенном ресурсе.

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

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

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

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

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

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

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

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

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

- Система для неравномерного размещения скважин совместно с буровыми платформами на газо-коденсатных шельфовых месторождениях , в условиях малой изученности и жестких технологических ограничений для Чайво (1981 год) и ряда месторождений Черного и Азовского морей (1984 год). Расчеты были проведены для следующих местождений и площадей: Черное море - Безымяное, Центральное, Шмидта, Евпаторийская, Прибойная; Азовское море - Белосарайская, Морская. р.Й-1?

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

Для персональных компьютеров:

- Система оценки различных вариантов сеток скважин с точки зрения решения задач кустования в различных условиях жестких

-131технологических ограничений на основе многовариантных расчетов и многокритериального анализа вариантов. Расчеты были проведены для следующих местождений: Белый Тигр (1986 год), Тенгиз (1987 год), Сандивей (1990 год), Лебяжье (1992 год).

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

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

Имитационная система многовариантных расчетов для определения очередности ввода расчетных элементов (с учетом схемы кустования и очередности ввода кустов) для системы гидродинамических расчетов "Лаура" (разработка ВНИИНефть) по импортируемым из нее данным о сетке скважин и экспортом в нее результатов расчетов (1994 год).

- Имитационная система оценки вариантов строительства и рациональной стоимости миниэлеваторов с учетом коньюктуры рынка в условиях перехода к малым формам производства в период перестройки для одного из районов Ставрополья (1991 год). [2?!

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

1. В.З.Беленысий. Геометрико-вероятностные модели кристаллизации1. М., Наука, 1980, 84 с.

2. Г.Ф Вороной. Исследование о примитивных полиэдрах (1909 г.) // Собр.соч. Киев, Изд-ва АН УССР, 1952, т.2, 239 с.

3. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа // М., Наука, 1969, 382 с.

4. Голыптейн Е.Г. Теория двойственности в математическом программировании и ее приложения // М., Наука, 1971, 351 с.

5. Э.Н.Гордеев, О.Г.Тарасцов. Задача Штейнера. Обзор // Дискретная математика, 1971, т.5, в.2, сс.3-28.

6. Киселева Е.М., Шор Н.З. Алгоритм решения многопродуктовой задачи оптимального разбиения с ограничениями // Киев, Кибернетика, 1985, 1, сс. 76-81.

7. Киселева Е.М. Решение одной задачи оптимального разбиения с размещением центров тяжести подмножеств // Журнал вычислительной математики и математической физики, 1989, 29, N0. 5, сс.709-722.

8. Киселева Е.М. Математические методы и алгоритмы решения непрерывных задач оптимального разбиения множеств и их приложения //Автореферат дисс.докт.физ.-мат.наук, Киев,1991,33 с.

9. Киселева Е.М., Ус С.А. Решение задачи оптимального разбиения множеств с нечеткими ограничениями // Вопросы прикладной математики и математического моделирования. Днепропетровск, ДГУ, 1991.

10. Киселева Е.М. Решение задачи Неймана-Пирсона с использованием методов оптимального разбиения множеств // Журнал вычислительной математики и математической физики, 1992,32,N 1.-иь

11. А.Н.Колмогоров, С.В.Фомин. Элементы теории функций и функционального анализа // М., Наука, 1972, 496 с.

12. Г.Корн, Т.Корн. Справочник по математике // М., Наука,1974, 831 с.

13. Р.Курант и Д.Гильберт. Методы математической физики// М.-Л., ГИТТЛ, 1951, Т.1, 476 с.

14. С.Ленг. Алгебра // М., Мир, 1968, 564 с.

15. К.Роджерс. Укладки и покрытия // М., Мир, 1968, 134 с.

16. С.А.Пиявский. Об оптимизации сетей // М., Тех.киб., 1968, 1.

17. Ф.Препарата, М.Шеймос. Вычислительная геометрия: введение // М., Мир, 1989, 478 с.

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

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

20. С.В.Туев "Оптимизация сбора и переработки распределенного ресурса" // Сборник "Оптимизация и стабильность", Вычислительный центр Российской Академии Наук, 1980, сс.21-31.

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

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

23. С.В.Туев "Задача сбора распределенного ресурса на множество линейных сегментов" // Тезисы докладов, IX Всесоюзный симпозиум "Системы программного обеспечения решения задач планирования" в г.Минск, Москва, ЦЭМИ РАН, 1986, сс.108-109.

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

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

26. С.В.Туев "Задача сбора распределенного ресурса на множество линейных сегментов" // Тезисы докладов, IX Всесоюзный симпозиум "Системы программного обеспечения решения задач планирования" в г.Минск, Москва, ЦЭМИ РАН, 1986, сс. 108-109.

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

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

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

30. И.А.Ушаков "Приближенный метод оптимизации систем сраспределенными объектами" // Техническая кибернетика, 1979,No.2.

31. В.Р. Хачатуров. Определение оптимального и всех близких к нему вариантов размещения предприятий с ограниченными объемами производства. // Изв. АН КазССР, сер.физ.-матем.,1967, с. 38-47.

32. В.Р. Хачатуров. Некоторые вопросы и приложения к задачам размещения методом последовательных расчетов // Дис.канд.физ.мат. наук. -М.ДЭМИ АН СССР 1968.

33. В.Р. Хачатуров. Математические методы регионального программирования // М., Мир, 1989, 297 с.

34. В.П.Черенин. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов. // Научно-методические материалы экономико-математического семинара ЛЭММ АН СССР М.:1962, вып.2.

35. Л.В.Канторович. О перемещении масс.// ДАН, 1942, 37,No7-8, с.227-229

36. Bollabas Bela. The optimal arrangment of producers // J. London Math. Soc., 1973, 6, No.4, pp. 605-613.-13638. Freidman M. On the analysis and solution in certain geographical optimal covering problems // Comp, and Oper. Res., 3, 1996, No.4.

37. Corley H.W. Roberts S.D. A partitioning problem with applications in regional design // Oper.Res.,1972, 20, No.5, pp. 1010-1019.

38. Corley H.W. Roberts S.D. Dualiti relationships for a partitioning problem // SLAM J.Math.,1972, 23, No.3, pp.490-494.

39. Fransis A.L. Sufficiant conditions for some optimum property facility design // Oper.Res.,1967,15, No.3, pp.448-466.-Í35

40. U Кс^его^и территории. CWr-op-m1. ГЦ. Уси-искТсв- Aie¿Töpüpu¿» Усимсксе ( кЬмсл)1. МЯГЫТП£ i-SDDDOлах радиус, Отхода (л)3 Y 8 ммг™/е/воЪлгость л-7 81. Гросрс/к i.g Ю m Зель/й /7?с/гр.ело ТП)б1/ ¿Dt/Ó'.1. РМ12 К1. График 2*4L/ / 'ff1.П6.я