Online User دیدگاه جبری روش سیمپلکس (قسمت اول) - مدیریت صنعتی Industrial Management

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

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

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

برای ادامه بحث در روش سیمپلکس و توضیح دیدگاه جبری این روش همچنان از مسئله شرکت ویندور کمک می گیریم. برای بررسی رابطه مفاهیم هندسی و مفاهیم جبری روش سیمپلکس، مرحله به مرحله چگونگی حل مسئله مذکور از دو دیدگاه هندسی و جبری، در جدول 1 آورده شده است. دیدگاه هندسی که در مطالب قبل اشاره شد بر اساس قالب اصلی مدل که دارای متغیرهای کمبود نمی باشد ارائه گردید. در ادامه به جزئیات هر مرحله از دیدگاه جبری (ستون سوم جدول) اشاره شده است.

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

مرحله حل 

تفسیر هندسی 

تفسیر جبری 

شروع

(0,0) را به عنوان جواب CPF اولیه انتخاب کنید.

X1 و x2 را به عنوان متغیرهای غیرپایه برای جواب BF اولیه قرار دهید: (0,0,4,12,18)

تست بهینگی 

جواب بهینه نیست، زیرا حرکت بر هر دو لبه خروجی از (0,0) باعث افزایش Z می گردد.

جواب بهینه نیست، زیرا افزایش هر یک از متغیرهای غیرپایه (x1 و x2) باعث افزایش Z می گردد.

تکرار اول 

   

مرحله 1 

بر روی لبه واقع بر محور x2 حرکت کنید

مقدار x2 را تا حدی افزایش می دهیم که تغییر در متغیرهای پایه دیگر منجر به خروج از منطقه موجه نگردد.

مرحله 2 

هنگامی که به اولین مرز محدودیت جدید (2x2=12) برخورد کردید حرکت را متوقف نمایید.

زمانیکه اولین متغیر پایه به صفر رسید متوقف شوید. (x4)

مرحله 3 

نقطه تقاطع جفت مرز محدودیت جدید را بیابید: (0,6) جوای CPF جدید است.

با وارد شدن متغیر x2 در متغیرهای پایه و خارج شدن متغیر x4 از پایه و تبدیل آن به متغیر غیر پایه، دستگاه معادلات جدید حل شود: (0,6,4,0,6) جواب BF جدید است.

آزمون بهینگی 

جواب بهینه نیست زیرا با حرکت بر لبه خروجی از (0,6) به سمت راست مقدار Z افزایش می یابد.

جواب بهینه نیست زیرا افزایش متغیر غیر پایه x1 باعث افزایش Z می گردد.

تکرار دوم 

   

مرحله 1 

بر روی لبه انتخاب شده به جلو حرکت کنید 

مقدار x1 را تا حدی افزایش می دهیم که تغییر در متغیرهای پایه دیگر منجر به خروج از منطقه موجه نگردد.

مرحله 2 

هنگامی که به اولین مرز محدودیت جدید (3x1+2x2=18) برخورد کردید حرکت را متوقف نمایید.

زمانیکه اولین متغیر پایه به صفر رسید متوقف شوید. (x5)

مرحله 3 

نقطه تقاطع جفت مرز محدودیت جدید را بیابید: (2,6) جوای CPF جدید است.

با وارد شدن متغیر x1 در متغیرهای پایه و خارج شدن متغیر x5 از پایه و تبدیل آن به متغیر غیر پایه، دستگاه معادلات جدید حل شود: (2,6,2,0,0) جواب BF جدید است.

آزمون بهینگی 

جواب (2,6) بهینه است زیرا با حرکت بر هر کدام از لبه های خروجی از (2,6)، مقدار Z کاهش می یابد.

جواب (2,6,2,0,0) بهینه است زیرا افزایش هیچ کدام از متغیرهای غیر پایه، باعث افزایش Z نمی گردد.

 شروع

انتخاب x1 و x2 به عنوان متغیرهای غیرپایه (متغیرهایی که مقدار صفر می گیرند) در جواب BF اولیه بر اساس مفهوم کلیدی حل شماره 3 ارائه شده در مطلب 6 مفهوم کلیدی که بیان می کند در صورت امکان در مرحله شروع روش سیمپلکس بهتر است نقطه مبداء، یعنی نقطه ای که همه متغیرهای تصمیم برابر با صفر باشند، به عنوان جواب CPF اولیه انتخاب گردد؛ صورت گرفته است. این تصمیم باعث می شود متغیرهای پایه (x3,x4,x5) در مدل زیر به سادگی محاسبه شوند.

بنابراین جواب BF اولیه (0,0,4,12,18) خواهد بود.

همانطور که ملاحظه می کنید هر معادله تنها دارای یک متغیر پایه است که دارای ضریب یک می باشد و این متغیرهای پایه تنها در یک معادله حضور دارند و در معادلات دیگر وجود ندارند و به واسطه این دلایل، جواب اولیه را می توان به راحتی با مشاهده سیستم معادلات نیز بدست آورد. در ادامه خواهید دید هنگامی که مجموعه متغیرهای پایه تغییر می کنند، روش سیمپلکس از یک رویه جبری (حذف گوسی) برای تبدیل معادلات جاری به معادلاتی به همین قالب ساده استفاده می کنند تا بتوان جواب BF بعدی را به راحتی محاسبه نمود. به این قابل ساده از معادلات در اصطلاح فرم صحیح حاصل از حذف گوسی (proper form from Gaussian elimination) می گویند.

