Inventory Control

We consider the problem where there is an amount of stock x_t at time t. You can perform the action to order a_t units of stock. Further the demand at time t is d_t. We assume d_t is independent over t. The change in the amount of stock follows the dynamic:

It is possible for x_t to be negative, which corresponds to backordered stock.

There is a cost for ordering a \in \mathbb R units of stock:

Note here c(a)=0 if a=0. There is a cost \kappa(x) for holding stock when x>0 or for unmet demand when x<0. Specifically

for positive constants h and p. If we consider the minimization problem over T time steps then we have a dynamic program:

The Bellman equation for this optimization problem is

Here y=x+a. If we define B(x) as follows

then (removing the subscript t for now) notice the above Bellman Equation becomes

There exists an explicit closed form solution to this optimization. Specifically there exists values s and S such that if the stock level goes below s then we order enough to have S units of stock. (We will show that S minimizes B(x) and s is such that B(s) = K+B(S).)

We give a proof for the case where K=0. This gives the necessary intuition for the more general case where K>0, which we subsequently discuss. (The formal argument is given in a series of exercises: Ex 2–Ex 4.)

S-Inventory control.

We consider the equation with K=0. Notice if B(x) is convex and B(x) \rightarrow\infty as |x|\rightarrow\infty then S, the minimum of B, is finite. Thus from it holds that:

Notice if B(x) is convex then relatively straight forward to check that L(x) is convex and L(x)\rightarrow\infty and |x| \rightarrow \infty (see Ex [sS:Ex0]). Also see the following Figure:

 

Figure: B(x) and L(x) for K=0.

Further, if, given the function L(x) above, we now update B(x) by taking

then it is straight-forward to check that the new function B is also convex and B(x)\rightarrow \infty as |x| \rightarrow\infty (see Ex [sS:Ex0]).

Thus (putting sub-script t back and noting that L_0(x) is convex) we see that the sequence of functions L_t(x) and B_t(x) are convex and that S_t, the minimum of B_t(x), defines the optimal control

  • If x < S_t then order so you have S_t units of stock, x+a = S_t .
  • If x \geq S_t then do nothing.

(s,S)-Inventory control.

We consider the equation with K>0. That is

In general B(x) will not be convex, but let’s assume it is for a moment in order to gain intuition. Again let S be the minimum of B(x). In this case the minimization over y >x above is solved at y=S if x\leq S and y=x if x>S. (Note if y=x in it is obviously better to take B(x) rather than B(x)+K.) So we have that

Now assuming B(x) is continuous then there will be a value of x=s < S such that This will be the point for which for x < s then K+B(S) is the minimum in , while for x \geq s, B(x) will be the minimum in . I.e. In this case the optimal control will be

For a convex function B(x) we plot L(x) +ca in Figure [sS:Fig2]. Notice that L(x) is clearly not convex. Essentially, the additional K term has introduced a “bump” of size K. So rather than assume convexity motivates, this motivates the idea of K-convexity.

 

Fig: B(x) and L(x)+cx for K>0.

Definition [K-convex] A function B is K-convex if

 

Remark. The definition above is not terribly intuitive. It can be shown that K-convexity means that for x<z the line segment from (z,B(z)+K) to (x,B(x)) does not intersect (y,B(y)) for any value of y between x and z. I.e. if you are standing at point (z,B(z)+K) you have an unobstructed view of (x,B(x)).

If B(x) is K-convex then we can show that is solved by , just like in the convex case. (This is Ex [sS:Ex1].) Further, we can show that if B(x) is K-convex then L(x) defined by is K-convex. (This is Ex [sS:Ex3]). Thus it can be shown that when we update B(x) according to the rule

then B is also K-convex. (This is Ex [sS:Ex2].)

Exercises

Ex 1. a) Given B(x) is convex and B(x) \rightarrow\infty for |x|\rightarrow\infty, show that

is such that L(x) is convex and L(x) \rightarrow\infty for |x|\rightarrow\infty.
b) Given L(x) is convex and L(x) \rightarrow\infty for |x|\rightarrow\infty, show that

is such that B(x) is convex and B(x) \rightarrow\infty for |x|\rightarrow\infty.

Ex 2. We let B(x) be K-convex, continuous with B(x) \rightarrow \infty as |x|\rightarrow\infty. Also let S= \min B(x) and s is the smallest number such that B(s) = B(S) + K.
a) Show that, for x < s, B(x) > B(S)+K .
(Hint: show B(x) > B(s).)
b) Show that for s < x<y, B(x) \leq B(y)+K.
(Hint: consider two cases x<S and x>S.)
c) Show that :

is solved by :

The following exercise establishes some properties of K-convex functions

Ex 3. Show that
a) The sum of K-convex functions is K-convex.
b) A convex function is K-convex.
c) If B(x) is K-convex then so is B(x+a) is K-convex.
d) The convex combination of K-convex functions is K-convex.
e) If B is K-convex then \mathbb E_Z [ B(x+ Z)] is K-convex.

Ex 4.  If we let

where S minimizes B(x) and s is the smallest value such that B(s) = K + B(S). We will show that L is K-convex:

Verifying by moving s through the following cases:
a) s \leq y-b
b) y-b <s < y and B(y) \geq B(s)
c) y-b <s < y and B(y) < B(s)
d) y < s < y+z
e) y+z <s

References.

The idea of K-convexity is due to Scarf. A full account of all the calculations above is given in the excellent text of Bertsekas.

Scarf, Herbert. “The optimality of (5, 5) policies in the dynamic inventory problem.” Optimal pricing, inflation, and the cost of price adjustment (1959).

Bertsekas, Dimitri P. Dynamic programming and optimal control. Vol. 1. No. 2. Belmont, MA: Athena scientific, 1995.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s