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

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература 13

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

Введение к работе

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

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

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

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

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

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

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

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

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

В обзоре литературы особое внимание уделено работам [ 7-J5], в которых учет эффекта агломерации в моделях осуществляется с помощью функций экономии затрат за счет территориальной концентрации производств. Авторы рассматривают некоторые виды этих функций и предлагают различные приближенные алгоритмы для решения задачи. Подробно описана работа Пз] » в которой предложен подход, положенный в основу используемого в диссертации метода исследования.

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

Цусть N [lt2,..yU] - множество отраслей, каждая из которых имеет набор Qe вариантов оо размещения предприятий на территории района. Каждый вариант сое представляет собой подмножество множества 17 =/, 2,...,7л} - множества пунктов возможного размещения производств, 6 Є Л/} оо с 7 . Тогда п -мерный вектор ю = ((х ь u Z) ...j oOn ) , -я компонента которого есть один из заданных вариантов размещения предприятий і -й отрасли, определяет вариант размещения предприятий всех отраслей на территории. Вектору to ставится в соответствие m -мерный вектор i/ (аУ) trz ...9crm)9 і-я компонента этого вектора есть набор отраслей, предприятия которых находятся в пункте с, uLcA/, le U . Отметим, что trL определяет структуру многоотраслевого комплекса, расположенного в пункте, а вектор и задает структуру многоотраслевого комплекса всего района.

После этого решается задача /піп / «О алгоритмом из главы 3. Приводится модификация алгоритма применительно к данному случаю, и излагаются вычислительные аспекты ее реализации.

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

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

Диссертапионное исследование проводилось в рамках педевой комплексной программы 0.Ц.027 "Межотраслевая система для автоматизированного проектирования схем комплексного освоения территорий", номер государственной регистрации 0182.2 043934.

Содержание различных разделов диссертации докладывалось на научных семинарах Щ АН СССР, ХХІУ, ХХУ научных конференциях МФТИ (Долгопрудный, 1979, 1980 г.г.), УП, УШ Всесоюзных симпозиумах "Системы программного обеспечения решения задач оптимального планирования" (Нарва4!ыэсуу 1982, 1984 г.г.) и Конференции по информатике, вычислительной технике, автоматизапии в науке и технике, народном хозяйстве (Москва, 1983 г.).

Основные результаты диссертации отражены в работах [19, 24, 25, 29, 31, 32, 36] . 

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

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

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

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

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

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

Чтобы выделить класс такого рода задач и исследовать его в диссертапии, опишем способы задания эффекта агломерации.

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

