Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
A
1 0 2/3 −1/3 0 0 30
0 1 1/3 1/3 0 0 20
0 0 2/3 −1/3 1 0 10
0 0 1/3 1/3 0 1 10
0 0 7/3 1/3 0 0 120
NB
(1) 1
(2) 2
(3) 5
(4) 6
NF
(1) 3
(2) 4
1
◦
. x
1
= 30, x
2
= 20 z
min
= −120.
(0, 0) (0, 5) R = (30, 20).
−∞
b ≥ 0 m
+1
x
B
≥ 0
≤
+ =
= −
+1
≥
− =
= −
−1
+ −
z
x
B
−1
x
1
, x
2
≥ 0
x
1
+ x
2
≤ 6;
−2x
1
+ 3x
2
≤ 3;
2x
1
+ 3x
2
≤ 21;
−2x
1
− 5x
2
= z → min .
A
1 1 0 0 1 6
→ −2 3 1 0 0 3
2 3 0 1 0 21
−2 −5 0 0 0 0
↑
NB
5
3
4
NF
1
2
= (0, 0, 3, 21, 6) = , 0 = z.
1
◦
. s = 2, l = 2
2
◦
. min(6, 1, 7) = 1, k = 2
3
◦
.
A
1 1 0 0 1 6
→ −2/3 1 1/3 0 0 1
2 3 0 1 0 21
−2 −5 0 0 0 0
↑
4
◦
.
A
→ 5
/
3 0
−
1
/
3 0 1 5
−2/3 1 1/3 0 0 1
4 0 −1 1 0 18
−16/3 0 5 /3 0 0 5
↑
NB
5
2
4
NF
1
3
= (0, 1, 0, 18, 5) = ; −5 = z.
1
◦
. s = 1, l = 1
2
◦
. min(3, ∞, 9/2) = 3, k = 1
3
◦
.
A
→ 1 0 −1/5 0 3/5 3
−2/3 1 1/3 0 0 1
4 0 −1 1 0 18
−16/3 0 5/3 0 0 5
↑
4
◦
.
A
1 0 −1/5 0 3/5 3
0 1 1 /5 0 2/5 3
0 0 −1/5 1 −12/5 6
0 0 3 /5 0 16/5 21
NB
1
2
4
NF
5
3
= (3, 3, 0, 6, 0) = ; −21 = min z.
1
◦
. a(m + 1, N F (l)), l = 1, 2
= (3, 3, 0, 6); −21 = min z.
Ox
1
x
2
(0, 0) → (0, 1) → (3, 3).
−1
−1
−1
2
◦
x
s
x
s
i −1
a
0
is
= a(i, s) b
0
i
= a(i, n + 1)
max(x
s
)
> 0 > 0 ∞
< 0 > 0 −∞
= 0 > 0 ∞ (∗)
> 0 < 0 ∞
< 0 < 0 b
0
i
/a
0
is
= 0 < 0 ∞
> 0 = 0 ∞
< 0 = 0 −∞
= 0 = 0 ∞
=
+1
x
1
, x
2
≥ 0
2x
1
≥ 3;
x
2
≥ 1;
x
1
+ x
2
= 6
−2x
1
+ 3x
2
≤ 3;
2x
1
+ 3x
2
≤ 21;
−2x
1
− 5x
2
= z → min .
A
2 0 −1 0 0 0 0 3
0 1 0 −1 0 0 0 1
1 1 0 0 0 0 1 6
→ −2 3 0 0 1 0 0 3
2 3 0 0 0 1 0 21
−2 −5 0 0 0 0 0 0
↑
NB
3
4
7
5
6
NF
1
2
= (0, 0, −3, −1, 3, 21, 6) 6= ; 0 = z.
1
◦
. s = 2, l = 2
2
◦
. min(∞, ∞, 6, 1, 7) = 1, k = 4
3
◦
.
A
2 0 −1 0 0 0 0 3
0 1 0 −1 0 0 0 1
1 1 0 0 0 0 1 6
→ −2/3 1 1 0 1/3 0 0 1
2 3 0 0 0 1 0 21
−2 −5 0 0 0 0 0 0
↑
4
◦
.
A
2 0 −1 0 0 0 0 3
2/3 0 0 −1 −1/3 0 0 0
→ 5/3 0 0 0 −1/3 0 1 5
−2/3 1 0 0 1/3 0 0 1
4 0 0 0 −1 1 0 18
−16/3 0 0 0 5/3 0 0 5
↑
NB
3
4
7
2
6
NF
1
5
= (0, 1, −3, 0, 0, 18, 5) 6= ; −5 = z.
1
◦
. s = 1, l = 1
2
◦
. min(∞, ∞, 3, ∞, 9/2) = 3, k = 3
3
◦
.
A
2 0 −1 0 0 0 0 3
2/3 0 0 −1 −1/3 0 0 0
→ 1 0 0 0 −1/5 0 3 /5 3
−2/3 1 0 0 1/3 0 0 1
4 0 0 0 −1 1 0 18
−16/3 0 0 0 5/3 0 0 5
↑
4
◦
.
A
0 0 −1 0 2/5 0 −6/5 −3
0 0 0 −1 −1/5 0 −2/5 −2
1 0 0 0 −1/5 0 3/5 3
0 1 0 0 1/5 0 2/5 3
0 0 0 0 −1/5 1 −12/5 6
0 0 0 0 3/5 0 16/5 21
NB
3
4
1
2
6
NF
7
5
= (3, 3, 3, 2, 0, 6, 0) = ; −21 = min z.
1
◦
. a(m+1, NF (l)), l = 1, 2 N F
7
x
7
= 0
x
7
= (3, 3, 3, 2, 0, 6), −21 = min z.
Ox
1
x
2
(0, 0) → (0, 1) → (3, 3),
+1
−1
x
7
x
1
+ x
2
≤ 6
2x
1
+ 3x
2
≤ 21
z = −2x
1
− 5x
2
2x
1
≥ 3;
x
2
≥ 1;
x
1
+ x
2
= 6;
−2x
1
+ 3x
2
≤ 3;
2x
1
+ 3x
2
≤ 21;
x
i
≥ 0 (i = 1, 2).
x
1
= 0 , x
2
= 0
2x
1
≥ 3 x
2
≥ 1 x
1
+ x
2
= 6
x
3
x
4
2x
1
− x
3
= 3;
x
2
− x
4
= 1,
x
3
≥ 0, x
4
≥ 0. x
1
= x
2
= 0
x
1
= x
2
= 0 x
3
= −3
x
4
= −1 x
3
≥ 0 x
4
≥ 0.
x
5
x
6
−2x
1
+ 3x
2
+ x
5
= 3;
2x
1
+ 3x
2
+ x
6
= 21,
x
1
= x
2
= 0 x
5
≥ 0, x
6
≥ 0.
≥
=
x
7
, x
8
x
9
x
3
2x
1
− x
3
= 3 x
3
− x
7
2x
1
≥ 3
2x
1
− x
3
+ x
7
= 3 x
3
≥ 0 x
7
≥ 0
x
4
x
2
− x
4
= 1 x
4
− x
8
x
2
≥ 1
x
2
− x
4
+ x
8
= 1 x
4
≥ 0 x
8
≥ 0
x
1
+ x
2
= 6 x
1
+ x
2
+ x
9
= 6
x
9
≥ 0.
x
1
= x
2
= 0
x
7
−x
3
= 3, x
8
−x
4
= 1 x
9
= 6
x
3
, x
4
, x
5
x
6
x
7
, x
8
x
9
2x
1
−3x
3
+x
7
= 3;
x
2
−x
4
+x
8
= 1;
x
1
+ x
2
x
9
= 6;
−2x
1
+ 3x
2
+x
5
= 3;
2x
1
+ 3x
2
+x
6
= 21,
x
1
= x
2
= x
3
= x
4
= 0, x
5
= 3, x
6
= 21, x
7
= 3, x
8
= 1
x
9
= 6.
x
7
, x
8
x
9
2x
1
−x
3
= 3;
x
2
−x
4
= 1;
x
1
+ x
2
= 6;
−2x
1
+ 3x
2
+x
5
= 3;
2x
1
+ 3x
2
+x
6
= 21;
x
i
≥ 0 ( i = 1, . . . , 6).
x
7
= 0
x
8
= 0 x
9
= 0.
x
7
= x
8
= x
9
= 0.
w = x
7
+ x
8
+ x
9
(3.8) x
i
≥ 0 ( i = 1, . . . , 9).
w
x
7
≥ 0, x
8
≥ 0,
x
9
≥ 0,
w 0
x
7
= x
8
= x
9
= 0
w 0
x
7
= x
8
= x
9
= 0, w = 0
np np = 2.
ng ≥ ng = 2.
ne = ne = 1.
nl ≤ nl = 2.
ns = ng + nl ns = 4.
na = ng + ne na = 3.
n = np + na + ns n = 9.
m = na + nl m = 5.