Dual Simplex with Artificial Constraints. Consider the following problem:

Maximize z = 2x1 - x2 + x3 subject to 2x1 + 3x2 - 5x3 Ú 4 -x1 + 9x2 - x3 Ú 3 4x1 + 6x2 + 3x3 … 8 x1, x2, x3 Ú 0 The starting basic solution consisting of surplus variables x4 and x5 and slack variable x6 is infeasible because x4 = -4 and x5 = -3. However, the dual simplex is not applicable directly, because x1 and x3 do not satisfy the maximization optimality condition.
Show that by adding the artificial constraint x1 + x3 … M (where M is sufficiently large not to eliminate any feasible points in the original solution space), and then using the new constraint as a pivot row, the selection of x1 as the entering variable (because it has the most negative objective coefficient) will render an all-optimal objective row. Next, carry out the regular dual simplex method on the modified problem.