Это позволило использовать
известные теоретические результаты (из математического анализа), поскольку функция Р(х) в этом случае является дифференцируемой и заданной на замкнутом ограниченном множестве —
отрезке [0, 500]. <...> Это позволило использовать
известные теоретические результаты (из математического анализа), поскольку функция Р(х) в этом случае является дифференцируемой и заданной на замкнутом ограниченном множестве —
отрезке [0, 500]. <...> Общая постановка оптимизационной задачи содержит:
• множество допустимых решений
множество);
Х ⊂ Rn
(допустимое
• целевую функцию f(x): Rn → R (критерий качества);
• условие оптимизации f ( x) → extr.
x∈ X
Задача оптимизации заключается в следующем: требуется
найти такое x0∈ X (если существует), доставляющее экстремальное (минимальное или максимальное) значение целевой функции
f (x) на множестве Х, а именно для x0 должно выполняться одно из
условий:
либо f (x0) ≤ f (x) для всех x∈X, (1.1)
либо f (x0) ≥ f (x) для всех x∈X. <...> (1.1), называется точкой глобального (или абсолютного) минимума функции f (x) на множестве Х. <...> Общая постановка оптимизационной задачи содержит:
• множество допустимых решений
множество);
Х ⊂ Rn
(допустимое
• целевую функцию f(x): Rn → R (критерий качества);
• условие оптимизации f ( x) → extr.
x∈ X
Задача оптимизации заключается в следующем: требуется
найти такое x0∈ X (если существует), доставляющее экстремальное (минимальное или максимальное) значение целевой функции
f (x) на множестве Х, а именно для x0 должно выполняться одно из
условий:
либо f (x0) ≤ f (x) для всех x∈X, (1.1)
либо f (x0) ≥ f (x) для всех x∈X. <...> (1.1), называется точкой глобального (или абсолютного) минимума функции f (x) на множестве Х. <...> 6
Точек глобального минимума функции f(x) на множестве Х
может быть: одна (рис. <...> 6
Точек глобального минимума функции f(x) на множестве Х
может быть: одна (рис. <...> Если множество Х⊂ Rn непусто
и компактно (ограничено и замкнуто), а функция f(x) непрерывна
на нем, то множество <...>
Методы_оптимизации.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б. Н. ЕЛЬЦИНА
А. Г. Кремлёв
МЕТОДЫ ОПТИМИЗАЦИИ
Учебное пособие
Рекомендовано методическим советом УрФУ
в качестве учебного пособия для студентов,
обучающихся по программе бакалавриата по направлению
подготовки 230400 «Информационные системы и технологии»
Екатеринбург
Издательство Уральского университета
2012
Стр.2
УДК 517.977.5(075.8)
ББК 22.19
К795
Рецензенты:
С. С. Ти т о в, доктор физико-математических наук, профессор,
заведующий кафедрой прикладной математики и технической
графики (Уральская государственная архитектурнохудожественная
академия);
А. М. Та р а с ь е в, доктор физико-математических наук
(Институт математики и механики УрО РАН)
Кремлёв, А. Г.
К7950
Методы оптимизации : учеб. пособие / А. Г. Кремлёв. —
Екатеринбург : Изд-во Урал. ун-та, 2012. – 196 с.
ISBN 978-5-7996-0770-8
Представлены основные разделы курса теории оптимизации.
Изложены основные понятия и методы решения экстремальных задач.
Каждый раздел пособия содержит теоретическую часть, систематизированную
подборку контрольных вопросов и практических заданий.
Предназначено студентам технических вузов всех форм обучения.
Библиогр.: 12 назв. Рис. 73.
УДК 517.977.5(075.8)
ББК 22.19
ISBN 978-5-7996-0770-8
© Уральский федеральный университет, 2012
© Кремлёв А. Г., 2012
Стр.3
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ ........................................................................................................5
1. ОБЩАЯ ПОСТАНОВКА ОПТИМИЗАЦИОННОЙ ЗАДАЧИ ......................7
Математическая модель ........................................................................... 7
Основные принципы построения математических моделей .............. 11
Формулировка задачи оптимизации ..................................................... 20
Разрешимость задачи оптимизации ...................................................... 26
Контрольные вопросы и задания .......................................................... 33
2. ОПТИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ ...........................36
Методы поиска решений задач оптимизации ...................................... 36
Необходимые и достаточные условия локального экстремума ......... 39
Выпуклые функции ................................................................................ 47
Контрольные вопросы и задания .......................................................... 50
3. ЧИСЛЕННЫЕ МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ ................51
Основные источники погрешностей .................................................... 51
Метод равномерного перебора .............................................................. 54
Алгоритмы со сжатием отрезка поиска ................................................ 56
Метод деления отрезка пополам (дихотомический) ........................... 59
Метод золотого сечения ......................................................................... 65
Метод Фибоначчи ................................................................................... 71
Контрольные вопросы и задания .......................................................... 76
4. ЭКСТРЕМУМ ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ ...................78
Дифференцируемые функции ............................................................... 81
Необходимые и достаточные условия экстремума ............................. 87
Контрольные вопросы и задания .......................................................... 98
5. ОПТИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ ..............................................100
Выпуклость квадратичных функций .................................................. 100
Свойства выпуклых функций .............................................................. 101
Экстремальные свойства выпуклых функций ................................... 105
Контрольные вопросы и задания ........................................................ 115
Стр.4
4
Оглавление
6. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ........................................................ 116
Формулировка задачи линейного программирования ...................... 116
Графический метод решения задачи
линейного программирования ...................................................... 120
Общее решение задачи ЛП .................................................................. 130
Контрольные вопросы и задания ........................................................ 135
7. СИМПЛЕКС-МЕТОД .......................................................................................137
Каноническая форма записи задачи ЛП ............................................. 137
Решение задачи линейного программирования
(в канонической форме) ................................................................ 139
Симплекс-таблица ................................................................................ 148
Контрольные вопросы и задания ........................................................ 156
8. ЧИСЛЕННЫЕ МЕТОДЫ МИНИМИЗАЦИИ
ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ .............................................158
Методы безусловной минимизации .................................................... 158
Метод наискорейшего спуска .............................................................. 165
Метод сопряженных градиентов ......................................................... 173
Метод Ньютона ..................................................................................... 180
Метод условного градиента ................................................................. 185
Контрольные вопросы и задания ........................................................ 187
СПИСОК ЛИТЕРАТУРЫ .....................................................................................190
Стр.5
ПРЕДИСЛОВИЕ
Настоящее пособие предназначено для студентов технических
вузов и включает основные разделы теории оптимизации:
постановка задачи конечномерной оптимизации, локальный и глобальный
экстремум, необходимые и достаточные условия экстремума
функций нескольких переменных, численные методы поиска
экстремума функции одной переменной (дихотомический метод,
методы Фибоначчи и золотого сечения), условный экстремум
(задача Лагранжа), линейное программирование, выпуклое программирование,
численные методы безусловной и условной оптимизации
функций нескольких переменных (градиентные методы,
метод Ньютона). Математический аппарат, применяемый в данном
пособии и используемый при изучении методов теории оптимизации
и решении задач, не выходит за пределы обычного (стандартного)
курса высшей математики в технических вузах.
Каждый раздел пособия тематически ориентирован, содержит
теоретическую часть, контрольные вопросы и практические задания.
В теоретической части приведены основные сведения (понятия,
определения, утверждения и их доказательства, формулы),
необходимые для понимания этого раздела, а также примеры, их
решения, графические иллюстрации.
Задачи, представленные в каждом разделе, имеют практическую
направленность. Поскольку изучение методов теории оптимизации
обязательно должно сопровождаться решением задач, то
среди представленных задач есть как простые, так и более сложные.
К первой группе относятся задачи, предназначенные для приобретения
навыков применения готовых формул и теорем (теоретических
утверждений, свойств), общих численных алгоритмов. Приведенные
примеры решений позволяют использовать указанные
методические приемы, являющиеся достаточно общими. Примеры
Стр.6
Зав. редакцией М. А. Овечкина
Редактор Е. Е. Крамаревская
Корректор Е. Е. Крамаревская
Компьютерная верстка Н. Ю. Михайлов
План выпуска 2012 г. Подписано в печать 15.11.2012.
Формат 60×84 1
Уч.-изд. л. 9,8. Усл. печ. л. 11,16. Тираж 150 экз. Заказ № 2412.
/16
Издательство Уральского университета
620000, г. Екатеринбург, ул. Тургенева, 4.
Отпечатано в Издательско-полиграфическом центре УрФУ.
620000, г. Екатеринбург, ул. Тургенева, 4.
Тел.: +7 (343) 350-56-64, 350-90-13.
Факс: +7 (343) 358-93-06.
E-mail: press.info@usu.ru
. Бумага офсетная. Гарнитура Times.
Стр.193