برنامه ریزی و کنترل تولید و موجودی‌ها

باسمه تعالی برنامه ریزی پویا – روش پیشرو ‏Dynamic ‏Programming برنامه ریزی و کنترل تولید و موجودی ها استاد :دکتر مهدوی ‏Forward ‏Approach تهیه کننده :سعید امینی دستور العمل پیشرو -بدون سفارشات عقب افتاده های M jk هزینه ت ول ید در دور ه j+1ج هتار ضاء ت قاضا هایدور ه : )(j = 0, 1,…T-1 ; k = j+1, j+2,…, T ‏j + 1, j + 2, j + 3…,k های گهدار یم وجود یو ت ول ید ا س .ت M jk ش ام لهزینه ن انتهای دوره jو انتهای دوره kنقاط شروع مجدد هستند .یعنی Ij = 0و Ik = 0 دستور العمل پیشرو -بدون سفارشات عقب افتاده در نتیجه: ‏k +…D ‏j+2 +D ‏j+1 =D ‏j+1 ‏X ‏I t = X j+1 - بنا بر این: ت هینه ب را یدور ه های k ,… ,2 ,1د ال لتدارد ب ه ش رط آ ن که I k = 0ب اشد .در ا ینصور :ت F kب ر هزینه س یاس ب , F0 =Fk دستور العمل پیشرو -بدون سفارشات عقب افتاده = Fk رابطه فوق معادل پیدا کردن کوتاهترین مسیر در یک شبکه است. ‏M04 4 ‏M34 ‏M03 3 ‏M23 ‏M24 ‏M13 ‏M14 ‏M02 2 ‏M12 1 ‏M01 0 دستور العمل پیشرو -بدون سفارشات عقب افتاده برای مرتب کردن روش محاسبه α jk ،را به عنوان هزینه بهینه برای دوره های ( k…1,2,3یک افق kدوره ای) تعریف می کنیم که در آن : ‏ J+1 آ خریندور ه ت ول ید ی عنی X j+1 > 0و در اینصورت: دستور العمل پیشرو -بدون سفارشات عقب افتاده در یک افق kدوره ای ،نقطه شروع مجدد قبلی بهینه ) j* (kاست که با رابطه زیر تعریف می شود: برای یک افق kدوره ای ،نقطه شروع مجدد قبلی بهینه ) j* (kبوده که با رابطه زیر تعریف می شود: برای هر نقطه مجدد kداده شده ،می توان نقطه شروع مجدد قبلی بهینه ،kیعنی ) j*(kرا که در آن سطح موجودی برابر صفر بوده ،پیدا نمود .به عبات دیگر آخرین تولید در دوره j*(k)+1اتفاق می افتد .با شروع از k = Tو استفاده از روش پسرو می توان نقاط شروع مجدد را در حل بهینه مشخص کرد. در صورتیکه کمبود مجز نباشد ،هزینه های تولید و نگهداری موجودی دارای شکل زیر هستند: )Ct(Xt دستور العمل پیشرو -بدون سفارشات عقب افتاده ‏α0T ‏α1T ‏α2T . . . ‏αT-1 T ‏FT )j * (T … … … … نقطه شروع مجدد افق برنامه ریزی ()k 1 2 3 قبلی ()j ‏α01 α02 α03 0 ‏α12 α13 1 ‏α23 2α . . . ‏T-1 ‏F3 )j*(3 ‏F2 )j*(2 ‏F1 )j*(1 دوره آخرین تولید ()j+1 1 2 3 . . . ‏T ‏Fk =min Xjk ]) [j* (kنقطه شروع مجدد قبلی دستور العمل پیشرو -بدون سفارشات عقب افتاده هزینه نگهداری یک واحد محصول در یک دوره هزینه متغیر هر واحد محصول هزینه راه اندازی تقاضای پیش بینی شده دوره ‏t ‏Dt ‏At ‏ct ‏ht 2 3 30 20 1 2 1 3 4 40 30 30 40 2 3 1 4 50 30 4 دستور العمل پیشرو -بدون سفارشات عقب افتاده ابتدا مساله را یک دوره ای در نظر بگیرید (:)k = 1 ‏M01 = A1 + c1 D1 = 30 + (3)(20) = 90 ‏F1 = α01 = F0 + M01 = 0 + 90 = 90 جواب: ‏j* (1) = 0 and X*1 = 20 دستور العمل پیشرو -بدون سفارشات عقب افتاده سپس مساله را دو دوره ای در نظر بگیرید (:)k = 2 ‏M02 = A1 + c1 (D1 +D2) + h1 D2 = 30 + (3) (20 + 30) + (2) (30) = 240 ‏M12 = A2 + c2 D2 = 40 + (3) (30)= 130 = F0 + M02 = 0 + 240 = 240 ‏α02 = F1 + M12 = 90 + 130 = 220 ‏α12 ‏F2 = min جواب: ‏F2 = 220, j* (2) = 1 and X*1 = 20 , X*2 = 30 دستور العمل پیشرو -بدون سفارشات عقب افتاده برای مساله 3دوره ای ( )k = 3داریم: ‏M03 = A1 + c1 (D1 +D2 + D3) + h1 (D2 + D3) + h2 D3 = 520 ‏M13 = A2 + c2 (D2 + D3) + h2 D3 = 330 ‏M23 = A3 + c3 D3 = 190 ‏α03 = F0 + M03 = 0 + 520= 520 ‏α13 = F1 + M13 = 90+ 330= 420 ‏α23 = F2 + M23 = 220+ 190= 410 ‏F2 = min جواب ‏ F3 = 410, j* (3) = 2 and X*1 = 20 , X*2 = 30 , X*3 = 40  بدون سفارشات عقب افتاده- دستور العمل پیشرو M04 M14 M24 M34 = = = = A1 A2 A3 A4 + + + + c1 c2 c3 c4 :) داریمk = 4( دوره ای4 برای مساله (D1 +D2 + D3 + D4 ) + h1 (D2 + D3 + D4) + h2 (D3 + D4) + h3 D4 = 760 (D2 + D3 + D4 ) + h2 (D3 + D4) + h3 D4 = 510 (D3 + D4) + h3 D4 = 340 D4 = 170 α04 = F0 + M03 = 0 + 520= 520 α13 = F1 + M13 = 90+ 330= 420 F3 = min α23 = F2 + M23 = 220+ 190= 410 α23 = F2 + M23 = 220+ 190= 410 جواب  F3 = 410, j* (3) = 2 and X*1 = 20 , X*2 = 30 , X*3 = 40 دستور العمل پیشرو -بدون سفارشات عقب افتاده به ازای k = 4آخرین نقطه شروع مجدد بهینه 2بوده،یعنی I*3 = D4 = 30و X*3 = D3 + D4 = 70 I*2 = 0و X*4 = 0ا س .ت از آنجا که موجودی در دوره 2صفر بوده K = 2 ،قرار می دهیم و پی می بریم که نطقه شروع مجدد قبلی بهینه 1است پس I*1 = 0و X*2 = D2 = 30است. به ازای k = 1و j*(1) = 0و در نتیجه X*1 = D1 = 20 دستور العمل پیشرو -سفارشات عقب افتاده مجاز است موقعی که کمبود مجاز بوده و سفارشاتی که با کمبود موجودی مواجه می شوند بعدا جبران گردند ،موجودی خالص It ،ممکن است مقادیر منفی بگیرد. فرض کنیم: )- (It ‏Kt (Xt,It) = Ct (Xt) ++H+ ‏t (It) -+ Ht سیاست تولید بهینه دارای این خاصیت است که حداقل دو تا از سه کمیت It-1و Itو Xtصفر خواهند بود .به عبارت دیگر تقاضا در هر دوره tکامال از موجودی (تولید در دوره های قبلی) یا کامال از سفارشات عقب افتاده (تولید در دوره های آینده) یا کامال از تولید در دوره ف تامین می گردد. دستور العمل پیشرو -سفارشات عقب افتاده مجاز است اگر تولید در دوره tصورت پذیرد و j<tو k>tنزدیکترین نقاط شروع مجدد باشند (:)Ik = 0 , Ij = 0 الزم به تذکر است که اگر jو kدو نقطه شروع متوالی باشند دقیقا یک دوره مانند tموجود بوده که j<t<kموجود بوده که در آن تولید صورت می گیرد. M jkح دا ق لهزینه ت ول ید ا س ت انتهای دوره jو انتهای دوره kنقاط شروع مجدد هستند .یعنی Ij = 0و Ik = 0 ‏C j+1 (D j+1), if k = j+1 = M jk + , for k >j +1 - - + + ‏min دستور العمل پیشرو -سفارشات عقب افتاده مجاز است ‏for l = j+1, j+2,…, t-1 =  It ‏for l = t, t+1,…, k-1 ‏ It + = معادله برگشتی پیشرو به صورت زیر خواهد بود: ‏for k = 1,2,…,T ‏Fk = [Fj + Mjk] = [] , دستور العمل پیشرو -سفارشات عقب افتاده مجاز است مثال قبل را با فرض مجاز بودن سفارشات عقب افتاده حل می کنیم. تابع جریمه سفارش های عقب افتاده به صورت زیر تعریف می شود: ‏Ht- (It-) = 𝞹t I-t ‏𝞹1 = 1 , 𝞹2 = 1 , 𝞹3 = 2 , 𝞹4 = 2 اولین قدم ،محاسبه M jkبه ازای k = 1,2,3,4و تمامی مقادیر j<kاست. t* (j,k) دور ه ب هینه ت ول ید ب ین jو kخ وا هد ب ود.  سفارشات عقب افتاده مجاز است- دستور العمل پیشرو  M01 = C1 D1 = 90; t* (0,1) = 1 + C1 (D1 +D2) + H1 (D2) = 240  M02 = min (0,2) = 2 - = 210; t* C2 (D1 +D2) + H1 (D2) = 210 + +  M03 = min C1 (D1 +D2 + - D3) ++H1 (D2 + D3) + H2 D3 = 520 C2 (D1 +D2 + D3)- + H1 D- 1 + H2 D3 = 410 C3 (D1 +D2 + D3) + H1 D1 + H2 (D1 + D2) = 460 = 410; t* (0,3) = 2  سفارشات عقب افتاده مجاز است- دستور العمل پیشرو = 760  M04 = min = 780 = 590; t* (0,4) = 2 + + + C1 ( ) + H1 (D2 +D3 + D4) +H2 (D3 + D4) + H3 (D4) - + + C2 ( ) + H1 (D1) + H2 (D3 + D4) + H3 (D4) = 590 + C3 ( ) + H1 (D1) + H2 (D1 + D2) + H3 (D4) = 610 C4 ( ) + H1 (D1) + H2 (D1 + D2) + H3 (D2 +D3 + D4)  سفارشات عقب افتاده مجاز است- دستور العمل پیشرو  M12 = C2 D2 = 130; t* (1,2) = 2 + 3) + H2 (D3) = 330 C2 (D2 +D  M13 = min (1,3) = 2 = 330; t* - C3 (D2 +D3) + H2 (D2) = 340 +  M14 = min + C2 (D2 +D3 + - D4) ++H2 (D3 + D4) + H2 D3 = 510 C3 (D2 +D3 + D4)- + H2 D- 2 + H3 D4 = 490 C4 (D2 +D3 + D4) + H2 D2 + H3 (D2 + D3) = 620 = 590; t* (1,4) = 3 دستور العمل پیشرو -سفارشات عقب افتاده مجاز است ‏ M23 = C3 D3 = 190; t* (2,3) = 3 + ‏C3 (D3 +D4) + H3 (D4) = 340 *= 340; t - ‏ M24 = min (2,4) = 3 ‏C4 (D3 +D4) + H3 (D3) = 410 ‏M34 = C4 D4 = 170; t* (3,4) = 4 دستور العمل پیشرو -سفارشات عقب افتاده مجاز است دوره تولید ()t ‏Mjk )t*(j,k 90 1 210 2 410 2 590 2 130 2 330 2 490 3 190 3 340 3 410 170 4 170 4 780 620 1 نقطه شروع مجدد بعدی ()k 90 1 210 240 2 460 410 520 3 610 590 760 4 3 340 490 2 130 2 330 3 510 4 190 3 340 4 4 نقطه شروع مجدد قبلی ()j 0 1 2 3 دستور العمل پیشرو -سفارشات عقب افتاده مجاز است 4 3 2 1 590 410 210 90 580 550 420 400 220 ‏j ‏k 0 1 2 3 570 4 550 400 210 90 ‏Fk 2 2 0 0 )j*(k