ВУЗ:
Составители:
Рубрика:
5
§ 1. Постановка задачи математического
программирования
Под задачей математического программирования понимается задача
нахождения в векторном пространстве R
n
такого вектора
*
x
, который
обеспечивает оптимальное (минимальное или максимальное) значение
функции
)
(
x
f
и при этом принадлежит некоторой области
n
R⊆Ω .
Рассмотрим следующую постановку задачи :
n
Rx
min)x(f
⊆∈
→
Ω
, (1)
где
nxxx
n1
−
=
),..,(
- мерный вектор,
−
)
(
x
f
функция, называемая функцией
цели ,
−⊆Ω
n
R
допустимое множество.
Задача поиска максимума функции
)
(
x
f
сводится к задаче поиска
минимума путем умножения целевой функции на -1:
))x(f(min)x(fmax
nn
RxRx
−
−
=
⊆∈⊆∈ ΩΩ
Задача поиска минимума и максимума называется задачей поиска
экстремума:
n
Rx
extrxf
⊆Ω∈
→
)(
Если
n
R
=
Ω
, то имеет место задача безусловной оптимизации. В противном
случае, т.е. если
n
R
⊂
Ω
– задача условной оптимизации.
Определение 1. Точка
Ω
∈
*
x
называется точкой глобального минимума
функции
)
(
x
f
на множестве
Ω
, если функция достигает в этой точке своего
наименьшего значения, т.е.
Ω
∈
∀
≤
x
x
f
x
f
),
(
*)
(
.
При этом используется обозначение
)x(fminarg*x
x Ω∈
=
.
Определение 2. Точка
Ω
∈
*
x
называется точкой локального минимума
функции
)
(
x
f
на множестве
Ω
, если
,
0
>
∃
ε
такое
что
∩
Ω
∈
∀
)
(
:
x
x
(
ε
<
−
||
*
||
x
x
), справедливо неравенство
)
(
*)
(
x
f
x
f
≤
.
Замечание 1. В качестве нормы вектора в
n
R
используется евклидова
норма:
∑
=
=
n
1i
2
i
xx ||||
5
§ 1. Постановка задачи математического
программирования
Под задачей математического программирования понимается задача
нахождения в векторном пространстве Rn такого вектора x * , который
обеспечивает оптимальное (минимальное или максимальное) значение
функции f (x) и при этом принадлежит некоторой области Ω ⊆ R n .
Рассмотрим следующую постановку задачи:
f ( x ) → min n , (1)
x∈Ω ⊆R
где x =( x1 ,.., x n ) −n -мерный вектор, f (x) −функция, называемая функцией
цели, Ω ⊆ R n −допустимое множество.
Задача поиска максимума функции f (x) сводится к задаче поиска
минимума путем умножения целевой функции на -1:
max f ( x ) =− min n ( −f ( x ))
x∈Ω ⊆R n x∈Ω ⊆R
Задача поиска минимума и максимума называется задачей поиска
экстремума:
f ( x) → extr
x∈Ω ⊆R n
Если Ω =R n , то имеет место задача безусловной оптимизации. В противном
случае, т.е. если Ω ⊂ R n – задача условной оптимизации.
Определение 1. Точка x* ∈Ω называется точкой глобального минимума
функции f (x) на множестве Ω , если функция достигает в этой точке своего
наименьшего значения, т.е. f ( x*) ≤ f ( x), ∀x ∈Ω .
При этом используется обозначение x* =arg min f ( x ) .
x∈Ω
Определение 2. Точка x* ∈Ω называется точкой локального минимума
функции f (x) на множестве Ω , если ∃ε >0, такое
что ∀x : ( x ∈Ω) ∩ ( || x −x* ||<ε ), справедливо неравенство f ( x*) ≤ f ( x) .
Замечание 1. В качестве нормы вектора в R n используется евклидова
n
норма: || x ||= ∑ xi2
i =1
