مقاله در مورد الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی
توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد
مقاله در مورد الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی دارای ۱۸ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است
فایل ورد مقاله در مورد الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.
توجه : در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله در مورد الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی،به هیچ وجه بهم ریختگی وجود ندارد
بخشی از متن مقاله در مورد الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی :
الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی
چکیده :
در این مقاله ، یک روش شاخه و کران موثر برای مسئله کسری خطی کلی ارائه می دهیم (GFP) . نخست، با استفاده از تکنیک تبدیل ، یک مسئله معادل (EP) از GFP بدست می آید ، سپس با به کار گرفتن ساختار EP ، برنامه نویسی وقفه ای خطی (LRP) از EP بدست می آید . برای تکمیل الگوریتم ، محاسباتی اصلی با حل کردن یک سلسله مسئله برنامه نویسی خطی درگیر می شود که می تواند به طور موثر حل شود . الگوریتم پیشنهادی به ماکزیمم کلی که در تصحیح متوالی جواب های یک سری از مسائل برنامه نویسی خطی است ، همگرا می باشد . آزمایش های عددی امکان پذیر بودن الگوریتم ما را نشان می دهند .
۱- مقدمه :
در این مقاله ، ما مسئله کسری خطی کلی را به شکل زیر در نظر می گیریم :
که ، همه هعداد حقیقی دلخواه هستند ،
که در اعداد صحیح تعریف شده است و x برای و .
جمع خطی مسئله نسبت ها یک بهینه سازی رده خاص در میان برنامه نویسی کسری است که برای چندین سال توجه محققان و متخصصان را جلب کرده است . اولین دلیل این است که آن مکرراً در کاربردها و برخی مسائل غیر خطی دیگری ظاهر می شود که قابل تبدیل به این شکل هستند . دلیل دیگر ، از نقطه نظر تحقیق ، این است که این مسائل اشکالات محاسباتی و نظری اصلی را مطرح می کنند ، برای مثال ، این روش عموماً برای داشتن ماکزیمم های نسبی متعددی شناخته شده است که به طور مطلق ماکزیمم نباشند . بنابراین ، لازم است روش خوبی مطرح شود . در طول سال های گذشته ، الگوریتم های مختلفی برای حل موارد خاص مسائل GFP پیشنهاد شده است که فقط برای جمع مسئله نسبت های خطی با فرض و برای همه x سفارش شده اند . برای مثال ، وقتی که چند بعدی است و m=2 و الگوریتم طوری ایجاد شده که روش ساده پارامتری را استفاده می کند ]۱[ .
وقتی که چند بعدی است ولی m 2 ، الگوریتم هایی پیشنهاد شده اند که مکرراً فضای خروجی غیر محدب را تا زمانی که جواب بهینه مطلق پیدا شود ، جستجو می کنند ]۲ ،۳ [
.
به علاوه با فرض اینکه و باشد ، الگوریتم شاخه و کران پیشنهاد شده است ]۴[ .
هدف این مقاله است که یک روش بهینه سازی کلی جدید را به وسیله ی حل کردن یک سلسله مسئله برنامه نویسی روی زیر مجموعه های تفکیک شده برای برنامع نویسی کسری خطی کلی تر ارائه کند . ویژگی اصلی این الگوریتم ، (۱) در GFP ، این است که ما فقط می خواهیم ، پس مدل سازی این مقاله کلی تر از مقاله های مطرح شده دیگر است . (۲) این الگوریتم با هدایت
کردن جستجوی شاخه و کردن در به جای در محاسبات مورد نیاز حرفه جویی کرد . (۳) رلاکسیون خطی EP بدست می آید که در محاسبات آسان تر از روش ]۵[ است و متغیرهای جدید تولید نمی کند . (۴) الگوریتم شاخه و کران پیشنهاد شده به ماکزیمم مطلق که در میان تصحیح متوالی رلاکسیون خطی منطقه ی تابع مورد نظر و توابع محدودیت و جواب های یک سری از LRP است ، همگرا می باشد . (۵) آزمایش های عددی داده می شوند تا امکان پذیری الگوریتم ما ار نشان دهند .
این مقاله به شکل زیر سازمان یافته است . در بخش ۲ ، با استفاده از تکنیک تبدیل ، مسئله EP طوری بدست می آید که با مسئله GFP معادل است . پردازش شاخه ای مستطیلی ، پردازش کران بالایی و پایینی ، که در این روش استفاده شد در بخش ۳ تعریف شده و مورد بررسی قرار می گیرند . الگوریتم در بخش ۴ معرفی می شود ، و همگرایی اش نشان داده می شود . بخش ۵ برخی نتایج عددی را که با حل کردن چند مثال بدست می آید ، گزارش می کند . در آخر ، خلاصه این مقاله داده می شود .
۲- اقدامات اولیه :
در این بخش ، ما نخست یک قضیه مهم ارائه می دهیم که اساس الگوریتم بهینه سازی کلی
است .
قضیه ۱ . فرض کنید x برای و سپس یا .
اثبات . با استفاده از قضیه مقدار میانی ، نتیجه بدیهی است .
برایx و
. پس ما داریم :
(۱) .
بدیهی است که در (۱) ، مخرخ ما همه مثبت هستند . بنابراین ، در مسئله GFP ، ما می توانیم فرض کنیم که همیشه حاصل می شود .
همچنین ، (۲)
که وقتی یک عددد مثبت است ، اگر به اندازه کافی بزرگ باشد ، می تواند حاصل شود . بنابراین ، در ادامه ، بدون از دست دادن کلیات ، می توانیم فرض کنیم که در GFP و
سپس ، نشان می دهیم که چگونه مسئله GFP را به مسئله معادل EP تبدیل می کنیم .
می گیریم . تعریف می شود که و
هستند ، پس مسئله GFP می تواند به مسئله معادل برنامه نویسی غیر محدب تبدیل شود که در ادامه می آید :
نتیجه هم ارزی کلیدی برای مسئله GFP و به وسیله قضیه بعدی داده می شود .
قضیه ۲ : اگر جواب بهینه کلی برای مسئله باشد ، پس جواب بهینه کلی برای مسئله GFP است . به عکس ، اگر جواب بهینه کلی برای مسئله GFP باشد ، پس جواب بهینه کلی برای مسئله است ، در جایی که و است .
اثبات : اثبات این قضیه به آسانی از تعریف مسائل GFP و بدست می آید ، بنابراین ، آن حذف شده است . با استفاده از قضیه ۲ ، برای حل کلی مسئله GFP ، می توان در عوض مسئله را به طور کلی حل کرد .
۳ عملیات پایه ای :
در این بخش ، بر مبنای مسئله معادل بالا ، یک الگوریتم شاخه و کران برای حل جواب بهینه کلی GFP پیشنهاد شده است . ایده اصلی الگوریتم شامل سه عملکرد اساسی می شود : قسمت بندی تصحیح شده پی در پی مجموعه امکان پذیر ، تخمین کران های بالایی و پایینی برای مقدار بهینه ی تابع مورد نظر . سپس ، ما آغاز به تشکیل الگوریتم با عملیات پایه ای بر اساس طرح شاخه وکران می کنیم .
۳۱ . پردازش شاخه ای :
در این الگوریتم ، پردازش شاخه به جای در انجام می شود که مکرراً مستطیلی p بعدی مسئله به مستطیل های زیر مجموعه ی کوچکتر تقسیم می شود که آن ها هم در بُعد p هستند . که مستطیل اولیه یا مستطیل های زیر مجموعه ی آن را مشخص می کند ، قانون شاخه ای در ادامه می آید :
به آسانی استنباط می شود که این پردازش شاخه ای جامع است ، برای مثال اگر توالی های تودرتوی مستطیل ها ( برای مثال ، ، برای همه k ها ) را مشخص کند که توسط پردازش شاخه ای شکل گرفته اند ، سپس یک نقطه منحصر به فرد وجود دارد به طوری که .
۳۲ کران های بالایی و پایینی :
برای هر مستطیل که توسط پردازش شاخه ای شکل گرفته است ، پردازش کران بالایی برای محاسبه ی یک کران بالا برای مقدار بهینه مسئله استفاده می شود .
در زیر دیده خواهد که کران بالایی می تواند با حل کردن یک برنامه خطی معمولی پیدا شود . در ادامه، برای راحتی بیان ، در نظر می گیریم :
در ابتدا ، تابع مورد نظر را درنظر می گیریم . داریم :
سپس ، تابع فرضی را در نظر می گیریم و
بر اساس بحث بالا ما می توانیم یک برنامه نویسی رلاکسیون خطی (LRP) به صورت زیر بسازیم که کران بالا را برای مقدار بهینه V(H) مسئله (H) EP فراهم می کند .
نکته ۱ V[p] مقدار بهینه مسئله p را مشخص می کند ، پس ، بر اساس بحث بالا ، مقادیر بهینه EP(H) , (LRP(H) برای به صورت V [LRP (H) ] V [ EP (H)] خواهد بود .
نکته ۲ . بدیهی است که اگر ، پس .
عملکرد اساسی دیگر این است که کران پایینی را برای مقدار بهینه مسئله مشخص کنیم . با پردازش کران پایینی ، با حل کردن (LRP(H) ، جواب بهینه را خواهیم داشت . اگر
باشد ، بدیهی است که یک جواب قابل قبول مسئله است ، بنابراین ، یک کران پایینی را برای مقدار بهینه مسئله فراهم می کند .
۴ الگوریتم و همگرایی آن :
بر مبنای نتایج و عملیاتی که در بخش ۳ داده شد ، الگوریتم شاخه و کران برای مسئله GFP ممکن است به صورت زیر بیان شود :
الگوریتم شاخه و کران گام را انتخاب کنید .
به وسیله مشخص می شود یک جواب بهینه و مقدار بهینه برای مسئله LRP( ) می یابیم . قرار می دهیم . قرار می دهیم :
اگر بود ، توقف می کنیم . به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . در غیر این صورت ، قرار می دهیم و به گام ۱ می رویم .
مرحله ۱ : قرار می دهیم . را به وسیله قاعده شاخه ای به دو مستطیل p – بعدی تقسیم می کنیم . قرار می دهیم .
مرحله ۲ : برای را محاسبه می کنیم و اگر ، یک جواب بهینه برای مسئله با شرط پیدا می کنیم . قرار می دهیم t=0 .
مرحله ۳ : قرار می دهیم t=t+1 . اگر t>2 بود ، به مرحله ۵ می رویم . در غیر این صورت ادامه می دهیم .
مرحله ۴ : اگر ، قرار می دهیم ، و به مرحله ۳ می رویم . در غیر این صورت ، قرار می دهیم .
قرار می دهیم . اگر بود به مرحله ۳ می رود .
اگر بود قرار می دهیم و قرار و ادامه می دهیم .
مرحله ۵ : قرار می دهیم : .
مرحله ۶ : قرار می دهیم : برقرار می گردد . اگر بود ، متوقف می شود . به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . در غیر این صورت ، قرار می دهیم و به مرحله ۱ می رویم .
مشخصات همگرایی الگوریتم در قضیه زیر داده شده اند .
قضیه ۳ (a) اگر الگوریتم متناهی باشد ، پس به محض خاتمه ، به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . (b) برای همه ی جواب ناگزیر را برای مسئله GFP در پایان مرحله k مشخص می کند .
اگر الگوریتم نامتناهی باشد ، هر نقطه انباشتگی یک جواب بهینه کلی برای مسئله GFP است و .
اثبات : (a) اگر الگوریتم متناهی باشد ، پس در مرحله خاتمه می یابد . به محض پایان یافتن ، بعد از اینکه به وسیله حل کردن مسئله EP(H) پیدا شد ، برای برخی و برای یک جواب بهینه و تنظیم کردن یک جواب قابل قبول برای مسئله GFP و یک جواب قابل قبول برای مسئله است . به محض پایان یافتن الگوریتم ، شرط برقرار است . مرحله ۰ و مرحله ۱ و مرحله ۴ اشاره دارند که . به وسیله الگوریتم ، نشان داده می شود که .چون جواب قابل قبول مسئله است، مجموع این دو اشاره دارد که . بنابراین (۳) . چون داریم :
. از (۳) ،در می یابیم که و اثبات بخش (a) کامل است .
(b) فرض کنید که الگوریتم نامتناهی است . پس آن یک سلسه جواب های ناگزیر برای مسئله تولید می کند که می توانیم با مشخص کنیم . برای هر به وسیله حل کردن مسئله پیدا می شود که برای برخی مستطیل های ، برای یک جواب بهینه و تنظیم کردن می باشد . بنابراین ، دنباله شامل جواب های قابل قبول مسئله GFP است . می گذاریم یک نقطه انباشتگی باشد و بدون از دست دادن کلیات فرض می کنیم که .
پس ، چون یک مجموعه پیوسته است ، است . بنابراین ف چون نامتناهی است ، می توانیم فرض کنیم که بدون از دست دادن نکات کلی ، برای دو . از Try , Horest [6] ، چون مستطیل های به وسیله دو بخش مستطیلی شکل گرفته اند ، این نشان می دهد که برای بعضی نقاط
قرار می دهیم و برای به وسیله داده می شود .
چون ، برای هر k ، با استفاده از نکته ۲ و مرحله ۴ ، این اشاره دارد که یک دنباله غیر صعودی از اعداد حقیقی است که از پایین به وسیله محدود شده است . بنابراین ، یک عدد متناهی است و شرط را بر قرار می کند . (۵) برای هر k ، از مرحله ۲ ، ، مقدار بهینه مسئله برابر است و یک جواب مطلوب برای این شکل است . از (۴) ، ما داریم : . چون و پیوستگی پس :
این اشاره دارد که یک جواب ممکن برای مسئله است . بنابراین .
با جستجو کردن (۵) ، بدست می آوریم که (۶) .
از این رو (۷)
از (۶) و (۷) داریم : ، بنابراین ، یک جواب بهینه کلی برای مسئله است .
- در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.