Is there an example of linear program in two variables that has infinite feasible region with an optimum solution of bounded cost?
Asked
Active
Viewed 3,676 times
0
-
What if the objective function is identically equals to zero, no matter what feasible solution is ...! – Red shoes Jun 28 '17 at 06:25
2 Answers
0
Hint:
Yes. One possible way is to think of how to make $(0,0)$ the optimal point if the feasible region is the first quadrant. That is think of one such objective function.
Siong Thye Goh
- 149,520
- 20
- 88
- 149
-
-
$$x-2y=(x-y)-y \leq 0,$$ hence that works. congrats.
Alternative solutions include $\min x $ subject to $x, y \geq 0$ or $\min x+y $ subject to $x, y \geq 0$ or even as suggested as Ashkan, just let the objective function be a constant.
– Siong Thye Goh Jun 28 '17 at 06:57 -
0
Let us consider the following linear program: $$\text{maximize } 5x+3y$$ $$5x-2y \geq 0$$ $$x+y \leq 7$$ $$x \leq 5$$ $$x,y \geq 0$$
The feasible region:
As you can see the feasible region is bounded by the following half spaces: $5x-2y \geq 0$, $x+y \leq 7$, $x \leq 5$ and $x,y \geq 0$
Taking out $x+y \leq 7$ and ($5x-2y \geq 0$ or $x \leq 5$) from the system of linear inequalities gives an infinite feasible region with the pair $(0,0)$ as a minimum feasible solution. Thus turning the initial problem to a minimum linear program and taking out $x+y \leq 7$ and ($5x-2y \geq 0$ or $x \leq 5$) will give a linear program in two variables that has infinite feasible region with an optimum solution of bounded cost.
Ayoub Falah
- 549