Оптимальная система автоматического управления

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Оптимальная система автоматического управления

Оптимальная система автоматического управления

Федеральное агентство по образованию

ГОУ ВПО «Московский Государственный Открытый Университет»

Чебоксарский политехнический институт

Кафедра: Управление и информатика в технических системах

специальность 220201

Курсовая работа

Оптимальная система автоматического управления

Выполнил: студент V курса д/о

ФУИТС шифр: 604020

Белоусов А.В.

Проверил: пр. Изосимова Т.

• Введение
• Задание
• 1. Анализ методов определения минимального, максимального значения функции без ограничения
• 1.1 Методы прямого поиска
• 1.2 Градиентные методы
• 1.3 Методы второго порядка
• 2. Нахождение экстремума функции без ограничения
• 2.1 Метод наискорейшего спуска
• 2.2 Метод сопряженных направлений
• 3. Анализ методов определения минимального, максимального значения функции при наличии ограничений
• 3.1 Методы возможных направлений
• 3.2 Методы проекции градиента
• 3.3 Методы линеаризации
• 3.4 Методы штрафов
• 4. Нахождение экстремума функции при наличии ограничения
• 4.1 Метод симплексных процедур
• 5. Синтез оптимальной по быстродействию системы с помощью принципа максимума Понтрягина
• Звулючение
• Список литературы
• Приложение
• Введение

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

Эффективность оптимизационных методов, позволяющих осуществить выбор наилучшего варианта без непосредственной проверки всех возможных вариантов, тесно связана с широким использованием достижений в области математики путем реализации итеративных вычислительных схем, опирающихся на строго обоснованные логические процедуры и алгоритмы, на базе применения вычислительной техники. Поэтому для изложения методологических основ оптимизации требуется привлечение важнейших результатов теории матриц, элементов линейной алгебры и дифференциального исчисления, а также положений математического анализа. Математические понятия и конструкции используются не только для того, чтобы повысить уровень строгости представления материала, но и потому, что они составляют терминологическую базу изложения, которая позволяет упростить описание и определение структурных элементов рассматриваемых вычислительных процедур и облегчить их понимание.

Поскольку размерность инженерных задач, как правило, достаточно велика, а расчеты требуют значительного времени, оптимизационные методы ориентированы главным образом на реализацию с помощью ЭВМ.

Задание

Вариант 2

Дана несепарабельная функция двух переменных:

,

где .

Дана начальная точка поиска -, где .

Получим функцию:

.

1) Найти безусловный экстремум функции f(x,y) методами:

- наискорейшего спуска;

- сопряженных направлений.

Точность вычислений:

/xi+1-xi/<0.01

/yi+1-yi/<0.01

/f(xi+1,yi+1)-f(xi,yi)/<0.01

2) Найти условный экстремум функции f(x,y) методом симплексных процедур при наличии следующих ограничений:

3) Выполнить синтез оптимальной по быстродействию системы с помощью принципа максимума Понтрягина (критерий по быстродействию), передаточная функция объекта имеет вид:

, где K=1, Т=1.

- разработать модель для данного типа ОСАУ;

- провести исследование ОСАУ с применением программного продукта

“20 Sim Pro 2.3”;

- снять переходные и импульсные характеристики.

1. Анализ методов определения минимального, максимального значения функции без ограничения

В данном разделе будет рассматриваться задача безусловной оптимизации, т.е. данная задача характеризуется тем, что минимум функции f: Rm ? R ищется на всем пространстве:

f(x) ? min, x ? Rm.

Методы безусловной оптимизации функции многих переменных отличаются относительно высоким уровнем развития по сравнению с другими методами нелинейного программирования. Условно их можно разбить на три широких класса по типу используемой информации:

1) Методы прямого поиска, основанные на вычислении только значений целевой функции.

2) Градиентные методы, в которых используются точные значения первых производных f (x).

3) Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f (x).

Метод поиска по симплексу

Процедура симплексного метода базируется на регулярном симплексе. Регулярный симплекс в N-мерном пространстве представляет собой многогранник, образованный N+1 равностоящими друг от друга точками - вершинами. Так в задаче с двумя переменными симплексом является равносторонний треугольник, с тремя - тетраэдр.

