2. PROBLEM DESCRIPTION

Recall that we consider a single-commodity system with positive or negative demand. Assume that items that are returned are immediately available for resale. All lead times are assumed to be zero, the production/scrapping and borrowing/storage costs are assumed to be linear, and the unmet demand is backlogged. The cost of inventory held or backlogged (negative inventory) is modeled as a convex function. The sequence of events is as follows. At the beginning of the period, a decision-maker decides how much of the product to order or to scrap (at a loss) to meet demand. In addition, the decision-maker simultaneously decides how much inventory to borrow from or store to a (potentially external) secondary source. During the period, demand is realized and holding costs are accrued on the surplus or backlogged inventory. At the end of the period, borrowed or stored material is returned and the process continues. Note that since borrowed or stored inventory is returned the next period, holding costs are accrued but the inventory level of the next period is not affected. The objective is to minimize the total expected discounted cost over a finite horizon or the discounted or average cost over an infinite horizon. Let the following hold:

• β ∈ (0,1] is the discount factor.
• Positive numbers c₊ and c₋ are the per unit ordering and scrapping costs, respectively.
• Positive numbers e₊ and e₋ are the per unit borrowing and storage costs, respectively.
• h(·) denotes the holding/backordering cost per period; convex, nonnegative function with finite values, and h(x) → ∞ as |x| → ∞.
• {D_n,n ≥ 0} is a sequence of i.i.d. random variables, where D_n represents demand in the nth period. We assume that
  
  for all
  
  , where D is a random variable with the same distribution as D_n. We note that this assumption and the assumed properties of the function h imply that
  
  .

For

, let a⁺ and a⁻ be the positive and negative parts of a, respectively; a⁺ = max{a,0} and a⁻ = max{−a,0}. Let X_n be the inventory position at period n and let the ordered pair (Y_n,Z_n) be the amount ordered/scrapped and the amount borrowed/stored in this period. Denote the one-step cost function by C(x,(a,b)):

We model the decision scenario as a Markov decision process (see, e.g., Bertsekas [5,6], Dynkin and Yushkevich [14], Feinberg and Shwartz [17], Puterman [33], or Ross [36]). A general policy can be randomized and depend on the history of the inventory levels and decisions. A policy is called stationary if decisions are nonrandomized and depend only on the current inventory level; that is, a stationary policy is defined by a measurable function that maps the inventory position (the state space,

) to the set of potential actions (the action space). A Markov policy is defined as a sequence d₀,d₁,…, where d_n(x) is the decision that should be selected if the inventory level is x at step n. In our model, if an action (a,b) is chosen in state x, the cost C(x,(a,b)) is accrued, the system moves to state x + a − D, and this process continues. As was alluded to earlier, since the amount that is borrowed or stored is returned the next period, it has no effect on the subsequent inventory position. For a policy π and for an initial inventory level x, we define

Equations (2.2), (2.3), and (2.4) define the N-stage expected discounted cost, the infinite horizon expected discounted cost, and the long-run average expected cost, respectively. In the finite horizon problem, only the portion of the policy required for the time horizon is used. In each case, we define the optimal values

where Π is the set of all policies. A policy φ is called optimal for the respective criterion if its value v_N,β^φ(x), v_β^φ(x), or w^φ(x) corresponds to the value on the right-hand side of (2.5), (2.6), or (2.7), respectively, for all

.

We remark that our assumptions also imply that v_β(x) < ∞ for all

. Indeed, the assumptions on the holding cost h imply that there is a point x* such that

. Without loss of generality, we assume that x* = 0 and h(0) = 0. Consider a policy φ that never borrows/stores and always orders/scraps in a way that the inventory level before the demand is known is zero. Then

3. FINITE HORIZON DISCOUNTED COST OPTIMAL POLICIES

In this section, we study the finite horizon problem. Since it is fixed throughout the section, we suppress β whenever possible. It is well known that if a solution to the following finite horizon optimality equations (FHOEs) exist, that solution is equal to v_n (componentwise) as defined in (2.5). Let v₀ ≡ 0 and for n = 1,2,…,

where

We observe that an equivalent system is

where

This observation leads to an algorithm for solving the proposed problem. First, solve (3.4) for g*. Using this function, find the optimal ordering/scrapping policy by solving (3.3). Finally, using g* evaluated at y + a, find the optimal borrowing/storage decision b. The following lemma provides preliminary results on v_n and g*.

