The following question was asked in an exam:
Consider the problem:
Maximize $2y_1+3y_2+5y_3+4y_4$
subject to
$y_1+y_2\leq 1,$ $y_2+y_3\leq 1,$
$y_4+y_1\leq 1,$ $y_3+y_4\leq 1$ and $y_i\geq 0$ for i=1,2,3,4.
Then the optimum value is
1. equal to 8
2. between 8 and 9
3. greater than or equal to 7
4. less than or equal to 7
I solved the above problem by the usual simplex method and got the optimal value to be 7. Now, I am just curious to know if there's any other simpler and faster method to solve such problems in competitive exams where time is a constraint.
Thank you in advance!
Asked
Active
Viewed 328 times
1
shwetha
- 695
2 Answers
1
You could let $z_1=y_1+y_2$, $z_2=y_2+y_3$ and $z_3=y_3+y_4$. Then the problem becomes:
Minimise $2z_1+z_2+4z_3$ subject to $z_1\leq 1$, $z_2\leq 1$, $z_3\leq 1$, $z_1-z_2+z_3\leq 1$,
Then, by inspection $z_1=z_2=z_3=1$ satisfies the constraints and attains the maximum.
Michael Hartley
- 2,498
-
Thank you so much for your answer! But what I don't understand is how this maximization problem became a minimization problem?! – shwetha Aug 04 '17 at 05:33
-
Sorry, it's a typo! :-P – Michael Hartley Aug 08 '17 at 05:56
0
The answer is $D$.
Express it as: $$2y_1+3y_2+5y_3+4y_4=2(\underbrace{y_1+y_2}_{\le 1})+(\underbrace{y_2+y_3}_{\le 1})+4(\underbrace{y_3+y_4}_{\le 1})\le7.$$ Equality occurs when $(y_1,y_2,y_3,y_4)=(1,0,1,0); (\frac12,\frac12,\frac12,\frac12);(0,1,0,1); etc.$
farruhota
- 31,482