I have the LP and need to solve it using the two phase simplex algorithm, not the dual two phase;
$$\max\quad4x_1 - 3x_2 + 6x_3$$ $$\text{Subject to: }\quad x_1 + x_2 \le -4$$ $$\text{ }\qquad\qquad\quad x_2 + x_3 \le -6$$ $$\quad\qquad x_3 \le 6$$
When I transform this into an auxiliary problem; $$\max zeta =\qquad\qquad\qquad\quad\quad$$ $$\text{S.T }\quad x_4 = -4 - x_1 - x_2 + x_0$$ $$x_5 = -6 - x_2 - x_3 + x_0$$ $$x_6 = 6 x_3 + x_0$$
And do my first pivot step with $x_0$ entering the basis and $x_5$ leaving the basis (because its the most negative coefficient).
I end up with the objective function being zeta $= -6 -x_2 -x_3 -x_5$, which doesn't allow me to carry on the simplex algorithm.
I’m unsure if those variables are supposed to be non-negative or unsigned, so we’re going to proceed for both cases:
Unsigned Model to Two-Phase:
Suppose we have the original model, $$\max\quad z=4x_1-3x_2+6x_3$$ Subject to, $$x_1+x_2\le-4$$ $$x_2+x_3\le-6$$ $$x_3\le6$$
We’ll need to make the right-hand-side non-negative such that we have $\ge$ constraints for artificial variables:
$$\max\quad z=4x_1-3x_2+6x_3$$ Subject to, $$-x_1-x_2\ge4$$ $$-x_2-x_3\ge6$$ $$x_3\le6$$
Of course, since this is unsigned, we’ll need to substitute a $x_j=x_j^{’}-x^{ ’’}_j$ for every unsigned variable in the program. So, we’ll have the following model:
$$\max\quad z=4x_1^{'}-4x_1^{''}-3x_2^{'}+3x_2{''}+6x_3^{'}-6x_3^{''}$$ Subject to, $$-x_1^{'}+x_1^{''}-x_2^{'}+x_2^{''}\ge4$$ $$-x^{'}_2+x^{''}_2-x^{'}_3+x^{''}_3\ge6$$ $$x^{'}_3-x^{''}_3\le6$$ $$x_1^{'},x_1^{''}, x_2^{'},x_2^{''}, x_3^{'},x_3^{''} \ge0$$
The standardized form of this model in the two phase approach would be: $$\min w= a_1+a_2$$ Subject to, $$-x_1^{'}+x_1^{''}-x_2^{'}+x_2^{''}-e_1+a_1=4$$ $$-x^{'}_2+x^{''}_2-x^{'}_3+x^{''}_3-e_2+a_2=6$$ $$x^{'}_3-x^{''}_3+s_3=6$$ $$x_1^{'},x_1^{''}, x_2^{'},x_2^{''}, x_3^{'},x_3^{''}, e_1, e_2,a_1,a_2,s_3\ge0$$
NOTE: Once this model has been solved, be sure to remember to plug in the values we got for $x_1^{'}\ldots x_3^{'’}$ back into their original substitutions to figure out the actual values for $x_1, x_2$, and $x_3$. For example, suppose we got $x_1^{''}=7$ and $x_1^{'}=3$ for the final output from the Simplex algorithm, then $x_1=3-7=-4$.
Non-Negative Model to Two-Phase
If the non-negative constraints were forgotten, then the model will go as follows: $$\max\quad z=4x_1-3x_2+6x_3$$ Subject to, $$-x_1-x_2\ge4$$ $$-x_2-x_3\ge6$$ $$x_3\le6$$ $$x_1,x_2,x_3\ge0$$
Which will standardize into:
$$\min\quad w=a_1+a_2$$ Subject to, $$-x_1-x_2-e_1+a_1=4$$ $$-x_2-x_3-e_2+a_2=6$$ $$x_3+s_3=6$$ $$x_1,x_2,x_3,e_1,e_2,a_1,a_2,s_3\ge0$$
In Either
In either approach, once we standardize the models, we’ll need to load them into their initial tableaus and solve for $a_1$ and $a_2$ to be our initial basic variables. Once both $a_1,a_2=0$, we’ll drop their respective columns and rows and proceed with Simplex normally as we would. From here, we’ll leave solving the rest of the model to the reader.