4
$\begingroup$

I try to solve the following linear program with the simplex method:

$$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & & & x_2 & \le & ~5 \\ & & x_1 & {}-{} & x_2 & \ge & 2 \\ & & x_1 & & & \ge & 0 \\ & & & & x_2 & \ge & 0 \\ \end{alignedat} $$

Convert to standard form:

$$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & & & x_2 & \le & 5 \\ & {}-{} & x_1 & {}+{} & x_2 & \le & ~-2 \\ & & x_1 & & & \ge & 0 \\ & & & & x_2 & \ge & 0 \\ \end{alignedat} $$

Convert to slack form:

$$ \begin{alignedat}{4} z & = & 0 & {}+{} & x_1 & {}-{} & 2x_2\\ x_3 & = & 5 & & & {}-{} & x_2\\ x_4 & = & ~-2 & {}+{} & x_1 & {}-{} & x_2\\ \end{alignedat} $$

The basic solution is $(x_1,x_2,x_3,x_4) = (0,0,5,-2)$.

Can I find an optimal solution here? If not, why not?

$\endgroup$
  • 4
    $\begingroup$ Welcome to OR.SE. I suggest that you use MathJax formatting (check here) for your formulation rather than coding style. Now about your problem: Are you trying to solve this problem with primal simplex or dual simplex? If primal, have you read around about 2-phase method? $\endgroup$ – EhsanK Jul 13 '19 at 5:38
  • $\begingroup$ Thank you EhsanK . I will edit this post using MathJax formatting.I have used Dual simplex to solve this problem. $\endgroup$ – Kavishka Gamage Jul 13 '19 at 7:15
  • 1
    $\begingroup$ @codekcg so, when you solved your problem, did you answer your own question? If so, you may retract the question or add an answer and edit the question so that others can learn from you $\endgroup$ – Marco Lübbecke Jul 13 '19 at 9:43
  • $\begingroup$ @MarcoLübbecke above I have tried to answer but I get stucked after getting a negative value for non basic variable(x4).So I don't know how to solve this further. $\endgroup$ – Kavishka Gamage Jul 13 '19 at 16:36
9
$\begingroup$

From the slack form we can observe two things about your starting point $(x_1,x_2) = (0,0)$.

  1. The starting point is not primal feasible. This follows from the fact that not all variables $x_1$, $x_2$, $x_3$, $x_4$ are non-negative ($x_4 < 0$).
  2. The starting point is not dual feasible. This follows from the fact that not all variable coefficients in the $z$-row are non-positive ($x_1$ has coefficient $1 > 0$).

This means that before you can use primal or dual simplex, you first have to find a primal or dual feasible solution. You can do this with the Big M method or with the two phase simplex method.

You can use the following very helpful site to see all the simplex steps for your problem:

The first link will tell you that the initial solution is indeed dual infeasible. The other links will show that the problem is actually unbounded, and does not have a solution.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you .Given links are very helpful. $\endgroup$ – Kavishka Gamage Jul 14 '19 at 6:36

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.