**American Journal of Operations Research** Vol.2 No.2(2012), Article ID:19937,4 pages DOI:10.4236/ajor.2012.22023

A New Proof for the Tight Range of Optimal Order Quantities for the Newsboy Problem with Mean and Standard Deviation

Department of Management and Marketing, Jennings A. Jones College of Business, Middle Tennessee State University, Murfreesboro, USA

Email: Jinfeng.yue@mtsu.edu

Received March 20, 2012; revised April 20, 2012; accepted April 30, 2012

**Keywords:** Newsboy Problem; Distribution-Free Approach; Optimal Decision

ABSTRACT

In the classical Newsboy problem, we provide a new proof for the tight range of optimal order quantities for the newsboy problem when only the mean and standard deviation of demand are available. The new proof is only based on the definition of the optimal solution therefore it is the most straightforward method. It is also shown that the classical Scarf’s rule is the mid-point of the range of optimal order quantities. This provides an additional understanding of Scarf’s order rule as a distribution free decision.

1. Introduction

The classical newsboy problem assumes that there is a single purchase decision before the selling season and the demand D is an unknown random variable. The objective is to decide the order quantity Q to maximize the expected profit. In Newsboy problem, the expected profit can be expressed as

(1)

where c > 0 is the unit cost, p is the selling price, s is the salvage value, G is the cumulative distribution function of demand. In (1), is the expected value and is defined as when Q is greater than D and zero otherwise. Furthermore, let p = c(1 + m) > c where m is the mark up, and s = (1 – d)c < c where d is the discount, (1) can be expressed as

To maxmize the above expected profit, it is equivalent to mininize the following cost function

(2)

To determine the order quantity Q, G is frequently assumed to be normally distributed in many OM/OR literatures ([1-3]). However, this assumption may not be true in many situations. Technically, it is much harder to obtain the entire distribution information than only part of the distribution information such as mean and standard deviation of G. Scarf [4] first used the min-max approach to find the distribution-free order quantity based on only finite mean µ and standard deviation. The order quantity is given by

(3)

In 1993, Gallego and Moon [5] reproved Scarf’s rule with a compact new proof. They also extended the above analysis to other situations such as the recourse case (there is a second purchasing opportunity), the fixed order cost case, the case of a random yield and the multi-item case where multiple items compete for a scare resource. Moon and Choi [6] extended Scarf’s rule to the newsboy problem with balking. Applications of Scarf’s order rule can also be found in many other inventory models, see for example, [7-10].

2. The Tight Range of Optimal Order Quantities

Consider a family of distributions with common mean and standard deviation. Scarf’s order rule is based upon the least favorable distribution in the family, which minimizes the objective function for any given Q. However, there are infinite distributions with common mean and standard deviation in and each distribution has its optimal solution. Therefore if we can obtain a tight range of the optimal solutions in family and find the relationship between the Scarf’s rule and this range, we can better understand the distribution free Newsboy problem and the demand distribution information’s value. The question of the tight range of optimal order quantities for all distributions in the family is answered by the following theorem.

Theorem. For any, the optimal order quantity G^{*} must be between the tight range [Q_{l}, Q_{u}] where the lower bound is

and the upper bound is

Coincidently, Scarf’s order rule is the midpoint of this tight optimal solution range.

In our previous research [11], we focused on the expected value of the distribution information and provide an indirect proof of optimal solution range based on the upper and lower bounds of the objective functions. The question here is if there is a direct proof of the above theorem only based on the definition of the optimal solution. We provide such a direct proof below.

Proof: For a cumulative distribution, if Q^{*} is the optimal order quantity which minimizes C(Q) in (2), then Q^{*} must satisfy the relation that the first derivative of C(Q) is zero. We have

(4)

If demand D is a continuous random variable, Q^{*} satisfies (5) when the first derivative of (4) is set to be zero. We have

(5)

That is,

(6)

When D is discrete, for general G(D), Q^{*} is an optimal order quantity if and only if either

or

, , (7)

where > 0. In general, no matter D is continuous or discrete, the necessary condition of the optimal order quantity is

(8)

To determine the range of optimal order quantities, it is equivalent to find the smallest (and the largest) Q^{*} which satisfies condition (8), and simultaneously show that the distribution G is in. To find such a smallest Q^{*}, we have the following optimization formulation:

(9)

s.t.

(10)

(11)

(12)

