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

خلاصه :

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

کلید واژه :

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

مقدمه :

یک دسته از مسائل برنامه ریزی خطی که در ادامه آمده است را ملاحظه می کنید :

جایی که :    

و  مقادیر حقیقی اختیاری هستند .  مقادیر حقیقی محدود هستند .  تابع وابسته خطی هستند که روی  تعریف شده است و برای تمام  است .

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

در دهۀ اخیر تعدادی راه حل برای حل کلی بعضی حالت های خاص مسائل (NP) پیشنهاد شده است مثلاً وقتی  و برای  مسئلۀ NP به مسئلۀ برنامه ریزی خطی چندگانه تبدیل می شود و وقتی  و  مسئلۀ NP به مسئلۀ برنامه ریزی خطی چندگانۀ تعمیم یافته تبدیل می شود برای این موارد روش های مختلفی به دست آمده که در بخش های [13-6] ارائه شده است . در [14] Jiao , Shen یک روش خطی سازی را برای یک دسته از برنامه ریزی چندگانه خطی با نما ارائه داده اند. وقتی  باشد مسئلۀ NP به مسئلۀ برنامه ریزی کسری تبدیل می شود . برای این نوع مسئله تعداد زیادی راه حل در [17-15] ارائه شده است . اخیراً Shen , Guo , Jiao در [18] روش عملی برای برنامه ریزی کسری خطی تعمیم یافته را با شرایط غیر خطی توسعه داده اند . وقتی که  متغییرهای ساده هستند مسئلۀ NP به مسئلۀ برنامه ریزی هندسی تعمیم یافته تبدیل می شود که برای این دسته از مسائل تعداد زیادی از روش های بهینه سازی پیشنهاد شده است . به عنوان مثال در [22-19] . اگرچه روش های بهینه سازی برای حالت های خاص مسئله NP در دست است اما بر اساس اطلاع ما ، روش بهینه سازی کلی بر اساس فرم های کلی مسئله NP در مقالات قبلی خیلی کم بررسی شده است بنابراین این ضروری است که یک روش موثر و مفید برای حل مسئله NP ارائه دهیم . هدف این مقاله ارائه روش موثر و قابل اطمینان برای حل مسائل برنامه ریزی غیر محدب (NP) است . در این روش  1) با به کار بردن تقریب خطی تابع نمایی و لگاریتمی ، ما روش آرام سازی خطی را برای مسائل NP توسعه می دهیم به طوری که مسائل برنامه ریزی خطی آرام شده بتواند با الگوریتم انشعاب – حد بدون افزایش متغییرها و شرایط جدید حل شود .   2) آرام سازی خطی مسئلۀ NP که به وجود آمد می تواند با هر یک از روش های برنامه ریزی خطی موثر حل شود  3) مقایسه با [21و18و14] : فرمول

اولاً مدل ریاضی پیشنهاد شده در این مقاله که یک بسط مهمی برای مدل بررسی شده در [21و18و14] است ثانیاً یک روش آرام سازی خطی 2 مرحله ای ارائه شده است . در این روش با به کار بردن تقریب های tangential hypersurface (سطح رویین مماسی) و مماس محدب تابع نمایی ، مرحلۀ اول آرام سازی به دست می آید ، بر اساس مرحلۀ اول آرام سازی با به کار بردن تقریب های tangential hypersurface (سطح رویین مماسی) و مماس مقعر تابع لگاریتمی برنامه ریزی خطی آرام سازی مسئلۀ اصلی ایجاد می شود . به علاوه روش آرام سازی خطی ارائه شده در این مقاله می تاوند به عنوان یک کاربرد الحاقی برای روش آرام سازی در [21و18و14] در نظر گرفته شود . این مقاله در ادامه به این صورت آمده است : در بخش 2 یک روش آرام سازی خطی برای ایجاد برنامه ریزی خطی آرام سازی در مسائل        NP ارائه شده است . در بخش 3 روش پیشنهاد شده توضیح داده می شود و ویژگی های همگرایی آن تأیید می شود نتایج عددی در چندین مثال برنامه ریزی غیر محدب در بخش های مختلف کاربرد در قسمت 4و5 بررسی می شود و همچنین یک خلاصه ای ارائه می شود .

روش آرام سازی خطی :