تست بهینگی

تابع هدف عبارت است از

بنابراین برای جواب BF اولیه Z=0 می گردد زیرا هیچ یک از متغیرهای پایه (x3,x4,x5) دارای ضریب غیر صفر در تابع هدف نیستند. ضریب هر متغیر غیر پایه (x1,x2) نشان دهنده نرخ بهبود در Z در صورت افزایش آن متغیر از مقدار 0 است. مقدار تغییر در متغیر غیر پایه تا حدی باید ادامه یابد که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند. نرخ های بهبود در این مسئله (3 و 5) مقادیری مثبت هستند. بنابراین بر اساس مفهوم کلیدی شماره 6 نتیجه می گیریم که (0,0,4,12,18) بهینه نیست.

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

تعیین جهت حرکت (مرحله اول تکرار)

افزایش یک متغیر غیرپایه از مقدار 0 (تا حدی که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند) یعنی حرکت بر روی یکی از لبه های خروجی از جواب CPF جاری. اینکه کدام متغیر غیر پایه باید برای افزایش انتخاب گردد، بر اساس مفاهیم کلیدی شماره 4 و 5 ارائه شده در مطلب 6 مفهوم کلیدی صورت می گیرد. از آنجا که نرخ بهبود تابع هدف، Z، برای متغیر x1 برابر است با 3 و برای متغیر x2 برابر است با 5، بنابراین متغیری انتخاب می شود که نرخ بهبود بیشتری داشته باشد یعنی در این مرحله متغیر x2 انتخاب می شود. بر اساس توضیحی که در ادامه می آید متغیر x2 به عنوان متغیر پایه ورودی برای تکرار اول انتخاب می شود.

در هر تکرار از روش سیمپلکس، هدف مرحله اول انتخاب یک متغیر غیر پایه برای افزایش از مقدار 0 است تا حدی که که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند. افزایش مقدار متغیر غیرپایه انتخاب شده از صفر، این متغیر را به متغیری پایه برای جواب BF بعدی تبدیل می کند. بنابراین به این متغیر، متغیر پایه ورودی (entering basic variable) برای تکرار جاری می گویند.

تعیین محل توقف حرکت (مرحله دوم تکرار)

مرحله دوم تکرار به این سوال پاسخ می دهد که افزایش متغیر پایه ورودی باید تا کجا ادامه یابد. افزایش متغیر x2 باعث افزایش مقدار Z می گردد، بنابراین باید این افزایش تا حد ممکن ادامه یابد بدون آنکه جواب از منطقه موجه خارج شود. زمانی که متغیر غیر پایه x1=0 ثابت نگه داشته شود و x2 افزایش یابد، مقادیر متغیرهای پایه دیگر نیز با توجه به رابطه های زیر تغییر می کند:

تغییر در این متغیرهای پایه باید به گونه ای باشد که غیر منفی بمانند. متغیرهای غیر پایه (که متغیر ورودی را نیز شامل می شود) غیر منفی هستند اما باید کنترل کنیم که مقدار متغیر x2 تا چه مقدار می تواند افزایش یابد به شکلی که متغیر های پایه نیز در محدودیت های غیر منفی بودن صدق کنند:

روابط بالا نشان می دهد که متغیر x2 تا مقدار 6 می تواند افزایش یابد. در این مقدار متغیر x4 به مقدار صفر نزول می کند و افزایش بیشتر متغیر x2 باعث غیر منفی شدن متغیر x4 می گردد و این یعنی خروج از منطقه موجه.

به محاسباتی که در بالا انجام شد در اصطلاح آزمون حداقل نسبت (Minimum ratio test) می گویند. هدف از این آزمون تعیین متغیر پایه ای است که با افزایش متغیر ورودی زودتر از بقیه به مقدار صفر می رسد. اگر در هر یک از معادلات محدودیت های مسئله، ضریب متغیر ورودی صفر یا منفی باشد، متغیرهای پایه موجود در این معادلات در اثر افزایش متغیر ورودی کاهش نخواهند داشت. برای مثال در معادله اول متغیر x3 از افزایش متغیر x2 تاثیر نمی پذیرد و در نتیجه لازم نیست آزمون حداقل نسبت در رابطه با این متغیر انجام شود. همینطور دقت کنید که برای هر معادله ای که ضریب متغیر ورودی مثبت مطلق است (>0)، این آزمون نسبت مقدار سمت راست به ضریب متغیر ورودی در معادله مورد نظر را محاسبه می کند. متغیر پایه ای که در معادله ای قرار دارد که کمترین نسبت را داراست، اولین متغیری است که با افزایش متغیر ورودی به مقدار صفر نزول می کند.

در هر تکرار از روش سیمپلکس، مرحله دوم از آزمون حداقل نسبت به منظور تعیین متغیر پایه ای که با افزایش متغیر ورودی زودتر به صفر می رسد استفاده می کند. کاهش مقدار این متغیر به صفر آن را تبدیل به متغیر غیر پایه در جواب BF بعدی خواهد کرد. بنابراین در تکرار جاری به این متغیر، متغیر پایه خروجی(Leaving basic variable) می گویند.

بنابراین متغیر x4، متغیر پایه خروجی برای تکرار اول این مثال است.

مطلب مرتبط بعدی: دیدگاه جبری روش سیمپلکس (قسمت دوم)

مطلب مرتبط قبلی: آماده سازی مسئله برای حل با روش جبری سیمپلکس