Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
·
B R
c
T
B
c
T
F
¸·
x
B
x
F
¸
=
·
b
z → min
¸
,
R
Ax = Bx
B
+ Rx
F
= b
x
F
.
B
−1
,
[I A
0
]
·
x
B
x
F
¸
= b
0
, A
0
= B
−1
R, b
0
= B
−1
b,
c
T
B
[c
T
B
c
T
B
A
0
]
·
x
B
x
F
¸
= c
T
B
b
0
,
[O
T
c
0T
]
·
x
B
x
F
¸
= z − z
0
→ min, c
0T
= c
T
F
− c
T
B
A
0
x
F
z = z
0
, z
0
= c
T
B
b
0
,
= [x
B
= b
0
, x
F
= 0].
π
T
= [π
1
, π
2
, . . . , π
m
]
[(π
T
B + c
T
B
) (π
T
R + c
T
F
)]
·
x
B
x
F
¸
= π
T
b + z → min,
π
T
B + c
T
B
= 0
T
.
π, π
T
= −c
T
B
B
−1
c
0T
= π
T
R+c
T
F
, z
0
= −π
T
b.
π
T
B + c
T
B
π
T
R + c
T
F
,
x
B
x
F
i x
i
i A
Ax = b, π
x
i
c
T
x = z
π.
m
A j
1
, j
2
, . . . j
m
,
B.
x
B
B π
T
,
c
T
B
= (c
j
1
, c
j
2
, . . . , c
j
m
),
c
T
x = z
π
T
B = −c
T
B
,
π.
rankB = m,
c
0T
= π
T
R + c
T
F
x
F
A
c
T
B
, c
T
F
x
B
, x
F
c
T
x = z.
a
j
A q e
q
,
c
j
a
j
B π
q
= 0;
a
j
R c
0
q
= π
q
.
e
q
π
q
, π
q
= 0,
x
B
.
1
◦
2
◦
1
◦
2
◦
1
◦
2
◦
1
m×m D
k
,
1 k 0.
k A
a
ks
, D
−1
ks
A,
D
ks
D
k
, k
a
ks
s A
x
s
x
B
x
r
,
r = N B(k), x
F
.
m × m
T
c
k
k
1 k
s A, T
c
ks
.
(T
c
ks
)
−1
,
k
k
A (T
c
ks
)
−1
D
−1
ks
A.
A m ×m, k
s k = s
s = 1, 2, . . . , m. m
(T
c
mm
)
−1
D
−1
mm
. . . (T
c
22
)
−1
D
−1
22
(T
c
11
)
−1
D
−1
11
A = I,
A
−1
= (T
c
mm
)
−1
D
−1
mm
. . . (T
c
22
)
−1
D
−1
22
(T
c
11
)
−1
D
−1
11
I.
I
A
−1
.
A
−1
t
= (T
c
tt
)
−1
D
−1
tt
A
−1
t−1
; A
−1
0
= I, t = 1, 2, . . . , m,
t A
−1
m
= A
−1
.
n.
1
m × n A
A = [ G | I ], G I
m ×m
A,
B
−1
t
= (T
c
ks
)
−1
D
−1
ks
B
−1
t−1
, B
−1
0
= I, t = 1, 2, . . . , N,
t B
t
t; B
−1
t
t; B
−1
0
0
N
k s
A
t,
t,
A,
I k = 1, 2, . . . , m,
t
B
−1
t
.
B
−1
t−1
B
t
B
t−1
k k ∈ {1, 2, . . . , m},
s, s ∈ {1, 2, . . . , n}, A.
(T
c
ks
)
−1
D
−1
ks
B
−1
t−1
B
−1
β
ij
,
i, j = 1, 2, . . . , m,
B
−1
=
β
11
··· β
1m
··· ··· ···
β
m1
··· β
mm
.
t = 0 A,
I. t, t = 1, 2, . . . , N, B
−1
t−1
.
t, t = 1, 2, . . . , N, B
−1
t
.
B
−1
t−1
B
−1
t
(T
c
ks
)
−1
D
−1
ks
(1) D
−1
ks
j = 1, 2, . . . , m β
+
kj
= β
kj
/a
0
ks
.
(2) (T
c
ks
)
−1
i = 1, 2, . . . , m, i 6= k j = 1, 2, . . . , m
β
+
ij
= β
ij
− a
0
is
β
+
kj
.
+ B
−1
a
0
ks
k s A a
0
is
a
0
s
.
a
0
s
a
0
s
= B
−1
a
s
,
B
−1
= B
−1
t
.
A
0
= B
−1
R
π
T
= −c
T
B
B
−1
,
A, B,
c
T
B
x
B
.
+
(π
+
)
T
= −(c
+
B
)
T
(B
+
)
−1
.
j (π
+
)
T
(B
+
)
−1
π
+
j
(1)
= −
m
P
i=1
c
NB
+
(i)
β
+
ij
(2)
= −
m
P
i
=1
,
(
i
6
=
k
)
c
NB
+
(i)
β
+
ij
− c
NB
+
(k)
β
+
kj
=
(3)
= −
m
P
i=1,(i6=k)
c
NB
+
(i)
(β
ij
− a
0
is
β
+
kj
) − c
NB
+
(k)
β
+
kj
=
(4)
=
−
m
P
i=1
c
NB(i)
(
β
ij
−
a
0
is
β
+
kj
)
−
c
NB
+
(k)
β
+
kj
=
(5)
= −
m
P
i=1
c
NB
(
i)
β
ij
+
m
P
i=1
c
NB(i)
a
0
is
β
+
kj
− c
NB
+
(k)
β
+
kj
=
(6)
= π
j
− β
+
kj
(c
s
−
m
P
i=1
c
NB(i)
a
0
is
)
(7)
= π
i
− β
+
kj
c
0
s
.
i 6= k,
i = k
c
NB
+
(i)
c
NB(i)
k c
B
c
+
B
NB
+
(k) = s s
c
0
s
= c
s
−
m
X
i=1
c
NB(i)
a
0
is
.
s c
0T
= c
T
F
− c
T
B
A
0
,
+ c
F
.
(c
+
B
)
T
k c
+
k
c
s
, s = NB
+
(k), x
s
,
+ x
B
x
F
x
B
x
r
, r = NB(k), x
B
+
π
+
j
= π
j
− β
+
kj
c
0
s
j = 1, 2, . . . , m.
·
G I
c
T
O
T
¸
x =
·
b
z
¸
, b ≥ 0,
I m × m
x
B
, c
T
x
F
= z → min,
G
A = [ G | I ] Ax = b,
x
F
x = (x
F
, x
B
)
b
b ≥ 0
A, b, c.
t (t = 1, 2, . . . , N )
π, B
−1
, b
0
, z,
π = 0, B
−1
= I, b
0
= b, z = 0.
G c
c
0T
= π
T
G + c
T
; A a
0
s
= B
−1
a
s
,
a
s
s A.
1
◦
. c
0T
= π
T
G + c
T
. NF (i)
(c
0T
, π
T
)
l s = NF (l)
x
s
,
c
0
s
2
◦
. a
0
s
= B
−1
a
s
.
b
0
a
0
s
, k
b
0
a
0
ks
= min
i,a
0
is
>0
µ
b
0
i
a
0
is
¶
.
r = N B(k) x
r
,
a
0
s
a
0
ks
.
3
◦
.
NB(k)
←
→
NF (l).
b
+
k
= b
0
k
/a
0
ks
; b
+
i
= b
0
i
− a
0
is
b
+
k
(i 6= k).
z
+
= z − c
0
s
b
+
k
.
−z.
β
+
kj
= β
kj
/a
0
ks
; β
+
ij
= β
ij
− a
0
is
β
+
kj
(i 6= k).
π
+T
= π
T
− β
+
k
c
0
s
.
β
+
k
k
β
+
kj
, j = 1, 2, . . . , m.
+
z := z−c
0
s
b
k
.
x
1
, x
2
, x
3
≥ 0
x
1
+ 2x
2
+ 5x
3
≤ 45;
2x
1
+ 3x
2
+ 3x
3
≤ 60;
x
1
+ x
2
+ 2x
3
≤ 27;
−9x
1
− 10x
2
− 15x
3
= z → min .
A b
1 2 5 1 0 0 45
2 3 3 0 1 0 60
1 1 2 0 0 1 27
−9 −10 −15 0 0 0 0
NB
1 4
2 5
3 6
NF
1 1
2 2
3 3
= (0, 0, 0, 45, 60, 27) = , 0 = z.
1
◦
. c
0T
= π
T
G+c
T
; c
0T
= c
T
= (−9, −10, −15).
π
T
= (0, 0, 0),
c
0T
= c
T
.
(c
0T
, π
T
) = (−9, −10, −15, 0, 0, 0) ⇒ l = 3, s = 3, c
0
s
= −15.
2
◦
. a
0
s
= B
−1
a
s
; a
0
s
= a
s
= a
3
=
1 2 3
B
−1
= I, a
0
s
= a
s
.
min
µ
45
5
,
60
3
,
27
2
¶
=
45
5
= 9 ⇒ k = 1, a
0
ks
= 5.
3
◦
.
NB =
1 2 3
, NF =
1 2 3
.
b
0
=
1 2 3
9 33 9
.
−z = 135.
B
−1
=
1/5 0 0
−3/5 1 0
−2/5 0 1
.
π
T
=
3 0 0
=
0 0 0
−
1/5 0 0
·
−15
.
1
◦
.
c
0T
−6 −4 0
↑1 2 3
=
π
T
3 0 0
4 5 6
·
G
1 2 5
2 3 3
1 1 2
+
c
T
−9 −10 −15
l = 1, s = 1, c
0
s
= −6.
2
◦
. a
0
s
=
1/5
7/5
3/5
=
1/5 0 0
−3/5 1 0
−2/5 0 1
·
1
2
1
min
µ
9
1/5
,
33
7/5
,
9
3/5
¶
=
9
3/5
= 15 ⇒ k = 3, a
0
ks
= 3/5.
3
◦
. NB =
1 2 3
, NF =
1 2 3
.
b
0
=
1 2 3
6 12 15
.
−z = 225.
B
−1
=
1/3 0 −1/3
1/3 1 −7/3
−2/3 0 5/3
.
π
T
=
−1 0 10
=
3 0 0
−
−2/3 0 5/3
·
−6
.
1
◦
.
c
0T
0 −2 0
1 ↑2 3
=
π
T
−1 0 10
4 5 6
·
G
1 2 5
2 3 3
1 1 2
+
c
T
−9 −10 −15
l = 2, s = 2, c
0
s
= −2.
2
◦
. a
0
s
=
1/3
4/3
1/3
=
1/3 0 −1/3
1/3 1 −7/3
−2/3 0 5/3
·
2
3
1
min
µ
6
1/3
,
12
4/3
,
15
1/3
¶
=
12
4/3
= 9 ⇒ k = 2, a
0
ks
= 4/3.
3
◦
. NB =
1 2 3
, NF =
1 2 3
.
b
0
=
1 2 3
3 9 12
.
−z = 243.
B
−1
=
1/4 −1/4 1/4
1/4 3/4 −7/4
−3/4 −1/4 9/4
.
π
T
=
−1/2 3/2 13/2
=
−1 0 10
−
1/4 3/4 −7/4
·
−2
.
1
◦
.
c
0T
0 0 0
1 2 3
=
π
T
−1/2 3/2 13/2
↑4 5 6
·
G
1 2 5
2 3 3
1 1 2
+
c
T
−9 −10 −15
l = 3, s = 4, c
0
s
= −1/2.
2
◦
. a
0
s
=
1/4
1/4
−3/4
=
1/4 −1/4 1/4
1/4 3/4 −7/4
−3/4 −1/4 9/4
·
1
0
0
min
µ
3
1/4
,
9
1/4
, ∞
¶
=
3
1/4
= 12 ⇒ k = 1, a
0
ks
= 1/4.
∞
3
◦
. NB =
1 2 3
, NF =
1 2 3
.
b
0
=
1 2 3
12 6 21
.
−z = 249.
B
−1
=
1 −1 1
0 1 −2
0 −1 3
.
π
T
=
0 1 7
=
−1/2 3/2 13/2
−
1 −1 1
·
−1/2
.
1
◦
.
c
0T
0 0 2
1 2 3
=
π
T
0 1 7
4 5 6
·
G
1 2 5
2 3 3
1 1 2
+
c
T
−9 −10 −15
.
(c
0T
, π
T
), NF,
b
0
NB,
NF