I am relatively new still to linear optimization and as I understand it, the two phase method is a common practice for finding the bfs before using the simplex or a simplex like solver (a solver relying on an initial bfs). I am using this document as a resource to understand how to construct a phase I, but I am getting doubts that the author has provided all the information needed.

I'll skip to the standard form of the problem which is as follows

\begin{align*} \text{max } & 2x_1 &+ 3x_2 &+ x_3 & \\ \end{align*}

Subject to

\begin{align*} &x_1 & +x_2 & +x_3 & +x_4 & & & =40\\ 2&x_1 & + x_2 & -x_3 & & -x_5 & & =10\\ & & -x_2 & +x_3 & & &-x_6 & =10\\ \end{align*}


\begin{align*} x_1,x_2,x_3,x_4,x_5,x_6\geq0 \end{align*}

We can see that we have 3 constraints and yet we only add two artificial variables $x_7$ and $x_8$. I believe that 2 artificial variables are always sufficient because it is explained that if $x_7+x_8=0$ then both independently equal 0.

The author doesn't state that two is sufficient but I believe it is what he is implying. Is this the correct interpretation?


\begin{align*} x_1 + x_2 + x_3 + x_4 & =40\\ 2x_1 + x_2− x_3 − x_5 & =10\\ −x_2 + x_3− x_6 & =10 \end{align*}

Solve all three equations for $x_4$, $x_5$, and $x_6$ after setting $x_1 = x_2 = x_3 = 0$. Now, \begin{align*} x_4 & = 40\\ -x_5 & = 10\\ -x_6 & = 10. \end{align*}

So we need only two artificial variables for the negative slack variables.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.