Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
x
F
,
(z−z
0
) = c
0T
x
F
z
x
s
x
F
x
B
i
+ a
0
is
x
s
= b
0
i
, x
B
i
≥ 0, x
s
> 0, i = 1, m.
x
s
z x
B
i
x
B
i
a
0
is
> 0 a
0
is
< 0 x
B
i
x
B
i
a
0
is
= 0
x
B
i
≥ 0
a
0
is
> 0
x
B
i
≥ 0
x
s
i
x
s
x
B
i
, x
B
i
x
B
i
= 0, x
s
x
s
= b
0
i
/a
0
is
. m
x
s
x
s
= min
i=1,m
µ
b
0
i
a
0
is
¶
.
k
x
s
= min
i=1,m
µ
b
0
i
a
0
is
¶
=
b
0
k
a
0
ks
.
x
s
b
0
k
/a
0
ks
k x
k
x
s
x
k
C
m
n
x
s
x
k
b
0
≥ 0
·
I A
0
O c
0T
¸·
x
B
x
F
¸
=
·
b
0
z − z
0
¸
, x
B
≥ 0, x
F
≥ 0,
I (m × m); A
0
= {a
0
j
}
j = m+1, . . . , n, a
0
j
; c
0
x
F
; z
0
= c
T
B
b
0
x = (x
B
, x
F
),
x
B
= b
0
, x
F
= 0.
◦
x
F
x
s
z z
0
c
0T
x
s
c
0T
x
s
x
s
s
◦
m m
b
0
k
a
0
ks
= min
i: a
0
is
>0
µ
b
0
i
a
0
is
¶
.
k
a
0
ks
x
s
◦
k
a
0
ks
, x
s
1
◦
k
x
s
k
k s
s
k
x
s
x
k
1
◦
3
◦
4
◦
x
s
1
◦
2
◦
1
◦
2
◦
−2x
1
− 4x
2
= z
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≤ 120
3x
1
+ 9x
2
≤ 270
¾
.
x
3
, x
4
≥ 0 :
2x
1
+ 3x
2
+ x
3
= 120;
3x
1
+ 9x
2
+ x
4
= 270;
−2x
1
− 4x
2
= z.
2 3 1 0
3 9 0 1
−2 −4 0 0
x
1
x
2
x
3
x
4
=
120
270
z
.
x
B
= (x
3
, x
4
). x
F
= (x
3
, x
4
).
x = (x
1
, x
2
, x
3
, x
4
) = (0, 0, 0, 0).
z = z
0
= 0.
1
◦
4
◦
2 3 1 0 | 120
3 9 0 1 | 270
−2 −4 0 0 | z
.
1
◦
4
◦
1
◦
. x
s
= x
2
2
◦
. min(
120
3
,
270
9
) = min(40, 30) = 30
k = 2
3
◦
.
→
2 3 1 0 | 120
1/3 1 0 1/9 | 30
−2 −4 0 0 | z
↑
4
◦
.
1 0 1 −1/3 | 30
1/3 1 0 1/9 | 30
−2/3 0 0 4/9 | z + 120
.
x
B
= (x
2
, x
3
).
x
F
= (x
1
, x
4
).
x = (x
1
, x
2
, x
3
, x
4
) = (0, 30, 40, 0).
z + 120 = 0 z = z
0
= −120.
1
◦
. x
s
= x
1
2
◦
. min(
40
1
,
30
1/3
) = min(40, 90) = 40
k = 1
3
◦
.
→
1 0 1 −1/3 | 30
1/3 1 0 1/9 | 30
−2/3 0 0 4/9 | z + 120
.
↑
4
◦
.
1 0 1 −1/3 | 30
0 1 −1/3 2/9 | 20
0 0 2/3 2/9 | z + 140
.
x
B
= (x
1
, x
2
).
x
F
= (x
3
, x
4
).
x = (x
1
, x
2
, x
3
, x
4
) = (30, 20, 0, 0).
z + 140 = 0, z = z
0
= −140.
1
◦
.
n n = 4,
x
1
= 30, x
2
= 20 z = −140.
(Ox
1
x
2
),
(x
1
= x
2
= 0).
x
1
= 0, x
2
= 30
x
1
x
1
= 0
3x
1
+ 9x
2
= 270 x
1
= 30, x
2
= 20.
1
◦
x
s
= x
1
,
x
1
= 60, x
2
= 0,
2x
1
+ 3x
2
= 120 x
1
= 30, x
2
= 20
z = −140.
z
z−z
0
= 0
z
0 140 z = −140
A
(m+1)×(n + 1). m
x
[I A
0
]
·
x
B
x
F
¸
= b
0
.
b
0
≥ 0. (m + 1)
[0 c
0T
]
·
x
B
x
F
¸
= z − z
0
.
(n + 1)
(x
B
= b
0
, x
F
= 0) 0
NB(i),
i = 1, m, i NF (j),
j = 1, 2, . . . , n −m,
z − z
0
.
1
◦
4
◦
1
◦
. NF (j)
a(m + 1, NF (j)), j = 1, 2, . . . , n − m
x
B
= b
0
, x
F
= 0, z
min
= z
0
,
x(NB(i)) = a(i, n + 1), i = 1, 2, . . . , m
x(NF (j)) = 0, j = 1, 2, . . . , n − m
z
min
= −a(m + 1, n + 1).
s, s = NF (l).
s
x(s)
2
◦
. i = 1, 2, . . . , m
k
NB(i),
s. i
x(NB(i)) + a
0
is
x(s) = b
0
i
,
a
0
is
A
0
; b
0
i
b
0
A a(i, j)
x(NB(i)) + a(i, s)x(s) = a(i, n + 1).
a
0
is
b
0
i
= a(i, n + 1),
max(x
s
)
x(s) x(NB(i))
i = 1, 2, . . . , m,
x(s)
1
◦
x(s) 2
◦
k,
k = arg min
i:a
0
i,s
>0,b
0
i
>0
·
b
0
i
a
0
is
¸
= arg min
i:a
0
i,s
>0,b
0
i
>0
·
a(i, n + 1)
a(i, s)
¸
.
x
s
i +1
a
0
is
= a(i, s) b
0
i
= a(i, n + 1)
max(x
s
)
> 0 > 0 b
0
i
/a
0
is
< 0 > 0 ∞
= 0 > 0 ∞
> 0 < 0 −∞
< 0 < 0 ∞
= 0 < 0 ∞
> 0 = 0 −∞
< 0 = 0 ∞
= 0 = 0 ∞
a
0
ks
= a(k, s)
k
s = NF (l)
NF (l)
←
→
NB(k).
3
◦
. k a(k, s )
4
◦
. k a(k, s),
i = 1, 2, . . . , m + 1, i = k
3
◦
4
◦
a(k, s)
1
◦
2
◦
(n − m + 1) A
n + 1 b
0
a(k, s) (n − m − 1)
x(NB(k)),
m
x
1
≥ 0, x
2
≥ 0
x
1
+ x
2
≤ 50;
−x
1
+ x
2
≤ 10;
x
1
≥ 20;
x
2
≥ 10;
−2x
1
− 3x
2
= z → min .
Ox
1
x
2
P = (20, 10)
Q = (20, 15) R = (30, 20) S = (40, 10) z
−grad(z) = (2, 3),
R z
min
= −120.
x
1
+ x
2
+ x
3
= 50;
−x
1
+ 2x
2
+ x
4
= 10;
x
1
− x
5
= 20;
x
2
− x
6
= 10;
−2x
1
− 3x
2
= z → min .
A(5, 7), N B(4) N F (2)
A
1 1 1 0 0 0 50
→ −1 2 0 1 0 0 10
−1 0 0 0 1 0 −20
0 −1 0 0 0 1 −10
−2 −3 0 0 0 0 0
↑
NB
(1) 3
(2) 4
(3) 5
(4) 6
NF
(1) 1
(2) 2
= (0, 0, 50, 10, −20, −10) 6= .
1
◦
. s ; l
2
◦
. min(50/1, 10/2, ∞, ∞) = 5; k
1
◦
2
◦
s = 2 k = 2;
2
3
◦
.
A
1 1 1 0 0 0 50
→ −1/2 1 0 1/2 0 0 5
−1 0 0 0 1 0 −20
0 −1 0 0 0 1 −10
−2 −3 0 0 0 0 0
↑
NB
(1) 3
(2) 4
(3) 5
(4) 6
NF
(1) 1
(2) 2
4
◦
. NF (l)
←
→
NB(k) :
A
→ 3/2 0 1 −1/2 0 0 45
−1/2 1 0 1/2 0 0 5
−1 0 0 0 1 0 −20
−1/2 0 0 1/2 0 1 −5
−7/2 0 0 3/2 0 0 15
↑
NB
(1) 3
(2) 2
(3) 5
(4) 6
NF
(1) 1
(2) 4
= (0, 5, 45, 0, −20, −5) 6= .
1
◦
. s ; l
2
◦
. min(
45
3/2
, ∞, ∞, ∞) = 30; k
s = 1, k = 1,
3/2
3
◦
.
A
→ 1 0 2/3 −1/3 0 0 30
−1/2 1 0 1/2 0 0 5
−1 0 0 0 1 0 −20
−1/2 0 0 1/2 0 1 −5
−7/2 0 0 3/2 0 0 15
↑
NB
(1) 3
(2) 2
(3) 5
(4) 6
NF
(1) 1
(2) 4
4
◦
. NF (l)
←
→
NB(k) :