Министерствообразования и науки Украины
Приазовскийгосударственный технический университет
Факультетинформационных технологий
Кафедраавтоматизации энергетических систем и электропривода
Специальность“Системы управления производством и распределением электроэнергии”
МАГИСТЕРСКАЯ РАБОТА
по специальности 8.090615“Системы управления производством и распределением электроэнергии”
на тему: Анализрежимов работы электрических сетей ОАО «ММК им. Ильича» и разработкаадаптивной системы управления режимами электропотребления
Студент Трубчанинова Анна Васильевна
Руководитель
Нормоконтроль
Рецензент
Проект рассмотрен на заседании кафедры
и допущен к защите в ГЭК
Зав. кафедрой АЭС и ЭП
В.Н. Кравченко
Мариуполь 2006 г
«УТВЕРЖДАЮ»
Зав. кафедрой АЭС иЭП
_____________ В.Н.Кравченко
ЗАДАНИЕ
на аттестационнуюработу магистра Трубчанинова Анна Васильевна
1. Тема работы Исследование режимов работы электрическихсетей ОАО «ММК им. Ильича» и разработка адаптивной системы управлениярежимами электропотребления
Тема утверждена приказом по ПГТУ №12-05 от 1 февраля 2006г.
2. Цель исследования Определение оптимальных режимовработы электрических сетей. Разработка программного обеспечения для расчетаоптимальных режимов работы электрических сетей.
3. Исходные данные (характеристика объекта, условийисследования и др.)
Однолинейные схемы замещения электрических сетей. Графикинагрузок подстанций.
4. Основные задачи исследования:
Определить диапазон изменения параметров электрическихсетей и нагрузок в рабочих и типовых аварийных режимах.
Исследовать и выбрать наиболее эффективные методыоптимизации режимов сетей.
5. Срок представления работы к защите — 1 июня 2006 г.
6. Дата выдачи задания — 1 сентября 2005 г.
Научный руководитель _______________________
Задание принял к выполнению _________________
Календарный план
№
п/п Название этапа работы Срок выполнения этапа Примечание 1. Получение задания на дипломную работу. 02.10.2005 2. Обзор технической литературы по теме работы. 30.10.2005 3. Изучение и описание системы электроснабжения ММК им. Ильича 30.11.2005 4. Исследование режимов работы системы электроснабжения ММК им. Ильича 15.01.2006 5. Разработка программного обеспечения для решения задачи оптимизации режимов электроснабжения 15.02.2006 6. Составление полной схемы замещения системы электроснабжения ММК им. Ильича 10.03.2006 7. Расчет и оптимизация режимов электроснабжения ММК им. Ильича 20.03.2006 8. Разработка структурной схемы автоматизированной системы оптимального управления режимами электроснабжения ММК им. Ильича 1.04.2003 9. Выбор элементной базы для реализации автоматизированной системы оптимального управления 15.04.2006 10. Написание пояснительной записки. Создание слайдов для доклада 25.04.2006 11. Предварительная защита 28.05.2006 12. Коррекция работы по результатам предзащиты 01.06.2006 13. Окончательное оформление пояснительной записки и слайдов. 12.06.2006 14. Защита дипломной работы 19.06.2006
Студент _____________________________
Руководитель проекта _________________
Реферат
Пояснительная записка: 96 страниц, 25 рисунков, 21таблица, 3 приложения, 14 источников.
Объект исследования: электрическая сеть ОАО ММК им.Ильича
Рассмотрены вопросы оптимизации текущего режимаэлектропотребления по реактивной мощности и разработки адаптивной системыуправления режимами электропотребления.
Разработано программное обеспечение по определениюоптимальных режимов работы электрических сетей.
Предложена система автоматизации процесса распределенияреактивной мощности, реализованная на оборудовании фирмы Allen-Bradley.
Разработанная система автоматизации производит сборнеобходимых параметров, рассчитывает текущий режим, определяет оптимальныемощности компенсирующих устройств и передает управляющие воздействия наустройства, регулирующие мощности компенсирующих устройств.
ОПТИМИЗАЦИЯ, ЭЛЕКТРОПОТРЕБЛЕНИЕ, РЕАКТИВНАЯ МОЩНОСТЬ,АКТИВНАЯ МОЩНОСТЬ, ПОТЕРИ МОЩНОСТИ, АВТОМАТИЗАЦИЯ
Abstract
Explanatory note: 96 page, 25 drawings,21 tables, 3 exhibits, 14 sources.
Object of research: electric network OAOMMK im. Iliicha
Considereded questions of optimizationcurrent mode electroconsumptions on reactive power and development adaptivemanagerial system by modes of electroconsumption.
Designeded software on determination ofoptimum states of working electric networks.
Offereded system to automation ofprocess of distribution reactive power marketed on equipping the companyAllen-Bradley.
Designeded system to automationsproduces the collection of necessary parameters, calculates the current mode,defines the optimum power compensating device and will send (pass) controllinginfluences on device, regulative power compensating device.
OPTIMIZATION, ELECTROCONSUMPTION,REACTIVE POWER, ACTIVE POWER, LOSS a POWER, AUTOMATION
Содержание
Введение… 9
1 Исследованиеметодов оптимизации. 17
1.1 Основныепонятия и определения оптимизации. 17
1.2 Математическаямодель. 17
1.3 Методырешения оптимизационных задач. 19
1.3.1 Общаяхарактеристика методов решения задач нелинейного программирования 19
1.4 Методыпрямого поиска. 21
1.4.1 МетодХука-Дживса. 22
1.4.1.1 Исследующийпоиск. 23
1.4.1.2 Поиск пообразцу. 23
1.4.1.3 Описаниеалгоритма метода. 24
1.4.2 Методкомплексов. 25
1.4.3 Методыслучайного поиска. 27
1.4.4 Методпокоординатного спуска. 29
1.5 Градиентныеметоды… 30
1.5.1 Градиентныйметод с постоянным шагом. 31
1.5.2 Методскорейшего спуска. 32
1.5.3 Методпроектирования градиента. 35
1.6 Методштрафных функций. 38
1.7 Методыполиномиальной аппроксимации. 39
1.7.1 Квадратичнаяаппроксимация. 40
1.7.1.1 МетодПауэлла. 41
1.7.2 Кубическаяинтерполяция. 43
1.7.3 Квадратичныефункции. 46
1.8 МетодНелдера-Мида. 48
1.9 Методнеопределенных множителей Лагранжа. 54
1.10 Выбор методаоптимизации. 56
2 Разработкаметода оптимизации по реактивной мощности. 58
3 Разработкапрограммного обеспечения метода оптимизации. 66
4. Разработкаадаптивной системы управления режимами электропотребления 73
4.1 Функцииавтоматизированной системы… 73
4.2 Описаниеработы системы… 73
4.2.1 Ввод системыв работу. 73
4.2.2 Работасистемы в нормальном режиме. 74
4.2.3 Работасистемы в случае изменения конфигурации сети. 75
4.3 Требования коборудованию и программному обеспечению… 77
4.4 Выбороборудование для адаптивной системы… 78
4.4.1 Учетэлектроэнергии. 78
4.4.1.1 Устройствамониторинга PowerMonitor 79
4.4.1.2 Программноеобеспечение RSEnergy для контроля электропотребления 80
4.4.2 Процессордля диспетчерского пункта. 80
4.4.3 Сервер связи. 81
4.4.3.1 Основныепреимущества. 83
4.4.3.2 Минимальныетребования RSLinx: 84
4.4.3.3 Различиямежду разными версиями программного обеспечения RSLinx 84
4.4.3.4 Версияпрограммного обеспечения RSLinx Lite. 84
4.4.3.5 Версияпрограммного обеспечения RSLinx OEM… 85
4.4.3.6 Версияпрограммного обеспечения RSLinxProfessional 86
4.4.3.7 Версияпрограммного обеспечения RSLinxGateway. 87
4.4.3.8 Версияпрограммного обеспечения RSLinx SDK… 88
4.4.3.9 Графическиефункции SuperWho и RSWho. 89
5 Исследованиеи получение оптимальных режимов для ОАО «ММК им. Ильича» 90
5.1 Расчетпараметров схемы замещения. 90
5.1.1 Теоретическиеположения. 90
5.1.2 Расчетпараметров схем замещения линий. 93
5.1.3 Расчетпараметров схем замещения трансформаторов. 93
5.2 Расчет сетипри различных нагрузках. 100
Выводы… 103
Перечень ссылок… 104
Приложение А… 106
Приложение Б… 118
Введение
При исследовании режимов электрических сетей необходимообратить особое внимание на явления, связанные с передачей реактивной мощностипо сети, а также на способы ее компенсации.
В отличие от активной мощности реактивная мощность,потребляется элементами сети и электроприемниками в соизмеримых количествах. Приэтом она может генерироваться не только на электрических станциях, но и в сети.В частности, генерация реактивной мощности емкостью линий является вынужденной.
Реактивная мощность является практически удачной формойучета условий протекания периодических процессов в цепи переменного тока.Поскольку для обеспечения условий их протекания при допустимых параметра режимаприходится применять специальные компенсирующие устройства, то возникает задачаих наивыгоднейшего использования в условиях эксплуатации сети.
При решении этой задачи целесообразно прежде всеговыяснить, с какими дополнительными явлениями связана передача реактивноймощности по элементам сети и какое влияние эти явления оказывают натехнико-экономические показатели работы систем электроснабжения.
Как известно, передача реактивной мощности приводит кувеличению потерь напряжения в сети. С передачей реактивной мощностинепосредственно связано увеличение нагрузки в соответствующих элементах сети.
Отсюда следует также и увеличение потерь активноймощности в элементах системы электроснабжения, которое должно учитываться вбалансе по системе, т. е. компенсироваться соответствующей дополнительнойустановленной мощностью оборудования электрических станций.
Одновременно увеличиваются потери энергии за любойпромежуток времени. Дополнительный расход электроэнергии означаетдополнительный расход энергоносителей, практически — топлива, что связано сдополнительными денежными и материальными расходами.
Это означает, что для выполнения поставленной вначалезадачи в действительности требуется генерация соответственно большей реактивноймощности, т. е. практически установка дополнительных компенсирующих устройств.
Следует обратить внимание и на вторичное явление.Указанное выше увеличение потерь напряжения при неограниченной величине высшегодопустимого напряжения приводит к снижению его низшего значения у приемногоконца сети. А это приводит к увеличению значений токов при тех же значенияхпередаваемой мощности и к дополнительной потере активной и реактивной мощности,а также к дополнительной потере энергии.
При наличии соответствующих компенсирующих устройствцелесообразно компенсировать реактивную мощность на месте, по возможностиустраняя передачу ее по элементам сети на большие расстояния. Однако надо иметьв виду, что включение в работу новых устройств или увеличение нагрузки ужеработающих иногда приводит к увеличению потерь активной мощности в них.Наивыгоднейшее решение заранее может быть неизвестно и получается путемрасчета.
В распределительных сетях, особенно в промышленности,обычно имеет место потребление реактивной мощности в больших количествах.Основными потребителями реактивной мощности являются асинхронные двигатели,только намагничивающий ток которых составляет от 40 до 60% номинального.
Компенсирующие устройства (батареи конденсаторов), устанавливаемыев распределительных сетях, могут быть использованы для регулированиянапряжения. Это сокращает потребность в местных регулирующих устройствах.Поэтому экономичность работы компенсирующих устройств в распределительных сетяхследует рассматривать с учетом воздействия на режим напряжений.
При этом потери энергии в сети не обязательно получаютсянаименьшими, так же как и в случае распределения активной мощности междуэлектрическими станциями в энергетической системе. Наибольшим должен бытьрезультирующий экономический эффект.
Другое положение получается при использовании реактивноймощности, генерируемой синхронными двигателями, которые могут быть установленыв промышленной распределительной сети. Генерация реактивной мощностисинхронными двигателями приводит к аналогичном эффекту регулированиянапряжения, но связана со значительными потерями активной мощности, аследовательно, и энергии в самих двигателях. Поэтому регулирование напряжения автоматическимизменением тока возбуждения синхронных двигателей не всегда экономическиобосновано. Обычно использование для этого синхронных двигателей малой мощностиэкономически не оправдывается.
В питающей сети, на всех приемных подстанциях которойимеются регулирующие устройства с достаточным регулировочным диапазоном,распределение реактивной мощности можно осуществлять по условиям экономичностиработы самой питающей сети. Определяющими здесь являются условия минимумапотерь активной мощности в сети при заданных ограничениях по наибольшемудопустимому напряжению и рабочей реактивной мощности источников питания.
В послеаварийных режимах перераспределением реактивноймощности в сети часто удается улучшить параметры режима. При этом экономичностьрежима приходится рассматривать как факт второстепенный.
Комплексная проблема определения оптимальных условийэксплуатации энергосистем или энергообъединений должна решаться на основеиспользования экономического критерия минимизации приведенныхнароднохозяйственных затрат на производство и распределение электрической и тепловойэнергии. Решение этой проблемы в настоящее время осуществляется на основерассмотрения ряда взаимосвязанных задач, условно представленных на рисункениже.
Каждая из перечисленных задач характеризуется своимичастичным экономическим критерием и математической моделью поведенияэнергосистемы, которым отвечают определенные алгоритмы, наиболее полноучитывающие специфику задачи. В процессе решения используются различныеисходные данные, в значительной мере вероятностные и неравноточные.
Под задачей оптимизации текущего режима энергосистемы илиэнергообъединения понимают наивыгоднейшее распределение генерируемых активных иреактивных мощностей между электростанциями, а также другими регулируемымиисточниками реактивной мощности — синхронными компенсаторами, управляемымиреакторами и батареями статических конденсаторов, которому отвечает минимумэксплуатационных издержек И на производство и распределение электрической итепловой энергии в топливном или стоимостном выражениях: И(Z)=min. Целеваяфункция И зависит от вектора переменных Z, включающего в себя всю совокупностьпараметров режима.
В зависимости от принятой математической моделиоптимизации, определяемой частичной задачей оптимизации и допущениями присоставлении модели, в состав Z могут входить активные и реактивные мощностиэлектростанций />,коэффициенты трансформации (в общем случае комплексные) />, модули напряжений /> в некоторых или во всех узлах расчетнойсхемы, а при необходимости и другие параметры режима и оборудования.
/>
Рис. Взаимосвязь различных задач оптимизации режимов
Составляющие вектора Z связаны между собой рядомконкретных условий, накладываемых свойствами электрической сети, техническимихарактеристиками и условиями надежной работы оборудования. Сюда относятсяобеспечение баланса мощностей, ограничение напряжений в узлах, ограничение токаи передаваемой мощности по линиям электропередачи, допустимость режимов поустойчивости параллельной работы электростанций, ограничение мощностиэлектростанций по характеристикам оборудования и т. п.
В такой общей постановке задача оптимизации текущегорежима является многоэкстремальной задачей нелинейного математическогопрограммирования и для произвольного вида функции И(Z) строгие методы еерешения не разработаны.
Из изложенного следует, что определения оптимальногорабочего режима электрической сети в процессе ее текущей эксплуатации нужнозначительное количество информации о параметрах режима и требуется выполнениедостаточно сложных расчетов по ее обработке и получению ответа. В некоторыхслучаях задача должна решаться одновременно для всей энергетической системы.Для этого требуется достаточно сложное программное и аппаратное обеспечение,осуществляющее получение и обработку информации, а также управление всемиавтоматизированными устройствами, имеющимися в системе.
В своем дипломном проекте я оптимизирую текущий режимэнергосистемы, а именно, минимизирую целевую функцию путем решения задачинелинейного программирования на языке программирования С++.
Задача безусловной минимизации (минимизации безограничений) состоит в поиске минимума min f(х), где функция f: R"®R — является по крайнеймере непрерывной. Процедуры безусловной минимизации подразделяются на 3категории:
оперирующие функцией одной переменной;
работающие с функцией нескольких переменных;
использующие нелинейный метод наименьших квадратов.
В случае функции одной переменной предполагается, что наисследуемом отрезке она имеет один экстремум. В противном случае осуществляетсяпоиск локального минимума.
Поиск минимума функции нескольких переменных можновыполнить квазиньютоновским методом, модифицированным алгоритмом Ньютона,методом сопряженных градиентов и методом деформируемого многогранника.
Перечисленные процедуры обеспечивают поиск локальногоминимума. Если же функция имеет несколько локальных минимумов и необходимонайти наилучший, то следует испытать разные начальные точки и интервалы поиска.С процедурами, использующими только значения функции, следует употреблятьдвойную точность. Также полезно использовать процедуры контроля производной,обеспечивающие проверку работы пользовательских процедур, оценивающихпроизводные. Как уже указывалось, в настоящее время не существуетединообразного подхода к задаче оптимизации мгновенного режима энергосистемы.Все многообразие практических методов использования ЦВМ можно классифицироватьпо некоторым главным направлениям. Основными задачами расчетов могут являться:
а) комплексная оптимизация распределения активных иреактивных генерируемых мощностей и коэффициентов трансформации по условиюминимума суммарного расхода или стоимости топлива в системе;
б) оптимальное распределение активных мощностей междуэлектростанциями с приближенным учетом потерь в сети по условию минимумасуммарного расхода или стоимости топлива;
в) оптимальное распределение реактивных мощностей междуэлектростанциями и синхронными компенсаторами и выбор оптимальных коэффициентовтрансформации регулируемых трансформаторов по минимуму потерь в сети.
В расчетах в качестве математической моделиустановившегося режима используются либо полные уравнения установившегосярежима, обычно уравнения узловых напряжений в форме баланса мощностей в узлах,либо упрощенные уравнения баланса активной мощности в целом по системе
/>
1. Исследование методовоптимизации
1.1 Основные понятия и определения оптимизации
Показатель, по величине которого оценивают, является лирешение оптимальным, называется критерием оптимальности.[1] В качестве критерияоптимальности наиболее часто принимается экономический критерий, представляющийсобой минимум затрат (финансовых, сырьевых, энергетических, трудовых) нареализацию поставленной задачи. При заданной или ограниченной величинеуказанных затрат экономический критерий выражается в получении максимальнойприбыли.
В электроэнергетике в зависимости от требованийпоставленной задачи могут применяться и другие критерии оптимальности, вчастности:
критерий надежности электроснабжения;
критерий качества электроэнергии;
критерий наименьшего отрицательного воздействия наокружающую среду (экологический критерий).
Решение оптимизационной задачи включает в себя следующиеэтапы:
сбор исходной информации (исходных данных);
составление математической модели, под которой понимаетсяформализованное математическое описание решаемой задачи;
выбор метода решения, определяемого видом математическоймодели;
выполнение математических вычислений, поручаемое, какправило, компьютеру;
анализ решения задачи.
Математическаямодель
Математическая модель – формализованное математическоеописание оптимизационной задачи.[1,2] Математическая модель включает в себя:
целевую функцию;
ограничения;
граничные условия.
Целевая функция представляет собой математическую записькритерия оптимальности. При решении оптимизационной задачи ищется экстремумцелевой функции, например минимальные затраты или максимальная прибыль.Обобщенная запись целевой функции имеет следующий вид:
/> (1.1)
где />-искомые переменные, значения которых вычисляются в процессе решения задачи;
n — общее количество переменных.
Зависимость между переменными в целевой функции (1.1)может быть линейной или нелинейной.
Ограничения представляют собой различные технические,экономические, экологические условия, учитываемые при решении задачи[1,2].Ограничения представляют собой зависимости между переменными />, задаваемые в форме неравенств илиравенств
/> (1.2)
Общее количество ограничений равно m.
Граничные условия устанавливают диапазон измененияискомых переменных
/> /> (1.3)
где di и Di — соответственно нижняя и верхняя границыдиапазона изменения переменной хi.
Методырешения оптимизационных задач
Для решения подавляющего большинства оптимизационныхзадач используются методы математического программирования, позволяющие найтиэкстремальное значение целевой функции (1.1) при соотношениях междупеременными, устанавливаемых ограничениями (1.2), в диапазоне измененияпеременных, определяемом граничными условиями (1.3).
Математическое программирование представляет собой, какправило, многократно повторяющуюся вычислительную процедуру, приводящую кискомому оптимальному решению.[2,3]
Выбор метода математического программирования для решенияоптимизационной задачи определяется видом зависимостей в математической модели,характером искомых переменных, категорией исходных данных и количествомкритериев оптимальности.
Общаяхарактеристика методов решения задач нелинейного программирования
Когда целевая функция (1.1) и ограничения (1.2) нелинейныи для поиска точки экстремума нельзя или очень сложно использоватьаналитические методы решения, тогда для решения задач оптимизации применяютсяметоды нелинейного программирования. Как правило, при решении задач методаминелинейного программирования используются численные методы с применением ЭВМ[3,4,5,6].
В основном методы нелинейного программирования могут бытьохарактеризованы как многошаговые методы или методы последующего улучшенияисходного решения. В этих задачах обычно заранее нельзя сказать, какое числошагов гарантирует нахождение оптимального значения с заданной степеньюточности. Кроме того, в задачах нелинейного программирования выбор величинышага представляет серьезную проблему, от успешного решения которой во многомзависит эффективность применения того или иного метода. Разнообразие методоврешения задач нелинейного программирования как раз и объясняется стремлениемнайти оптимальное решение за наименьшее число шагов.
Большинство методов нелинейного программированияиспользуют идею движения в n-мерном пространстве в направлении оптимума. Приэтом из некоторого исходного или промежуточного состояния Uk осуществляетсяпереход в следующее состояние Uk+1 изменением вектора Uk на величину DUk,называемую шагом, т.е.
/> (1.4)
В ряде методов шаг, т.е. его величина и направлениеопределяется как некоторая функция состояния Uk
/> (1.5)
Следовательно, согласно (1.4) новое состояние Uk,получаемое в результате выполнения шага (1.5) может рассматриваться как функцияисходного состояния Uk
/> (1.6)
В некоторых методах DUk обусловлен не только состояниемUk, но и рядом предшествующих состояний
/> (1.7)
/> (1.8)
Естественно, что алгоритмы поиска типа (1.8) являютсяболее общими и принципиально могут обеспечить более высокую сходимость коптимуму, т.к. используют больший объем информации о характере поведенияоптимальной функции.
В настоящее время для решения подобных задач разработанозначительное число методов, однако нельзя отдать предпочтение какому- либоодному. Выбор метода определяется сложностью объекта и решаемой задачейоптимизации.
Методы решения задач нелинейного программирования(условной многопараметрической оптимизации) подразделяют следующим образом:
методы прямого поиска;
градиентные методы;
методы штрафных функций;
методы полиномиальной аппроксимации.
Методыпрямого поиска
Одними из методов нахождения минимума функцииn-переменных являются методы прямого поиска. Методы прямого поиска являютсяметодами, в которых используются только значения функции[1,7].
В методах прямого поиска ограничения учитываются в явномвиде. Необходимость разработки этих методов связана с тем, что в инженерныхприложениях часто приходится сталкиваться с случаями, когда целевые функции незаданы в явном виде. Эти методы строятся на интуитивных соображениях, неподкреплены строгой теорией и, следовательно, не гарантируется их сходимость.Несмотря на это, в силу своей логической простоты эти методы легко реализуются.
Перед непосредственным применением методов прямого поисканеобходимо провести ряд мероприятий по подготовке задачи к решению, а именно
исключить ограничения в виде равенств;
определить начальную допустимую точку.
Простейший способ исключения ограничений в виде равенствзаключается в решении его относительно одной из переменных с последующимисключением этой переменной путем подстановки полученного выражения всоотношения, описывающие задачу. При этом следует учитывать, что границызначений исключаемых переменных сохраняются в задаче в виде ограничений — неравенств.
Несмотря на то, что подстановка является самым простымспособом исключения ограничений — равенств, не всегда оказывается возможным ееосуществить. В этом случае проблема решается путем численного решения уравненияотносительно зависимых переменных при заданных значениях независимыхоптимизирующих переменных.
Для определения начальной допустимой точки целесообразноиспользовать процедуру случайного поиска, основная идея которого будетрассмотрена ниже.
После проведения процедуры подготовки задачи к решениюследует приметить один из методов условной оптимизации[5,6]. Рассмотрим методыпрямого поиска:
модифицированныйметод Хука-Дживса;
методкомплексов;
методслучайного поиска;
метод покоординатного спуска.
1.4.1 Метод Хука-Дживса
Одним из методов прямого поиска есть метод Хука-Дживса[5,7],который был разработан в 1961г, но до сих пор является весьма эффективным иоригинальным. Метод Хука-Дживса характеризуется несложной стратегией поиска,относительной простотой вычислений и невысоким уровнем требований к памяти ЭВМ.Это один из первых алгоритмов, в котором при определении нового направленияпоиска учитывается информация, полученная на предыдущих итерациях. ПроцедураХука-Дживса представляет собой комбинацию исследующего поиска с циклическимизменением переменных и ускоряющего поиска по образцу.
1.4.1.1 Исследующий поиск
Для проведения исследующего поиска необходимо знатьвеличину шага, которая может быть различной для разных координатных направленийи изменяться в процессе поиска. Исследующий поиск начинается в некоторойисходной точке. Если значение целевой функции в пробной точке не превышаетзначение в исходной точке, то шаг поиска рассматривается как успешный. Впротивном случае надо вернуться в предыдущую точку и сделать шаг впротивоположном направлении с последующей проверкой значения целевой функции.После перебора всех n- координат исследующий поиск завершается. Полученную врезультате точку называют базовой точкой.
1.4.1.2 Поиск по образцу
Поиск по образцу [5,6] заключается в реализацииединственного шага из полученной базовой точки вдоль прямой, соединяющей этуточку с предыдущей базовой точкой. Новая точка образца определяется всоответствии с формулой
Xp(k+1)=X(k)+(X(k)-X(k-1)). (1.9)
Как только движение по образцу не приводит к уменьшениюцелевой функции, точка Xp(k+1)фиксируется в качестве временной базовой точки ивновь проводится исследующий поиск. Если в результате получается точка сменьшим значением целевой функции, чем в точке X(k), то она рассматривается какновая базовая точка X(k+1). С другой стороны, если исследующий поиск неудачен,необходимо вернуться в точку X(k) и провести исследующий поиск с цельювыявления нового направления минимизации. В конечном счете возникает ситуация,когда такой поиск не приводит к успеху. В этом случае требуется уменьшитьвеличину шага путем введения некоторого множителя и возобновить исследующийпоиск. Поиск завершается, когда величина шага становится достаточно малой.Последовательность точек, получаемую в процессе реализации метода, можнозаписать в следующем виде:
X(k) — текущая базовая точка,
X(k-1)- предыдущая базовая точка,
Xp(k+1)- точка, построенная при движении по образцу,
X(k+1)- следующая (новая) базовая точка.
Приведенная последовательность характеризует логическуюструктуру поиска по методу Хука-Дживса.
1.4.1.3Описание алгоритма метода
Шаг 1. Выбрать начальную базисную точку b1 и шаг длинойhj для каждой переменной xj, j=1,2,...,n.
Шаг 2. Вычислить f(x) в базисной точке b1 с цельюполучения сведений о локальном поведении функции f(x). Функция f(x) в базиснойточке b1 находится следующим образом:
Вычисляется значение функции f(b) в базисной точке b1.
Каждая переменная по очереди изменяется прибавлениемдлины шага. Таким образом, мы вычисляем значение функции f(b1+h1*e1), гдеe1-единичный вектор в направлении оси х1.
Если это приводит к уменьшению значения функции, то d1заменяется на b1+h1*e1. В противном случае вычисляется значение функцииf(b1-h1*e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1*e1.
Если ни один из проделанных шагов не приводит куменьшению значения функции, то точка b1 остается неизменной и рассматриваютсяизменения в направлении оси х2, т.е. находится значение функции f(b1+ h2*e2) ит.д. Когда будут рассмотрены все n-переменныx, мы будем иметь новую базиснуюточку b2.
Если b2=b1, т.е. уменьшение функции не было достигнуто,то исследование повторяется вокруг той же базисной точки b1, но с уменьшеннойдлиной шага.
Если b2/>b1, то производится поиск по образцу.
Шаг 3. При поиске по образцу используется информация,полученная в процессе исследования, и минимизация функции завершается поиском внаправлении, заданном образцом. Эта процедура производится следующим образом:
Разумно двигаться из базисной точки b2 в направленииb2-b1, поскольку поиск в этом направлении уже привел к уменьшению значенияфункции. Поэтому вычислим функцию в точке образца
P1=b1+2*(b2-b1). (1.10)
В общем случае
Pi=bi+2*(b(i+1)-bi). (1.11)
Затем исследование следует продолжать вокруг точкиP1(Pi).
Если наименьшее значение на шаге B,2 меньше значения вбазисной точке b2(в общем случае b(i+1)), то получают новую базисную точку b3(b(i+2)), после чего следует повторить шаг B,1. В противном случае непроизводить поиск по образцу из точки b2(b(i+1)), а продолжить исследования вточке b2(b(i+1)).
Шаг 4. Завершить этот процесс, когда длина шага (длинышагов) будет уменьшена до заданного малого значения.
1.4.2 Метод комплексов
Алгоритм [7]:
Заданы границы значений всех переменных xiL, xiU,i=1,2,..., N (размерность задачи), допустимая точка xo, параметр отображения a(рекомендуется a =1,3) и параметры окончания вычислений и d .
Шаг 1. Построение начального комплекса, состоящего из Pдопустимых точек (рекомендуется P=2N). Для каждой точки p = 1, 2,...,P-1
случайным образом определить координаты xp;
если xp — недопустимая точка, то найти центр тяжести xцтуже найденных точек и положить xp = xp + (xцт — xp); повторять процедуру до техпор, пока xp не станет допустимой;
если xp — допустимая точка, повторять до тех пор, покаp=P;
вычислить W(xp) для p=0,1,...,P-1.
Шаг 2. Отражение комплекса:
выбрать точку xR, для которой W(xR) = max W(xp) = Wmax(решается задача минимизации);
найти центр тяжести xцт и новую точку xm = xцт + a (xцт — xR);
если xm — допустимая точка и W(xm)
если xm — допустимая точка и W(xm)
если xm — недопустимая точка, то перейти к шагу 3.
Шаг 3. Корректировка для обеспечения допустимости:
если xim
если xim>xiU(верхняя граница допускаемой области), тоположить xim = xiU;
если xm — недопустимая точка, то уменьшить в два разарасстояние до центра тяжести; продолжать до тех пор, пока xm не станетдопустимой точкой.
Шаг 4. Проверка условий окончания вычислений:
положить
/>
и
/>;
если
/>
и
/>,
то вычисления прекратить; в противном случае перейти кшагу 2a.
1.4.3 Методы случайного поиска
Наиболее простой процедурой случайного поиска [3,5] являетсяпрямая выборочная процедура, заключающаяся в разыгрывании на ЭВМпоследовательности точек с координатами
xi =xiL +ri (xiU — xiL), i=1,2,...,N, (1.12)
где ri — случайная величина, равномерно распределенная наинтервале [0,1].
После проверки каждой точки на допустимость вычисляютсязначения целевой функции, которые сравниваются с наилучшим значением,полученным к данному моменту. Если текущая точка дает лучшее значение, то оназапоминается, в противном — отбрасывается. Процесс прекращается после заданногочисла итераций N или по исчерпанию заданного машинного времени. Для получения90% доверительного интервала величиной i (xiU — xiL), где 0 испытаний. При N=5, i=0,01 число испытаний оценивается в 2,3 1010, что исключает возможностьнепосредственного использования метода.
Значительного увеличения эффективности процедурыслучайного поиска можно достигнуть путем группировки выборок в серии. При этомнаилучшая точка в каждой серии используется как начальная точка следующейсерии, точки которой уже выбираются из интервала меньшей величины. Даннаяпроцедура получила название выборки со сжатием пространства поиска. Рассмотримболее подробно ее алгоритм.
Заданы границы значений всех переменных xiL, xiU,i=1,2,..., N (размерность задачи), начальные допустимая точка xo и интервалпоиска D xo = xiU — xiL, количество серий Q, количество точек в серии P ипараметр окончания вычислений . Для каждой из серий, начиная с q = 1,необходимо выполнить следующие действия.
Шаг 1. Для i = 1,2,...,N вычислить
xip = xiq-1 +ri Dxq-1, (1.13)
где ri — случайная величина, равномерно распределенная наинтервале [-0,5;0,5].
Шаг 2.
если xp — недопустимая точка и p
если xp — допустимая точка, то запомнить xp и W(xp) и
если p
если p = P, то найти среди всех допустимых точек xp точкус наименьшим значением W(xp) и положить ее равной xq.
Шаг 3. Уменьшить интервал поиска, полагая D∙xiq = i∙D∙xiq-1.
Шаг 4.
Если q > Q, то закончить вычисления.
В противном случае увеличить q=q+1 и продолжитьвычисления, начиная с шага 1.
1.4.4 Метод покоординатного спуска
/>
Рисунок 1.1 — Метод покоординатного спуска
Рассмотрим функцию двух переменных. Ее линии уровняпредставлены на рис. 1.1, а минимум лежит в точке (x1*,x2*). Простейшим методомпоиска является метод покоординатного спуска[3,4]. Из точки А произведем поиск минимумавдоль направления оси х1 и, таким образом, находим точку В, в которойкасательная к линии постоянного уровня параллельна оси х1. Затем, производяпоиск из точки В в направлении оси х2, получаем точку С, производя поискпараллельно оси х2, получаем точку D, и т.д. Таким образом, мы приходим коптимальной точке. Очевидным образом эту идею можно применить для функции nпеременных.
Теоретически данный метод эффективен в случаеединственного минимума функции. Но на практике он оказывается слишком медленным.Поэтому были разработаны более сложные методы, использующие больше информациина основании уже полученных значений функции.
1.5 Градиентные методы
Как следует из названия, эти методы решения нелинейныхоптимизационных задач используют понятие градиента функции[3,5,7]. Градиентомфункции /> называетсявектор
/> (1.14)
где /> - единичные вектора (орты).
Величина этого вектора определяется по выражению
/> (1.15)
Из (1.14) и (1.15) видно, что функция, градиент которойопределяется, должна быть дифференцируемой по всем n переменным.
Физический смысл градиента функции в том, что онпоказывает направление (1.14) и скорость (1.15) наибольшего изменения функции врассматриваемой точке. Если в некоторой точке />, функция в этой очке не изменяется (не возрастает ине убывает). Эта точка соответствует экстремуму функции.
1.5.1 Градиентный метод с постоянным шагом
Сущность градиентных методов решения нелинейныхоптимизационных задач [1,5,7] поясним для случая отыскания абсолютного минимумафункции двух переменных />, иллюстрируемого рис. 1.2. этот минимум находится вточке с координатами х10 и х20.
/>
Рисунок 1.2 – Иллюстрация градиентного метода спостоянным шагом />
В соответствии с граничными условиями (1.3), вбольшинстве практических оптимизационных задач они принимают толькоположительные или нулевые значения, областью /> допустимых значений переменных будет первыйквадрант системы координат х1 и х2. в этой области произвольно выберем исходное(нулевое) приближение – точку с координатами х10, х20. значение целевой функциив этой точке составляет Z0. В соответствии с выражением (1.15) вычислим в этойточке величину градиента функции Z.
Выполним шаг единичной длины (/>) в направлении убывание функции Z. Врезультате выполненного шага получим первое приближение – точки с координатамих11, х21. Значение целевой функции в этой точке составляет Z1.
Далее вычислительная процедура повторяется:последовательно получаем 2-е, 3-е и 4-е приближения – точки с координатами х12,х22; х13, х23 и х14, х24. Значения целевой функции в этих точках соответственносоставляют Z2, Z3 и Z4.
Из рис. 1.2 видно, что в результате вычиcлительногопроцесса последовательно осуществляется «спуск» к минимуму функции Z.Вычислительная процедура заканчивается, когда относительное изменение целевойфункции на предыдущем i-м и последующем (i+1)-м шагах оказывается меньшезаданной точности вычислений />:
/> (1.16)
Рассмотренная вычислительная процедура носит названиеградиентного метода с постоянным шагом. В этом методе все шаги выполнялисьодинаковой длины />.Метод достаточно прост. Основной его недостаток – большая вероятностьзацикливания вычислительного процесса в окрестности минимума функции Z. Всоответствии с рис. 1.2 вычислительный процесс зациклится между точками с координатамих13, х23 и х14, х24. При этом в качестве искомого решения следует принять однуиз этих точек.
Для получения более точного результата необходимо выбратьшаг меньшей длины. При этом объем вычислений (количество шагов) увеличится.
Таким образом, точность и объем вычислений в градиентномметоде с постоянным шагом определяются величиной этого шага.
1.5.2Метод скорейшего спуска
Как было отмечено выше, при увеличении длины шага объемвычислений (количество шагов) уменьшается, однако уменьшается и точностьопределения минимума целевой функции. При уменьшении длины шага точностьувеличивается, однако объем вычислений (количество шагов) возрастает.
Поэтому вопрос о выборе рациональной длины шага в градиентныхметодах является своего рода оптимизационной задачей. Один из способовопределения оптимальной длины шага /> иллюстрируется на рис. 1.3 и носит название методаскорейшего спуска [1,7].
/>
Рисунок 1.3 – Иллюстрация метода скорейшего спуска (а) ипараболическая аппроксимация целевой функции для выбора оптимального шага (б)
В методе наискорейшего спуска желательно использоватьрассмотренное свойство направления градиента. Поэтому, если мы находимся вточке хi на некотором шаге процесса оптимизации, то поиск минимума функцииосуществляется вдоль направления -/>. Данный метод является итерационным. На шаге iточка минимума аппроксимируется точкой хi. Следующей аппроксимацией являетсяточка
/> (1.17)
где λi — значение λ, минимизирующее функцию.
/>. (1.18)
Значение λi может быть найдено с помощью одного изметодов одномерного поиска (например, методом квадратичной интерполяции).
В приложении приведена программа, позволяющая реализоватьметод наискорейшего спуска. В ней множитель Лагранжа обозначен через h. Векторdi является единичным.
Для поиска минимума функции
/> (1.19)
в направлении di из точки xi используется методквадратичной интерполяции.
В точке />, и мы выбираем длину шага λ такой, чтобы шаг«перекрыл » минимум функции φ(λ). Производная
/>. (1.20)
Данный оператор for(i=0;i
/>. (1.21)
Оператор if (ff[2]>=ff[0] || g2>=0) проверяетусловие «перекрытия» минимума, которое выполняется при выполнениилибо одного, либо другого условия. Если минимум не попал в отрезок (0,λ),то λ удваивается, и это повторяется столько раз, сколько необходимо длявыполнения условия «перекрытия».
Удостоверившись, что отрезок (0,λ) содержит минимум,в качестве третьей точки возьмем точку λ/ 2. Минимальную точкусглаживающего квадратичного полинома находим в соответствии с соотношением
/> (1.22)
что отражено следующими операторами
l[3]=h*(ff[1]-.75*ff[0]-.25*ff[2]);
l[3]/=2*ff[1]-ff[0]-ff[2];
Оператор for(i=0;i
{ x[i]=y[i]+l[0]*d[i]; y[i]=x[i]; }
производит присваивание xi+1=xi, и если |g(xi+1)|достаточно мало, то процесс заканчивается. В процессе поиска предполагаетсясходимость к экстремуму, поэтому для эффективности процедуры разумно уменьшитьдлину шага. При этом деление шага пополам выбрано произвольно.
В методе скорейшего спуска, по сравнению с градиентнымметодом с постоянным шагом, количество шагов меньше, точность получаемогорезультата выше, отсутствует зацикливание вычислительного процесса, однакообъем вычислений на одном шаге больше.
1.5.3 Метод проектирования градиента
Рассмотренные выше градиентные методы предполагалиотыскание абсолютного минимума целевой функции Z. При наличии в математическоймодели нелинейных ограничений ищется уже не абсолютный, а относительный минимумцелевой функции Z [1].
Рассмотрим один из методов отыскания относительногоминимума целевой функции, получивший название метода проектирования градиента.
Для упрощения алгоритма допустим, что имеется одноограничение в виде линейного неравенства
/> (1.23)
При наличии указанного ограничения минимум целевойфункции следует искать в области />, расположенной по одну сторону от прямой />например выше этойпрямой (рис. 1.4).
Начало вычислительной процедуры такое же, как и впредыдущих методах:
в области /> принимается исходное (нулевое) приближение х10,х20;
вычисляется значение целевой функции в этой точке Z0;
в соответствии с выражением (1.15) в этой точкевычисляется градиент целевой функции grad Z;
из исходной точки в направлении убывания целевой функциивыполняется шаг.
/>
Рисунок 1.4 – Иллюстрация метода проектирования градиента
Выбор величины шага может осуществляться различнымобразом. Выберем шаг в соответствии с алгоритмом метода скорейшего спуска иполучим первое приближение – точку с координатами х11, х21. Вычисляетсязначение целевой функции в этой точке Z1.
Необходимо проверить, принадлежит ли точка с координатамих11, х21 области /> допустимыхзначений переменных. Для этого проверяется неравенство (1.23), в котороеподставляются координаты х11, х21:
/> (1.23)
Если это неравенство выполняется, вычислительный процесспродолжается.
Из точки с координатами х11, х21 выполняется следующийшаг. В результате этого шага имеем второе приближение – точку с координатамих12, х22. значение целевой функции в этой точке Z2.
Пусть для этой точки неравенство /> не выполняется. Следовательно, точка скоординатами х12, х22 вышла из области /> и необходимо выполнить возврат в эту область.
Возврат в область /> выполняется следующим образом. Из точки скоординатами х12, х22 опускается перпендикуляр на прямую /> т.е. конец вектора (х11, х21;х12, х22) проектируется на эту прямую. В результате получается новоеприближение – точка с координатами х13, х23, которая принадлежит области />. В этой точкевычисляется значение целевой функции Z3.
Дальнейший спуск к относительному минимуму целевойфункции продолжается из точки х13, х23. на каждом шаге вычисляется значениецелевой функции и проверяется принадлежность нового приближения к области />. Вычислительный процессзаканчивается при выполнении условия (1.16).
1.6 Метод штрафных функций
Рассмотрим задачу поиска локального минимума критерияоптимальности W в области, ограниченной системой неравенств (3.16)-(3.17).Введение обобщенного критерия оптимальности по методу штрафных функций [3,5] производитсяс помощью непрерывной функции
/>. (1.24)
Обобщенным критерием оптимальности согласно методуштрафных функций является выражение
T=W+RQ(x),
где R — некоторое положительное число, называемоекоэффициентом штрафа.
Рассматривается некоторая неограниченная, монотонновозрастающая последовательность {Rk}, k=1,2,… положительных чисел. Дляпервого элемента этой последовательности с помощью метода покоординатногоспуска отыскивается локальный минимум функции T. Пусть этот минимум достигаетсяпри значениях (b*,R1).
Вектор (b*,R1) используется как начальное приближение длярешения задачи поиска минимума функции T где R2>R1 и т.д. Таким образом,решается последовательность задач минимизации функций T(b*,Rk), k=1,2 ...,причем результат предыдущей оптимизации используется в качестве начальногоприближения для поиска последующей.
/>
Рисунок 1.5 – Блок-схема метода штрафных функций
1.7 Методы полиномиальной аппроксимации
Согласно теореме Вейерштрасса об аппроксимации,непрерывную функцию в некотором интервале можно аппроксимировать полиномомдостаточно высокого порядка [6]. Следовательно, если функция унимодальна инайден полином, который достаточно точно ее аппроксимирует, то координаты точкиоптимума функции можно оценить путем вычисления координаты точки оптимумаполинома.
Рассмотрим следующие вопросы:
квадратичнаяаппроксимация;
кубическаяинтерполяция;
квадратичныефункции.
1.7.1 Квадратичная аппроксимация
Используется несколько значений функции в определенныхточках для аппроксимации функции обычным полиномом по крайней мере в небольшойобласти значений. Затем положение минимума функции аппроксимируется положениемминимума полинома, поскольку последний вычислитель проще.
Простейший случай основан на том факте, что функция,принимающая минимальное значение во внутренней точке интервала, должна быть покрайней мере квадратичной.
Если целевая функция W(x) в точках x1, x2, x3 принимаетсоответствующие значения W1, W2, W3, то можно определить коэффициенты aо, a1,a2 таким образом, что значения квадратичной функции
q(x)= ao + a1(x — x1) + a2(x — x1)(x — x2) (1.25)
совпадут со значением W(x) в трех указанных точках.Вычислим q(x) в трех указанных точках (см. табл.1.1).
Таблица 1.1 — Вычисление значений
/>
/>
/>
/>
/>
/>
/>
/>
1.7.1.1Метод Пауэлла
Если известны значения функции f(x) в трех разных точках α,β, γ равные соответственно fα, fβ,fγ, то функция f(x) может быть аппроксимирована квадратичнойфункцией
ö(x)=Ax2+Bx+C,(1.26)
где А, В и С определяются из уравнений
Aá2+Bá+C=fá,
Aâ2+Bâ+C=fâ,
Aã2+Bã+C=fã. (1.27)
После преобразований этих уравнений получаем
A=[(ã-â)fá+(á-ã)fâ+(â-á)fã] / D,
B=[(â2-ã2)fá+(ã2-á2)fâ+(á2-â2)fã] / D,
C=[âã(ã-â)fá+ãá(á-ã)fâ+áâ(â-ã)fã] / D, (1.28)
где D=(á-â)(â-ã)(ã-á)
Ясно, что φ(x) будет иметь минимум в точке
x=-B/2A,
если А>0. Следовательно, можно аппроксимировать точкуминимума функции f(x) значением
/> (1.29)
Этот метод может непосредственно применяться к функциямодной переменной. Он может быть очень полезен для выполнения линейного поиска впроцедурах, описанных в теме №3. В этих процедурах требуется найти минимумфункции f(x) в точках прямой x0+λd, где x0- заданная точка, а d определяетзаданное направление. Значение функции f(x0+λd) на этой прямой являетсязначениями функции одной переменной λ:
φλ= f(x0+λd). (1.30)
Идеи и результаты, изложенные выше, преобразуются ввычислительные процедуры, описанные далее. Предположим, что заданы унимодальнаяфункция одной переменной f(x), начальная аппроксимация положения минимума идлинна шага D, является величиной того же порядка, что и расстояние от точки Адо точки истинного минимума x*(условие, которое не всегда простоудовлетворить). Вычислительная процедура имеет следующие шаги:
Шаг 1. x2 = x1 + D x.
Шаг 2. Вычислить W(x1) и W(x2).
Шаг 3.
если W(x1) > W(x2), то x3 = x1 + 2 D x;
если W(x1)
W(x1) > W(x2),
Шаг 4. Вычислить W(x3) и найти
Wmin = min{ W(x1),W(x2), W(x3)},
Xmin = xi, соответствующая Wmin.
Шаг 5. По x1, x2, x3 вычислить x*, используя формулу дляоценивания с помощью квадратической аппроксимации.
Шаг 6. Проверка окончания
если | Wmin — W(x*)|
если | Xmin — x*|
Шаг 7. Выбрать Xmin или x* и две точки по обе стороны отнее. Обозначить в естественном порядке и перейти к шагу 4.
Заметим, что если точка Езадана слишком малой, то á,â, ã, а также fá, fâ, fã будут очень близко друг к другу и значение d(1.29) может стать вообще недостижимыми. Чтобы преодолеть эту трудность,перепишем (1.29) для второй и последней интерполяции:
/> (1.31)
1.7.2 Кубическая интерполяция
Квадратичная интерполяция, которая рассматривалась впредыдущем разделе, называется методом Пауэлла и аппроксимирует функциюквадратным трехчленом. В этом разделе рассматривается метод Давидона [6,7],который гарантирует большую точность и аппроксимирует функцию кубическимполиномом.
Для кубической интерполяции в этом методе используютсязначения функции и ее производной, вычисленных в двух точках.
Рассмотрим задачу минимизации функции f(x) на прямой x0 +hd, то есть минимизацию функции
/> (1.32)
Предположим, что известные следующие значения:
/> (1.33)
Эту информацию можно использовать для построениякубического полинома a+bh+ch2+dh3, который будет аппроксимировать функцию φ(h)Если p=0, то уравнения, которые определяют a, b, c, d имеют вид :
/> (1.34)
Следовательно, если r является точкой минимумакубического полинома,
/> (1.35)
где
/>
Одно из значений этого выражения является минимумом.Друга производная равна 2c +6dh.
Если мы выберем положительный знак, то при
/>
другая производная будет
/> (1.36)
/> (1.37)
Выбор точки q зависит от нас. Если Gp >0, то надовыбрать значение q положительным, то есть сделать шаг в направлении уменьшенияфункции φ(h), в другом случае значения q надо выбиратьотрицательным. Значение должно быть таким, чтобы интервал (0, ) включал в себяминимум. Это будет верным, если φq > φ p или Gp >0.
Если ни одно из этих условий не исполняется, то мыудваиваем значения q, повторяя это в случае необходимости, пока указанныйинтервал не будет содержать в себе минимум.
Давидон, Флетчер и Пауэлл предложили выбирать q следующимпутем:
/> (1.38)
где φm — оценка самого малого значения истинногоминимума φ(h),
h-константа, значение которой обычно берут 2 или 1.
1.7.3Квадратичные функции
Квадратичная функция [7,8]
/> (1.39)
где a — константа;
b — постоянный вектор;
G — положительно определенная симметричная матрица — имеет минимум в точке x*, где x* определяется следующим путем:
/> (1.40)
откуда
/>
Любую функцию можно аппроксимировать в окрестности точкиx0 функцией
/> (1.41)