Online User آماده سازی مسئله برای حل با روش جبری سیمپلکس - مدیریت صنعتی Industrial Management

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

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

آماده سازی مسئله برای حل با روش جبری سیمپلکس
نویسنده : محسن رحیمی - ساعت ٧:٤٧ ‎ب.ظ روز ۱۳٩٠/٥/۱٩
 

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

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

انجام عملیات تبدیل علامت، احتیاج به وارد کردن متغیرهای کمبود (Slack variables) دارد. برای نمونه اولین محدودیت ساختاری مسئله شرکت ویندور را در نظر بگیرید:

متغیر کمبود برای این محدودیت به صورت زیر تعریف می شود:

که برابر است با مقدار کمبود عبارت سمت چپ نامعادله محدودیت. بنابراین داریم:

با در نظر گرفتن این معادله، x1 کوچکتر مساوی 4 خواهد بود اگر و تنها اگر

بنابراین محدودیت اولیه، معادل دو محدودیت زیر خواهد بود:

و

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

شکل 1. قالب اصلی مدل در سمت چپ و قالب افزوده مدل در سمت راست

اگرچه هر دو قالب مدل در اصل یک مسئله را نشان می دهند ولی قالب افزوده برای حل جبری و تعیین جواب های CPF بسیار راحت تر است. به این قالب از آن جهت قالب افزوده می گویند که با افزودن تعدادی متغیر کمکی به قالب مدل اصلی بدست می آید.

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

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

جواب افزوده (augmented solution) جوابی است برای متغیرهای اصلی مسئله (متغیرهای تصمیم) که متغیرهای کمبود را نیز شامل می شوند. برای مثال نقطه جواب (3,2) در مثال بالا به صورت افزوده به شکل جواب افزوده (3,2,1,8,5) در خواهد آمد زیرا مقادیر متغیرهای کمبود مرتبط عبارتند از x3=1، x4=8 و x5=5

جواب پایه (basic solution) عبارت است از یک جواب گوشه ای افزوده.

این حقیقت که جواب های گوشه ای و همچنین جواب های پایه می توانند موجه یا غیر موجه باشند تعریف زیر را الزامی می کند:

جواب پایه موجه (basic feasible (BF) solution) یک جواب CPF افزوده است.

بنابراین یکی از جوابهای CPF مسئله شرکت ویندور به صورت (0,6) معادل یک جواب پایه موجه (BF) به صورت (0,6,4,0,6) برای قالب افزوده آن مسئله است.

بنابراین تنها تفاوت جواب های پایه و جواب های گوشه ای (یا بین جواب های CPF و جواب های BF) وجود متغیرهای کمبود در جواب است و جواب گوشه ای مرتبط با هر جواب پایه با کنارگذاشتن متغیرهای کمبود از جواب به سادگی بدست می آید. بنابراین رابطه هندسی و جبری بین این دو جواب بسیار به هم نزدیک است که در مطالب بعدی بیشتر به آن می پردازیم.

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

2 = 3 – 5 = تعداد معادلات – تعداد متغیرها

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

جواب پایه دارای ویژگی های زیر است:

  1. هر متغیر در جواب پایه یا متغیر پایه است یا متغیر غیر پایه.
  2. تعداد متغیرهای پایه برابر است با تعداد محدودیت های ساختاری (که در قالب افزوده به صورت معادله درآمده اند). بنابراین تعداد متغیرهای غیرپایه برابر است با تعداد کل متغیرها منهای تعداد محدودیت های ساختاری.
  3. متغیرهای غیرپایه برابر با صفر تنظیم می شوند.
  4. مقدار متغیرهای پایه با قرار دادن مقدار صفر برای متغیرهای غیرپایه در مجموعه معادلات قالب افزوده و حل مجموعه معادلات بدست می آیند. به مجموعه متغیرهای پایه در اصطلاح پایه (basis) می گویند.
  5. اگر متغیرهای پایه در محدودیت های غیرمنفی صدق کنند، جواب پایه یک جواب BF خواهد بود.

برای مثال جواب BF اشاره شده در مثال بالا، (0,6,4,0,6)، را دوباره در نظر بگیرید. این جواب قبلاً با افزودن متغیرهای کمبود به جواب CPF مربوط به آن یعنی (0,6) بدست آمد. با این حال راه دیگر بدست آوردن این جواب به این شرح است که ابتدا دو متغیر x1 و x4 را به صورت اختیاری به عنوان متغیر غیر پایه انتخاب نموده و مقدار فرضی صفر را به آنها بدهید. سپس سه معادله مسئله را حل نمایید که به ترتیب جواب های x3=4، x2=6 و x5=6 از حل سه معادله بدست می آید که متغیرهای پایه جواب هستند و به ترتیب زیر بدست می آیند:

از آنجا که هر سه متغیر پایه غیر منفی هستند بنابراین این جواب پایه یک جواب پایه موجه یعنی جواب BF است.

جواب های BF مربوط به جواب های CPF مجاور را نیز در اصطلاح مجاور می نامند. یک راه ساده برای تعیین اینکه دو جواب BF مجاور هستند یا خیر به شرح زیر است:

دو جواب BF را مجاور گویند اگر به غیر از یکی از متغیرهای غیر پایه همه آنها مشابه باشند یا زمانیکه به غیر از یکی از متغیرهای پایه، همه آنها مشابه باشند.

در نتیجه حرکت از جواب BF جاری به یک جواب مجاور یعنی تبدیل یک متغیر غیر پایه به یک متغیر پایه و بالعکس تبدیل یک متغیر پایه به یک متغیر غیر پایه با مقدار صفر.

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

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

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

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

مطلب مرتبط قبلی: 6 مفهوم کلیدی حل در روش سیمپلکس