Setting up the Bellman equations for dynamic programming

Question

I have the following question I want to understand.

The owner of a chain of three grocery stores has purchased five crates of fresh strawberries. The estimated probability distribution of potential sales of the strawberries before spoilage differs among the three stores. Therefore, the owner wants to know how to allocate five crates to the three stores to maximize expected profit. For administrative reasons, the owner does not wish to split crates between stores. However, he is willing to distribute no crates to any of his stores. The table below gives the estimated expected profit at each store when it is allocated various numbers of crates. Use dynamic programming to determine how many of the five crates should be assigned to each of the three stores to maximize the total expected profit. Start by giving the Bellman equations. $$ \begin{array}{c|ccc} &&\text{Stores}\\ \text{Crates} & 1 & 2 & 3 \\ \hline 0 & 0 & 0 & 0 \\ 1 & 5 & 6 & 4 \\ 2 & 9 & 11 & 9 \\ 3 & 14 & 15 & 13 \\ 4 & 17 & 19 & 18 \\ 5 & 21 & 22 & 20 \end{array} $$

Define $x_i$ to be the number of crates allocated to store $i$, and let $p_i(x_i)$ provide the expected profit from allocating $x_i$ crates to store $i$. Let $s_i$ denote the aggregated number of crates to be available for stores $i,i+1,i+2$ (for as far they exists). So $s_3$ denotes the number of crates for only store $3$; and $s_1$ denotes the number of crates for stores $1,2$ and $3$ together.

Per the solution: The Bellman equations (backward recursion) are now given by: $$\begin{align*} &f_i(s_i) = \max_{0 \leq x_i \leq s_i} [p_i(x_i) + f_{i+1}(s_i - x_i)] \text{ for } i=1,2,3 \\ & f_4(s_4)=0\end{align*}$$

I understand the $p_i(x_i)$ part. As that is the direct profit associated with taking decision $x_i$. My problem is with the $s_i - x_i$ part. Why does this appear in the recursion formula?

Thanks in advance.

Answer 1

$f_1(s_1)$ is the value of having $s_1$ crates left to assign to store 1. After assigning $x_1$ crates to store 1, the owner has $s_2 = s_1 - x_1$ crates left for store 2. Etc.

If this is too simplistic please let me know and I'll try to be more articulate.

Answer 2

Perhaps the maximum being taken over $x_i$ that satisfy $0 \leq x_i \leq s_i$ will help you understand. $s_i$ is the number of crates available to all stores whose index is $\geq i$. You can assign any number of crates $x_i$ to store $i$, as long as $0 \leq x_i \leq s_i$. And then you will have $s_i - x_i$ crates remaining to assign to the rest of the stores, starting at index $i+1$. The notation makes it so that the input to $f_i$ is always called $s_i$, and so this is how the $s_i$ are defined in terms of $s_{i-1}$ and $x_{i-1}$. Maybe that's the way to see how the recursive formula arises: Basically, whatever you pass into $f_i$ is called $s_i$, even though technically the $s_i$ are not explicitly defined recursively in your equations. And, deducing from the equations, $s_i$ is always defined as $s_{i-1} - x_{i-1}$, except for $i = 1$.