Диссертация (Разработка математической модели, численных методов и алгоритмов для структурно-параметрического синтеза электросети мегаполиса с учетом его перспективного развития), страница 10

На основе информации***о значениях векторов X 1n , X 2n , X 3n производится расчет значения целевойфункции Zn X, Sst . Результат решения подзадачи 3 передается модулю III.()Модуль III задачи координации осуществляет проверку выполненияˆ , Zˆ ) = 1 и, в случае Р(Хˆ ,Zˆ ) ≠ 1, передаетусловия окончания вычислений Р(Хnnnn*вектор X 3n модулю I, который определяет дальнейшую тактику решения задачиˆ ,Zˆ ) = 1, решение задачи завершается.ПРЭ. В случае если Р(Хnn65Математические постановки подзадач 1 – 3Подзадача 1.

Заданными являются:• множество подключаемых потребителей С = СH ∪ СL ;*• вектор X 2n−1 (для n > 0 );• множество возможных мест строительства новых объектов O ;• вектор параметров координации S n .На итерации n решения подзадачи 1 отыскивается вектор варьируемыхпараметров*X 1n ,обеспечивающийминимумскалярногокритерияоптимальности:*Для n = 0 : Z 1 ⎛⎜ Х 1n , S n ⎞⎟ = min Z1 X1n , Sstn ;⎝⎠ X1n ∈D(**)*(3.9)Для n > 0 : Z 1 ⎛⎜ Х 1n , Х n2 −1, S n ⎞⎟ = min Z1 ⎛⎜ X1n , Х n2 −1, Sstn ⎞⎟ .⎝⎠ X1n ∈D ⎝⎠Предложено два следующих подхода к формированию критериевоптимальности (3.9).1) Выделение из общего вектора критериев оптимальности Z(X ) критериев,относящихся только к подзадаче 1.

Поскольку задача ПРЭ является техникоэкономической задачей, гарантированно известно, что для подзадачи 1существует хотя бы один такой критерий – стоимость строительства всехобъектов, возводимых в результате решения подзадачи. В выделенные критериидолжны быть включены параметры координации.2) Применение эвристического подхода для определения новых критериевоптимальности.Подзадача 2.

Исходные данные:()• граф исходной электросети G исх = Tисх , R исх , Lисх ;• множество подключаемых потребителей С = СH ∪ СL ;*• вектор X 1n .66Решением подзадачи 2 на итерации n является вектор варьируемых*параметров X 2n , такой, что***Z 2 ⎛⎜ Х 2n , Х 1n , S n ⎞⎟ = min Z2 ⎛⎜ X2n , Х 1n ,Sstn ⎞⎟ ,⎝⎠ X2n ∈D ⎝⎠(3.10)*где Z2 ⎛⎜ X2n , Х 1n , Sstn ⎞⎟ – скалярный критерий оптимальности.⎝⎠Подходы к формированию критерия (3.10) аналогичны подходам,приведенным ранее для получения критериев (3.9) подзадачи 1.Подзадача 3. Исходными данными для подзадачи 3 являются:()• граф исходной электросети G исх = Tисх , R исх , Lисх ;*• вектор X 1n .*• вектор X 2n ;~• область допустимых значений вектора варьируемых параметров D.*На итерации n определяется вектор варьируемых параметров X 3n ,обеспечивающий минимальное значение итогового критерия оптимальности:*****Z ⎛⎜ Х 1n , Х 2n , Х 3n , S n ⎞⎟ = Z ⎛⎜ Х , S n ⎞⎟ = min Z ⎛⎜ Х 1n , Х n2 , Х 3n , Sstn ⎞⎟⎝⎠⎝⎠ X3n ∈D ⎝⎠В качестве критерия оптимальности для подзадачи 3 используется критерий(3.1).Задача координацииАлгоритм решения задачи координации включает в себя три модуля(Рис.

3.3 – 3.5).***Модуль I (Рис. 3.3). На основании сведений о векторах X 1n , X 2n , X 3nмодулем I принимается решение о переходе к одному из следующих вариантовдействий.671) Решение подзадачи 1 без коррекции вектора S n . В этом случае**предполагается получение вектора X 1n+1 , отличного от X 1n , за счет мультистартарешения подзадачи 1.2) Решение подзадачи 1 с коррекцией вектора S n . Коррекция вектора*координирующих параметров S n производится на основании вектора X 2n ивоздействует на решение подзадачи 1 путем определения начального*приближения, позволяющего достичь за минимальное время решение X 1n ,*лучше X 1n−1 .3)Завершение вычислений.

