Introduction

An Inventory system is a storage device which from time to time receives inputs, and from which output is removed. Usually the manager can control the inputs (when?, how much?) but there are situations where output is subject to control (water storage systems are the most common example). In either case there are associated costs and profits which must be optimized over some period. The difficulty of the decision lies in the interpretation af the term some period. Very frequently the process has no obvious point in time at which it will terminate and some mathematical device is required which will sum all future costs. Dynamic Programming is such a device, but in an infinite time period any replenishment policy will yield infite costs. There are two ways of keeping costs finite; the first is to apply a discount factor to future costs and the second is to consider the long run average costs'per month. Realistically the discount factor must be close to one and the two apparoaches yield very similar policies in practice.

The Warehouse Problem

In what follows we will assume that decisions about replenishment are to be made once a month, and that there are costs associated with the quantity ordered (or produced). We also assume an income associated with sales and for costs associated with holding stocks or failure to meet demand. As an example consider the problem of the owner of a warehouseof capacity H who has a stock of s H items. Suppose that in each of the months to come he can buy unlimited quantities or sell any

---

*) Associate Professor, Case Institute of Technology.

amount up to his current inventory; the cost in month i being a and the sales price pi. Let his planning horizon be n months and assume that replenishment ordered in each month is delivered after the sales have taken place. The problem of hoy f much to buy and sell can be formulated as a linear programming problem as follows.

Let xt 0, y% 0(i=1,2,...,n)be quantities bought and sold in
month i, so the net profit P is given by:

However xi, y% and subject to the constraints:

T
For r=l,2,••., n s+ 2 (xi—yi) H (capacity limitation)

r-1
For r=1,2,...,n s+2 (xi—yi) —xr 0 (no negative stocks).

Thus we have a problem in 2n variables with 2n constraints, and for
n = 12, corresponding to a horizon of one year, we have a formidable
calculation.

Let us define ft{u) to be the maximum profil; starting with a stock
of u in month {n — t+\) and continuing for t months until month n.
Then if we buy x and sell y in month n we have

where the maximum is over all x and y which satisfy

It is easy enough to see that the optimal values of x, y are one of the
following: (See figure)

Since pn > 0, cn > 0 we see
x — 0, y ■— u and fi(u) = ppnu.

Now if in month (n — t+\) we start with u, buy x and sell y we start the following month with a stock of u'=u-\-x—y. Hence

where the maximum is over all x, y satisfying the previous restrictions.
If we know ft-\{u) and it is linear, then the fuction to be maximized is
linear and finding ft-i(u) is comparitively simple.

Now, we know fi(u) and it is linear so we can find h{u). Let us
assume ft-i{u) is linear in u, say

Then ft(u) has one of the forms below:

Thus in all cases ft(u) is a linear function of u, and we have a complete
system of recursive calculation. A numerical example is given in reference
4, pages 274-278.

More general problems do not assume that the system is deterministic; usually instead of unlimited demand, we consider demand in any month to be subject to a probability distribution and we study expected costs (or profits). Suppose that we made decisions every month and that if we start with a stock s and order q = S — s, then the expected costs during the month of holding inventory plus the penalty costs of failing to meet demand are f (s,S). Let the procurement cost be k + cq if a > 0 and zero if q = 0. We wish to find a policy for determining q, or what amounts to the same thing, for determining S.

Let f\(s) be the minimum expected cost over the month following the
decision.

Thus f\(s) can be determined (tabulated!) with comparitive ease.

Now assume that the density function for demand during any month is ø (x), independent of the previous month's demand. Assume also that failure to meet a demand results in a lost sale. Let ft(s) be the minimum expected cost over t months. We obtain the following equation for ft(s) in terms of ft-i(s).

[We assume that a total of q -\- s = .S becomes available during the
current month].