Работа алгоритма симплексного поиска начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой из вершин симплекса. При этом отбрасывается вершина, которой соответствует наибольшее значение целевой функции.

Преимущества метода:

· сравнительная простота логической структуры метода и, соответственно, программы для ЭВМ;

· используется сравнительно небольшое число заранее установленных параметров;

· невысокий уровень требований к ЭВМ.

· алгоритм эффективен даже в тех случаях, когда ошибка вычисления значений целевой функции велика, т.к. при его реализации используют наибольшие значения функции в вершинах, а не меньшие.

Недостатки метода:

· возникает проблема масштабирования, поскольку все координаты вершин симплекса зависят от одного масштабного множителя. Чтобы избежать такого рода проблем в практических задачах, следует промасштабировать все переменные с тем, чтобы их значения были сравнимы по величине;

· алгоритм работает достаточно медленно, т.к. полученная на предыдущих итерациях информация не используется для ускорения поиска;

· не существует простого способа расширения симплекса. Требуется перерасчет значений целевой функции во всех точках образца.

Метод поиска Хука-Дживса

Процедура поиска Хука-Дживса представляет собой комбинацию "исследующего поиска" и "ускоряющего поиска по образцу".

Исследующий поиск ориентирован на выявление локального характера поведения целевой функции и определение направлений вдоль "оврагов". Для проведения исследующего поиска необходимо задать величину шага, которая может быть различной для разных координатных направлений и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превышает значение функции в исходной точке, то шаг поиска рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположное направление с последующей проверкой значения целевой функции. После перебора всех N координат исследующий поиск завершается. Полученную в результате точку называют "базовой точкой".

Поиск по образцу заключается в реализации единственного шага из полученной базовой точки xk вдоль прямой, соединяющей эту точку с предыдущей базовой точкой xk-1. Новая точка образца xk+1 определяется в соответствии с формулой

xk+1 = xk + (xk - xk-1).

Как только движение по образцу не приводит к уменьшению целевой функции, точка xk+1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке xk, то она рассматривается как новая базовая точка xk+1.

С другой стороны, если исследующий поиск неудачен, то необходимо вернуться в точку xk и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете, возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и продолжить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой.

Рис. 1.1 - Метод поиска Хука-Дживса

Преимущества метода:

· несложная стратегия поиска;

· невысокий уровень требований к ЭВМ;

· широкое применение в инженерных приложениях.

Недостатки:

· при значительных нелинейных эффектах алгоритм вырождается в последовательность исследующих поисков без переходов к ускоряющему поиску по образцу.

Метод сопряженных направлений

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), xEn, где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением f(x*)=0.

Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), xEn, где f(x) является целевой функцией n независимых переменных.

Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений

Методы решения задач с ограничениями типа равенств.

Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)-(3.2) основывается на необходимом условии экстремума -- правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)-(3.2) соответствует экстремум (x*, ?*) функции Лагранжа L, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле, если в точке x ограничения не выполняются, то за счет выбора ? функцию L (поскольку по ? она линейна) можно сделать как сколь угодно большой положительной, так и сколь угодно большой отрицательной. Поэтому естественно искать решение x* как первые m координат стационарной точки функции Лагранжа, например, методом Ньютона, мы приходим к методу Ньютона решения задач с ограничениями типа равенств -- это просто метод Ньютона решения уравнения L?(x, ?) = ? (в регулярном случае):

L?(xn, ?n) + L??(xn, ?n)(xn+1 ? xn, ?n+1 ? ?n) = ?

в "координатной" форме

L?x(xn,?n) + L??xx(xn,?n)(xn+1 ? xn) + L??x?(xn,?n)(?n+1 ? ?n) = ?,

L??(xn,?n) + L??x?(xn,?n)(xn+1 ? xn) + L????(xn,?n)(?n+1 ? ?n) = ?.

Остается подставить в эти уравнения явные выражения производных функции Лагранжа (учитывая, в частности, что L????(xn,?n) = ?):

f ?0(xn)+ [f ?(xn)]*?n + (f ??0(xn)+ ?nif ??i(xn)) (xn+1 ? xn) + [f ?(xn)]*(?n+1 ? ?n) = ?,f(xn) + f ?(xn)(xn+1 ? xn) = ?

