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

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

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

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

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

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

(760 کلمه)

مطلب مرتبط بعدی:نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی

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


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

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

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

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

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

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

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

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

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

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

مطلب مرتبط بعدی: نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی

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