Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
B =
µ
3 0
9 1
¶
, B
−1
=
µ
1/3 0
−3 1
¶
B
−1
A =
µ
2/3 1 1/3 0
−3 0 −3 1
¶
, b
0
= B
−1
b =
µ
40
−90
¶
2/3 1 1/3 0 40
−3 0 −3 1 −90
2/3 0 4/3 0 160
(0, 40, 0, −90)
−160 = z < z
min
(0, 40)
z < z
min
, 6= .
(90, 0) (0, 40)
(1, 3) :
A
1 3 0 1/3 90
→ 0 −3 1 −2/3 −60
0 2 0 2/3 180
↑
NB
1
3
NF
2
4
1
◦
. k = 2. k = 2,
2
◦
. min
l=1,2; j=NF (l)
³
2
|−3|
,
2/3
|−2/3|
´
= 2/3; l = 1; s = 2.
s = 2,
3
◦
. 4
◦
.
A
1 3 0 1/3 90
0 1 −1/3 2/9 20
0 2 0 2/3 180
A
1 0 1 −1/3 30
0 1 −1/3 2/9 20
0 0 2/3 2/9 140
NB
1
2
NF
3
4
1
◦
. = (30, 20, 0, 0) = , −140 = z
min
.
5x
1
+ 3x
2
≤ 150.
A
b
NB NF
c
−z
(A, b, c, −z)
NB
A
c
b
−z
NF
(−z, c), b.
x
5
NB
1
2
(5)
140 0 0 2/3 2/9 0
30 1 0 1 −1/3 0
20 0 1 −1/3 2/9 0
150 5 3 0 0 1
NF
3
4
NB 5
x
1
x
2
5, 3.
NB
1
2
→ 5
140 0 0 2/3 2/9 0
30 1 0 1 −1/3 0
20 0 1 −1/3 2/9 0
−60 0 0 −4 1 1
↑
NF
3
4
= (30, 20, 0, 0, −60) 6= , −140 = z.
1
◦
. k = 3.
2
◦
. min
³
2/3
|−4|
´
= 1/6; l = 1, s = NF (l) = 3.
3
◦
.
140 0 0 2/3 2/9 0
30 1 0 1 −1/3 0
20 0 1 −1/3 2/9 0
→ 15 0 0 1 −1/4 −1/4
↑
4
◦
. N B(k)
←
→
NF (l)
NB
1
2
3
130 0 0 0 7/18 1/6
15 1 0 0 −1/12 1/4
25 0 1 0 5/36 −1/12
15 0 0 1 −1/4 −1/4
NF
5
4
= (15, 25, 15, 0, 0) = , −130 = z
min
.
Ox
1
x
2
(30, 20) z < z
min
(15, 25).
(15, 25, 15)
(2, 4)
NB
2
4
(5)
160 2/3 0 4/3 0 0
40 2/3 1 1/3 0 0
−90 −3 0 −3 1 0
150 5 3 0 0 1
NF
1
3
x
2
x
4
,
k
k = 1,
x
2
, NB(k) = NB(1) = 2,
NB
2
→ 4
5
160 2/3 0 4/3 0 0
40 2/3 1 1/3 0 0
−90 −3 0 −3 1 0
30 3 0 −1 0 1
↑
NF
1
3
k = 2, x
4
,
NB(k) = NB(2) = 4.
0
= (0, 40, 0, −90, 30) 6= , −160 = z < z
min
.
1
◦
. k = 2
2
◦
. k
NF 1
3
min
j=1,3
Ã
c
0
j
| a
0
kj
|
!
= min
µ
2/3
| −3 |
,
4/3
| −3 |
¶
= min
µ
2
9
,
4
9
¶
=
2
9
.
l = 1 j = NB(l) = s = 1.
1
◦
2
◦
−3
3
◦
.
160 2/3 0 4/3 0 0
40 2/3 1 1/3 0 0
→ 30 1 0 1 −1/3 0
30 3 0 −1 0 1
↑
4
◦
. N B(k)
←
→
NF (l) :
NB
2
1
→ 5
140 0 0 2/3 2/9 0
20 0 1 −1/3 2/9 0
30 1 0 1 −1/3 0
−60 0 0 −4 1 1
↑
NF
4
3
= (30, 20, 0, 0, −60) 6= , −140 = z < z
min
.
1
◦
. k = 3.
2
◦
. l = 2, j = NF (l) = 3, s = 3.
3
◦
.
140 0 0 2/3 2/9 0
20 0 1 −1/3 2/9 0
30 1 0 1 −1/3 0
→ 15 0 0 1 −1/4 −1/4
↑
4
◦
. N B(k)
←
→
NF (l) :
NB
2
1
3
130 0 0 0 7/18 1/6
25 0 1 0 5/36 −1/12
15 1 0 0 −1/12 1/4
15 0 0 1 −1/4 −1/4
NF
4
5
= (15, 25, 15, 0, 0) = , −130 = z
min
.
1
◦
.
= (15, 25, 15, 0, 0), z
min
= −130.
(0, 40) → (30, 20) → (15, 25).
x
1
, x
2
≥ 0
2x
1
≥ 3;
x
2
≥ 1;
−2x
1
+ 3x
2
≤ 3;
2x
1
+ 3x
2
≤ 21;
−2x
1
− 5x
2
= z → min
x
1
+ x
2
≤ 6.
NB
3
4
→ 5
6
0 −2 −5 0 0 0 0
3 2 0 −1 0 0 0
1 0 1 0 −1 0 0
3 −2 3 0 0 1 0
21 2 3 0 0 0 1
↑
NF
1
2
= (0, 0, −3, −1, 3, 21) 6= , 0 = z.
1
◦
. s = 2, l = 2.
2
◦
. min(∞, ∞, 3/3, 21/3) = 1, k = 3.
3
◦
.
0 −2 −5 0 0 0 0
3 2 0 −1 0 0 0
1 0 1 0 −1 0 0
1 −2/3 1 0 0 1/3 0
21 2 3 0 0 0 1
4
◦
. N B(k)
←
→
NF (l) :
NB
3
4
2
→ 6
5 −16/3 0 0 0 5/3 0
3 2 0 −1 0 0 0
0 2/3 0 0 −1 −1/3 0
1 −2/3 1 0 0 1/3 0
18 4 0 0 0 −1 1
↑
NF
1
5
= (0, 1, −3, 0, 0, 18) 6= , −5 = z.
1
◦
. s = 1, l = 1.
2
◦
. min(∞, ∞, ∞, 18/4) = 9/2, k = 4.
3
◦
.
5 −16/3 0 0 0 5/3 0
3 2 0 −1 0 0 0
0 2/3 0 0 −1 −1/3 0
1 −2/3 1 0 0 1/3 0
→ 9/2 1 0 0 0 −1/4 1/4
↑
4
◦
. N B(k)
←
→
NF (l) :
NB
3
4
2
1
29 0 0 0 0 1/3 4/3
−6 0 0 −1 0 1/2 −1/2
−3 0 0 0 −1 −1/6 −1/6
4 0 1 0 0 1/6 1/6
9/2 1 0 0 0 −1/4 1/4
NF
6
5
= (9/2, 4, 6, 3, 0, 0) = , −29 = z
min
.
−1
NB
3
4
2
1
(7)
29 0 0 0 0 1 /3 4/3 0
6 0 0 1 0 −1/2 1/2 0
3 0 0 0 1 1 /6 1/6 0
4 0 1 0 0 1 /6 1/6 0
9/2 1 0 0 0 −1/4 1/4 0
6 1 1 0 0 0 0 1
NF
6
5
(3, 4, 2, 1),
1 2
NB
3
4
2
1
→ 7
29 0 0 0 0 1/3 4/3 0
6 0 0 1 0 −1/2 1/2 0
3 0 0 0 1 1/6 1/6 0
4 0 1 0 0 1/6 1/6 0
9/2 1 0 0 0 −1/4 1/4 0
−5/2 0 0 0 0 1/12 −5/12 1
↑
NF
6
5
= (9/2, 4, 6, 3, 0, 0, −5/2) 6= , −29 = z.
1
◦
. k = 5. x
7
, NB(5) = 7,
x
7
= −5/2 < 0.
2
◦
. s = 6, l = 1,
min
l,j=NF (l):a
0
kj
<0
Ã
c
0
j
| a
0
kj
|
!
= min
j=6
µ
4/3
| −5/12 |
¶
=
16
5
.
3
◦
.
29 0 0 0 0 1 /3 4/3 0
6 0 0 1 0 −1/2 1/2 0
3 0 0 0 1 1 /6 1/6 0
4 0 1 0 0 1 /6 1/6 0
9/2 1 0 0 0 −1/4 1/4 0
→ 6 0 0 0 0 −1/5 1 −12/5
↑
4
◦
. N B(k)
←
→
NF (l) :
NB
3
4
2
1
6
21 0 0 0 0 3/5 0 16/5
3 0 0 1 0 −2/5 0 6/5
2 0 0 0 1 1/5 0 2/5
3 0 1 0 0 1/5 0 2/5
3 1 0 0 0 −1/5 0 3/5
6 0 0 0 0 −1/5 1 −12/5
NF
7
5
= (3, 3, 3, 2, 0, 6, 0) = , −21 = z
min
.
=
x
1
+ x
2
= 6.
x
7
w = x
7
0 0 1 0 −1/2 1/2 0 6
0 0 0 1 1/6 1/6 0 3
0 1 0 0 1/6 1/6 0 4
1 0 0 0 −1/4 1/4 0 9/2
1 1 0 0 0 0 1 6
0 0 0 0 1/3 4/3 0 29
0 0 0 0 0 0 1 0
NB
3
4
(2)
(1)
(7)
NF
5
6
x
2
, x
1
x
7
x
2
, x
1
x
7
0 0 1 0 −1/2 1/2 0 6
0 0 0 1 1/6 1/6 0 3
0 1 0 0 1/6 1/6 0 4
1 0 0 0 −1/4 1/4 0 9/2
→ 0 0 0 0 1/12 −5/12 1 −5/2
0 0 0 0 1/3 4/3 0 29
0 0 0 0 −1/12 5/12 0 5/2
↑
NB
3
4
2
1
7
NF
1 5
2 6
= (9/2, 4, 6, 3, 0, 0, −5/2) 6= , z = −29, w = −5/2.
w
−1/12
1
◦
. l = 1, s = 5.
2
◦
. min
³
∞,
3
1
/
6
,
4
1
/
6
, ∞, −∞
´
.
−∞
k = 5
x
5
x
5
−1/12
−5/2
w = 0 k = 5
3
◦
.
0 0 1 0 −1/2 1/2 0 6
0 0 0 1 1/6 1/6 0 3
0 1 0 0 1/6 1/6 0 4
1 0 0 0 −1/4 1/4 0 9/2
→ 0 0 0 0 1 −5 12 −30
0 0 0 0 1/3 4/3 0 29
0 0 0 0 −1/12 5/12 0 5/2
↑
4
◦
.
0 0 1 0 0 −2 6 −9
0 0 0 1 0 1 −2 8
0 1 0 0 0 1 −2 9
1 0 0 0 0 −1 3 −3
→ 0 0 0 0 1 −5 12 −30
0 0 0 0 0 3 −4 39
0 0 0 0 0 0 1 0
↑
NB
3
4
2
1
5
NF
1 7
2 6
= (−3, 9, −9, 8, −30, 0, 0) 6= , z = −39, w = 0 .
NF (1) = 7
(0, 0, 0, 0, 0, 3) (−9, 8, 9,
−3, −30)
z
1
◦
. k = 5.
2
◦
. s = 6.
3
◦
.