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

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

Московский государственный открытый университет

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

Курсовой проект

по дисциплине: "Оптимальные системы автоматического управления"

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

Выполнил:

студент 5 курса,

ФУИТС, гр. И-52/06,

Терсенидис М. Г.

Проверила:

Изосимова Т. А.

Чебоксары – 2010

Задание

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

,

где a = 1, b = 0.5, c = 1, d = 0, e = 1, f = 0.333.

Дана начальная точка поиска A⁰(x⁰, y⁰), где x⁰ = 0.5, y⁰ = 2.5.

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

· методом наискорейшего спуска;

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

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

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

1.5x + у – 3.75 ≥ 0;

0.5х + у - 3.75 ≤ 0;

x- у - 2 ≤ 0.

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

, где k = 4, T₁ = 10, T₂ = 5.

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

· провести исследование ОСАУ с применением программного продукта "20-simPro 2.3";

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

Содержание

Введение

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

2. Нахождение экстремума функции без ограничения

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

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

5. Синтез оптимальной по быстродействию системы с помощью принципа максимума Понтрягина

Заключение

Список использованной литературы

Приложение

функция переменная экстремум максимум

Введение

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

· методы исследования функций классического анализа;

· методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

· нелинейное программирование.

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

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

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

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

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

В данном разделе будет рассматриваться задача безусловной оптимизации, т.е. данная задача характеризуется тем, что минимум функции f: R^m® R ищется на всем пространстве: f(x) ® min, x Î R^m.

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

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

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

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

Методы прямого поиска

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

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

· не требуют явного выражения целевой функции в аналитическом виде;

· может требовать более значительных затрат времени по сравнению с методами, основанными на производных.

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

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

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

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

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

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

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

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

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

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

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

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

Градиентные методы

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

Градиент функции F(x) – это вектор, составляющие которого равны частным производным функции F(x) по соответствующим переменным, т.е.

Направление вектора градиента совпадает с направлением наискорейшего возрастания функции. Вектор противоположного знака -ÑF(x) называется антиградиентом, его направление совпадает с направлением наискорейшего убывания функции.

Матрица вторых производных Ñ2F(x) – это симметричная квадратная матрица порядка n вторых частных производных функции F(x). Эту матрицу называют матрицей Гессе и обозначают H(x) = Ñ2F(x). Ее элемент, расположенный на пересечении i-й строки и j-го столбца, равен:

Пусть х^Т=[x₁, x₂,…, x_n] – вектор переменных. Для наличия в точке x* локального минимума (максимума) необходимо, чтобы выполнялось равенство ÑF(x*) =0 и матрица Гессе H(x*) = ѲF(x*) была положительно (отрицательно) полуопределенной, т.е. x^THx ³0 ( x^THx £0).

Достаточным условием существования минимума (максимума) в точке x* является положительная (отрицательная) определённость матрицы Гессе в этой точке, т.е. x^THx >0 ( x^THx<0).

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой x^k+1 = x^k + a^ks(x^k), где

x^k - текущее приближение к решению x^*;

a^k - параметр, характеризующий длину шага;

s(x^k) - направление поиска в N - мерном пространстве управляемых переменных x_i, i = 1, 2,..., N.