الگوریتم انشعاب و حد برای حل کلی یک دسته از مسائل برنامه ریزی غیر محدب

فهرست

خلاصه : 1
کلید واژه 1
مقدمه 1
روش آرام سازی خطی 3
2.1 : مرحلۀ اول آرام سازی 5
2.2 : مرحلۀ دوم آرام سازی 7
2.3 : برنامه ریزی خطی آرام سازی 9
الگوریتم و همگرایی آن 14
بیان الگوریتم: 15
پلۀ 1 : جدید کردن باند بالایی 16
پلۀ 2 : (انشعابی کردن ) 16
پلۀ 3 : ( تجدید نظر در باند پایین ) 17
پلۀ 4 : بررسی همگرایی 17
قضیۀ 3 : نتایج همگرایی 17
4) آزمایش عددی 17
نتیجه گیری 22

کلید واژه :
برنامه ریزی غیر محدب ؛ بهینه سازی کلی ، آرام سازی خطی – انشعاب و حد –

مقدمه :
یک دسته از مسائل برنامه ریزی خطی که در ادامه آمده است را ملاحظه می کنید :
 
جایی که :     
و   مقادیر حقیقی اختیاری هستند . مقادیر حقیقی محدود هستند . تابع وابسته خطی هستند که روی   تعریف شده است و برای تمام   است .

بر اساس بیان بالا ما تابع اصلی و تابع شرایط را برای مسئله NP به صورت مجموع یا اختلاف برای نتایج اختیاری بعضی توابع خطی مثبت با نما نشان می دهیم . در گسترۀ تعریف ما ، برنامه ریزی درجۀ 2 ، برنامه ریزی کسری خطی ، برنامه ریزی افزاینده ( ضربی) خطی و برنامه ریزی چند جمله ای و به علاوه برنامه ریزی هندسی تعمیم یافته در دسته ی مسائل (NP) قرار می گیرند . مسائل NP و فرم خاص آن به علت تعداد زیاد کاربردهای عملی آن در حوزه های گوناگون مطالعه شامل 1) اقتصاد خرد  2) بهینه سازی مالی  3) بهینه سازی سهام (دارایی)  4) طراحی طرح های صنعتی  5) بهینه سازی قوی ( شدید ) و مانند اینها در مقالات به صورت قابل ملاحظه ای مورد توجه قرار گرفته است . از نظر تحقیقاتی مسائل NP چالش های تئوری و محاسباتی با معنی را مطرح می کند و این اساساً به این علت است که فهمیده شده نقطۀ بهینۀ محلی چندگانه به عنوان بهینۀ اصلی نیست