This is straight from the book: Optimization Methods in Finance.
Overview
The question is about how the transition state works from the example provided in the book. I attempted to trace through it myself but came across a contradiction.
In Chapter 13, we come across an example similar to the Knapsack Problem. The main difference is we can make "multiple investments" in each project (instead of simple binary 1-0 choice)
The example problem
We want to optimize between 4 projects with total budget of $14 (values in millions)
$$ Maximize \;\; 11x_1 + 8x_2 + 6x_3 + 4x_4 \\ Subject \;to \;\; 7x_1 + 5x_2 + 4x_3 + 3x_4 <= 14 \\ x_j >= 0, \; j = 1..4$$
Note that $y_j$ will be the cost (constraint) and $p_j$ will be the profit (what we want to maximize) as we proceed.
The book proceeds to formulate the dynamic programming approach with four stages: $i=1,2,3,4$ where the fourth stage will have states $(4,0), (4,3), (4,6), (4,9), (4,12)$ corresponding to 0, 1, 2, 3, and 4 investments in the fourth project.
The decision to be made at stage $i$ is the number of times one invests in the investment opportunity $i$. Therefore, for state $(i,j)$, the decision set is given by:
$$ S(i,j) = \{d|\frac{j}{y_i} \geq d \} $$ where d is a non-negative integer
The transition state is : $$ T((i, j), d) = (i + 1, j - y_i* d) $$
My issue and contradiction
Now, let us say we have a state at stage 3: $(i,j)$ is $(3,12)$ Since investment 3 has a cost $y_3=4$, it means $(3,12)$ is a state where 4 investments are made in investment 3.
Calculating our decision set: $$S(3, 12) = \{d\|\frac{12}{4} \geq d\} \\S(3,12) = \{0, 1, 2, 3\}$$
However, since we are currently at \$12, that means we should only have \$2 left to spend.
Applying the transition function:
$$T(3,12), 0) = (4, 12 - 4*0)\\T(3,12), 0) = (4, 12)$$ How is this feasible? Also for the following:
$$T(3,12), 1) = (4, 12 - 4*1) \\T(3,12), 1) = (4,8)$$ This is a state that does not exist, since it was provided in the book that the possible states for stage 4 is $(4, 0), (4,3), (4,6), (4,9), (4,12)$
Pictures below for full problem:
