مقدار دهی اولیه الگوریتم سیمپلکس بدون متغیر مصنوعی

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

 

عملیات مقدماتی :

  • تبدیل متغیر های آزاد به متغیر های نامنفی
  • حذف شروط زاید از مسئله
  • ضافه کردن متغیر های مازاد و کمبود

هدف این الگوریتم رسیدن به جدول سیمپلکسی با الویت های زیر است :

1- در جدول نهایی مجموعه متغیر های پایه ای کامل شده است.
2- تمام  Cj ها نامثبت شده باشند. (شرط بهینگی)
3- بایستی همواره نامنفی بودن ستون RHS را در نظر بگیریم. (شرط شدنی بودن )
 

فرآیند الگوریتم

گام 0:با معرفی متغیرهای کمبود و مازاد، تمام قیود نامساوی را به تساوی تبدیل میکنیم.

گام  1: آیا BVS کامل شده است؟ اگر کامل شده است،با قوانین سیمپلکس معمولی مقدار بهین را محاسبه می کنیم. اگر نه، ستون محوری (PC) را انتخاب می کنیم.

گام 2: PC : متغیر غیر پایه ای با بیشترین ضریب Cj (که می تواند منفی هم باشد) را به عنوان متغیر ورودی به پایه BVS انتخاب می کنیم.

گام 3 :نسبت C/R را برای ستون محور گیری محاسبه می کنیم (محاسبه مقدار RHS/PC برای هر PC>0)آیا کمترین مقدار نامنفی C/R در یک سطر اشغال نشده قرار دارد؟ * اگر بله این سطر، سطر محور گیری می باشد.

      گام 3.1 : PR: متغیر انتخاب شده را با عملیات سطری GJ در BVS  قرار می دهیم.          به گام 1 بر می گردیم. * اگر نه به گام 4 بروید.

گام 4 :آیا متغیر غیر پایه ای دیگری برای ورود به پایه وجود دارد؟ اگر نه، مسئله نشدنی است و اگر بله، متغیر بعدی را با بیشترین مقدار Cj انتخاب کرده و به گام 3.1 می رویم.

/ 2 نظر / 41 بازدید
مهدی

سلام .لینک دانلود نمیشه. میشه برام ایمیل کنید نیاز دارم. باتشکر

مهدی

سلام .لینک دانلود نمیشه. میشه برام ایمیل کنید نیاز دارم. باتشکر