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

ВВВДЕНЙЕ.

ГЛАВА I. Основные подходы к решению задач размещения предприятий нескольких отраслей с учетом эффекта агномерапии

1*1. Обзор экономико-математических моделей и методов, применяемых для решения задач размещения предприятий нескольких отраслей

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

ГЛАВА 2. Постановка и алгоритм решения задачи определения оптимальной совокупности многоотраслевых комплексов с учетом эффекта агломерапии

2.1. Общая постановка задачи и основные положения используемых комбинаторных методов

2.2. Алгоритм решения задачи.

2.3. Особенности решения задачи при некоторых способах учета эффекта агломерапии

ГЛАВА 3. Вычислительные алгоритмы решения задачи определения оптимальной совокупности многоотраслевых комплексов с учетом эффекта агломерапии

3.1. Алгоритм точного решения

3.2. Алгоритмы приближенного решения

3.3. Примеры и анализ решенных задач.

ГЛАВА 4. Задача размещения предприятий двух типов на одной территории с учетом эффекта агломерапии и ее приложение.

4.1. Задача оптимального размещения предприятий двух отраслей на одной территории с учетом эффекта агломерапии и ее решение

4.2. Применение алгоритмов, описанных в главе 3, для решения задач размещения объектов двух технологических систем обустройства нефтяного месторождения. Н

В документах ХХУ1 съезда партии в качестве одной из проблем хозяйственного развития нашей страны отмечается проблема дальнейшего улучшения размещения производительных сил, совершенствования территориально-экономических связей, обеспечения рапионально-го сочетания отраслевого и территориального планирования. В настоящее время при решении этих сложных задач в качестве объекта планирования рассматриваются районные (региональные) территориально-производственные комплексы (ТШС).

При формировании ТПК должен быть решен пелнй ряд вопросов развития промышленной и социальной инфраструктуры района. Применение экономико-математических моделей и методов оптимизации для этих пелей вызывает значительные трудности. Данной проблематике посвящены работы А.Г.Аганбегяна, Н.Н.Некрасова, М.М.Албе-гова, М.К.Баццмана и других.

В 1972-1974 г.г. В.Р.Хачатуровнм была сформулирована комбинаторная постановка пелого класса задач оптимального формирования ТШС района, в которых эффект от агломерации проявляется скачкообразно, и показана применимость аппроксимапионно-комбинаторного метода для их решения.

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

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

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

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

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

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

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

Номер Начальное временно-оптимальное значение целевой функпии Число просчитанных вариантов Время счета

I 6113,41 689 II мин 48 с

6000,07 529 8 мин 45 с

2 6113,41 828 13 мин 43 с

6000,07 529 8 мин 52 с

3 6113,41 866 14 мин 28 с

6000,07 529 9 мин 4 с

С дальнейшим увеличением общего числа вариантов величина массивов, необходимых для работы алгоритма точного решения, и массивов исходной информации превосходит возможности ОЗУ. Поэто му эти задачи рассматриваются как задачи большой размерности. Результаты их приближенного решения приводятся в табл. II. Погрешность решения оценивалась с помощью Р (и*} и>| ) по формуле из 3.2.

Та б липа II

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

Номер Общее число вариантов, равное iq:H qh Наименование алгоритма Число просчитанных вариантов Время счета Погрешность решения

I 157000 h h 361 862 II мин 8 с II мин 26 с 2$ 2$

2 222000 h h 970 971 12 мин 24 с 12 мин 41 с 2$ 2$

3 483000 h 1403 1404 17 мин 56 с 18 мин 14 с 2$ 2$

Изложим результаты решения задачи размещения объектов двух технологических систем с учетом агломерационного эффекта. Я, * 300, Rz * 300; IQ'I = 215, \Q°J = 260; |Q>|Q;| = = 56000; P (co^ 5881,50; ffa,^) = 6000,07.

Просчитывалось 866 вариантов, что составляет 1,6$ от общего числа. По критерию оптимальности аппроксимапионно-комбинаторно-го метода полученное решение является оптимальным, так как fU/}oi2)=6000>07 * Р(и)f, +R, 6401,50.

В табл. 12 приводятся стоимости размещения объектов систем ДНС и КНС с учетом эффекта агломерапии и без него.

Стоимости размещения объектов систем ДНС и КНС ( в тыс. руб.)

I 2 3

