4.4 Decomposition Principle 201A 1 X 1 +A 2 X 2 + · · · +ApXp=b 0 (4.25b)B 1 X 1 =b 1
B 2 X 2 =b 2
..
.
BpXp=bp
(4.25c)X 1 ≥ 0 , X 2 ≥ 0 ,·· ·,Xp≥ 0where
X 1 =
x 1
x 2
..
.
xm 1
,X 2 =
xm 1 + 1
xm 1 + 2
..
.
xm 1 +m 2
,... ,
Xp=
xm 1 +m 2 +···+mp− 1 + 1
xm 1 +m 2 +···+mp− 1 + 2
xm 1 +m 2 +···+mp− 1 +mp
X=
X 1
X 2
..
.
Xp
It can be noted that if the size of the matrixAkis (r 0 ×mk) and that ofBkis (rk×mk),
the problem has
∑p
k= 0 rkconstraints and∑p
k= 1 mkvariables.
Since there are a large number of constraints in the problem stated in Eqs. (4.25),
it may not be computationally efficient to solve it by using the regular simplex
method. However, the decomposition principle can be used to solve it in an efficient
manner. The basic solution procedure using the decomposition principle is given by
the following steps.
1.Definepsubsidiary constraint sets using Eqs. (4.25) as
B 1 X 1 =b 1B 2 X 2 =b 2
..
.
BkXk=bk
..
.BpXp=bp(4.26)
Thesubsidiary constraint set
BkXk=bk, k= 1 , 2 ,... , p (4.27)
representsrkequality constraints. These constraints along with the requirement
Xk≥ 0 define the set of feasible solutions of Eqs. (4.27). Assuming that this set