دانلود پاورپوینت مسائل با ابعاد بزرگ و الگوريتم تجزيه

مسائل با ابعاد بزرگ و الگوريتم تجزيه مسائل با ابعاد بزرگ و الگوريتم تجزيه به ط ور كلي مس ائل برن امه‌ريزي خطي ب ه دو گ روه عم ده قاب ل تقس يم هس تند: مسائل داراي ساختاري خاص و مسائل فاقد اين ويژگي .شايد با بعضي از مسائل مانند مدل حمل و نقل ،تخصيص و يا شبكه‌ها كه ساختاري خاص دارند ،آشنا باشيد. اين مسائل به علت داشتن اين ويژگي امكان استفاده از الگوريتم‌هاي كارا تري از سيمپلكس را يافته و اين امر موجب كاهش محاسبات مي‌گردند. دانتزي گ ( )Dantzigتكنيك‌ه اي محاس باتي ك ارا را ب ه منظ ور ك اهش محاس بات ب ه دو گ روه تقس يم مي‌كن د .تكنيك‌ه ايي ك ه م وجب «ك اهش تع داد تكراره ا» مي‌گ ردد و تكنيك‌هايي كه «موجب فشرده شدن ماتريس معكوس» مي‌شود« .الگوريتم اوليه - ثانويه» و «الگوريتم تجزيه» به ترتيب نمونه‌هايي از اين دو گروه هستند. مسائل با ساختار خاص ان واع خ اص مس ائل برن امه‌ريزي خطي ك ه در اين قس مت مع رفي مي‌گردد« ،مسائل بزرگ مقياس ( »)large-scaleاست كه تعداد بسيار زيادي محدوديت و متغير دارند .از خصوصيات مهم اين‌گونه مسائل با ابع اد ب زرگ آن اس ت ك ه بس ياري از ض رايب متغيره اي تص ميم در مح دوديت‌هاي مس أله ،ص فر هس تند ،و در بعض ي از ان واع مش خص، ص رفًا مع دودي ض رايب غ ير ص فر وج ود دارد .در نتيج ه ،ب ه منظ ور ايجاد شكل ساده و كاراتري از روش سيمپلكس مي‌توان از ساختار رياضي خاص آنها استفاده كرد و ميزان محاسبات الزم را تا حد زيادي مسائل چند بخشي مسائل چندبخشي – چند دوره‌اي مدلي با بخش‌هاي مستقل مسائل چند دوره‌اي مدلي با بخش‌هاي مستقل اين ن وع مس ائل وض عيت ش ركت‌هاي ب زرگي را نش ان مي‌ده د ك ه شركت‌هاي كامًال مستقلي را تحت پوشش داشته و هيچ نظام كنترل ‏q ‏s ‏r ‏j s 1 ‏j r 1 ‏j 1 ‏Maxنوع مدلZاين متمركزي براي اداره و يا كنترل آنها به يc j x j  كارc j xنم ‏j  cjxj ‌گيرد= . مسائل به صورت زير است. ‏r ‏ a x b )(i 1,2,...m ‏i ) (i m  1, m  2,...t ‏i ‏j ‏ij ‏j 1 ‏s ‏ a x b ‏j ‏ij ‏j r 1 ‏q ) (i t  1, t  2,...u ‏ a x b ‏i ‏j ‏ij ‏j s 1 ‏x j 0 مسائل چند بخشي يكي از متداولترين مسائل برنامه‌ريزي خطي بزرگ مقياس ،مسائل چن د بخش ي اس ت .مس ائل چندبخش ي بي انگر وض عيت ش ركت‌هاي بزرگي است كه تعدادي شركت‌هاي فرعي تحت پوشش با بخش‌هاي مختلف و نسبتًا مستقل از هم دارند .از آنجا كه هريك از بخش‌هاي شركت صرفٌا به دنبال بهينه كردن عمليات مربوط به خود است لذا مسأله تقريب ٌا به چند مسأله فرعي تجزيه مي‌شود .اما شركت مادر به منظور ايجاد هماهنگي ،كنترل و اعمال سياس ت‌هاي كلي خود بر شركت‌ها ي ا بخش‌ه اي تابعه ،من ابع و امكان ات مش تركي را بين آنه ا بخش آخر بخش 2بخش 1 هر كدام از مربع‌هاي كوچك معرف ضرايب محدوديت‌هاي هر شركت تابعه يا بخش است كه به هر كدام بلوك ( )blockمي‌گويند .مستطيل بزرگ و بااليي شامل ضرايب محدوديت‌هايي است كه بخش‌ها را به يكديگر پيوند مي‌دهد و محدوديت‌هاي مشترك ناميده مي‌شود. مسائل چند دوره‌اي شبيه مسائل چند بخشي ،مسائل چند دوره‌اي تقريب ًا قابل تجزيه به چند قسمت است .هر بخش در اين وضعيت ،به دنبال بهينه كردن عملي ات س ازماني خ ود در دوره‌ي زم اني برن امه‌ريزي اس ت .در اين نوع مسائل براي هماهنگي فعاليت‌ها در دوره‌هاي زماني مختلف به منظ ور بهين ه ك ردن عملي ات ب راي تم امي اف ق برن امه‌ريزي ،وج ود مح دوديت‌هاي مش ترك ض رورت پي دا مي‌كن د .ص ورت‌بندي اين ن وع مس ائل ك ه در آن برن امه‌ريزي ج امع چن دين دوره‌ي زم اني م د نظ ر است به مسائل چند دوره‌اي (دوره به معني روز ،ماه‌ ،سال و غيره) مسائل چند بخشي -چند دوره‌اي در جه ان واق ع مس ائل بس ياري وج ود دارد ك ه هم‌زم ان خص لت چندبخشي و چنددوره‌اي دارد .اين نوع از مسائل معموًال داراي تعداد زيادي مسائل فرعي است كه هدف هر مسأله بهينه كردن عمليات براي هر بخش و در هر دوره است .اين نوع مسائل داراي تعدادي متغير‌هاي رابط و محدوديت‌هاي مشترك هستند. مباني الگوريتم تجزيه الگوريتم تجزيه يا به عبارت دقيق‌تر ،الگوريتم تجزيه‌ي دانتزيك – ولف ( )Dantzig-Wolf decomposition algorithmغالب ٌا توانايي حل مسائل بسيار بزرگ را داد .هرگاه ماتريس ضرايب مسأله‌اي داراي ساختاري خاص به صورت مسائل چند بخشي باشد ،كارايي اين الگوريتم بسيار توس عه مي‌يابد .هم ان‌طور كه قبٌال گفت ه شد اين نوع مسائل داراي بخش‌ها (بلوك‌ها) ي مستقلي هستند كه با تعدادي محدوديت به هم پيوند داده مي‌شوند. الگوريتم تجزيه بر اساس اين چهار مفهوم بنيان شده‌است: -1الگوريتم سيمپلكس تجديد نظر شده -2نمايش مجموعه‌ي محدب بر حسب نقاط گوشه‌اي نمايش مجموعه‌ي محدب بر حسب نقاط گوشه‌اي منطقه‌ي موج ه مس ائل برن امه‌ريزي خطي ،نم ونه‌اي از مجم وعه‌اي محدب است .مجموعه محدبي را در صفحه در نظر بگيريد .نقاطي كه گوشه‌هاي مجموعه را تشكيل مي‌دهند ،نقاط گوشه‌اي (extreme )pointsناميده مي‌شود ،يعني نقطه‌اي از مجموعه‌ي محدب را كه بر روي پاره‌خطي كه دو نقطه‌ي ديگر از مجموعه را به هم وصل مي‌كند قرار ندارد نقطه‌ي گوشه‌اي مي‌نامند. مفهوم ديگري كه در اين بخش با آن آشنا مي‌شويد ،مفهوم تركيب محدب ( )convex combinationاست. ‏n ‏i 1 2 ‏n ‏ ‏X ‏X ‏ ‏X ‏ ‏ ‏X ‏ ‏ .... ‏ ‏X ‏ ‏ ‏i )linearاز ‏combination تركيبي بردار (نقطه‌ي) Xدر فضاي En 1 2 j خطي ( n 1 بردارهاي i يعني (نقاط) X1, X2, …, Xnاست .اگر Xبرابر باشد با مقادير ثابت هستند كه مي‌توانند در رابطه فوق هر عدد حقيقي مثبت يا منفي باشند. هر ت ركيب خطي در فض اي دو بع دي ،ي ك خ ط و در فضاي سه بع nدي ي ك ‏ ‏ ‏ ‏ 1 ‏ ص فحه تعري ف ميi ‏ ،مق  i اديري غ ير ‌كن د .هرگ اه در تركي بي خطي مق ادير ‏ i 1 ،تركيب محدب تعريف منفي بوده و مجموع آنها برابر با يك باشد 2 محدب...از 2 X 2  مي‌شود .يعني بردار Xتركيبي  n X n بردارهاي XXn 1،X21 Xو Xn ...است اگر )(i 1,2,..., n ‏i 0 ‏  1 ‏i ‏i 1 مجم وعه‌ي تم ام تركيب ات مح دب برداره اي X1, X2در فض اي دو بع دي پ اره‌خطي مس تقيم اس ت ك ه ش امل نق اط پاي اني اين دو ب ردار ن يز هست. مجموعه‌ي تمام تركيبات محدب نقاط ،پوسته‌ي محدب ( )convex hullرا تشكيل مي‌دهد .پوسته محدب هر دو نقطه‌اي از Enپاره‌خطي است كه آن نق اط را ب ه هم وص ل مي‌كن د ،و پوس ته‌ي مح دب ه ر س ه نقطه‌ي متمايز در صفحه (كه همه‌ي آنها روي يك خط نباشند) يك مثلث است و پوسته‌ي محدب مجموعه‌ي تمام نقاطي كه بر محيط دايره‌اي واقعند روش كاهش محدوديت‌ها از آنجا كه محدوديت‌هاي برنامه‌ريزي مسائل خطي تشكيل دهنده‌ي چند وجهي محدبي به نام منطقه‌ي موجه است ،در صورت دانستن تمامي نقاط گوشه‌اي منطقه‌ي موجه ،هر جواب موجه را مي‌توان به صورت تركيبي محدب از نقاط گوش ه‌اي نوشت .به اين ترتيب براي حل مسأله برنامه‌ريزي خطي بايد تركيبي محدب از اين نقاط را به گونه‌اي به دست آورد كه تابع هدف را بهينه نمايد .با انجام اين عمل تعداد محدوديت‌هاي مسأله كاهش يافته و تعداد متغير‌هاي آن افزايش خواهد يافت .در مسائل چند بخشي اين كار بر حسب نقاط گوشه‌اي 1 2 ‏q ‏Max Z = C1 X  C2 X  ...  Cq X ‏b0 ‏A1 X 1  A2 X 2  ...  Aq X q ‏b1 ‏D1 X 1 ‏D2 X 2 ‏b2 ... ‏Dq X q bq ‏X 1 , X 2 , X 3 ,..., X q 0 ماتريسيmXj j،nداراي njمؤلفه و bj ماتريسي Dj ، كه b0برداري ستوني با m0مؤلفه (عنصر) و هر Aj ‏m0 n j ‏j داراي mjمؤلفه است. توج ه كني د ،مع ادله‌ي اول بي انگر مح دوديت‌هاي مش ترك بين بخش‌ه ا (بلوك‌ه ا) اس ت و س اير معادالت ،محدوديت‌هاي خاص هر بخش را نشان مي‌دهد .در صورتي كه Aj=0به ازاي هر j آن گاه مسأله به مسأله‌اي به qبخش مستقل از هم تبديل خواهد شد .اما اگر يك يا چند Aj مخالف صفر باشدبين بخش‌ها يا تعدادي از آنها ارتباط وجود داشته و مسأله چند بخشي ناميده مي‌شود. روش توليد ستون هنگام به كارگيري روش كاهش محدوديت‌ها ،در ازاي كاهش تعداد محدوديت‌ها تعداد متغير‌هاي مسأله افزايش مي‌يابد .تعداد متغير‌هاي ‌ي جدي دي ك ه ب دين ص ورت تش كيل مي‌ش ود ب ه مس أل هi مس أل هi ‌ي با اص لي ( )master problemمع روف اس ت و تع داد متغيره اي آن تعداد نقاط گوش ه‌اي موجه مسأله‌ي چند بخشي ابتدايي برابر است. از آنجا كه در مسائل واقعي با بخش‌هاي متعدد ،تعداد محدوديت‌هاي هر بخش معموًال زياد است ،تعداد نقاط گوش ه‌اي موجه اين مسائل بس يار زي اد و در ح د ي ك ميلي ون و ي ا بيش تر اس ت .ل ذا تع داد متغ ير (ستون) هاي مسأله‌ي اصلي فوق‌العاده افزايش مي‌يابد. يكي از خ واص مهم روش س يمپلك آن اس ت ك ه انج ام ه ر تك رار در صورتي كه تابع هدف مسأله به صورت Maxباشد .اطالع از متغيري كه داراي بزرگترين ضريب مثبت در تابع هدف (منفي‌ترين ضريب در سطر تابع ه دف ،ج دول) ب ه منظ ور تع يين متغ ير ورودي ،ض رايب اين متغ ير در محدوديت‌هاي مسأله كه ستون لوال را تشكيل مي‌دهد و اعداد سمت راست كه براي انتخاب متغير خروجي مورد استفاده قرار مي‌گيرند ،كافي است .به همين دليل بود كه در روش سيمپلكس تجديد نظر شده ،ضرايب كليه‌ي متغيرها در تابع هدف محاسبه و متغ ير ورودي از ميان آنان انتخاب مي‌شد و تنها اعداد س تون زي ر متغ ير ورودي انتخ اب مي‌ش د .در ش كل ص فحه‌ي بع د قس مت‌هاي س ايه خ ورده در ه ر ج دول محاس به مي‌ش ود .ام ا در مس أله‌ي ناش ي از چن د بخش ي ب ه علت زي اد ب ون تع داد ض رايب متغيره ا در ت ابع ه دف ،اس تفاده از ش يوه‌ي س يمپلكس تجدي د نظ ر ش ده ك ارا نيس ت .مشكل‌گش اي چ نين ح االتي اعداد سمت راست ‏s1s2 ….sm ‏x2… xj… xn ‏X1 متغير اساسي ‏z Xjمتغير ورودي اطالعات الزم براي انجام تكرار در روش توليد ستون اعداد سمت راست ‏s1s2 ….sm ‏x2… xj… xn ‏X1 متغير اساسي ‏z اطالعات الزم براي انجام تكرار در روش سيمپلكس تجديد نظر شده الگوريتم تجزيه الگوريتم تجزيه غالب ًا توانايي حل مسائل بزرگ را داراست و هنگامي كه ماتريس ضرايب مدل در محدوديت‌ها داراي ساختار خاص زاويه‌اي مانن د مس ائل چن د بخش ي باش د ،اين ك ارايي فوق‌الع اده اف زايش مي‌ياب د .عالوه ب ر آن در بعض ي از م دل‌هاي برن امه‌ريزي خطي محدوديت‌هاي مسأله را مي‌توان به دو گروه «محدوديت‌هاي آسان» ( )easy constraintsو «محدوديت‌هاي سخت» ( )hard constraintsتقسيم كرد. مسائلي با يك بخش در اين نوع مسائل فقط يك بخش يا بلوك وجود دارد ،به عبارت ديگر شكل كلي مسائل چند بخشي (كه در آن )q=1چنين است: ()1 ()2 ()3 ‏Max Z = CX ‏AX=b0 ‏DX=b1 ‏X 0 ‏m0 n ‏m0 1 در مدل فوق Aماتريسي b0 ،بردار ستوني ‏n 1 ‏1n است. X ،بردار ستوني و Cبردار سطري ‏m1 n D ،ماتريسي همانطور كه مشاهده مي‌كنيد مسأله داراي دو گروه محدوديت است: مجموعه محدوديت‌هايي كه در شكل فوق با معادالت ( )2مشخص شده و مح دوديت‌هاي س خت را تش كيل مي‌ده د و مع ادالت ش ماره ( )3ك ه محدوديت‌هاي آسان را تشكيل مي‌دهد. توج ه كني د ك ه منطق ه موج ه مس ائل برنام ه ري زي خطي ب ه ص ورت چندضلعي محدب است .در اين صورت منطقه موجه بخش يعني DX=b1 ‏S X DX b1 , X 0 نيز چند ضلعي محدبي است كه آن را با Sنمايش داده و به صورت زير نوشته مي‌شود: ‏i 0 ‏t ‏  1 , ‏i ‏i 1 , ‏t ‏X  i X i ‏i 1 هر نقطه‌ي Xرا در Sمي‌ت وان ب ه ص ورت تركي بي مح دب از نق اط با جايگزين كرد Xاز روي رابطه ( )4در معادالت ( )2( ،)1و ( )3و ‏t ‏i 1 ‏0  كردنiمحدوديت‌هاي و ،مسأله‌ي يك بخشي اوليه ،با شيوه اضافه ‏i 1 به صورت كاهش تعداد محدوديت‌ها به مسأله‌ي جديدي بر حسب زير كه مسأله اصلي ( )master problemنام دارد تبديل مي‌شود: ‏t ()5 ‏Max Z  (CX i )i ‏i 1 يا ‏t ()6 ‏i ( ‏AX )i b0 ‏ ‏i 1 ‏t ()7 يا ‏ t ‏ ‏i ‏Max Z C   X  ‏ j 1 ‏ ‏ ‏ ‏A   i X i  b0 ‏ i 1 ‏ ‏t ‏t ‏  1 ‏  1 ‏i 0 ‏i 0 ‏i ‏i 1 ‏i ‏i 1 i اين مسأله حاال مسأله‌اي برنامه ريزي خطي با i ‏X متغير‌هاي تصميم اس ت و مق اديري ث ابت از نق اط گوش ه‌اي اس ت .ب راي سادگي عمليات ،با تغيير متغير gi=CXiو hi=AXtiمسأله اصلي به صورت زير در مي‌آيد: ()8 ‏Max Z  ‏g i i ‏i 1 ‏t ‏i ‏h ‏ i b0 ‏i 1 ()7 ‏t ‏  1 ‏i ‏i 1 ()6 ‏i 0 مس أله اص ل ف وق داراي m +1مح دوديت در مقايس ه ب ا m +m ستون مورد نياز ستوني است كه در معادله‌ي تابع هدف Maxمسأله ،در هر تكرار بزرگ ترين ض ريب مثبت (منفي‌ت رين مق دار در س طر ص فر ج داول س يملكس) را داشته باشد .به طور كلي ضرايب متغيرها در معادله‌ي تابع هدف (به جز ضرايب ‏i متغيرهاي اساسي شروع مسأله) با عبارت ‍Cj – Zj jنمايانده مي‌شود .مقدار آن براي ‏h  از C j  است Z j عبارت g j  با استفاده از رابطه‌زيرY   متغير تصميم 1 ‏  ()11 ‏hj ‏i ‏  ‏1 كه Yبردار قيمت‌هاي سايه (يا ضرايب سيمپلكس) و ضريب ستون مسأله‌ي تبديل شده بر حسب است .بردار Yرا مي‌توان به دو قسمت تقسيم كرد :ضرايب سيمپلكس مربوط به معادالت ( )9كه با برداد Y0و ضرايب سيمپلكس محدوديت ‏ AX j  ‏C j  Z j CX j  Y0 , Y1  ‏ ( )10كه با Y1نشان داده مي‌شود ‏ 1  ‏CX j  Y0 AX j  Y1 از آنجا كه هدف يافتن متغيري با بزرگترين ضريب در تابع هدف به منظورiتعيين متغير ورودي( ) است بايد Cj – Zjحداكثر گردد .اما از آنجا كه Y1مقداري است ثابت ،اين مقدار موقتًا از معادله (‌)12حذف مي‌گردد .پس ‏Max Z ' CX j  Y0 AX j ‏X 0 ()13 ام ا ب ا ي ادآوري اين نكت ه ك ه Xjنق اط گوش ه‌اي مجم وعه‌ي مح دب S است كه در آن ‏Max Z ' CX  Y0 AX و ،DX=b1اين مجموعه محدوديت‌ها را بايد با تابع هدف فوق در نظر گرفت ()14 ‏st : DX b1 ‏X 0 بنابر اين به منظور پيدا كردن متغير و ستون ورودي براي مسأله‌ي اصلي ،مسأله‌ي فرعي (معادالت )15( ،)14و ( )16حل خواهد شد و ج واب بهينه‌ي آن يع ني X*kمتغ ير ورودي و س تون ل والي مس أله‌ي اصلي عبارت است از و ضريب تابع هدف gk=CXkاست. ‏ n k   AX *k  ‏   ‏ ‏1  1  گام‌هاي الگوريتم تجزيه براي مسائل يك بخشي گام .1يك جواب موجه ابتدايي براي مسأله اصلي پيدا كنيد. گام .2متغير ورودي را انتخاب كنيد. مسأله فرعي را به منظور تعيين مثبت‌ترين ضريب متغير غير اساسي كانديداي ورود ،حل كنيد .در مسأله فرعي براي بدست آوردن Y0از رابطه‌ي Y=(Y ,Y )=C B-1استفاده كنيدi . ‏B 1 0 ) در تابع هدف تذكر :با توجه به معادله ،5ضريب متغير ورودي ( ‏i ‌آيد. ي م ‌دست ه ب ‏CX مسأله از رابطه‌ي ‏b  ‏b B 1  دستور زير صفر باشد به جواب دستور توقف .اگر مقدار Cj – Zjاز 0 ‏1 ‏C j – Z j Z' – Y1 بهينه رسيده‌ايد و توقف كنيد( .مقدار متغيرهاي اساسي جواب بهينه ‏Cj – Zj ‏i به‌دس ت مي‌آي د) ،در غ ير اين ص ورت ب ه گ ام بع د از رابطه‌ي گام .3متغير خروجي را انتخاب كنيد. الف .ستون لوال را از رابطه زير به دست *k آوريد ‏ ‏AX ‏1 ‏ak  B  ‏ ‏ 1  ب .اعداد سمت راست به طريق زير محاسبه مي‌شوند ‏ b0  ‏bk B   ‏ 1 ‏1 از تقس يم اع داد س مت راس ت ب ر اع داد ل وال و انتخ اب كوچك ترين نسبت حاصل متغير خروجي را مشخص كنيد. گام B-1 .4جديد را محاسبه كنيد و به گام 2برويد .براي انجام اين كار از روش‌ه اي مختل ف مي‌ت وان اس تفاده ك رد ،ام ا ك اراترين روش، شيوه‌اي است كه در روش سيمپلكس تجديد نظر شده با آن آشنا شده‌ايد. مسأله موجودي كاال ميزان تقاضاي كاالي شركتي در چهار ماه آينده عبارت است از ماه اول دوم سو چهار م م 1 4 3 2 ميزان تقاضاباي د هزين ه ث ابتي مع ادل 3 در هرم اه اگر ش ركت تولي د داشته‌باش د، عالوه بر هزينه متغيري برابر با 1براي هر واحد توليد كاال بپردازد .حد اكثر ظرفيت توليد كاالي شركت در هر ماه معادل 5مي‌باشد .اندازه انبار شركت در حدي است كه ماهانه 4واحد كاال مي‌توان در آن نگه داشت .هزينه‌ي نگهداري هر واحد كاال در هر ماه معادل 2/1است كه در هنگام تحويل كاال به انبا پرداخت مي‌شود .شركت در هر ماه چند واح د ك اال باي د تولي د كن د ك ه ض من ت أمين تقاض ا ،ح داقل هزين ه را بپردازد؟ در اين مسأله موجودي كاالي در ابتداي دوره معادل صفر مسأله تخصيص ظرفيت شركتي داراي 6خط براي توليد سه مدل مختلف تلويزيون است .جدول زير سود ناشي از اختصاص خطوط به مدل‌هاي سه گانه تلويزيون را در هر ماه نشان مي‌دهد. سود ماهانه هر خط تخصيص داده‌شده به هر مدل (بر حسب ميليون ريال) تعداد خطوط تخصيص داده شده مدلA مدلB مدلC 0 15 30 40 45 0 10 15 20 25 0 20 35 45 50 0 1 2 3 4 ت كنيد فرض تناسب براي ميزان سود ارائه شده به ازاي تعداد خطوط اختصاص يافته به هر مدل برقرار نيست .مثًال سود ناشي از تخصيص يك خط به مدل Cبرابر 20است ولي با تخصيص دو خط به اين مدل س ود دوبراب ر نمي‌ش ود بلك ه ب ه 35اف زايش مي‌ياب د .اين ام ر ف رض خطي ب ودن رواب ط را در م دل از بين مي‌ب رد .در عم ل اين وض عيت ممكن اس ت ناش ي از تف اوت ك ارايي خط وط ش ش‌گانه و تف اوت در هزينه‌ه اي متغ ير خط‌ه ا باش د .ه دف در مس أله ،تع يين تع داد خط وط تخصيص داده شده به هر مدل به گونه‌اي است كه سود شركت را حداكثر كند. مسأله كوله‌پشتي يكي از معروف‌ترين مس ائل در برنامه ريزي پويا ،مس أله كوله پشتي و يا هر وسيله حمل بار است .فرض كنيد كل وزني كه مي‌توان با يك وسيله حمل بار جابه‌جا كرد wباشد .همچنين nنوع شي‌ء وجود دارد كه بايد با اين وسيله حمل گردد و ارزش هر شيء معادل viاست .هدف در اين مسأله تعيين پر ارزش‌ترين محموله‌اي است كه مي‌توان با وسيله حمل جابه‌جا كرد .در حالت خاص فرض كني د ح داكثر وزني ك ه ب ا كوله‌پش تي س ربازي مي‌ت وان جابه‌ج ا ك رد 5كيل وگرم است .سه نوع كاالي C, B, Aوجود دارد كه بايد حمل شود .اگر وزن وارزش اين سه نوع كاال به قرار جدول بعد باشد ،از هر كاال به چه تعداد بايد انتخاب كرد تا با ارزش‌ترين محموله حاصل شود؟ نوع كاال وزن هرواحد كاال دو سو چهار م م م 2 1 50 20 2 60 مسأله تخصيص يك منبع كارخانه‌اي سه نوع محصول C, B, Aتوليد مي‌كند .هر محصول نيازمند استفاده از يك نوع ماده اوليه است كه از آن چهار تن در اين كارخانه موج ود اس ت .ب ه ازاي تخص يص م يزان معي ني از م واد اولي ه ب ه ه ر محص ول عاي دي مش خص نص يب كارخان ه خواه د ش د .مق دار من ابع تخصيص يافته و عايد حاصل از آن در جدول زير ارائه گرديده است. محصوالت به منظور حداكثر كردن بهمحصول هدف ،تخصيص بهينه ماده اوليهنوع ‏C B A تخصيص ماده اوليه(تن) عايد كارخانه است. 0 1 2 3 0 0 0 8 6 10 1 17 15 1 - 19 مسأله سرمايه‌گذاري شخصي داراي شش ميليون تومان براي سرمايه‌گذاري در سه سطح مختلف است .اگر dj مقدار سرمايه‌گذاري (بر حسب ميليون تومان) در طرح jباشد و ارزش فعلي خالص ناشي از سرمايه‌گذاي( rj(dj) ،برحسب ميليون تومان) و به صورت زير باشد ،روش بهينه سرمايه گذاري را به گونه‌اي تعيين كنيد تا ارزش فعلي خالص سرمايه‌گذاري حداكثر گردد. )(d1>0 ‏r1(d1) = 7d1+2 )(d2>0 ‏r2(d2) = 3d2+7 )(d3>0 ‏r3(d3) = 4d3+5 ‏r1(0) = r2(0) = r3(0) = 0 توضيح آنكه ،ميزان سرمايه گذاري در هر طرح بايد مضربي صحيح از ميليون تومان باشد. مسأله تخصيص چند منبع كارخانه‌اي مي‌تواند سه نوع محصول C, B, Aدر تعداد‌هاي مختلف توليد كند .ساخت هر واحد از محصوالت مستلزم استفاده از دو نوع ماده اوليه xو yكه براي ،2 ،1و 3واحد از محصوالت سه‌گانه مورد نياز است و درآمد حاصل از توليد آنها در جدول زير ارائه شده است .مطلوب است تعيين ميزان توليد هر محصول به گونه‌اي كه كل درآمد حاصل ،حداكثر گردد. ميزان منابع الزم مقدار توليد 0 1 2 3 ‏A ‏C ‏B X yدرآمد حاصل X yدرآمد حاصل X yدرآمد حاصل 0 10 15 19 0 6 17 - 0 8 11 - مسأله ساخت قطعات مورد نياز محصولي در دو كارگاه مختلف يك كارخانه توليد مي‌گردد .هر كارگاه از دو بخش تشكيل شده‌است .قطعات ساخته‌شده در هر كارگاه به كارگاه مونتاژ منتقل مي‌شود تا محصول نهايي توليد گردد .مراحل توليد در شكل زير نشان داده شده است. ماشين A ماشين B محصول نهايي ماشين Aمواد اوليه ماشين B خط I خط J ماشين C ماشين D ماشين Cمواد اوليه ماشين D همان‌طور كه مشاهده مي‌كنيد ،توليد قطعات يا در كارگاه 1و يا در كارگاه 2 صورت مي‌گيرد .قطعات در هر كارگاه بايد در دو بخش ساخته‌شوند .براي انجام عمليات ساخت در هر بخش از يكي از دو نوع ماشين موجود مي‌توان استفاده كرد .به همين ترتيب ،دو خط مونتاژ نيز در كارگاه 3وجود كه براي مونتاژ نهايي يكي از اين دو خط بايد انتخاب شود. هزينه‌هاي عملياتي با توجه به نوع ماشين‌آالت انتخابي در هر بخش و خطوط مونتاژ با توجه به هزينه‌هاي ثابت و متغير كه در جدول ارائه شده است .در حال حاضر نياز روزانه براي محصول نهايي 4واحد است .هر ماشين بيش از س ه قطع ه در روز نمي‌توان د بس ازد .مس أله انتخ اب ماش ين‌ها و خط وط مونتاژي است كه ضمن تأمين نياز روزانه محصول ،حداقل هزينه را براي كارخانه داشته باشد. ماشي ماشين بعدي ن هزينه ثابت هزينه متغير ماشي ن ماشين بعدي هزينه ثابت هزينه متغير ‏E ‏F ‏E ‏F ‏G ‏H ‏G ‏H ‏I ‏J 12 20 8 13 7 11 16 14 18 10 2 10 4 5 6 2 3 7 6 5 ‏F ‏F ‏G ‏G ‏H ‏H ‏I ‏J ‏I ‏J ‏I ‏J ‏I ‏J - 15 21 11 15 9 17 10 13 4 7 5 3 10 8 4 3 ‏A ‏A ‏B ‏B ‏C ‏C ‏D ‏D ‏E ‏E مسأله فروشنده‌ي دوره‌گرد يكي از مس ائل مع روف و مط رح تحقي ق در عملي ات مس أله‌ي فروش نده‌ي دوره‌گ رد ( )Traveling Salesmanاس ت ك ه كاربرده اي متن وعي دارد .تعري ف مس أله براس اس مسافرت فردي از شهر محل اقامت خود به تعدادي شهر ديگر و نهايت ًا برگشت به محل اقامت خود شكل مي‌گيرد .هدف در اين مسأله پيداكردن كوتاه‌ترين مسيري است كه فرد بايد از ميان مسيرهاي متعدد اين سفر انتخاب كند .به مثال زير توجه كنيد: فروشنده‌ي دوره‌گردي در نظر دارد براي فروش اجناس از رووستاي محل اقامت خود (روستاي )1به سه روستاي اطراف مسافرت كرده ،نهايت ًا به روستاي خود باز گردد .در ص ورتي ك ه فاص له‌ي روس تاها از هم مط ابق ج دول زي ر باش د ،كوت اه‌ترين مس ير س فر فروشنده را تعيين كنيد. روس تاي 1 روستاي 4 روستاي 1 روستاي 2 روستاي 3 روس تاي 2روس تاي 3 15590 13340 13340 13970 13430 15590 8090 13430 9210 مسأله برنامه‌ريزي توليد شركتي درصدد برنامه‌ريزي توليد يك كاال براي دو ماه آينده است .هزينه توليد هر واحد كاال برابر 1000و قيمت فروش آن 2000است .هزينه‌ي انبارداري كاال هر ماه معادل 100است كه در هنگام تحويل كاال به انبار پرداخت مي‌گردد .در صورتي كه كااليي در پايان دو ماه در انبار باقي بماند ،اسقاط محسوب شده و به 4/1قيمت به فروش خواهد رسيد .موجود ابتداي ماه اول صفر و حداكثر توليد در هر م اه برابر 3واح د است .تقاضا در ه ر ماه به ص ورت احتم الي و طبق جدول زير است. مقدار تقاضا در هر ماه احتمال 1 2 3 0 4/025/0 2/0 15/0 هدف ،تعيين بهترين شيوه‌ي توليد با باالترين عايدي است. پایان