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

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

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

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

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

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

در جدول 1 سعی شده است مقایسه بین دستگاه معادلات اولیه مسئله شرکت ویندور در فرمت جبری و فرمت جدولی آورده شود که به جدول ارائه شده در سمت راست در اصطلاح جدول سیمپلکس (Simplex tableau) می گویند. متغیرهای پایه در جدول ابتدایی عبارت بودند از x3، x4 و x5 و متغیرهای دیگر متغیرهای غیرپایه هستند. بعد از قرار دادن x1=0 و x2=0، ستون سمت راست مقادیر متغیرهای پایه را می دهد و به این ترتیب جواب BF اولیه عبارت خواهد بود از (x1,x2,x3,x4,x5)=(0,0,4,12,18) که بر اساس این جواب خواهیم داشت Z=0.

شکل جدولی روش سیمپلکس برای نمایش مختصر و مفید دستگاه معادلات مورد استفاده جهت یافتن جواب BF صحیح از جدول سیمپلکس استفاده می کند. در جدول سیمپلکس مقدار هر متغیری که در ستون سمت چپ قرار داشته باشد برابر است با عدد واقع در همان سطر و در ستون سمت راست جدول و هر متغیری نیز که در ستون مذکور قرار ندارد متغیر غیر پایه بوده و مقدارش صفر است. هنگام انجام آزمون بهینگی و همچنین هنگام انجام مراحل هر تکرار تنها اعدادی که در سمت راست ستون Z واقع شده اند مورد استفاده قرار می گیرند. اصطلاح سطر تنها به ردیفی از اعداد که در سمت راست ستون Z واقع شده اند و اعداد سمت راست را نیز شامل می شود اطلاق می گردد. سطر iام مربوط است به معادله iام.

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

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

فرمت جدولی

فرمت جبری

سمت راست

ضرایب

معادله

متغیر پایه

 

x5

x4

x3

x2

x1

Z

0

0

0

0

-5

-3

1

(0)

Z

4

0

0

1

0

1

0

(1)

x3

12

0

1

0

2

0

0

(2)

x4

18

1

0

0

2

3

0

(3)

x5

 خلاصه ای از روش سیمپلکس جدولی در تکرار اول

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

در مثال: فعالیت های اشاره شده در این مرحله برای مسئله شرکت ویندور جدول سیمپلکس اولیه با جواب BF اولیه (0,0,4,12,18) را که در جدول 1 آورده شده است حاصل خواهد نمود.

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

در مثال: با توجه به اینکه معادله Z=3x1+5x2 بیانگر این مطلب است که افزایش هر یک از دو متغیر x1 و x2 باعث افزایش Z می گردد، جواب BF کنونی بهینه نیست. این نکته را می توان از جدول سیمپلکس نیز دریافت به این صورت که با دیدن دو مقدار منفی -3 و -5 در ضرایب موجود در سطر صفر جدول سیمپلکس اولیه می توان به این نتیجه رسید که جواب کنونی بهینه نیست.

تکرار اول.

مرحله 1: متغیر غیرپایه ای را که دارای منفی ترین مقدار ضریب در سطر 0 است به عنوان متغیر پایه ورودی انتخاب کنید. ستون مربوط به متغیر ورودی را با رسم یک خط اطراف آن مشخص نمایید. به این ستون در اصطلاح ستون لولا (Pivot column) گفته می شود.

در مثال: منفی ترین ضریب در سطر 0 مربوط است به متغیر x2 که برابر است با -5 و بنابراین x2 از متغیر غیر پایه به متغیر پایه تبدیل خواهد شد. (این تغییر در جدول 2 با خطی که اطراف ستون مربوط به x2 و زیر -5 رسم شده است مشخص شده است.)

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

  • کلیه ضرایب مثبت مطلق در ستون لولا را انتخاب نمایید.
  • مقدار سمت راست مربوط به سطر هر یکی از این ضرایب را بر آن تقسیم نمایید و مقدار آن را یادداشت کنید.
  • سطری که نسبت محاسبه شده مربوط به آن دارای کمترین مقدار است را مشخص کنید.
  • متغیر پایه مربوط به این سطر همان متغیر پایه خروجی است بنابراین در جدول سیمپلکس بعدی این متغیر از پایه خارج شده و متغیر پایه ورودی که در مرحله قبل تعیین شد به جای آن می نشیند.

اطراف سطر مربوط به متغیر پایه خروجی را نیز با خطی بسته مشخص کنید و آن را سطر لولا (Pivot row) بنامید. همچنین به عددی که در تقاطع سطر و ستون لولا قرار دارد عدد لولا (Pivot number) گویند.

در مثال: محاسبات مربوط به آزمون حداقل نسبت در سمت راست جدول 2 نشان داده شده است. طبق این محاسبات سطر 2 سطر لولا و متغیر x4 متغیر پایه خروجی خواهد بود. در جدول سیمپلکس بعدی که در جدول 3 (در مطلب مرتبط بعدی خواهید دید) نمایش داده شده است متغیر x2 در سطر دوم جایگزین متغیر x4 در ستون مربوط به متغیرهای پایه گردیده است.

جدول 2. تعیین متغیر ورودی و متغیر خروجی برای جدول سیمپلکس اولیه مسئله شرکت ویندور

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

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