While dealing with a linear programming problem we usually try to start with the basic feasible solution corresponding to the identity Matrix in the coefficient matrix. I have no idea how to solve the following type of LPP:

Solve the LPP using simplex method starting with the basic feasible solution $x_1=4$ and $x_2=0$

Max $z=-x_1+2x_2$ subject to $$3x_1+4x_2=12$$ $$2x_1-x_2\leq 12$$ $$x_1\geq 0, x_2\geq 0$$

Please help!


This is a case where you have to introduce an artificial variable. I don't know why an initial solution in terms of $x_1$ and $x_2$ is given since it is not with these variables that we begin.

I introduced an artificial variable $x_4$ to account for the first constraint being an equation. The second constraint doesn't need an artificial variable because when we put it in the standard form, the slack variable $x_3$ gives us a basis to begin the iterations. So our basic feasible solution here is $x_3 = 12$, $x_4 = 12$, but we now want to minimize a new objective function $w = x_4$.

After following the simplex algorithm, I get $w = 0$ which is surely its minimum, since $w$ is a non-negative function, and I end up with a basis in terms of variables $\{x_2, x_3\}$. This means the original problem is feasible and attains its optimal solution at the same point $w$ attain its minimum --- which is at $x_2 = 3, x_3 = 15$, when $z = 6$.

So the final answer is $z = 6$ at $(0, 3)$ because the original problem is only involved with variables $x_1$, $x_2$, so we must not mention $x_3$ and $x_4$ here.

If you haven't seen artificial variables yet, you need to study that. Once you know how to work with it, this answer should make sense. If not, let me know the point of confusion and I'll clarify the answer.


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.