# Solving Linear Programming Via Big M method

$$\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:

moving $$x_1$$ to the basis we get:

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?

• The latter: there is no feasible solution. – LinAlg Jul 8 at 12:39