Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
x y
(x, y) x y
A A = {(x, y) ∈ IR × IR :
x = y} A
A A
A = {x : (x, y) ∈ A y}.
A
A A
A = {y : (x, y) ∈ A x}.
f
(x, y) ∈ f (x, y
∗
) ∈ f y = y
∗
{1, 2, . . . , n} n
n
{1, 2, . . . , n} n
IR
n
IR
n
n
n n
n x x = (x
1
, x
2
, . . . x
n
)
IR
n
n x = (x
1
, x
2
, . . . x
n
)
x = (x
1
, x
2
, . . . x
n
)
T
x
T
= (x
1
, x
2
. . . x
n
)
←−−
P Q P Q
p, q ∈ IR
n
θp + (1 −θ)q, 0 ≤ θ ≤ 1.
q + θ(p − q) 0 ≤ θ ≤ 1,
q θ
(0 ≤ θ ≤ 1) (p − q) Q
P θ γ, γ = 1 − θ
P Q
S
∀p, q ∈ S : θp + (1 − θ)q ∈ S, 0 ≤ θ ≤ 1,
S S
S
b ∈ S S
p, q ∈ S b = θp + (1 − θ)q
0 < θ < 1
P
1
, P
2
, . . . P
k
p
1
, p
2
, . . . p
k
y = θ
1
p
1
+ θ
2
p
2
+ . . . θ
k
p
k
,
k
X
i=1
θ
i
= 1, 0 ≤ θ
i
, i = 1, k.
θ
i
P
1
, P
2
y
2
= k
2
p
2
+ (1 − k
2
)p
1
, 0 ≤ k
2
≤ 1,
P
1
P
2
.
P
3
y
3
= k
3
p
3
+(1−k
3
)y
2
= k
3
p
3
+(1−k
3
)k
2
p
2
+(1−k
3
)(1−k
2
)p
1
, 0 ≤ k
3
≤ 1,
P
1
P
2
P
3
P
4
y
4
= k
4
p
4
+ (1 − k
4
)y
3
= k
4
p
4
+ (1 − k
4
)k
3
p
3
+
+(1 − k
4
)(1 − k
3
)k
2
p
2
+ (1 − k
4
)(1 − k
3
)(1 − k
2
)p
1
, 0 ≤ k
4
≤ 1,
P
1
P
2
P
3
P
4
P
5
y
4
y
5
= k
5
p
5
+(1−k
5
)y
4
=
= k
5
p
5
+(1−k
5
)(k
4
p
4
+(1−k
4
)(k
3
p
3
+(1−k
3
)(k
2
p
2
+(1−k
2
)p
1
))), 0 ≤ k
5
≤ 1,
P
1
P
2
P
3
P
4
P
5
y
5
= θ
5
p
5
+ θ
4
p
4
+ θ
3
p
3
+ θ
2
p
2
+ θ
1
p
1
,
θ
5
= k
5
θ
4
= (1 − k
5
)k
4
θ
3
= (1 − k
5
)(1 − k
4
)k
3
θ
2
= (1 − k
5
)(1 − k
4
)(1 − k
3
)k
2
θ
1
= (1 − k
5
)(1 − k
4
)(1 − k
3
)(1 − k
2
)
θ
i
θ
1
+ θ
2
+ θ
3
+ θ
4
+ θ
5
= 1, θ
i
≥ 0, i = 1, 5.
θ
i
, 0 ≤ θ
i
≤ 1
k
5
= θ
5
, 0 ≤ k
5
≤ 1;
k
4
=
θ
4
(1 − θ
5
)
=
θ
4
(θ
1
+ θ
2
+ θ
3
+ θ
4
)
, 0 ≤ k
4
≤ 1;
k
3
=
θ
3
(1 − θ
5
− θ
4
)
=
θ
3
(θ
1
+ θ
2
+ θ
3
)
, 0 ≤ k
3
≤ 1;
k
2
=
θ
2
(1 − θ
5
− θ
4
− θ
3
)
=
θ
2
(θ
1
+ θ
2
)
, 0 ≤ k
2
≤ 1.
k
2
, k
3
, k
4
k
5
(k
2
) (k
3
)
(k
4
) (k
5
)
p
1
, p
2
, . . . , p
k
θ
1
+ θ
2
+ . . . + θ
k
= 1
θ
i
y = θ
1
p
1
+ θ
2
p
2
+ . . . + θ
k
p
k
.
f A
f, f
A
f
A A
f
A
(t) = f(t) t ∈ A .
f f
n
C ⊆ f f C
f(x)
n x = (x
1
, x
2
, . . . , x
n
)
f
1
(x), . . . , f
n
(x) f
i
(x) = ∂f (x)/∂x
i
f x n
grad f(x) ≡ (f
1
(x), . . . , f
n
(x)).
f n
f f
−grad f(x)
f
f n
f
f
Ax = b, A = A(m, n), rankA = m, (m < n), x ∈ IR
n
,
b ∈ IR
m
x, x ≥ 0 ∀i :
x
i
≥ 0
min
x
c
T
x c ∈ IR
n
c = (c
1
, c
2
, . . . , c
n
)
z = c
T
x grad z = c
x ∈ IR
n
m × m
m ×(n + 1) A
a
= [A | b]
X IR
n
Ax = b, x ≥ 0
X
X = {x ∈ IR
n
: Ax = b, x ≥ 0}
x, y X
Ax = b, x ≥ 0; Ay = b, y ≥ 0.
w
w = αx + βy, α + β = 1, α ≥ 0, β ≥ 0, w ≥ 0.
Aw = A(αx + βy) = αAx + βAy = α b + βb = (α + β)b = b
Aw = b, w ≥ 0
x = P
µ
B
−1
b
O
¶
,
P A
AP = [B |R] B m×m O (n−m)
R (n−m)
B
¡
n
m
¢
=
n!
m!(n−m)!
m A n
P
m A
B Ax = b
AP y = b y = P
−1
x
y y = (y
B
, y
F
), y
B
m
y
F
(n − m)
y
B
= B
−1
b − B
−1
Ry
F
, y =
µ
B
−1
b − B
−1
Ry
F
y
F
¶
.
y AP y = b
y
F
y =
µ
B
−1
b
O
¶
.
x x = P y
x
x = P y,
n−m y
F
y
AP y = b
m x = P y
P
P
a
i
∈ IR
m
, i = 1, n
A
A = [a
1
, a
2
, . . . , a
n
].
x
1
a
1
+ x
2
a
2
+ . . . + x
n
a
n
= b.
A rankA = m
n m
C
m
n
=
¡
n
m
¢
=
n!
m!(n−m)!
n m
x
i
a
i
m
x = (x
1
, x
2
, . . . , x
n
)
x
i
≥ 0 i = 1, n
x = (x
1
, x
2
, . . . , x
n
)
a
i
x
i
x = (x
1
, x
2
, . . . , x
n
)
a
i
x
i
, x
i
> 0
r
m, r
≤
m
a
i
m