Исследование методов оптимизации

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]. Рассмотрим методы прямого поиска:

модифицированный метод Хука-Дживса;

метод комплексов;

метод случайного поиска;

метод покоординатного спуска.