Consider the linear programming problem minimize c1x + c2y subject to x + y ? 4
ID: 3710714 • Letter: C
Question
Consider the linear programming problem minimize c1x + c2y subject to x + y ? 4 x + 3y ? 6 x ? 0, y ? 0 where c1 and c2 are some real numbers not both equal to zero.
(a) Give an example of the coefficient values c1 and c2 for which the problem has a unique optimal solution.
(b) Give an example of the coefficient values c1 and c2 for which the problem has infinitely many optimal solutions.
(c) Give an example of the coefficient values c1 and c2 for which the problem does not have an optimal solution.
Explanation / Answer
x+y >= 4x+3y >= 6x >=0
y>=0
so first find out all the constraint equations
x+y>=0; 4x+3y>=0; x>=0; y>=0; 3x+2y<=0; 5x-y<=0;2x-3y<=0
now for unique optimal solution , we need all critical points to be intersection points. When you plot the curves and find the optimal region, we see that the intersection of all regions gives only the region between y=0 and y=5x with intersection at origin.
so now all you have to do is put c1 and c2 such that :
1. for unique solution: the 3 lines intersect. eq. c1=5, c2=6
2. for infinite solution : the line should be coincident on any one of these lines: so c1= 5 c2=-1;
3. for no solution: the lines should be parallel which is not possible in this case since the constraint has no offset. so c1x+c2y=0 can only be an intersecting line or a conincident line.
had we had a constraint line like 5x-2=y, we could have got no solution case with c1=5 and c2=-1.