Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
q
q = m−r, 0 < q < m
b r
B A B
a
i
x
i
(n − r) r
P
x
j
= 0, j = r + 1, r + 2, . . . , n
r
X
j=1
x
j
a
j
= b, x
j
> 0, j = 1, 2, . . . , r.
{a
j
, j = 1, 2, . . . , r} r ≤ m
m = rankA
(m − r)
{a
j
, j = 1, 2, . . . , r}
r
X
j=1
α
j
a
j
= 0
α
i
= 0 α
k
> 0 k = 1, r
−1
a
k
= −
r
X
j=1,j6=k
(
α
j
α
k
)a
j
.
x
1
a
1
+ . . . + x
k
a
k
+ . . . + x
r
a
r
= b.
a
k
x
1
a
1
+ . . . + x
k
(. . . −
α
k−1
α
k
a
k−1
−
α
k+1
α
k
a
k+1
− . . .) + . . . + x
r
a
r
= b.
r
X
j6=k,j=1
(x
j
−
α
j
x
k
α
k
)a
j
= b.
k
x
k
α
k
= min
j
(
x
j
α
j
; α
j
> 0).
X
j
= x
j
− α
j
(
x
k
α
k
), j 6= k, j = 1, r
X
j
= 0, j = k, r + 1, r + 2, . . . , n.
X = (X
1
, X
2
, . . . , X
n
)
n
X
i=1
X
i
a
i
= b
X
i
≥ 0 i = 1, n (r − 1)
(n − r + 1)
a
k
a
j
j = 1, r, Ax = b
r ≤ m
X x, Ax = b, x ≥ 0
x
0
x
0
X x, Ax = b, x ≥ 0
x
0
= (x
1
, . . . , x
m
, 0, . . . , 0)
T
x
0
Ax = b x ≥ 0
(n − m)
x
0
x
0
x
0
X u v
x
0
= θu + (1 −θ)v θ, 0 < θ < 1 Au = b,
Av = b, u, v ≥ 0 u, v ∈ X (n −m)
u v
0 = θu
m+1
+ (1 − θ)v
m+1
0 = θu
m+2
+ (1 − θ)v
m+2
0 = θu
n
+ (1 − θ)v
n
.
θ (1 − θ)
x
0
u
v u
m+1
, . . . , u
n
≥ 0 v
m+1
, . . . , v
n
≥ 0.
u
j
= 0 v
j
= 0, j = m + 1, . . . , n u v
Ax = b, x ≥ 0 (n −m)
x
0
= u = v
x
0
X x
0
r
x
0
r ≤ m
r a
j
x
0
α
j
= 0, j = 1, r
r
X
j=1
α
j
a
j
= 0.
ρ α
j
6= 0
0 < ρ < min
j
x
0
j
| α
j
|
.
x
1
= x
0
+ ρα, x
2
= x
0
− ρα
x
1
≥ 0 x
2
≥ 0
α α = (α
1
, α
2
, . . . , α
r
, 0, . . . , 0)
Aα = 0
Ax
1
= A(x
0
+ ρα) = Ax
0
+ ρAα = Ax
0
= b;
Ax
2
= A(x
0
− ρα) = Ax
0
− ρAα = Ax
0
= b.
x
0
=
1
2
(x
1
+ x
2
) = θx
1
+ (1 − θ)x
2
, θ =
1
2
,
x
1
, x
2
∈ X
x
0
x
0
x
0
α
j
a
j
,
j = 1, r a
j
∈ IR
m
r m, r ≤ m
x
0
X
a
j
Ax = b, x ≥ 0
z = c
T
x
X
p
1
, p
2
, . . . , p
k
z
1
, z
2
, . . . , z
k
z = c
T
p
i
z
i
= c
T
p
i
, i = 1, 2, . . . , k.
p
1
, p
2
, . . . , p
k
X
x
x = θ
1
p
1
+ θ
2
p
2
+ . . . θ
k
p
k
, θ
i
≥ 0,
k
X
i=1
θ
i
= 1.
x x ∈ X
z = c
T
x = θ
1
c
T
p
1
+ θ
2
c
T
p
2
+ . . . θ
k
c
T
p
k
= θ
1
z
1
+ θ
2
z
2
+ . . . θ
k
z
k
.
x ∈ X
min z = min c
T
x
θ
i
≥ 0 1
z = θ
1
z
1
+ θ
2
z
2
+ . . . θ
k
z
k
,
z
i
= c
T
p
i
z
i
z
min
l
z
j
= z
min
, j = 1, 2 . . . , l z = θ
1
z
1
+. . . θ
k
z
k
z
min
θ
1
+. . . θ
l
= 1 θ
i
= 0 i = l + 1, . . . , k.
z = c
T
x
p
j
p
1
, p
2
, . . . , p
l
x =
l
X
i=1
θ
i
p
i
,
l
X
i=1
θ
i
= 1, 0 ≤ θ
i
X
m
n
X
m
a
j
A
m x
1
, x
2
, . . . , x
m
.
B = [a
1
, a
2
, . . . , a
m
].
A = [B | R] R = [a
m+1
, . . . , a
n
]
B
x
B
= (x
1
, x
2
, . . . , x
m
)
T
x
F
= (x
m+1
, x
m+2
, . . . , x
n
)
T
,
x = (x
B
, x
F
).
c
B
= (c
1
, . . . , c
m
)
T
c
F
= (c
m+1
, . . . , c
n
)
T
c = (c
B
, c
F
).
z = c
T
x
Ax = b, x ≥ 0.
B
−1
Ax = b
Bx
B
+ Rx
F
= b, x
B
+ B
−1
Rx
F
= b
0
, b
0
= B
−1
b.
B
−1
R m ×(n −m) A
0
A
0
= B
−1
R = [a
0
m+1
: a
0
m+2
: . . . : a
0
n
];
a
0
j
= B
−1
a
j
, j = m + 1, . . . , n.
z = c
T
x
z = c
T
B
x
B
+ c
T
F
x
F
= c
T
B
(b
0
− A
0
x
F
) + c
T
F
x
F
=
= c
T
B
b
0
+ (c
T
F
− c
T
B
A
0
)x
F
= z
0
+ c
0T
x
F
,
c
0
, c
0T
= c
T
F
− c
T
B
A
0
,
c
0
j
= c
j
− c
T
B
a
0
j
, j = m + 1, . . . , n,
z x
F
= 0 z
0
z
0
= c
T
B
b
0
.
min
x
(z = c
T
x), Ax = b, x ≥ 0
x
B
= (x
1
, . . . , x
m
) :
z − z
0
= c
0T
x
F
x
B
+ A
0
x
F
= b
0
, x
B
≥ 0, x
F
≥ 0,
z
0
= c
T
B
b
0
; b
0
= B
−1
b; A
0
= {a
0
j
}, j = m + 1, . . . , n
c
0
j
= c
j
− c
T
B
a
j
, a
0
j
= B
−1
a
j
, j = m + 1, . . . , n.
B = {a
j
}, j = 1, m, rankB = m; A = {a
j
}, j = 1, n.
x
B
(z − z
0
)
x
F
.
x
F
= 0;
x
B
= b
0
;
z = z
0
= c
T
B
b
0
.
b
0
≥ 0,
b
0
≥ 0.
z
z :
z − z
0
= c
0T
x
F
.
c
0
c
0
> 0 z x
F
= 0
x
F
≥ 0
z = z
0
c
0
c
0
s
a
0
is
≤ 0 i = 1, . . . , m
z
a
0
is
> 0 i
z
c
0
c
0
≥ 0
c
0
s
z
x x
(1)
x
(2)
x = θx
(1)
+ (1 − θ)x
(2)
, 0 ≤ θ ≤ 1
z
c
0
c
0
≥ 0,
x
F
≥ 0 z x
F
= 0.
z = z
0
c
0
z 0
x
F
,
(z − z
0
) = c
0T
x
F
c
0
,
x
B
+ A
0
x
F
= b
0
, x
B
≥ 0, x
F
≥ 0.