Анализ режимов работы электрических сетей ОАО "ММК им. Ильича" и разработка адаптивной системы управления режимами электропотребления

114

Министерство образования и науки Украины

Приазовский государственный технический университет

Факультет информационных технологий

Кафедра автоматизации энергетических систем и электропривода

Специальность “Системы управления производством и распределением электроэнергии”

МАГИСТЕРСКАЯ РАБОТА

по специальности 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 OAO MMK im. Iliicha

Considereded questions of optimization current mode electroconsumptions on reactive power and development adaptive managerial system by modes of electroconsumption.

Designeded software on determination of optimum states of working electric networks.

Offereded system to automation of process of distribution reactive power marketed on equipping the company Allen-Bradley.

Designeded system to automations produces the collection of necessary parameters, calculates the current mode, defines the optimum power compensating device and will send (pass) controlling influences 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 Версия программного обеспечения RSLinx Professional 86

4.4.3.7 Версия программного обеспечения RSLinx Gateway 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)< Wmax, уменьшить в два раза расстояние между xm и центром тяжести xцт, продолжать поиск, пока W(xm)<Wmax;

если xm - допустимая точка и W(xm)<Wmax, то перейти к шагу 4;

если xm - недопустимая точка, то перейти к шагу 3.

Шаг 3. Корректировка для обеспечения допустимости:

если xim<xiL(нижняя граница допускаемой области), то положить xim = xiL;

если 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<? <1, для переменной xi совместный случайный поиск требует испытаний. При 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 D xq-1, (1.13)

где ri - случайная величина, равномерно распределенная на интервале [-0,5;0,5].

Шаг 2.

если xp - недопустимая точка и p < P, то повторить шаг 1;

если xp - допустимая точка, то запомнить xp и W(xp) и

если p < P, то повторить шаг 1;

если 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<n;i++) g2+=g[i]*d[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<n;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)=Ax²+Bx+C, (1.26)

где А, В и С определяются из уравнений

Aб²+Bб+C=f_б,

Aв²+Bв+C=f_в,

Aг²+Bг+C=f_г. (1.27)

После преобразований этих уравнений получаем

A=[(г-в)f_б+(б-г)f_в+(в-б)f_г]--/--D,

B=[(в²-г²)f_б+(г²-б²)f_в+(б²-в²)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(x2), то x3 = x1 - D x;

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*)| < W, то закончить поиск. В противном случае к шагу 7;

если | Xmin - x*| < x, то закончить поиск. В противном случае к шагу 7.

Шаг 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.