новая папка 1 / 241566

2075

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра высшей математики

МЕТОДЫ ОПТИМИЗАЦИИ И ТЕОРИИ УПРАВЛЕНИЯ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ к самостоятельной работе

по дисциплинам «Методы оптимизации», «Математические методы теории управления» Составитель Ю.И. Денисенко

Липецк Липецкий государственный технический университет

2013

1

УДК 681.518(05) Д.332

Рецензент - канд. физ.– мат. наук, Н. М. Мишачев

Д.332 Денисенко, Ю.И.

Методы оптимизации и теории управления. [Текст]: методические указания к самостоятельной работе по дисциплинам «Методы оптимизации», «Математические методы теории управления» / сост.Ю.И. Денисенко. Липецк: Изд-во ЛГТУ, 2013.–16 с.

Методические указания предназначены для самостоятельной работы студентов направлений 010800.62 («Механика и математическое модели-рование») и 220100.62 («Системный анализ») по дисциплине «Методы оптимизации», «Ма-

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

Табл. 2. Библиогр.: 17 назв.

© ФГБОУ ВПО «Липецкий государственный технический университет», 2013

2

Содержание

1.Цель работы……………….………………………………………….…………3

2.Лабораторная работа №1. Линейное программирование………………….…3

3.Лабораторная работа № 2. Вычисление расстояния между кривыми............6

4.Лабораторная работа №3. Методы оптимизации первого порядка.……..…10

5.Лабораторная работа №4. Нелинейная задача о наименьших квадратах….11

6.Лабораторная работа №5. Методы условной оптимизации…….….…….…11

7.Лабораторная работа №6, Расчет алгоритмов стабилизации непрерывных систем» (первая часть)………………………………………………….….….12

8.Лабораторная работа №6. Расчет алгоритмов стабилизации дискретных систем (вторая часть)…………………………………………….……..….….14

9.Библиографический список……………………………………..……..……..14

Цель работы

Для закрепления знаний студентов по отдельным разделам курсов «Методы оптимизации», «Математические методы теории управления» проводятся лабораторные занятия, целью которых является формирование навыков самостоятельной работы по решению оптимизационных задач и задач теории управления. Для лабораторных занятий обязательным является изучение основных методов оптимизации (безусловной и условной), методов решения нелинейной задачи о наименьших квадратах, методов адаптации и оптимизации в современной теории автоматического управления, алгоритмов стабилизации непрерывных и дискретных систем управления.

В методических указаниях рассмотрены некоторые понятия по дисциплинам «Методы оптимизации», «Математические методы теории управления», приведены задания к лабораторным работам, содержащие требования к оформлению отчетов о проделанной работе.

3

Лабораторная работа №1. Линейное программирование

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

граммирования. В них требуется найти экстремум целевой функции f = c1x1 +… cnxn

при наличии ограничений в виде неравенств ai1 +...+ ainxn ≤ bi, i =1,2,...,m. Эти условия можно записать в матричной форме

CTX→extr, AX ≤ b (1).

Здесь b и c – векторы-столбцы, А – матрица размера m*n. Существует другая форма записи, называемая канонической, когда ограничения имеют вид ра-

венств, а на переменные накладывается требование положительности

CTX→ min, AX = b, X ≥ 0 (2)

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

ВАРИАНТЫ ЗАДАНИЙ

Решить задачу линейного программирования (1) для указанных матриц A, b, C. Значения A, b, C взять из таблицы 1.

Лабораторная работа № 2. Вычисление расстояния между кривыми

Цель работы: найти двумя способами расстояние между двумя фигурами на плоскости (методом множителей Лагранжа и при помощи вариационного исчисления). Для компьютерного получения решения и его визуализации использовать пакет MAPLE или другие математические пакеты [17].

1. Метод множителей Лагранжа Стандартная условно-экстремальная задача формулируется следующим образом: найти минимум функции (критерия)

J = f(x1, ..., xn)

при наличии ограничений g1(x1, ..., xn) = 0, …, gm(x1, ..., xn) = 0, или коротко

J = f(X) →min; g(X) =0; X Rn

Основной аналитический метод решения связан с введением вектора множителей Лагранжа λ = [λ1,… , λ m] и построением составного критерия (функции Лагранжа)

L = f(X) + λ g(X) → min

или в более подробной записи L= f + λ1g1 + … + λ mgm.

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

2. Применение вариационного исчисления Методы Ферма и Лагранжа позволяют аналитически решать конечномерные

экстремальные задачи, когда критерий зависит от конечного числа неизвес т- ных. Более трудны для решения бесконечномерные экстремальные задачи, когда критерий зависит от неизвестной функции f(x). Такие задачи решают мето-

дами вариационного исчисления. Простейшая задача вариационного исчисления формулируется следующим образом. Требуется найти кривую y = f(x), проходящую через две заданные точки A(x1, y1), В(x2, y2) и доставляющую экстремум функционалу

6

Эйлер доказал, что искомая кривая удовлетворяет уравнению

Fх ddх Fу 0 (2)

