ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2021
Просмотров: 1233
Скачиваний: 3
Л.5. Построение математической модели
f
(
x
,
y
,
z
)
→
min
h
1
(
x
,
y
,
z
)
≤
0
,
h
2
(
x
,
y
,
z
)
≤
0
(
∗
)
Пока вектор
−∇
f
направлен из (
V
) (что распознается по знаку
h
1
), производим проецирование точек на
h
1
= 0
.
Если через какое-то число шагов вектор
−∇
f
направлен внутрь
(
V
), то связь снимается.
Если при спуске по поверхности
h
1
= 0
, приходим к точке, где и
второе неравенство (*) нарушено, то надо спроецировать на ребро
{
h
1
= 0
,
h
2
= 0
}
и в дальнейшем в соответствии с направлением
−∇
f
спускаться либо по этому ребру, либо по примыкающим к
нему граням (
h
1
= 0
и
h
2
= 0
).
Для выбора имеется алгоритм, определяемый
теоремой
Куна-Таккера
(нелинейное программирование).
2014
66 / 74
Л.5. Построение математической модели
Некоторые классы задач на экстремум с ограничениями:
Задача
линейного программирования
: целевая функция является
линейной, равно как и все уравнения и неравенства, связывающие
ее аргументы.
Задача
линейного целочисленного программирования
: аргументы
целевой функции по своему смыслу могут принимать только
целочисленные значения.
Задача
выпуклого программирования
: целевая функция и левые
части высвобождающих связей, записанных по образцу (*),
являются выпуклыми функциями, а все невысвобождающие связи
линейные.
Задача выпуклого программирования, для которой целевая
функция квадратична, а высвобождающие связи линейны,
называется задачей
квадратичного программирования
.
2014
67 / 74
Л.5. Построение математической модели
Класс задач, в которых используется
метод динамического
программирования
Пусть состояние некоторого объекта характеризуется величиной
x
(непрерывной или дискретной) и этот объект надо перевести из
заданного состояния
x
0
в момент
t
0
в заданное состояние
x
N
в момент
t
N
, подобрав для этого промежуточные состояния
x
1
,
x
2
, . . . ,
x
N
−
1
в
моменты
t
1
,
t
2
, . . .
t
N
−
1
.
Пусть при этом известна стоимость
f
i
(
x
,
y
)
перевода объекта из
состояния
x
в момент
t
i
в состояние
y
в момент
t
i
+1
.
Задача состоит в том, чтобы минимизировать общую сумму затрат:
f
0
(
x
0
,
x
1
) +
f
1
(
x
1
,
x
2
) +
· · ·
+
f
N
−
1
(
x
N
−
1
,
x
N
)
→
min
.
2014
68 / 74
Л.5. Построение математической модели
9. Задачи на экстремум с искомой функцией
функционал(функция)
→
min
Пример: задача о кривой наибыстрейшего спуска (Галилей).
Среди всех кривых, лежащих в плоскости
x
,
y
и имеющих заданные
концы
A
(
a
,
h
)
,
B
(
b
,
0)
, найти такую, двигаясь по которой под
действием только силы тяжести, материальная точка, отправляясь из
A
без начальной скорости, достигнет
B
за минимально возможное
время.
f
(
y
) =
Z
b
a
s
1 + [
y
′
(
x
)]
2
2
g
[
h
−
y
(
x
)]
dx
→
min
,
y
(
a
) =
h
,
y
(
b
) = 0
.
2014
69 / 74
Л.5. Построение математической модели
Задача на условный экстремум (изопериметрическая)
f
(
y
) =
Z
b
a
F
(
x
,
y
(
x
)
,
y
′
(
x
))
dx
→
min
,
y
(
a
) =
y
a
,
y
(
b
) =
y
b
,
g
(
y
) =
Z
b
a
G
(
x
,
y
(
x
)
,
y
′
(
x
))
dx
= 0
.
Пример: среди всех линий заданной длины на плоскости найти такую,
которая ограничивает фигуру наибольшей площади.
2014
70 / 74