Five Preliminaries
For every basic feasible solution x ∉ χ we have by Lemma 1 a feasible basis B. for every feasible basis B with index set I we have the reduced system $$ x_B + B^{ - 1} Rx_R = \bar b $$ (4.1) where \( \bar b = B^{ - 1} b \) . Hence a basic feasible solutio
- PDF / 867,049 Bytes
- 7 Pages / 547 x 686 pts Page_size
- 54 Downloads / 171 Views
For every basic feasible solution x E X we have by Lemma 1 a feasible basis B . For every feasible basis B with index set I we have the reduced system
+ B-IRxR = b
XB
where b =
B-Ib.
(4.1)
Hence a basic feasible solution x E X is defined by Xi
=
bp e for all e E l ,
Xi
=
0 for all e E N - I ,
where Pi is the position number of the variable e E l . If 1= {k l , . . . , km } . we can write equivalently Xki
For short. we write
= bi for aliI :::; i
XB = B-Ib. XR =
:::; m ,
Xi
= 0 for all
eE N -
I .
O.
Sufficient Optimality Criterion: Let B be a feasible basis. CB be the subvector of the row vector C corresponding to the basic variables. CR be the rest and ZB = cBB-Ib. If C R = CR -
c B B - I R 2: 0 ,
then the basic feasible solution x defined by B is optimal. Unboundedness Criterion: Let B be a feasible basis and I be the index set of basic variables. If there exists a j E N - I such that
(i)
Cj -
la
c BB -
j
< 0 and
(ti) B -Iaj :::;
O.
then the linear programming problem (LP) has an objective function value which is not bounded from below. Rank-One Update: Let B be a nonsmgular m x m matrix and u , v vectors with m components such that v T sr>« =I=- -1. Then (B
+ uv T) - 1 = B - 1 _
be any two column
(B- lu)(VT B- 1).
1 _
1 +vTB
E ~m
lU
Since the rank of the matrix uv T for any u. v E ~m is at most one. the above formula for the inverse of the matrix B when changed by uv T is called a "rank-one" update. Basis Change: Let B be a feasible basis with index set I. If there exists a j E N - I such that
(i)
Cj
=
c BB- laj
Cj -
< 0 and
(ti) B -1aj
1::. 0
(i.e.. B- 1aj has at least one positive entryll, then we obtain a new feasible basis B' with objective function value ZB' by replacing any column a i of B by the column a j if the variable eEl satisfies Pi = r where r is determined by
byj
-
r
. = mIn
{byj
D. Alevras et al., Linear Optimization and Extensions © Springer-Verlag Berlin Heidelberg 2001
i
~ :
YJi'
> O' , t = 1 , 2 , .. . , m }
(4.2)
56
4. FIVE PRELIMINARIES
and Yi = B- 1a j = (yJ ,y] ,.. . ,yj f· The "entering" variable j gets the position Pj = r in the new basis while the variable e that "leaves" the basis looses its position number. Moreover,
(4.3) where () = Yj b~ is the minimum ratio (4.2) . We note that a basis change can be described schematically as follows where rvt means "changes to": Row
I
o * 1
kl
Col. £
o o
Col. j
RHS
cBB-laj
Cj -
yJ
*
bl
I
Col. £
*k l
-(Cj - cBB- laj) /yj - Yj1/Yjr
Col. j RHS 0 -b -*()Yj1 0 l
"'-* :
m km
B CB
I
0
= (ak = (Ck = {k 1 , ...
yj
kr = j
yj
km
1' • • •
,kr
1
() = br/yj
- Yim/Yjr
0
bm
-
()yj
= a e, . . . , a km ) B ' = (ak l ' . . . , a kr = aj , ... , a km ) = ce, . .. , Ckm ) C B' = (Ck ,Ckr = Cj , . .. ,Ckm ) = e, ... ,km } I' = {kl, .. . .k; = i ,... , k m } .
, a kr ,Ckr
1 ' •• •
l/yj
rvt
rvt
1' • • •
rvt
Algebraically. a basis change is summarized by B' = B + (aj
where u,!, compute
= (
0
1 ...
-
0) (B ' ) -
ae)u~ E jRTn
l
and
CB'
= CB
+ (Cj
-
ce)
Data Loading...
