Multiple optimal solutions

A common misconception among beginners in optimization is the idea that optimization problems really have just one solution. Surprisingly, this is typically not true. For many practical problems, the objective (whether it is cost or revenue or ...) is dominated by a handful of variables, while most variables are just there to ensure that the actual operation of the solution is possible. Consider a staffing problem, for example, where cost is typically driven by the number of people who work on a given day, not by the specific people.

These kind of situations naturally lead to problems similar to

<span>$</span>\begin{array}{lrrl}
\max & y & \vec{c}=&(0,1)\
s.t. & -x \leq 0 & A_{1\cdot}=...
... \leq 0 & A_{3\cdot}=&(0,-1)\
& y \leq 1 & A_{4\cdot}=&(0,1).\
\end{array}<span>$</span>
Graphically this can be depicted as
\scalebox{1.0}{\includegraphics[width=4in]{refman_misc/codedraw5.pdf}}
In this situation is clear that <span>$</span>x^1<span>$</span>, <span>$</span>x^3<span>$</span>, and all solutions lying on the line between these two points are optimal. The simplex algorithm will return either <span>$</span>x^1<span>$</span> or <span>$</span>x^3<span>$</span> (and may switch if you change parameters). The barrier algorithm (without crossover) will return <span>$</span>x^2<span>$</span>. These solutions are all correct; the problem as stated has no reason to prefer one over the other. If you do have a preference, you'll need to state it in your objective function.