برنامه ريزي پویا

[SonBol]

ويژگي هاي مسائل برنامه ريزي پويا



1) مسئله را مي توان به چند مرحله تقسيم كرد. در هر مرحله ، يك خط مشي تصميم گيري مورد نياز است. همچنين مي توان گفت مرحله بخشي از مسئله را نشان مي دهدكه قرار است براي آن تصميم گيري شود.

2) هر مرحله داراي تعدادي حالت وابسته به خود است.به طور كلي مي توان گفت حالت ها عبارتند از انواع وضعيت هاي احتمالي كه دستگاه مي تواند در آن مرحله داشته باشد. تعداد حالت ها در هر مرحله مي تواند متناهي يا نا متناهي باشد . ونيز حالت ها در يك مرحله ممكن است پيوسته يا گسسته باشند.

3) درهر مرحله با اتخاذ يك تصميم ، حالت مرحله ي فعلي به حالتي كه وابسته به مرحله ي بعدي باشد ، انتقال مي يابد( ممكن است براساس يك تابع توزيع احتمال نيز باشد). مسائل برنامه ريزي پويا را مي توان با شبكه ها مقايسه كرد ، در اين حالت (شبكه ها ) ،هر گره متناظر يك حالت است. شبكه شامل ستون هايي از گره هاست كه كه هر ستون معرف يك مرحله است به طوري كه جريان از يك گره به گره بعدي كه در سمت راست آن است مي تواند حركت كند.هر شاخه اي كه دو گره را به هم وصل مي كند با عددي مشخص مي شودكه اين عدد را مي توان افزايش تابع هدف ناشي از حركت از حالتي به حالتي در مرحله ي بعدي تعبير كرد. با در نظرگرفتن چنين تعبيري ، هدف مسائله پيداكردن كوتاه ترين يا بلندترين مسير شبكه است . بسياري از مسائل تصميم ، حالت مرحله ي بعدي را با اطمينان مشخص نمي كنند. به جاي آن تصميم فعلي ، تابع توزيع احتمال ، حالت مرحله ي بعدي را مشخص مي كند.

4) با دانستن حالت فعلي ، خط مشي مراحل باقي مانده مستقل از خط مشي پذيرفته شده در مراحل قبلي است.پس براي مسئله ي برنامه ريزي پويا در حالت كلي ، اطلاعات حالت فعلي سيستم منتقل كننده ي تمامي اطلاعات ضروري مربوط به رفتار قبلي آن براي معين نمودن خط مشي بهينه از اين حالت به بعد مي باشد( اين خاصيت را خاصيت ماركفي ناميم)و آن را تحت عنوان اصل بهينگي درنظر مي گيريم.درحقيقت اگر در مسائلي حالت داراي خاصيت ماركفي نباشد نمي توان آن را بابرنامه ريزي پويا حل نمود. توجه به اين مطلب از ضروريات است كه بايد ملحوظ گردد.

5) روند حل مسئله با پيدا نمودن خط مشي بهينه براي هر حالت از مرحله ي نهايي شروع مي گردد. اين مطلب تحت عنوان شروع از انتها (پسرو ) معروف است، جواب اين مرحله معمولا بديهي است زيرا روند از مقصد پيگيري مي شود.( لازم به ذكر است كه از روش پيشرو نيز مي توان استفاده كرد كه در مثال هاي آتي به اين نكته هم خواهم پرداخت )

6) سياست بهينه ي همه ي حالت هاي مرحله ي n را مي توان با يك رابطه ي بازگشتي و با فرض معلوم بودن سياست بهينه ي تمام حالت هاي مرحله يn+1 مشخص نمود.

7) روش حل با حركت از انتها و باستفاده از رابطه ي بازگشتي بند 6 از مرحله اي به مرحله ي قبل اعمال مي شود. در هر مرحله ، سياست هاي بهينه درمورد تمام حالت هاي آن مرحله مشخص مي گردد تا سرانجام بهينه ي اولين مرحله تعيين شود.

در همه ي مسائل برنامه ريزي پويا براي هر مرحله بايد جدولي شبيه جدول زير درنظر گرفته شود:

Xn*

Fn*(s)

S

كه در ستون

S : كليه ي حالت هاي دستگاه در مرحله ي n ام

Fn*(s) : مقدار بهينه ي هدف مورد نظر در حالت s از مرحله ي n ام

Xn* : تصميم بهينه در محله ي n ام

نوشته مي شود.