Стоимость размещения объектов системы ДНС без учета эффекта агломерации 1845,24 ^ ={19,36,42}

Стоимость размещения объектов системы КНС без учета эффекта агломерапии 4599,16 в {3,19,30,39,42}

Общая стоимость размещения объектов систем ДНС и КНС без учета эффекта агломерапии 6444,40 СО{19,36,42} i4= {3,19,30,39,42}

Общая стоимость размещения объектов систем ДНС и КНС с учетом эффекта агломерапии 6X13,41 {19,36,42} {3,19,30,39,42}

Наименьшая общая стоимость размещения объектов системы ДНС я КНС с учетом эффекта агломерапии 6000,07 d7 = {19,39,42} *(2= {3,19,30,39,42}

I 2 3

Снижение затрат 444,33

Снижение затрат на размещение объектов системы ДНС в абсолютном и процентном выражениях 127,33 (6,9*)

Снижение затрат на размещение системы КНС в абсолютном и процентном выражениях 317,10 (6,9*)

Стоимость размещения объектов системы ДНС с учетом эффекта агломерации 1717,91 {19,39,42}

Стоимость размещения объектов системы КНС с учетом эффекта агломерапии 4282,06 с^ = {3,19,30,39,4^

На рис. 9 представлена схема пунктов возможного размещения объектов систем ДНС и КНС. На рис. 10 изображена схема совместного размещения объектов двух систем без учета эффекта агломерапии. На рис. II - схема совместного размещения с учетом агломерационного эффекта. Обозначения на схемах аналогичны предыдущим . й- —I -q a M j r sfi uJ a

IAП fa. a L

IH,

DO r

J" ел i rl

Рис. 9. Схема пунктов возможного размещения объектов систем ДНС и КНС

Рис. 10. Схема совместного размещения объектов систем ДНС и КНС без учета агломерационного эффекта

Рис. II. Схема совместного размещения объектов систем ДНС и КНС с учетом агломерационного эффекта

Алгоритмы я программы решения задачи определения оптимальной совокупности многоотраслевых комплексов с учетом эффекта агломерапии по одноиндексному способу вошли в состав математического обеспечения Системы проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ. Акт об их внедрении в СПГСО прилагается.

А к а д е м и я наук СССР

В Ы Ч И С J1 И Т Е J Ь Н Ы И ЦЕНТ Р

П7967 ГСП -1, Мосмпа. В -333, ул Вавилова 40. Для телеграмм Москва, В-333, ВЦАН

Тел 135-24-89, 135-04-40

На Л» л Г J

СПРАВКА О ВЩДРЕНИИ

Разработанные В.В. Григорьевым алгоритмы и программы для определения оптимальной совокупности многоотраслевых комплексов с учетом эффекта агломерации включены в математическое обеспечение Системы проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ (СПГСО)

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

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

1. Некрасов Н.Н. Региональная экономика.-М.Экономика, 1975. - 317 с.

2. Аганбегян А.Г., Багриновский К.А., Гранберг М.Г. Система моделей народнохозяйственного планирования. М.:Мысль,1972. 348 с.

3. Моделирование формирования территориально-производственных комплексов. Новосибирск: Наука, Сибирское отд., 1976. -338 с.

4. Алаев Э.Б. Экономико-географическая терминология. М.: Мысль, 1977. - 199 с.

5. Пробст А.Е. Вопросы размещения социалистической промышленности. М.: Наука, 1971. - 379 с.

6. Пчелинпев О.С. Экономическое обоснование размещения производства. Методы, применяемые в капиталистических странах. -М.: Наука, 1966. 264 с.

7. Арушанян И.И., Бандман М.К., Беленький В.З. и др. Нелинейная модель оптимизации пространственной структуры ТЖ. -Известия Сибирского отд. АН СССР. 1976, $ I, с. 62-71.

8. Албегов М.М. Проблемы оптимизации территориального планирования. Экономика и матем. методы, 1975, т. II, Л I,с. 147 159.

9. Албегов М.М., Солодилов Ю.И. Вопросы оптимизации размещения системы промышленных комплексов. Экономика и матем. методы, 1970, т. 6, вып. 6, с. 864-870.

10. Албегов М.М., Голубишсая М.В., Петухов Д.Г. Вопросы моделирования внутрирайонного размещения производства. В кн.: Проблемы теории и практики размещения производительных сил.-М.: Наука, 1976, с. 268-285.

11. Албегов М.М., Блинчевский B.C. Алгоритм и программа для решения целочисленной задачи. В кн.:. Математическое обеспечение задач размещения производства. - М., Наука, 1974, с. 5-24.

12. Албегов М.М., Солодилов Ю.И. Метод увязки отраслевых и районных планов. Экономика и матем. методы, 1968, т. 4, вып. 3, с. 353-363.

13. Хачатуров В.Р. Аппроксимапионно-комбинаторный метод и некоторые его приложения. ЖВМ и Ш, 1974, т. 14, Л 6, с. 14641487.

14. Злотов А.В., Хачатуров В.Р. О решении задач оптимального размещения предприятий двух отраслей. В кн. Системы программного обеспечения решения задач оптимального планирования. УП Всесоюзный симпозиум. Краткие тезисы докладов.

15. М.: ЦЭМИ АН СССР, 1982, с. 73-74.

16. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. -М.: Наука, 1981. 208 с.

17. Isa.rd W., Smith Т. Coa.(itiorL foca.tlon g&mes.-Region&i Science Association. Papers, v. 19/ {9G7.1.zrc/ W., Smith T. Location games: with application.to cfassic iocdtion pro6Cems. Regional Science Association. Papers, v.20y i9&8.

18. Ларина Н.И. Математические методы в формировании ТПК. -М.: Экономика, 1979. 94 с.

19. Лебедев С.С., Финкелыптейн Ю.Ю. Дискретное программирование. В кн. Математическое программирование (лекпии). Всесоюзная летняя школа по математическому программированию. Вып. 5. - Алма-Ата : 1969, с. I-II9.

20. Хачатуров В.Р., Калдыбаев С.У. Решение распределительной задачи с булевыми переменными аппроксимапионно-комбинатор-ным методом. В кн.: Труды У зимней школы по математическому планированию и смежным вопросам. - М.: ЦЭМИ АН СССР, 1973, с. 226-240.

21. Кацдыбаев С.У. Алгоритм аппроксимапионно-комбинаторного метода для решения распределительной задачи с булевыми переменными. Известия АН Каз.ССР, сер. физ.-матем., 1975, вып. 5, с. 43-49.

22. Хачатуров В.Р., Астахов Н.Д., Григорьев В.В. Алгоритмы определения оптимальной совокупности отраслевых вариантов размещения предприятий с учетом эффекта агломерапии. М.:1. ВЦ АН СССР, 1984. 22 с.

23. Григорьев В.В. Алгоритмы решения одной задачи определения оптимальной совокупности многоотраслевых комплексов. М.: ВЦ АН СССР, 1984. - 28 с.

24. Голыптейн Е.Г. Некоторые вопросы теории выпуклого программирования. В кн. Математическое программирование (пекши) . Всесоюзная летняя школа по матем. программированию. Вып. I. - Алма- Ата, 1969, с. 1-87.

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

26. Астахов Н.Д. Алгоритмы возможных направлений для решения некоторых задач транспортного типа. ЖВМ и МФ, 1976, т. 16, В 5, с. 1146 - 1154.

27. Григорьев В.В. Алгоритм приближенного решения многоотраслевой задачи размещения с учетом агломерапии. В кн.: Труды ЛИГИ, Сер. "Аэрофизика и прикладная математика". -М.: МОТ, 1980, с. 102 - 104.

28. Веселовский В.Е. Алгоритмы решения задач размещения большой размерности. Диссертация канд. физ.-матем. наук. -М., 1977. - 143 с.

29. Григорьев В.В. 0 решении одной задачи размещения предприятий двух отраслей. В кн.: Труды ЩГИ. Сер,"Аэрофизикаи прикладная математика". Долгопрудный: МФТИ, 1979, с. 214 - 217.

30. Хачатуров В.Р. Некоторые вопросы и приложения к задачам размещения метода последовательных расчетов. Диссертация канд. физ.-матем. наук. - М., 1968* - 164 с.

31. Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов. (Материалы к конференции по опыту и перспективам применения матем. методов и ЭВМ в планировании.) Новосибирск: Изд-во СО АН СССР, 1962.

32. Хачатуров В.Р., Аржанов Ф.Г., Астахов Н.Д. и др. Система проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ и опыт ее использования. Нефтяная промышленность. Сер."Нефтепромысловое строительство". - М.: ВНИИОЭНГ, 1980. - 68 с.