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

بخشی از مقاله

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

چکیده :
در این مقاله ، یک روش شاخه و کران موثر برای مسئله کسری خطی کلی ارائه می دهیم (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 فراهم می کند .

نکته 1. V[p] مقدار بهینه مسئله p را مشخص می کند ، پس ، بر اساس بحث بالا ، مقادیر بهینه EP(H) , (LRP(H) برای به صورت V [LRP (H) ] ≥ V [ EP (H)] خواهد بود .
نکته 2 . بدیهی است که اگر ، پس .
عملکرد اساسی دیگر این است که کران پایینی را برای مقدار بهینه مسئله مشخص کنیم . با پردازش کران پایینی ، با حل کردن (LRP(H) ، جواب بهینه را خواهیم داشت . اگر
باشد ، بدیهی است که یک جواب قابل قبول مسئله است ، بنابراین ، یک کران پایینی را برای مقدار بهینه مسئله فراهم می کند .

4. الگوریتم و همگرایی آن :
بر مبنای نتایج و عملیاتی که در بخش 3 داده شد ، الگوریتم شاخه و کران برای مسئله GFP ممکن است به صورت زیر بیان شود :
الگوریتم شاخه و کران گام را انتخاب کنید .
به وسیله مشخص می شود یک جواب بهینه و مقدار بهینه برای مسئله LRP( ) می یابیم . قرار می دهیم . قرار می دهیم :

اگر بود ، توقف می کنیم . به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . در غیر این صورت ، قرار می دهیم و به گام 1 می رویم .
مرحله 1 : قرار می دهیم . را به وسیله قاعده شاخه ای به دو مستطیل p – بعدی تقسیم می کنیم . قرار می دهیم .
مرحله 2 : برای را محاسبه می کنیم و اگر ، یک جواب بهینه برای مسئله با شرط پیدا می کنیم . قرار می دهیم t=0 .
مرحله 3 : قرار می دهیم t=t+1 . اگر t>2 بود ، به مرحله 5 می رویم . در غیر این صورت ادامه می دهیم .
مرحله 4 : اگر ، قرار می دهیم ، و به مرحله 3 می رویم . در غیر این صورت ، قرار می دهیم .

قرار می دهیم . اگر بود به مرحله 3 می رود .
اگر بود قرار می دهیم و قرار و ادامه می دهیم .
مرحله 5 : قرار می دهیم : .
مرحله 6 : قرار می دهیم : برقرار می گردد . اگر بود ، متوقف می شود . به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . در غیر این صورت ، قرار می دهیم و به مرحله 1 می رویم .
مشخصات همگرایی الگوریتم در قضیه زیر داده شده اند .

قضیه 3. (a) اگر الگوریتم متناهی باشد ، پس به محض خاتمه ، به ترتیب جواب های . بهینه کلی برای مسئله های GFP , EP (H0) هستند . (b) برای همه ی جواب ناگزیر را برای مسئله GFP در پایان مرحله k مشخص می کند .
اگر الگوریتم نامتناهی باشد ، هر نقطه انباشتگی یک جواب بهینه کلی برای مسئله GFP است و .
اثبات : (a) اگر الگوریتم متناهی باشد ، پس در مرحله خاتمه می یابد . به محض پایان یافتن ، بعد از اینکه به وسیله حل کردن مسئله EP(H) پیدا شد ، برای برخی و برای یک جواب بهینه و تنظیم کردن یک جواب قابل قبول برای مسئله GFP و یک جواب قابل قبول برای مسئله است . به محض پایان یافتن الگوریتم ، شرط برقرار است . مرحله 0 و مرحله 1 و مرحله 4 اشاره دارند که . به وسیله الگوریتم ، نشان داده می شود که .چون جواب قابل قبول مسئله است، مجموع این دو اشاره دارد که . بنابراین (3) . چون داریم :
. از (3) ،در می یابیم که و اثبات بخش (a) کامل است .
(b) فرض کنید که الگوریتم نامتناهی است . پس آن یک سلسه جواب های ناگزیر برای مسئله تولید می کند که می توانیم با مشخص کنیم . برای هر به وسیله حل کردن مسئله پیدا می شود که برای برخی مستطیل های ، برای یک جواب بهینه و تنظیم کردن می باشد . بنابراین ، دنباله شامل جواب های قابل قبول مسئله GFP است . می گذاریم یک نقطه انباشتگی باشد و بدون از دست دادن کلیات فرض می کنیم که .
پس ، چون یک مجموعه پیوسته است ، است . بنابراین ف چون نامتناهی است ، می توانیم فرض کنیم که بدون از دست دادن نکات کلی ، برای دو . از Try , Horest [6] ، چون مستطیل های به وسیله دو بخش مستطیلی شکل گرفته اند ، این نشان می دهد که برای بعضی نقاط

قرار می دهیم و برای به وسیله داده می شود .
چون ، برای هر k ، با استفاده از نکته 2 و مرحله 4 ، این اشاره دارد که یک دنباله غیر صعودی از اعداد حقیقی است که از پایین به وسیله محدود شده است . بنابراین ، یک عدد متناهی است و شرط را بر قرار می کند . (5) برای هر k ، از مرحله 2 ، ، مقدار بهینه مسئله برابر است و یک جواب مطلوب برای این شکل است . از (4) ، ما داریم : . چون و پیوستگی پس :

این اشاره دارد که یک جواب ممکن برای مسئله است . بنابراین .
با جستجو کردن (5) ، بدست می آوریم که (6) .
از این رو (7)


از (6) و (7) داریم : ، بنابراین ، یک جواب بهینه کلی برای مسئله است .