Lemma 3.1:

Proof: For any convex function k(y) and random variable X such that

is also convex in y (cf. Bertsekas [6, Lemma4.2.1]). Since h is convex, the function inside the infimum in (3.4) is jointly convex in y and b. Thus, applying Proposition B-4 of Heyman and Sobel [27], we have that g*(y) is convex in y. The fact that g*(y) → ∞ as |y| → ∞ follows from the assumption that h(y) → ∞ as |y| → ∞.

We prove parts (i) and (ii) by induction. By assumption, v₀ is convex. Assume that convexity holds for n − 1. Since we have just shown that g* is convex, the function inside the infimum in (3.3) is jointly convex in y and a. Again applying Proposition B-4 of Heyman and Sobel [27] yields that v_n(y) is convex in y. Moreover, note that v_n(y) → ∞ as |y| → ∞ is implied by the fact that g*(y) → ∞ as |y| → ∞ and the result is proven.

To verify (iii), we observe that for each y the function of b on the right-hand side of (3.4) is convex in

and, therefore, continuous. In addition, this function tends to ∞ as |b| → ∞. This is also true for (3.3) with the variable a instead of b. █

For a function f (y), let d⁻f (y)/dy denote the left-hand derivative of f. This derivative exists if f is convex. In light of the results of Lemma 3.1, the infimums in (3.3) and (3.4) can be replaced by minimums. The minimum can be computed by finding the place at which the left-hand derivative changes sign. We, thus, can define the following quantities for n = 1,2,…:

where the supremum (infimum) of the empty set is taken to be −∞ (∞). Although the values defined in (3.5)–(3.8) depend on β, to keep the notation simple, we continue to suppress this dependence in the current section. For example, the full notation for L_n^p is L_n,β^p.

We remark that Eqs. (8-58a) and (8-58b) of Heyman and Sobel [27] are similar to our (3.5)–(3.12), but only one point where the appropriate convex functions achieve their minimums was considered in [27]. Here, we consider the intervals of all possible solutions. Obviously, L_n^p ≤ L_n^p, U_n^p ≤ U_n^p, L^b ≤ L^b, and U^b ≤ U^b, where equalities are possible in each case. We say that L_n^p is a lower actual inventory threshold if

U_n^p is an upper actual inventory threshold if

L^b is a lower total (actual plus borrowed) inventory threshold if

and U^b is an upper total inventory threshold if

The following lemma clarifies these definitions.

Lemma 3.2: For any n = 1,2,…, consider four threshold levels L_n^p, U_n^p, L^b, and U^b satisfying (3.13)–(3.16). Define the following decisions: order up/scrap down to the level

where y is the current inventory level, and borrow up/store down to the level

Then the actions a_n(y) = t_n′ − y and b_n(y) = z_n′ − a_n(y) minimize the right-hand sides of the optimality equations (3.3) and (3.4), respectively. Therefore, for any N = 1,2,…, the policy φ = {d_N,d_N−1,…,d₁} is optimal for the N-step problem, where d_n(x) = (a_n(x),b_n(x)), n = 1,…,N, and −∞ < x < ∞.

Proof: In light of Lemma 3.1, the problem of finding optimal policies via (3.3) and (3.4) is simply the single-period cash balance models discussed in [15] and [27, Sect.8-4]. Thus, similar to [27, Sect.8-4], we have optimal order-up-to and order-down-to levels defined by the minimums of the convex functions defined in (3.3) and (3.4) when the changes of variables z = y + a and z = y + b are applied. For any L_n^p ∈ [L_n^p,L_n^p] , an optimal action is to order up to level L_n^p if the current inventory y < L_n^p. If the inventory level is above any level U_n^p ∈ [U_n^p,U_n^p] , an optimal action is to reduce the inventory level to U_n^p. If the inventory level is between L_n^p and U_n^p, an optimal action is not to use the ordering/scrapping option. Similarly, the optimal decision obtained from (3.4) is to increase y to L^b ∈ [L^b,L^b] if y < L^b and to decrease y to U^b ∈ [U^b,U^b] if y > U^b. No borrowing/storage action is required if L^b < y < U^b. █

The following lemma simplifies the structure of the optimal policy in the sense that it displays that we need not produce (scrap) and store (borrow) in the same period.

