In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
$\begingroup$
$\endgroup$
1
$\begingroup$
$\endgroup$
For an example, consider the constraints $x \ge 0, y \ge 0$ and $y_1 \le-px+q$. The thing you have to maximise is $I=ax+by_2$, so $y_2=\frac{I}{b}-\frac{a}{b}x$, and we have to maximise the $y$-intercept of $y_2$. The optimal $y_2$ will intercept $y_1$ at $(0,\frac{I}{b})$ or $y_2=y_1$ for all $x$, which would give infinite optimal solutions, more than the $2$ you alluded to.
1
$\begingroup$
$\endgroup$
Not True.
\begin{align} \min &\qquad x+y+z\\ s.t.\\ x+y+z&\geq1\\ x,y,z&\in \mathbb{R}^+ \end{align} We have $(1,0,0)$,$(0,1,0)$,$(0,0,1)$.
