ترجمه قسمتی از کتاب فرایند های مارکوف

این مطلب قسمتی از فرایند های تصمیم گیر مارکوف می باشد که از کتاب Markov Processes for Stochastic Modeling از صفحه ۲۹۷ ترجمه شده است.

معرفی

فرایند کنترل مارکوف کلاسی از فرایند­هایی است که بر اساس احتمالات تصمیم گیری می­کنندکه این فرایند­ها فرایند تصمیم گیری مارکوف (mdp) ، فرایند تصمیم گیری شبه مارکوف (smdp) ، مشاهدات جزئی فرایند تصمیم گیری مارکوف (pomdp) هستند که می­توان آن­ها را به عنوان مدل­های ریاضی در نظر گرفت. این مدل­های ریاضی با استراتژی بهینه تصمیم گیری باید تصمیمات پی در پی در طول زمان با نتایج نامطمئن بگیرند.

در این فصل این سه فرایند تصمیم گیری موضوع بحث هستند.

فرایند های تصمیم گیری مارکوف

در mdp  نماینده یا تصمیم گیرنده می تواند بر روی حالتی از سیستم با انجام عمل (action)تاثیر بگذارد که موجب می شود سیستم کارایی از پیش تعریف شده را بهینه کند.

برای این کار نماینده در نقطه های خاصی از زمان که به آن مبدا تصمیم گیری گویندحالت سیستم را مشاهده می کند و اطلاعات ضروری را جمع آوری می کند تا عملیاتی را انتخاب کند که به هدف کارایی مورد نظرش برساند.

هر عمل (action) نماینده یک پاداش یا جریمه هستند و این عمل (action) بر روی حالت سیستم و در نتیجه بر روی عملیات آینده تاثیر می­گذارد.

با اعمال عمل(action) انتخابی به سیستم ؛ نماینده متحمل هزینه می­شود و سیستم بر اساس  توزیع احتمال انتقال (transition probability distribution) به حالت جدید می­رود.

به طور کلی هزینه متحمل شده و توزیع احتمال انتقال (transition probability distribution) به حالت و عمل انتخابی (action) بستگی دارد.

اگر مجموعه زمان شروع تصمیم گیری (epochs) را با T  نشان دهیم آن گاه فرایند تصمیم گیری به عنوان  فرایند تصمیم گیری در زمان گسسته یا پیوسته می تواند کلاس بندی شود که بستگی به  آن دارد T گسسته است یا پیوسته.

در فرایند تصمیم گیری با زمان گسسته ، تصمیم گیری فقط در زمان شروع (epoch) گرفته می شود و به طور مشابه در فرایند تصمیم گیری با زمان پیوسته تصمیم گیری به طور پیوسته یا در زمان های تصادفی گرفته می شود.

در فرایند تصمیم گیری با زمان گسسته مجموعه نقاط تصمیم گیری (T) می تواند محدود یا نامحدود باشد. وقتیT محدود است آن گاه T={ 1,2,…,N}  و N<∾ است و وقتی T  نامحدود است آن گاه T={1,2,..N} یعنی تصمیم گیری به صورت نامحدود انجام می شود و اعضای T نقطه شروع تصمیم گیری هستند که با t  نشان می دهند.

وقتی N  محدود است فرایند تصمیم گیری را فرایند تصمیم گیری محدود افقی و یا مرحله محدود (finite-stage یا finite-horizon) گویند در غیراین صورت آن را فرایند تصمیم گیری نامحدود افقی یا  مرحله نامحدود (infinit-stage) گویند.

نتیجه تصمیم بعدی قابل پیش بینی نیست اما قبل از تصمیم گیری بعدی از روی توزیع احتمال انتقال می توان تا حدودی  آن را پیش بینی کرد و همچنین عمل هایی (action ) که به سیستم اعمال می شوند دارای نتیجه منطقی طولانی مدت (long-term) هستند زیرا تصمیمات گرفته شده در زمان شروع تصمیم گیری(epoch) فعلی بر روی تصمیمات در زمان شروع تصمیم گیری (epoch) بعدی تاثیر می گذارد بنابراین نمی توان به صورت تنها یا منزوی تصمیم گیری کرد در نتیجه ضروری است که بین هزینه کم به عنوان یک هدف و هزینه های بالای آینده تعادل برقرار کنیم بنابراین نیازمند قوانین خوب تصمیم گیری هستیم تا عملیاتی را که باید در هر نقطه تصمیم گیری و حالت انجام شوند را اختصاص دهیم .