Lemma 3.3: The following inequalities hold: L_n^p ≤ U^b and L^b ≤ U_n^p, for n = 1,2,….

Proof: We prove the first inequality. The proof of the second inequality is similar. Suppose L_n^p > U^b and set L_n^p = L_n^p and U^b = U^b. For n = 1 and y < L₁^p, (3.1) and Lemma 3.2 imply that for a = L₁^p − y > 0 and b = L^b − L₁^p < 0,

where the last expression corresponds to the policy that orders (a⁺ − b⁻) units and borrows nothing. This violation of the optimality equation implies the contradiction. Thus, the case n = 1 is proven.

For n ≥ 2, the inequality L_n^p > U^b is not possible by similar arguments, but we must consider two-step decisions. Again, suppose that this inequality holds. According to Lemma 3.2, when the initial state y < L_n^p, there is an optimal policy φ that prescribes to order up to the level L_n^p (a = L_n^p − y) and then to store down to the level U^b (b = U^b − L_n^p < 0). Consider now a policy ψ (when the initial state is y) that prescribes to order up to the level U^b at the first step and borrow nothing. At the second step, it orders/scraps the amount that the policy φ would order/scrap at the second step if the inventory level were L_n^p − D₁ plus it orders −b = L_n^p − U^b to make up the difference. It also borrows the same amount as the policy φ given that their actual inventory levels are the same. At the following steps, the policies coincide so that the inventory position seen by ψ coincides with φ; the processes couple.

Denote by c(y,d₁(y)) the ordering/scrapping costs for policy φ at the second step. The total ordering costs at the first two steps plus the borrowing/storage cost at stage 2 for policy φ are

Similarly for the policy ψ, we have

All other costs for these two policies coincide. Since C^ψ(y) < C^φ(y) (almost surely), we have v_n^ψ(y) < v_n^ψ(y). Thus, φ is not an optimal policy. This contradiction completes the proof. █

For L_n^p, U_n^p, L^b, and U^b satisfying (3.13)–(3.16), define

and

Lemma 3.3 implies

Combining Lemmas 3.2 and 3.3 and (3.24), we arrive at the major result of this section.

Theorem 3.4: Consider four threshold levels L_n^p, U_n^p, L^b, and U^b satisfying (3.13)–(3.16) and consider L_n^b and U_n^b defined in (3.22) and (3.23). Moreover, for the current inventory level y, let t_n′ be the order up/scrap down to action defined in (3.17) and let z_n′ be the borrow up/store down to action defined by

Then, (3.24) holds and the actions a_n(y) = t_n′ − y and b_n(y) = z_n′ − a_n(y) minimize the right-hand sides of the optimality equations (3.3) and (3.4), respectively. Therefore, for any N = 1,2,…, the policy φ = {d_N,d_N−1,…,d₁} is optimal for the N-step problem, where d_n(x) = (a_n(x),b_n(x)), n = 1,…,N, and −∞ < x < ∞.

Theorem 3.4 implies the existence of an optimal policy that in each period either produces (scraps) up (down) to the level L_n^p (U_n^p) and then potentially borrows (scraps) up (down) to the level L^b (U^b). These ideas are illustrated in the following example.

Example 3.5: Consider a finite horizon discounted cost problem with the following parameters:

The holding cost is assumed quadratic, and when x > 0 units are held in inventory, the holding cost is 0.002x², and when x ≤ 0, the backordering cost is 0.008x². The probability mass function p(·) of demand per period is

After a finite state approximation, the optimal policy can be defined by t_n′ in (3.17), where the optimal production/scrapping levels are

and L_n^b = 0, U_n^b = 2 for all n = 1,2,… in (3.25).

Aside from the observation that there exists several order-up-to or down-to levels, one should also note that the borrowing and storage options are used as secondary options to meet demand. Thus, the borrow-up-to level is higher than the order-up-to level, and the store-down-to level is lower than the scrap-down-to level.

Example 3.5 illustrates that it is possible that an optimal policy uses all four options: producing, scrapping, borrowing, and storing. The following two propositions give sufficient conditions when only ordering/scrapping options should be used and managers should not borrow or store. Proposition 3.6 states that borrowing and storage should not be used when they are relatively expensive. Proposition 3.7 indicates that borrowing and storage should not be used when the demand is either nonnegative or nonpositive.