کار اصلی در توسعۀ راه حل ها برای حل مسئلۀ (NP) ساختار بدنی مسائل برنامه ریزی آرام سازی خطی برای بدست آوردن حدود پایین در مقادیر بهینۀ این مسئله است . مفهوم توابع حدی خطی (LBFS) داده شده است . در بررسی مسائل (NP) ما نیازمندیم که توابع با حد پایین خطی (LBFS) را به ترتیب برای توابع اصلی ( تابع هدف ) و تابع شرایط ساختار بندی کنیم . در این بخش روش آرام سازی خطی با LLBFS تابع هدف و تابع شرایط توسعه پیدا کرده است ( ایجاد شده است ) . همۀ جزئیات این روش در ادامه آمده است . بنابراین ابتدا بعضی از اصطلاحات را ملاحظه می کنیم :

برای هر  ما نیاز داریم یک LLBF را ساختار بندی کنیم و از آنجایی که :

در نظر می گیریم : فرمول

پس ما می توانیم یک حالت هم ارز از  به دست آوریم همان طور که در ادامه آمده است :

2.

که: فرمول

در اینجا ما روش آرام سازی خطی 2 مرحله ای را می پردازیم . در مرحلۀ اول یک تابع حد پایین خطی (LIBF) از  بر اساس  به دست می آید سپس در مرحلۀ دوم سرانجام LIBF از  بر اساس x ساختار بندی می شود .

2.1 : مرحلۀ اول آرام سازی :

این مشخص است که تابع  یک تابع محدب نسبت به y است .  به ترتیب LLBF و تابع حد بالای خطی LUBF را برای  در بازۀ  ارائه می دهند . پس با تحدب  و LLBF می تواند به صورت ادامه داده شود :

که :

که تقریب tangential (مماسی) در نقطۀ  نامیده می شود و به سادگی به دست می آید . به علاوه ما به سادگی می توانیم LUBF روی  در فاصلۀ  به صورت زیر ارائه دهیم :

که منحنی مقعر  در فاصلۀ  است .

با استفاده از ویژگی های هندسی تابع  ما ادامه می دهیم ( نتیجه می گیریم ) که :

بر اساس بحث بالا برای هر بخش  ما می توانیم مرحلۀ اول آرام سازی LIBF متناظر برای  بر اساس y را ساختار بندی کنیم . بر اساس رابطه ی داده شده بر حسب x حد برای  نیز می تواند به دست آید . حد بالا و پایین برای  به وسیلۀ  بر اساس رابطۀ داده شده در این الگوریتم مشخص شده است . حد بالا و پایین برای  به وسیلۀ  [که به سادگی به دست می آید] مشخص شده است . پس ما داریم :

که :

به علاوه ما می توانیم توابع باند پایین خطی  برای  بر اساس  همان گونه که در ادامه آمده است به دست آوریم :

3.                                      

بعد  را در نظر بگیرید سپس  . پس ما می توانیم  در (3) را با  جایگزین کنیم . مرحلۀ اول آرام سازی تابع حد پایین با  پیرامون x برای بعضی از  در ادامه داده شده است :

4.

2.2 : مرحلۀ دوم آرام سازی

با یک روش مشابه ما می توانیم LLBF و LUBF را در روی تابع  در بازۀ  به دست آوریم ( شکل 1 را ببینید )

که :

سپس  ( که در 4 آمده است ) را با  که در ادامه آمده است جایگزین می کنیم :

5.

که :

و در آخر LLBF را برای  بر اساس x برای بعضی از  به دست می آوریم که مقدار  به مقدار ناچیزی تقریب زده می شود .

6.

که  در 5 داده شده است .

پس LLBF تابع  بر اساس X می تواند با رابطه ی زیر به دست آید :

7.

که  در 6 داده شده است . به روشنی مشخص است که :

2.3 : برنامه ریزی خطی آرام سازی

برای هر  

بر طبق بحث بالا برنامه ریزی خطی آرام سازی (RLP) در مسئلۀ NP در  می تواند به صورت آنچه در ادامه آمده است توصیف شود .

که  در 7 داده شده است .

قضیۀ 1 : در نظر بگیریم :

پس این روشن است که ما فقط باید ثابت کنیم :

پس ابتدا تفاضل  را ملاحظه می کنیم که هست :

با تعریف  ما می فهمیم که  و

حالا توجه کنید که :

فرمول

(فرمول ها در فایل اصلی موجود است )