146 Linear Programming I: Simplex Method
form as shown below:Basic Variables b′′
i/a
′′
isfor
variables x 1 x 2 x 3 x 4 x 5 x 6 −f b′′i a′′is> 0x 4 2 1
Pivot
element− 1 1 0 0 0 2 2←Smaller one
(x 4 drops from
next basis)
x 5 2 − 1 5 0 1 0 0 6
x 6 4 1 1 0 0 1 0 6 6
−f − 1 − 2 − 1 0 0 0 1 0
↑Most negativec′′i(x 2 enters next basis)Result of pivoting:x 2 2 1 − 1 1 0 0 0 2
x 5 4 0 4
Pivot
element1 1 0 0 8 2 (Select this
arbitrarily.x 5
drops from next
basis)
x 6 2 0 2 − 1 0 1 0 4 2
−f 3 0 − 3 2 0 0 1 4↑
Most negativec′′i(x 3 enters the next basis)Result of pivoting:x 2 3 1 0 54 14 0 0 4
x 3 1 0 1 14 14 0 0 2
x 6 0 0 0 −^32 −^12 1 0 0
−f 6 0 0 114 34 0 1 10Allc′′i are ≥ 0 and hence the present solution is optimum.Example 3.5 Unbounded SolutionMinimizef= − 3 x 1 − 2 x 2subject tox 1 −x 2 ≤ 1
3 x 1 − 2 x 2 ≤ 6
x 1 ≥ 0 , x 2 ≥ 0