Proposition 3.6: Suppose the holding and backordering costs are linear,

If e₊ > h₋, then the optimal policy presented in Theorem 3.4 does not borrow. Similarly, if h₊ < e₋, this optimal policy does not store. In addition, if e₊ = h₋, then L^b = −∞ and the optimal policy defined in Theorem 3.4 with L^b = −∞ does not borrow. Similarly, if e₋ = h₊, then U^b = ∞ and the optimal policy defined in Theorem 3.4 with U^b = ∞ does not store.

The case when e₊ = h₋ (e₋ = h₊) has the potential that one could borrow (store) and still be optimal but that this option need not be exercised. This is a consequence of the possibility of multiple optimal borrowing (storage) levels.

Proof: Note that

Thus, (3.9) implies that L^b = −∞ and yields the first result. Now, note that

so that the second result follows by assumption since h₊ < e₋ implies U^b = ∞. The cases e₊ = h₋ and h₊ = e₋ follow from similar considerations. █

Theorem 3.4 implies that

Similarly, for n ≥ 1,

For standard inventory problems with nonnegative demands and zero setup costs, so-called S-policies (also called “order-up-to” or “basestock” policies) are optimal: Always order up to the level S when the inventory level is smaller than S. For finite horizon problems, these order-up-to levels may depend on the stage number. The following statement demonstrates that for inventory problems with nonnegative demands, borrowing should not be used unless borrowing costs per unit are less expensive than ordering costs. Unlike Proposition 3.6, we do not assume that the holding costs are linear.

Proposition 3.7: Suppose c₊ ≤ e₊ and P(D ≥ 0) = 1. Then L^b ≤ L_n^p, and by selecting L^b = L^b in Theorem 3.4, we have that the optimal policy defined by (3.17) and (3.25) never borrows.

Proof: If L^b ≤ L_n^p and L^b = L^b, then L_n^b = L_n^p and the policy defined by (3.17) and (3.25) never borrows. So, we need only prove that L^b ≤ L_n^p. According to (3.5), this inequality is equivalent to

for all z < L^b. We fix z < L^b. Note that from (3.27)

and (3.29) holds for n = 0 as a nonstrict inequality. We consider any n = 1,2,… and make the induction assumption that the left-hand side of (3.29) is nonpositive for n − 1. Differentiating (3.28) yields (recall L^b ≤ L_n^b ≤ U_n^p)

Adding c₊ + (d⁻g*(z)/dz) = c₊ − e₊ to both sides of (3.30) and applying the inductive hypothesis (since D ≥ 0 almost surely) yields that (3.29) holds and the result is proven. █

Since the cases when the demand is nonnegative and nonpositive are symmetric, Proposition 3.7 implies the following corollary.

Corollary 3.8: Suppose c₋ ≤ e₋ and P(D ≤ 0) = 1. Then, U^b ≥ U_n^p, and by selecting U^b = U^b in Theorem 3.4, we have the optimal policy defined by (3.17) and (3.25) never stores.

Finally, we remark that the assumption that v₀ = 0 is simply for convenience; the results of this section hold when v₀ is an arbitrary nonnegative convex function.

4. INFINITE HORIZON DISCOUNTED COST OPTIMAL POLICIES

In order to obtain results analogous to Theorem 3.4 for the infinite horizon discounted problem, it is sufficient to justify taking limits as n approaches infinity on each side of the finite horizon optimality equations (3.3). This result is alluded to for the cash balance problem in [21] and [27], but apparently not shown.

Assume β < 1. Unlike the previous section, we do not suppress β. Since the optimality equations hold for problems with nonnegative costs (see, e.g., Theorem 8.2 in Strauch [39]), we may write the discounted cost optimality equations (DCOEs),

where g(y,b) is defined in (3.2). The system (4.1) is equivalent to

where g* is as defined in (3.4).

The model satisfies the following two conditions: All costs are nonnegative, and for all

and all n = 1,2…, the sets

are compact. Therefore, in view of [5, Prop.1.7, p.148] or [7, Prop. 9.17], v_n,β ↑ v_β as n → ∞. Thus, v_β is a convex function and Lemma 3.1 holds for the objective function v_β and for each of the optimality equations (4.1) and (4.2). Similar to the finite horizon case, we can rewrite the optimality equation (4.2) in the form

