138 Linear Programming I: Simplex Method
into the current basis in place ofx 2. Thus we have to pivota′′ 23 in Eq. (II 4 ) This leads.
to the following canonical system:x 1 +x 2 = 3 I 5 =I 4 +^13 II 5x 3 + 3 x 2 = 6 II 5 = II (^34)
x 4 −x 2 = − 1 III 5 = III 4 −^13 II 5
The solution forx 1 ,x 3 , andx 4 is given by
x 1 = 3 −x 2
x 3 = 6 − 3 x 2
x 4 = − 1 +x 2
from which the basic solution can be obtained as
x 1 = 3 , x 3 = 6 , x 4 = − 1 (basic variables)
x 2 = 0 (nonbasicvariable)
Since all thexjare not nonnegative, this basic solution is not feasible.
Finally, to obtain the canonical form in terms of the basic variablesx 2 ,x 3 , andx 4 ,
we pivot ona′′ 12 in Eq. (I 5 ), thereby bringingx 2 into the current basis in place ofx 1.
This gives
x 2 +x 1 = 3 I 6 =I 5
x 3 − 3 x 1 = − 3 II 6 = II 5 − I (^36)
x 4 +x 1 = 2 III 6 = III 5 +I 6
This canonical form gives the solution forx 2 ,x 3 , andx 4 in terms ofx 1 as
x 2 = 3 −x 1
x 3 = − 3 + 3 x 1
x 4 = 2 −x 1
and the corresponding basic solution is
x 2 = 3 , x 3 = − 3 , x 4 = 2 (basic variables)
x 1 = 0 (nonbasic variable)
This basic solution can also be seen to be infeasible due to the negative value forx 3.
3.8 Motivation of the Simplex Method
Given a system in canonical form corresponding to a basic solution, we have seen how
to move to a neighboring basic solution by a pivot operation. Thus one way to find the
optimal solution of the given linear programming problem is to generate all the basic