It is easy to verify that for a two point distribution with weight [m/(m + d)] on Q_{l} and weight [d/(m + d)] on Q_{u} any Q between Q_{l} and Q_{u} is an optimal solution since it satisfies condition (7}). Therefore Q_{l} and Q_{u} are two achievable optimal order quantities. We now prove that an optimal Q^{*} can not be outside of [Q_{l}, Q_{u}]. Assume that (Q_{l} –) (where > 0) is an optimal order quantity for a cumulative distribution function, from (10) we have

(13)

From (11) we have

(14)

Also,

(15)

From (12) we have

(16)

and

(17)

From (13), (14), (15), (16), and (17), the cumulative distribution function G_{1}(D) must simultaneously satisfy:

(18)

(19)

and

(20)

We have

(21)

According to (18) and (19), we have

(22)

and

(23)

Use the fact that

combine with (22) and (23), (21) becomes

This contradicts (20). Therefore Q_{l} –(with >0) cannot be an optimal order quantity for. Similarly, we can prove that optimal order quantity cannot be larger than Q_{u}. To prove this optimal solution range is a tight range, we consider a two point distribution with the weight of [m/(d + m)] at point Q_{l} and weight of [d/(d + m)] at point Q_{u}, we can easily verify that this two point distribution is in the family of, and has the optimal solution at any point between Q_{l} and Q_{u}.

End of Proof

To obtain a distribution free, and robust order quantity based upon the range of optimal order quantities of [Q_{l}, Q_{u}], one can simply use the average of Q_{l} and Q_{u}. We can see that the robust order quantity is exactly the same as Scarf’s order quantity. Therefore, Scarf’s order quantity is not only the solution of the min-max approach, but also the mid-point of the range of optimal order quantities. This provides an added dimension of our understanding of Scarf’s order rule as the optimal rule based on a distribution free procedure.

3. Conclusion

This Research provides a new direct proof of the tight range of the optimal solution range for the Newsboy problem with only demand distribution mean and standard deviation available. This new proof only uses the definition of the optimal solution. The Scarf’s order rule turns out to be the midpoint of this tight range and which is another indicator of the robustness of the Scarf’s rule. In practice, if only the demand distribution mean and standard deviation are available, we can find the upper and lower bounds of the optimal solution range and compare them with the Scarf’s rule. If the range is not too large, order decision by Scarf’s rule will be a good decision. If the range is very large, Scarf’s rule will be very risky and it is recommended to obtain the entire distribution information to decide the order quantity.

REFERENCES

- G. Hadley and T. Whitin, “Analysis of Inventory Systems,” Prentice-Hall, New Jersey, 1963.
- F. Hillier and G. Lieberman, “Introduction to Operations Research,” 5th Edition, Holden-Day, California, 1990.
- S. Nahmias, “Production and Operations Analysis,” Irwin, Illinois, 1989.
- H. A. Scarf, “A Min-Max Solution of an Inventory Problem,” In: K. J. Arrow, S. Karlin and H. E. Scarf, Eds., Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, California, 1958, pp. 201-209.
- G. Gallego and I. Moon, “The Distribution Free Newsboy Problem: Review and Extensions,” Operations Research Society, Vol. 44, 1993, pp. 825-834.
- I. Moon and I. Choi, “The Distribution Free Newsboy Problem with Balking,” Operations Research Society, Vol. 46, 1995, pp. 537-542
- G. Gallego, “A Minimax Distribution Free Procedure for the (Q, R) Inventory Mode,” Operations Research Letters, Vol. 11, No. 1, 1992, pp. 55-60. doi:10.1016/0167-6377(92)90063-9
- I. Moon and G. Gallego, “Distribution Free Procedures for Some Inventory Models,” Operations Research Society, Vol. 45, 1994, pp. 651-658.
- G. Gallego, “New Bounds and Heuristics for (Q, R) Policies,” Management Science, Vol. 44, No. 2, 1998, pp. 219-223. doi:10.1287/mnsc.44.2.219
- M. Hariga and M. Ben-Daya, “Some Stochastic Inventory Models with Deterministic Variable Lead Time,” European Journal of Operations Research, Vol. 113, No. 1, 1999, pp. 42-51. doi:10.1016/S0377-2217(97)00441-4
- J. Yue, B. Chen and M. C. Wang, “Expected Value of Distribution Information for the Newsvendor Problem,” Operations Research, Vol. 54, No. 6, 2006, pp. 1128- 1136. doi:10.1287/opre.1060.0318