We define the numbers L_β^p, L_β^p, U_β^p, and U_β^p defined by (3.5)–(3.8) with v_n−1 replaced by v_β. As in the finite horizon case, note that L_β^p ≤ L_β^p and U_β^p ≤ U_β^p and define lower and upper actual inventory thresholds L_β^p and L_β^p satisfying the inequalities

The following lemma is similar to Lemma 3.2 and has a virtually identical proof, with the only difference being that (4.2) should be considered instead of (3.3).

Lemma 4.1: Consider four threshold levels L_β^p, U_β^p, L^b, and U^b satisfying (4.5), (4.6), (3.15), and (3.16), respectively. The stationary policy that orders up/scraps down to the level

where y is the current inventory level, and borrows up/stores down to the level

is optimal.

Similar to Lemma 3.3, we have that

The proofs of these inequalities coincide with the proof of Lemma 3.3 for n ≥ 2. We also define

. Thus, similar to Theorem 3.4, we have the main result for infinite horizon discounted cost problems.

Theorem 4.2: Consider four threshold levels L_β^p, U_β^p, L^b, and U^b satisfying (4.5), (4.6), (3.15), and (3.16), respectively. The stationary policy defined by the ordering/scrapping decision (4.7) for a current inventory level y and by the borrowing/storage decision to borrow up/store down to the level

is optimal.

Example 4.3: Consider the infinite horizon analog of Example 3.5. An optimal policy is defined by

. This is simply the four-threshold policy from Example 3.5 for n ≥ 6.

For infinite horizon problems, Propositions 3.6 and 3.7 hold for the stationary policy defined in Theorem 4.2. The proofs are virtually unchanged. However, since Theorem 4.2 describes a stationary policy, a stronger version of Proposition 3.7 holds.

Proposition 4.4: Suppose c₊ ≤ e₊ and P(D ≥ 0) = 1. Then, L^b ≤ L_β^p, and by selecting L^b = L^b in Theorem 4.2, we have that the L_β^p policy that prescribes to order at each step up to the level L_β^p, never borrows, never scraps, and never stores is optimal when the initial inventory level y ≤ L_β^p.

Similar to Corollary 3.8, we have the following statement.

Corollary 4.5: Suppose c₋ ≤ e₋ and P(D ≤ 0) = 1. Then, U^b ≥ U_β^p, and by selecting U^b = U^b in Theorem 4.2, we have that the policy that prescribes to scrap at each step down to the level L_β^p, never borrows, never orders, and never stores is optimal when the initial inventory level y ≥ U_β^p.

We remark that in addition to the convergence of the values v_n,β ↑ v_β, the convergence of the optimal policies takes place. Indeed, if

are limit points of sequences of the optimal ordering/scrapping thresholds for the objective function v_n,β, then for any L^b and U^b satisfying (3.15) and (3.16), we have that the four-threshold policy with

defined in Theorem 4.2 is optimal for the infinite horizon problem. This follows, for example, from the remark in [5, p.149].

5. AVERAGE COST PER UNIT TIME OPTIMAL POLICIES

In this section, we extend the previous results for the average cost case. We define the constant

where

.

As is shown in the next section, for our problem, w < ∞ and there exists a function u(x) with nonnegative finite values such that

where g(y,b) is as defined in (3.2). In addition, there exists a sequence β_n ↑ 1 such that lim_βn↑1(1 − β_n)m_βn = w and u(x) = lim_n→∞{v_βn(x) − m_βn} ≥ 0 for all

. Thus, the function u is nonnegative and convex and u(x) → ∞ as |x| → ∞.

Analogous to the discounted case, an equivalent system is

where g* is defined as in (3.4).

Similar to (3.5)–(3.8), define

and consider L^b, L^b, U^b, and U^b defined by (3.9), (3.10), (3.11), and (3.12), respectively. Consider L^b and U^b satisfying (3.15) and (3.16), respectively. As analogs to (3.13) and (3.14), consider L^p and U^p satisfying the inequalities

Lemma 5.1: Consider four threshold levels L^p, U^p, L^b, and U^b satisfying (5.8), (5.9), (3.15), and (3.16), respectively. The stationary policy that prescribes to order up/scrap down to

where y is the current inventory level, and to borrow up/store down to the level