قوانین تصمیم گیری در هر زمان شروع تصمیم گیری (epoch) ، سیاست خوانده می شود.

سیاست استفاده شده در نقطه شروع تصمیم گیری t می تواند از تاریخچه سیستم تا t استفاده کند ( یعنی حالتهای پی در پی و عملیات پی در پی مشاهده شده در سیستم ).

بنابراین ما می توانیم سیاست را به عنوان قوانین تصمیمات پی در پی درنظر بگیریم که توصیف کننده عمل انجام شده در نقطه شروع تصمیم گیری است.

سیاست را با D={  ,   , … , }  نشان می دهیم و  عملی است که در نقطه شروع تصمیم گیری انجام می شود.

سیاست ها به دو دسته ایستا و پویا تقسیم می شوند.

در حالت ایستا هر موقع سیستم در حالت i است یک عمل خاص  انجام می شود.

برای مثال فرایند تصمیم گیری ای را در نظر بگیرید که حالتهای فرایند در نتیجه ضربه زدن به یک سکه است. اگر سیاست نماینده ۲$ زمانی که نتیجه شیر بود و ۱$ زمانی که نتیجه خط بود، باشد  آن گاه این یک سیاست ایستا است.

در سیاست پویا هنگامی که سیستم در حالتی قرار دارد می تواند هر عمل مختلفی را انجام دهد. عملی که انجام می شود ممکن است به  زمان شروع تصمیم گیری بستگی داشته باشد.

برای فرایند مرحله محدود هنگامی که فرایند در مرحله k  است می توانیم در ابتدای محدوده یک عمل انجام دهیم و وقتی سیستم دوباره در حالت k  است عمل متفاوتی را به سمت پایان محدوده انجام دهیم .

فرایند تصمیم گیری مارکوف به رنج وسیعی از مسائل کنترل stochastic  اعمال شده است از قبیل سیستم های  بررسی- نگهداری- جایگزینی ، مدیریت کالا ، برنامه ریزی اقتصادی.

موضوع در چندین کتاب پوشش داده شده است که شامل موارد زیر است :

Bertsekas (1976, 1995a, 1995b), Borovkov (2003), Heyman and Sobel(1984), Howard (1960, 1971b), Kumar and Varaiya (1986), Puterman (1994), Ross (1970, 1983), andTijms (1995).

فرایند تصمیم گیری مارکوف در مدل شبکه های ارتباطی در Tosley  (۲۰۰۰)اعمال شد، دارایی وانتخابات پویا در Schal(2001) ، مخزن آب درlamond  ( ۲۰۰۱)، درمان پزشکی در schaefer(2004).

با خلاصه ای از برنامه نویسی پویا شروع می کنیم.

خلاصه ای از برنامه نویسی پویا

برنامه نویسی پویا (dp) یک تکنیک ریاضی است که برای بهینه کردن مساله های تصمیم گیری چند سطحی یا چند گامی استفاده می شود.

مساله تصمیم گیری چند سطحی ، مساله ای است که می تواند به چند سطح یا مرحله مجزا شود(یک مساله را می توان به چند مرحله تبدیل کرد) که هر مرحله شامل بهینه ای از دقیقا یک متغیر است.

در هر مرحله محاسبات با الگوریتم های بازگشتی انجام می شوند که راه حل بهینه عملی برای کل مساله وقتی که به آخرین مرحله می رسد مطمئنن بدست می آید.

بحث اخیر در مورد بهینه کردن هر گام بر اساس تصمیم و  تصمیمات پی در پی که سیاست خوانده می شود است.

هر مرحله تعدادی حالت های مرتبط با آن دارد. وقتی حالت در هر شرایط ممکنی است سیستم مرتبط با مساله چند مرحله ای می تواند در آن حالت باشد.

تعدااد مراحل می تواند محدود یا نا محدود باشد و تصمیم در هر مرحله حالت فعلی را به حالت جدیدی که  مرتبط با مرحله بعدی است تبدیل می کند.

در مساله تصمیم چند مرحله ای معمولا مقدار خاصی را که مرتبط با هر تصمیم گرفته شده است باز می گرداند. این مقدار بازکردانده شده می تواند سود یا ضرر باشد.

منظور از راه حل مساله این است که سیایت بهینه را تعیین کنیم  یعنی یساستی که بهترین مقدار ار بر می گرداند.

برنامه نویسی پویا بر اساس قوانین بهینگی Bellman  به صورت زیر بیان می شود:

قواعد بهینگی

