Multiple optima
Multiple Optima
A linear programming problem has multiple optima when more than one feasible point has the same best objective value.
Graphically, this usually happens when the objective contour line is parallel to an edge of the feasible region.
Basic Idea
The objective contour lines are:
\[c^Tx=k\]At the optimal value $k^*$, the final contour line may touch the feasible region along an entire edge.
Then every point on that edge is optimal.
Example
Consider:
\[\max x_1+x_2\]subject to:
\[x_1+x_2\le 4\] \[x_1\ge 0\] \[x_2\ge 0\]The feasible region is a triangle with vertices:
\[(0,0),\quad (4,0),\quad (0,4)\]The objective is:
\[x_1+x_2\]The constraint:
\[x_1+x_2\le 4\]has boundary:
\[x_1+x_2=4\]This boundary is also the optimal contour line.
Therefore, every point on the segment from $(4,0)$ to $(0,4)$ is optimal.
Optimal Set
The optimal set is:
\[\{(x_1,x_2)\mid x_1+x_2=4,\\ x_1\ge 0,\ x_2\ge 0\}\]Equivalently:
\[\{(t,4-t)\mid 0\le t\le 4\}\]The optimal value is:
\[z^*=4\]How to Detect Multiple Optima Graphically
Multiple optima occur when:
- the final objective contour line overlaps a boundary edge
- not just one point, but a segment remains feasible
In other words, the objective line and one active constraint line have the same slope.
Slope Test
For an objective contour:
\[c_1x_1+c_2x_2=k\]if $c_2\ne 0$, the slope is:
\[-\frac{c_1}{c_2}\]For a constraint boundary:
\[a_1x_1+a_2x_2=b\]if $a_2\ne 0$, the slope is:
\[-\frac{a_1}{a_2}\]If these slopes are equal and the boundary is the final supporting edge, multiple optima may occur.
Not Every Parallel Constraint Gives Multiple Optima
The objective line may be parallel to some constraint line that is not optimal.
Multiple optima occur only if the parallel edge is the final edge reached in the direction of improvement.
Algebraic Meaning
If $x$ and $y$ are two different optimal solutions, then every convex combination is also optimal:
\[\alpha x+(1-\alpha)y\]for:
\[0\le \alpha\le 1\]This happens because:
\[c^T(\alpha x+(1-\alpha)y)=\alpha c^Tx+(1-\alpha)c^Ty\]If both have value $z^$, then the combination also has value $z^$.
Reporting the Answer
When there are multiple optima, do not report only one point unless asked.
Report:
- one optimal point
- the optimal value
- the full set of optimal solutions if possible
Example:
\[z^*=4\]and all points:
\[(t,4-t),\qquad 0\le t\le 4\]are optimal.
Checklist
You understand multiple optima if you can:
- recognize when the objective line overlaps an edge
- compute the endpoints of the optimal edge
- express the whole optimal segment
- distinguish multiple optima from a unique vertex optimum
- report the optimal value clearly
See Also
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.