defines the values a = t′ − y and b = z′ − t′ that minimize the right-hand side of (5.3) and (3.4), respectively. In addition, the infimum of the average costs per unit time, w(y) defined in (2.7), equals the constant w defined in (5.1), and the thresholds t′ and z′ define a stationary optimal policy.

Proof: Similar to Lemma 3.2, the convexity of u and h implies that the policy described minimizes the right-hand sides of (5.3) and (3.4). We recall that a policy for an MDP is called stationary if it is defined by a measurable mapping of the state space into an action space. The interpretation of this mapping is that if the system is at some state, the value of this mapping is the selected action (independent of time). For our problem, a stationary policy φ is a measurable mapping from

to

, where the first coordinate is how much to order/scrap and the second coordinate is how much to borrow/store. We remark that t′ = t′(y) in (5.10) and z′ = z′(t′) = z′(t′(y)) in (5.11) for an inventory level y. We consider the mapping φ(y) = (a(y),b(y)) = (t′(y),z′(t′(y))). Since the functions t′ and z′ have simple threshold forms, φ is measurable. Thus, we have

According to Schäl [37, Prop. 1.3], if the left-hand side of (5.12) is greater than or equal to the right-hand side, then w^φ(y) = w(y) = w for all

. █

Lemma 5.2: L^p ≤ U^b and L^b ≤ U^p.

Proof: Let φ be the (stationary) policy defined by (5.10) and (5.11). Since φ defines actions that minimize the right-hand sides of (5.3) and (3.4), the policy φ is canonical; see [25, Sect.5.2]; that is, for any n ≥ 1, φ minimizes the criterion

. The rest of the proof follows from the coupling arguments in the proof of Lemma 3.3 for n ≥ 2. █

Corresponding to (3.22) and (3.23), define

Lemma 5.2 implies

, which together with Lemma 5.1 imply our main result for undiscounted costs.

Theorem 5.3: For four thresholds L^p, U^p, L^b, and U^b satisfying (5.8), (5.9), (3.15), and (3.16), respectively, consider the thresholds

defined in (5.13) and (5.14). The stationary policy that prescribes for a current inventory level y to order up/scrap down to the level t′ defined in (5.10) and to borrow up/store down to the level

where y is the current inventory level and

have been defined in (5.13) and (5.14), is optimal.

Example 5.4: Suppose we use the same parameters as Example 3.5, but consider the average cost criterion. An optimal policy is defined by

.

The following proposition is similar to Proposition 3.6. Its proof is identical to that of Proposition 3.6, with the major difference being that (5.3) should be considered instead of (3.3).

Proposition 5.5: Suppose the holding costs are linear (i.e., (3.26) holds). If e₊ > h₋, then the optimal policy presented in Theorem 5.3 does not borrow. Similarly, if h₊ < e₋, this policy does not store. In addition, if e₊ = h₋, then L^b = −∞ and the optimal policy defined in Theorem 5.3 with L^b = −∞ does not borrow. Similarly, if e₋ = h₊, then U^b = ∞ and the optimal policy defined in Theorem 5.3 with U^b = ∞ does not store.

Analogous to Proposition 4.4 and Corollary 4.5, we have the following two results.

Proposition 5.6: Suppose c₊ ≤ e₊ and P(D ≥ 0) = 1. Then L^b ≤ L^p, and by selecting L^b = L^b in Theorem 5.3 we have that the L^p policy that prescribes to order at each step up to the level L^p, never borrows, never scraps, and never stores, is optimal when the initial inventory level y ≤ L^p.

Corollary 5.7: Suppose c₋ ≤ e₋ and P(D ≤ 0) = 1. Then U^b ≥ U^p, and by selecting U^b = U^b in Theorem 5.3 we have that the policy that prescribes to scrap at each step down to the level U^p, never borrows, never orders, and never stores, is optimal when the initial inventory level y ≥ U^p.

At the end of Section 4, we established that discounted cost finite horizon optimal thresholds converge to discounted cost infinite horizon optimal thresholds. Similarly, discounted cost infinite horizon optimal thresholds converge in some sense to optimal thresholds for the average cost criterion. Indeed, for ordering and scrapping decisions, let

be limit points of a sequence of optimal ordering/scrapping thresholds L_βn^p and U_βn^p as n → ∞, where the sequence {β_n,n ≥ 0} is chosen as discussed in the text following 5.2. Appealing to the results in the the next section implies that