سیاست بهینگی دارای ویژگی هایی است . مقدار اولیه حالت و تصمیم هر مقداری باشد اثر باقی مانده تصمیمات باید سیاست بهینگی را با پاداش دادن به مرحله نتیجه شده از تصمیم اول ترکیب کند. این قواعد به حالت فعلی اشاره می کند. سیاست بهینه برای مراحل باقی مانده مستقل از سیاست استفاده شده در مراحل قبلی است. به عبارت دیگر اطلاعات از حالت فعلی سیستم متضمن همه اطلاعات درباره رفتار گذشته است یعنی برای تعیین سیاست بهینه ضروری است.

پیاده سازی این قواعد با پیدا کردن سیاست بهینه برای هر  حالت ار آخرین مرحله شروع می شود سپس آن مرحله به مرحله عقب حرکت می کند. در هر مرحله جهت تعیین بهترین سیاست برای ترک کردن هر حالت مرحله از نتایج بدست آمده در مرحله قبلی استفاده می شود.

مثالی از برنامه نویسی پویا

موقعیتی را در نظر بگیرید که x  منبع داده شده تا در N  فعالیت قرار داده شوند. برای مثال ما ممکن است

$X برای سرمایه گذاری بر روی N  پروژه نیاز داشته باشیم.

فرض کنید جدولی داریم که لیستی از  ri(x)  را برمی گرداند که تحقق می یابد از تخصیص مقدار x  از منابع فعالیت  i . تا جایی که      i = 1, . . . , N و x  = ۰, ۱, . . . , X است ،پس مسئله ای که ما ا آن روبرو هستیم به شرح زیر است:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

این مسئله را از دیدگاه برنامه نویسی پویا نگاه کنیم، در نظر بگیرید N مرحله با برچسب های  ۱, ۲, . . . , N  است که در آن هر مرحله نشان دهنده یک فعالیت است و ما برای اولین بار تخصیص می دهیم مقدار x1 را از مجموع منابع به فعالیت ۱ در مرحله ۱ ، سپس مقدار x2 از باقیمانده منابع X x1 به فعالیت ۲ در مرحله ۲ و به همین ترتیب.

برای اینکه قادر به بهینه سازی روند باقی مانده باشیم  ما باید مجموع واحدهایی که اختصاص داده شده در هر مرحله و مقدار سمت چپش را بدانیم. مقدار بهینه تابع vk (x)  تعریف می کنیم: به عنوان حداکثر بازده به دست آمده از فعالیت های k تا N ، با توجه به اینکه واحد  xاز منابع باقی مانده اختصاص داده شده است. از اصل بهینگی رابطه بازگشتی زیر را به دست می آوریم :

که در آن xk به فعالیت k تخصیص داده شده است و x = 0, 1, . . . , X  است و  محدودیت شرطی هست

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

و راه حلی برای حل  مسئله  v1(x) است.

مثال ۱۰٫۱  یک مثال عددی فرض می کنیم ، ۶ =X و ۶ =N

■ جدول ۱۰٫۱ مقدار ri(x)را نشان می دهد.

راه حل: از آنجا که N = 3 فعالیت وجود دارد، ۳ مرحله تعریف می کنیم با محدودیت شرایط:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

در اصل مقادیری از   r3(x3) هستند.

mk (x)   نشان دهنده مقدار xk  است که حداکثر  سمت راست رابطه بازگشتی است . سپس با استفاده از رابطه بازگشتی نتایج زیر را  بدست می آوریم:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

جدول ۱۰٫۱   داده ها برای مثال عددی

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

از آنجا که ما با ۶ واحد شروع کردیم ، ما تنها نیاز به محاسبه v1(6), ، داریم که بدست می آید به وسیله:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

بنابراین، برمی گرداند بهینه را از ۶ واحد  که مجموع تخصیص برابر ۱۸ است. تعدادتخصیصها  به شرح زیر است:

از آنجا که m1(6) = 5، ما تخصیص می دهیم ۵ واحد به فعالیت.۱ که رها کرده ۱ واحد را. از آنجا که m2(1) = 1، ما تخصیص میدهیم ۱ واحد به فعالیت ۲، که رها کرده  توازن ۰ را.  به این ترتیب، ما تخصیص نمیدهیم واحدی  به فعالیت ۳٫ ما می توانیم چک کنیم که r1(5) + r2(1) = 18.

فرایندهای پاداش مارکوف

