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

بخشی از مقاله

الگوریتم انشعاب – حد برای حل کلی یک دسته از مسائل برنامه ریزی غیر محدب (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 : در نظر بگیریم :



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


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


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

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


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

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




ثانیاً تفاضل را ملاحظه می کنیم که هست :


که :



از آنجایی که تابع مقعر برای در بازۀ است . این نتیجه گرفته می شود که می تواند ماکزیمم در نقطۀ به دست آید و






از طرف دیگر از آنجایی که تابع محدب برای به ازای هر است . نتیجه گرفته می شود که می تواند ماکزیمم را در نقطۀ به دست آورد . بنابراین :


با :
ما داریم :
پس :
همین طور
به علاوه بر طبق بحث بالا ما می توانیم ادامه دهیم که :

از بحث بالا به روشنی مشخص است که خطای ارضا می کند :

این اثبات قضیۀ 1 را کامل می کند .
از قضیۀ 1، ما نتیجه می گیریم که به ترتیب به اندازۀ کافی به تابع همگراست و همین طور نتایجی که در ادامه آمده است بعضی از ویژگی های مهم مسائل (RLP) را ایجاد می کند که در طراحی روش پیشنهادی ضروری است . به منظور تسهیل در کار ، مقدار بهینه برای مسئلۀ NP را با V(NP) نشان می دهیم .
قضیۀ 2 : و بنابراین باند پایین در مقدار بهینه را برای برنامۀ اولیۀ (NP) فراهم می کند .
اثبات : با روش ساختار بندی بالا نتیجه روشن است .

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

حدسازی) می تواند برای ارتقاء راه حل ها به کار گرفته شود . روش انشعاب – باند براساس تقسیم بندی مجموعۀ به sub hyper rectangles انجام شود که هر کدام وابسته به یک گره در درخت انشعاب – باند است و هر گروه وابسته به یک برنامه ریزی آرام سازی خطی در sub hyper rectangles متناظر است . بنابراین در هر مرحلۀ k از الگوریتم ، فرض شده که ما یک مجموعه از گره های فعال داریم که با مشخص شده است و هر کدام وابسته به یک hyper rectangles هستند . برای هر گرۀ x ما باید باند پایین LB(X) مسئلۀ NP را از طریق

حل به وسیله RLP محاسبه کنیم که حد پایین مقدار بهینه در مسئلۀ NP در سراسر منطقۀ اولیۀ در مرحلۀ K با رابطه ی داده می شود . هنگامی که جواب برنامه ریزی آرام سازی خطی RLP برای مسئلۀ NP عملی نباشد در صورت لزوم حد بالا برای UB جواب فرضی تجدید می شود . سپس هر مجموعه از گره های فعال رابطۀ LB(X)<UB ( به ازای ) را ارضا می کند در هر مرحله از K حالا ما یک گرۀ فعال را برای جزء بندی کردن از hyper rectangles به 2 تا sub hyper rectangles همان طور که توصیف می شود انتخاب می کنیم ، باند پایین را برای هر گرۀ جدید مثل قبل محاسبه می کنیم .

با بررسی هر گرۀ اصلاح نشده ما یک کجموعه از گره های فعال برای مرحلۀ بعدی به دست می آوریم و این فرآیند تا به دست آوردن همگرایی تکرار می شود . انتخاب استراتژی مناسب جزءبندی یکی از مسائل مهم در تأیید همگرایی به مینیمم اصلی است . در این مقاله ما یک دستور 2 بخشی ساده و استاندارد را انتخاب می کنیم این روش به اندازۀ کافی همگرایی را تأیید می کند زیرا همۀ بازه ها را برای همۀ متغییرها به صفر می رساند . دستورالعمل انشعابی در ادامه آمده است . فرض کنید که :

می خواهد دسته بندی شود پس ما متغیر شاخه ای ( انشعابی ) که رابطه ی را ارضا کند انتخاب می کنیم و بخش بازۀ داخلی را به فاصله های فرعی تقسیم می کند . در نظر بگیریم که مقدار تابع بهینه RLP برای sub hyper rectangles است و جزءای از arg min متناظر است . پلۀ اصلی در روش بهینه سازی اصلی فرض شده به صورت خلاصه در ادامه آمده است .

بیان الگوریتم:
پلۀ 0 : شمارش گر داخلی k=0 ، مجموعۀ همۀ گره های فعال و باند بالای و مجموعۀ نقاط ممکن را تنظیم می کنیم . مسئلۀ (RLP) را برای X=X0 حل می کنیم ،
به دست می آوریم . اگر برای (NP) قابل قبول بود در صورت نیاز UB , F را تجدید می کنیم . اگر ( که تلورانس صحت (دقت) است ) پس با به عنوان جواب مفید برای مسئلۀ NP ، پروسه را متوقف می کنیم . یا به عبارت دیگر به پلۀ 1 می رویم .

پلۀ 1 : جدید کردن باند بالایی
نقطۀ میانی در را انتخاب می کنیم اگر برای (NP) قابل قبول باشد پس باند بالای را تعریف می کنیم . اگر بهترین نقطۀ عملی شناخته شده به صورت مشخص می شود .

پلۀ 2 : (انشعابی کردن ) :
یک متغیر انشعابی xp از بخش به منظور به دست آوردن sub hyper rectangle جدید براساس دستور انشعابی انتخاب شدۀ بالا انتخاب می کنیم . مجموعۀ بخش های جدید rectangle به عنوان نامیده می شود .
2.1 : برای هر باند پایین برای rectangle محاسبه می کنیم .
در حالی که حد پایین است و براساس فرمول 6 در sub hyper rectangle محاسبه می شود . اگر باشد در این حالت یکی از حدود پایین رابطۀ زیر را ارضا می کند .

پس sub rectangle متناظر با X از جدا می شود می پرد .
2.2 : اگر باشد با حل کردن x(x) , LB(x) , (RLP) برای هر به دست می آید اگر
در نتیجه : مجموعۀ . در غیر این صورت در صورت امکان مانند مرحلۀ 1 مقدار در دسترس بهتری برای b,f,UB ارائه می دهد .