are respectively optimal ordering and scrapping thresholds for the average cost per unit time criterion.

6. THE AVERAGE COST OPTIMALITY EQUATIONS

In this section, we prove the existence of a solution to the ACOEs (5.2) and (3.2). Instead of restricting attention solely to the problem at hand, we provide sufficient conditions for the existence of a solution to the ACOEs for a more general MDP, and then show that these conditions are satisfied for our problem.

Consider an MDP with a standard Borel state space

. Suppose ρ is a metric on

such that ρ(x,y) < ∞ for all

is complete and separable. Assume that the one-step costs c(x,a) are nonnegative and that the MDP satisfies the standard Borel measurability conditions (see, e.g., [37]). The optimal values in the infinite horizon discounted cost case, v_β(x), are defined for discount factors β ∈ [0,1). Let A(x) be the set of available actions at state x and q be the transition probability. Consider the following set of assumptions

Assumptions C:

1. There exists a nondecreasing, continuous function η on R₊ = [0,∞) such that η(0) = 0, η(r) < ∞ for all

,

for all

, and

for all

and a ∈ A(x).

where

.

3. For

, there exists a compact subset

such that c(x) ≥ N for all

, where c(x) = inf_a∈A(x) c(x,a).

Note that Assumption C1 implies that v_β(x) is a continuous function in x for any β ∈ [0,1). Since v_β(x) ≥ c(x), there exist x_β such that v_β(x_β) = m_β. Let M(β) = {x ∈ X|v_β(x) = m_β}. In particular, M(β) ⊆ K_N for N > m_β. The following lemma is similar to Lemma 4.6 in [37] and to Lemma 4 in [8].

Lemma 6.1: Let Assumptions C2 and C3 hold. Suppose {β(n),n ≥ 1} is a subsequence such that β(n) ↑ 1 and w = lim_n→∞(1 − β(n))m_β(n). Then, there exists a compact subset

and a finite integer [ell ] such that M(β(n)) ⊆ K for n ≥ [ell ].

Proof: Consider N > w + 1. Then, N > lim_n→∞(1 − β(n))m_β(n) + 1 and there exists an integer [ell ] such that for n ≥ [ell ]

Set K = K_N as defined in Assumption C3. We prove by contradiction that K is the set whose existence is postulated by the lemma. Let β satisfy (6.2) and suppose that this is not the case. Then, there exists

; that is, c(x) ≥ N and v_β(x) = m_β. Let T be the first hitting time of K; T = inf{n ≥ 0|X_n ∈ K}. Then, for any stationary policy π,

where the strict inequality follows from (6.2) and the last inequality follows from T ≥ 1 when x ∉ K. Since π is arbitrary, v_β(x) > m_β and the inclusion x ∈ M(β) is not possible. █

We recall that a real-valued function f defined on a metric space Y is called inf-compact if the set

is compact for any

. Note that since compact sets are closed, inf-compactness implies lower-semicontinuity. Consider the following two additional conditions:

Assumptions C (continued):

4. For each fixed

, the function c(x,a) is inf-compact in a.

5. Transition probabilities q(·|x,a) are weakly continuous in a for each

.

Theorem 6.2: Suppose C hold. Then the following hold:

1. There exists a continuous nonnegative function u on

such that for all

,

2. There exists a sequence β(n) → 1 such that u(x) = lim_n→∞ u_β(n)(x), where u_β(x) = v_β(x) − m_β,

.

3. If

is a linear space and the functions v_β are convex for all β ∈ [0,1), then u is convex.

4. For fixed

, let a* be a limit point of a sequence {a_n,n ≥ 1}, where v_β(n)(x) = c(x,a_n) + β(n)∫v_β(n)(y)q(dy|x,a_n) (the point a* exists in view of Lemma 6.1). Then

Proof: Consider the discount cost optimality equations (DCOEs),

In particular, the minimum is achieved in the right-hand side of (6.4) since the expression minimized is lower semicontinuous (the sum of two lower semicontinuous functions). The first function is lower semicontinuous because of Assumption C4 and the second function is lower semicontinuous because of Assumptions C1 and C5. The former implies that v_β(x) is continuous. In addition, v_β(x) ≥ 0.

