Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
Кафедра математического моделирования
Н.Л. Майорова
Материалы по дисциплине
«Методы оптимизации»
Методические указания
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по специальности
Прикладная математика и информатика
Ярославль 2009
1
Стр.1
УДК 51:37
ББК В183.4я73
М 14
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2009 года
Рецензент
кафедра математического моделирования
Ярославского государственного университета им. П.Г. Демидова
М 14
Майорова, Н.Л. Материалы по дисциплине «Методы
оптимизации»: метод. указания / Н.Л. Майорова;
Яросл. гос. ун-т. – Ярославль : ЯрГУ, 2009. – с.
Методические указания содержат материалы, необходимые
для изучения дисциплины «Методы оптимизации»:
общую характеристику дисциплины, требования к
уровню овладения предметом, программу дисциплины,
список литературы, вопросы к экзамену, примерные варианты
контрольных работ, варианты расчетнографической
работы, место дисциплины в итоговой государственной
аттестации, разбор решений некоторых
вариационных задач.
Предназначены для студентов 4 курса математического
факультета, обучающихся по специальности 010501 –
Прикладная математика и информатика (блок ОПД).
УДК 51:37
ББК В183.4я73
© Ярославский государственный университет, 2009
2
Стр.2
1. Введение
С задачами оптимизации приходится встречаться в различных
сферах деятельности человека. Каждое разумное действие
является в определенном смысле оптимальным, так как выбирается
после сравнения с другими вариантами. Исторически с задачами
оптимизации человечество столкнулось уже в древние века.
Так, уже давно были решены разнообразные задачи геометрического
типа, связанные со свойствами элементарных фигур.
Наиболее простая задача безусловной оптимизации функций
многих переменных привлекла внимание математиков во времена,
когда закладывались основы математического анализа. Она во
многом стимулировала создание дифференциального исчисления.
С появлением дифференциального исчисления возникла возможность
исследования более сложных задач. Первый общий аналитический
прием решения экстремальных задач был разработан
Пьером Ферма и являлся одним из первых крупных результатов
анализа. Открыт он был, по-видимому, в 1629 году, но впервые
достаточно полно изложен в письме к Робервалю в 1638 году. На
современном языке прием Ферма сводится к тому, что в точке
экстремума x
~ в задаче без ограничений () extr
место равенство () 0~ =∇ xf
f x → должно иметь
. Первый намек на этот результат содержится
в словах Кеплера из «Стереометрии винных бочек». Точный
смысл рассуждения П. Ферма приобрели через 46 лет, когда
в 1684 году появилась работа Лейбница, в которой закладывались
основы математического анализа. В своей статье Лейбниц не
только получает в качестве необходимого условия соотношение
∇ () 0~ =xf
употребляет второй дифференциал для различения максимума и
минимума, то есть, по существу, формулирует условия экстремума
второго порядка.
Большинство излагаемых Лейбницем фактов было к тому
времени известно также и Ньютону, но его работа, завершенная к
1671 году, была опубликована лишь в 1736 году. Важнейшие ре3
(сейчас
этот результат называют теоремой Ферма), но и
Стр.3
зультаты по минимизации функций были в дальнейшем получены
Эйлером и Лагранжем.
На первых лекциях курса «Методы оптимизации» излагаются
задачи минимизации скалярных функций конечного числа переменных.
До некоторой степени этот материал является повторением
и обобщением знаний, полученных студентами в курсе математического
анализа. Приходится также для более полного понимания
использовать
геометрическую
интерпретацию
излагаемых
фактов, для чего бывает необходимым вспомнить
классификацию поверхностей второго порядка, изучаемую в курсе
алгебры, понятие линии и поверхности уровня функций многих
переменных, а также некоторые сведения из теории квадратичных
форм и алгебраический критерий Сильвестра знакопостоянства
квадратичной формы.
Затем изучается переход от необходимых и достаточных условий
оптимальности решений оптимизационных задач без ограничений
к соответствующим критериям условных задач, то есть
задач с различными типами ограничений на независимые переменные.
Студентам рассказывается о том, что условная задача
является наиболее общим типом оптимизационных задач нелинейного
программирования (как, впрочем, и линейного), к которому
приводит большой ряд инженерных задач (с ограничениями
на управляемые переменные). Такие ограничения существенно
уменьшают размеры области, в которой проводится поиск оптимума.
На первый взгляд может показаться, что уменьшение размеров
допустимой области должно упростить процедуру поиска
оптимума. Между тем, напротив, процесс оптимизации становится
более сложным, поскольку установленные критерии безусловной
оптимизации нельзя использовать при наличии ограничений.
При этом может нарушаться даже основное условие, в соответствии
с которым оптимум достигается в стационарной точке, характеризующейся
нулевым градиентом. Например, безусловный
минимум функции () ( )2
f x = − 2x
имеет место в стационарной точке
x ≥ 4, то будет найден условный экстремум, которому соответствует
точка x = 4 . Эта точка не является стационарной точкой
функции f , так как () 44 =∇f
x = 2 . Но если задача оптимизации решается с учетом ограничения
.
Поэтому для данного типа задач не4
Стр.4
обходимо сформулировать новые условия оптимальности решений
задач с ограничениями.
По опыту многолетнего преподавания данной дисциплины
можно отметить, что ввиду недостаточности учебного времени,
отведенного на практические занятия (примерно 8 – 9 занятий в
группе за семестр на все три большие темы данной дисциплины),
и невозможности полностью отработать решение каждого типа
задач, во время экзамена для многих студентов может оказаться
достаточно сложной даже любая простейшая задача на условный
экстремум (
xy→ + =yxextr
,
1), поскольку учащиеся пользуются критерием
Сильвестра для идентификации стационарной точки (является
ли она точкой минимума, максимума или в ней вообще нет
экстремума), который «не работает» для задач с ограничениями, а
справедлива соответствующая теорема – достаточное условие оптимума
для данного типа задач. Большие трудности вызывает
также проверка условий регулярности при применении общего
метода решений задач с ограничениями – метода множителей Лагранжа,
так как все условия регулярности формулируются в терминах
точки оптимума, поиск которой и ведется. Общеизвестно,
что со времен Лагранжа почти на протяжении целого века правило
множителей формулировалось с
0 1= , хотя без дополнительных
предположений, например, линейной независимости векторов-градиентов
функций-ограничений в точке оптимума это правило
неверно.
Отдельной темой рассматривается частный случай общей задачи
условной оптимизации со смешанной системой ограничений
– выпуклая задача программирования. Студентам поясняется, что
доказываемые свойства выпуклых задач имеют важное значение
не только в теории, но и в численных методах оптимизации, поскольку
большинство существующих численных методов позволяет,
вообще говоря, находить лишь локальные решения, а точнее,
стационарные точки задачи. Поэтому для выпуклой задачи
отыскание стационарной точки означает отыскание решения,
причем глобального.
Другой класс изучаемых в данном курсе задач на экстремум
– это задачи вариационного исчисления. Следы интереса к
ним можно найти и в античной математике, однако подлинное
5
λ
Стр.5