1

Do not know how to approach this problem. The task is to convert the problem of mathematical programming:

$\max(\prod_{i=1}^nx_i)$

$\sum_{i=1}^na_ix_i\leq c$

$c \gt 0, a_i \gt 0$

into a problem of dynamic programming. Write down Bellman equations for this problem and find an optimal solution when

$n=3, a_1 = 1, a_2 = 2, a_3 = 3, c = 10$

I do not ask for a total solution, but I just need conceptual hints. By now I've tried $\lambda-method$ - used natural log of the value function, so that it transformed from a product to a sum of logs, then linearized them on their intervals, but all that resulted in a terrible linear programming problem, which I still didn't know how to convert to a dynamic programming problem.

Jacobian
  • 113

1 Answers1

0

Think of choosing the $x_i$'s sequentially, i.e., $x_1$ is chosen first, $x_2$ is chosen second, and followed by $x_3$. To make things simpler, let's assume that the $x_i$'s can only take integer values (otherwise we would have to discretize the continuous space).

In order to capture the constraint, at each stage we have a budget $B$, which takes values in $\{0, 1, \ldots, 10\}$ and for each of these values we compute the Value Function. Intuitively, for stage 3, think of budget $B$ as $(c - a_1 x_1 - a_2 x_2)$. Since the objective is increasing in $x_3$, $$V_3(B) = \begin{cases} \lfloor B/a_3 \rfloor\quad &\text{if}\ B \geq 0,\\ 0 &\text{otherwise.} \end{cases} $$ For stage 2, calculate $$ V_2(B) = \max_{0\leq x_2 \leq B}\{x_2 V_3(B - a_2 x_2)\}, $$ for all values of $B \in \{0, 1, \ldots, 10\}$.

Finally for stage 1, we can can calculate, $$ V_1(10) = \max_{0\leq x_1 \leq 10}\{x_1 V_2(10 - a_1 x_1)\}. $$

vdesai
  • 658
  • Thanks for a good advice! Actually, I did it almost in the same manner, just with minor differences. Since, we are maximizing the function we can exclude 0 from budget B - because if any of x's takes zero value, then the whole product becomes zero. And that sounds reasonable, especially if we convert the initial Value function to a log form, or to the sum of log(x1) + log(x2) + log(x3). And in this new from our new Value function reaches its optimum sumultaneously with the initial function – Jacobian Oct 29 '14 at 08:49
  • You are right we can exclude 0 from budget. Thanks for pointing it out. – vdesai Oct 29 '14 at 14:26