Уравнение Эйлера (2) представляет собой нелинейное дифференциальное уравнение второго порядка, семейство решений которого содержит экстре-

мальную кривую y = f(x). Следует заметить, что уравнение Эйлера не дает окончательного решения поставленной задачи, а лишь выделяет класс кривых, подозрительных на экстремум. Ситуация здесь вполне аналогична поиску экстремума функции путем ее дифференцирования, когда экстремум может оказаться либо в одной из точек, где производная равна нулю, либо на краях ин-

тервала.

Общее решение уравнения (2) зависит от двух произвольных постоянных y = f(x, C1, C2) и задает двухпараметрическое семейство экстремалей. Для определения постоянных C1, C2 и выделения из семейства экстремалей одной кривой – решения исходной задачи используют краевые условия:

f(x1) = y1; f(x2) = y2.

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

Пусть левая точка А находится на кривой φ(x), а правая точка В – на кривой

ϕ(x). Рассмотрим случай, когда в качестве функционала (1) выступает длина кривой y = f(x), соединяющей кривые φ(x) и ϕ(x), т.е. он имеет вид

х 2

J = 1 у 2 dx.

х1

К минимизации такого критерия сводятся разнообразные задачи о расстоянии между точками, прямыми и кривыми.

Уравнение Эйлера (2) в этом случае принимает простой вид у 0 (покажите это), его решения (экстремали) – прямые линии y = kx + b. Это соответствует

7

очевидному геометрическому факту, что кратчайшие пути на плоскости – отрезки прямых. Для определения постоянных k, b привлекают так называемые условия трансверсальности. Они имеют вид

Одно из них относится к левому концу искомой кривой у, другое – к правому. 3. Задание для самостоятельной работы.

Требуется вычислить расстояние между двумя фигурами (согласно варианту задания). В случае если фигуры пересекаются, путем переноса центра окружности и/или поворота одной из парабол или гипербол нужно добиться того, чтобы фигуры не пересекались. При этом следует привести исходные и результирующие уравнения, а также указать, на какой угол был осуществлен поворот. Затем нужно двумя способами вычислить расстояние между фигурами (методом неопределенных множителей Лагранжа и с использованием вариационного исчисления). Вращение фигуры на плоскости осуществляется следующим образом. Предположим, исходная фигура задана уравнением f(x,y) = 0. Для того чтобы повернуть ее вокруг начала координат на угол φ против часовой стрелки,

нужно осуществить подстановку

х1= xcosφ + ysinφ; y1 = ycosφ – xsinφ.

Отчет по самостоятельной работе должен содержать:

1) уравнение, описывающее две заданные фигуры, их чертеж. Если фигуры пе-

ресекаются, то привести уравнения и чертеж измененных фигур вместе с текстом программы для получения преобразованных уравнений; 2) определение кратчайшего расстояния между фигурами методом множителей

Лагранжа. Чертеж, содержащий две фигуры, отрезок минимальной длины, с о- единяющий их, и точки его пересечения с двумя фигурами. Значения множите-

лей Лагранжа; 3) поиск кратчайшего расстояния средствами вариационного исчисления.

Уравнение Эйлера, его решение. Вывод уравнений трансверсальности. Чертеж,

8

содержащий две фигуры, экстремальные прямые и точки их пересечения с фигурами; 4) сравнение результатов, полученных двумя методами. Координаты точек пе-

ресечения искомой прямой с обеими фигурами. Уравнение, описывающее эту прямую.

4. Контрольные вопросы

1.Найти расстояние между параболой y = x2 и прямой x – y = 5: а) методом множителей Лагранжа; б) с помощью вариационного исчисления.

2.Найти расстояние от точки A(1,0) до эллипса 4x2+9y2 = 36:

а) методом множителей Лагранжа; б) с помощью вариационного исчисления.

3. Выписать и решить уравнение Эйлера для функционалов:

В каждом варианте требуется найти расстояние между двумя заданными фигу-

Лабораторная работа №3. Методы оптимизации первого порядка

Задание для лабораторной работы

1.Написать условие задачи и аналитическое выражение для градиента.

2.Решить задачу методом Коши, используя:

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

3.Решить задачу методами Флетчера-Ривса и Полака-Рибьера.

4.Решить задачу методами DFP и BFGS.

Представить результаты решения задачи различными методами в таблице.

Сравнить результаты, полученные методами первого порядка и методами второго порядка.

Контрольные вопросы

1.Математическая модель задачи безусловной оптимизации.

2.Метод Коши.

3.Метод Флетчера-Ривса.

4.Метод Полака-Рибьера.

5.Методы DFP и BFGS.

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

Задание выдается студентам в электронной форме.

Лабораторная работа №4. Нелинейная задача о наименьших квадратах

Задание для лабораторной работы

1.Сформировать исследуемую функцию согласно варианту.

2.Найти минимум функции следующими методами: методом Гаусса-Ньютона, методом Левенберга -Марквардта, методом BFGS, методом DFP.

3.Представить результаты расчета всеми методами в таблице.

4.Сделать выводы, в которых необходимо отразить:

а) влияние НЗНК на решение алгоритмов;

10