В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.
Шаг 1. Найдем значения функции в вершинах симплекса:
f1=f( x1), f2=f(x2) ... fn+1=f(xn+1) (1.46)
Шаг 2. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg , наименьшее значение функции fl и соответствующие им точки xh, xg и xl.
Шаг 3. Найдем центр тяжести всех точек, за исключением точки xh. Пусть центром тяжести будет
(1.47)
и вычислим f(x0)=f0.
Шаг 4. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки x0, получим точку xr и найдем f(xr) = fr.
Операция отражения иллюстрируется рис. 1.6.
Рисунок 1.6 - Операция отражения
Если α>0 - коэффициент отражения, то положение точки xr определяется следующим образом:
xr-x0=α (x0-xh), т.е.
xr=(1+α)x0 -αxh. (1.48)
Замечание.
α= |xr-x0| / |x0 -xh|.
Шаг 5. Сравним значения функций fr и fl.
Если fr<fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe=f(xe). Рисунок 1.7. иллюстрирует операцию растяжения симплекса. Коэффициент растяжения γ1 можно найти из следующих соотношений: xe-x0=γ (xr-x0), т.е.
xe=γxr+ (1-γ)x0. (1.49)
Рисунок 1.7 - Операция растяжения
Замечание
γ=|xe-x0| / |xr-x0|
Если fe<fl, то заменяем точку xh на точку xe и проверяем (n+1)-ую точку симплекса на сходимость к минимуму (см. шаг 8). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг 2.
Если fe=fl , то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг 5, 1) проверить сходимость и, если она достигнута, вернуться на шаг 2.
Если fr>fl, но fr <=fgто xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг 2, т.е. выполняем пункт 1,б, описанный выше.
Если fr>fl и fr>fgто перейдем на шаг 6.
Шаг 6. Сравним значения функций fr и fh.
Если fr>f h, то переходим непосредственно к шагу сжатия 6,2.
Если fr<fh, то заменяем точку xh на точку xr и значение функции fh на значение функции fr. Запоминаем значение fr>f g из шага 5,2, приведенного выше. Затем переходим на шаг 6,2.
В этом случае fr>f h, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Пытаемся исправить это, найдя точку xc (а затем fс) с помощью шага сжатия, показанного на рис. 1.8.
Если fr>f h, то сразу переходим к шагу сжатия и находим точку xc из соотношения
xc-x0=β(xh-x0), (1.50)
где β(0<b<1)- коэффициент сжатия. Тогда
xc=βxh+(1-β)x0. (1.51)
Если fr<f h, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения
xc-x0=β(xr-x0), т.е.
xc=βxr+(1-β)x0. (1.52)
Шаг 7. Сравниваем значения функций fc и fh.
Если fc<f h, то заменяем точку xh на точку xc, и если сходимость не достигнута ,то возвращаемся на шаг 2.
Если fc>f h, то очевидно, что все наши попытки найти значение меньшее fh закончились неудачей, поэтому мы переходим на шаг 8.
На этом шаге мы уменьшаем размерность симплекса делением пополам расстояния от каждой точки симплекса до xl-точки, определяющей наименьшее значение функции.
Рисунок 1.8 - Шаг сжатия для fr>fh
Рисунок 1.9 - Шаг сжатия для fr<fh
Таким образом, точка xi заменяется на точку
,
т.е. заменяем точку xi точкой .
Затем вычисляем fi для i=1,2,...,(n+1), проверяем сходимость и, если она достигнута, возвращаемся на шаг 2.
Шаг 9. Проверка сходимости основана на том, чтобы стандартное отклонение (n+1) -го значения функции было меньше некоторого заданного малого значения. В этом случае вычисляется
, (1.53)
где .
Если σ<ε, то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции xl. Исходя из этого, такой критерий сходимости является разумным, хотя Бокс, Дэвис и Свенн предлагают то, что они считают более "безопасной" проверкой.
Коэффициенты αβγ в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать α=1, β=0.5 и γ=2. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.
Начальный симплекс выбирается на наше усмотрение. В данной программе точка x1 является начальной точкой, затем в программе формируются точки
x2=x1+ke1,
x3=x1+ke2,
xn+1=x1+ken, (1.54)
где k - произвольная длина шага,
ej - единичный вектор.
1.9 Метод неопределенных множителей Лагранжа
Естественно, что решение задач условной оптимизации значительно сложнее решения задач безусловной оптимизации [3]. Естественно стремление сведения задачи условной оптимизации (поиска относительного экстремума) к более простой задаче безусловной оптимизации (поиска абсолютного экстремума). Такая процедура осуществляется в методе Лагранжа. Рассмотрим сущность этого метода.
Необходимо найти условный экстремум нелинейной функции
(1.55)
n переменных, при m ограничениях
(1.56)
Ограничения-неравенства преобразуются в равенства, а свободные члены переносятся в левые части ограничений, т.е. система (1.56) приводится к виду
(1.57)
В соответствии с методом Лагранжа вместо относительного экстремума функции (1.55) при ограничениях (1.57) ищется абсолютный экстремум функции Лагранжа, которая имеет следующий вид:
(1.58)
где - неопределенные множители Лагранжа, являющиеся, как и переменные искомыми переменными.
Видно, что в функцию Лагранжа входит целевая функция плюс каждое ограничение, умноженное на множитель Лагранжа.
Доказано, что относительный экстремум целевой функции (1.55) при ограничениях (1.57) совпадает с абсолютным экстремумом функции Лагранжа (1.58).
Поиск абсолютного экстремума функции (1.58) выполняется известными методами. В частности, определяются и приравниваются к нулю частные производные функции Лагранжа:
(1.59)
Последние m уравнений представляют собой ограничения (1.57) оптимизационной задачи.
Система (1.59) содержит (m+n) уравнений и такое же количество неизвестных.
Решение системы (1.59) даст координаты абсолютного минимума функции Лагранжа (1.58) или относительного минимума целевой функции (1.55) при ограничениях (1.57).
Решение системы (1.59) выполняется известными методами вычислительной математики. Если система (1.59) линейная, используется, как правило, метод Гаусса. Если система (1.59) нелинейная - метод Ньютона.
1.10 Выбор метода оптимизации
Перед выбором метода оптимизации, проведем краткий анализ задач, которые должно решать разрабатываемое программное обеспечение:
программа должна решать задачу условной минимизации, т.е. находить относительный экстремум, так как в математической модели кроме линейных ограничений будут иметь место и нелинейные;
так как целевая функция - функция нескольких переменных, то она может иметь несколько экстремумов, и в этом случае программа должна осуществлять поиск локального минимума.
Проведя анализ наиболее часто использующихся методов оптимизации, для реализации поставленной цели был выбран градиентный метод квадратичного программирования, который представляет собой наиболее эффективный из вышеперечисленных градиентных методов, модифицированный с методами полиномиальной аппроксимации.
Предполагается, что целевая функция и граничные условия аппроксимируются квадратичными зависимостями или полиномами второго порядка. Более подробно этот метод будет рассмотрен далее в разделе "Разработка программного обеспечения метода оптимизации".
Данный метод позволяет создать надежную программу, соответствующую всем вышеперечисленным требованиям.
2. Разработка метода оптимизации по реактивной мощности
Требуемая в электроэнергетической системе (ЭЭС) суммарная мощность компенсирующих устройств определяется из уравнения баланса реактивной мощности (6.1). Эту мощность необходимо разместить в узлах электрической сети с минимальными затратами.
, (2.1)
где - суммарная реактивная мощность, генерируемая в ЭЭС, включая реактивную мощность, поступающую из соседних ЭЭС;
- суммарная реактивная мощность потребителей ЭЭС, включая реактивную мощность, отдавая в соседние ЭЭС;
- суммарная реактивная мощность собственных нужд электростанций;
- суммарные потери реактивной мощности;
- суммарное потребление реактивной мощности в ЭЭС.
Рассмотрим простейшую схему существующей сети (рис.2.1). от источника питания с напряжением U через сопротивление сети R получает питание нагрузка мощностью S=P+jQ [9]. На шинах нагрузки установлено компенсирующее устройство мощностью Qк.
Рисунок 2.1 - Простейшая схема компенсации реактивной мощности
Потери активной мощности в линии при отсутствии у потребителя компенсирующего устройства () составляют
. (2.2)
При установке у потребителя компенсирующего устройства () эти потери уменьшатся до величины
. (2.3)
Таким образом, компенсация реактивной мощности позволяет уменьшить потери активной мощности в схеме электроснабжения и, следовательно, улучшить технико-экономические показатели этой схемы.
Оценим влияние КУ на затраты в сети.
Выражение для суммарных затрат на передачу мощности к нагрузке при установке КУ будет иметь вид:
(2.4)
где ЗК - затраты на КУ;
соΔР - затраты на покрытие потерь активной мощности в сети;
со - стоимость единицы потерянной активной мощности;
зк - удельные затраты на КУ.
Для определения минимума функции З приравняем к нулю ее производную от переменной QK:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
