Online User روش دوفازی (The Two-Phase Method) - مدیریت صنعتی Industrial Management

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

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

روش دوفازی (The Two-Phase Method)
نویسنده : محسن رحیمی - ساعت ٦:٤٥ ‎ب.ظ روز ۱۳٩٠/٧/٢٥
 

در این بخش برای آشنایی با روش دوفازی، مسئله زیر را بوسیله روش دوفازی حل می کنیم.

 

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

(1050 کلمه/1 عکس/3 جدول)

مطلب مرتبط بعدی: روش M بزرگ یا روش دوفازی؟

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


در این بخش برای آشنایی با روش دوفازی، مسئله زیر را بوسیله روش دوفازی حل می کنیم.

 تابع هدف مسئله عبارت است از:

روش M بزرگ برای حل این مسئله از تابع هدف زیر استفاده نمود:

از آنجا که M عددی بسیار بزرگ در نظر گرفته می شود، ضریب دو عبارت اول تابع بالا در مقایسه با M بسیار کوچک هستند. روش دو فازی، با در نظر گرفتن دو تابع هدف زیر، هر یک برای یک فاز جداگانه، می تواند M را حذف نماید.

تابع هدف فاز اول، با تقسیم تابع هدف روش M بزرگ بر M و سپس حذف عبارات بسیار کوچک (اعداد تقسیم بر M) بدست می آید. هدف فاز اول بدست آوردن یک جواب BF برای مسئله اصلی است که در آن x4=0 (بار) و x6=0 (بار) است. در فاز دوم از این جواب به عنوان جواب BF اولیه در روش سیمپلکس برای حل مسئله اصلی استفاده می شود. تابع هدف فاز دوم همان تابع هدف مسئله است.

قبل از اینکه مثال را با روش دوفازی حل کنیم، خلاصه ای از کلیات این روش را بیان می کنیم:

خلاصه ای از روش دو فازی

شروع: محدودیت های مسئله را با وارد کردن متغیرهای مصنوعی مناسب بازنویسی نمایید.

فاز اول: هدف این فاز یافتن یک جواب BF برای مسئله اصلی است. برای این کار تابع هدف به صورت مینیمم کردن مجموع متغیرهای مصنوعی تعریف می شود. جواب بهینه ای که از این مسئله به دست می آید (با Z=0)، در حقیقت یک جواب BF برای مسئله اصلی است.

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

برای مثال، در صورتیکه بخواهیم مسئله را به کمک روش دو فازی حل کنیم، مسائلی که در فازهای اول و دوم باید حل شوند عبارت خواهند بود از:

فاز اول:

فاز دوم:

تنها تفاوت بین مسائل فاز اول و دوم، معادله تابع هدف و وجود (فاز اول) و عدم وجود (فاز دوم) متغیرهای مصنوعی x4 (بار) و x6 (بار) است. بدون استفاده از متغیرهای مصنوعی، مسئله فاز دوم دارای جواب BF اولیه ای که براحتی بتوان ان را تشخیص داد، نمی باشد. هدف اصلی حل مسئله فاز اول یافتن جواب BF خاصی است که که در آن x4=0 (بار) و x6=0 (بار) باشد (یعنی بدون متغیر مصنوعی) و بتوان از آن به عنوان جواب BF اولیه برای مسئله فاز 2 استفاده نمود.

جدول 1 نتایج به کارگیری روش سیمپلکس برای حل مسئله فاز 1 را نشان می دهد. ردیف 0 در جدول ابتدایی با تبدیل تابع هدف

به تابع هدف

و سپس اعمال عملیات حذف اولیه برای کنار گذاشتن متغیرهای x4 (بار) و x6 (بار) از

بدست آمده است. در جدول یکی مانده به آخر x3 یا x5 هر دو می توانند به عنوان متغیر پایه ای ورودی انتخاب شوند که در اینجا به صورت اختیاری متغیر x3 را انتخاب می کنیم. جوابی که در پایان فاز 1 بدست آمده عبارت است از

که با در نظر نگرفتن x4 (بار) و x6 (بار)خواهیم داشت:

.

همانطور که در خلاصه نیز عنوان شد، این جواب می تواند یک جواب BF برای مسئله اصلی (مسئله فاز 2) باشد زیرا این جواب در دستگاه معادلات سه محدودیت ساختاری مسئله فاز 2 صدق می کند. در حقیقت می توان گفت اگر از جدول 19 ستون های x4 (بار) و x6 (بار) را حذف کنیم، جدول جدید نمایش دهنده راهی برای حل دستگاه معادلات مسئله با استفاده از حذف گوسی و تبدیل آن به قالبی است که در جدول نهایی قابل مشاهده است.

جدول 1. فاز اول از حل مسئله به کمک روش دوفازی

 جدول 2 نحوه آماده کردن نتیجه نهایی بدست آمده از فاز 1 را برای ورود به فاز دوم نشان می دهد. با جدول پایانی سیمپلکس فاز اول (یعنی آخرین بخش جدول 1) شروع می کنیم و متغیرهای مصنوعی (در اینجا x4 (بار) و x6 (بار)) را حذف می کنیم و تابع هدف مسئله فاز دوم را جایگزین ردیف 0، ردیف مربوط به تابع هدف می کنیم و با استفاده از قواعد حذف گوسی ضرایب متغیرهای x4 (بار) و x6 (بار) را در سطر 0 به صفر می رسانیم تا جدول شکل صحیح خود را بیابد. برای این کار 0.4 برابر سطر یک و 0.5 برابر سطر 3 را در جدول یکی مانده به آخر از سطر صفر کم می کنیم تا سطر صفر نمایش داده شده در جدول آخر بدست آید. ملاحظه می کنید که سطر های 1 و 3 به غیر حذف دو ستون مربوط به متغیرهای مصنوعی تغییر دیگری نکرده اند و تنها تنظیماتی در سطر 0 صورت گرفته است تا تابع هدف مسئله فاز 2 جایگزین تابع هدف فاز 1 شود.

جدول 2. آماده سازی برای ورود به فاز دوم

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

بدست خواهد آمد. این جواب، جواب دلخواه برای مسئله اصلی است.

جدول 3. فاز دوم حل مسئله با روش دوفازی

حال در شکل 1 به صورت ترسیمی خواهیم دید که روش دوفازی چگونه عمل می کند. با شروع از نقطه مبدا، فاز اول چهار جواب CPF مسئله مصنوعی را مورد بررسی قرار می دهد. سه جواب ابتدایی، جواب های گوشه ای غیر موجه برای مسئله اصلی هستند که در شکل 1 به خوبی این مطلب قابل مشاهده است. جواب CPF چهارم، یعنی (6,6)، اولین جوابی است که در محدودیت های مسئله اصلی صدق می کند و به عبارت دیگر جواب موجه مسئله اصلی است و همان جواب CPF اولیه برای مسئله فاز دوم است. یک تکرار در فاز دوم کافی است تا به جواب CPF بهینه در (7.5,4.5) برسیم.

شکل 1. چگونگی حل مسئله به کمک روش دوفازی

اگر در انتخاب متغیر پایه ورودی در جدول سیمپلکس یکی به آخر جدول 1، متغیر دیگر یعنیx5 انتخاب می گردید، در فاز اول مستقیماً از (8,3) به (7.5,4.5) منتقل می شدیم و در نتیجه در جدول ابتدایی فاز دوم آزمون بهینگی نشان می داد که جدول بهینه است و بنابراین احتیاج به تکرار در فاز دوم نمی بود.

مطلب مرتبط بعدی: روش M بزرگ یا روش دوفازی؟

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