Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи
Подождите немного. Документ загружается.
f(x) X
x, y ∈ X α ∈ (0, 1)
f(αx + (1 −α)y) ≤ max(f(x), f (y)) x 6= y
f(x)
X = {x ∈ E
n
| Ax ≥ a, Bx = b} A
B m × n l × n a ∈ E
m
, b ∈ E
l
x, y ∈ X z = αx + (1 − α)y
α ∈ [0, 1] Az = αAx + (1 − α)Ay ≥ αa + (1 − α)a = a Bz = αBx + (1 − α)By =
αb + (1 − α)b = b z X X
f
j
(x) (j = 1, m) E
n
X =
{x |f
j
(x) ≤ 0 (i = 1, m)}
f
j
(x) (j = 1, m) X
f(x) = a
1
f
1
(x) + . . . + a
m
f
m
(x) X a
j
≥ 0 (j = 1, m)
f
i
(x) (i ∈ I) X
f(x) = sup
i∈I
f
i
(x) X
B n ×n p ∈ E
n
f(x) = hBx, xi + hp, xi B
f(t) [a, b] a = −∞ b =
+∞ g(x) X ⊂ E
n
g(x) ∈ [a, b]
x ∈ X h(x) = f(g(x)) X
f(x) X
g(x) = (f(x))
p
p ≥ 1
f(x) x
1
∈ E
n
hf
0
(x
1
), x − x
1
i ≥ 0 x ∈ E
n
x
1
f(x)
f(x)
X
X
f(x)
X λ Z = {x ∈ X | f(x) ≤ λ}
f
j
(x) (j = 1, m) Z = {x ∈
X | f
j
(x) ≤ 0 (j = 1, m)}
f(x) X
Z(x) = {y ∈ X | f(y) ≤ f(x)} x ∈ X
f(x) X x
∗
∈ X
x
∗
f(x) X
f(x) g(x)
X x ∈ X f(x) ≥
g(x) h(x) f(x) ≥ h(x) ≥ g(x)
x ∈ X
a X
X = {(x, y) ∈ E
2
| a(x − y
2
) = 0, x + y = 1}
X = {(x, y) ∈ E
2
| a(x − y
2
) = 0, x + y = a}
X = {(x, y) ∈ E
2
| a(x − y
2
) ≤ 0, x + y = a}
X = {(x, y) ∈ E
2
| x
2
(a
2
+ 3a + 2) − y ≥ 0}
X = {(x, y) ∈ E
2
| e
x
(a
2
− 5a + 6) − y(a
2
+ 2) ≤ 0}
X = {(x, y) ∈ E
2
| y = e
ax
, y ≤ x}
X = {(x, y) ∈ E
2
| x
2
/(a
2
+ 1) + (y + a)
2
≤ 1, x
2
+ (y −1)
2
≤ a, }
X = {(x, y) ∈ E
2
| y ≤ e
x
, y ≤ ax}
X = {(x, y) ∈ E
2
| x + y ≥ 1, y ≤ ax
2
}
X = {(x, y) ∈ E
2
| y ≥ ln x, y ≥ ax, x > 0}
f(x) X
f(x) = x
1
x
2
, X = {x | x
1
≥ 0, x
2
≥ 0}
f(x) = 1/x
1
+ 1/x
2
, X = {x | x
1
≥ 0, x
2
≥ 0}
f(x) = x
2
− |x
1
− 2|, X = E
2
f(x) = x
6
1
+ x
2
2
+ x
2
3
+ x
2
4
+ 10x
1
+ 5x
2
− 3x
4
− 20, X = E
4
f(x) = e
2x
1
+x
2
, X = E
2
f(x) = −x
5
2
+ x
2
3
/2 + 7x
1
− x
3
+ 6, X = {x | x
i
≤ 0, i = 1, 2, 3}
f(x) = 3x
2
1
+ x
2
2
+ 2x
2
3
+ x
1
x
2
+ 3x
1
x
3
+ x
2
x
3
+ 3x
2
− 6, X = E
3
f(x) = x
3
1
+ 2x
2
3
+ 10x
1
+ x
2
− 5x
3
+ 6, X = {x | x
i
≤ 0, i = 1, 2, 3}
f(x) = 5x
2
1
+ x
2
2
/2 + 4x
2
3
+ x
1
x
2
+ 2x
1
x
3
+ 2x
2
x
3
+ x
3
+ 1, X = E
3
.
a, b, c f(x)
f(x) = ax
2
+ bx + c
f(x) = ax
2
1
+ 2bx
1
x
2
+ cx
2
2
f(x) = ae
2x
+ be
x
+ c
f(x) −→ min
x∈X
, (1)
X = {x | ϕ
j
(x) ≤ 0 (j = 1, m)}. (2)
f(x) ϕ
j
(x) (j = 1, m)
x
∗
∈ X
ϕ
j
(x) ≤ 0 ϕ
j
(x
∗
) = 0
I(x
∗
) = {j ∈ {1, . . . , m} | ϕ
j
(x
∗
) = 0}.
F (x, y) = f(x) +
m
X
j=1
y
j
ϕ
j
(x),
x ∈ E
n
, y ≥ 0
(x
∗
, y
∗
) x
∗
∈ E
n
, y
∗
≥ 0,
F (x, y) F(x
∗
, y) ≤ F (x
∗
, y
∗
) ≤ F (x, y
∗
) x ∈ E
n
, y ≥ 0
f(x) ϕ
j
(x) (j = 1, m)
x
∗
∈ X
y
j
≥ 0 (j ∈ I(x
∗
))
−f
0
(x
∗
) =
X
j∈I(x
∗
)
y
j
ϕ
0
j
(x
∗
).
(x
∗
, y
∗
) x
∗
X
x ∈ X ϕ
j
(x) < 0 j = 1, m
f(x) ϕ
j
(x)
(j = 1, m) X = {x | ϕ
j
(x) ≤ 0 (j = 1, m)}
x
∗
∈ X
y
j
≥ 0 (j ∈ I(x
∗
))
−f
0
(x
∗
) =
X
j∈I(x
∗
)
y
j
ϕ
0
j
(x
∗
). (3)
x
∗
∈ X
f(x) X = {x | ha
j
, xi − b
j
≤ 0 (j = 1, m)}
y
j
≥ 0 (j = 1, m)
−f
0
(x
∗
) =
X
j∈I(x
∗
)
y
j
a
j
.
x
∗
∈ X
s
hϕ
0
j
(x
∗
), si ≤ 0 (j ∈ I(x
∗
)) hf
0
(x
∗
), si ≥ 0
x
∗
X
x
∗
∈ X I(x
∗
)
(3) x
∗
(3) y
∗
≥ 0
x
0
= (0, 2) x
00
= (
√
5−1
2
,
3−
√
5
2
)
f(x) = 2x
2
1
+ 4x
2
2
− 2x
1
x
2
− 4(
√
5 − 2)x
1
− 5(2 −
√
5)x
2
−→ min x
2
1
+ x
2
2
≤
4, x
2
1
− x
2
≤ 0, x
1
+ x
2
≥ 1, x
1
≥ 0
f(x)
f
00
(x) =
µ
4 −2
−2 8
¶
ϕ
1
(x) = x
2
1
+ x
2
2
− 4, ϕ
2
(x) = x
2
1
−
x
2
, ϕ
3
(x) = −x
1
− x
2
+ 1 ϕ
4
(x) = −x
1
x = (0.5, 1) ϕ
j
(x) < 0 j = 1, 2, 3, 4
X = {x | ϕ
j
(x) ≤ 0, j = 1, 2, 3, 4}
x
0
x
00
X I(x
0
) =
{1, 4}, I(x
00
) = {2, 3}.
(3) x
0
−f
0
(x
0
) = y
1
ϕ
0
1
(x
0
) + y
4
ϕ
0
4
(x
0
)
µ
4
√
5 − 4
−5
√
5 − 6
¶
= y
1
µ
0
4
¶
+ y
4
µ
−1
0
¶
.
y
1
= (−5
√
5−6)/4, y
4
= 4−4
√
5
x
0
(3) x
00
−f
0
(x
00
) = y
2
ϕ
0
2
(x
00
) + y
3
ϕ
0
3
(x
00
)
µ
√
5 − 3
−3
¶
= y
2
µ
√
5 − 1
−1
¶
+ y
3
µ
−1
−1
¶
.
y
2
= 1, y
3
= 2
x
00
f(x)
X
x = (−1/2, 1/4) f(x) = e
x
2
−→
min ϕ
1
(x) ≡ (x
1
+ 1)
2
−x
2
≤ 0, ϕ
2
(x) ≡ (x
1
−1/2)
2
+ (x
2
+ 3/4)
2
−2 ≤ 0
ϕ
1
(x) = ϕ
2
(x) = 0, x I(x) = {1, 2}
(3) −f
0
(x) = y
1
ϕ
0
1
(x) + y
2
ϕ
0
2
(x) y
1
−2y
2
= 0, −y
1
+
2y
2
= −e
1/4
x
x
x
x
0
= (−3, 1, 2) x
00
= (−5, 3, 1)
f(x) = x
2
1
+2x
2
2
+30x
1
−16x
3
−→ min 5x
1
+3x
2
−4x
3
= −20, x
1
−6x
2
+3x
3
≤
0, x
3
≥ 0
ϕ
1
(x) ≡ 5x
1
+ 3x
2
− 4x
3
+ 20 ≤ 0, ϕ
2
= −ϕ
1
(x) ≡
−5x
1
− 3x
2
+ 4x
3
− 20 ≤ 0, ϕ
3
≡ x
1
− 6x
2
+ 3x
3
≤ 0, ϕ
4
(x) ≡ −x
3
≤ 0.
I(x
1
) = I(x
2
) = {1, 2} (3)
−f
0
(x) = y
1
ϕ
0
1
(x) + y
2
ϕ
0
2
(x) = (y
1
−y
2
)ϕ
0
1
(x) ϕ
2
(x) ≡ −ϕ
1
(x)
y = y
1
− y
2
x
∗
∈ X
y
j
≥ 0
y
j
−f
0
(x
∗
) =
X
j∈I(x
∗
)
y
j
ϕ
0
j
(x
∗
).
x
0
−24 = 5y, −4 = 3y, 16 =
−4y x
0
x
00
−20 = 5y, −12 = 3y, 16 = −4y
y = −4 y
x
00
f(x) = −2x
2
1
− 3x
2
2
+ x
1
− 6 −→ max
X
X = {x | x
2
1
+ x
1
− 3 ≤ 0, 2x
1
+ x
2
− 5 ≤ 0, x
2
≥ 0}
x
1
= (1, 1), x
2
= (2, 1), x
3
= (1/4, 0), x
4
= (0, 0)
f(x) = x
2
1
+ 3x
1
−→ min
X
X = {x | x
2
1
+ x
2
2
− 2x
1
+ 8x
2
+ 16 ≤ 0, x
1
− x
2
≤ 5}
x
1
= (1, −4), x
2
= (0, −4), x
3
= (2, −4);
f(x) = 7x
2
1
+ 2x
2
2
− x
1
x
2
+ x
1
− x
2
−→ min
X
X = {x | x
1
+ x
2
≤ 2, x
1
− 3x
2
≤ 4, −2x
1
+ x
2
≤ −3}
x
1
= (5/2, −1/2), x
2
= (1, −1), x
3
= (2, 0);
f(x) = x
2
1
/2 + x
2
2
− 5x
1
+ x
2
−→ min
X
X = {x | x
1
+ x
2
− 2x
3
≤ 3, 2x
1
− x
2
− 3x
3
≥ −11, x
1
≥ 0, x
2
≥ 0, x
3
≥ 0}
x
1
= (1, 0, 2), x
2
= (0, 0, −1), x
3
= (1, 3, 0), x
4
= (2, 1, 1), x
5
= (5, 0, 1);
f(x) = e
x
1
+x
2
+ x
2
1
− 2x
2
−→ min
X
X = {x | x
2
≤ ln x
1
, x
1
≥ 1, x
2
≥ 0}
x
1
= (2, ln 2), x
2
= (e, 0), x
3
= (1, 0);
f(x) = e
x
1
+x
2
+ x
2
3
+ 2x
1
+ 2x
2
−→ min
X
X = {x | x
2
1
+ x
2
2
+ x
2
3
≤ 18, 2x
1
+ x
2
− x
3
+ 3 ≤ 0}
x
1
= (−3, 3, 0), x
2
= (1, −1, 4), x
3
= (−3, −3, 0), x
4
= (0, 0, 3);
f(x) = −5x
2
1
− 6x
2
2
− x
2
3
+ 8x
1
x
2
+ x
1
−→ max
X
X = {x | x
2
1
− x
2
+ x
3
≤ 5, x
1
+ 5x
2
≤ 8, x
1
≥ 0, x
2
≥ 0}
x
1
= (0, 0, 0), x
2
= (1, 0, 4), x
3
= (3/14, 1/7, 0), x
4
= (4, 0, −11);
f(x) = −x
2
1
− 2x
2
2
+ x
1
x
2
− 26 −→ max
X
X = {x | x
2
1
≤ 25, x
1
+ 2x
2
− 5 ≤ 0, x
2
≥ 0}
x
1
= (0, 0), x
2
= (−1, 2), x
3
= (0, −6), x
4
= (3, 0);
f(x) = 10x
2
1
+ 5x
2
2
− x
1
+ 2x
2
− 10 −→ min
X
X = {x | 2x
2
1
+ x
2
≤ 4, x
1
+ x
2
≤ 8, x
1
≥ 0}
x
1
= (0, 0), x
2
= (1, 1), x
3
= (0, −1);
f(x) = 4x
2
1
+ 3x
2
2
+ 4x
1
x
2
− x
1
+ 6x
2
− 5 −→ min
X
X = {x | − x
2
1
− x
2
2
≥ −3, 3x
2
1
+ x
2
≤ 4, x
1
≥ 0, x
2
≥ 0}
x
1
= (0, 0), x
2
= (5, 0), x
3
= (1, −1), x
4
= (1, 1);
f(x) = x
2
1
+ 5/2x
2
2
− x
1
x
2
−→ min
X
X = {x | x
2
1
− 4x
1
− x
2
≤ −5, −x
2
1
+ 6x
1
− x
2
≥ 7}
x
1
= (2, 1), x
2
= (3, 2)
I = {1, . . . , m}, J = {1, . . . , n}, I
1
, I
2
⊂ I, J
1
⊂ J, I
1
∪ I
2
=
I, I
1
∩ I
2
= ∅. c
j
, b
i
, a
ij
(i ∈ I, j ∈ J)
x
w(x) =
n
X
j=1
c
j
x
j
a
i
x − b
i
≥ 0, i ∈ I
1
;
a
i
x − b
i
= 0, i ∈ I
2
;
x
j
≥ 0, j ∈ J
1
.
a
i
= (a
i1
, . . . , a
in
) i A, i ∈ I x = (x
1
, . . . , x
n
)
>
J
1
= J
I
1
= ∅
I
2
= ∅
w(x) = cx → min,
Ax = b,
x ≥ 0,
c = (c
1
, . . . , c
n
) x b = (b
1
, . . . , b
m
)
>
A = (a
ij
)
m × n.
w(x) = cx → min,
Ax ≥ b,
x ≥ 0.
−1
n
X
j=1
a
ij
x
j
≤ b
i
−1
n
X
j=1
a
0
ij
x
j
≥ b
0
i
,
a
0
ij
= −a
ij
, b
0
i
= −b
i
.
n
X
j=1
a
ij
x
j
≥ b
i
y
i
=
n
X
j=1
a
ij
x
j
− b
i
≥ 0.
n
X
j=1
a
ij
x
j
− y
i
= b
i
,
y
i
≥ 0.
n
X
j=1
a
ij
x
j
= b
i
n
X
j=1
a
ij
x
j
≥ b
i
,
n
X
j=1
a
ij
x
j
≤ b
i
.
x
j
x
j
= x
1
j
− x
2
j
, x
1
j
≥ 0, x
2
j
≥ 0.
x
1
+ x
2
→ max,
2x
1
+ x
2
≥ 1,
x
1
− x
2
≤ 0,
x
1
≥ 0.
−1
w(x) = −x
1
− x
2
.
x
3
≥ 0, x
4
≥ 0 :
2x
1
+ x
2
− x
3
= 1,
x
1
− x
2
+ x
4
= 0.
x
2
x
5
≥
0, x
6
≥ 0 :
x
2
= x
5
− x
6
.
−x
1
− x
5
+ x
6
→ min,
2x
1
− x
3
+ x
5
− x
6
= 1,
x
1
+ x
4
− x
5
+ x
6
= 0,
x
i
≥ 0 (i = 1, 3, 4, 5, 6).
w(x) = 2x
1
− x
2
→ min,
x
1
− x
2
≤ 1,
2x
1
+ x
2
= 2,
x
2
≥ 0.
x
1
x
3
≥ 0, x
4
≥ 0 :
x
1
= x
3
− x
4
.
2x
1
+ x
2
≤ 2,
2x
1
+ x
2
≥ 2.
−x
2
+ 2x
3
− 2x
4
→ min,
−x
2
+ x
3
− x
4
≤ 1,
x
2
+ 2x
3
− 2x
4
≤ 2,
−x
2
− 2x
3
+ 2x
4
≤ −2,
x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
x
1
− x
2
+ x
3
−→ max
x
1
− x
2
= 0, x
2
≤ 1, x
3
≥ 0
x
1
+ x
2
+ 3x
3
−→ max
2x
1
+ x
2
+ x
3
≤ 1, x
2
+ x
3
≥ 0, x
2
≥ 0, x
3
≥ 0
x
1
− x
2
− x
3
− x
4
−→ min
x
1
+ x
2
− x
4
≤ 1, −x
1
+ x
2
+ x
4
≤ 1, x
2
+ x
3
= 1,
x
1
≥ 0, x
2
≥ 0
x
1
− x
2
− 2x
3
− 3x
4
−→ min
x
1
− x
2
+ x
3
+ x
4
= 1, −x
1
− x
4
≤ 5, x
2
+ x
3
≥ 10,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0
x
1
− x
2
− x
3
+ 10x
4
−→ max
x
1
+ x
2
+ x
3
+ x
4
= 1, x
2
+ x
3
+ x
4
= 1, x
3
+ x
4
= 1
cx → min,
Ax ≥ b,
x ≥ 0
y = (y
1
, . . . , y
m
)
>
cx → min,
Ax − Ey = b,
x ≥ 0, y ≥ 0
E m × m (x, y)
x
n
X
j=1
c
j
x
j
→ min,
n
X
j=1
a
ij
x
j
≥ b
i
, i ∈ I
1
,
n
X
j=1
a
ij
x
j
= b
i
, i ∈ I
2
,
x
j
≥ 0, j ∈ J
1
.
y
i
(i ∈
I
1
) x
j
(j ∈ J \ J
1
)
x
j
= x
1
j
− x
2
j
, j ∈ J \ J
1
.
X
j∈J
1
c
j
x
j
+
X
j∈J\J
1
c
j
(x
1
j
− x
2
j
) → min,
X
j∈J
1
a
ij
x
j
+
X
j∈J\J
1
a
ij
(x
1
j
− x
2
j
) − y
i
= b
i
, i ∈ I
1
,
X
j∈J
1
a
ij
x
j
+
X
j∈J\J
1
a
ij
(x
1
j
− x
2
j
) = b
i
, i ∈ I
2
,
x
j
≥ 0, j ∈ J
1
, x
1
j
≥ 0, x
2
j
≥ 0, j ∈ J \ J
1
,
y
i
≥ 0, i ∈ I
1
.
x
j
(j ∈ J
1
), x
1
j
, x
2
j
(j ∈ J \ J
1
), y
i
(i ∈ I
1
)
x
j
(j ∈ J
1
), x
j
= x
1
j
− x
2
j
(j ∈ J \ J
1
)
A m (m ≤ n) A m
A
j
= (a
1j
, . . . , a
mj
)
>
, j ∈
J
A
σ(1)
, . . . , A
σ(m)
m
B = [A
σ(1)
, . . . , A
σ(m)
]
A A = [B, N] N
A
x x =
³
x
B
x
N
´
x
B
= (x
σ(1)
, . . . , x
σ(m)
)
>
x
j
x
B
x
N
x =
³
x
B
x
N
´
=
³
B
−
1
b
0
´
B
x
{A
j
| x
j
6= 0, j ∈ J} A
C
m
n
X = {x | Ax = b, x ≥ 0} Ax = b
B
B
−1
b ≥ 0
x
x X
X 6= ∅
X 6= ∅ w(x) X
x
1
+ x
2
+ x
3
+ x
4
= 1,