Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
x
1
, x
2
≥ 0
x
1
+ x
2
≥ 3;
x
1
+ 2x
2
≤ 2;
−x
1
− x
2
= z → min .
−1 −1 1 0 −3
→ 1 2 0 1 2
−1 −1 0 0 0
↑
NB
3
4
NF
1
2
= (0, 0, −3, 2) 6= , z = 0.
1
◦
. s
2
◦
. min(∞, 2/1) = 2 ⇒ k = 2.
3
◦
.
4
◦
.
→ 0 1 1 1 −1
1 2 0 1 2
0 1 0 1 2
NB
3
1
NF
4
2
= (2, 0, −1, 0) 6= , z = −2.
1
◦
. k
2
◦
. k
x
5
w = x
5
, w → min .
x
3
x
4
x
5
1 1 −1 0 1 3
1 2 0 1 0 2
−1 −1 0 0 0 0
0 0 0 0 1 0
x
B
= (x
4
, x
5
) w = x
5
1 1 −1 0 1 3
→ 1 2 0 1 0 2
−1 −1 0 0 0 0
−1 −1 1 0 0 −3
↑
NB
5
4
NF
1
2
3
= (0, 0, 0, 2, 3) = , z = 0, w = 3.
1
◦
. l s
2
◦
. min(
3
1
,
2
1
) = 2 ⇒ k = 2
3
◦
.
4
◦
.
0 −1 −1 −1 1 1
1 2 0 1 0 2
0 1 0 1 0 2
0 1 1 1 0 −1
NB
5
1
NF
4
2
3
= (2, 0, 0, 0, 1) = , z = −2, w = 1.
1
◦
.
w w
min
= 1.
4
◦
x
5
Ax =
b, c
T
x = z → min
m ×m [A, b]
m×(n+1)
b
0
A
0
x = b
0
b
0
x
1
, x
2
≥ 0
−2x
1
+ x
2
≤ 2;
−x
1
+ 2x
2
≤ 4;
x
1
+ x
2
≤ 8;
x
1
− 3x
2
= z → min .
−2 1 1 0 0 2
−1 2 0 1 0 4
1 1 0 0 1 8
1 −3 0 0 0 0
NB
3
4
5
NF
1 1
2 2
= (0, 0, 2, 4, 8) = , z = 0.
1
◦
. l = 2 s = 2
2
◦
. min
¡
2
1
,
4
2
,
8
1
¢
= min(2, 2, 8).
k = 1 k = 2
3
◦
.
4
◦
.
−2 1 1 0 0 2
3 0 −2 1 0 0
3 0 −1 0 1 6
−5 0 3 0 0 6
↑
NB
2
4
5
NF
1 1
2 3
= (0, 2, 0, 0, 6) = , z = −6.
x
4
= 0
1
◦
. l = 1, s = 1
2
◦
. min(∞, −∞, 6/3)
(−∞) s
s
k
0
1
◦
. l = 2, s = 2
2
◦
. min
¡
2
1
,
4
2
,
8
1
¢
= min(2, 2, 8). k = 2 k = 1
3
◦
. 4
◦
.
−2 1 1 0 0 2
→ −1/2 1 0 1/2 0 2
1 1 0 0 1 8
1 −3 0 0 0 0
↑
−3/2 0 1 −1/2 0 0
−1/2 1 0 1/2 0 2
→ 3/2 0 0 −1/2 1 6
−1/2 0 0 3/2 0 6
↑
NB
3
2
5
NF
1 1
2 4
= (0, 2, 0, 0, 6) = , z = −6.
x
3
= 0
0
1
◦
. l = 1, s = 1.
2
◦
. min
³
∞, ∞,
6
3/2
´
⇒ k = 3.
3
◦
. 4
◦
.
−3/2 0 1 −1/2 0 0
−1/2 1 0 1/2 0 2
→ 1 0 0 −1/3 2/3 4
−1/2 0 0 3/2 0 6
↑
0 0 1 −1 1 6
0 1 0 1/3 1/3 4
1 0 0 −1/3 2/3 4
0 0 0 4/3 1/3 8
NB
3
2
1
NF
1 5
2 4
= (4, 4, 6, 0, 0) = , z
min
= −8.
(−∞)
1
◦
. l = 1, s = 1.
2
◦
. min(∞, −∞, 6/3). k = 2
3
◦
. 4
◦
.
−2 1 1 0 0 2
→ 1 0 −2/3 1/3 0 0
3 0 −1 0 1 6
−5 0 3 0 0 6
↑
0 1 −1/3 2/3 0 2
→ 1 0 −2/3 1/3 0 0
0 0 1 −1 1 6
0 0 −1/3 5/3 0 6
↑
NB
2
1
5
NF
4
3
= (0, 2, 0, 0, 6) = , z = −6.
x
1
= 0
1
◦
. l = 2, s = 3.
2
◦
. min(∞, ∞, 6/1) k = 2
3
◦
. 4
◦
.
0 1 −1/3 2/3 0 2
→ −3/2 0 1 −1/2 0 0
0 0 1 −1 1 6
0 0 −1/3 5/3 0 6
↑
−1/2 1 0 1/2 0 2
→ −3/2 0 1 −1/2 0 0
3/2 0 0 −1/2 1 6
−1/2 0 0 3/2 0 6
↑
NB
2
3
5
NF
4
1
= (0, 2, 0, 0, 6) = , z = −6.
x
3
= 0
1
◦
. l = 2, s = 1.
2
◦
. min
³
∞, ∞,
6
3/2
´
. k = 2
3
◦
. 4
◦
.
−1/2 1 0 1/2 0 2
→ 1 0 −2/3 1/3 0 0
3/2 0 0 −1/2 1 6
−1/2 0 0 3/2 0 6
↑
0 1 −1/3 2/3 0 2
1 0 −2/3 1/3 0 0
0 0 1 −1 1 6
0 0 −1/3 5/3 0 6
NB
2
1
5
NF
4
3
= (0, 2, 0, 0, 6) = , z = −6.
x
1
= 0
(x
1
, x
2
) = (0, 2)
x
1
= 0
x
3
= 0 −2x
1
+ x
2
= 2
x
4
= 0 −x
1
+ 2x
2
= 4
x
1
= 0 x
3
= 0 x
1
= 0 x
4
= 0
x
3
= 0 x
4
= 0
z = −6
k = 2
b
0
k
= 0
b
0
k
= 0 x
4
= 0 b
0
k
= 0
x
1
= 0 b
0
k
= 0 x
3
= 0
ε
i
i = 1, 2, . . . , m
i
ε = 0
1
0
2
0
z = 0
x
4
= 0
z = −6
-
-
x
1
= 0
z = −6-
x
3
= 0
z = −6
z = −8
-
C
0
C
1
C
2
C
∗
?
C
3
6
z = −16
-
3
00
2
00
C
4
1
0
-
6
?
2
0
-
-
-
¾
-
C
0
C
∗
C
1
, C
2
, C
3
x
4
, x
1
, x
3
C
4
C
1
C
2
←
→
C
3
C
1
00
1
◦
. l = 1, s = 1.
2
◦
. min(∞, −∞, 6/3). k = 3
3
◦
. 4
◦
.
−2 1 1 0 0 2
3 0 −2 1 0 0
→ 1 0 −1/3 0 1 /3 2
−5 0 3 0 0 6
↑
0 1 1/3 0 2/3 6
→ 0 0 −1 1 −1 −6
1 0 −1/3 0 1/3 2
0 0 4/3 0 5/3 16
↑
NB
2
4
1
NF
1 5
2 3
= (2, 6, 0, −6, 0) 6= , z = −16 < z
min
.
−2x
1
+ x
2
= 2 x
3
= 0
x
1
+ x
2
= 8 x
5
= 0
00
1
◦
. k = 2.
2
◦
. min
³
4/3
|−1|
,
5/3
|−1|
´
= 4/3 ⇒ l = 2, s = 3.
3
◦
. 4
◦
.
0 1 1/3 0 2/3 6
→ 0 0 1 −1 1 6
1 0 −1/3 0 1/3 2
0 0 4/3 0 5/3 16
↑
0 1 0 1/3 1/3 4
0 0 1 −1 1 6
1 0 0 −1/3 2/3 4
0 0 0 4/3 1/3 8
NB
2
3
1
NF
5
4
= (4, 4, 6, 0, 0) = , z
min
= −8.
C
2
←
→
C
3
C
3
1
0
2
0
C
∗
C
2
k
b
0
k
= 0
0
1
◦
. l = 2 s = 3.
2
◦
. min(∞, ∞, 6/1). ⇒ k = 3.
3
◦
. 4
◦
.
0 1 −1/3 2/3 0 2
1 0 −2/3 1/3 0 0
→ 0 0 1 −1 1 6
0 0 −1/3 5/3 0 6
↑
0 1 0 1/3 1/3 4
1 0 0 −1/3 2/3 4
0 0 1 −1 1 6
0 0 0 4/3 1/3 8
NB
2
1
3
NF
4
5
= (4, 4, 6, 0, 0) = , z = −8 = z
min
.
1/4x
1
− 8x
2
− x
3
+ 9x
4
≤ 0;
1/2x
2
− 12x
2
− 1/2x
3
+ 3x
4
≤ 0;
x
3
≤ 1;
−3/4x
1
+ 20x
2
− 1/2x
3
+ 6x
4
= z → min .
5
6
6
1
1
2
2
3
3
4
4
5
- - - - -- -
C
0
C
1
C
2
C
3
C
4
C
5
¾
-
C
6
C
∗
- -
1
0
2
0
k s
A
(k, s)
C
0
C
0
x
5
x
6
(k, s)
1
0
(k, s) = (3, 3) 2
0
(k, s) = (2, 1)
C
6
C
∗
C
∗
(1, 0, 1, 0, 3/4, 0, 0), z
min
= −5/4.
x
1
x
2
≥ 0
2x
1
+ x
2
≥ 7;
x
1
+ x
2
≥ 4;
x
1
+ 3x
2
≥ 9;
−2x
1
− 3x
2
= z → min .
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
0 0 0 0 0 1 1 1 0