Online User تفاوت روش نقاط داخلی و روش سیمپلکس - مدیریت صنعتی Industrial Management

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

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

تفاوت روش نقاط داخلی و روش سیمپلکس
نویسنده : محسن رحیمی - ساعت ۸:٠٠ ‎ب.ظ روز ۱۳٩٠/٩/۱٩
 

یکی از راه‌های مقایسه الگوریتم‌های نقاط داخلی با روش سیمپلکس بررسی پیچیدگی محاسبات و خصوصیات تئوری آن‌هاست. ثابت شده است که ورژن اصلی الگوریتم نقاط داخلی یک الگوریتم زمان چند جمله‌ای (Polynomial time algorithm) است به این معنی که زمان لازم برای حل هر مسئله برنامه ریزی خطی به کمک این الگوریتم، تابعی چند جمله‌ای از اندازه مسئله است. مثال‌های گوناگونی ساخته شده‌اند که نشان می‌دهد روش سیمپلکس این‌گونه نیست و به نوعی در زمره الگوریتم‌های زمان نمایی  ...

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

(670 کلمه)

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

مطلب مرتبط قبلی: روش نقاط داخلی


یکی از راه‌های مقایسه الگوریتم‌های نقاط داخلی با روش سیمپلکس بررسی پیچیدگی محاسبات و خصوصیات تئوری آن‌هاست. ثابت شده است که ورژن اصلی الگوریتم نقاط داخلی یک الگوریتم زمان چند جمله‌ای (Polynomial time algorithm) است به این معنی که زمان لازم برای حل هر مسئله برنامه ریزی خطی به کمک این الگوریتم، تابعی چند جمله‌ای از اندازه مسئله است. مثال‌های گوناگونی ساخته شده‌اند که نشان می‌دهد روش سیمپلکس این‌گونه نیست و به نوعی در زمره الگوریتم‌های زمان نمایی (Exponential time algorithm) قرار دارد یعنی زمان لازم برای حل هر مسئله برنامه ریزی خطی به کمک این روش، تابعی نمایی از اندازه مسئله است.

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

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

برای مسائل کوچک، تعداد تکرار‌های لازم برای حل نهایی مسئله توسط هر دو روش تقریباً یکسان است. برای مثال در مسئله‌ای با 10 محدودیت ساختاری، هر دو الگوریتم نیاز به حل 20 تکرار دارند. در نتیجه در مسائلی با این اندازه، کل زمان لازم برای حل توسط کامپیوتر با روش نقاط داخلی بسیار بیشتر از حل به کم روش سیمپلکس است.

نقطه کلیدی و مزیت اصلی روش نقاط داخلی این است که تعداد تکرارهای لازم برای حل مسائل بسیار بزرگ خیلی بیشتر از تکرار لازم برای حل مسائل کوچکتر نمی‌باشد. برای مثال مسئله‌ای که دارای 10000 محدودیت ساختاری باشد احتمالاً با چیزی کمتر از 100 تکرار توسط روش نقاط داخلی حل خواهد شد اما روش سیمپلکس برای حل چنین مسئله‌ای باید حدود 20000 تکرار را حل نماید. با در نظر گرفتن این مطلب، اگر چه میانگین زمان حل هر تکرار در روش نقاط داخلی بسیار بالاست اما استفاده از آن در چنین مواردی مطلوب‌تر است. بنابراین الگوریتم نقاط داخلی اغلب سریع‌تر از روش سیمپلکس مسائل بسیار بزرگ را حل می‌کند.

دلیل اختلاف بسیار زیادی که در تعداد تکرارهای لازم در این دو روش وجود دارد، به مسیری که این دو روش برای رسیدن به جواب نهایی طی می‌کنند بر می‌گردد. در روش سیمپلکس در هر تکرار از نقطه CPF کنونی به یکی از نقاط CPF مجاور که بر روی مرزهای منطقه موجه قرار دارد حرکت می‌کنیم. در مسائل بسیار بزرگ تعداد نقاط CPF می‌تواند نجومی و در نتیجه ممکن است مسیر طی شده از نقطه CPF اولیه به جواب نهایی مسیری بلند و پر پیچ و خم باشد و تعداد تکرارها به همین دلیل بسیار زیاد خواهد شد. در مقابل از آنجا که الگوریتم نقاط داخلی، در فضای موجه درونی حرکت می‌کند با چنین مشکلی روبرو نیست. افزایش تعداد محدودیت‌ها به مسئله، باعث افزایش تعداد نقاط CPF می‌گردد و این امر تأثیر کمی ‌بر تعداد تکرارها در روش نقاط داخلی دارد. این ویژگی باعث می‌شود که الگوریتم نقاط داخلی انتخاب مناسبی برای حل مسائل بسیار بزرگ باشد.

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

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

مطلب مرتبط قبلی: روش نقاط داخلی