A little algebra in (6.4) reveals

Utilizing Assumption C2, there exists a sequence β(n) ↑ 1 as n → ∞ such that lim_n→∞ β(n)m_β(n) = w. Lemma 6.1 implies that we can select this sequence such that M(β(n)) ⊆ K, where K is a compact subset of

. Let diam(K) denote the maximal distance between two points in K (the diameter of K). Since K is compact, diam(K) exists and is finite. We fix any point z₀ ∈ K. Then, according to Assumption C1,

where z ∈ K is such that v_β(n)(z) = m_β(n).

Since |u_β(x) − u_β(y)| ≤ ε when η(ρ(x,y)) < ε, the family of functions u_β(n) is equicontinuous. By the Ascoli theorem [25, p.96], there exists a subsequence {β(n_k),k ≥ 1} of the sequence {β(n),n ≥ 1} such that u_β(nk) converges pointwise to a continuous function u and this convergence is uniform on each compact subset of

. In particular, for each

,

Fix

. We first show that

where the minimum in (6.8) is attained by the same reasons as in (6.3). For each β(n_k), consider a(n_k) such that

Without loss of generality, select the sequence n_k such that |(1 − β(n_k))m_β(nk) + u_β(nk)(x) − w − u(x)| ≤ 1 for all n_k. Assumption C4 implies that all a(n_k) belong to the compact set K_N(x), where N = w + u(x) + 1. Thus, there exists a* ∈ A(x) and a subsequence {m_k} of {n_k} such that a(m_k) → a*. The result obtained by Serfozo's [38] extension of Fatou's lemma (see also Lemma 2.3 in [37]) implies that

Since c is lower semicontinuous,

Thus, (6.8) is proved.

From (6.5), we have that for any a ∈ A(x),

Consider (6.11) for β = β(n) defined above and apply sequentially the Ascoli theorem [25, p.96] and Lebesgue's dominated convergence theorem. The latter is applicable in view of Assumption C1 and (6.6). Indeed, (6.6) yields

and (6.1) implies that

We, thus, have for any a ∈ A(x),

which is equivalent to

The next result shows that the ACOEs (5.2) and (3.2) hold for the inventory problem considered. We remark that Theorem 6.2 also implies the validity of the ACOEs for problems without borrowing and storage (let

in (5.2)).

Proposition 6.3: In the inventory problem considered, there exists a solution to the ACOEs (5.2) and (3.2), (w,u(y)), such that the relative value function u(y) is nonnegative, convex, and equal to the limit of functions u_β(n) described in Theorem 6.2.

Proof: We verify that Assumptions C1–C5 hold so that Theorem 6.2 applies. First, in our case

, ρ(x,y) = |x − y|, and η(r) = r max{c₊,c₋}. Consider two inventory levels x and z. In state x, suppose the manager orders or scraps inventory to bring the level to z, then implements an optimal policy thereafter. Since this policy may not be optimal, v_β(x) ≤ v_β(z) + max{c₊,c₋}|z − x|. In other words,

Since

for any

, h is convex, and h(x) → ∞ as x → ∞, we have

and Assumption C1 is verified.

Fix

. Consider the policy φ that always orders up to level x. The renewal reward theorem implies that w^φ(x) = lim_n→∞(1/n)v_n,1^φ(x) < ∞. Thus, lim inf_β↑1(1 − β)m_β ≤ lim inf_β↑1(1 − β)v_β(x) ≤ lim inf_β↑1(1 − β)v_β^φ(x) = w^φ(x) < ∞ and Assumption C2 holds.

To verify Assumption C3, we must prove that c(x) → ∞ as |x| → ∞. Let x → ∞ and let d = min{c₊,c₋,e₊,e₋}. Note that d > 0 and for

,

where the first inequality follows by setting y = a + b and applying Jensen's inequality. To verify the second inequality, consider the two possibilities (a)

and (b)

. The case x → −∞ is similar.

Assumption C4 holds since for

, {(a,b)|C(x,(a,b)) ≤ λ} is closed and bounded. The fact that it is bounded follows from the fact that C(x,(a,b)) → ∞, as either a or b → ∞. It is closed since the cost function is convex and, therefore, continuous. Assumption C5 is equivalent to

as a_n → a, for any bounded, continuous f, which follows from Lebesgue's dominated convergence theorem. █