دانلودمقاله الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی

اختصاصی از فی بوو دانلودمقاله الگوریتم بهینه سازی کلی برای برنامه نویسی کسری خطی دانلود با لینک مستقیم و پر سرعت .

چکیده :
در این مقاله ، یک روش شاخه و کران موثر برای مسئله کسری خطی کلی ارائه می دهیم (GFP) . نخست، با استفاده از تکنیک تبدیل ، یک مسئله معادل (EP) از GFP بدست می آید ، سپس با به کار گرفتن ساختار EP ، برنامه نویسی وقفه ای خطی (LRP) از EP بدست می آید . برای تکمیل الگوریتم ، محاسباتی اصلی با حل کردن یک سلسله مسئله برنامه نویسی خطی درگیر می شود که می تواند به طور موثر حل شود . الگوریتم پیشنهادی به ماکزیمم کلی که در تصحیح متوالی جواب های یک سری از مسائل برنامه نویسی خطی است ، همگرا می باشد . آزمایش های عددی امکان پذیر بودن الگوریتم ما را نشان می دهند .
1- مقدمه :
در این مقاله ، ما مسئله کسری خطی کلی را به شکل زیر در نظر می گیریم :

که ، همه هعداد حقیقی دلخواه هستند ،
که در اعداد صحیح تعریف شده است ∅ ≠ Λ و x ∈ Λ∀ برای و .
جمع خطی مسئله نسبت ها یک بهینه سازی رده خاص در میان برنامه نویسی کسری است که برای چندین سال توجه محققان و متخصصان را جلب کرده است . اولین دلیل این است که آن مکرراً در کاربردها و برخی مسائل غیر خطی دیگری ظاهر می شود که قابل تبدیل به این شکل هستند . دلیل دیگر ، از نقطه نظر تحقیق ، این است که این مسائل اشکالات محاسباتی و نظری اصلی را مطرح می کنند ، برای مثال ، این روش عموماً برای داشتن ماکزیمم های نسبی متعددی شناخته شده است که به طور مطلق ماکزیمم نباشند . بنابراین ، لازم است روش خوبی مطرح شود . در طول سال های گذشته ، الگوریتم های مختلفی برای حل موارد خاص مسائل GFP پیشنهاد شده است که فقط برای جمع مسئله نسبت های خطی با فرض و برای همه x ∈ Λ سفارش شده اند . برای مثال ، وقتی که Λ چند بعدی است و m=2 و الگوریتم طوری ایجاد شده که روش ساده پارامتری را استفاده می کند ]1[ .
وقتی که Λ چند بعدی است ولی m ≥ 2 ، الگوریتم هایی پیشنهاد شده اند که مکرراً فضای خروجی غیر محدب را تا زمانی که جواب بهینه مطلق پیدا شود ، جستجو می کنند ]2 ،3 [ .
به علاوه با فرض اینکه و باشد ، الگوریتم شاخه و کران پیشنهاد شده است ]4[ .
هدف این مقاله است که یک روش بهینه سازی کلی جدید را به وسیله ی حل کردن یک سلسله مسئله برنامه نویسی روی زیر مجموعه های تفکیک شده برای برنامع نویسی کسری خطی کلی تر ارائه کند . ویژگی اصلی این الگوریتم ، (1) در GFP ، این است که ما فقط می خواهیم ، پس مدل سازی این مقاله کلی تر از مقاله های مطرح شده دیگر است . (2) این الگوریتم با هدایت کردن جستجوی شاخه و کردن در به جای در محاسبات مورد نیاز حرفه جویی کرد . (3) رلاکسیون خطی EP بدست می آید که در محاسبات آسان تر از روش ]5[ است و متغیرهای جدید تولید نمی کند . (4) الگوریتم شاخه و کران پیشنهاد شده به ماکزیمم مطلق که در میان تصحیح متوالی رلاکسیون خطی منطقه ی تابع مورد نظر و توابع محدودیت و جواب های یک سری از LRP است ، همگرا می باشد . (5) آزمایش های عددی داده می شوند تا امکان پذیری الگوریتم ما ار نشان دهند .
این مقاله به شکل زیر سازمان یافته است . در بخش 2 ، با استفاده از تکنیک تبدیل ، مسئله EP طوری بدست می آید که با مسئله GFP معادل است . پردازش شاخه ای مستطیلی ، پردازش کران بالایی و پایینی ، که در این روش استفاده شد در بخش 3 تعریف شده و مورد بررسی قرار می گیرند . الگوریتم در بخش 4 معرفی می شود ، و همگرایی اش نشان داده می شود . بخش 5 برخی نتایج عددی را که با حل کردن چند مثال بدست می آید ، گزارش می کند . در آخر ، خلاصه این مقاله داده می شود .
2- اقدامات اولیه :
در این بخش ، ما نخست یک قضیه مهم ارائه می دهیم که اساس الگوریتم بهینه سازی کلی است .
قضیه 1 . فرض کنید x ∈ Λ∀ برای و سپس یا .
اثبات . با استفاده از قضیه مقدار میانی ، نتیجه بدیهی است .
برایx∈Λ∀ و
. پس ما داریم :
(1) .

بدیهی است که در (1) ، مخرخ ما همه مثبت هستند . بنابراین ، در مسئله GFP ، ما می توانیم فرض کنیم که همیشه حاصل می شود .
همچنین ، (2)


که وقتی یک عددد مثبت است ، اگر به اندازه کافی بزرگ باشد ، می تواند حاصل شود . بنابراین ، در ادامه ، بدون از دست دادن کلیات ، می توانیم فرض کنیم که در GFP و
سپس ، نشان می دهیم که چگونه مسئله GFP را به مسئله معادل EP تبدیل می کنیم .

می گیریم . تعریف می شود که و
هستند ، پس مسئله GFP می تواند به مسئله معادل برنامه نویسی غیر محدب تبدیل شود که در ادامه می آید :

نتیجه هم ارزی کلیدی برای مسئله GFP و به وسیله قضیه بعدی داده می شود .
قضیه 2 : اگر جواب بهینه کلی برای مسئله باشد ، پس جواب بهینه کلی برای مسئله GFP است . به عکس ، اگر جواب بهینه کلی برای مسئله GFP باشد ، پس جواب بهینه کلی برای مسئله است ، در جایی که و است .
اثبات : اثبات این قضیه به آسانی از تعریف مسائل GFP و بدست می آید ، بنابراین ، آن حذف شده است . با استفاده از قضیه 2 ، برای حل کلی مسئله GFP ، می توان در عوض مسئله را به طور کلی حل کرد .

3. عملیات پایه ای :
در این بخش ، بر مبنای مسئله معادل بالا ، یک الگوریتم شاخه و کران برای حل جواب بهینه کلی GFP پیشنهاد شده است . ایده اصلی الگوریتم شامل سه عملکرد اساسی می شود : قسمت بندی تصحیح شده پی در پی مجموعه امکان پذیر ، تخمین کران های بالایی و پایینی برای مقدار بهینه ی تابع مورد نظر . سپس ، ما آغاز به تشکیل الگوریتم با عملیات پایه ای بر اساس طرح شاخه وکران می کنیم .

3.1 . پردازش شاخه ای :
در این الگوریتم ، پردازش شاخه به جای در انجام می شود که مکرراً مستطیلی p بعدی مسئله به مستطیل های زیر مجموعه ی کوچکتر تقسیم می شود که آن ها هم در بُعد p هستند . که مستطیل اولیه یا مستطیل های زیر مجموعه ی آن را مشخص می کند ، قانون شاخه ای در ادامه می آید :



به آسانی استنباط می شود که این پردازش شاخه ای جامع است ، برای مثال اگر توالی های تودرتوی مستطیل ها ( برای مثال ، ، برای همه k ها ) را مشخص کند که توسط پردازش شاخه ای شکل گرفته اند ، سپس یک نقطه منحصر به فرد وجود دارد به طوری که .

3.2. کران های بالایی و پایینی :
برای هر مستطیل که توسط پردازش شاخه ای شکل گرفته است ، پردازش کران بالایی برای محاسبه ی یک کران بالا برای مقدار بهینه مسئله استفاده می شود .

در زیر دیده خواهد که کران بالایی می تواند با حل کردن یک برنامه خطی معمولی پیدا شود . در ادامه، برای راحتی بیان ، در نظر می گیریم :






در ابتدا ، تابع مورد نظر را درنظر می گیریم . داریم :


سپس ، تابع فرضی را در نظر می گیریم و


بر اساس بحث بالا ما می توانیم یک برنامه نویسی رلاکسیون خطی (LRP) به صورت زیر بسازیم که کران بالا را برای مقدار بهینه V(H) مسئله (H) EP فراهم می کند .

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله  14  صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید