$ 5r + 4s + 3t + 6u = 100, \:\: r \ge s \ge t \ge u \ge 0 $ maximum and minimum possible of $r + s + t + u$?

Question

We have $$ 5r + 4s + 3t + 6u = 100, \:\: r \ge s \ge t \ge u \ge 0 $$ What is the sum of the maximum and minimum possible of $r + s + t + u$?

---

Attempt:

Assume that $r'+s'+t'+u'$ is the maximum. Now if $u > 0$, then we can have $$ (r' + K) + s' + t' + (u' - \frac{5}{6} K), \:\: K > 0 $$ is bigger than the claimed maximum, with ($r=r'+K, s=s', t=t', u = u' - \frac{5}{6}K$). We have a contradiction. So $u'=0$.

Now see $$ 5r + 4s + 3t = 100 $$

Similarly, let $r^{*} + s^{*} + u^{*}$ maximum. Then

$$ r^{*} + (s^{*} - \frac{3}{4}C) + (t^{*} + C), \:\: C > 0 $$

is bigger then the claimed maximum, provided that $s = s^{*} -(3/4)C \ge t = t^{*} + C$ with $$ C \le \frac{4}{7}(s^{*}-t^{*})$$

After this I have no idea.

---

Answer 1

Okay, so i got the constraints wrong. In second attempt, we introduce the slack variables $a,b,c \ge 0$, where $u \ge 0, t = u+a \ge u, s= t+b \ge t, r = s+c \ge s$. Now we reformulate the problem. We have: $$\max (4u+3a+2b+c)$$ $$\text{subject to }\quad 18u+12a+9b+5c = 100 ,\quad a,b,c,u\ge0$$

now we replace the constraint into the objective $c = \frac{100-18u-12a-9b}{5} \ge 0$ and thus $\max (4u+3a+2b+\frac{100-18u-12a-9b}{5}) = \max(\frac{100+2u-12a+b}{5})$. Since this i linear program and the line is monotone, so the max or min is at the end or beginning of the intervals. we consider extreme cases. since $c \ge 0$ one of these cases must be the solution $(b = 100/9 , a=c=u=0)$ or $(b = 0, a=100/12,c=u=0)$ or $(b=a=0 ,c=100/5,u=0)$ or $(b =a=c=0 , u=100/18)$. By inspection we get $(b = 0, a=100/12,c=u=0)$ is indeed the f***ing solution which is equal to $\frac{100+100/4}{5}=25$.

Now back for the minimum, we have $$\min (4u+3a+2b+c)$$ $$\text{subject to }\quad 18u+12a+9b+5c = 100 ,\quad a,b,c,u\ge0$$

by the same chain of reasoning we get that in this case $(b=a=0 ,c=100/5,u=0)$ is our fortunate candidate and the answer is $c=100/5=20$.

Answer 2

Hint: We get $$20\le r+s+t+u\le 25$$, where the minum will be attained for $$r=20,s=t=u=0$$ and the maximum by $$r=s=t=\frac{25}{3},u=0$$

Answer 3

Just to elaborate on one of the bounds in @Dr. Sonnhard Graubner's answer. Using Chebyshev's inequality, because $5>4>3$ and $r\geq s \geq t$ $$100=5r + 4s + 3t + 6u\geq \frac{5+4+3}{3}\cdot(r+s+t) + 6u=\\ 4\cdot(r+s+t) + 6u\geq 4\cdot(r+s+t) + 4u$$ and $$r+s+t+u\leq 25$$

Answer 4

Continuing my answer, thnks to Dr.Sonhard's hint.

If
$$ s^{*} > t^{*} $$ then there is C such that $r^{*},s^{*},t^{*}$ does not sum to maximum. So it must be that $s^{*}=t^{*}$.

Now we have $$ 5r^{*} +7s^{*}=100 $$

Similarly, $$ (r^{*} + C) + (s^{*} - (5/7) C) $$ Will be bigger than the claimed. With $$ C \ge (7/12)(s^{*}-r^{*}) $$ Thus we must have also $r^{*}=s^{*}$.

So the solution is $r=s=t=25/3$, for the maximum case.