تحقیق در عملیات ( Operation Research)

بهینه سازی

مقدار دهی اولیه الگوریتم سیمپلکس بدون متغیر مصنوعی
نویسنده : دکتر نعمت اله تقی نژاد - ساعت ۱٢:۳٢ ‎ب.ظ روز جمعه ٢٠ بهمن ۱۳٩۱
 
 مقدار دهی اولیه الگوریتم سیمپلکس بدون متغیر مصنوعی
الگوریتم سیمپلکس برای حل مسائلی که در نقطه شروع جواب شدنی پایه ای ندارند، متغیرهای مصنوعی را بکار می گیرد. در مسائلی که برخی از قیود به صورت = یا <= با مقدار سمت راست نامنفی است از روش هایی چون روش دوفازی و روش M بزرگ استفاده می کنیم. 
در روش دو فازی با تولید تابع هدف مصنوعی در جستجوی یک جواب شدنی پایه ای هستیم. 
  • در روش M بزرگ واحدهای جریمه ای به تابع هدف افزوده می شود که از جمع متغیر های مصنوعی با ضرایب مثبت بسیار بزرگ حاصل می شود.
  • در این الگوریتم از هیچ متغیر مصنوعی، تابع هدف مصنوعی و یا قیود مصنوعی استفاده نمی شود.
برای مطالعه کامل پست به "ادامه مطلب" مراجعه کنید و همچنین فایل کامل پروژه را از لینک زیر می توانید دانلود کنید.
 
 

در ابتدا الگوریتم با مجموعه متغیرهای پایه ای 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 می رویم.


 
 
 



backgroundcolor= class=#2f57a2width:230px; padding-top: 5px;td width=logo