МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» В.И. Рейзлин ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ Рекомендовано в качестве учебного пособия Редакционно-издательским советом Томского политехнического университета Издательство Томского политехнического университета 2013 УДК 519.85(075.8) ББК 22.193я73 Р35 Рейзлин В.И. <...> Р35 Численные методы оптимизации: учебное пособие / В.И. Рейзлин; Томский политехнический университет. <...> В пособии рассматриваются следующие вопросы: постановка задач оптимизации и численные методы их решения; одномерная и многомерная безусловная оптимизация; условная оптимизация; линейное программирование. <...> В результате смешивания этих компонентов в пропорциях 1:1:1 и 3:1:2 получается бензин сорта А и Б соответственно. <...> Определить месячный план производства бензина сорта А и Б, при котором стоимость выпущенной продукции будет максимальной. <...> В этом случае задача отыскания максимума или минимума, которую также называют задачей оптимизации, называется безусловной. функция ()f x Заметим, что если функция ()f x имеет в точке *x минимум, то в *x имеем максимум. <...> У функции может быть много локальных минимумов. <...> В последующем изложении функцию ()f x будем называть целевой функцией, уравнения () 0 неравенства () 0 k hx – ограничениями в виде равенств, а gxi – ограничениями в виде неравенств. <...> Критерии оптимальности Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). <...> Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой – критерием оптимальности. <...> Критерием оптимальности называется количественная оценка оптимизируемого качества объекта. <...> На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой <...>
Численные_методы_оптимизации.pdf
УДК 519.85(075.8)
ББК 22.193я73
Р35
Рейзлин В.И.
Р35
Численные методы оптимизации: учебное пособие / В.И. Рейзлин;
Томский политехнический университет. – Томск: Изд-во Томского
политехнического университета, 2013. – 112 с.
В пособии рассматриваются следующие вопросы: постановка задач оптимизации
и численные методы их решения; одномерная и многомерная безусловная
оптимизация; условная оптимизация; линейное программирование.
Предназначено для студентов, обучающихся по основной образовательной
программе подготовки магистров по направлению 230100 «Информатика
и вычислительная техника», и может быть полезно студентам и аспирантам,
применяющим в своей научной и учебной работе численные методы.
УДК 519.85(075.8)
ББК 22.193я73
Рецензенты
Доктор технических наук
начальник кафедры «сети и системы связи» ИКСИ
Академии ФСБ РФ
И.А. Шалимов
Кандидат технических наук
заведующая лабораторией реологии нефти
Института химии нефти СО РАН
Н.В. Юдина
© ФГБОУ ВПО НИ ТПУ,2013
© Рейзлин В.И., 2013
© Оформление. Издательство Томского
политехнического университета, 2013
Стр.2
СОДЕРЖАНИЕ
1. ВВЕДЕНИЕ ........................................................................................................ 3
1.1. Постановка задач оптимизации .................................................................. 3
1.2. Математическая постановка задач оптимизации ...................................... 5
1.2.1. Виды ограничений ................................................................................. 5
1.2.2. Критерии оптимальности ...................................................................... 7
1.2.3. Классификация задач ............................................................................. 9
2. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ ............................................................ 12
2.1. Методы сужения интервала неопределенности ...................................... 12
2.1.1. Общий поиск ........................................................................................ 12
2.1.2. Унимодальные функции ...................................................................... 13
2.1.3. Метод деления интервала пополам .................................................... 14
2.1.4. Метод золотого сечения ...................................................................... 15
2.1.5. Установление первоначального интервала неопределенности ....... 19
2.2. Ньютоновские методы ............................................................................... 20
3. МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ .......................... 23
3.1. Рельеф функции .......................................................................................... 23
3.2. Метод покоординатного спуска (Метод Гаусса) .................................... 25
3.3. Метод оврагов............................................................................................. 27
4. МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ ......................... 28
4.1. Градиентные методы ................................................................................. 30
4.2. Метод Ньютона .......................................................................................... 31
4.3. Метод Марквардта ..................................................................................... 32
5. УСЛОВНАЯ ОПТИМИЗАЦИЯ .................................................................. 35
5.1. Задачи с ограничениями в виде равенств ................................................ 35
5.1.1. Множители Лагранжа .......................................................................... 35
5.2. Задачи с ограничениями в виде неравенств ............................................ 38
5.2. Методы штрафных функций ..................................................................... 41
5.3. Метод факторов .......................................................................................... 45
6. СЛУЧАЙНЫЙ ПОИСК ................................................................................ 47
6.1. Простой случайный поиск ......................................................................... 47
6.2. Ненаправленный случайный поиск .......................................................... 48
6.3. Направленный случайный поиск .............................................................. 48
6.3.1. Алгоритм парной пробы ...................................................................... 48
6.3.2. Алгоритм наилучшей пробы ............................................................... 49
6.3.3. Метод статистического градиента ..................................................... 50
6.3.4. Алгоритм наилучшей пробы с направляющим гиперквадратом .... 51
6.4. Алгоритмы глобального поиска ............................................................... 52
110
Стр.110
7. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ .................................................... 55
7.1. Примеры задач линейного программирования ....................................... 55
7.1.1. Задача об использовании сырья .......................................................... 55
7.1.2. Задача об использовании мощностей оборудования ........................ 56
7.1.3. Транспортная задача ............................................................................ 58
7.1.4. Задача о питании .................................................................................. 60
7.2. Основная задача линейного программирования ..................................... 61
7.3. Основная задача линейного программирования
с ограничениями-неравенствами .............................................................. 65
7.4. Геометрическое толкование задач линейного программирования ....... 68
8. СИМПЛЕКС МЕТОД ИЛИ МЕТОД
ПОСЛЕДОВАТЕЛЬНОГО УТОЧНЕНИЯ ОЦЕНОК ............................ 79
8.1. Алгоритм симплекс метода ....................................................................... 82
8.2. Вырожденность в задачах линейного программирования ..................... 86
8.3. Двойственность задачи линейного программирования ......................... 88
8.4. Метод последовательного уточнения оценок ......................................... 95
8.5. Методы решения транспортной задачи ................................................... 98
8.5.1. Метод северо-западного угла ............................................................. 99
8.5.2. Метод минимального элемента ........................................................ 100
8.5.3. Метод потенциалов ............................................................................ 101
СПИСОК ЛИТЕРАТУРЫ .............................................................................. 109
СОДЕРЖАНИЕ ................................................................................................ 110
111
Стр.111