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

فرض کنیم در جدول سیمپلکس در تکرار i ام  متغیر xk  وارد پایه شود و متغیر xr از پایه خارج شود . آیا امکان دارد در تکرار دیگری ((i+2) ام به بعد) این عمل برعکس انجام شود یعنی متغیرxr  وارد پایه شود و متغیر xk از پایه خارج شود ؟

ناگفته پیداست که در تکرار i+1 ام (تکرار بلافاصله )  چنین چیزی امکان پذیر نیست. 

بتدریج جواب اساتید گرانقدر به این سوال را در همین وبلاگ خواهم گذاشت. 

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

                                                                                                                                
جواب دکتر محمدباقر احمدی (دانشگاه شیراز ) : جواب سوال شما مثبت است. مساله زیر را حل کنید تا نتیجه را ببینید:

                                        
max z=x1+2x2

-x1+x2<=1
x1+3x2<=6
x1,x2>=0

جواب دکتر میردهقان(دانشگاه شیراز):

Dear Mr. Arami

Thanks for your communication.

Of course, It may be happen. To see an example, please see Klee example in Chapter 8 of "Linear Programming and Network Flows" written by Bazaraa et al. It is a famous book in OR.


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

جواب دکتر عشقی(دانشگاه صنعتی شریف ):

Hi Mr. Arami,

It is possible when cycling occurs. You can refer to "Linear Programming and Network Flows, 4th edition, M. Bazaraa et al., John Wiley, 2010, pages 175-180".

Best regards,

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

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