Online User موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه خروجی - مدیریت صنعتی Industrial Management

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

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

موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه خروجی
نویسنده : محسن رحیمی - ساعت ٩:٠٤ ‎ب.ظ روز ۱۳٩٠/٦/۱
 

فرض کنید در مرحله دوم تکراری بیش از یک متغیر پایه شرایط انتخاب شدن به عنوان متغیر پایه خروجی را داشته باشد. آیا مهم است کدام یک به عنوان خروجی انتخاب گردد؟ برای پاسخ دادن به این سوال باید عنوان نمود که از لحاظ تئوری به دلیل امکان پیش آمدن مورد زیر، اینکه کدام متغیر از پایه خارج گردد اهمیت دارد. در ابتدا همه متغیرهایی که امکان انتخاب به عنوان متغیر پایه خروجی را دارند با افزایش مقدار متغیر پایه ورودی همزمان صفر می شوند و بنابراین آن متغیرهایی که به عنوان متغیر خروجی انتخاب نمی شوند علی رغم اینکه دارای مقدار صفر هستند در جواب BF جدید به عنوان متغیرپایه وجود خواهند داشت. لازم به ذکر است در اصطلاح به متغیر پایه ای که دارای مقدار صفر باشد متغیر فاسد[1] می گویند و از همین اصطلاح برای جواب BF مربوطه نیز استفاده می کنند. اگر یکی از متغیرهای پایه فاسد که دارای مقدار صفر است در تکرارهای بعدی به عنوان متغیر پایه خروجی انتخاب گردد، متغیر پایه ورودی در آن تکرار نیز باید صفر باقی بماند، زیرا هرگونه افزایش متغیر ورودی منجر به ظهور مقدار منفی برای متغیر پایه خروجی می گردد که امکان پذیر نیست. بنابراین مقدار Z نیز بدون تغییر باقی می ماند. در نتیجه اگر مقدار Z در تکرارهای متوالی بدون تغییر باقی بماند و افزایش نداشته باشد گفته می شود روش سیمپلکس درون یک چرخه (loop) گرفتار شده است. در یک چرخه دنباله ای از جواب ها به صورت دوره ای بدست می آیند بدون اینکه مقدار Z افزایش یابد و به سمت جواب بهینه حرکت کند و این در حالی است که آزمون بهینگی صحت بهینه بودن جواب ها را تایید نمی کند. در واقع، جواب های بدست آمده جواب هایی مصنوعی هستند  و در یک حلقه دائمی تبدیل گیرافتاده است.

خوشبختانه، اگر چه امکان وقوع حلقه دائمی از لحاظ تئوری ممکن است، در مسائل عملی به ندرت مشاهده شده است. در صورت مواجه شدن با یک حلقه می توانید با تغییر متغیر انتخاب شده به عنوان متغیر پایه خروجی از آن خارج شوید. علاوه بر این قوانین خاصی نیز در برخی مراجع ذکر شده است که با رعایت آنها از برخورد با چنین حلقه هایی می توان جلوگیری نمود. با این حال رعایت این قوانین در بسیاری از مسائل واقعی پیچیده و گاهاً غیر ممکن است که در اینجا مجال پرداختن به این قوانین وجود ندارد. برای کسانی که به دنبال مرجع معتبری در رابطه با این قوانین هستند کتاب mathematics of Operations research (1977) نوشته R. Bland صفحات 103 الی 107 توصیه می شود. در نتیجه پیشنهاد می شود بدون نگرانی از برخورد با حلقه ها به صورت اختیاری متغیر پایه خروجی را انتخاب نمایید و در صورت قرار گرفتن در حلقه انتخاب خود را تغییر داده و مجدداً به حل مسئله بپردازید.



[1]  degenerate

مطلب مرتبط بعدی: موارد خاص روش سیمپلکس: عدم وجود متغیر پایه خروجی (تابع هدف بیکران)

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