# Simplex Method with Nontrivial Initial Solution

I have a linear program with the following tableaux:

$$\begin{array}{crrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & P & rhs \\ \hline & 67& 126& 52& 36& -7& 0& 988\\ & -24& -46& -19& -14& 3& 0& -358 \\ & -9& -17& -7& -5& 1& 0& -133\\ \hline & -40 & -30 & 0 & 0 & 0 & 1 & 0 \\ \hline \end{array}$$

where I want to maximize $$P$$. I want to apply the simplex method starting from the initial solution $$(x_1,x_2,s_1,s_2,s_3)=(8,0,8,1,0)$$, but I'm confused about how to pivot when nearly all elements of the matrix are nonzero.

You have to make $$x_1$$, $$s_1$$, and $$s_2$$ basic first. To achieve this you can execute a sequence of pivots such that the matrix corresponding to these columns is the identity matrix $$I$$. This is the same process used in Gaussian elimination to produce a reduced row echelon form. After that continue with Phase II of the Simplex method.