UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A diffusion model for a two product inventory system Ling, Daymond 1978

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1978_A4_6 L56.pdf [ 3.14MB ]
Metadata
JSON: 831-1.0094229.json
JSON-LD: 831-1.0094229-ld.json
RDF/XML (Pretty): 831-1.0094229-rdf.xml
RDF/JSON: 831-1.0094229-rdf.json
Turtle: 831-1.0094229-turtle.txt
N-Triples: 831-1.0094229-rdf-ntriples.txt
Original Record: 831-1.0094229-source.json
Full Text
831-1.0094229-fulltext.txt
Citation
831-1.0094229.ris

Full Text

A DIFFUSION MODEL FOB A THO PRODUCT INVENTORY SYSTEM by DAYMOND LING B . S c , U n i v e r s i t y of B r i t i s h Columbia, 1976 ft THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN BUSINESS ADMINISTRATION THE FACULTY OF GRADUATE STUDIES DIVISION OF MANAGEMENT SCIENCE we accept t h i s t h e s i s as conforming t o the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1978 fc} Daymond L i n g , 1978 i n In presenting th i s thes is in p a r t i a l fu l f i lment of the requirements for an advanced degree at the Univers i ty of B r i t i s h Columbia, I agree that the L ibrary shal l make it f ree l y ava i lab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho lar l y purposes may be granted by the Head of my Department or by h is representat ives . It is understood that copying or pub l i ca t ion of th is thes is for f i n a n c i a l gain sha l l not be allowed without my wr i t ten permission. Department of MANAGEMENT SCIENCE The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date A p r i l OA _ 1Q7« fi ABSTRACT T h i s t h e s i s presents the r e s u l t s o f an i n v e s t i g a t i o n of a continuous-time two product i n v e n t o r y model i n which the stock l e v e l of two d i v i s i b l e commodities i s rep r e s e n t e d by a two dimensional d i f f u s i o n process. Two c l a s s e s o f replenishment p o l i c i e s are co n s i d e r e d . One i s a two dimensional analog of the s t a t i o n a r y one dimensional (s,S) p o l i c y ; i . e . , when e i t h e r the inv e n t o r y of product one d e c l i n e s t o s t or when the i n v e n t o r y of product two d e c l i n e s to sz, both s t o c k s are i n s t a n t a n e o u s l y r e p l e n i s h e d , product one up t o S_, and product two up to S 2. T h i s i s r e f e r r e d t o as the (s_,s_. ,S_ ,S^) p o l i c y . The i n v e n t o r y i s then allowed t o d e c l i n e again and i s r e p l e n i s h e d . These c y c l e s continue i n d e f i n i t e l y . There are c o s t s a s s o c i a t e d with the replenishment of stock and ma i n t a i n i n g a g i v e n i n v e n t o r y . The o b j e c t i v e i s to choose v a l u e s f o r (s_,s_ ,S_ ,S_,) t o minimize the long-run average c o s t of o p i r a t i n g such a system. The a p p r o p r i a t e theory o f d i f f u s i o n processes i s h e u r i s t i c a l l y developed and then a p p l i e d to e v a l u a t e t h i s c o s t . In g e n e r a l , a n a l y t i c s o l u t i o n s cannot be obt a i n e d . , C l a s s i c a l numerical a n a l y s i s methods are used t o o b t a i n the average c o s t s f o r given (s_ , s z ,S_ , S_,) v a l u e s and t o s e l e c t the best such v a l u e s . One dimensional d i f f u s i o n models are a s p e c i a l case o f the present model and Puterman's [ 2 1 ] r e s u l t s are used to v e r i f y the r e s u l t s o b t a i n e d . The other p o l i c y examined d i f f e r s from the two dimensional (s 1,s__,S 1 ,S._) p o l i c y i n t h a t the lower l e v e l s , s_ and st, of the stock l e v e l s are coupled i n the form of an e l l i p t i c a r c . Numerical s o l u t i o n o f t h i s p o l i c y can be obtained and comparisons of the two p o l i c i e s are made. i i i TABLE OJ CONTENTS 1. Introduction And Summary .............................. 1 2. Literature Survey . 3 3. Diffusion Processes .. • • • 5 4., Hodel Description And Renewal Structure ...... 9 5. Evaluation Of The Long-run Average Cost ............... 14 6. Hethods Of Solution ................................... 21 7. The (s_ ,s_, ,S_ tSz ) Policy 25 8. The Modified Policy ................. ........ ,..v...., 39 9. Recommendations For Future Research ................... 44 References ................................................ 46 Appendix ... .... ., •. . ... . ... ... .... • . . 48 LIST OF TABLES Table 1. Search Of G l o b a l O p t i a a l ( s ^ s ^ . S ^ S ^ ) P o l i c y V LIST OF FIGURES F i g . 1. a C o n t r o l Region Of The ( s ( ,sz , S± , Sz ) P o l i c y ...... 13 F i g . 2 . A C o n t r o l Region Of The M o d i f i e d P o l i c y 13 F i g . 3. Sample Output Of (s_ ,sz rS± ,SZ) P o l i c y Code ........ 34 F i g . 4. Convexity Of S<4.,/>0 With Respect To ( s ± r s z ) 35 F i g , 5. E f f e c t s Of C o r r e l a t i o n On 6<*„ 4_,»;,>, 36 F i g . 6 . The Phenomenon Of S p l i t t i n g 37 F i g . 7 . E f f e c t s Of Unequal Variance 38 F i g . 8 . Sample Output Of Modif i e d P o l i c y Code 11 F i g . 9. The Convexity Of 0 M t h Respect To ( x r , y r ) ....... 42 Fig.10. E f f e c t Of E o r r e l a t i o n On Th§ M o d i f i e d P o l i c y ..... 43 Fig.11. The Nine-point Star Approximation «... 48 v i Acknowledgments I am ind e b t e d t o P r o f e s s o r H a r t i n L. Paterman ( D i v i s i o n o f Management Science, F a c u l t y of Commerce and Business A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h Columbia) f o r i n t r o d u c i n g me to the s u b j e c t o f d i f f u s i o n processes and f o r g u i d i n g t h i s r e s e a r c h . , H i s i n t e r e s t , guidance, and p a t i e n c e have been i n v a l u a b l e and I ' am deeply g r a t e f u l . I am a l s o indebted t o P r o f e s s o r Shelby L. .,. Bruraelle ( D i v i s i o n o f Management s c i e n c e . F a c u l t y o f Commerce and Business A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h Columbia) whose wisdom i n s t o c h a s t i c processes has a l s o been i n v a l u a b l e , and P r o f e s s o r Derek A t k i n s ( D i v i s i o n o f Management Science, F a c u l t y o f Commerce and Business A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h Columbia) f o r h i s comments on the form and contents o f t h i s t h e s i s . 1 Is. -lBi£9iSStASS KBJL Summary In t h i s t h e s i s a continuous-time s t o c h a s t i c model of a s t o r a g e system f o r two d i v i s i b l e commodities i s s t u d i e d . The s t o c k l e v e l of the two commodities i s r e p r e s e n t e d by a two dimensional d i f f u s i o n process (Markov process with continuous sample p a t h ) , with a n e g a t i v e d r i f t v e c t o r . The continuous sample paths n a t u r a l l y suggests f a c i l i t i e s s t o r i n g l i q u i d s such as gas, o i l , petroleum products, but the model may a l s o be used t o approximate n o n - d i v i s i b l e q u a n t i t i e s such as automobiles, t e l e v i s i o n s , books, o r pens, e s p e c i a l l y i f the numbers are l a r g e . , The stock l e v e l o f the system i s observed c o n t i n u o u s l y through time and two s t a t i o n a r y o p e r a t i n g p o l i c i e s are c o n s i d e r e d . One i s the two dimensional analog, (s_ ,s 0SX ,S__) , of the one dimensional (s,S) p o l i c y ; i . e . , when the stock l e v e l o f commodity i f a l l s t o s c , both commodities are i n s t a n t a n e o u s l y r e p l e n i s h e d to the l e v e l (S_,S__). The process i s then allowed to d r i f t again with the s w i t c h i n g repeated i n d e f i n i t e l y . There are c o s t s a s s o c i a t e d with r e - o r d e r i n g as well as m a i n t a i n i n g a given i n v e n t o r y . The other p o l i c y examined d i f f e r s from the (s_ , s a ,S t,S z) p o l i c y i n t h a t the lower l e v e l s st and sz o f the r e - o r d e r curve (In two dimensions i t i s r e f e r e d t o as the r e -order curve r a t h e r than the r e - o r d e r point) are coupled i n the form of an e l l i p t i c a r c . T h i s i s r e f e r e d to as the modified p o l i c y . Our o b j e c t i v e i s t o c h a r a c t e r i z e the long-run average c o s t , determine the v a l u e s o f {st,sz,S_,SZ) that minimize t h i s c o s t , examine the p r o p e r t i e s o f the s o l u t i o n and note the d i f f e r e n c e between the two c l a s s e s of o p e r a t i n g p o l i c i e s . 2 T h i s t h e s i s i s o r g a n i z e d as f o l l o w s . , In S e c t i o n 2 the r e l a t e d l i t e r a t u r e i s surveyed. In S e c t i o n 3 r e l e v a n t r e s u l t s from the theory o f m u l t i - d i m e n s i o n a l d i f f u s i o n processes are reviewed. In S e c t i o n 4 the model i s formulated and the un d e r l y i n g renewal s t r u c t u r e d e s c r i b e d . , The a p p r o p r i a t e theory of d i f f u s i o n p r o c e s s e s i s h e u r i s t i c a l l y developed i n S e c t i o n 5 to o b t a i n p a r t i a l d i f f e r e n t i a l eguations which c h a r a c t e r i z e the 8xpfcted v a l u e s ©f the random f u n c t i o n s used i n the e v a l u a t i o n of the long-run average c o s t . S u f f i c i e n t c o n d i t i o n s f o r these expected values to be f i n i t e are a l s o g i v e n . S e c t i o n 6 d i s c u s s e s the methods a v a i l a b l e t o s o l v e these p a r t i a l d i f f e r e n t i a l e g u ations and shows t h a t i n g e n e r a l s o l u t i o n s cannot be obtained i n c l o s e d form. In S e c t i o n 7 the p r o p e r t i e s of the (s_,s_ #S_ ,S_ ) p o l i c y i s s t u d i e d . , C l a s s i c a l numerical a n a l y s i s methods are used t o o b t a i n the average c o s t f o r given fs. ,s, ,S, ,S„) values and to s e l e c t the b e s t v a l u e s . , Puterman's [21] r e s u l t s f o r the one-dimensional problem are used t o v e r i f y the r e s u l t s o b t a i n e d . / Q u a l i t a t i v e f e a t u r e s o f the numerical s o l u t i o n are a l s o presented., In S e c t i o n 8 the modified p o l i c y i s examined and comparisons between the two p o l i c i e s are made. Some p o s s i b l e f u t u r e r e s e a r c h areas are d i s c u s s e d i n S e c t i o n 9. 3 2., L i t e r a t u r e Survey In t h i s t h e s i s we study g e n e r a l i z a t i o n s of the one-dimensional (s,S) i n v e n t o r y model. Much o f the r e l a v e n t l i t e r a t u r e on (s,S) p o l i c i e s are surveyed e x t e n s i v e l y i n [ 2 1 ) . The d i f f u s i o n process model f o r i n v e n t o r y systems was i n t r o d u c e d by Bather [3] and f u r t h e r s t u d i e d by Gimon [ 1 4 ] and Puterman [ 2 1 ] , s i m i l i a r r e s u l t s f o r a r e l a t e d model have been o b t a i n e d by C o n s t a n t i n i d e s and Richard [ 6 ] . The l i t e r a t u r e of m u l t i - p r o d u c t i n v e n t o r y systems i s more s c a r c e and l e s s e x t e n s i v e than the one product l i t e r a t u r e . / Some of the r e c e n t works are t h a t of Goswick and S i v a z l i a n M 5 ] , and I g n a l l [ 17], , I g n a l l [ 1 7 ] i n v e s t i g a t e d a two product c o n t i n u o u s l y reviewed i n v e n t o r y system where demand of the two goods come from two independent Poisson processes. The c o s t s t r u c t u r e c o n s i s t s of shortage and h o l d i n g c o s t s and a v a r i a b l e c o s t o f r e o r d e r i n g . fi (s,c,S) p o l i c y was c o n s i d e r e d ; i f the stock o f any product drops to i t s r e - o r d e r p o i n t , s, a l l the products with stock l e s s than i t s can-order p o i n t , c, are re-ordered back to i t s o r d e r - t o p o i n t , S. , I g n a l l showed that the (s,c,S) p o l i c y i s not always o p t i m a l , i n c e r t a i n cases the o p t i m a l p o l i c y has the c h a r a c t e r i s t i c t h a t the g u a n t i t y ordered of the product t h a t t r i g g e r e d the r e - o r d e r depends on the i n v e n t o r y o f the other product. Goswick and S i v a z l i a n [ 1 5 ] a l s o examined a model with v a r i a b l e r e - o r d e r cost.„ The model s t u d i e d i s a two-product p e r i o d i c review model with uniform demand distribution.„ The steady s t a t e behaviour of the system was analyzed and a comparisons between mixed re-ordering, i n d i v i d u a l re-ordering and j o i n t re-ordering are made. I t was shown that each of the three policy was optimal i n some situations and not i n others. , The two p o l i c i e s examined in t h i s t h e s i s belong to the class of joint replenishment p o l i c i e s , i . e . , when an order i s placed, both products are replenished. This thesis can be considered as an extension of Puterman*s T21] r e s u l t s to higher dimensions., 5 -3.; D i f f u s i o n Processes D i f f u s i o n processes a re s p e c i a l cases of strong Markov processes with almost c e r t a i n l y continuous sample paths. The simplest example i s the motion of very s m a l l p a r t i c l e s suspended i n a f l u i d , the s o - c a l l e d Brownian motion* The study of systems with white n o i s e and continuous models f o r random-walk problems a l s o l e a d to d i f f u s i o n processes. Much of the m a t e r i a l presented below are t r e a t e d i n great d e t a i l i n A r n o l d f 2 ] and Dynkinf 9 ]. Let I denote an nonempty index s e t and (n#u,P) a p r o b a b i l i t y space. A f a m i l y { D t ; t e I } of iC valued random v a r i a b l e s i s a s t o c h a s t i c process with index s e t I and s t a t e space ^ . Let I be an i n t e r v a l of the extended r e a l l i n e and f D t ; t ^ I ] a s t o c h a s t i c process, then D t(«)is, f o r every f i x e d t£l, an ^ valued random v a r i a b l e whereas, f o r every f i x e d od , D. (<ui) i s an TR* valued f u n c t i o n d e f i n e d on I. I t i s c a l l e d a sample fiath of the s t o c h a s t i c p r o c e s s . Let I be an open connected d i f f e r e n t i a l manifold i n H"- with boundary 3B and x=<x_,...,xn) a n-vector i n B. To uni q u e l y d e f i n e a d i f f u s i o n process we must s p e c i f y i t s behaviour on B and 3B. F i r s t we d i s c u s s B. A n-dimensional Markov process with p r o b a b i l i t y t r a n s i t i o n f u n c t i o n p(s,x,t,A) (p(s,x,t,A) i s the c o n d i t i o n a l p r o b a b i l i t y of D^A given t h a t D/L=x, i . e . , P(s,x,t,A) = p( D t a TI D^= x )) on B i s a d i f f u s i o n i f i t s a t i s f i e s the f o l l o w i n g c o n d i t i o n s ; 1) For any &>0, t>0, x B, i y - * i > £ 6 2) There ex i s t s jji{x,t) and L, (x,t) such that for any £>0, t>0 the n-vector pL(x,t) with components u;_(x,t) the d r i f t -c o e f f i c i e n t s , i s the d r i f t vector. The nxn matrix °f elements o~- (x,t) the d i f f u s i o n c o e f f i c i e n t s , i s the d i f f u s i o n matrix. The c o r r e l a t i o n between the i - t h and the j-th component is' defined by CU: ISA) Corresponding to each d i f f u s i o n , there e x i s t s an i n f i n i t e s i m a l operator - on the class of twice continuously d i f f e r e n t i a b l e functions of the form (3) 7 The i n f i n i t e s i m a l o p e r a t o r has the .following i n t e r p r e t a t i o n . Let f ( • ) be a f u n c t i o n d e f i n e d on the sample paths of the d i f f u s i o n . Then Af {•) can be thought of as t h e expected time r a t e of change o f f (•)... The d r i f t c o e f f i c i e n t s and the d i f f u s i o n c o e f f i c i e n t s have the f o l l o w i n g i n t e r p r e t a t i o n . , I f T)A - x, then f o r s m a l l 6>0r DA<.6 - x i s d i s t r i b u t e d a c c o r d i n g t o the n-dimensional normal d i s t r i b u t i o n H{ | A(x,t ) 6 , £(x,t ) 6 | . C o n d i t i o n s (4)- (5) are imposed on the d r i f t and d i f f u s i o n c o e f f i c i e n t s t o ensure the e x i s t e n c e of a d i f f u s i o n c orresponding to (3)[9,p.162 ].{[13 rp.32] g i v e analogous e x i s t e n c e c o n d i t i o n s which are more r e s t r i c t i v e ) . (Q) u._(x,t) , (x#t) ( i , j=1,... ,n) are bounded and s a t i s f y a Hdlder c o n d i t i o n on B, t>0. (5) t h e r e e x i s t s a p o s i t i v e constant ^ such t h a t , f o r a l l x € B, t>0 and a l l n - t u p l e s (\, ,... rA n) o f r e a l numbers, U cr. (x,t) XLX- > i L X_ I f an i n f i n i t e s i m a l o p e r a t o r . A, s a t i s f i e s c o n d i t i o n s (5) a t x,t , then i t i s a non-degenerate o p e r a t o r at x , t . Otherwise i t i s a degenerate operator., For i n s t a n c e c o n d i t i o n (5) i s v i o l a t e d i f p-u.t) - i L - , I f 1 i s i t g t n e r a t e f o r a l l x i n B and t«I, then some component(s) of the d i f f u s i o n process are d e t e r m i n i s t i c f u n c t i o n s o f the other components. Thus the d i f f u s i o n process can be re p r e s e n t e d by another d i f f u s i o n 8 process of lower dimension. For example, i f D t i s a degenerate d i f f u s i o n process i n TRZ, then knowledge o f one component of Dt completely s p e c i f i e s the other component. Thus D t, a d i f f u s i o n process i n ^ , cam be r e p r e s e n t e d by another d i f f u s i o n process i n TR1 . . Se now d i s c u s s t h e behaviour o f d i f f u s i o n processes on a B . To t r e a t t h i s t o p i c p r o p e r l y dB should be a s u f f i c i e n t l y smooth s u r f a c e so t h a t the n o t i o n s i n t r o d u c e d below make sense. The behaviour o f d i f f u s i o n process may be m o d i f i e d by imposing boundary c o n d i t i o n s on 9B. W e n t z e l l [ 2 3 ] has shown t h a t the p o s s i b l e behaviours near the boundaries a r e t e r m i n a t i o n , r e f l e c t i o n , adhesion, jump and any s u i t a b l e combination o f these behaviour. , With each type o f boundary behaviour, t h e r e i s a corresponding c o n d i t i o n on the d i f f u s i o n process. T h i s correspondes to r e s t r i c t i n g the domain o f the i n f i n i t e s i m a l o p e rator (3), For i n s t a n c e , i f i n a d d i t i o n t o r e g u i r i n g t h a t the domain i n c l u d e a l l t w i c e c o n t i n u o u s l y d i f f e r e n t i a b l e f u n c t i o n s f on B , we r e g u i r e that f ( x ) = 0 on 9B, then the process w i l l t e rminate upon r e a c h i n g the boundary., I f we r e g u i r e t h a t t h e normal d e r i v a t i v e o f f (x) - 0 on aB , the process w i l l be r e f l e c t e d at t h e p o i n t of c o n t a c t on dB. These two c o n d i t i o n s are of c o n s i d e r a b l e importance i n our study. 9 Us. Hodel D e s c r i p t i o n find Renewal S t r u c t u r e We now r e s t r i c t our a t t e n t i o n t o H . L e t { D ^ , t > 0 , i > 1 } be a sequence o f i . i . d . (independent and i d e n t i c a l l y d i s t r i b u t e d ) two-dimensional d i f f u s i o n processes with a negative d r i f t vector.... The process D4 i s allowed t o take v a l u e s i n B ^ JR2 . Assume t h a t t h e process i s time homogeneous, i . e . , the t r a n s i t i o n p r o b a b i l i t i e s are s t a t i o n a r y i n time. Mathematically t h i s means P(s,x,t,A) = P ( t - s , x , A ) , }MZ,t) - J M U ^ and U x , t ) = H ( x ) , i • . . Let D_ , t h e i n i t i a l p o s i t i o n of the i - t h process, be S = ( S ^ S ^ ) f o r a l l i > 1. The process D_ r e p r e s e n t the stock l e v e l d u r i n g the i - t h c y c l e . A s t o p p i n g c r i t e r i o n i s imposed on t h a t when s a t i s f i e d , t e rminates . In the i n v e n t o r y context, t h i s correspondes t o p l a c i n g an order t o r e p l e n i s h the s t o c k on hand. The s e t of p o i n t s t h a t s a t i s f i e s t h e s t o p p i n g c r i t e r i o n i s the s t o p p i n g curve. In the i n v e n t o r y context i t i s a l s o r e f e r e d to as the recorder curve. L e t a seguence of random v a r i a b l e s { T. , i > 1 } be d e f i n e d by T_ = i n f { t > T__, : D^ . e s t o p p i n g curve } , i > 1 where T c eguals zero. T_ i s a s t o p p i n g time f o r D<.. A d d i t i o n a l assumptions w i l l be made i n S e c t i o n 5 t o ensure t h a t ET_ < 00 . Define the process I t by v t = K * T.., < t < T. . Y t r e p r e s e n t s the stock l e v e l at time t . The parameters o f the 10 two dimensional d i f f u s i o n process can be i n t e r p r e t e d as f o l l o w s . The d r i f t v e c t o r r e p r e s e n t s the net demand r a t e o f the two products, the d i a g o n a l elements o f the d i f f u s i o n matrix r e p r e s e n t s the demand v a r i a t i o n per u n i t time of each product, and •• p.. (x) - ( 5 ) / j & i i x ) ^jj"'- i s t h e c o r r e l a t i o n between the mean demand r a t e of the two products., D i f f u s i o n processes allow p o s i t i v e increments even though the d r i f t i s n e g a t i v e , i . e . , the net demand i n s m a l l time i n t e r v a l s may be p o s i t i v e even though the average demand i s n e g a t i v e . However, f o r l a r g e i n t e r v a l s such r e v e r s a l s are very improbable., The economic parameters o f the system a r e as f o l l o w s . There i s a f i x e d c o s t ft > 0 o f r e - o r d e r i n g and a v a r i a b l e c o s t gf«) t h a t depends on the q u a n t i t i e s r e - o r d e r e d . There a l s o i s a c o s t c(x) per u n i t time the stock l e v e l i s x. I n S e c t i o n 5 c o n d i t i o n s on c{x) and g(x) are presented to ensure t h a t the expected shortage and h o l d i n g c o s t s per c y c l e and the expected v a r i a b l e c o s t per c y c l e w i l l be f i n i t e . , Note t h a t the sequence ( T_, i •> 1 } c o n s t i t u t e r e q e n e r a t i o n p o i n t s f o r the process { Y t, t > 0 }. Thus the process Yt can be viewed as a sequence o f i . i . d . c y c l e s , where each c y c l e c o n s i s t s o f a s o j o u r n from S, the i n i t i a l p o s i t i o n , to the s t o p p i n q curve., T h i n k i n g of t h e problem t h i s way a l l o w s r e s u l t s from the t h e o r y o f r e g e n e r a t i v e processes t o be a p p l i e d ; c f , , Boss£22j|. fts a consequence, the lonq-run average c o s t can be e v a l u a t e d by d i v i d i n g the expected c o s t per r e g e n e r a t i o n c y c l e by the expected l e n g t h o f t h e r e g e n e r a t i o n c y c l e . Let the random f u n c t i o n C { t ) , the c o s t i n c u r r e d i n [ 0 , t ] , be d e f i n e d by 11 where N(t) i s the number o f replenishments i n [ ® , t ] , f-L i s the stopping time of the i - t h s o j o u r n , and e s t o p p i n g curve i s the t e r m i n a t i n g p o s i t i o n o f T t on the i - t h sojourn. „• The f o l l o w i n g theorem f o l l o w s from p r o p o s i t i o n 5.9 of Ross(22,p.98]. Theorem 1 A I f E $ T, < oo , E s j" c(Yu) du < co , — • o and E s g (x^ ) < <*> , then with p r o b a b i l i t y one. The r e s u l t i s a l s o v a l i d i f r e p l a c e s ~~!jr Here E_ denotes the e x p e c t a t i o n with r e s p e c t t o a process s t a r t i n g a t S, i . e . , I 0 = (S_,S_). The l i m i t i n g p r o b a b i l i t y of being i n a s e t Q not on the boundary can a l s o be obtained by u s i n g the i n d i c a t o r o f Q as the s t o c k l e v e l c o s t f u n c t i o n and s e t t i n g K and the v a r i a b l e c o s t egual t o zero* Let the l i m i t i n (7) be denoted by 9 . 0 depends on the s t o p p i n g curve i m p l i c i t e l y through the the random v a r i a b l e Tt . He w i l l study two c l a s s e s o f o p e r a t i n g p o l i c i e s . One i s the two-dimensional analog o f the (s,S) p o l i c y - the (s, ,s, ,S. ,S, ) 12 p o l i c y . a t y p i c a l c o n t r o l r e g i o n o f the ( s x , s_ , S_ , S_ ) p o l i c y i s shown i n F i g . 1 . , The jagged l i n e i n d i c a t e s the e v o l u t i o n o f the stock l e v e l over time u n t i l i t i s necessary t o r e - o r d e r . I t s s t a r t i n g p o s i t i o n i s (S_,S Z) and i t terminated when the supply of the goods reached ( x T , y _ ) . One of the o b j e c t i v e s w i l l be t o f i n d t he va l u e s of s_ , sz, S_ and Sz t h a t minimize © . The modified p o l i c y d i f f e r s from the (s±,s_,S_,SZ) p o l i c y i n t h a t the lower l e v e l s , st and s_, are coupled v i a an e l l i p t i c a r c . a t y p i c a l c o n t r o l r e g i o n i s shown i n F i g . 2 . There e x i s t s an important d i f f e r e n c e between one dimensional and two dim e n s i o n a l p r o c e s s e s . I n one dimension the v a r i a b l e c o s t of a (s,S) p o l i c y i s not a random f u n c t i o n because the r e - o r d e r p o i n t i s a s i n g l e t o n s e t , i . e . , Y-r = s. However, i n two dimensions Y T i s s t o c h a s t i c thus the v a r i a b l e c o s t i s a random function.„ T h i s d i f f e r e n c e a r i s e s because the p o i n t a t which the process reaches t h e boundary i s not determined i n advance. F i g . 1. A C o n t r o l Region Of The (st ,sz ,S_ ,SZ ) P o l i c y Fig.2. a C o n t r o l Region Of The M o d i f i e d P o l i c y 1U 5. Eva1nation Of The Long-ran Average Cost Let the f u n c t i o n c(x,y) mapping B <k TR 1 t o be the shortage and h o l d i n g c o s t r a t e f u n c t i o n . Define V(x,y,s) f o r (x,y) e B and se[0,oo) by T h i s i s the expected shortage and h o l d i n g c o s t from time s onward given t h a t D A = x = (x,y) . l e f o r m a l l y show t h a t ?(x,y*s) s a t i s f i e s a nonhomogeneous Kolmogorov backward eguation on the i n t e r i o r of B. A r i g o r o u s proof of t h i s r e s u l t i s an easy conseguence of Theorem 5.1 of Dynkin [9,p. 132], The proof here i s i n the s p i r i t o f Chernoff [ 5 ] and g i v e s i n s i g h t i n t o the meaning of the model parameters. Let the process d r i f t f o r an i n f i n i t e s i m a l time 6 , a c o s t c ( x ,y ) S i s i n c u r r e d , and the process d r i f t s t o T>Ati . Thus assuming V(x,y,s) i s s u f f i c i e n t l y d i f f e r e n t i a b l e t o apply T a y l o r ' s theorem. where V, H denotes t h e g r a d i e n t and the Hessian o p e r a t o r s r e s p e c t i v e l y and s u p e r s c r i p t T denote transpose. Hence -r t Bearranging terms d i v i d i n g both s i d e s by 6 and a p p l y i n g (2) y i e l d s & Taking l i m i t as 6 approaches 0 , 16 provided the d e r i v a t i v e s are r i g h t - c o n t i n u o u s with r e s p e c t t o s. T h i s i s the backward equation because the time d e r i v a t i v e i s with r e s p e c t to s, the i n i t i a l time. The analogous forward equation i s d e r i v e d s i m i l a r l y , see [ 1 2 ] . S i n c e the process i s time homogeneous, (the d r i f t v e c t o r and t h e d i f f u s i o n matrix are independent of t i m e ) , V(x,y,s) i s constant i n s and the l e f t hand s i d e of (8) i s zero. L e t t i n g V (x,y) be V(x,y,0), t h i s y i e l d s the f o l l o w i n g eguation t h i s i s shorthand f o r the p a r t i a l d i f f e r e n t i a l e g u a t i o n which together with the f o l l o w i n g boundary c o n d i t i o n s determines the expected c o s t . The d i f f u s i o n process i s r e g u i r e d t o terminate on r e a c h i n g the s t o p p i n g c u r v e , t h e r e f o r e (10) i s imposed on the d i f f u s i o n 1 7 do) V (x) = 0 f o r x & s t o p p i n g curve., t h i s c o n d i t i o n i s i n t u i t i v e l y s a t i s f y i n g s i n c e i f the stock l e v e l s t a r t s out on the s t o p p i n g curve T, = 0 and no c o s t w i l l be i n c u r r e d d u r i n g t h e c y c l e , a d d i t i o n a l boundary c o n d i t i o n are needed at i n f i n i t y t o u n i q u e l y determine s o l u t i o n s t o (9). Below are two dimensional analogs of the r e s u l t of Puteraan [ 2 1 ] . e 1 5 ? £ < x ' ^ - 0 Um. These c o n d i t i o n s say t h a t the growth of V(x,y) i s e x p o n e n t i a l l y bounded. (11) i s a l s o t h e c o n d i t i o n on V(x,y) i f r e f l e c t i n g boundaries i f placed near i n f i n i t y , c.f.[4]« I f the c o s t r a t e , c ( x ) , i s s e t e g u a l t o one, then We denote t h i s expected sojourn l e n g t h by T|x,y). The expected v a r i a b l e c o s t i n c u r r e d i n one C y e i t given t h a t DQ = ( x , y ) , denoted by Z ( x , y ) , i s the s o l u t i o n o f the f o l l o w i n g p a r t i a l d i f f e r e n t i a l eguation Al L*>V - ° ttz.) SUBJECT To it<K,v - 3«V3> £ cB ftHV (.11) flfP/-l£D TO ZcK.y . 18 Thus a l l the e x p e c t a t i o n s t h a t are needed t o c a l c u l a t e the lo n g -run average c o s t r a t e can be computed by s o l v i n g the f o l l o w i n g p a r t i a l d i f f e r e n t i a l eguations. s a e j £ c T T o ( \o~) } c 11") . SUBTEST To (10)- , Cll) dPPi-lEP To T<r*,3) -t 5ugjecT To f i l j AfpLlEP To £1*,$) 19 To apply Theorem 1 we need s u f f i c i e n t c o n d i t i o n s to ensure that the s o l u t i o n s of the above p a r t i a l d i f f e r e n t i a l e g u ations are f i n i t e . . I f the s o l u t i o n s of the p a r t i a l d i f f e r e n t i a l e guations are indeed f i n i t e (by o b t a i n i n g and examining the s o l u t i o n s ) , then the expected val u e s of shortage and h o l d i n g c o s t per s o j o u r n , sojourn l e n g t h , and v a r i a b l e c o s t i n c u r r e d per sojourn are f i n i t e . The f o l l o w i n g c o n d i t i o n s g i v e a n a l y t i c c o n d i t i o n s t o ensure t h a t the s o l u t i o n s of (13) are f i n i t e . Let G » , G 2 denote A + A a1 . , sL. + sL r e s p e c t i v e l y . , Assume G»M-# G2p., G*R, G 2 R e x i s t and are continuous where R i s the square r o o t o f L ., Let c(») have two continuous d e r i v a t i v e s and OS) \CT1C\ 6 ( i + ixi ? } i = u where a 1 , a 2 , b*, b 2 , a 1 , <*2» fi, and p 2 are c o n s t a n t s . Then by 20 Theorem 5.5 of Friedman £ 11,-p. 122], V(x,y) has two continuous d e r i v a t i v e s and t h e r e f o r e i t i s a l s o continuous. Thus f o r any f i n i t e (x,y) , V(x,y) i s f i n i t e . From p a r t i a l d i f f e r e n t i a l equation theory £ 8 ] , the maximum a t t a i n e d a c t u a l l y occurs on the boundary.„The f u n c t i o n c(x,y) = 1 s a t i s f i e s (15) t r i v i a l l y . T h e r e f o r e , T(x,y) i s f i n i t e f o r f i n i t e (x,y) i f the d i f f u s i o n process s a t i s f i e s (11). Since the v a r i a b l e c o s t g(x,y) i s i n c u r r e d o n l y from r e o r d e r i n g , i f g(•) i s f i n i t e f o r f i n i t e ( x , y ) , then Z(x,y) i s f i n i t e . 21 6. .-, Hethods Of S o l u t i o n The problem we study i s t h a t o f s o l v i n g t h e t h r e e p a r t i a l d i f f e r e n t i a l eguations i n (13). Each p a r t i a l d i f f e r e n t i a l eguation i s a boundary v a l u e problem and i s e l l i p t i c i f the c o r r e l a t i o n of the two d i f f u s i o n s i s not ±1 (non-degenerate) and i s p a r a b o l i c i f the c o r r e l a t i o n i s egual t o ±1 (degenerate). There are four main technigues a v a i l a b l e f o r s o l v i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n s . , They are t r a n s f o r m methods, e i g e n f u n c t i o n methods. Green's f u n c t i o n methods, and numerical methods. Each method w i l l be c o n s i d e r e d i n terms of i t s a p p l i c a b i l i t y t o the problem.„, The c l a s s i c a l F o u r i e r and L a p l a c e transform methods are g e n e r a l l y used i n s o l v i n g problems i n v o l v i n g i n f i n i t e or semi-i n f i n i t e r e g i o n s , c . f . [ 8 ] , f 20 ]. T y p i c a l l y one assumes t h a t the f u n c t i o n v a l u e s and the d e r i v a t i v e s a t i n f i n i t y are e g u a l t o z e r o . However, due the presence of t h e f i r s t order d e r i v a t i v e (the d r i f t term), the transforms of the p a r t i a l d i f f e r e n t i a l eguations i n (13) a l l i n v o l v e the f u n c t i o n value a t i n f i n i t y . S i n c e V(x,y), T ( x , y ) , and Z ( x , y ) a r e the expected shortage and h o l d i n g c o s t d u r i n g one s o j o u r n , s o j o u r n l e n g t h , and v a r i a b l e r e o r d e r i n g c o s t per s o j o u r n , we cannot set the f u n c t i o n value a t i n f i n i t y t o z e r o . In f a c t we expect i t t o be i n f i n i t e . Thus transform methods does not seem t o be a p p r o p r i a t e . The method of e i g e n f u n c t i o n s u s u a l l y a r i s e s when the p a r t i a l d i f f e r e n t i a l equation i s s e p a r a b l e i n a s u i t a b l e c o o r d i n a t e system i n a f i n i t e domain, i . e . , by seeking s o l u t i o n s of the form F* (•)?*(*) where F* (•) , F 2(») a r e f u n c t i o n s o f the two c o o r d i n a t e s o n l y , the p a r t i a l d i f f e r e n t i a l e g u a t i o n can be 2 2 reduced t o separate o r d i n a r y d i f f e r e n t i a l e guations, c f . [ 8 ] . For the ( s ^ s ^ ,S± ,5^) p o l i c y , the r e g i o n i s r e c t a n g u l a r thus the C a r t e s i a n c o o r d i n a t e system i s the n a t u r a l c o o r d i n a t e system. However, the p a r t i a l d i f f e r e n t i a l eguation i s not sepa r a b l e i n the C a r t e s i a n c o o r d i n a t e system u n l e s s the c o v a r i a n c e of the d i f f u s i o n process i s zero { independent d i f f u s i o n s ). Given that the c o v a r i a n c e i s z e r o , the c o n t r o l r e g i o n may be made f i n i t e by r e p l a c i n g (11) with (16) c s „ 3) 6 .:.'B t h i s correspondes t o p l a c i n g b a r r i e r s a t x=S1 and y=S i. However, (10), (16) a r e not s u i t a b l e because t h e r e does not e x i s t any r e c t a n g u l a r harmonics ( e i g e n f u n c t i o n s ) r e l a t i v e to them. Rectangular harmonics of (13) i n v o l v e t r i g o n o m e t r i c f u n c t i o n s i n one c o o r d i n a t e and h y p e r t r i g o n o m e t r i c f u n c t i o n s i n the other.„ The t r i g o n o m e t r i c f u n c t i o n s can be made t o f i t (10),(16), but the h y p e r t r i g o n o m e t r i c f u n c t i o n s cannot. T h e r e f o r e , e i g e n f u n c t i o n methods do not y i e l d s o l u t i o n s . ft Green*s f u n c t i o n i s an apparatus t o sol v e g e n e r a l p a r t i a l d i f f e r e n t i a l e g u a t i o n s , c.f.£8], £ 2 0 ] . R e p l a c i n g the non-homogeneous r i g h t hand s i d e o f the p a r t i a l d i f f e r e n t i a l eguation with a d e l t a or sou r c e f u n c t i o n , the s o l u t i o n i s the Green's f u n c t i o n of the p a r t i a l d i f f e r e n t i a l equation., The s o l u t i o n t o the o r i g i n a l eguation i s o b t a i n e d by i n t e g r a t i n g the non-av ( S,, = o CIG) 3\l ( "S* ) - e> 23 homogeneous term with the Green's f u n c t i o n over the r e g i o n . Green's f u n c t i o n s a r e known f o r standard p a r t i a l d i f f e r e n t i a l e guations with n i c e boundary c o n d i t i o n s * However, t o o b t a i n the Green's f u n c t i o n f o r (13) with boundary c o n d i t i o n s (10), (11) o r (10) (16) may be j u s t as d i f f i c u l t as t h e o r i g i n a l problem i f not more, and one o b t a i n s o n l y an i n t e g r a l r e p r e s e n t a t i o n o f the s o l u t i o n which may not be i n t e g r a b l e i n c l o s e d form., Thus although Green's f u n c t i o n method w i l l y i e l d a ' s o l u t i o n ' , i t i s not e a s i l y o b t a i n a b l e and does not h e l p us i n s o l v i n g the problem. Where c l a s s i c a l a n a l y s i s methods f a i l , n u merical a n a l y s i s come i n . , There are two main types of technigues used i n s o l v i n g p a r t i a l d i f f e r e n t i a l equations. They are f i n i t e d i f f e r e n c e and f i n i t e element ( c o l l o c a t i o n ) . They both r e q u i r e f i n i t e r e g i o n s . Thus boundary c o n d i t i o n s (10),(16) are used. The method of f i n i t e element works as f o l l o w s . F i r s t , the r e g i o n i s p a r t i t i o n e d i n t o a number o f c e l l s . , Then a s o l u t i o n b a s i s u s u a l l y c o n s i s t i n g of Hermite polynomials i s chosen i n each c e l l t o r e p r e s e n t the s o l u t i o n . The p a r t i a l d i f f e r e n t i a l o p e r a t o r i s then a p p l i e d t o each c e l l which y i e l d s a system of a l g e b r a i c eguations t h a t determines the c o e f f i c i e n t s of the s o l u t i o n b a s i s i n each c e l l . One a l s o has to impose c o n d i t i o n s on the boundaries o f the c e l l s t o ensure the c o n t i n u i t y of t h e s o l u t i o n , and/or the d e r i v a t i v e s . Once the c o e f f i c i e n t s i n each c e l l i s know, the s o l u t i o n i n the whole r e g i o n i s known. F i n i t e d i f f e r e n c e , u n l i k e f i n i t e element, only c o n s i d e r s the f u n e t i o n v a l u e at d i s c r e t e p o i n t s i n the r e g i o n . I t approximates the d e r i v a t i v e s by s u i t a b l e ' f i n i t e * d i f f e r e n c e s , c.f.CVI* f 161. 24 T h i s r e s u l t s i n an a l g e b r a i c system which when s o l v e d , y i e l d s the approximate f u n c t i o n v a l u e s at the d i s c r e t e p o i n t s c o n s i d e r e d . One of the advantages of numerical methods i s t h a t approximate s o l u t i o n s can be obtained when the r e g i o n i s i r r e g u l a r l y shaped and/or when the problem i s a n a l y t i c a l l y u n t r a c t a b l e . , The method o f f i n i t e d i f f e r e n c e i s used t o s o l v e the p a r t i a l d i f f e r e n t i a l equations i n (13) s u b j e c t t o (10)* (16). As mentioned p r e v i o u s l y , d i f f u s i o n processes allow p o s i t i v e increments even though t h e d r i f t i s negat i v e , however, f o r l a r g e time i n t e r v a l s such r e v e r s a l s are very improbable. Thus r e p l a c i n g (11) by (16) and changing from a s e m i - i n f i n i t e r e g i o n to a f i n i t e r e g i o n may not be a bad approximation. „. A l s o i f t h e r a t i o o f d r i f t t o v a r i a n c e i s l a r g e , i . e . , the system does not have great v a r i a t i o n s , the p r o b a b i l i t y of such r e v e r s a l s f o r any given time i n t e r v a l i s e x c e e d i n g l y s m a l l . , 25 Is. -r The ( s ^ s ^ S ^ S ^ - P o l i c y In t h i s s e c t i o n , the ( s 1 , s z , S 1 , s z ) p o l i c y i s examined. He w i l l r e s t r i c t o u r s e l v e s t o t h e c l a s s of spatially-homogeneous d i f f u s i o n processes i n our computations, i . e . , the d r i f t and d i f f u s i o n c o e f f i c i e n t s are s c a l a r c o n s t i n t s and the i n f i n i t e s i l a l ©pefator i s given by R e c a l l from S e c t i o n 3 t h a t the d r i f t v e c t o r , ( u.,, u.J, i s n e g a t i v e . . We w i l l a l s o assume t h a t g(x,y) = 0 f o r ease o f computation. Our o b j e c t i v e i s t o o b t a i n 6 f o r a s e t of given system parameters : p., # s, , sz, S( , Sz, c ( x , y ) , K, and study the e f f e c t s of d i f f e r e n t parameter values on Q , „ A code was developed which, u t i l i z i n g the method of f i n i t e d i f f e r e n c e , c a l c u l a t e s the o p t i m a l long-run average c o s t r a t e o f a s p e c i f i e d d i f f u s i o n and c o s t s t r u c t u r e f o r a s p e c i f i e d stopping curve, i . e . , i t determines an o p t i m a l r e o r d e r p o i n t S t, S^ f o r a f i x e d boundary x = s a , y = sz . Soundary c o n d i t i o n s (10), (16) are used i n the computation, (16) has an a d d i t i o n a l s i d e b e n e f i t o f being one of the necessary c o n d i t i o n s of o p t i m a l i t y . The code works as f o l l o w s . The program has as i t s i n p u t JA , L » s ( , sz, c ( x , y ) , K, and t r i a l v alues of S, , S, . 26 (1) V ( x r y ) , the expected shortage and h o l d i n g c o s t per s o j o u r n g i v e n t h a t D Q = (x,y) 4 and T ( x , y ) ; the expected s o j o u r n l e n g t h g i v e n t h a t D Q = (x,y) are c a l c u l a t e d by s o l v i n g the f o l l o w i n g d i f f e r e n t i a l eguations. i u B j ' E c T To C103 o k ) . (Il) + ju2 ^c*x.-3) - - 1 To (|<0 ., (l(>) To Tcxjp . These p a r t i a l d i f f e r e n t i a l e g u ations are s o l v e d by the method o f f i n i t e d i f f e r e n c e . A g r i d i s chosen f o r the new c o n t r o l r e g i o n bounded by the s t o p p i n g c u r v e , x = s t # y B s^, and the r e f l e c t i n g boundaries x=Sx , y=S z on which approximate values o f V(x ry) and T(x,y) are c a l c u l a t e d at t h e g r i d p o i n t s . See the 27 appendix f o r d e t a i l s o f the c a l c u l a t i o n . „ (2) The long run average c o s t r a t e g i v e n that Dc = (x,y) , Q , i s c a l c u l a t e d by f c <*,y ) (3) The minimum 6 on the g r i d i s found by s e a r c h i n g the g r i d s e g u e n t i a l l y . (4) I f t h i s o p t i m a l 6 i s p o s i t i o n e d on the boundary, the b i n d i n g boundary(s) i s r e l a x e d by i n c r e a s i n g S t and/or Sz and steps (1) , (2) and (3) are repeat e d . Step {4} i s repeated u n t i l the optimum i s found t o be s t r i c t l y i n the i n t e r i o r . .: Step (5) i s then performed. (5) The g r i d i s shrunk by r e d u c i n g S 1 and/or S z t o place the r e f l e c t i n g boundaries at t h i s optimum p o s i t i o n and steps <1), (2), (3) are repeated., T h i s s h r i n k i n g process continues u n t i l the p o s i t i o n of the optimum remained s t a t i o n a r y , i . e . , t h e p o s i t i o n o f the o p t i m a l d i d not change from one i t e r a t i o n of step (1)i (2), (3) to the next. T h i s value i s taken t o be the o p t i m a l long-run average c o s t r a t e f o r a f i x e d s t o p p i n g curve. I t i s denoted by 28 ^ ( s ^ f S ^ ) and the optimal Sx a r e denoted by Sx ,'sa (the dependence of Q{s±,sZj) on |A, H , c(x,y) and K and the dependence of S, , on s, are suppressed i n the n o t a t i o n ) . The g l o b a l o p t i m a l v a l u e s o f s x ,sz -,S ,SZ and © are denoted by ,^§^ ,5 ,S 4 and 6 and are found by i t e r a t i v e l y r e p e a t i n g the above process with d i f f e r e n t sx, s^ v a l u e s . Table 1 demonstrates t h e s e a r c h o f a g l o b a l o p t i m a l (s. ,s, ,S, ,S, ) the f i n i t e d i f f e r e n c e scheme used t o approximate s o l u t i o n s of (17) i s presented i n t h e appendix along with a d i s c u s s i o n o f the e r r o r s i n v o l v e d . & sample output i s shown i n Fig.3. In order to v e r i f y the code, we c o n s i d e r t h e s p e c i a l case o f symmetric d i f f u s i o n • , i . e . , p.,., 6~„ = 6n_ t and a c o r r e l a t i o n of +1. The i n f i n i t e s i m a l g e n e r a t o r , a, i s degenerate and because the two dimensional d i f f u s i o n i s symmetric, i t c o l l a p s e s t o an one-dimensional d i f f u s i o n . , Puterman [21} has i n v e s t i g a t e d the one-dimensional model i n d e t a i l , and f o r t h e case of g u a d r a t i c c o s t r a t e , a n a l y t i c r e s u l t s were ob t a i n e d i n c l o s e d form. T h i s was used t o v e r i f y t h e code. I t was observed t h a t on the average, the numerical s o l u t i o n , 0 , agrees with the t h e o r e t i c a l r e s u l t t o 0.08%. , The f o l l o w i n g summarizes our main f i n d i n g s . , fhe d i f f u s i o n parameters used t o o b t a i n the r e s u l t s below were chosen f o r numerical e f f i c i e n c y and to r e p r e s e n t moderate v a r i a t i o n . They are as f o l l o w s . D r i f t c o e f f i c i e n t s : (Xt = [A?. = -2 d i f f u s i o n c o e f f i c i e n t s : di, = ^ = 1 , pet-1,1} 29 the f i x e d r e - o r d e r i n g c o s t used i s 125/12. For (1)-(5) the c o s t s t r u c t u r e used i s c(x,y) = ax 2+by 2, where a =b = 1/2., T h i s s e p a r a b l e c o s t s t r u s t u r e a l l o w s comparisons with the one-dimensional r e s u l t s . R e c a l l t h a t p i s the c o r r e l a t i o n between the two mean demand r a t e s and i s d e f i n e d by The f o l l o w i n g q u a l i t a t i v e r e s u l t s summarize the numerical computations f o r the above data., 1) §{s, ,s^) i s convex with r e s p e c t t o ( s ^ s ^ ) f o r p e f~1»1]« T h i s i s demonstrated i n F i g . a , , Puterraan has shown t h a t 6(s f S ) i s convex with r e s p e c t t o s,S f o r g u a i r a t i c h o l d i n g c o s t i n one dimension. T h i s p r o p e r t y c a r r i e s over t o two dimensions. We expect the c o n v e x i t y property to c a r r y over t o higher dimensions as w e l l . .. 2) B (s, » S 2 . ) i n c r e a s e s as p decreases from 1 t o -1 f o r a f i x e d s t o p p i n g curve., T h i s i s demonstrated i n F i g . 5 . T h i s r e s u l t i s expected because as the c o r r e l a t i o n decreases from +1 t o -1, t i e d i f f u s i o a sample paths become more e r r a t i c , the v a r i a t i o n of the system g e n e r a l l y i n c r e a s e s thus i n c r e a s i n g the c o s t of o p e r a t i n g the system. 30 3) As K i n c r e a s e s , s, , sz, the optimal values of s, , sz decrease. T h i s i s because vhen computing the o p t i m a l p o l i c y , we t r y t o balance the shortage and h o l d i n g c o s t s a g a i n s t the r e - o r d e r c o s t . As the r e - o r d e r c o s t i n c r e a s e s i t i s b e t t e r t o r e - o r d e r l e s s f r e q u e n t l y thus S.-s. , 1=1,2 i n c r e a s e s lowering s^,s^ and i n c r e a s i n g S 1 #S Z.,.' Si n c e t h e process can have p o s i t i v e iner@mtnts, i t i s expected t h a t sx and s z decrease more than S t and Sz i n c r e a s e . A l t e r n a t i v e l y i f c (x,y) i n c r e a s e s we expect the opposite to occur. The important g u a n t i t y i s the r a t i o o f K t o c ( x , y ) . T h i s i s analogous to the one-dimensional r e s u l t . 4) As p decreases from 1 t o -1, and sz decreases as w e l l . T h i s i s a l s o demonstrated i n F i g . 4 . T h i s i s expected from the i n t u i t i o n t h a t i n general the system t r i e s t o co u n t e r a c t more v a r i a t i o n by lowering s^,sz, 5) For (s, ,3^) > (s, ,sz) , S, ,S t i s symmetric, i . e . , S, = s\ , i f the d i f f u s i o n i s symmetric. i' \.' " v. . For ( s ^ s ^ ) < ( s ^ s . J , i t i s p o s s i b l e t h a t S, # S^. T h i s r e s u l t s i n • s p l i t t i n g * , i . e . , the o p t i m a l v a l u e s a re no longer on the main d i a g o n a l , but on the minor d i a g o n a l s . T h i s i s d e p i c t e d i n Fig.6. Once s p l i t t i n g has ocurred, moving ( s i r s z ) f u r t h e r away from (s^,s^) r e s u l t s i n the optimal minor d i a g o n a l s moving f u r t h e r away from the main d i a g o n a l . 6) As (s, ,s, ) > (s, ,s „) decrease toward (s, , s , ) , S~s. i n c r e a s e s . . T h i s t r e n d c o n t i n u e s a f t e r ( s 1 , s 2 ) pass through ( s ^ , ^ ) . 31 7) S-s i n c r e a s e s as p decreases from *1 t o -1. 8) He were unable t o p r e d i c t the e f f e c t o f unequal v a r i a n c e s f o r a f i x e d s t o p p i n g curve. T h i s i s shown i n F i g . 7 . , For some c e r r e l a t i o n s eu.,*>increased as one o f the v a r i a n c e s decreased and yet f o r other c o r r e l a t i o n s the o p p o s i t e i s t r u e . , However, F i g . 7 again demonstrates t h a t as t h e c o r r e l a t i o n d e c r e a s e d , ^ u . ^ i n c r t a s e s . 3) For the case o f unequal v a r i a n c e s , 0) a l s o holds and § ^ # 5 ^ are r e l a t i v e l y i n s e n s i t i v e t o changes i n one o f the v a r i a n c e s . , R e s u l t s 10) -11) are obtained using c(x,y) = (ax+by) 2, where a = b = 1/2., T h i s c o s t s t r u c t u r e i s not s e p a r a b l e and the system e x h i b i t s some q u i t e d i f f e r e n t behaviour from the p r e v i o u s c o s t s t r u c t u r e . 10) The s p l i t t i n g e f f e c t i s sharp. For ( s ^ s ^ ) < (s± 0sz) , s p l i t t i n g always occur, t h i s i s not the case with the pr e v i o u s c o s t s t r u c t u r e . , The d i f f e r e n c e may stem from the f a c t t h a t the i s o - c o s t contours of the present c o s t s t r u c t u r e i s open while the i s o - c o s t contours o f t h e pre v i o u s c o s t s t r u c t u r e i s c l o s e d . , 11) fts ( s t , s z ) move away from ( s l f s j i n e i t h e r d i r e c t i o n , §-s decreases. T h i s i s o p p o s i t e t o 6 ) . „ • 32 Table 1 demonstrates a search f o r a g l o b a l optimal ( s ^ , s ^ , S ^ ) p o l i c y . 0 search of a g l o b a l o p t i m a l ( s 1 # s 7 # S . , rS„) p o l i c y -L A* 1_ 2t fx, = ^ -- -Z (7,, - 0\T- = 1 p - O C C * , V = ^ o c 1 + j ^ /< =• 125 / 12. A. - Z.fS 7. i f - a.is 7-oZ - 3oS - 3.35 -- 3 f 5 6.^ 7 - 4. 25 7-/6 - 4oo 7?o Q£IIML_ £ l * £ J]_LJQJd££_&^ CONVEXITY TE SF , RUN i PAGE ^ 3V" ] P . O . E . COEFFICIENTS | FA- * .,... J > SIGMA X = .1.000 MUX = 2 .000 COVARIANCE = 1 . 000 SIGMA Y = 1 .0 00 MUY = 2 . 0 0 0 % %. j peU^ ] COST STRUCTURE 1 CX = 5 .00C000OE -01 CY = 5 . 0 0 0 0 0 0 0 E - 0 1 SWITCHING COST = 1.0416667E+01 | GRID EXPANSION PARAMETERS I INCREMENTAL EXPANSION = 5 MULTIPLICATIVE EXPANSION •= 1.5000000E+00 I RELAXATION ITERATION PARAMETERS 1 OVER—RELAXATICN PARAMETER = 1.31666666667 MAXIMUM ITERATIONS IS 100 COARSE RESIDUE TOLERANCE = 1.O0QQ000E-O4 FINE RESIDUE TOLERANCE = LOOOOOOOE-IO | PROGRAM OUTPUTS j THE SMALLEST 10 AV COST RATES WILL BE PRINTED RELAXATION GRIO # 1 SPECIFICATIONS X = ( - 1 . 2 5 C 0 0 , 3 . 2 5 0 0 0 ) X STEP = 0 . 2 5 0 0 0 Y = I - 1 . 2 5 0 0 0 , 3 . 2 5 0 0 0 ) Y STEP = 0 . 2 5 0 0 0 CQSI CALC.ULAIIQC1 10 20 24 9 . 4 8 4 4 1 2 1 0 6 9 2 7 7 E - 0 3 3 . 1 1 1 0 6 9 2 9 4 1 9 9 9 E - 0 4 8 . 6 0 4 4 4 9 7 8 3 2 8 9 1 E - 0 5 > OEIIM&L_£Ii<£fi_LflM£_£fJ^^ CONVEX I TY TEST , RUN 1 : ; " ' R E S I D U E T O L E R A N C E ' R E ACHED PAGE -ir 3H c< > I IHE £AL£ULAIIQ£1 IIEJLA.IIQN MZ &£S.ifiU£ Il^_YALiJ£S • \ 10 20 2.5 3.73574914L5377E-04 7.,6 513 613 215.1 57E-05 RESIDUE TOLERANCE REACHED **** * * * * * * * * * * * * RESULTS * *** ************ O E E i x 2.5G0OO 2.50000 7.8730045108869E+00 2 2.7500 0 2.75000 7.8998892208495E+00 7 4 2.50000 2.75000 2.50000 7.9238585043857E+00 5 . 2.25000 2.25000 7.9355819042445E*00 : T 6 7 2. 25000 2.50000 2.25000 7.9486021501625E+00 8 1C 2.75000 3.00000 3.00000 7.9621402733680E+00 3.00000 7.9767611645190E+00 * * * * * * * * * : * * * * * : * * * * * 4 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * RELAXATION GRIO # 2 SPECIFICATIONS X = ( -1.25000 , \2. 75000 .. } X STEP = 0.25000 . Y =' ( -1.25000 , 2. 75000 ) Y STEP = 0.25000 C.QSJL _£AL£ U L A H Q N a£IIMAL_E12££_Lfi^^ CONVEXITY TEST , RUN 1 PAGE - 3 ^ 3 ^ JIIRAOQN 10 20 2.0432203265300E-03 6.4440346613322E-05 . < > 30 40 50 1.63931932 87063E-06 9.4073375679028E-08 5.3210086263802E-09 64 9.0133496437466E-11 RESIDUE TOLERANCE . REACHED ' JLIEBAIIQN MX E££1DU£ IN VALUES 10 20 30 .1.7546 274.152017E-04 1.8517977703692E-06 5.5760024150214E-08 50 53 2.2269430804449E-10 9.3586155024946E-1I RESIDUE TOLERANCE REACHED * RESULTS * **** alM i 2.50000. 2.50000 7.92000887I5692E+00 " . • 2 2 .25COO 2.25000 7.9678791384453E+00 3 4 '2.50000 2.25000 7.9709026498949E+00 5 2.00000 2.25000 8.0893637971261E+00 6 1 2.25000 2.00000 2.00000 8.1262956914557E+00 8 2.00000 2.50000 8.1533888501528E+00 9 1G 1.75000 2.00000 8.3245074271854E+00 BOUNDARY RECTANGLE HAS BEEN FOUND *** OPFBRC5 *** • J V 1 • : " . . . 35 36 3 1 - l o I-a F i g . 5. E f f e c t s Of C o r r e l a t i o n On (WjFor The (s 1 , s z ,S1 ) p o l i c y . F i g . 6 . The Phenomenon Of S p l i t t i n g For The <s i rs^,S 1 ,S,^ ) p o l i c y . <3"„= I o.if o & o.g (.a Fig.7., Effects Of Unequal Variance 39 8*.The Mo d i f i e d P o l i c y T h i s p o l i c y i s d e s c r i b e d by s i x parameters; St , Sz, (x°,y°) the c e n t e r o f the e l l i p s e , and ( x ^ y ^ ) t h e l e n g t h o f the a x i s . Note that i f x°, y° = s J # s^ and x K =y r = 0 t h i s reduces the modified p o l i c y to the ( s : L , s ^ , S 1 # S 2 ) p o l i c y c o n s i d e r e d i n the prev i o u s s e c t i o n . As with the ( s a , s x ,S t , ) p o l i c y , we have a computer code which e v a l u a t e t h e long run average c o s t f o r a given p o l i c y . The program has as i t s input the f o l l o w i n g parameters: ^ , £» , c ( x , y ) , K, x ° , y ° , xY, y r , S± , Sz. R e f l e c t i n g boundaries again are imposed a t x = S 1 # y = Sz. T h i s code has been observed t o have accuracy o f the o r d e r o f 0.3%. A sample output i s shown i n F i g . 8 . The f o l l o w i n g summarizes our f i n d i n g s . R e s u l t s 1)-5) are obtained using c(x,y) = ax 2+by 2 with a = b = 1/2. 1) e i s convex with r e s p e c t t o (x y r,y y r) f o r p e [ - 1 , 1 ] . , T h i s i s demonstrated i n Fig . 9 f o r t hs case o f f>= 0. 2) 0 i n c r e a s e s as p decreases from 1 to -1 f o r a f i x e d p o l i c y . T h i s i s demonstrated i n Fig. 1 0 . T h i s i s c o n s i s t e n t with r e s u l t s from the ( s 1 # s z , S 1 , S Z ) p o l i c y . , 3) As K i n c r e a s e s , xy,jy. i n c r e a s e s . tt) The modified p o l i c y i s at l e a s t as cheap as t h e ( s 1 ,sz,S1 .S^ ) p o l i c y i f not cheaper. y 5) The modified p o l i c y seems t o be l e s s s e n s i t i v e t o changes t o 40 R e s u l t s 6)-7) are o b t a i n e d u s i n g c(x,y) = (ax+by) 2 with a = b = 1/2. , 6) Ss p decreased from +1 t o -1, the m o d i f i e d p o l i c y does p r o g r e s s i v e l y b e t t e r than the • (s1,sz,S1 ,Sz) p o l i c y . For the data used, a t p= 0, i t i s at l e a s t 3.751 b e t t e r * and a t p- -1, i t i s at l e a s t 5.7% b e t t e r . 7) 6 i s g u i t e i n s e n s i t i v e t o the c o r r e l a t i o n . The r e s u l t s show t h a t the modified p o l i c y i s b e t t e r than the (s. ,s, ,S ,S„) p o l i c y , e s p e c i a l l y i f the products a r e s u b s t i t u t a b l e . The i n p l e m e n t a t i o n o f t h i s p o l i c y i s not d i f f i c u l t . The user merely checks the i n v e n t o r y on hand and compares i t t o a c h a r t which s p e c i f i e s the o p t i m a l s t o p p i n g curve. I f the i n v e n t o r y i s lower than as s p e c i f i e d on the c h a r t , an order i s p l a c e d t o b r i n g the stock up t o (S 1,S 1-)... The numerical r e s u l t s o b t a i n e d depends on the c o s t s t r u c t u r e used. F o r c(x,y) •= ax* • by*, the i s o c o s t c o n t o u r s are c l o s e d e l l i p s e s * w h i l e the i s o c o s t contours o f c(x,y) = (ax+by) 2 are s t r a i g h t l i n e s . Se suspect t h i s d i f f e r e n c e l e a d t o o b s e r v a t i o n (11) of the p r e v i o u s s e c t i o n , however the dependence of 9 on t h i s d i f f e r e n c e i s s t i l l u n resolved. £LLI£i£_y_£ES.LQM_I EFFECTS OF PARTIAL CORRELATION FOR THE CURVED POLICY RUN 1 PAGE I P.O.E. COEFFICIENTS SIGMA X SIGMA Y = 1.000 MUX = 2.000 COVARIANCE = 0.750 1.000 MUY = 2.000 I REGION SPECIFICATIONS I UX = 2.50000 UY = 2.50000 XCNTR = 2.50000 YCNTR = 2 .50000 XAXIS = 7.42462 YAXIS = 7.42462 BOUNDARY CLOSENESS TOLERANCE = 1.OOOOOOOOOOOOOE-10 I COST STRUCTURE 1 CX = 5.0000000E-01 CY = 5.0000000E-01 SWITCHING COST = 1.0416667E+0 1 1 RELAXATION ITERATION PARAMETERS I OVER-RELAXATION PARAMETER 1 . 3 1 6 6 6666667 MAXIMUM ITERATIONS IS 100 RESIDUE TOLERANCE = 1.000000OE-10 | PROGRAM OUTPUTS i THE SMALLEST 30 AV COST RATES WILL BE PRINTED ***** LI ST PROCESSING ***** X 4.75000 1 1.00000 E£EE£iEtiIA.IIQ^ 00110110 •4.-7 500 0 •4.75000 •4.75000 1.25000 1.5000C 1.75000 001001.10 CO 100 110 .0010.0110 -4.75000 •4.75000 •4. 5000 0 2.COOOC 2.25000 0.25000 001 00 110 001 00 n o 00110110 EFFECTS OF PARTIAL CORRELATION FOR THE CURVED POLICY RUN 1 PAGE 2^ f./*. \ > > -4.50000 -4.50000 -4.50000 0. 50000 C.150CG 1.00000 00100110 G0100010 000 00010 J -4.25000 -4.25000 -4.25000 . -0. 5000 0 -0.25000 00110110 00100110 < -4.25000 -4.00000 -4.00000 0.25000 -1.00000 -0.75000 000000.10 C O l l O l l O 00100010 -4.00000 -3.75000 -3.75000 -0.50000 -1 . 5000 0 -1.25000 COOOOOlO C O l l O l l O 0010001 o -3.75000 -3.50000 • -3.50000 -1.00000 -1.75000 -1.50000 COOOOOlO C0I10010 000 00010 -3.25000 -3.25000 _ -3.00000 -2.COOOO -1.75000 -2.25000 00110010' COOOOOlO 0O11OO10 -3.00000 -2.75000 -2.75000 -2.OOOOG -2.5000 0 -2.25000 00000010 00110010 00000010 -2.50000 -2.50000 -2.7 500C -2.50000 00110010 00000010 -2.25000 -2.00000 -2.00000 -2.75000 -3.25000 -3.0000 0 COOOOOlO 00110010 000 00010 -1.75000 - 1.75000 - 1.50000 - 3 . 5000 0 -3.25000 C0110010 boooooio -1.50000 - 1.25000' -1.00000 -3.5000 0 -3.75000 -4.OOOCO COOOOOlO 00010010 00110011 -1.00000 - 0.75000 -0.50000 ' -3.75000 -4.0000 0 COOOOOlO 00010010 -0.50000 -0.25000 0.00000 -4.00000 -4.2500C -4.25000 COOOOOlO 00010011 G0010010 0.25000 0,25000 0.50000 -4.5000G -4.25000 00110011 GOO 00010 0.75000 1.00000 1.00000 -4.50 00 0 , -4.75000 -4.50GOG 000 10010 001 10 011 COOOOOlO 1.25000 1.50000 1.75000 -4.75000 -4.75000 000 10011 000 10011 2.00000 2.25000 2.50000 -4. 75000 -4.75000 -4.7500 0 000 10011 COOlOOll COO 10011 QQSI-. __QAJXULATION i ITERATION. MAX &E5I0JJE IN_VALiJ£S J ELLLRSE_Y£&SLQN„1 EFFECTS OF PARTIAL CORRELATION FOR THE CURVED POLICY RUN 1 PAGE V — 10 20 30 3.3709873202146E-l.2937C9 8960727E-1.86 86657003130F-03 05 0 7 j < 40 3.0607594178849E- 09 < RESIDUE TOLERANCE REACHED IIEBA.IIQN &AX.££Simj£_IM_^ALU£S 10 1.6458520708152E-03 30 40 4.303851 1746120E-5. 82 82 092 9741 98E-08 10 RESIDUE TOLERANCE REACHED *************** , *************** 1 ££££C_I£D CILSI R.AI£ 1 2.25000 2.25000 6. 376223 6261 967F, +00 2 2.00000 2.25000 6. 39 99 80 7 554 75 9E + 00 .3 2.25000 2*00000 6. 4007983741 412E+00 4 2 .00000 5 1.75000 2.25000 6.46 46 047751 437E+00 6 2.25000 1.75 000 6. 4665788742431E+00 7 1.75000 2.00 000 6.4704844214667E +00 8 2.00000 1.75 000 6.4715061315665E+00 9 1 .75000 1.75000 6. 513881651672 7E +00 10 1.50000 2.00000 6.57 19224401619E +00 11 2.00000 1.50000 6. 57 41 694 846 51 IE+0 0 12 1 .50000 2.25000 6.5755267937 302E+00 13 2.25000 1.50000 6. 57 90 064921 22 7E +0 0 >-14 1.50000 1.75000 6.60 28 828347546E+00 EFFECTS OF PARTIAL CORRELATION FOR THE CURVED POLICY RUN 1 1.75000 1 .50000 6.60 39099342 572E+00 PAGE X > ^ 17 1 .25000 •L . J VJ U \J U 2.00000 6. 72 233 8 80 86 66 2E+0 0 : < 18 2.00000 1.25000 6.726176661018 IE+00 19 1.25000 2.25 000 6. 73 48 224551 38IF+0 0 20 2.25000 1.2 5000 6. 74030441 97 599E+00 21 1.25000 1.75000 6.7415214486472E+00 22' 1 .75000 1.25000 6. 7437387537597E+00 23 1 .25000 1.50000 6.805968069262 IE+00 24 1.50000 1.25000 6.80692 51968559E+00 25 1 .25000 1.2 5000 6.9206084498766F+0 0 26 1.00000 2.00000 6. 9229437070352E+00 27 2.00000 1.00 000 6, 92 89 353109 676E + 00 2 8 1.00000 1.75000 6.9312592347342E+00 29 1.75000 1.00000 6. 93 50479 883 355E+00 30 1.00000 2.25000 6.9436045691489E+00 EXECUTION TERMINATED ***** ELLIPSE VERSION I ***** 3SSIG ' • ' ' . ' • ' . . . ' • . ' ' p 4 I tcl; Fig.9. The Convexity Of The H o a i f i e d P o l i c y . e p F i g . 1 0 . Effects of c o r r e l a t i o n on the modified policy 44 9. Recommendations For Future Research The case o f a f i x e d l e n g t h lagged d e l i v e r y can be accomodated e a s i l y i n t h e present model. Let L > 0 be the time l a g between the time a r e - o r d e r i s decided and t h e time the a c t u a l replenishment o c c u r s . In the i n v e n t o r y c o n t e x t , t h i s may be thought o f as the d e l i v e r y time or the p r o d u c t i o n setup time., The cumulative demand i n the time i n t e r v a l <t,t+L] i s Y t + L - T t , which by the s t a t i o n a r i t y of the d i f f u s i o n process, has the same c o n d i t i o n a l d i s t r i b u t i o n as I L - Y0 . Furthermore, i f the demand i s s p a t i a l l y homogeneous, then Ya can be s e t t o z e r o . D e f i n i n g £(•) by c (y) = c t y * ! ^ ) , t h i s i s the expected c o s t L time u n i t s i n the f u t u r e . , To o b t a i n r e s u l t s f o r t h i s model, one simply r e p l a c e c(») by c(«) i n (2). The t e r m i n a t i n g d i s t r i b u t i o n o f the d i f f u s i o n path on t h e s t o p p i n g curve can be o b t a i n e d by s o l v i n g the f o l l o w i n g p a r t i a l d i f f e r e n t i a l e g u a t i o n : S U < 3 7 £ c - | T O T o o 3 3 = 1 O O } ) £ I Q where I Q i s the i n d i c a t o r of t h e s e t Q which i s p a r t of the boundary., P(x,y) i s the p r o b a b i l i t y t h a t D T £ Ta g i v e n t h a t D0 = <x,y). Knowledge of t h i s t e r m i n a t i n g d i s t r i b u t i o n should r e v e a l g r e a t i n s i g h t t o the behaviour of t h e d i f f u s i o n paths. Through the backward e g u a t i o n we were ab l e t o c h a r a c t e r i z e the long-run average c o s t r a t e of o p e r a t i n g the i n v e n t o r y system, and c a l c u l a t e the expected v a r i a b l e r e - o r d e r i n g c o s t . 45 Programs have been developed which can c a l c u l a t e the expected v a r i a b l e c o s t , Z ( x,y), and the t e r m i n a t i n g d i s t r i b u t i o n of the d i f f u s i o n paths, P(x,y).> Other problems such as d i f f e r e n t c o s t s t r u c t u r e s can and should b# i n v e s t i g a t e d f u r t h e r to r e v e a l the u n d e r l y i n g dynamics o f m u l t i - d i m e n s i o n a l d i f f u s i o n processes. A very important and s t i l l unanswered g u e s t i o n i s what i s the form of t h e o p t i m a l p o l i c y . In t h i s r e s e a r c h i t was assumed t h a t the order t o p o i n t , S, i s independent of the t e r m i n a t i n g p o s i t i o n of the sojourns on the s t o p p i n g curve. , In f a c t , t h e o p t i m a l p o l i c y may be to order t o a p o i n t t h a t depends on the t e r m i n a t i n g p o s i t i o n o f the s o j o u r n s . , An important problem from the a p p l i c a t i o n p o i n t of view i s t h a t of the e s t i m a t i o n of the d i f f u s i o n parameters, t h i s problem has not yet been i n v e s t i g a t e d . , T h i s myriad o f g u e s t i o n s remain t o be answered. 46 References [ 1 ] E. Sngel and R. Bellman, * Dynamic Programming and P a r t i a l D i f f e r e n t i a l Eguations*, (academic P r e s s , New York, 1969). [21 L. a r n o l d , • S t o c h a s t i c D i f f e r e n t i a l Equations: Theory and a p p l i c a t i o n * , (John Wiley & Sons, Inc., New York, 1974). [ 3 ] J . Bather, *a d i f f u s i o n model f o r the c o n t r o l of a dam*, J . appl . Prob. 5(1968) 55-71. [ 4 ] L. Breiman, ' P r o b a b i l i t y * , (Addison-Wesley, Reading, Massachusetts, 1968). [ 5 ] H. C h e r n o f f , 'Optimal S t o c h a s t i c C o n t r o l * , Sankhya: The Indian J o u r n a l of S t a t i s t i c s , S e r i e s a, vol.30, part 3, 221-252. [ 6 ] G.M. C o n s t a n t i n i d e s and S.F. Ri c h a r d , E x i s t e n c e o f Optimal Simple P o l i c i e s f o r Discounted-Cost Inventory and Cash Management i n Continuous Time*, Management Science Research Paper No.. 379, Graduate School of I n d u s t r i a l a d m i n i s t r a t i o n , Carnegie-Mellon U n i v e r s i t y , 1977. [ 7 ] Courant and H i l b e r t , •Methods of Mathematical P h y s i c s * , ( I n t e r s c i e n c e P u b l i s h e r s , New York, 1962). [ 8 ] G.F.D. Duff and D. Naylor, * D i f f e r e n t i a l Eguations o f A p p l i e d Mathematics*, (John Wiley S Sons, I n c . , New York, 1966). [9} E.B. Dynkin, *Markov Processes I , I I * , (Academic Press I n c . , P u b l i s h e r s , Sew York, 1965). [10] D. Freedman, 'Brownian Motion and D i f f u s i o n * , ( Holden-Day, San F r a n c i s c o , 1971). [ 1 1 ] ft. Friedman, ' S t o c h a s t i c D i f f e r e n t i a l Equations and a p p l i c a t i o n s Volume 1,2*, (Academic P r e s s , San F r a n c i s c o , 1976). [12] I . I . Gikhman and A.V. Skorohod, »Introduction to the Theory of Random Processes*, (W.B., Saunders, P h i l a d e l p h i a , 1969) [ 1 3 ] I . I . Gikhman and a.V. Skorohod, 'The Theory of S t o c h a s t i c processes I I * , ( S p r i n g e r - V e r l a g , New York, 1975). [14] J . Gimon, » a continuous time i n v e n t o r y model*. T e c h n i c a l Report No.29, Department of S t a t i s t i c s , S t a n f o r d U n i v e r s i t y ( 1 9 6 7 ) . [15] T.E. Goswick and B.D. S i v a z l i a n , 'The Mixed Or d e r i n g P o l i c y In P e r i o d i c Review S t o c h a s t i c Multi-commodity Inventory Systems', Naval Research L o g i s t i c s Q u a r t e r l y , V o l . 21, Ho.3, Sept. 1974, p.389-410. 47 [16] D. Greenspan, * I n t r o d u c t o r y Numerical A n a l y s i s of E l l i p t i c Boundary Value Problems', (Harper and Row, P u b l i s h e r s , New York, 1965). [17] E.Y. I g n a l l , 'Optimal continuous review p o l i c i e s f o r two product i n v e n t o r y systems with j o i n t set-up c o s t s ' . Management Science 15, No.5, Jan 1969, p.278-283. [18] P. Mandl, ' A n a l y t i c a l Treatment o f One-Dimensional Harkov Processes', ( S p r i n g e r - V e r l a g , New York, 1968)., [19] A.B. M i t c h e l l , 'Computational Methods i n P a r t i a l D i f f e r e n t i a l E guations', (John Wiley & Sons, I n c . , New York, 1969) . [ 2 0 ] P.M.. Morse and H. Feshbach, 'Methods of T h e o r e t i c a l P h y s i c s ' , (McGraw-Hill Book Company, Inc., Toronto, 1953). [21 ] M.L. Puterman, *A D i f f u s i o n Process Model f o r a Storage System', L o g i s t i c s , Volume 1, North loll a n a i / T i m s S t u d i e s i n the Management S c i e n c e s , M . G e i s s l e r , ed. 1975, p.143-156. [22] S,B. Ross, ' A p p l i e d P r o b a b i l i t y Models with O p t i m i z a t i o n A p p l i c a t i o n s ' , (Holden-Day, San F r a n c i s c o , 1970). [23] A.D. W e n t z e l l , *0n boundary c o n d i t i o n s f o r m u l t i -dimensional d i f f u s i o n processes', ( i n R u s s i a n ) , Teor. Veroyatnost. i Primenen. 4, p.172-185(1959). 48 APPENDIX The purpose of t h i s appendix i s t o present the computational scheme used to s o l v e ( 9 ) s u b j e c t t o (16) -(16). „ The method used i s the method o f f i n i t e d i f f e r e n c e . The main i d e a i s t o r e p l a c e the d e r i v a t i v e s by s m a l l f i n i t e d i f f e r e n c e s which approximate the d e r i v a t i v e s on a mesh obtained by d i s c r e t i z i n g the r e g i o n of i n t e r e s t . • Given a p a r t i a l d i f f e r e n t i a l e g uation of the form M** *B0,V •CU y y •DUx*BUv+FO = g(x,y) c o n s i d e r the f o l l o w i n g aiMrEOiSl s t a r approximation of d e r i v a t i v e s . . F i g . 1 1 . The Nine-point S t a r Approximation Of D e r i v a t i v e s 49 The p o i n t s are numbered 0 to 8 with the d i s t a n c e s as shown i n F i g . J 1 . These d i s t a n c e s were chosen t o allow f o r i r r e g u l a r g r i d p o i n t s ( p o i n t s with unequal d i s t a n c e s t o i t s neighbour points) which occurs near the s t o p p i n g curve o f the modified p o l i c y . L e t the f u n c t i o n v a l u e s a t t h e nine p o i n t s be 0°,...,U 8. Constants k°,.,,,k* are t o be determined such t h a t Z l k L n L = AUXX +B0xy *C0 y y +D0X +E0 +FD = g(X,y) (18) T a y l o r expanding 0J , j=1,...,8 about U°, and c o l l e c t i n g the terras y i e l d s the f o l l o w i n g system of 6 eguations with 9 unknowns. ko+ki+k2+k3*k*+ks+k*+k*+k«» = F h » k » - h 3 k 3 + h s » k s - h * * k * - h » i k * * h * i k « » = D h ? k 2 - h * k * + h S 2 ] c s « . h * 2 k « - h 7 2 k 7 - h » 2 k 8 = E ( h * ) Z k * + ( h 3 ) 2 k 3 * ( h s » ) 2 k 5 * ( l » * * ) k * + ( h T i ) 2 k ' * ( h « i ) 2 k « = 2A f h 2 ) 2 k 2 * ( h ^ ) 2 k * + ( h s * ) 2 k s * ( h * * ) k * * ( h ^ * ) 2 k 7 + ( i i 8 * ) 2 k 8 = 2C h s i h S 2 k s-h*>h* 2 k*+h^»h ^ 2 k 7 - h 8»h* 2 k 8 = B T h i s system as i t stands i s indeterminate, t h e r e f o r e 3 more independent equations are added. KS+k*>kT+k« = 0 B s i fcs_h**k<»-h7*k**h « i»k« = o h 5 2 k s + h * 2 k * - h * * k ' , - h « * k 8 = 0 50 These eguations serve to e l i m i n a t e the c o n t r i b n t a t i o n s of p o i n t s 5, 6, 7, 8 to the c o e f f i c i e n t s o f the f i n i t e d i f f e r e n c e term which r e p r e s e n t the f i r s t order d e r i v a t i v e s . L e t hsa/ h s i = h 7 2 / h * » = r * h 6 2 / h « i = h « 2 / h « i = r 2 The s o l u t i o n t o t h i s system i s F-k* - k 2 - k 3 - k * k* = [ 2 A + D h 3 - K » ]/[h* (h » * h 3 ) ] k 2 = [2C+Eh»-K 2 ]/[ h 2(h 2+h*)] ks = [2A-Dh*-K * M h 3(h* + h 3 ) 1 k* •= [2C-Eh 2-K 2]/[hMh 2 + h*) ] ks = B/{fhsih^*r *+h«»h**r 2 ](1*hsi/h^*)} k* = -B/C [ h s i h 7 i r*+h**h«»r 2l(1*h«*/ha»)} XT B/{[hsih**r**h«»h*»r 2 ](1*h**/h S 1)} k » = -B/ { [ h 5*h 7*r*+h«»h»»r 2](1*h»Vh*»)} where K* = (hst) 2 Ks+ (h»») ak** (h*») 2k*+ (h*») 2k» K 2 = (hsz) 2 k s * (h« 2) 2k*+ (h* 2) 2k*+ (h» 2) 2k« S u b s t i t u t i n g these c o e f f i c i e n t s i n t o (18) reduces the problem t o an a l g e b r a i c system by r e g u i r i n g t h i s formula t o hold f o r a l l 0° i n the i n t e r i o r o f B*. T h i s a l g e b r a i c system i s most c o n v e n i e n t l y s o l v e d by the method o f s u c c e s s i v e o v e r - r e l a x a t i o n , c f . , [ 1 5 ] . , The system can be w r i t t e n as 51 Ax = b where A i s a banded matrix and b i s g(x,y) at the g r i d p o i n t s . Using the c o e f f i c i e n t s d e r i v e d above and s u c c e s s i v e over-r e l a x a t i o n , approximate s o l u t i o n s to t h e p a r t i a l d i f f e r e n t i a l eguations of (13) can be o b t a i n e d . , T h i s approximation has a t r u n c a t i o n e r r o r o f the order o(h') from the f i n i t e T a y l o r expansion. T h i s e r r o r can be reduced by t a k i n g h s m a l l . Greenspan p r o v i d e s c o n d i t i o n s on the c o e f f i c i e n t s , k°,.... ,k 8, t h a t guarantees the a l g e b r a i c system w i l l converge and s a t i s f y t he weak max-min property t h a t the a n a l y t i c s o l u t i o n posses, c . f . [ 1 5 ] . „-

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0094229/manifest

Comment

Related Items