Online User روش نقاط داخلی (Interior-point approach) - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

روش نقاط داخلی (Interior-point approach)
نویسنده : محسن رحیمی - ساعت ٩:۳٦ ‎ب.ظ روز ۱۳٩٠/٩/٥
 

جالب‌ترین روشی که در دهه 1980 برای حل مسائل برنامه ریزی خطی ابداع شد روشی بود به نام روش نقاط داخلی (Interior-point approach) که توسط یک ریاضیدان جوان به نام نارندرا کارمارکار در آزمایشگاه AT&T Bell در سال 1984 معرفی شد. اگر چه این روش در ابتدا در مقایسه با روش سیمپلکس توجه‌ها را به خود جلب ننمود اما اصول و مفاهیم کلیدی به کار رفته در آن که در ادامه نیز به آن‌ها می‌پردازیم نشان می‌داد که این روش خاص پتانسیل حل مسائل برنامه ریزی خطی بسیار بزرگ را به گونه‌ای دارد که روش سیمپلکس به سختی آن‌ها را حل می‌کند.

 

 

برای مطالعه متن کامل این مقاله روی گزینه "ادامه مطلب" کلیک کنید.

(588 کلمه)

مطلب مرتبط بعدی: تفاوت روش نقاط داخلی و روش سیمپلکس

مطلب مرتبط قبلی: تحلیل های پس از بهینه سازی به کمک سیمپلکس


جالب‌ترین روشی که در دهه 1980 برای حل مسائل برنامه ریزی خطی ابداع شد روشی بود به نام روش نقاط داخلی (Interior-point approach) که توسط یک ریاضیدان جوان به نام نارندرا کارمارکار در آزمایشگاه AT&T Bell در سال 1984 معرفی شد. اگر چه این روش در ابتدا در مقایسه با روش سیمپلکس توجه‌ها را به خود جلب ننمود اما اصول و مفاهیم کلیدی به کار رفته در آن که در ادامه نیز به آن‌ها می‌پردازیم نشان می‌داد که این روش خاص پتانسیل حل مسائل برنامه ریزی خطی بسیار بزرگ را به گونه‌ای دارد که روش سیمپلکس به سختی آن‌ها را حل می‌کند. محققان زیادی جهت اصلاح و بهبود این الگوریتم کار کردند و به همین دلیل الگوریتم‌های قدرتمندی بر اساس روش نقاط داخلی ابداع و معرفی نمودند. امروزه، اغلب نرم افزارهای قدرتمند طراحی شده جهت حل مسائل بزرگ برنامه ریزی خطی حداقل یکی از الگوریتم‌های ابداع شده بر اساس روش نقاط داخلی را در کنار روش سیمپلکس دارند. همان‌طور که تحقیقات بر روی بهبود این روش ادامه داشت، تلاش‌های فراوانی جهت به‌کارگیری آن به صورت کامپیوتری در نرم افزارهای گوناگون نیز انجام می‌شد. تفاوت بین روش سیمپلکس و روش نقاط داخلی در اصل در حل مسائل با اندازه‌های مختلف مشخص می‌شود.

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

مفاهیم کلیدی حل به روش نقاط داخلی

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

تفاوت اصلی در ماهیت جواب‌ها است. در روش سیمپلکس جواب‌های بدست آمده از هر تکرار، جواب‌های CPF (نقاط گوشه‌ای موجه) بودند و بنابراین مسیری که روش سیمپلکس برای بهبود جواب‌ها طی می‌کرد بر مرزهای منطقه موجه مسئله بود. اما در روش نقاط داخلی نقاط جواب نقاط داخلی هستند، یعنی نقاطی هستند که درون مرزهای منطقه موجه قرار دارند. به همین دلیل به الگوریتم کارمارکار و روش‌های توسعه یافته آن الگوریتم‌های نقاط داخلی می‌گویند.

شکل زیر مسیر طی شده توسط الگوریتم نقاط داخلی را برای حل مسئله شرکت ویندور نشان می‌دهد که از نقطه (1,2) شروع شده است.

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

همان‌طور که می‌بینید همه جواب‌های نشان داده شده در طول مسیر درون مرزهای منطقه موجه مسئله قرار دارند و در انتها به نقطه (2,6) ختم می‌شوند. البته همه جواب‌های حاصل از این روش در شکل نشان داده نشده است اما آن‌ها نیز همین خاصیت را دارند. جواب‌های کامل را می‌توانید در جدول زیر مشاهده کنید. حال می‌توانید این مسیر را با مسیر طی شده توسط روش سیمپلکس برای حل مسئله شرکت ویندور (از(0,0) به (0,6) و در نهایت به(2,6)) مقایسه کنید.

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

 

جدول 1. جواب‌های حاصل از تکرارهای روش نقاط داخلی برای حل مسئله شرکت ویندور

مطلب مرتبط بعدی: تفاوت روش نقاط داخلی و روش سیمپلکس

مطلب مرتبط قبلی: تحلیل های پس از بهینه سازی به کمک سیمپلکس