# How does the Big $M$ method work when there is more than one solution?

Let's say I've got a linear programming problem $(P)$ which consits in maximizing $z=c^tx$ subject to $Ax=b$, and in the process, I need to add an artificial variable $x_a$ to get a feasible solution.

When applying the Big-M method to the problem, that is, maximizing $z=c^tx-Mx_a$, I get an optimal solution $\overline{x}^*$ with objective function value of $\overline{z}$ (the final value for $x_a$ is $0$). My question then is,

Can I get more optimal solutions for the problem $(P)$? How can I tell if $(P)$ has more than one solution by looking only at the simplex algorithm using the Big-M method?

The simplex algorithm (whether using the big M method or not) gives you only one solution. Having several optimal solutions would mean you have a facet of solutions on the polyhedron $\{x:Ax=b\}$. Once you have one optimal solution, this can be seen by calculating the dimension of $\{x:Ax=b,c^tx=\bar z\}$ (check the rank of the matrix $(c,A^t)^t$)
• Thanks for your answer! But when terminating the simplex algorithm (with the tableaux form), I can check if there is more than one solution by looking at the terms $z_j-c_j$ for the non-basic variables, right? If one of them is $0$, then the variable $x_j$ would enter and it might provide another optimal solution $\overline{x}'$. Hence, the complete set of solutions would be $\lambda \overline{x}+(1-\lambda)\overline{x}'$. However, I encountered a problem in which,, when applying the Big M method, non of the $z_j-c_j$ terms were $0$ but more than one solution exists. – user313212 Sep 6 '16 at 17:05