# Simplex method and basic solutions I have put this into the form

$0.5x_1 + 0.25x_2 + x_3=6$

$-x_1 - 3x_2 + x_4=-2$

$x_1 + x_2 = 10$

Is this correct? If so, how do I find a basic solution so that I can begin the simplex algorithm?

• i have computed $2x_1+3x_2\geq 20$ and the equalsign holds if $x_1=10,x_2=0$ – Dr. Sonnhard Graubner Oct 27 '14 at 20:24
• @Amzoti I got $x_5=6, x_6=2, x_7=10$? – Mark Oct 27 '14 at 20:28

## 1 Answer

The system of linear equations in the question can't help finding a basic feasible solution since artificial variables $x_5, x_6 \ge 0$ are missed in the second and third constraints.

$0.5x_1 + 0.25x_2 + x_3=6$

$-x_1 - 3x_2 + x_4 + x_5=-2$

$x_1 + x_2 + x_6 = 10$

To find a basic feasible solution to the original LP, we use the two-phase simplex method.

To start with phase I, consider $\min(x_5 + x_6)$ with the above constraints. This can be done with simplex algorithm. As @Dr.SonnhardGraubner points out, this LP has a basic optimal feasible solution $x_1 = 10, x_2 = 0, \dots, x_5 = x_6 = 0$. (You may end up with another feasible solution.) The artificial variables vanish, so we have a basic feasible solution to the original LP.