Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
0 0 1 0 0 −2 −9
0 0 0 1 0 1 8
0 1 0 0 0 1 9
1 0 0 0 0 −1 −3
→ 0 0 0 0 −1/5 1 6
0 0 0 0 0 3 39
↑
4
◦
.
0 0 1 0 −2/5 0 3
0 0 0 1 1/5 0 2
0 1 0 0 1/5 0 3
1 0 0 0 −1/5 0 3
0 0 0 0 −1/5 1 6
0 0 0 0 3/5 0 21
NB
3
4
2
1
6
NF
(7)
5
= (3, 3, 3, 2, 0, 6) = , z = −21.
1
◦
.
z
min
= −21
Ox
1
x
2
x
1
+x
2
= 6 (9/2, 4)
(−3, 9)
2x
1
+ 3x
2
= 21 x
1
+ x
2
= 6
(3, 3)
z
=
+1
+1
−1
z < z
min
.
z < z
min
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≥ 6;
2x
1
+ 6x
2
≥ 9;
2x
1
+ 2x
2
≤ 7;
x
1
+ 4x
2
= z → min .
x
1
x
2
x
3
x
4
x
5
b
0
2 3 −1 0 0 6
→ 2 6 0 −1 0 9
2 2 0 0 1 7
1 4 0 0 0 0
↑
NB
1 3
2 4
3 5
NF
1 1
2 2
= (0, 0, −6, −9, 7) 6= , 0 = z.
1
◦
. NB(i) b
0
a
0
[i, NB(i)] · b
0
(i) < 0. k
k = 2.
2
◦
. NF (i)
k a
0
[k, N B(k)] = −1,
a
0
[k, N B(k)] = +1.
min
j
Ã
c
0
j
| a
0
kj
|
!
.
min
µ
1
| 2 |
,
4
| 6 |
¶
=
1
2
.
i = l s = NF (l)
l = 1, s = 1.
3
◦
. k a
0
ks
,
a
0
ks
= 2,
2 3 −1 0 0 6
→ 1 3 0 −1/2 0 9/2
2 2 0 0 1 7
1 4 0 0 0 0
↑
4
◦
. k a
0
is
i 6= k NB(k)
←
→
NF (l),
0 −3 −1 1 0 −3
1 3 0 −1/2 0 9/2
→ 0 −4 0 1 1 −2
0 1 0 1/2 0 −9/2
↑
NB
1 3
2 1
3 5
NF
1 4
2 2
= (9/2, 0, 3, 0, −2) 6= , 9/2 = z.
1
◦
. a
0
[3, NB(3)] · b
0
(3) < 0, ⇒ k = 3.
2
◦
. a
0
[3, NB(3)] = +1; −4 ⇒ l = 2
s = 2.
3
◦
.
0 −3 −1 1 0 −3
1 3 0 −1/2 0 9/2
→ 0 1 0 −1/4 −1/4 1/2
0 1 0 1/2 0 −9/2
↑
4
◦
.
0 0 −1 1/4 −3/4 − 3/2
1 0 0 1/4 3/4 3
0 1 0 −1/4 −1/4 1/2
0 0 0 3/4 1/4 −5
NB
1 3
2 1
3 2
NF
1 4
2 5
= (3, 1/2, 3/2, 0, 0) = , 5 = z = z
min
.
1
◦
. a
0
[i, NB(i)] · b
0
(i) ≥ 0, ⇒
≥ =
6=
=
x
6
w = x
6
, =
≤ ≥
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≥ 6;
2x
1
+ 6x
2
≥ 9;
x
1
+ x
2
≤ 4;
2x
1
+ 2x
2
= 7;
x
1
+ 2x
2
= z → min .
2 3 −1 0 0 0 0 6
→ 2 6 0 −1 0 0 0 9
1 1 0 0 1 0 0 4
2 2 0 0 0 1 0 7
2 2 0 0 0 0 −1 7
1 2 0 0 0 0 0 0
↑
NB
1 3
2 4
3 5
4 6
5 7
NF
1 1
2 2
= (0, 0, −6, −9, 4, 7, −7) 6= , 0 = z.
1
◦
. a
0
[1, NB(1)] · b
0
(1) = −6 < 0;
a
0
[2, NB(2)] · b
0
(2) = −9 < 0;
a
0
[5, NB(5)] · b
0
(5) = −7 < 0, ⇒ k = 2.
2
◦
. a
0
[2, NB(2)] = −1.
a
0
[2, NF (1)] = 2, a
0
[2, NF (2)] = 6
min
µ
1
| 2 |
,
2
| 6 |
¶
=
1
3
, ⇒ l = 2, s = 2.
3
◦
.
2 3 −1 0 0 0 0 6
→ 1/3 1 0 −1/6 0 0 0 3/2
1 1 0 0 1 0 0 4
2 2 0 0 0 1 0 7
2 2 0 0 0 0 −1 7
1 2 0 0 0 0 0 0
↑
4
◦
.
1 0 −1 1/2 0 0 0 3/2
1/3 1 0 −1/6 0 0 0 3/2
2/3 0 0 1/6 1 0 0 5/2
4/3 0 0 1/3 0 1 0 4
→ 4/3 0 0 1/3 0 0 −1 4
1/3 0 0 1/3 0 0 0 −3
↑
NB
1 3
2 2
3 5
4 6
5 7
NF
1 1
2 4
= (0, 3/2, −3/2, 0, 5/2, 4, −4) 6= , 3 = z.
1
◦
. a
0
[1, NB(1)] · b
0
(1) = −3/2 < 0;
a
0
[5, NB(5)] · b
0
(5) = −4 < 0, ⇒ k = 5.
2
◦
. a
0
[5, NB(5)] = −1 & a
0
[5, NF (1)] = 4/3 > 0 &
a
0
[5, NF (2)] = 1/3 > 0, ⇒
min
µ
1/3
| 4/3 |
,
1/3
| 1/3 |
¶
=
1
4
, ⇒ l = 1, s = 1.
3
◦
.
1 0 −1 1/2 0 0 0 3/2
1/3 1 0 −1/6 0 0 0 3/2
2/3 0 0 1/6 1 0 0 5/2
4/3 0 0 1/3 0 1 0 4
→ 1 0 0 1/4 0 0 −3/4 3
1/3 0 0 1/3 0 0 0 −3
↑
4
◦
.
0 0 −1 1/4 0 0 3/4 −3/2
0 1 0 −1/4 0 0 1 /4 1/2
0 0 0 0 1 0 1/2 1/2
0 0 0 0 0 1 1 0
1 0 0 1/4 0 0 − 3/4 3
0 0 0 1/4 0 0 1/4 −4
NB
1 3
2 2
3 5
4 6
5 1
NF
1 7
2 4
= (3, 1/2, 3/2, 0, 1/2, 0, 0) = , −4 = z
min
.
1
◦
. a
0
[i, NB(i)] · b
0
(i) ≥ 0, ⇒
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≥ 6;
2
x
1
+ 6
x
2
≥
9;
x
1
+ x
2
≤ 4;
2x
1
+ 2x
2
= 7;
x
1
+ 2x
2
= z → min .
=
x
6
w = x
6
2 3 −1 0 0 0 6
2 6 0 −1 0 0 9
1 1 0 0 1 0 4
2 2 0 0 0 1 7
1 2 0 0 0 0 0
0 0 0 0 0 1 0
w w
(x
3
, x
4
, x
5
, x
6
) x
6
w
2 3 −1 0 0 0 6
2 6 0 −1 0 0 9
1 1 0 0 1 0 4
→ 2 2 0 0 0 1 7
1 2 0 0 0 0 0
−2 −2 0 0 0 0 −7
↑
NB
3
4
5
6
NF
1 1
2 2
= (0, 0, −6, −9, 4, 7) 6= , 0 = z, 7 = w.
w
1
◦
. l = 1, s = 1.
2
◦
. min
¡
∞, ∞,
4
1
,
7
2
¢
= 7/2 ⇒ k = 4 .
3
◦
.
2 3 −1 0 0 0 6
2 6 0 −1 0 0 9
1 1 0 0 1 0 4
→ 1 1 0 0 0 1/2 7/2
1 2 0 0 0 0 0
−2 −2 0 0 0 0 −7
↑
4
◦
.
0 1 −1 0 0 −1 −1
→ 0 4 0 −1 0 −1 2
0 0 0 0 1 −1/2 1/2
1 1 0 0 0 1/2 7/2
0 1 0 0 0 −1/2 −7/2
0 0 0 0 0 1 0
↑
NB
3
4
5
1
NF
1 6
2 2
= (7/2, 0, 1, −2, 1/2, 0) 6= , 7/2 = z, 0 = w.
x
6
1
◦
. a
0
[2, NB(2)] · b
0
(2) = −2 < 0, ⇒ k = 2.
2
◦
. a
0
[2, NB(2)] = −1,
a
0
[2, NF (2)] = 4, ⇒
min
j
Ã
c
0
j
| a
0
kj
|
!
= min
µ
1
| 4 |
¶
=
1
4
, ⇒ l = 2 , s = 2.
3
◦
.
0 1 −1 0 0 −1
→ 0 1 0 −1/4 0 1/2
0 0 0 0 1 1/2
1 1 0 0 0 7/2
0 1 0 0 0 −7/2
↑
4
◦
.
0 0 −1 1/4 0 −3/2
0 1 0 −1/4 0 1/2
0 0 0 0 1 1/2
1 0 0 1/4 0 3
0 0 0 1/4 0 −4
NB
3
2
5
1
NF
1 6
2 4
= (3, 1/2, 3/2, 0, 1/2) = , 4 = z.
1
◦
. a
0
[i, NB(i)] · b
0
(i) ≥ 0, ⇒
z
min
= 4, ⇒
1
◦
(n−m)
2
◦
x
s
,
m a
0
s
m
b
0
(n + m)
1
◦
m
b
0
k 2
◦
x
r
, r = NB(k),
(n − m) k
(n − m)
(n −m)
2n − m
1
◦
2
◦
3
◦
4
◦
1
◦
2
◦
π
B
−1
m×m,
a
0
s
π
1
◦
2
◦
Ax = b, x ∈ IR
n
, b ∈ IR
m
, m < n
rank(A) = m, x ≥ 0, c
T
x = z → min .
m x
x
B
, n −m
x
F
.
x = (x
B
, x
F
).
m
x x
B
,
x
B
n A
m
IR
m
.
x x
B
,
B. c
c
B
x
B
c
F
x
F
.