2
$\begingroup$

In the following inventory problem, there are $N$ units of inventory available at the beginning of the time horizon $T$. Each day $t\in T$, it is possible to sell one unit of the inventory at price $c_t$. The problem is find the optimal sequence of days where the units are sold, in order to maximize revenues.

It is obvious that the optimal sequence of days are the $N$ days with largest price $c_t$, however the point of the exercise is to use dynamic programming with the following (backwards) recursive equation: $$ f(t,n) = \max\left\{ f(t+1,n), f(t+1,n-1)+c_t \right\} $$ The equation states that on day $t$ with $n$ units of inventory, the optimal revenue is the maximum value between:

  • $f(t+1,n)$, in which case the inventory is kept constant
  • $f(t+1,n-1)+c_t$, in which case one unit is sold at price $c_t$, and inventory decreases by one unit

The recursive equation can be initialized with $f(|T|+1,n)=0$ (the items of the inventory cannot be sold after the last day of the time horizon), and the optimal strategy consists in selling one unit on day $t$ if $$c_t \ge f(t,n)-f(t,n-1)$$ i.e. if the marginal revenue of one unit of inventory is smaller than the price $c_t$.

If I decide to solve this problem with linear programming, is it possible to extract the value $f(t,n)-f(t,n-1)$ somehow? Indeed, I understand that this value is of interest because it can be used to find the optimal trajectory, but also because it represents the future revenues that can be expected from one unit of inventory at a given time, at a given level. In other words, it is a measure of the "value" of the inventory. If the problem becomes more complex with side constraints, or that dynamic programming is no longer an option for some reason, how can I still compute this indicator? Is it hidden somewhere in the equivalent linear program?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you asking about finding $f(t,n)-f(t,n-1)$ for all $n$ or just for the optimal value of $n$ entering time $t?$ $\endgroup$ Commented Oct 14, 2024 at 15:51
  • $\begingroup$ To begin with, just for the optimal value of $n$ entering time $t$. Does it make a difference? I am curious if you have something in mind for all $n$. $\endgroup$ Commented Oct 14, 2024 at 21:10
  • $\begingroup$ That depends on whether you are willing to solve a modified LP model for each combination of $t$ and $n,$ or for each $t$ given the optimal value of $n$ at that time, or only solve one LP model total (in which case I'm not sure you can get an answer). $\endgroup$ Commented Oct 14, 2024 at 22:09
  • $\begingroup$ I am willing to solve a modified LP model each combination. $\endgroup$ Commented Oct 15, 2024 at 6:21

1 Answer 1

Reset to default
1
$\begingroup$

You can compute $f(t, n)$ by solving the following linear program: \begin{alignat*}{1} \max\ \sum_{\tau=t}^{T} & c_{\tau}x_{\tau}\\ \textrm{s.t. } & y_{t}=n\\ y_{\tau} & =y_{\tau-1}-x_{\tau-1}\quad\tau=t+1,\dots,T+1\\ y_{\tau} & \ge0\quad\forall\tau\\ x_{\tau} & \in[0,1]\quad\forall\tau \end{alignat*}

Here $x_t$ is what you sell in period $t$ and $y_t$ is the inventory at the start of period $t.$ We include $y_{T+1}$ just to ensure that you do not end the time horizon with a negative inventory position.

If you are willing to solve a gaggle of these LPs, you can compute $f(t,n)$ for all relevant combinations of $t$ and $n$ and compute $f(t,n)-f(t,n-1)$ from those results.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.