2
$\begingroup$

$$\text{Max } x_1 +3x_2$$ $$\text{s.t } 3x_1+x_2\leq 3$$ $$x_1-x_2\geq 2$$ $$x_1,..,x_2\geq 0$$

So we first transform to the standard form:

$$\text{Min } -x_1 -3x_2$$ $$\text{s.t } 3x_1+x_2+x_3= 3$$ $$x_1-x_2-x_4= 2$$ $$x_1,..,x_4\geq 0$$

Because there is no basic feasible solution we will add and artificial variable to move to a canonical form:

$$\text{Min } -x_1 -3x_2$$ $$\text{s.t } 3x_1+x_2+x_3= 3$$ $$x_1-x_2-x_4+x_5= 2$$ $$x_1,..,x_5\geq 0$$

Using Big M we will add $mx_5$ to the objective function:

$$\text{Min } -x_1 -3x_2+mx_5$$ $$\text{s.t } 3x_1+x_2+x_3= 3$$ $$x_1-x_2-x_4+x_5= 2$$ $$x_1,..,x_5\geq 0$$

But now, it is is not in basic form as the objective function need to be written in the non basic variables, so we will add -M times equation 2 to the objective function:

$$\text{Min } (-m-1)x_1 +(m-3)x_2+mx_4=-m-1$$ $$\text{s.t } 3x_1+x_2+x_3= 3$$ $$x_1-x_2-x_4+x_5= 2$$ $$x_1,..,x_5\geq 0$$

Now we can start the simplex: enter image description here

moving $x_1$ to the basis we get:

enter image description here

But here all the coefficients of the objective function is positive as $m$ is a big positive number, how can we continue? or we can not and we still have $x_5$ is the basis so there is no feasible solution?

$\endgroup$
  • 2
    $\begingroup$ The latter: there is no feasible solution. $\endgroup$ – LinAlg Jul 8 at 12:39

Your Answer

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

Browse other questions tagged or ask your own question.