ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 691
Скачиваний: 1
21
Чем
ближе
к
минимуму
при
0
r
,
тем
меньше
градиент
функции
)
,
(
r
u
P
.
Поиск
заканчивается
,
если
k
r
,
где
–
малая
положительная
величина
.
Графическая
иллюстрация
примера
показана
на
рис
. 6.
Линии
уровня
функции
2
2
2
1
2
1
9
6
)
(
u
u
u
u
u
J
есть
концентрические
окружности
с
центром
в
точке
с
координатами
)
2
/
9
;
3
(
)
,
(
2
1
u
u
.
,
4
/
117
)
2
/
9
(
)
3
(
2
2
2
1
u
u
если
0
J
,
,
4
/
121
)
2
/
9
(
)
3
(
2
2
2
1
u
u
если
1
J
и
так
далее
.
Рис
. 6
АЛГОРИТМ
Шаг
1
.
Задать
0
-
требуемую
точность
.
Задать
координаты
исходной
точки
u
.
Положить
1
,
0
k
r
k
.
Шаг
2
.
Найти
минимум
функции
)
,
(
k
r
u
P
в
точке
k
u
*
.
Проверить
критерий
остановки
метода
k
r
.
Если
он
выполнен
,
то
вычисления
завершаются
.
Точка
минимума
найдена
k
u
*
.
Считаем
)
(
*
u
J
.
22
Шаг
3
.
Положить
C
r
r
k
k
k
k
/
,
1
1
.
Принять
за
новую
начальную
точку
1
*
k
u
u
.
Перейти
к
шагу
2
.
Замечание
.
Использование
штрафных
функций
для
решения
задач
связано
с
определенной
вычислительной
трудностью
.
Прежде
всего
поиск
может
начинаться
с
допустимой
точки
u
,
для
которой
.
,...,
2
,
1
,
0
)
,...,
(
1
m
i
u
u
g
n
i
Для
некоторых
задач
находить
такую
точку
довольно
сложно
.
Кроме
того
,
вследствие
использования
в
алгоритме
оптимизации
дискретных
шагов
около
границы
}
0
)
,...,
(
:
{
1
n
i
u
u
g
u
возможен
шаг
,
который
выводит
за
границы
допустимой
области
.
Он
приводит
к
уменьшению
значений
функции
)
,
(
k
r
u
P
,
т
.
е
.
к
фиктивному
успеху
.
Таким
образом
,
нужна
явная
проверка
допустимости
каждой
последующей
точки
,
для
чего
на
каждой
итерации
необходимо
вычислять
значения
функции
,...
2
,
1
),
(
k
u
g
k
i
.
МЕТОД
БАРЬЕРНЫХ
ФУНКЦИЙ
Метод
штрафных
функций
относится
к
группе
методов
внутренней
точки
,
т
.
е
.
он
начинает
работать
с
допустимой
точки
0
u
и
генерирует
последовательность
допустимых
точек
n
u
u
u
,...,
,
2
1
.
Метод
барьерных
функций
,
наоборот
,
относится
к
группе
методов
внешней
точки
,
он
начинает
поиск
с
недопустимой
точки
и
генерирует
последовательность
недопустимых
решений
,
которая
приближается
к
оптимальному
решению
извне
допустимой
области
.
Постановка
задачи
.
Требуется
найти
минимум
функции
)
,...,
(
1
n
u
u
J
при
ограничениях
m
i
u
u
g
n
i
,...,
2
,
1
,
0
)
,...,
(
1
,
l
m
i
u
u
h
n
i
,...,
,
1
,
0
)
,...,
(
1
или
inf,
)
,...,
(
1
n
u
u
J
m
i
u
u
g
n
i
,...,
2
,
1
,
0
)
,...,
(
1
,
l
m
i
u
u
h
n
i
,...,
,
1
,
0
)
,...,
(
1
.
В
частности
,
для
искомых
функций
–
ограничений
целесообразно
использовать
барьерную
функцию
следующего
вида
))
(
(
))
(
(
)
(
1
2
1
1
u
h
R
u
g
R
u
i
l
m
i
i
m
i
,
где
2
1
,
R
R
-
непрерывные
функции
,
которые
удовлетворяют
условиям
0
)
(
1
v
R
,
если
0
v
и
0
)
(
1
v
R
,
если
0
v
,
0
)
(
2
v
R
,
если
0
v
и
0
)
(
2
v
R
,
если
0
v
.
23
Типичными
являются
следующие
выражения
для
функций
2
1
,
R
R
p
v
v
R
})
,
0
(max{
)
(
1
,
p
v
v
R
|
|
)
(
2
,
где
p
-
целое
положительное
число
.
Далее
от
исходной
задачи
переходим
к
задаче
безусловной
оптимизации
вспомогательной
функции
.
Минимизировать
)
(
)
(
u
r
u
J
,
где
0
r
-
штрафной
коэффициент
.
Пусть
–
непрерывная
функция
.
Обозначим
)}
(
)
(
{
inf
)
(
u
r
u
J
r
.
Подход
,
связанный
с
барьерной
функцией
состоит
в
решении
задачи
вида
максимизировать
)
(
r
при
ограничении
0
r
.
АЛГОРИТМ
Шаг
0.
Выбрать
0
.
Выбрать
начальную
точку
1
u
,
параметр
штрафа
0
r
и
число
1
.
Положить
1
k
и
перейти
к
основному
этапу
.
Основной
этап
(
k
-
я
итерация
).
Шаг
1.
При
начальной
точке
k
u
и
параметре
штрафа
k
r
решить
следующую
задачу
:
минимизировать
функцию
p
i
l
m
i
p
i
m
i
k
k
u
h
u
g
r
u
J
u
r
u
J
|
)
(
|
)})
(
,
0
(max{
{
)
(
)
(
)
(
1
1
,
где
p
-
целое
положительное
число
.
Положить
1
k
u
равным
оптимальному
решению
задачи
и
перейти
к
шагу
2
.
Шаг
2.
Если
)
(
1
k
k
u
r
,
то
вычисления
завершить
.
Иначе
положить
k
k
r
r
1
,
1
k
k
.
Перейти
к
шагу
1
.
Замечание
.
На
эффективность
метода
барьерных
функций
существенно
влияют
выбор
начального
значения
0
r
и
метод
сокращения
значений
в
процессе
минимизации
,
а
также
выбор
весовых
коэффициентов
i
w
.
Если
в
функции
значение
)
,
(
r
u
P
,
выбирают
слишком
малым
,
то
уже
на
начальной
стадии
процесса
приходят
к
минимуму
функции
)
(
u
J
,
который
вряд
ли
окажется
вблизи
действительного
условного
минимума
в
точке
*
u
.
С
другой
стороны
,
если
значение
0
r
,
выбирается
слишком
большим
,
то
на
первых
итерациях
24
вычислительного
процесса
текущая
точка
неизбежно
окажется
слишком
далеко
за
пределами
допустимой
области
,
и
поиск
из
-
за
необходимости
возврата
в
пределы
допустимой
области
окажется
весьма
затяжным
.
Задания
. 1.
Показать
,
что
для
метода
наискорейшего
градиентного
спуска
,
применённого
к
функции
2
2
2
1
2
1
)
,
(
u
u
u
u
J
,
0
,
выполнение
одной
итерации
из
точки
)
/
,
(
)
,
(
2
1
k
k
u
u
приводит
к
уменьшению
значения
функции
по
закону
)
(
1
q
J
J
k
k
,
где
)
/
1
)(
/
1
(
)
/
1
(
1
)
(
2
2
3
2
2
2
q
.
Исследовать
зависимость
q
от
параметра
размещения
точки
начала
итерации
.
Какая
связь
1
k
J
с
k
J
будет
в
случае
использования
метода
Ньютона
?
2.
Для
функции
2
2
1
2
2
1
2
1
)
(
)
(
4
)
,
(
u
u
u
u
u
u
J
построить
множество
точек
,
в
которых
выполняется
критерий
останова
||
)
,
(
||
2
1
u
u
J
grad
при
1
.
3.
Для
функции
2
2
2
1
2
1
)
,
(
u
u
u
u
J
,
0
применить
метод
наискорейшего
спуска
,
метод
Ньютона
из
начальной
точки
)
/
,
(
)
,
(
0
2
0
1
0
u
u
u
построив
k
u
для
2
,
1
k
.
Сколько
итераций
потребуется
этим
методам
для
попадания
в
минимум
функции
J
?
4.
Решить
задачу
многомерной
минимизации
inf
)
(
u
J
.
Помимо
точек
минимума
посчитать
число
итераций
и
сделать
вывод
о
целесообразности
использования
каждого
из
методов
в
той
или
иной
ситуации
.
Использовать
методы
:
а
)
дробления
шагом
;
б
)
наискорейшего
спуска
;
в
)
Ньютона
;
г
)
штрафных
функций
.
В
двух
последних
методах
ограничения
брать
из
приведённых
выше
примеров
.
Решение
поставленной
задачи
оформить
в
виде
отчёта
.
1.
2
2
2
1
2
1
2
2
3
)
(
u
u
u
u
u
J
. 2.
2
2
2
1
2
1
3
4
3
)
(
u
u
u
u
u
J
.
3.
2
1
2
2
2
1
8
2
)
(
u
u
u
u
u
J
. 4.
2
2
2
1
2
1
5
4
)
(
u
u
u
u
u
J
.
5.
2
2
2
1
)
6
(
4
)
5
(
9
)
(
u
u
u
J
. 6.
2
2
2
1
)
(
u
u
u
J
.
7.
2
2
2
1
)
4
(
)
3
(
)
(
u
u
u
J
. 8.
2
2
2
1
2
1
6
)
(
u
u
u
u
u
J
.
9.
2
2
2
1
2
1
2
3
)
(
u
u
u
u
u
J
. 10.
2
2
2
1
2
1
4
)
(
u
u
u
u
u
J
.
11.
2
1
2
2
1
)
(
)
(
u
u
u
u
u
J
. 12.
2
2
2
1
2
1
3
)
(
u
u
u
u
u
J
.
13.
2
2
2
1
)
3
(
)
4
(
)
(
u
u
u
J
. 14.
2
2
2
1
2
1
4
3
5
)
(
u
u
u
u
u
J
.
15.
2
1
2
2
1
)
2
(
)
(
u
u
u
u
u
J
. 16.
2
2
2
1
2
1
3
)
(
u
u
u
u
u
J
.
17.
2
2
2
1
)
5
(
)
3
(
)
(
u
u
u
J
. 18.
2
2
2
1
2
1
)
(
u
u
u
u
u
J
.
19.
2
2
2
1
)
3
(
)
5
(
)
(
u
u
u
J
. 20.
2
1
2
2
1
3
2
)
(
)
(
u
u
u
u
u
J
21.
2
2
2
1
2
1
4
3
)
(
u
u
u
u
u
J
. 22.
2
2
2
1
2
1
3
)
(
u
u
u
u
u
J
.
25
23.
2
1
2
2
1
9
)
(
)
(
u
u
u
u
u
J
. 24.
2
2
2
1
2
1
3
2
4
)
(
u
u
u
u
u
J
25.
2
1
2
2
1
5
)
(
)
(
u
u
u
u
u
J
.
ЗАДАЧА
ПРОДАВЦА
ГАЗЕТ
Рассмотрим
конкретный
пример
.
Пусть
i
-
номер
дня
.
Нас
интересует
q
-
размер
партии
заказа
.
Известно
2
h
-
издержки
хранения
;
4
d
-
издержки
дефицита
;
i
r
-
столько
газет
куплено
(
для
непрерывной
задачи
пишем
r
вместо
i
r
);
i
P
-
вероятность
продажи
.
Ряд
распределения
запрашиваемых
газет
выглядит
так
i
r
0 1 2 3 4 5 6 7 8 9 10
i
P
0,1 0,05 0,15 0,1 0,05 0,1 0,1 0,1 0,15 0,1 0
Интересующая
нас
величина
q
ˆ
-
оптимальная
партия
.
Чтобы
ее
посчитать
,
нужно
знать
характеристическое
соотношение
затрат
)
ˆ
(
q
L
d
h
d
.
Учтем
,
что
)
ˆ
(
)
1
ˆ
(
q
L
d
h
d
q
L
,
где
)
1
(
)
(
)
(
0
1
q
r
P
P
q
L
q
i
q
i
i
i
i
.
Посчитаем
величину
667
,
0
6
/
4
d
h
d
и
заполним
таблицу
.
q
i
r
i
P
q
i
i
P
0
1
q
i
i
i
r
P
)
1
(
1
q
r
P
q
i
i
i
)
ˆ
(
q
L
0 0 0,1 0,1
0,25
0,125 0,225
1 1 0,05 0,15
0,2
0,3
0,45
2 2 0,15 0,3
0,12 0,31
0,615
3 3 0,1 0,4
0,09
0,34
0,71
4 4 0,05 0,45
0,08 0,36
0,81
5 5 0,1 0,55
0,06
0,33
6 6 0,1 0,65
0,04
7 7 0,1 0,75
0,03
8 8 0,15 0,9
0,01
9 9 0,1 1
0
Как
видно
из
таблицы
наше
3
ˆ
q
,
т
.
е
.
оптимальная
партия
газет
3
штуки
.
Задание
.
Написать
программу
,
реализующую
данный
алгоритм
.
Сделать
подробные
комментарии
и
инструкцию
пользователя
.
Необходимые
величины
взять
произвольными
и
для
них
определить
оптимальный
размер
партии
заказа
.