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

[SonBol]

زمينه ي تاريخي



پدر برنامه ريزي پويا ريچارد بلمن (Richard Belman) است . بلمن مفاهيم اوليه ي برنامه ريزي پويا را در اواخر سال 1940 و اوايل سال 1950 كه در مؤسسه ي راند ( Rand ) مشغول كار بود گسترش داد. وي در سال 1957 كتابي تحت عنوان برنامه ريزي پويا تاليف كرد. اين كتاب تنها منبع شامل مسائل مهندسي گوناگون بود. كتاب دوم را بلمن در سال 1961منتشر كرد. سومين كتاب وي با همكاري دري فوس ( S.E.Dreyfus) در سال 1962 عرضه شد.پس از بلمن همكاران علمي او سهم مهمي در شناساندن روش هاي برنامه ريزي پويا و بهتر نمودن آنها داشتند. آريس ( Aris ) دو كتاب در اين زمينه نوشت كه به ترتيب در سال هاي 1961و1964 منتشر شدند.در اواخر سال 1964 آريس و وايلد بررسي كلي دستگاه هاي چند مرحله اي را گسترش دادند. همچنين ال.جي.ميتن ‌(L.G.Mitten) سهم بسزايي در گسترش مفاهيم برنامه ريزي پويا داشته است.

[SonBol]

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



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

[SonBol]

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



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

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

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

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

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

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

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

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

Xn*

Fn*(s)

S

كه در ستون

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

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

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

نوشته مي شود.

[SonBol]

دسته بندي مسائل برنامه ريزي پويا

به طور كلي مسائل برنامه ريزي پويا را مي توان به دو دسته تقسيم كرد :

1) برنامه يزي پوياي قطعي


2) برنامه ريزي پوياي احتمالی


منبع :

تحقيق در عمليات (2) / مؤلف : دكتر غلامرضا جهانشاهلو / انتشارات دانشگاه پيام نور