$Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$.

Question

Consider the linear programming problem:

Which is correct ?

(A) Set of feasible solutions is empty.

(B) Set of feasible solution is non-empty but there are no optimal solution.

(C) Optimal value is attained at $(0,5/4)$.

(D) Optimal value is attained at $(5/3,0)$.

I have no idea about this problem..I tried to draw the figure but I did not get any region , as there are only one constraint is given..I could not deal with only one constraint..How I solve this?

Use corner point theorem? Or maybe sometimes solution exist along a whole side. — Someone, May 12 '15 at 18:39
What is corner point theorem ?? Please state..I don't know it.. — Empty, May 12 '15 at 18:40
It's obvious that the objective function can assume arbitrarily large negative values on the feasible set; whence there is no minimum: Choose $x=y=10^6$; then $\phi(x,y)=-7\cdot 10^6$. — Christian Blatter, May 12 '15 at 19:43

Will Jagy · Accepted Answer · 2015-05-12T19:12:47.080

2

buy some graph paper. It has little squares. One thing that has been confirmed on MSE is that a student who relies on software to draw diagrams will never learn to visualize, neither in two dimensions nor three. It is, of course, slower to do it yourself.

Next, evaluate your objective function $-2x-5y$ at some integer points in the region, $(1,0), $ $(0,1), $ $(2,0), $ $(1,1), $ $(0,2), $

enter image description here

edited May 12 '15 at 19:12

answered May 12 '15 at 18:42

Will Jagy

139,541

I got that the set of all feasible solutions in non-empty..but why there are no optimal solution ? – Empty May 13 '15 at 06:48
@S.Panja-1729, if you don't know yet, evaluate your objective function at even more integer points, maybe $(2,2),$ $(3,3),$ $(4,4),$ $(5,5).$ If you cannot understand the question in symbols, you need to plug in some actual numbers and see what happens. You, not me. – Will Jagy May 13 '15 at 18:20
@S.Panja-1729, I looked at your profile, you've given a number of answers, some of which are pretty good. I do not understand why you had trouble drawing this picture, or continue to have trouble seeing how the objective function $-2x-5y$ behaves in different parts of the region given. – Will Jagy May 13 '15 at 18:34

score 0 · Answer 2 · answered May 12 '15 at 19:14

Consider a 2-d surface. $x\ge 0$ means only points to the left of the origin, $y\ge 0$ means only points to the upwards of origin. So, these two conditions together mean only points in the first quadrant. Now draw the line $3x+4y=5$. This line divides the first quadrant (and the entire space) into two regions, we want to know $3x+4y\ge 5$ refers to which region. Pick any point say (2,2). Clearly, this satisfies $3x+4y\ge 5$, so this inequality refers to the region where this point lies. Now you have a region bounded by three constraints. Now just find out where does the line $z=-2x-5y$ get minimised in this region.

$Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$.

2 Answers2