Starting with fi(s) we can obtain [2, h, ■ • • • successively. So long as t remains finite we can obtain the optimal procurement policy. If t becomes infinite both sides of the equation tend to infinity for all policies. To avoid this we can argue that next month's costs should be discounted by a factor a = 1/(1 + i) where i is the interest per month. We then define ft(s) as the minimum discounted costs and obtain:

It can be shown that so long as 0 a<l the sequence of functions /1, h, • • ■ ■ converge to a function f(s) and moreover / is independent of /1; further,./ is the unique solution of the equation obtained by dropping the subscripts in the last equation. Equations of this type have been discussed extensively. (See references 1, 2, 4).

The alternative to using a discount factor is to study the asymptotic form of ft(s). It can be shown that for any given procurement policy the total costs over t months have the asymptotic form v(s) + gt where v and g depend on the policy and g is independent of s. We woud choose the policy to minimize g - the long run average cost.

We have

Thus

Now a given policy expresses S as a function of s so in the theory we van solve this equation for v(s) and g. Actually we can only determine v(s) up to an additive constant. (If v — u(s) is a solution then clearly so is v = u{s) + c). However we are mostly interested in g and we may assume for example that v(Q) ~ 0. In practice some form of numerical calculation is required and the following system due to Howard is suggested. (Reference3).

Let the units of sbeso defined that s takes the values of 0, 1, 2, .. „ k. The effect of a procurement decision is to change s to s with a known probability. Thus if p_x is the probability of demand for x and our policy calls for procurement of S — s, the probability of s' is ps-s\ (Of course S may be a function of s).

Let pf. be the probability, that if we use policy A, a stock of i at the end of one month will become a stock of ; at the end of the next month Let KAK^A be the expected costs, including procurement costs, incurred during a. month starting with stock i; let fi{n) be the minimum costs over n months. Finally let f^A(n) be the costs associated with policy A.

Then

a:

and

(2)

where the minimum is over all policies.

Howard shows that fA(n) has the asymptotic form

(3)

and it is clear that the optimal policy is the one which minimizes gA
(the long run average cost).

If we insert (3) in (1) we have

(4)

or

From (4) we may determine the vf (up to an additive constant) and gA.
As we are primarily interested in gA we may arbitrarily set vA = 0 and
solve (4) for vA, ..., vf and gA. Once this is done we can search for
a better policy than A as follows:

Let

The minimum is achieved for that policy B which minimizes
k
Kf + 2 pf. vf. Howard shows that if B = A for all i, then policy A

is optimal, in the sense that gAgegAgc for any C-jJr-4. If B =\=A we can
solve equations (4) for vB and gB and repeat the minimization procedure.If
at any stage there is a value of i for which

we keep policy A for that i, even if some other policy B yields equality.
It may be shown that this process must converge in the sense that we
must eventually find Bee A.

In many cases sales demand has a seasonable pattern. This may be included in the model by writing pp^A _t for the probability that using policy A a stock of i at the start of month t becomes ;' at the start of month t+ 1, (mod 12). Of course in place of Kf and v^A we have KAK^A and<. (*=l, 2, .... 12)

We now define the following matrices and vectors:

(k + 1 sided square matrix).

(column vector),

(column vector),

(column vector).

In place of equations (4) we have

(5)

(6)

We can substitute for vvA2 from (6) into the last of (5) and then substitute
for vvA± in the next equation of (5) and so on, until we obtain:

(7)

Now since each of PAPA (t =/,..., 12) is a stochastic matrix with rows
adding to one, so are the products PAPA PAPA ... . Pf2. As gA is a column
vector of indentical elements, gA, we see that

Thus (7) may be written

(8)

where

and

Equation (8) has exactly the same form as (4). It may be solved for vA
and gA provided we first set vvAt =0. Once vA is known, t^9 vvAt ...
vA may be found by successive substitutions in equations (6) and (5).

The procedure for finding the optimizing policy is carried out by
successive improvements on policy A, using the technique described for
the non-seasonal case.

References

1. Arrow, K. J., Karlin, S.; Scarf, H. Studies in the Methematical Theory of Inventory
Control; Stanford University Press, 1958.

2. Bellman, R., Dynamic Programming; Princeton University Press, 1957.

3. Howard R., Dynamic Programming and Markov Processes; MIT Press and John
Wiley, New York, 1960.

4. Sasieni, M. W.; Yaspan, A.; Friedman, L.; Operations Research: Methods and
Problems; John Wiley, New York, 1959.
(also available in German, Physica-Verlag, Rudolf Liebing KG, Wiirzburg, 1962).

5. Hadley, C, Within, T. M., Analysis of Inventory Systems. Prentice-Hall, Englewood
Cliffs, New Jersey, 1963.

6. Wagner H., Statistical Management of Inventory Systems. John Wiley. New York,
1963.