и мы получаем m+k линейных уравнений для нахождения m+k неизвестных (xn+1, ?n+1).

Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи (3.1)-(3.2). Поскольку, как сказано выше, точка (x*, ?*) - это седловая точка функции Лагранжа, то естественно пытаться с помощью градиентного метода минимизировать ее по x, одновременно максимизируя ее по ?:

xn+1 = xn ? ?L?x(xn,?n), ?n+1 = ?n + ?L??(xn,?n),

или, что то же xn+1 = xn ? ?(f ?0(xn)+ [f ?(xn)]*?n), ?n+1 = ?n + ?f(xn).

Можно доказать, что этот метод (его обычно называют методом Эрроу -- Гурвица) при естественных ограничениях на гладкость и при условии положительной определенности оператора L??xx(x*,?*) локально линейно сходится.

Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные (?) переменные.

Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xn+1 ищется как минимум функции x ? (f ?0(xn),x ? xn) + ?||x ? xn||2 на касательной гиперплоскости ??xn. Здесь "штрафной член" ?||x ? xn||2 позволяет "минимизировать" линейную функцию x ? (f ?0(xn),x ? xn). Таким образом, мы приходим к прямому методу

xn+1 = argmin [(f ?0(xn),x ? xn) + ?||x ? xn||2], (3.4)

fi(xn) + (f ?i(xn),x ? xn) = 0, i = 1, ..., k. (3.5)

Ограничения (3.5) в этом методе -- это, очевидно, линеаризации ограничений (3.2) в точке xn: минимум ищется на касательной гиперплоскости ??xn.

Один из распространенных методов решения задач с ограничениями, с которым мы еще столкнемся -- так называемый метод штрафов. Он позволяет сводить задачу с ограничениями к задаче без ограничений и суть его заключается в наказании за невыполнение ограничений. Именно, вместо минимизации функции f0 с ограничениями (3.2) минимизируется функция fs(x) = f0(x) + s||f(x)||2 без ограничений, в которой s -- положительный параметр.

Теперь рассмотрим постановку задач с ограничениями типа неравенств gj(x) ? 0, j = 1, ..., l (6).

Рис. 3.2

Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (3.1)- (3.3), (3.6) можно записывать в виде

f(x) = ?, g(x) ? ?.

(напомним, что неравенство g(x) ? ? означает покоординатные неравенства).

f0(x) ? min, f(x) = ?, g(x) ? ?.

Через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j ? {1, ..., l}: gj(x) = 0} -- это номера ограничений, которые в данной точке существенны.

Теорема (обобщенное правило множителей Лагранжа).

Пусть f0, f, g ? C1, а x* -- локальное решение задачи f0(x) ? min, f(x) = ?, g(x) ? ?. Тогда найдутся такие ?*0 ? R, ?* ? Rk, ?* ? Rl, не равные одновременно нулю, такие, что ?*j ? 0 при j ? J(x*) и

?*0 f ?0(x*)+ ??*i f ?i(x*)+??*j g?j(x*) = ?. (3.7)

Регулярный случай.

Так же, как и в случае ограничений-равенств, в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если ?*0? 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (3.7) на ?*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: RmЧRkЧRk ? R (в регулярном случае) равенством

(x, ?, ?) = f0(x) + (?, f(x)) + (?, g(x)).

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ?1(x),..., f ?k(x) линейно независимы и для некоторого ненулевого вектора

h?Rm (f ?i(x),h) = 0 при i = 1, ..., k и (g?j(x),h) < 0 при j ? J(x).

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ?i(x)),и, во-вторых, он образует с градиентами g?j(x)активных ограничений (указывающими, очевидно, вовне множества ?) тупой угол

Рис. 3.3

Основная идея здесь заключается в переходе от задачи (1), (3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества ? допустимых точек (внешний штраф), либо приближение изнутри множества ? к его границе (внутренний штраф). Различают методы внешних штрафов и внешних штрафов. При методе внешних штрафов задачу решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности s. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества ? возводятся барьеры, не позволяющие приближаться к его границе.

Вывод: ни один метод или класс методов не выделяется своей собственной высокой эффективностью при решении оптимизационных задач различных типов, т.е. универсальностью. Инженер вынужден приспосабливать применяемый метод к конкретным характеристикам решаемой задачи.

4. Нахождение экстремума функции при наличии ограничения