Решение о завершении вычислений может*быть принято ЛПР или автоматически по результатам анализа векторов X 1n и*X 2n .SnПересчет S nПодзадача 1Да*НетS n = S n−1Необходима коррекция S n ?Да*Модуль IIХ2nХ 3nМодуль IIIP Хˆ 2n , Zˆ 2n = 1 ?()*Х, ZРис. 3.3. Блок-схема модуля IМодуль II (Рис.

3.4). Полученный в результате решения подзадачи 2 векторX2n проверяется модулем II на наличие потребителей, для которых на итерации( n − 1) не найдены возможные варианты подключения к электросети. В68результате проверки определяется дальнейшая последовательность вычислений:если такие потребители существуют, вектор X2n передается модулю I задачикоординации; в противном случае, вектор X2n поступает в блок решенияподзадачи 3.Модуль I*Х 2nДа*Подзадача 2Х 2n∃ Сi*( X i )n −1 = 0?*Х 1n , Х 2n , S stnПодзадача 3Рис. 3.4. Блок-схема модуля IIМодуль III (Рис.

3.5). В модуле III выполняется проверка условия окончания***вычислений. В модуль поступают сведения о значениях векторов X 1n , X 2n , X 3n. Модуль также обладает информацией о значениях этих векторов на всехитерациях от 1 до n. Проверка производится на основании информации овекторах Х̂n и Ẑn путем вычисления предиката (3.1).Модуль I*Х 3n Нет*Подзадача 3 Zn , Х nP Хˆ n , Zˆ n = 1 ?()ДаZ * , X*Рис. 3.5. Блок-схема модуля IIIРассматриваем следующие условия окончания вычислений:69• достижение заданного времени вычислений timelim ;• достижение максимального допустимого числа итераций t lim ;• отсутствие улучшения решения в последних nlim итераций (стагнация).3.3.Подходы к решению подзадач 1-3, выделенных методамиредукции и декомпозицииПодзадачи 1 – 3 относятся к классу детерминированных дискретныхнелинейных задач оптимизации.

Эти задачи являются задачами переборноготипа, то есть каждая из них разрешима перебором конечного числа вариантов[32]. Зачастую решение задачи посредством перебора вариантов решенияневозможно, так как сопряжено с неприемлемыми затратами машинноговремени в виду значительной размерности задачи. В общем случае решениеданногоклассазадачможетпроизводитьсяметодамидискретногопрограммирования, которые разделяют на две группы [48] (Рис.

3.6):• точные методы;• приближенные методы.Методы решениядискретных задач оптимизацииТочныеПриближенн ыеметод ветвей играницдетерминированныеметодыметод полногоперебораметоды случайногопоискаметод динамическогопрограммированияметоды решения задачспециальной структурыэвристические методыРис. 3.6. Классификация методов решения дискретных задач оптимизации70Кточнымкомбинаторныеметодамметоды,дискретногокоторыепрограммированиягарантируютполучениеотносятглобальногооптимального решения. На практике широко применяют следующие точныеметоды.1)Метод ветвей и границ.

Метод реализует ограниченный перебордопустимых решений дискретной задачи. Сокращение перебора достигаетсяпутем массового отсеивания неперспективных подмножеств решений споследующим исследованием перспективных, среди которых может бытьоптимальное [20].2)Метод полного перебора. Это метод решения дискретной задачипутем перебора и оценки всех возможных вариантов ее решения. Сложностьметода зависит от размерности пространства всех возможных вариантоврешения. Как правило, из-за неприемлемо большого времени решения,использованиеметодадлярешенияпрактически-значимыхзадачнепредставляется возможным [55].3)Метод динамического программирования. Это – точный методрешения задачи дискретного программирования, в котором реализуетсямногошаговый процесс построения оптимального решения.