Для математического описания агломерэпионного эффекта введем следующие обозначения. Пусть А/ = /і, 2, ... , п J множество отраслей, предприятия которых необходимо разместить на данной территории; С7 = ГI, 2, ... ,/nJ - множество пунктов возможного размещения; о - набор отраслей, предприятия кото Є рых размещаются в с -м пункте, х. - мощность предприятия t -й отрасли ( & W; ), расположенного в / -м пункте. Тогда функцию сокращения общих затрат или дополнительной экономии запишем в виде д /. ((/. х?) . Здесь в л ft включается сокращение как капитальных, так и эксплуатационных затрат.

Дня упрощения математического описания эффекта агломерации предположим, что сокращение капитальных затрат не зависит от мощности размещаемых предприятий, а сокращение эксплуатационных затрат является аддитивной функцией от отраслевой экономии (экономии для каждой отрасли вследствие территориального совмещения предприятий), которая пропорциональна мощности предприятия: a fl (ч, xf) = д 7? (ц) Е л к(ч)-х?. Тогда суммарный эффект от агломерации в районе расположения предприятий будет равен 2_ /3 / (щ, xt- )

Сделанное предположение о виде функции й, f- (uL) х[) не уменьшает основных трудностей, связанных с определением эффекта агломерации. В ряде работ [1, 3, 5, 7-15", 1] , рассмотренных в предыдущем параграфе, указывалось, что необходимо иметь воз можность вычислять величину агломерационного эффекта для разно го рода затрат в зависимости от набора отраслей в пункте разме щения их предприятий. Другими словами, в каждом пункте t J должны быть заданы функции Д 7/ (и: ) и йк (и-) на мно жестве всех возможных подмножеств ст. с л/ . Общее коли чество возможных (Хс в каждом пункте равно 2 , и, следо вательно, для описания эффекта агломерации в пункте размещения предприятий, вообще говоря, необходимо определить 2 значе ний функций А Т[ (ггс) и п- значений функций дк?(г/с).

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

При описании алгоритма, не умаляя общности, будем считать, что число возможных вариантов размещения предприятий \Я.е\ для всех отраслей одинаково я равно J , a Q ={о со ,..., }. Введем в рассмотрение переменные $t f ї є {о,ї,..., q-/}, ел/, с таким условием, что , е[0: у f Ті f -J для всех 6 Л/ . Тогда, если для некоторого -Ь» = / , то для -й отрасли реализуется вариант размещения ее предприятий Задачу (2.8) можно теперь представить в виде: nU f(f), (2Л2) где /(f) =f (co; , ft,..., uf ); t-o t 0,4, ..., y-fj.

Так же, как в алгоритме решения распределительной задачи с буле выми переменными [24, 22 L каждый элемент f - [ ft , j & , можно представить в виде ҐІ -разрядного Q -ичного числа: =/,Д.--Д , где fe Q [o,l,..., f } , І/Іу является номером той строки матрипы ll$fll » Дяя которой f S При таком способе записи f(fJ /(w/ fy ..., ) Алгоритм заключается в последовательном переборе элементов ZeD с отбраковкой заведомо неоптимальных решений. В нем используется такой же способ построения элементов $ ЄІ , который был предложен в [Ziy 22] для решения распределительной задачи с булевыми переменными. Т.е. берется f"- (0yO,..,;oJt Є очередное f образуется из предыдущего элемента f по правилу Ґ (f + ) 1) = /2,.,-, -1, и тем самым лексикографически упорядочиваются все Є Т f f ... f-\

В алгоритме применяются два правила отбраковки: правило отбраковки по отклонениям и правило отбраковки по опенкам. Сформулируем эти правила.

I. Правило отбраковки по отклонениям.

Будем считать, что известна аппроксимирующая функция Р(ы)= = И Ре ( 9 fM & P(L) СлеДУя ВДее метода упорядоченного перебора, расположим элементы каждого множества в порядке возрастания f (ti e) и заново перенумеруем их: Определим bfe = Ре(Ч ) - РеЫ У, Д ф- Е Atf ЄЄА/ Тогда О = Дое А,е 4 ... Дг е P(V „ («?) Pewter)- P(LOJ= Z Ре (и?) Для некоторого неотрипательного числа R введем множество 4l (R) всех элементов и}є Q со значениями Р(со) , отличающимися от Р ( и)0) не более, чем на R , которое образуется исключением всех , для которых й (f) R Это дает возможность в соответствии с аппроксимапионно-комбина-торным методом сузить область допустимых решений и искать опти 59 мальное решение задачи (2.8) среди элементов множества Q(R), вг« c Q. Детализируем применение этого правила в рассматриваемом алгоритме. Пусть $ получено из J . Тогда существует число г є N такое, что $ч $, /,2,..„ г-/, л (f ) вычисляется по формуле А (Ї ) = А (% ) - X, Дуз е 4/С г Если окажется, что A ( ) R то не нужно рассматривать все у , у которых fe =J3e для =-//2,..., t-/9 Число S отбракованных элементов t равно ( Q, -J3 ) у. . Следующий элемент f образуется из элемента K+S f - ( f ) Заметим, что каждый раз, когда для некоторого К оказывается % = к , подсчитывается значение f ( Щ, [, tci \ .. . , С0Л ) , находится очередное времен но-оптямальное (наилучшее среди просмотренных) решение Г с соответствующим значением функционала f(fj и определяется

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

Если условие (3.7) не выполняется, то определяется следую " (к) щая компонента Vr J » которой соответствует ск) \иь min, llt) V (\w Г\ к) Г\і ) и переходим к следующей итерапии, начиная с шага I.

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

Алгоритм был реализован для решения задачи определения оптимальной совокупности многоотраслевых комплексов без ограничений на мощности предприятий в виде программы на алгоритмическом языке МГОЛ-60 для ЭВМ БЭСМ-6. Изложение результатов его работы приводится в 3.3, а практическому применению посвящена глава 4. Использование этого алгоритма в случае задачи с ограничениями на мощности предприятий требует разработки алгоритмов решения транспортных задач, незначительно отличающихся одна от другой и возникающих при вычислении опенок Рк . Для этого применяется ряд приемов, описанных в работах [Z7, 28] при решении задач размещения предприятий с ограниченными мощностями.

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

При решении практических задач не всегда требуется нахождение точного решения, иногда бывает достаточно и приближенного. Для этой пели предлагается использовать следующие алгоритмы [25, 23]. I. Алгоритм последовательного перебора всех возможных вариантов с остановкой по времени или по числу итерапий»

В этом алгоритме реализована схема последовательного перебора всех возможных вариантов. При этом на tf-й итерапии алгоритма подсчет значения функции f (\J-K)) происходит С учетом результатов промежуточных расчетов, связанных с определением значения /(u/-K 1lJ для о/ " , отличающегося от ( одной или двумя компонентами. Для получения опенки точности решения d , найденного в результате работы этого алгоритма, нужно построить функцию P(u))= И РР / о ) так же, как в алгоритме точного ре-шения. Затем определить для всех М ,w% рС е)-Рр( ). Тогда И Р ( o)f(oi) ffil или / {kj - приближенное реше-ниє с опенкой точности [(f(Z) /L Ре ( еу/ЇІ )! 00/ . Отметим, что эта опенка, как правило, является грубой. Если известно точное решение, используется опенка [(f() {(ф1 f&)у№І Опенки, полученные в результате эксперимента, сравниваются в 3.3. 2. Алгоритм покоординатного спуска [29] .

Этот алгоритм определяет приближенное решение задачи в результате последовательного нахождения наименьшего по каждой из компонент вектора со значения функции ffa) . Пусть на о нд шаге каким-либо образом выбраны компоненты этого вектора, т.е. (л) =ч& /; ,..., л/» я вычислено значение функпии /С J j Алгоритм состоит из ft итерапии. Пусть на (?Ч ) й итерапии имеется временно-оптимальное решение со1 с j -ft1 / С -я итерация ( гъ ) заключается в следующем. При фиксированных компонентах ,,,, г \ и\..., їт находится ntuv /fa6 .., со/ 0, l , Єи -)---1 п / ОР1 достигается для a\(e)Q Затем полагается to - ї для всех s ї , я тем самым определяется новое временно-оптимальное решение со с ( s f ( и (с ) . Опенку точности полученного решения можно определять так же, как в алгорятме I.

3. Адгорятм нахожденяя локального минимума. Приведем понятяе локального минимума в задаче нахождения Функция /(со) на векторе ш« (Со1,оо2у.,.jи6п) достигает локальный минимум, если для любого В этом алгоритме для нахожденяя локального мянямума функпии f(tu) используется описанный выше алгоритм покоординатного спуска.

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

Следует отметить, что значение функпии Я (ше ) для и) можно интерпретировать как опенку затрат для варианта Сдс размещения предприятий -й отрасли, -42, . Эта опенка используется при выборе Q - совокупности наиболее перспективных вариантов размещения предприятий данной отрасли для их совместного размещения на одной территории с предприятиями других отраслей. Что касается вариантов из множеств Qc в задаче (2.8), то они могут быть выбраны по каким-либо другим "отраслевым соображениям", т.е. без использования функций ?е (г ) -Причем, опенка затрат і -й отрасли для неко торого варианта tug Є Q. g , вообще говоря, не совпадает с опенкой Ре (СОе ) . Следовательно, множество Q , составленное из наиболее перспективных с точки зрения размещения предприятий -й отрасли вариантов, может содержать совершенно иные варианты размещения, чем множество Q-e . Поэтому в задаче (2.8) оптимальная совокупность многоотраслевых комплексов определяется в результате увязки представленных отраслями вариантов размещения предприятий, а в задаче (4.10) оптимальную совокупность многоотраслевых комплексов определяет набор отраслевых вариантов размещения предприятий, определенный в результате решения оптимизационной задачи.

Рассмотрим теперь особенности решения задачи (4.10) с помощью алгоритма, разработанного в главе 3.

Заметим, что аппроксимирующая функция Р (и ) имеет такой же вид, как и опенка, используемая в алгоритме из параграфа ЗЛ. Поэтому в данном случае можно считать, что значения Ре( е) подсчитаны для всех ti e Ъе у в = /, г.

Учитывая это замечание, не будем повторять описание алгоритма из ЗЛ, а остановимся на его модификации, применяемой при реше нии задачи (4.10). В основе этой модификации лежит возможность использования опенки fl (u)L) вместе с Р (и)1) и Р(ш) и предварительный подсчет значений опенок fi C ) и f"( zj » чего не было в алгоритмах из главы 3. Итак, считаем, что вычис лены значения 0 (u)t) для всех со1 Q1 и J (u)z) для всех и)2 Є Q2 ,

Предложенные в работе модели и алгоритмы их решения нашли свое применение в математическом обеспечении Системы проектирования генеральных схем обустройства нефтяных месторождений на ЭШ [35] .

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

Проект генсхемы месторождения представляет собой взаимосвязанную совокупность проектов генеральных схем основных технологических систем: кустования скважин, сбора и транспорта нефти, поддержания пластового давления, электроснабжения, автомобильных дорог. Так, схемы линий электропередач и автодорог зависят от размещения объектов систем сбора и поддержания пластового давления, размещение объектов системы поддержания ПЛЭСТОЕОГО давления в свою очередь зависит от размещения объектов системы сбора и транспорта нефти.

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

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

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