Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
A(1..m + 2, 1..n + 1), A(1..7, 1..10) (7 × 10)
NB(1..m), NB(1..5) 5
NF (1..n − m), N F (1..4) 4
A
A(1..m + 1, 1..np), A(1..6, 1..2)
A(1..m + 1, n + 1), A(1..6, 10)
A
2 0 −1 0 0 0 1 0 0 3
0 1 0 −1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 1 6
−2 3 0 0 1 0 0 0 0 3
2 3 0 0 0 1 0 0 0 21
−2 −5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0
NB
7
8
9
5
6
NF
1
2
3
4
= (0, 0, 0, 0, 3, 21, 3, 1, 6) = , 0 = z
min
, 0 = w.
x
1
x
2
x
3
, x
4
, x
5
x
6
x
7
, x
8
x
9
≥ = A
w
(−w)
(−z). −z
w
w = x
7
+ x
8
+ x
9
(x
7
, x
8
, x
9
)
na
na = 3
A
→ 2 0 −1 0 0 0 1 0 0 3
0 1 0 −1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 1 6
−2 3 0 0 1 0 0 0 0 3
2 3 0 0 0 1 0 0 0 21
−2 −5 0 0 0 0 0 0 0 0
−3 −2 1 1 0 0 0 0 0 −10
↑
10 = w.
≥ = ≤
(np + ng + 1) n = np + na + ns, 5 9.
w → min .
1
◦
. s = 1, l = 1
2
◦
. min(3/2, ∞, 6, ∞, 21/2) = 3/2, k = 1
3
◦
.
A
→ 1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 0 −1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 1 6
−2 3 0 0 1 0 0 0 0 3
2 3 0 0 0 1 0 0 0 21
−2 −5 0 0 0 0 0 0 0 0
−3 −2 1 1 0 0 0 0 0 −10
↑
4
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
→ 0 1 0 −1 0 0 0 1 0 1
0 1 1/2 0 0 0 −1/2 0 1 9/2
0 3 −1 0 1 0 1 0 0 6
0 3 1 0 0 1 −1 0 0 18
0 −5 −1 0 0 0 1 0 0 3
0 −2 −1/2 1 0 0 3/2 0 0 −11/2
↑
NB
1
8
9
5
6
NF
7
2
3
4
= (3/2, 0, 0, 0, 6, 18, 1, 9/2) = ; −3 = z; 11/2 = w.
1
◦
. s = 2, l = 2
2
◦
. min(∞, 1, 9/2, 2, 6) = 1, k = 2
3
◦
.
1
4
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 0 −1 0 0 0 1 0 1
0 0 1/2 1 0 0 −1/2 −1 1 7/2
→ 0 0 −1 3 1 0 1 −3 0 3
0 0 1 3 0 1 −1 −3 0 15
0 0 −1 −5 0 0 1 5 0 8
0 0 −1/2 −1 0 0 3/2 2 0 −7/2
↑
NB
1
2
9
5
6
NF
7
8
3
4
= (3/2, 1, 0, 0, 3, 15, 0, 0, 7/2) = ; −8 = z; 7/2 = w.
1
◦
. s = 4, l = 4
2
◦
. min(∞, ∞, 7/2, 1, 5) = 1, k = 4
3
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 0 −1 0 0 0 1 0 1
0 0 1/2 1 0 0 −1/2 −1 1 7/2
→ 0 0 −1/3 1 1/3 0 1/3 −1 0 1
0 0 1 3 0 1 −1 −3 0 15
0 0 −1 −5 0 0 1 5 0 8
0 0 −1/2 −1 0 0 3/2 2 0 −7/2
↑
4
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 −1/3 0 1/3 0 1/3 0 0 2
→ 0 0 5/6 0 −1/3 0 −5/6 0 1 5/2
0 0 −1/3 1 1/3 0 1/3 −1 0 1
0 0 2 0 −1 1 −2 0 0 12
0 0 −8/3 0 5/3 0 8/3 0 0 13
0 0 −5/6 0 1/3 0 11/6 1 0 −5/2
↑
NB
1
2
9
4
6
NF
7
8
3
5
= (3/2, 2, 0, 1, 0, 12, 0, 0, 5/2) = ; −13 = z; 5/2 = w.
1
◦
. s = 3, l = 3
2
◦
. min(∞, ∞, 3, ∞, 6) = 3, k = 3
3
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 −1/3 0 1/3 0 1/3 0 0 2
→ 0 0 1 0 −2/5 0 −1 0 6/5 3
0 0 −1/3 1 1/3 0 1/3 −1 0 1
0 0 2 0 −1 1 −2 0 0 12
0 0 −8/3 0 5/3 0 8/3 0 0 13
0 0 −5/6 0 1/3 0 11/6 1 0 −5/2
↑
4
◦
.
A
1 0 0 0 −1/5 0 0 0 3/5 3
0 1 0 0 1/5 0 0 0 2/5 3
0 0 1 0 −2/5 0 −1 0 6/5 3
0 0 0 1 1/5 0 0 −1 2/5 2
0 0 0 0 −1/5 1 0 0 −12/5 6
0 0 0 0 3/5 0 0 0 16/5 21
0 0 0 0 0 0 1 1 1 0
NB
1
2
3
4
6
NF
7
8
9
5
= (3, 3, 3, 2, 0, 6, 0, 0, 0) = ; −21 = min(z); 0 = min(w).
w
A
A
z w
Ox
1
x
2
(0, 0) → (3/2, 0) → (3/2, 1) → (3/2, 2) → (3, 3).
1
◦
. s = 3, l = 3
2
◦
. min(∞, ∞, 7, ∞, 15) = 7, k = 3
3
◦
.
A
1 0 −1/2 0 0 0 1/2 0 0 3/2
0 1 0 −1 0 0 0 1 0 1
→ 0 0 1 2 0 0 −1 −2 2 7
0 0 −1 3 1 0 1 −3 0 3
0 0 1 3 0 1 −1 −3 0 15
0 0 −1 −5 0 0 1 5 0 8
0 0 −1/2 −1 0 0 3/2 2 0 −7/2
↑
4
◦
.
A
1 0 0 1 0 0 0 −1 1 5
0 1 0 −1 0 0 0 1 0 1
0 0 1 2 0 0 −1 −2 2 7
0 0 0 5 1 0 0 −5 2 10
0 0 0 1 0 1 0 −1 −2 8
0 0 0 −3 0 0 0 3 2 15
0 0 0 0 0 0 1 1 1 0
NB
1
2
3
5
6
NF
7
8
9
4
= (5, 1, 7, 0, 10, 8, 0, 0, 0) = ; −15 = z; 0 = min(w).
0 w
w
w 0
w 6= 0
z
−3 A
A
(np + na + 1) n,
7 9 NF
ns
ns = 3.
1
◦
. s = 4, l = 4
2
◦
. min(5, ∞, 7/2, 2, 8) = 2, k = 4
3
◦
. 4
◦
.
A
1 0 1 1 0 0 5
0 1 0 −1 0 0 1
0 0 1 2 0 0 7
→ 0 0 0 1 1/5 0 2
0 0 0 1 0 1 8
0 0 0 −3 0 0 15
↑
A
1 0 1 0 −1/5 0 3
0 1 0 0 1/5 0 3
0 0 1 0 −2/5 0 3
0 0 0 1 1/5 0 2
0 0 0 0 −1/5 1 6
0 0 0 0 3/5 0 21
NB
1
2
3
4
6
NF
5
= (3, 3, 3, 2, 0, 6) = ; −21 = min(z).
Ox
1
x
2
(0, 0) → (3/2, 0) → (3/2, 1) → (5, 1) → (3, 3)
z = z
min
z > z
min
z < z
min
z > z
min
.
z < z
min
,
z z
min
,
z
min
z < z
min
z,
z
min
(x
B
)
+1
−1
−1
·
I A
0
O
T
c
0T
¸·
x
B
x
F
¸
=
·
b
0
z − z
0
¸
, c
0
≥ 0,
= {x
B
= b
0
, x
F
= 0}.
b
0
.
1
◦
. b
0
.
z
min
= x
0
= (x
B
= b
0
, x
F
= 0).
k, b
0
k
b
0
. x
r
, r = N B(k),
x
B
x
r
= b
0
k
< 0.
x
F
x
r
x
s
.
k
a
0
ks
< 0.
b
0
.
j
c
+
j
= c
0
j
− c
0
s
a
00
kj
.
a
00
kj
j k
a
00
kj
= a
0
kj
/a
0
ks
.
c
+
j
≥ 0 c
0
j
≥ 0 c
0
s
≥ 0.
j
c
+
j
≥ 0, a
00
kj
> 0. c
+
j
≥ 0
c
0
j
| a
0
kj
|
≥
c
0
s
| a
0
ks
|
,
s, x
s
,
c
0
s
| a
0
ks
|
= min
j: a
0
kj
<0
c
0
j
| a
0
kj
|
.
2
◦
. k
a
0
kj
.
a
0
ks
,
s,
a
0
ks
3
◦
. k a
0
ks
4
◦
. k a
0
is
i (i 6= k).
3
◦
4
◦
1
◦
2
◦
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≤ 120;
3x
1
+ 9x
2
≤ 270;
−2x
1
− 4x
2
= z → min
2 3 1 0 120
3 9 0 1 270
−2 −4 0 0 0
A =
µ
2 3 1 0
3 9 0 1
¶
, b =
µ
120
270
¶
c
T
=
¡
−2 −4 0 0
¢
, Ax = b
c
T
x = z.
= (0, 0, 120, 270) =
z = 0, (0, 0) Ox
1
x
2
C
2
4
= 6
B =
µ
2 3
3 9
¶
, B
−1
=
µ
1 −1/3
−1/3 2/9
¶
B
−1
A =
µ
1 0 1 −1/3
0 1 −1/3 2/9
¶
, b
0
= B
−1
b =
µ
30
20
¶
1 0 1 −1/3 30
0 1 −1/3 2/9 20
0 0 2 /3 2/9 140
(30, 20, 0, 0)
−140 = z
min
(30, 20)
B =
µ
2 1
3 0
¶
, B
−1
=
µ
0 1/3
1 −2/3
¶
B
−1
A =
µ
1 3 0 1/3
0 −3 1 −2/3
¶
, b
0
= B
−1
b =
µ
90
−60
¶
1 3 0 1/3 90
0 −3 1 −2/3 −60
0 2 0 2/3 180
(90, 0, −60, 0) 6=
−180 = z < z
min
(90, 0)
B =
µ
2 0
3 1
¶
, B
−1
=
µ
1/2 0
−3/2 1
¶
B
−1
A =
µ
1 3/2 1/2 0
0 9/2 −3/2 1
¶
, b
0
= B
−1
b =
µ
60
90
¶
1 3/2 1 /2 0 60
0 9/2 −3/2 1 90
0 −1 1 0 120
(60, 0, 0, 90)
−120 = z > z
min
(60, 0)
B =
µ
3 1
9 0
¶
, B
−1
=
µ
0 1/9
1 −1/3
¶
B
−1
A =
µ
1/3 1 0 1/9
1 0 1 −1/3
¶
, b
0
= B
−1
b =
µ
30
30
¶
1/3 1 0 1/9 30
1 0 1 −1/3 30
−2/3 0 0 4/9 120
(0, 30, 30, 0)
−120 = z > z
min
(0, 30)