1
$\begingroup$

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.