فرایندهای پاداش مارکوف (MRP) گسترش یافته  فرایند اصلی مارکوف  است که عضو پیوسته  هر حالت از یک فرآیند مارکوف با پاداش است. به طور خاص فرض کنید ،  {Xk , k = 1, 2, . . . , N}   باشد  زنجیره مارکوف زمان گسسته با یک فضای حالت محدود {۱, ۲, . . . , N}   و گذار ماتریس احتمال P . فرض کنید که وقتی که این فرایند وارد حالت i   می شود  پاداش   rij را دریافت می کند ، زمانی که یک گذار به حالت j،دارد که در آن  rij   می تواند مثبت یا منفی باشد. درنظر بگیرید ماتریس پاداش R به صورت زیر تعریف شود:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

که، R ماتریس پاداش است. فرایند {Xn, R} را یک فرایند پاداش مارکوف زمان گسسته تعریف می کنیم.

در نظر بگیرید vn(i) که دلالت دارد بر مجموع درآمد در n  انتقال بعدی، با توجه به این که فرایند جاری در حالت i است. فرض کنید که این فرایند باعث می شود یک گذار به حالت   j با احتمال  pij داشته باشیم. آن پاداش rij را دریافت می کند ، تا جائیکه

j = 1,…,N برای محاسبه vn(i) ، در نظر بگیرید  پاداش را زمانی که n گذار وجود داشته باشدنمایش داده شود با RN  و در نظر بگیرید sn نشان دهنده حالت  جاری است. سپس داریم:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

