3.7 Pivotal Reduction of a General System of Equations 137Finally we pivot ona′ 33 to obtain the required canonical form asx 1 +x 4 = 2 I 3 =I 2 − III (^53)
x 2 −x 4 = 1 II 3 = II 2 + III (^43)
x 3 + 3 x 4 = 3 III 3 = −^18 III 2
From this canonical form, we can readily write the solution ofx 1 ,x 2 , andx 3 in terms
ofthe other variablex 4 as
x 1 = 2 −x 4
x 2 = 1 +x 4
x 3 = 3 − 3 x 4
If Eqs.(I 0 ) I,(I 0 ) and, (III 0 ) arethe constraints of a linear programming problem, the
solution obtained by setting the independent variable equal to zero is called a basic
solution. In the present case, the basic solution is given by
x 1 = 2 , x 2 = 1 , x 3 = 3 (basic variables)
andx 4 = (nonbasic or independent variable). Since this basic solution has all 0 xj≥
0 (j= 1 , 2 , 3 , 4 ), it is a basic feasible solution.
If we want to move to a neighboring basic solution, we can proceed from the
canonical form given by Eqs.(I 3 ) I,(I 3 ) and, (III 3 ) Thus if a canonical form in terms.
of the variablesx 1 ,x 2 , andx 4 is required, we have to bringx 4 into the basis in place
of the original basic variablex 3. Hence we pivot ona′′ 34 in Eq. (III 3 ) This gives the.
desired canonical form as
x 1 −^13 x 3 = 1 I 4 =I 3 − III 4
x 2 +^13 x 3 = 2 II 4 = II 3 + III 4
x 4 +^13 x 3 = 1 III 4 =^13 III 3
This canonical system gives the solution ofx 1 ,x 2 , andx 4 in terms ofx 3 as
x 1 = 1 +^13 x 3
x 2 = 2 −^13 x 3
x 4 = 1 −^13 x 3
and the corresponding basic solution is given by
x 1 = 1 , x 2 = 2 , x 4 = 1 (basic variables)
x 3 = 0 (nonbasic variable)
This basic solution can also be seen to be a basic feasible solution. If we want to move
to the next basic solution withx 1 ,x 3 , andx 4 as basic variables, we have to bringx 3