Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a weird optimization problem I recently came across which I cannot solve.

Suppose we start off with an empty container of M&Ms. We take and add M&Ms to the container every year for $n$ years. The number of M&Ms I take out each year, $B$, is always the same (think of it as a parameter). The number added in year $i$, $A(i)$, is known (think of it as data).

If $A(i) - B < 0$, I have an M&M "bank" I can go to cover my losses and so I can keep operating even with a deficit. We let $D(0)$ represent the initial amount in the bank and $D(i)$ denote the amount in the bank in year $i$, where we calculate $D(i)$ as: $D(i) = D(i-1) + A(i) - B$, if $A(i) - B <= 0$; $D(i) = \min(D(0), D(i-1) + A (i) - B)$, if $A(i) - B > 0$ (in the latter case, I throw away any extra M&Ms left over after I cover my debt to the bank).

The problem is: "Find the maximum value of $B$ such that $D(n) = D(0)$" (i.e., what is the maximum number of M&Ms I can take out every year, so I have no deficit with the bank at the end of the $n$ years?).

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Since you can't store extra M&Ms, and you can't be in debt to the bank at the end, your constraint is basically that, for each year $i$, there have to be more M&Ms going in than M&Ms going out from year $i$ through year $n$. This gives rise to the following linear programming formulation of your problem:

$$ \begin{align} \text{Maximize } &B \\ \text{subject to } &\sum_{k=i}^n (A_i - B) \geq 0, \text{ for each }i \in \{1,2,\ldots,n\}, \\ &B \geq 0. \end{align} $$ This problem is simple enough that you don't even need an LP solver. Rewrite the constraint as $$\begin{align} &\sum_{k=i}^n A_i \geq B(n-i+1), \text{ or } \\ &B \leq \frac{1}{n-i+1}\sum_{k=i}^n A_i. \end{align}$$ Thus the solution is $$B = \min_{1 \leq i \leq n} \left\{\frac{1}{n-i+1}\sum_{k=i}^n A_i\right\}.$$ If $B$ is required to be an integer, then you'll need to round this expression down to the nearest integer.

share|improve this answer
    
Thank you very much Professor Spivey. My background does not include linear programming and I would never have seen this solution! I appreciate your time and work greatly!! –  Matt Brenneman Nov 19 '11 at 13:54
    
@MattBrenneman: You're welcome. :) –  Mike Spivey Nov 20 '11 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.