1
$\begingroup$

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?

Thanks in advance!

$\endgroup$
1
$\begingroup$

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$)

Following comment : what you are describing is a special case of having many optimal solutions. It could be more difficult to see, hence the dimension estimation.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user313212 Sep 6 '16 at 17:05
  • $\begingroup$ Then, did I mess it up at some stage of the algorithm or is this result consistent with the algorithm? $\endgroup$ – user313212 Sep 6 '16 at 17:06

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.