Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
w = x
6
+ x
7
+ x
8
→ min x
6
x
7
x
8
w
2 1 −1 0 0 1 0 0 7
1 1 0 −1 0 0 1 0 4
→ 1 3 0 0 −1 0 0 1 9
−2 −3 0 0 0 0 0 0 0
−4 −5 1 1 1 0 0 0 −20
↑
NB
6
7
8
NF
1
2
3
4
5
= (0, 0, 0, 0, 0, 7, 4, 9) = , z = 0, w = 20.
1
◦
. l = 2 s = 2.
2
◦
. min(
7
1
,
4
1
,
9
3
) = 3 ⇒ k = 3.
3
◦
.
2 1 −1 0 0 1 0 0 7
1 1 0 −1 0 0 1 0 4
→ 1/3 1 0 0 −1/3 0 0 1/3 3
−2 −3 0 0 0 0 0 0 0
−4 −5 1 1 1 0 0 0 −20
↑
4
◦
.
5/3 0 −1 0 1/3 1 0 −1/3 4
→ 2/3 0 0 −1 1/3 0 1 −1/3 1
1/3 1 0 0 −1/3 0 0 1/3 3
−1 0 0 0 −1 0 0 1 9
−7/3 0 1 1 −2/3 0 0 5/3 −5
↑
NB
6
7
2
NF
1
8
3
4
5
= (0, 3, 0, 0, 0, 4, 1, 0) z = −9, w = 5.
1
◦
. l = 1 s = 1.
2
◦
. min(
4
5/3
,
1
2/3
,
3
1/3
) = 3/2 ⇒ k = 2.
3
◦
.
5/3 0 −1 0 1/3 1 0 −1/3 4
→ 1 0 0 −3/2 1/2 0 3/2 −1/2 3/2
1/3 1 0 0 −1/3 0 0 1/3 3
−1 0 0 0 −1 0 0 1 9
−7/3 0 1 1 −2/3 0 0 5/3 −5
↑
4
◦
.
→ 0 0 −1 5/2 −1/2 1 −5/2 1/2 3/2
1 0 0 −3/2 1/2 0 3/2 −1/2 3/2
0 1 0 1/2 −1/2 0 −1/2 1/2 5/2
0 0 0 −3/2 −1/2 0 3/2 1/2 21/2
0 0 1 −5/2 1/2 0 7/2 1/3 −3/2
↑
NB
6
1
2
NF
7
8
3
4
5
=
µ
3
2
,
5
2
, 0, 0, 0,
3
2
, 0, 0
¶
z = −21/2, w = 3/2.
1
◦
. l = 4 s = 4.
2
◦
. min(
3/2
5/2
, ∞,
5/2
1/2
) = 3/5 ⇒ k = 1.
3
◦
.
→ 0 0 −2/5 1 −1/5 2/5 −1 1/5 3/5
1 0 0 −3/2 1/2 0 3/2 −1/2 3/2
0 1 0 1/2 −1/2 0 −1/2 1/2 5/2
0 0 0 −3/2 −1/2 0 3/2 1/2 21/2
0 0 1 −5/2 1/2 0 7/2 1/2 −3/2
↑
4
◦
.
0 1 −2/5 1 −1/5 2/5 −1 1/5 3/5
1 0 −3/5 0 1/5 3/5 0 −1/5 12/5
0 1 1/5 0 −2/5 −1/5 0 2/5 11/5
0 0 −3/5 0 −4/5 3/5 0 4/5 57/5
0 0 0 0 0 1 1 1 0
NB
4
1
2
NF
7
8
3
6
5
=
µ
12
5
,
11
5
, 0,
3
5
, 0, 0, 0, 0
¶
z = −57/5, w = 0.
x
6
x
7
x
8
w
0 0 −2/5 1 −1/5 3/5
→ 1 0 −3/5 0 1/5 12/5
0 1 1/5 0 −2/5 11/5
0 0 −3/5 0 −4/5 57/5
↑
NB
4
1
2
NF
3
5
1
◦
. l = 2 s = 5.
2
◦
. min(∞,
12/5
1/5
, ∞) = 12 ⇒ k = 2.
3
◦
. 4
◦
.
0 0 −2/5 1 −1/5 3/5
→ 5 0 −3 0 1 12
0 1 1/5 0 −2/5 11/5
0 0 −3/5 0 −4/5 57/5
↑
1 0 −1 1 0 3
5 0 −3 0 1 12
2 1 −1 0 0 7
4 0 −3 0 0 21
NB
4
5
2
NF
3
1
= (0, 7, 0, 3, 12) z = −21.
1
◦
. l = 1 s = 3.
2
◦
. min(∞, ∞, ∞) = ∞ ⇒
∞
∞
x
1
x
2
≥ 0
x
1
− x
2
≥ 1;
x
2
≤ 2;
−x
1
− x
2
= z → min .
→ 1 −1 −1 0 1
0 1 0 1 2
−1 −1 0 0 0
↑
NB
3
4
NF
1
2
= (0, 0, −1, 2) 6= , z = 0.
1
◦
. s = 1.
2
◦
. min(∞, ∞) = ∞ ⇒ k = 1.
3
◦
.
4
◦
.
1 −1 −1 0 1
→ 0 1 0 1 2
0 −2 −1 0 1
↑
NB
1
4
NF
3
2
= (1, 0, 0, 2) = , z = −1.
1
◦
. s = 2.
2
◦
. min(∞, 2/1) ⇒ k = 2.
3
◦
.
4
◦
.
→ 1 0 −1 1 3
0 1 0 1 2
0 0 −1 2 5
↑
NB
1
2
NF
3
4
= (3, 2, 0, 0) = , z = −5.
1
◦
. s = 3.
2
◦
. min(∞, ∞) ⇒ k = 1.
3
◦
. 4
◦
.
→ −1 0 1 −1 − 3
0 1 0 1 2
0 0 −1 2 5
↑
→ −1 0 1 −1 −3
0 1 0 1 2
−1 0 0 1 2
↑
NB
3
2
NF
1
4
= (0, 2, −3, 0) 6= , z = −2.
1
◦
. s = 1.
2
◦
. min(∞, ∞) ⇒ k = 1.
3
◦
. 4
◦
.
→ 1 0 −1 1 3
0 1 0 1 2
−1 0 0 1 2
↑
→ 1 0 −1 1 3
0 1 0 1 2
0 0 −1 2 5
NB
1
2
NF
3
4
= (3, 2, 0, 0) = , z = −5.
z
∞
x
1
x
2
≥ 0
2x
1
+ x
2
≤ 7;
x
1
+ x
2
≤ 4;
x
1
+ 3x
2
≤ 9;
−x
1
− x
2
= z → min .
2 1 1 0 0 7
1 1 0 1 0 4
→ 1 3 0 0 1 9
−1 −1 0 0 0 0
↑
NB
3
4
5
NF
1
2
= (0, 0, 7, 4, 9) = , z = 0.
1
◦
. l = 2 s = 2.
2
◦
. min(7/1, 4/1, 9/3) = 3 ⇒ k = 3.
3
◦
. 4
◦
.
2 1 1 0 0 7
1 1 0 1 0 4
→ 1/3 1 0 0 1/3 3
−1 −1 0 0 0 0
↑
5/3 0 1 0 −1/3 4
→ 2/3 0 0 1 −1/3 1
1/3 1 0 0 1/3 3
−2/3 0 0 0 1/3 3
↑
NB
3
4
2
NF
1
5
= (0, 3, 4, 1, 0), z = −3.
1
◦
. l = 1 s = 1.
2
◦
. min(
4
5/3
,
1
2/3
,
3
1/3
) = 3/2 ⇒ k = 2.
3
◦
. 4
◦
.
5/3 0 1 0 −1/3 4
→ 1 0 0 3/2 −1/2 3/2
1/3 1 0 0 1/3 3
−2/3 0 0 0 1/3 3
↑
→ 0 0 1 −5/2 1 /2 3/2
1 0 0 3/2 −1/2 3/2
0 1 0 −1/2 1/2 5/2
0 0 0 1 0 4
↑
3
1
2
5
4
= (
3
2
,
5
2
,
3
2
, 0, 0), z = −4.
x
5
z
1
◦
. l = 2 s = 5.
2
◦
. min(
3/2
1/2
, ∞,
5/2
1/2
) = 3 ⇒ k = 1.
3
◦
. 4
◦
.
→ 0 0 2 −5 1 3
1 0 0 3/2 −1/2 3/2
0 1 0 −1/2 1/2 5/2
0 0 0 1 0 4
↑
→ 0 0 2 −5 1 3
1 0 1 −1 0 3
0 1 −1 2 0 1
0 0 0 1 0 4
↑
NB
5
1
2
NF
4
3
= (3, 1, 0, 0, 3), z = −4.
x
3
1
◦
. l = 2 s = 3.
2
◦
. min(
3
2
,
3
1
, ∞) = 3/2 ⇒ k = 1.
3
◦
. 4
◦
.
→ 0 0 1 −5/2 1/2 3/2
1 0 1 −1 0 3
0 1 −1 2 0 1
0 0 0 1 0 4
↑
0 0 1 −5/2 1/2 3/2
1 0 0 3/2 −1/2 3/2
0 1 0 −1/2 1/2 5/2
0 0 0 1 0 4
NB
3
1
2
NF
4
5
= (3/2, 5/2, 3/2, 0, 0), z = −4.
=
µ
3 −
3
2
θ, 1 +
3
2
θ,
3
2
θ, 0, 3 − 3θ
¶
,
0 ≤ θ ≤ 1
≥ ≤
≥ ≤
−1
≥ ≤
≥ ≤ ≥
≥ ≤
= ≤ ≥ ≤
= ≥ ≤ ≥
= ≥ ≤
=
= ≤ ≥ ≤