0
$\begingroup$

enter image description here

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?

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

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.

$\endgroup$

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.