معادله فوق را اینطور می توان تفسیر کرد  که حاصل جمع اول  ، تمام پاداش های تعلق گرفته حاصل از انتقال حالت i به همه حالات ممکن با طول۱  را نشان می دهد. بعد از اینکه ما از حالت i  با انتقال مرحله قبل به حالت جدید آمده ایم ، از این مرحله به بعد  با توجه به اینکه تعداد حالات باقی مانده برای انتقال n-1  عدد می باشد لذا ما می توانیم به n-1 حالت باقی مانده در این مرحله انتقال داشته باشیم.بنابراین جمع دوم  پاداش حاصله مورد انتظار از تمامی این حالات باقی مانده را به ما نشان می دهد(با توجه به اینکه ما  در حالت j هستیم  و باید احتمال آمدن از تمامی احتمالات  انتقال از حالت i به حالت j را در مرحله قبل محاسبه کرده باشیم.

 

پایه و بنیان  MDP

MDP توسعه یافته MRP و DP است که این عامل یک مجموعه فعالیتهایی است که می تواند مورد استفاده قرار گیرد برای کنترل سیستم در هر حالت با به حداکثر رساندن  امید پاداش. MDP احتمال زمان گسسته سیستم است که می تواند توسط تاپل (S, A, R, P) نشان داده شود. که در آنS  یک مجموعه متناهی از  Nحالت است، که S = {1,2,…,N} . در تکرار (تمرین) حالتهای یک سیستم مجموعه ای از پارامترهای است که می تواند برای توصیف سیستم مورد استفاده قرار گیرد. به عنوان مثال، حالتی از یک ربات می تواند مختصاتی از ربات باشد.

A  یک مجموعه متناهی از فعالیت های K  است که می تواند در هر حالت گرفته شده باشد. که، A = {a1, a2, . . . , aK }است. در مورد یک ربات که می تواند در مراحل گسسته حرکت کند، برای مثال : هرعمل می تواند جمله ای مانند “رفتن به شرق” و یا “رفتن به غرب.”باشد .R  ماتریس پاداش، که می تواند متفاوت با عمل انجام شده باشد، بنابراین، برای عمل a A  ما  پاداش ارتباط با یک گذار از مرحله i تا مرحله j   وقتی عمل a  انجام شده باشد را توسط rij (a) . نشان میدهیم

P ماتریس احتمال گذار، که می تواند برای هر عمل مختلف باشد. بنابراین، برای عمل a A  دلالت دارد بر احتمالی که فرایند حرکت میکند از مرحله i به مرحله j  که عمل a توسط pij (a)  انجام گرفته شده باشد.

برای چنین سیستم ما می توانیم در نظر بگیریم:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

بنابراین، احتمالات انتقال و توابع پاداش، تنها توابع آخرین مرحله  و اقدامات بعدی هستند. هر زنجیره مارکوف همگن {Sn} که احتمال گذار pij (a) است یک فرایند تصمیم گیری مارکوف نامیده میشود.، تاجائیکه که    ∑pij(a) =1   باشد برای همه i S و همهa A.

همانطور که پیشتر گفته شد، اقدامات صورت گرفته در هر یک از مراحل معمولا با توجه به انتخاب دلخواه به خوبی تعریف شده است. بنابراین، یک سیاست D یک نگاشت از S به A است.به طور رسمی می توایم سیاست را به عنوان یک نقش برای در نظر گرفتن اقدامات در طول هر مرحله در یک دوره تصمیم گیری تعریف کنیم. از آنجا که هدف در فرایند تصمیم گیری به حداکثر رساندن مقدار امید از  مجموع بازگشتی ها (که نامیده میشودامید کل  بازگشت) در طول زمان داده شده است.

شرط بهینه را به عنوان شرطی که حداکثر کل امید بزگشتی برای  هر مرحله شروع i و تعدادی از انتقال n است. ما علاقه مند هستیم به شرطهای ثابت و بدون تغییر. شرطهایی  که قبلا تعریف شده است، یک شرط ثابت شرطی است که اختصاص داده شده  به هر مرحله  i و عمل ثابت a = Ri است  که همیشه در فرایند آن مرحله استفاده می شود.

توجه داشته باشید که بسیاری از متون از π برای نشان دادن سیاست (policy)استفاده میکنند. با این حال، در این کتاب ما از D استفاده کردیم زیرا  در فصل های قبلی از π برای  نمایش محدودیت مراحل احتمالات زمان گسسته زنجیره مارکوف استفاده شده است.

برای حل این مشکل از نظر ما شروع  تصمیم باشد مرحله تصمیم گیری فرایند اجازه دهید vn(i, d)  را معنی کنیم امید کل بازگشتی در مراحل بعدی n ،که فرایند در مرحله i  است و از شرط d استفاده میکند. vn(i, d)  است که گاهی اوقات

تابع ارزش نامیده می شود. برای مشتق گرفتن از معادله بازگشتی برای vn(i, d) در نظر می گیریم

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 از شکل مشاهده می کنیم که برای یک سیستم مرحله- محدود، معادله بازگشتی مربوط به  vn(i, d) و  vn(i, d) ارائه شده است توسط:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

امید بازگشتی در انتقال بعدی از مرحله i  از شرط d استفاده میکند. بنابراین،استفاده از اصل بهینگی بلمن، بازده بازگشتی مربوط به مرحله iداده شده توسط:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

 

          MDPها با تخفیف هایش                                                                 MDPs with Discounting 

در بسیاری از سیستم های اقتصادی، مهم است که هزینه پول را با نظر گرفتن میزان نزول (کاهش) در نظر بگیریم.. این با توجه به این واقعیت است که ارزش $۱ در حال حاضر  همان ارزش خود را در مدت سه سال. قبل ندارد. این تفاوت را می توان با معرفی اصطلاح بازگشت با تخفیف نشان داد. اجازه دهید فاکتور تخفیف  βرا معنی کنیم ارزش در آغاز از یک فاصله گذار از وصول بازگشتی واحد در پایان گذار، که ۰ ≤ β < 1   متغیر تصادفی ℜ ، همانطور که قبلا تعریف شده است. سپس برای سیستم مرحله محدود،  vn(i, d, β)  تعریف شده توسط :

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

بنابراین، تنها تفاوت برمی گردد  در به معرفی عامل تخفیف به آینده.

راه حل و روش ها

راه حل برای هر فرایند تصمیم گیری دنباله ای از اعمال است که بهینه سازی با توجه به تابع ارزش انجام می گیرد. سه روش کلی حل مشکلات MDP وجود دارد.روش ارزش تکرار که برای مشکلات افق محدود مورد استفاده قرار می گیرد؛

روش شرطی تکرار، است که برای مشکلات بی نهایت افق مورد استفاده قرار می گیرد؛ و روش برنامه ریزی خطی، که آن هم برای مشکلات بی نهایت افق استفاده می شود، امادر اینجا مورد بحث قرار نخواهیم داد. روش ارزش تکرار شده است گاهی اوقات به نام روش تقریب های متوالی بکار میرود.از روش  شرطی تکرار شرط های ثابتی که  بهینه سازی تابع ارزش هر دو زمانی که هیچ تنزیلی ندارند و هنگامی که تنزیل دارند استفاده می شود.روش ارزش تکرار ممکن است شرط بهینه استفاده شده در از تعداد محدودی از تکرارها را دارا نباشد. با این حال، در مقایسه با روش تکرار شرط این مزیت را دارد که در آن نیاز به حل همزمان معادلات یک سیستم به عنوان یک شرط تکرار نیست وروش های برنامه نویسی خطی انجام می دهد. بنابراین، با روش ارزش تکرار، هر تکرار را می توان به سادگی و به سرعت انجام داد.

روش ارزش تکرار

روش ارزش تکرار محاسبه به صورت دنباله ای بازگشتی از توابع ارزش تخمین هزینه بهینه در واحد زمان است. آن ضروری است گسترش تکنیک استفاده برای حل مشکل قطعی برنامه نویسی پویا و در نتیجه یک رابطه به عقب بازگشتی به شرح زیر است:

 

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

روش های پاسخ

پاسخ به هر یک از فرآیندهای تصمیم گیری ، دنباله ای از اعمال است که تابع مقدار ، داده شده را بهینه می نماید. برای حل مسائل MDP ، سه روش عمومی وجود دارد. روش مقدار- تکرار[۱] که برای مسائل کران-محدود استفاده می شود، روش سیاست- تکرار  که برای مسائل کران-نامحدود  استفاده می گردد. و روش برنامه نویسی خطی که این روش نیز برای مسائل کران-نامحدود استفاده می گردد، اما در اینجا بحث نخواهد شد. روش مقدار- تکرار ، گاهاً روش تخمین های متوالی  نیز نامیده می شود.

روش سیاست- تکرار ، سیاست سکون را خواهد یافت که چه تخفیف استفاده شود و چه استفاده نشود تابع مقدار را بهینه خواهد کرد. روش مقدار- تکرار با استفاده از تکرارهای محدود، ممکن است سیاست بهینه را ارائه ندهد. هر چند ، در مقایسه با روش سیاست – تکرار ، این روش برتری دارد که به پاسخ برابری همزمان سیستم احتیاج ندارد که روش های سیاست – تکرار و برنامه نویسی خطی به این پاسخ نیاز دارند. بنابراین ، در روش مقدار- تکرار ، هر تکرار می تواند به سادگی و به سرعت اجرا گردد.

روش مقدار- تکرار

این روش دنباله ای از تابع های مقدار را به صورت بازگشتی ، با تخمین هزینه بهینه در هر واحد زمانی محاسبه می نماید . این روش در واقع تعمیمی از تکنیکی است که برای حل مسائل برنامه نویسی پویا قطعی استفاده می شود.بنابراین رابطه بازگشتی عقبگرد زیر را به کار می برد.

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

رابطه بالا، حاصل مورد انتظار در مرحله اول را بر می گرداند ، فرایندی که در آن مرحله در حالت i است وقتی که سیاست بهینه انتخاب می شود را ارائه می دهد. با استفاده از این مجموعه ی  می توان  را بدست آورد، که  حاصل مورد انتظار در مرحله دوم به شکل زیر می باشد:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

این فرایند تا زمانیکه به مرحله اول برسیم به طور عقبگرد ادامه پیدا می کند. پاسخ مسئله برابر  است، جاییکه T تعداد دوره های تصمیم گیری است ، و با تعداد مراحل برابر می باشد. بنابراین ، فرایند به شکلی که در شکل ۱۰٫۲ نشان داده شده است خلاصه می شود.

مثال ۱۰٫۲: در نظر بگیرید تجهیزاتی را که در پایان هر روز کاری بررسی می شوند و در زمان بررسی  می توانند در یکی از سه حالات خوب ، قابل قبول و یا بد باشند. این مسئله وجود دارد که وضعیت در زمان بررسی برای روز داده شده، به طور احتمالی به وضعیت در زمان بررسی روز قبل، وابسته است.اگر قطعه ای در وضعیت خوب باشد،در روز بعد ، به احتمال ۰٫۶ هنوز خوب است ، به احتمال ۰٫۳ قابل قبول و به احتمال ۰٫۱ بد می باشد. به طور مشابه، اگر قطعه ای در وضعیت قابل قبول باشد در روز بعد، با احتمال ۰ خوب است، با احتمال ۰٫۶ قابل قبول و با احتمال ۰٫۴ بد می باشد . در نهایت، اگر قطعه در وضعیت بد باشد. در روز بعد با احتمال ۰  خوب  است، با احتمال ۰ در وضعیت قابل قبول و با احتمال ۱ در وضعیت بد می باشد.اعمال تعمیر و نگهداری ممکن به شکل زیر می باشند:

  1. هیچ کاری صورت نمی گیرد و احتمالات انتقالی تعریف شده در بالا دنبال می شود.
  2. قطعه برای تعمیر پیاده می شود،که قطعه با احتمال مساوی به وضعیت خوب و یا وضعیت قابل قبول می رود. و هزینه تعمیر قطعات ۵۰۰$ می باشد.
  3. قطعه تعویض می شود ، که به صورت خودکار به وضعیت خوب می رود.و هزینه قطعه جدید برابر ۲۰۰۰$ می باشد.

در نظر بگیرید وقتی تجهیزات در وضعیت خوب عمل کنند کارخانه $۱۰۰۰ بدست می آورد. و اگر در وضعیت قابل قبول عمل کنند کارخانه $۵۰۰ سود می کند.و اگر در وضعیت بد عمل نمایند کارخانه $۵۰۰ از دست می دهد. ما سیاست های زیر را در نظر می گیریم:

  1. تجهیزات تنها وقتی جایگزین می شوند که در وضعیت بد باشند و نه در هیچ وضعیت دیگری.
  2. تجهیزات زمانی که در وضعیت بد باشند تعویض می شوند و زمانی تعمیر خواهند شد که در وضعیت قابل قبول باشند.
  3. تجهیزات زمانی تعویض خواهند شد که در یکی از وضعیت های بد و یا قابل قبول باشند.

هزینه اعمال بهینه تجهیزات را وقتی T=4 می باشد تعیین نمایید.

حالت ها یه صورت زیرتعریف می شود:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

ما مسأله را با  اختصاص دادن مقادیر منفی به هزینه های تعیین شده توسط شرکت به یک مسأله بیشینه سازی تبدیل می کنیم. ما۵۰۰$ را به عنوان هزینه خط پایه در نظر می گیریم،یعنی این که ما ۵۰۰$ را هزینه پایه فرض کرده ایم.اگر ما،ماتریس انتقال،ماتریس جایزه وماتریس بازگشت رامشخص کنیم.

برایd by p(d), R(d)  و Q(d) ،به ترتیب،سپس ماتریس انتقال،ماتریس جایزه وماتریس بازگشت برای روش های مختلف به صورت زیر است:

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

توجه داشته باشید که عناصر R(1), R(2)و R(3) هزینه جابجایی وتعمیرتجهیزات را،به حساب می گیرند.برای مثال تحت روش ۲در حالت۲است،تجهیزات با هزینه ۱واحدتعمیرمی شوند (یا۵۰۰$) ،که از بهره ایجاد شده در حالتی که انتقال بعدی رتبه می گیرد،کسرخواهد شد.

بنابراین ورودی ها،پاداش های خالص را نشان می دهند.

درادامه حل،ما در طبقات زیرپیشروی میکنیم.ما با v0(i, d) = 0 که می دهد v1(i, d) = qi(d) شروع می کنیم.

راه حل بهینه نشان می دهد که کاربرزمانی که قطعات در وضعیت خوبی هستند،در هیچ سالی،نباید کاری انجام دهد،چه تعویض قطعات در هرسالی مورد قبول باشد،چه بدباشد.هزینه بازگشتی پیش بینی شده بعداز ۴ سال اگر تجهیزات در سال اول خوب باشد v4(1) = 4.5144 اگر تجهیزات در سال اول قابل قبول باشد ۴٫۴۶۴ v4(1) =  اگرتجهیزات در سال اول بد باشد۱٫۴۶۴ v4(1) = .

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

راه حل بهینه نشان‌دهنده این است که در زمانی که تجهیزات در هرسالی خوب است، کاربر باید کاری انجام ندهد و اگر در

هر سال تجهیزات قابل قبول باشد باید جایگزین شود. و همچنین اگر تجهیزات در هر سال بد باشد نیز باید جایگزین شود. اگر تجهیزات در سال اول خوب باشد، کل بازده مورد انتظار پس از ۴ سال برابر V4(1)= 4.5144 واحد است، اگر تجهیزات در سال اول قابل قبول باشد V4(2)= 4.464 واحد است و اگر تجهیزات در سال اول بد باشد V4(3)= 1.464 واحد است.

روش تکرار سیاست

همانطور که قبلا بحث شد، متد تکرار سیاست برای مشکلات افق بی‌نهایت مورد استفاده قرار می‌گیرد. این روش نیاز به تکرار دو مرحله دارد: مرحله تعیین ارزش به دنبال آن یک گام بهبود سیاست. مرحله تعیین ارزش‌ از طریق انتخاب دل‌خواه یک سیاست اولیه d حاصل می‌شود و سپس معادله برای بدست آوردن تابع ارزش بلند مدت در واحد زمان حل می‌شود. سپس با استفاده از روش بهبود سیاست، یک سیاست بهتر انتخاب می‌شود و گام تعیین ارزش، تکرار می‌شود. این مرحله ادامه دارد تا دو تکرار پی‌درپی که منجر به سیاست‌های یکسان شود و آنگاه این روش به دلیل رسیدن به یک سیاست بهینه متوقف می‌شود. پس از هر مرحله از طرح بهبود سیاست، تست بهینگی انجام می‌شود. اگر نتیجه تست منفی باشد، بهبود توسط گام دیگری ایجاد می‌شود، در غیر این صورت این روش متوقف می‌شود و یک راه‌حل بهینه به دست می آید.

روش سیاست تکراری کاهشی

رویه حل سیاست تکراری کاهشی مشابه روش غیر کاهشی آن است. هرچند , در دو مورد با یکدیگر متفاوت هستند. اولاً , یک فاکتور نزولی به نام β را معرفی می‌نماید. دوما ,  همان طور که در Howard(1960) نشان داده شده است, در مقدار عملکردی تعیین‌شده‌ ما استفاده می‌کنیم از  و    برای سیاست انتخاب‌شده تا معادله قرار داده‌شده را حل کند.

توجه کنید که =(gain))اثر( g در معادله ظاهر نمی‌شود. بنابراین ما N معادله  و N مجهول خواهیم داشت که به این معنی است که مقادیر  مقادیر نسبی نیستند به استثنای مقدارهای صحیح.

رویه بهبودیافته سیاست به خاطر معرفی فاکتور کاهش از یک سیستم غیر کاهشی تمایز پیدا می‌نماید. بنابراین , برای هر مرحله i , ما پیدا می‌کنیم سیاست  را که به آخرین حد افزایش یافته است = (maximizes)

برای مقادیر  از مقادیر جاری آن در سیاست قبلی استفاده شده است.

روش سیاست- تکرار با تخفیف

روال پاسخ برای روش سیاست- تکرار با تخفیف مشابه با بدون تخفیف است.البته، دو نواحی متفاوت بین هر دو وجود دارد. اولاً ضریب تخفیف  معرفی می شود. ثانیاً همانطور که در هوارد( ۱۹۶۰) نشان داده شده است، ما در عملیات تعیین مقدار برای انتخاب سیاستی که مجموعه ای از معادلات را حل می کند از  و  استفاده می کنیم.

دقت نمایید که بهره g در این معادله ظاهر نشده است.بنابراین ما N معادله در N ناشناخته داریم.به این معنی که مقادیر  مقادیر مرتبطی نیستند اما مقادیر صحیحی هستند.

روال پیشرفت سیاست، بوسیله ی معرفی ضریب تخفیف از سیستم بدون تخفیف متفاوت می شود.برای هر حالت i ، ما سیاست  را می یابیم که بیشینه می کند

استفاده از مقادیر حاضر  از مقادیر قبلی.

مثال ۱۰٫۴ : مثال ۱۰٫۳ را در نظر بگیرید و   فرض نمایید. ما MDP را برای دو سیاست با پارامترهای زیر در نظر می گیریم:

مانند مثال ۱۰٫۳ ما به بدست آوردن سیاست عملیاتی بهینه درازمدت برای مسئله احتیاج داریم.

پاسخ : مانند مثال ۱۰٫۳ ما برای هر دو حالات با   شروع می کنیم.بنابراین معادلات سیستم به شکل زیر حل خواهند شد

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

از بالا پاسخ های  و  را بدست آوردیم. این مقادیر را در روال پیشرفت سیاست  به کار می بریم و بدست می آوریم

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

در نتیجه سیاست بهبود یافته در مرحله بعدی از عملیات  تعیین سیاست به کار می رود که سیاست ۲ برای هر دو حالت ۱و ۲ است. بنابراین ، معادلات سیستم به شکل زیر حل خواهند شد:


با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

از بالا پاسخ های  و  را بدست آوردیم. این مقادیر را در روال پیشرفت سیاست  به کار می بریم و بدست می آوریم

با عرض پوزش؛ در فایل ضمیمه این پست تصاویر قرار دارد.

 

جدول بالا نشان می دهد که سیاست بهبود یافته برای هر دو حالت ۱و ۲ ، سیاست ۲ است.به این دلیل که ، سیاست بهبود یافته مشابه سیاست حاضر است، روال، سیاست بهینه را یافته و پایان می پذیرد.مقادیر حاضر برای حالات ۱و ۲ با استفاده از سیاست بهینه به ترتیب برابر ۳۰٫۶۸۹ و ۲۳٫۲۹۱ می باشد

 

برای دانلود متن به همراه تصویر کلیک کنید.

Add a Comment

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

پاسخ من را به ایمیلم ارسال کن