ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 688
Скачиваний: 1
МИНИСТЕРСТВО
ОБРАЗОВАНИЯ
И
НАУКИ
РФ
ФЕДЕРАЛЬНОЕ
ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ
«
ВОРОНЕЖСКИЙ
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
»
ЛАБОРАТОРНЫЙ
ПРАКТИКУМ
ПО
МЕТОДАМ
ОПТИМИЗАЦИИ
И
ИССЛЕДОВАНИЮ
ОПЕРАЦИЙ
Составитель
И
.
Д
.
Коструб
Издательско
-
полиграфический
центр
Воронежского
государственного
университета
2013
Утверждено
научно
-
методическим
советом
факультета
прикладной
матема
-
тики
,
информатики
и
механики
19
февраля
2013
г
.,
протокол
№
6
Рецензент
доцент
кафедры
ММИО
Ю
.
В
.
Бондаренко
Практикум
подготовлен
на
кафедре
нелинейных
колебаний
факультета
ПММ
Воронежского
государственного
университета
.
Рекомендуется
для
студентов
3-
го
курса
дневного
отделения
.
Для
специальности
010501 –
Прикладная
математика
и
информатика
3
Лабораторный
практикум
написан
по
курсу
«
Методы
оптимизации
и
исследование
операций
»
и
посвящён
численным
методам
минимизации
функций
одной
и
нескольких
переменных
,
а
также
решению
задач
курса
«
Исследование
операций
»
с
помощью
ЭВМ
.
Предназначен
практикум
для
лабораторной
и
самостоятельной
работы
студентов
.
В
каждом
параграфе
приводятся
теоретические
сведения
,
необходимые
для
решения
сформулированных
задач
.
Приводятся
образцы
решения
задач
,
а
также
задания
для
самостоятельной
работы
.
ЧИСЛЕННЫЕ
МЕТОДЫ
МИНИМИЗАЦИИ
Определение
.
Пусть
функция
)
(
u
J
определена
всюду
в
некоторой
окрестности
точки
P
.
Тогда
эта
функция
имеет
в
точке
P
локальный
максимум
(
или
соответственно
локальный
минимум
),
если
существует
такая
окрестность
точки
P
,
что
для
всех
точек
этой
окрестности
значение
)
(
P
J
является
наибольшим
(
или
соответственно
наименьшим
)
среди
всех
значений
)
(
u
J
этой
функции
.
Локальный
максимум
и
локальный
минимум
объединяются
общим
названием
локальный
экстремум
.
Если
функция
)
(
u
J
дифференцируема
в
данной
точке
P
и
имеет
в
этой
точке
локальный
экстремум
,
то
0
)
(
u
J
.
Точки
,
в
которых
производная
0
)
(
u
J
функции
)
(
u
J
обращается
в
нуль
,
называются
стационарными
точками
функции
.
Каждая
стационарная
точка
–
это
точка
возможного
экстремума
функции
.
Однако
сделать
заключение
о
том
,
что
в
данной
стационарной
точке
на
самом
деле
имеется
экстремум
,
можно
лишь
на
основании
дополнительного
исследования
,
для
проведения
которого
существуют
достаточные
условия
экстремума
.
ЧИСЛЕННЫЕ
МЕТОДЫ
ОДНОМЕРНОЙ
МИНИМИЗАЦИИ
КЛАССИЧЕСКИЙ
МЕТОД
МИНИМИЗАЦИИ
Численные
методы
минимизации
составной
своей
частью
содержат
поиск
точек
локального
минимума
функции
вдоль
заданного
направления
,
т
.
е
отыскание
точек
минимума
функции
одной
переменной
(
как
правило
,
на
заданном
отрезке
).
Постановка
задачи
.
Найти
решение
следующей
задачи
,
,
inf
)
(
b
a
U
u
u
J
где
)
(
u
J
действует
следующим
образом
R
X
J
:
,
X
-
это
область
определения
,
причём
X
U
.
Точки
U
u
называются
допустимыми
,
а
)
(
u
J
-
целевой
функцией
.
4
Теорема
(
Вейерштрасса
).
Если
U
замкнуто
и
ограничено
,
а
)
(
u
J
непрерывна
на
нем
,
то
функция
)
(
u
J
ограничена
снизу
на
этом
множестве
.
Пусть
функция
)
(
u
J
кусочно
-
непрерывна
и
кусочно
-
дифференцируема
.
Подозрительными
на
экстремум
считаются
следующие
точки
:
1.
Стационарные
0
)
(
u
J
.
2.
Концы
отрезка
(
краевой
максимум
и
краевой
минимум
объединяют
общим
названием
-
краевой
экстремум
).
3.
Точки
разрыва
.
4.
Точки
,
в
которых
производная
не
существует
.
5.
Точки
разрыва
производной
.
Затем
следует
провести
дополнительные
исследования
в
стационарных
точках
.
Пусть
0
)
(
...
)
(
)
(
0
)
(
0
0
P
J
P
J
P
J
k
,
а
0
)
(
0
)
1
(
P
J
k
.
Если
)
1
(
k
четная
и
0
)
(
0
)
1
(
P
J
k
,
то
0
P
-
точка
минимума
;
если
)
1
(
k
четная
и
0
)
(
0
)
1
(
P
J
k
,
то
0
P
-
точка
максимума
.
Если
)
1
(
k
нечетная
,
то
0
P
-
точка
перегиба
.
Определение
.
Функция
R
U
J
:
называется
унимодальной
на
b
a
U
,
,
если
существуют
числа
b
a
,
такие
,
что
на
отрезке
]
,
[
a
функция
убывает
,
на
отрезке
]
,
[
b
возрастает
,
а
на
отрезке
]
,
[
остается
постоянной
(
см
.
рис
. 1).
Рис
. 1
5
МЕТОД
ДЕЛЕНИЯ
ОТРЕЗКА
ПОПОЛАМ
Рассмотрим
метод
деления
отрезка
пополам
,
предполагая
,
что
целевая
функция
является
унимодальной
на
рассматриваемом
отрезке
.
Заметим
,
что
выпуклая
на
отрезке
b
a
,
функция
является
унимодальной
на
нём
,
поэтому
для
дважды
непрерывно
дифференцируемой
на
)
,
(
b
a
функции
)
(
u
J
условие
неотрицательности
второй
производной
0
)
(
"
u
J
,
)
,
(
b
a
u
является
достаточным
для
унимодальности
функции
на
отрезке
b
a
,
.
Нахождение
точки
]
,
[
*
b
a
u
доставляющей
локальный
минимум
,
осуществляется
путем
последовательного
уменьшения
отрезка
,
содержащего
точку
минимума
.
Для
сужения
отрезка
унимодальности
будут
использоваться
две
точки
1
u
и
2
u
,
расположенные
симметрично
относительно
середины
отрезка
2
/
)
(
1
a
b
u
,
2
/
)
(
2
a
b
u
,
2
/
)
(
0
a
b
;
причем
]
,
[
,
2
1
b
a
u
u
и
2
1
u
u
.
В
каждой
из
трех
возможных
ситуаций
длина
отрезка
]
,
[
2
1
u
u
не
должна
превышать
2
/
)
(
a
b
.
Если
величина
мала
,
то
длина
отрезка
унимодальности
уменьшается
почти
вдвое
,
чем
и
мотивировано
название
метода
.
Рис
. 2
АЛГОРИТМ
Шаг
1
.
Положить
0
n
,
задать
,
,
,
b
a
.
Шаг
2
.
Положить
1
n
n
,
2
/
)
(
1
a
b
u
,
2
/
)
(
2
a
b
u
.
Шаг
3
.
Вычислить
)
(
1
1
u
J
J
,
)
(
2
2
u
J
J
.