В этом процессекаждый шаг оптимизируется с учетом возможных результатов предыдущихшагов, а также с учетом эффекта всех последующих шагов [82].Анализ вычислительных характеристик известных алгоритмов реализацийточных методов [60, 75] показывает, что в настоящее время отсутствуютэффективные, то есть полиноминально сложные алгоритмы для практическизначимых задач дискретного программирования.Приближенные методы не гарантируют получение оптимального решениязадачи, но обеспечивают эффективное (за полиномиальное время) получениерешения, разумно близкого к оптимальному. Эти методы можно разделить наследующие четыре группы [105].711)Детерминированные методы.

К детерминированным методамотносят модификацию точных методов, которая ориентирует их на получениеприближенного решения. Такая модификация, например, может заключаться впрерывании процесса вычислений на определенном шаге решения. Кдетерминированным также относят методы локальной оптимизации, примеромкоторых являются так называемые «жадные» алгоритмы. Идея этих алгоритмовзаключается в последовательном формировании локальных оптимальныхрешений, когда на каждом шаге делается попытка достичь некоторой локальнойвспомогательной цели, но при этом отсутствует оценка результатов предыдущихили последующих шагов алгоритма [105].2)Методы случайного поиска.

Отличительной особенностью данныхметодов является случайный характер перебора допустимых решений. Кметодам случайного поиска относят эволюционные методы – отжига,генетические, роя частиц, колонии муравьев и т. д. [83].3)Методы решения задач специальной структуры. Эти методыоснованы на сведении задачи дискретного программирования к задачам, длякоторых разработаны специальные эффективные методы приближенногорешения.

Примером таких задач являются задачи целочисленного линейногопрограммирования, задача коммивояжера, задача размещения и т. д. [92].4)Эвристические методы. Данные методы заключаются в применениеразнообразных эвристик, которые используют неформальные предположения,специфичные для конкретной задачи. Под эвристиками понимаются разумныепредположения, обосновать которые научно не удается [57].Важная особенность всех приближенных методов решения заключается вследующем: невозможно доказать и не следует допускать, что приближенныйметод поиска решения при любых исходных данных найдет решение, близкое коптимальному. При решении задачи приближенными методами невозможнозаранее определить какой из методов даст результат наиболее близкий коптимальному.

Это можно установить только применив для решения задачисовокупность различных методов. В большинстве случаев этот прием не72является обременительным, поскольку все приближенные алгоритмы имеютполиномиальную сложность.Особенности постановок подзадач 1 – 3 (сложность и неопределенностьисходных данных) приводят к тому, что усилия по поиску их точных решений неявляется оправданным. На этом основании, решение задачи ПРЭ в диссертациипроизводим приближенными методами.3.4.Выводы по главе 31) Для решения подзадачи перспективного развития электросети разработанметод редукции задачи к совокупности трех вложенных подзадач глобальнойминимизации меньшей размерности, который предполагает разбиение исходнойзадачи на три подзадачи дискретного программирования:Подзадача 1 – определение числа и мест строительства новых РП и ТП;Подзадача 2 – определение варианта подключения новых потребителей кэлектросети;Подзадача 3 – определение варианта возможного подключения новых ТП,«построенных» при решении подзадачи 1, к существующей электросети.2) Разработан метод декомпозиции задачи перспективного развитияэлектросети на три подзадачи меньшей размерности (аналогичные подзадачам,выделяемымметодомдекомпозиции)изадачукоординации.Задачакоординации обеспечивает взаимодействие подзадач 1-3 путем введения висходную задачу ПРЭ вектора координирующих параметров.3) Выполнен анализ и оценка размерности векторов варьируемых параметровподзадач 1 – 3, на основании чего сделано заключение о невозможностиприменения точных методов решения задачи ПРЭ мегаполиса ввидунеприемлемо высоких вычислительных затрат.