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

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

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

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

 سوال: چگونه مسائلی را که دارای متغیرهای آزاد در علامت هستند، با روش سیمپلکس حل کنیم؟

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

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

 (1018 کلمه)

 مطلب مرتبط بعدی: تحلیل های پس از بهینه سازی به کمک سیمپلکس (Postoptimality analysis)

 مطلب مرتبط قبلی: تشخیص عدم وجود فضای موجه از جدول سیمپلکس


سوال: چگونه مسائلی را که دارای متغیرهای آزاد در علامت هستند، با روش سیمپلکس حل کنیم؟

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

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

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

که Li عددی ثابت و منفی است و کران پایین متغیر تصمیم است. برای تبدیل این محدودیت به محدودیت نامنفی بودن باید تغییر متغیر زیر را اعمال کنیم، یعنی روش این است که اختلاف دو طرف محدودیت بالا را به عنوان متغیر جدیدی تعریف کنیم :

بنابراین عبارت

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

فرض کنید متغیری که در ابتدای بحث به آن اشاره کردیم یعنی نرخ تولید کالا، دارای کران پایین 10- باشد. به این ترتیب داریم:

طبق تکنیکی که در بالا اشاره کردیم متغیر جدید به صورت زیر نوشته خواهد شد:

حال باید متغیر را جایگزین کنیم. به مثال زیر توجه کنید:

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

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

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

را از مدل کنار بگذارید. برای اینکه بتوان مسئله را با سیمپلکس حل کرد باید x1 را با اختلاف دو متغیر غیر منفی جایگزین نمود:

به این ترتیب خواهیم داشت:

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

متغیرهای جدید یعنی xj+ و xj- را می توان به سادگی تفسیر کرد. همانطور که در پاراگراف های بعدی توضیح داده خواهد شد، در هر جواب گوشه ای موجه مسئله جدید، لزوماً باید یا xj+=0 باشد یا xj-=0 و یا هر دو. بنابراین در جواب بهینه بدست آمده از طریق روش سیمپلکس که خود یک جواب گوشه ای است خواهیم داشت:

به طوریکه xj+ بخش مثبت متغیر تصمیم xj است و xj- بخش منفی است.

برای مثال اگر xj=10 باشد، از معادلات بالا xj+=10 و xj-=0 به دست می آید. مقادیر دیگری نیز می تواند در

صدق کند که از مقادیر بالا بزرگتر باشد مانند xj+=11 و xj-=1 و یا xj+=15 و xj-=5 . رسم مقادیر ممکن برای xj+ و xj- بر روی صفحه مختصات خطی را می دهد که از نقطه xj+=10 و xj-=0 شروع می شود و در ربع اول صفحه مختصات پیش می رود. زیرا در ربع اول هر دو متغیر مثبت هستند و این باعث می شود از محدودیت های نامنفی بودن منحرف نشویم. در نتیجه نقطه xj+=10 و xj-=0 تنها جواب گوشه ای روی این خط می باشد. بنابراین این نقطه می تواند بخشی از جواب CPF نهایی یا جواب BF اصلی مدل باشد. این نشان می دهد که چرا در جواب BF، یا متغیر xj+ برابر با صفر می باشد یا متغیر xj- و یا هر دو.

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

جایگزین نماییم، کافی است مقدار xj- را برای همه jها ثابت و مشابه بگیریم. به این ترتیب -xj- برابر خواهد بود با بزرگترین مقدار منفی که در jهای مختلف بدست می آید. در نتیجه در این روش برخی از xj+ ها بزرگتر از صفر خواهند بود با اینکه xj- نیز بزرگتر از صفر است.

 مطلب مرتبط بعدی: تحلیل های پس از بهینه سازی به کمک سیمپلکس (Postoptimality analysis)

مطلب مرتبط قبلی: تشخیص عدم وجود فضای موجه از جدول سیمپلکس