Engineering Optimization: Theory and Practice, Fourth Edition

136 Linear Programming I: Simplex Method

One special solution that can always be deduced from the system of Eqs. (3.19) is

xi=

{

b′′i, i= 1 , 2 ,... , m

0 , i=m+ 1 , m+ 2 ,... , n

(3.20)

This solution is called abasic solutionsince the solution vector contains no more

thanmnonzero terms. The pivotal variablesxi, i= 1 , 2 ,... , m, are called thebasic

variablesand the other variablesxi,i=m+ 1 ,m+ 2 ,... , n, are called thenonbasic

variables. Of course, this is not the only solution, but it is the one most readily deduced

from Eqs. (3.19). If allb′′i, i= 1 , 2 ,... , m, in the solution given by Eqs. (3.20) are

nonnegative, it satisfies Eqs. (3.3) in addition to Eqs. (3.2), and hence it can be called

abasic feasible solution.

It is possible to obtain the other basic solutions from the canonical system of Eqs.

(3.19). We can perform an additional pivotal operation on the system after it is in

canonical form, by choosinga′′pq (which is nonzero) as the pivot term,q>m,and

using any rowp(among 1, 2 ,... , m). The new system will still be in canonical form

but withxqas the pivotal variable in place ofxp. The variablexp, which was a basic

variable in the original canonical form, will no longer be a basic variable in the new

canonical form. This new canonical system yields a new basic solution (which may or

may not be feasible) similar to that of Eqs. (3.20). It is to be noted that the values of

all the basic variables change, in general, as we go from one basic solution to another,

but only one zero variable (which is nonbasic in the original canonical form) becomes

nonzero (which is basic in the new canonical system), and vice versa.

Example 3.3 Find all the basic solutions corresponding to the system of equations

2 x 1 + 3 x 2 − 2 x 3 − 7 x 4 = 1 (I 0 )

x 1 +x 2 +x 3 + 3 x 4 = 6 (II 0 )

x 1 −x 2 +x 3 + 5 x 4 = 4 (III 0 )

SOLUTION First we reduce the system of equations into a canonical form withx 1 ,

x 2 , andx 3 as basic variables. For this, first we pivot on the elementa 11 = to obtain 2

x 1 +^32 x 2 −x 3 −^72 x 4 =^12 I 1 =^12 I 0

0 −^12 x 2 + 2 x 3 +^132 x 4 =^112 II 1 = II 0 −I 1

0 −^52 x 2 + 2 x 3 +^172 x 4 =^72 III 1 = III 0 −I 1

Then we pivot ona 2 ′ 2 = −^12 , to obtain

x 1 + 0 + 5 x 3 + 61 x 4 = 71 I 2 =I 1 −^32 II 2

0 +x 2 − 4 x 3 − 31 x 4 = − 1 1 II 2 = − 2 II 1

0 + 0 − 8 x 3 4 − 2 x 4 = − 2 4 III 2 = III 1 +^52 II 2