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

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

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

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

یافتن جواب BF جدید (مرحله سوم تکرار)

افزایش مقدار متغیر x2از صفر به 6 ما را از جواب BF اولیه به جواب BF جدید منتقل می کند.

 

جواب BF اولیه

جواب BF جدید

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

x1=0, x2=0

x1=0, x4=0

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

x3=4, x4=12, x5=18

x3=?, x2=6, x5=?

 هدف از مرحله سوم تبدیل سیستم معادلات به شکلی ساده تر برای محاسبه آزمون بهینگی و در صورت لزوم رفتن به تکرار بعدی با این جواب BF جدید است که این قالب ساده تر از طریق فرآیندی به نام حذف گوسی بدست می آید. در حین این فرآیند مقادیر x3 و x5 نیز برای جواب جدید محاسبه می شوند.

در اینجا دوباره سیستم معادلات اصلی مسئله را ارائه می کنیم. همانطور که مشاهده می کنید Z در تابع هدف نقش یک متغیر پایه را بازی می کند:

تنها تفاوتی که وجود دارد این مطلب است که متغیر x2 به جای متغیر x4 وارد متغیرهای پایه شده است. برای حل این دستگاه معادلات و محاسبه Z، x2، x3 و x5 لازم است به منظور ایجاد الگوی ضرایب (0,0,1,0) برای متغیر x2 به جای متغیر x4 و باز نویسی دستگاه معادلات، از چند عملیات جبری اولیه استفاده شود. برای این کار می توان از دو نوع عملیات جبری ساده زیر استفاده نمود:

  • ضرب (تقسیم) یک معادله در (بر) یک عدد ثابت غیر صفر.
  • جمع (کسر) مضربی از یک معادله با (از) معادله ای دیگر.

برای استفاده از این عملیات ها، دقت داشته باشید که ضرایب متغیر x2 در دستگاه معادلات بالا به ترتیب عبارتند از 2, 0, -5 و 3 که باید به 1, 0, 0 و 0 تبدیل شوند. برای تبدیل ضریب 2 در معادله (2) به 1، از اولین نوع عملیات جبری استفاده نموده و معادله (2) را بر 2 تقسیم می کنیم و حاصل عبارت خواهد بود از:

برای تبدیل ضرایب -5 و 3 به صفر، باید از عملیات نوع دوم استفاده شود. برای این کار ما پنج برابر معادله (2) جدید را به معادله (0) اضافه می نماییم و 2 برابر معادله (2) جدید را از معادله (3) کسر می کنیم. دستگاه معادلات جدید عبارت خواهد بود از:

 از آنجا که داریم x1=0 و x4=0، به کمک دستگاه بازنویسی شده بالا به سادگی می توان جواب BF جدید را به صورت (x1,x2,x3,x4,x5)=(0,6,4,0,6) بدست آورد که در این نقطه جواب جدید داریم Z=30.

به این فرآیند که برای ایجاد دستگاه معادلات جدید و حل آن انجام می گیرد روش حذفی گوس جردن (Gauss-Jordan method of elimination) و یا به اختصار حذف گوسی می گویند. مفهوم کلیدی این روش استفاده از عملیات های جبری ساده جهت تبدیل دستگاه معادلات اصلی به دستگاهی جدید از معادلات است که در آن هر متغیر پایه تنها در یک معادله و آن هم یا ضریب +1 دیده می شود و از دیگر معادلات حذف شده است.

آزمون بهینگی برای جواب BF جدید

معادله (0) جدید مقدار تابع هدف را در حالی می دهد که تنها متغیرهای غیرپایه در رابطه آن وجود دارند:

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

تکرار دوم و محاسبه جواب بهینه

با توجه به معادله

،

مقدار Z با افزایش متغیر x1 و نه متغیر x4 افزایش خواهد داشت. بنابراین مرحله اول متغیر x1 را به عنوان متغیر پایه ورودی در این تکرار انتخاب می کند.

در مرحله دوم برای محاسبه حداکثر مقداری که متغیر x1 می توان افزایش یابد از آزمون حداقل نسبت استفاده نموده و محاسبات آن با توجه به اینکه x4=0 به شرح زیر است:

بنابراین، آزمون حداقل نسبت بیان می کند که متغیر x5، متغیر پایه خروجی است.

در مرحله سوم، با جایگزینی متغیر x1 به جای x5 در متغیر های پایه و بکارگیری عملیات های جبری برای بازنویسی دستگاه معادلات فعلی به دستگاه معادلاتی که در آن ضرایب متغیر پایه ورودی،x1، به صورت (0,0,0,1) باشد خواهیم داشت:

بنابراین جواب BF بعدی عبارت است از (x1,x2,x3,x4,x5)=(2,6,2,0,0) که در این نقطه داریم Z=36. برای بکارگیری آزمون بهینگی در رابطه با جواب BF جدید، از معادله (0) کنونی که مقدار Z را بر اساس متغیرهای غیرپایه ارائه می دهد استفاده می کنیم:

با توجه به این معادله افزایش هر کدام از دو متغیر غیرپایه x4 و x5 باعث کاهش مقدار Z می گردد و در نتیجه هیچ کدام از جواب های BF مجاور به خوبی جواب فعلی نیست. بنابراین بر اساس مفهوم کلیدی 6 جواب BF کنونی جواب بهینه است.

با توجه به شکل اصلی مدل مسئله که دارای متغیرهای کمبود نمی باشد، جواب بهینه عبارت است از x1=2 ، x2=6 که در نتیجه خواهیم داشت:

.

در بخش آینده خلاصه ای از روش سیمپلکس بر اساس فرمت جدولی آن که کاربرد بسیار زیاد و راحتی دارد بیان خواهد شد.

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

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