Online User حل مسائل غیر استاندارد با سیمپلکس – وجود محدودیت مساوی (قسمت اول) (روش M بزرگ) - مدیریت صنعتی Industrial Management

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

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

حل مسائل غیر استاندارد با سیمپلکس – وجود محدودیت مساوی (قسمت اول) (روش M بزرگ)
نویسنده : محسن رحیمی - ساعت ۸:٢٩ ‎ب.ظ روز ۱۳٩٠/٦/۱۸
 

هر محدودیت به شکل معادله

در اصل برابر است با جفت محدودیت غیر مساوی زیر:

با این حال، به جای استفاده از این جایگزینی و افزایش دادن تعداد محدودیت ها، بهتر است از تکنیک متغیرهای مصنوعی استفاده کنیم. این تکنیک را با مثال زیر تشریح می کنیم:

مثال: مسئله شرکت ویندور را دوباره به خاطر آورید با این اصلاح که لازم است از کل ظرفیت کارخانه سوم استفاده شود. در نتیجه تفاوت مدل جدید و با مدل قبلی آن است که محدودیت سوم،

به یک معادله به صورت

تبدیل خواهد شد.

بنابراین مدل کامل مسئله جدید به صورت روابط نشان داده شده در گوشه بالا، سمت راست شکل 1 تغییر خواهد کرد. همچنین از شکل کاملاً مشخص است که منطقه موجه تنها یک پاره خط بین نقاط (2,6) و (4,3) است.

پس از آنکه متغیرهای کمبود مورد نیاز به محدودیت های نامعادله افزوده شد، مجموعه معادلات مربوط به فرمت افزوده مسئله به شرح زیر خواهد بود:

متاسفانه این معادلات دارای یک جواب BF اولیه واضح نیستند زیرا معادله (3) دارای متغیر کمبود نیست که بتوان از آن به عنوان متغیر پایه اولیه استفاده نمود. برای شروع روش سیمپلکس لازم است به یک جواب BF اولیه دسترسی داشته باشیم.

شکل 1 . حالت ترسیمی مسئله شرکت ویندور در صورت تبدیل شدن محدودیت ساختاری سوم به معادله

بدست آوردن جوابBF ابتدایی: این فرآیند شامل ساخت یک مسئله مصنوعی است که جواب بهینه آن، جواب بهینه مسئله اصلی نیز می باشد. در این فرایند دو تغییر زیر در مسئله اصلی صورت می گیرد:

  • بکاربردن تکنیک متغیرهای مصنوعی با افزودن یک متغیر مصنوعی غیر منفی به معادله 3، که معادله مذکور را به شکل زیر تغییر می دهد:

  • تخصیص یک جریمه بسیار زیاد به تابع هدف برای شرایط

    که تابع هدف را به صورت زیر تغییر خواهد داد:

    که M نماد یک عدد مثبت بسیار بزرگ است. (در این روش که باعث می شود مقدار صفر گردد را روش M بزرگ (Big M) می گویند.)

حال با استفاده از روش سیمپلکس و بکارگیری آن بر روی مسئله مصنوعی، جواب بهینه ای بدست می آید که جواب بهینه مسئله اصلی نیز می باشد. برای شروع از جواب BF اولیه زیر استفاده می کنیم:

متغیرهای غیر پایه: 

متغیرهای پایه: 

از آنجا که در مسئله مصنوعی نقش متغیر کمبود را برای محدودیت سوم بازی می کند، این محدودیت مشابه محدودیت

(که دقیقاً در مدل مسئله اصلی نیز وجود دارد) عمل می کند. در زیر مسئله اصلی و مسئله مصنوعی حاصل از آن آورده شده است:

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

یعنی داشته باشیم:

شکل 2 همچنین ترتیب جواب های CPF (یا جواب های BF پس از تبدیل مسئله به مسئله افزوده) محاسبه شده در روش سیمپلکس را نشان می دهد و اعداد درون دایره ها بیانگر این مطلب هستند که هر جواب در کدام تکرار محاسبه شده است. دقت داشته باشید که در اینجا جهت حرکت روش سیمپلکس بر خلاف عقربه های ساعت است در صورتیکه در حل مسئله اصلی شرکت ویندور جهت این حرکت مطابق با عقربه های ساعت بود. دلیل این اختلاف وجود عبارت اضافه شده

به تابع هدف مسئله مصنوعی است.

شکل 2 . حالت ترسیمی مسئله شرکت ویندور در صورت تبدیل شدن محدودیت ساختاری سوم به معادله

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

مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس- وجود محدودیت مساوی (قسمت دوم)

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس – مقدمه