Engineering Optimization: Theory and Practice, Fourth Edition

224 Linear Programming II: Additional Topics and Extensions

whereX= {x 1 , x 2 ,... , xn}T, c={c 1 , c 2 ,... , cn}T, and [ a]is anm×nmatrix. In

addition, an interior feasible starting solution to Eqs. (4.59) must be known. Usually,

X=

{

1

n

,

1

n

,· · ·

1

n

}T

is chosen as the starting point. In addition, the optimum value off must be zero for

the problem. Thus

X(^1 )=

{

1

n

1

n

· · ·

1

n

}T

= nterior feasiblei

fmin= 0

(4.60)

Although most LP problems may not be available in the form of Eq. (4.59) while

satisfying the conditions of Eq. (4.60), it is possible to put any LP problem in a form

that satisfies Eqs. (4.59) and (4.60) as indicated below.

4.7.2 Conversion of an LP Problem into the Required Form

Let the given LP problem be of the form

MinimizedTX

subjectto

[α]X=b

X≥ 0

(4.61)

To convert this problem into the form of Eq. (4.59), we use the procedure suggested

in Ref. [4.20] and define integersmandnsuch thatXwill be an (n−3)-component

vector and [α] will be a matrix of orderm− 1 ×n−3. We now define the vector

z= {z 1 , z 2 , · ·· , zn− 3 }Tas

z=

X

β

(4.62)

whereβis a constant chosen to have a sufficiently large value such that

β>

∑n−^3

i= 1

xi (4.63)

for any feasible solutionX(assuming that the solution is bounded). By using Eq. (4.62),

the problem of Eq. (4.61) can be stated as follows:

MinimizeβdTz

subject to

[α]z=

1

β

b

z≥ 0

(4.64)