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

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 تحقیق در مورد الگوریتم انشعاب و حد برای حل کلی یک دسته از مسائل برنامه ریزی غیر محدب دارای ۲۷ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

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

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی تحقیق در مورد الگوریتم انشعاب و حد برای حل کلی یک دسته از مسائل برنامه ریزی غیر محدب،به هیچ وجه بهم ریختگی وجود ندارد

---

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

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

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

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

جایی که :
و مقادیر حقیقی اختیاری هستند . مقادیر حقیقی محدود هستند . تابع وابسته خطی هستند که روی تعریف شده است و برای تمام است .
بر اساس بیان بالا ما تابع اصلی و تابع شرایط را برای مسئله NP به صورت مجموع یا اختلاف برای نتایج اختیاری بعضی توابع خطی مثبت با نما نشان می دهیم . در گستر تعریف ما ، برنامه ریزی درج ۲ ، برنامه ریزی کسری خطی ، برنامه ریزی افزاینده ( ضربی) خطی و برنامه ریزی چند جمله ای و به علاوه برنامه ریزی هندسی تعمیم یافته در دسته ی مسائل (NP) قرار می گیرند . مسائل NP و فرم خاص آن به علت تعداد زیاد کاربردهای عملی آن در حوزه های گوناگون مطالعه شامل ۱) اقتصاد خرد ۲) بهینه سازی مالی ۳) بهینه سازی سهام (دارایی) ۴) طراحی طرح های صنعتی ۵) بهینه سازی قوی ( شدید ) و مانند اینها در مقالات به صورت قابل ملاحظه ای مورد توجه قرار گرفته است . از نظر تحقیقاتی مسائل NP چالش های تئوری و محاسباتی با معنی را مطرح می کند و این اساساً به این علت است که فهمیده شده نقط بهین محلی چندگانه به عنوان بهین اصلی نیست .

در ده اخیر تعدادی راه حل برای حل کلی بعضی حالت های خاص مسائل (NP) پیشنهاد شده است مثلاً وقتی و برای مسئل NP به مسئل برنامه ریزی خطی چندگانه تبدیل می شود و وقتی و مسئل NP به مسئل برنامه ریزی خطی چندگان تعمیم یافته تبدیل می شود برای این موارد روش های مختلفی به دست آمده که در بخش های [۱۳-۶] ارائه شده

است . در [۱۴] Jiao , Shen یک روش خطی سازی را برای یک دسته از برنامه ریزی چندگانه خطی با نما ارائه داده اند. وقتی باشد مسئل NP به مسئل برنامه ریزی کسری تبدیل می شود . برای این نوع مسئله تعداد زیادی راه حل در [۱۷-۱۵] ارائه شده است . اخیراً Shen , Guo , Jiao در [۱۸] روش عملی برای برنامه ریزی کسری خطی تعمیم یافته را با شرایط غیر خطی توسعه داده اند . وقتی که متغییرهای ساده هستند مسئل NP به مسئل برنامه ریزی هندسی تعمیم یافته تبدیل می شود که برای این دسته از مسائل تعداد زیادی از روش

های بهینه سازی پیشنهاد شده است . به عنوان مثال در [۲۲-۱۹] . اگرچه روش های بهینه سازی برای حالت های خاص مسئله NP در دست است اما بر اساس اطلاع ما ، روش بهینه سازی کلی بر اساس فرم های کلی مسئله NP در مقالات قبلی خیلی کم بررسی شده است بنابراین این ضروری است که یک روش موثر و مفید برای حل مسئله NP ارائه دهیم . هدف این مقاله ارائه روش موثر و قابل اطمینان برای حل مسائل برنامه ریزی غیر محدب (NP) است . در این روش ۱) با به کار بردن تقریب خطی تابع نمایی و لگاریتمی ، ما روش آرام

سازی خطی را برای مسائل NP توسعه می دهیم به طوری که مسائل برنامه ریزی خطی آرام شده بتواند با الگوریتم انشعاب – حد بدون افزایش متغییرها و شرایط جدید حل شود . ۲) آرام سازی خطی مسئل NP که به وجود آمد می تواند با هر یک از روش های برنامه ریزی خطی موثر حل شود ۳) مقایسه با [۲۱و۱۸و۱۴] :

اولاً مدل ریاضی پیشنهاد شده در این مقاله که یک بسط مهمی برای مدل بررسی شده در [۲۱و۱۸و۱۴] است ثانیاً یک روش آرام سازی خطی ۲ مرحله ای ارائه شده است . در این روش با به کار بردن تقریب های tangential hypersurface (سطح رویین مماسی) و مماس محدب تابع نمایی ، مرحل اول آرام سازی به دست می آید ، بر اساس مرحل اول آرام سازی با به کار بردن تقریب های tangential hypersurface (سطح رویین مماسی) و مماس مقعر تابع لگاریتمی برنامه ریزی خطی آرام سازی مسئل اصلی ایجاد می شود . به علاوه روش آرام سازی خطی ارائه شده در این مقاله می تاوند به عنوان یک کاربرد الحاقی برای روش آرام سازی در [۲۱و۱۸و۱۴] در نظر گرفته شود . این مقاله در ادامه به این صورت آمده

است : در بخش ۲ یک روش آرام سازی خطی برای ایجاد برنامه ریزی خطی آرام سازی در مسائل NP ارائه شده است . در بخش ۳ روش پیشنهاد شده توضیح داده می شود و ویژگی های همگرایی آن تأیید می شود نتایج عددی در چندین مثال برنامه ریزی غیر محدب در بخش های مختلف کاربرد در قسمت ۴و۵ بررسی می شود و همچنین یک خلاصه ای ارائه می شود .

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

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

در نظر می گیریم :

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

که:

در اینجا ما روش آرام سازی خطی ۲ مرحله ای را می پردازیم . در مرحل اول یک تابع حد پایین خطی (LIBF) از بر اساس به دست می آید سپس در مرحل دوم سرانجام LIBF از بر اساس x ساختار بندی می شود .
۲۱ : مرحل اول آرام سازی :
این مشخص است که تابع یک تابع محدب نسبت به y است . به ترتیب LLBF و تابع حد بالای خطی LUBF را برای در باز ارائه می دهند . پس با تحدب و LLBF می تواند به صورت ادامه داده شود :

که :

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

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

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

که :

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

۲۲ : مرحل دوم آرام سازی
با یک روش مشابه ما می توانیم LLBF و LUBF را در روی تابع در باز به دست آوریم ( شکل ۱ را ببینید )

که :

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

که :

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

که در ۵ داده شده است .
پس LLBF تابع بر اساس X می تواند با رابطه ی زیر به دست آید :
۷

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

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

که در ۷ داده شده است .
قضی ۱ : در نظر بگیریم :

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

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

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

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

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

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

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

که :

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

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

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

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

این اثبات قضی ۱ را کامل می کند .
از قضی ۱، ما نتیجه می گیریم که به ترتیب به انداز کافی به تابع همگراست و همین طور نتایجی که در ادامه آمده است بعضی از ویژگی های مهم مسائل (RLP) را ایجاد می کند که در طراحی روش پیشنهادی ضروری است . به منظور تسهیل در کار ، مقدار بهینه برای مسئل NP را با V(NP) نشان می دهیم .
قضی ۲ : و بنابراین باند پایین در مقدار بهینه را برای برنام اولی (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 به ۲ تا sub hyper rectangles همان طور که توصیف می شود انتخاب می کنیم ، باند پایین را برای هر گر جدید مثل قبل محاسبه می کنیم .

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

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

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

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

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

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