زمانی که در یکی از تکرار های الگوریتم سیمپلکس یکی از جواب های پایه ای مقداری برابر با صفر پیدا کند آنگاه گویم که آن نقطه پایه ای (یا آن جدول سیمپلکس) تباهیده است. جواب تباهیده زمانی بدست می آید که در مدل ریاضی خود محدودیت مازاد داشته باشیم (به این معنی که در واقع برای تعریف فضای جواب نیازی به آن محدودیت نباشد). در صورتی که جواب نهایی بدست آمده یکی از متغیرهای پایه ای مقدار صفر داشته باشد، آنگاه گوییم که جواب نهایی تباهیده است.
نقاط پایه ای تباهیده برای الگوریتم سیمپلکس مشکل ایجاد می کنند، آنها باعث می شوند تا الگوریتم سیمپلکس در یک تکرار به تکرار بعدی بهبودی را ایجاد نکند (در واقع ما داریم بر روی یک راس تکرار های غیر مفید انجام می دهیم) که به این واقعه وجود چرخه در سیمپلکس می گویند.
در برخی از اوقات چرخه ایجاد شده پس از چند تکرار از بین خواهد رفت و سیمپلکس ادامه بهبود خود را انجام می دهد، اما در برخی از دیگر اوقات ممکن است الگوریتم سیمپلکس نتواند از چرخه خارج شود و الگوریتم در این زمان به جواب بهیته نرسد.
برای جلوگیری از وقوع چرخه در الگوریتم سیمپلکس نیاز است تا قبل از رسیدن به یک جدول تباهیده بجای استفاده از تست مینیمم از قاعده الفابی (lexicography) استفاده کنیم تا بتوانیم از چرخه خارج شویم.
در این بخش قاعده الفبایی در الگوریتم سیمپلکس تشریح خواهد شد
هر آنکس که باشد از ایرانیان ببندد بدین بارگه برمیان
بیابد ز ما گنج و گفتار نرم چو باشد پرستنده با رای و شرم
چو بیداد جوید یکی زیردست نباشد خردمند و خسروپرست
مکافات باید بدان بد که کرد نباید غم ناجوانمرد خورد
داستان به تخت نشستن کسری نوشین روان از شاهنامه فردوسی
زمانی که در یکی از تکرار های الگوریتم سیمپلکس یکی از جواب های پایه ای مقداری برابر با صفر پیدا کند آنگاه گویم که آن نقطه پایه ای (یا آن جدول سیمپلکس) تباهیده است. جواب تباهیده زمانی بدست می آید که در مدل ریاضی خود محدودیت مازاد داشته باشیم (به این معنی که در واقع برای تعریف فضای جواب نیازی به آن محدودیت نباشد). در صورتی که جواب نهایی بدست آمده یکی از متغیرهای پایه ای مقدار صفر داشته باشد، آنگاه گوییم که جواب نهایی تباهیده است.
نقاط پایه ای تباهیده برای الگوریتم سیمپلکس مشکل ایجاد می کنند، آنها باعث می شوند تا الگوریتم سیمپلکس در یک تکرار به تکرار بعدی بهبودی را ایجاد نکند (در واقع ما داریم بر روی یک راس تکرار های غیر مفید انجام می دهیم) که به این واقعه وجود چرخه در سیمپلکس می گویند.
در برخی از اوقات چرخه ایجاد شده پس از چند تکرار از بین خواهد رفت و سیمپلکس ادامه بهبود خود را انجام می دهد، اما در برخی از دیگر اوقات ممکن است الگوریتم سیمپلکس نتواند از چرخه خارج شود و الگوریتم در این زمان به جواب بهیته نرسد.
برای جلوگیری از وقوع چرخه در الگوریتم سیمپلکس نیاز است تا قبل از رسیدن به یک جدول تباهیده بجای استفاده از تست مینیمم از قاعده الفابی (lexicography) استفاده کنیم تا بتوانیم از چرخه خارج شویم.
در این بخش قاعده الفبایی در الگوریتم سیمپلکس تشریح خواهد شد
دریافت محتویات این درس
۱۵: تباهیدگی در الگوریتم سیمپلکس
۱۰,۰۰۰ تومان افزودن به سبد خرید