بخشی از مقاله
بهینه سازی سراسری برنامه ریزی کسری خطی تعمیم یافته با محدودیت های غیر خطی
چکیده :
این مقاله یک الگوریتم انشعاب – و – حد را برای حل سراسری یک مجموعۀ گسترده از مسائل برنامه ریزی کسری خطی تعمیم یافته ارائه می کند . این مجموعه شامل مسائل این چنینی می باشد : به حداقل رساندن یک مقدار ، یا خطا برای محصول یک تعداد محدود از نسبت های توابع خطی ، برنامه ریزی
ضربی خطی ، برنامه ریزی چند جمله ای و غیره – در منطقه ی قابل قبول نامحدب . ابتدا یک مسئله به دست می آید که معادل مسئله ی (GLFP) می باشد . در این الگوریتم ، کران های پایینی با حل یک مجموعۀ متوالی از مسائل برنامه ریزی داهلش خطی ، که براساس ساختار توابع خطی با کران پایین برای تابع هدف و توابع محدودیت مسئله ی در منطقه ی قابل قبول می باشد ، به دست می آیند . ویژگی همگرایی الگوریتم ارائه شده ، ثابت می شود و نتایج عددی برای نشان دادن امکان پذیری الگوریتم پیشنهادی ، ارائه می شوند .
واژه های کلیدی :
برنامه ریزی کسری خطی تعمیم یافته ؛ بهینه سازی سراسری ؛ داهلش خطی ؛ انشعاب و حد .
1- مقدمه :
مسئله ی برنامه ریزی کسری خطی تعمیم یافته ی زیر را در نظر بگیرید :
که :
ضرایب حقیقی اختیاری هستند و اعداد حقیقی اختیاری هستند و p یک عدد طبیعی می باشد . توابع خطی آفین در می باشند به طوریکه برای همۀ باشد . به ازای بعضی ، اگر باشد چون عبارت می باشد . بنابراین ، بدون از دست دادن کلیت ، می توانیم فرض کنیم که اعداد حقیقی مثبت هستند . مسئله ی (GLFP) سال های زیادی است که توجه محققان و کارآموزان را به خود جلب کرده است . دلیل این امر آنست که ، از دیدگاه علمی ، مسئله ی (GLFP) و موارد خاصی از مسئله ی (GLFP) چند کاربرد مهم دارند . این کاربردهای مهم شامل مسائل حمل و نقل چند مرحله ای ، تحلیل خوشه ای ، سهام اوراق فرضه چند
هدفه و غیره می باشند . از دیدگاه یک محقق ، مسئله (GLFP) مشکلات محاسباتی و نظری مهمی را به وجود می آورد . این بیشتر به دلیل این حقیقت می باشد که این مسئله به طور کلی به داشتن چند حد مطلوب موضعی شناخته شده است که به طور جامع مطلوب (بهینه) نیستند . در دهه ی اخیر ، الگوریتم های جواب بسیاری برای حل سراسری (جامع) موارد خاصی از (GLFP) پیشنهاد شده اند . برای مثال ، وقتی که باشد ، الگوریتم های بسیاری برای حل
سراسری مجموع مسائل نسبت های (کسری) خطی با محدودیت های خطی پیشنهاد شده اند . وقتیکه P=1 باشد ، عدد حقیقی مثبت می باشد و ، مسئله ی (GLFP) با محدودیت های خطی به مسئله ی برنامه ریزی ضربی خطی تبدیل می شود ، چند الگوریتم خاص را می توان به دست آورد ، [7 و 6] . وقتی که یک عدد یا متغیر حقیقی باشند ، و عدد حقیقی اختیاری باشد ، مسئله ی (GLFP) به مسئله ی برنامه ریزی هندسی تعمیم یافته تبدیل می شود ، الگوریتم
های بسیاری به دست آمده اند [8] . اخیراً ، یک الگوریتم جدید برای حل سراسری مجموع مسائل نسبت های خطی با ضرایب در یک چند سقفی ارائه شده است . گرچه روش های بهینه سازی برای اشکال خاصی از مسئله ی (GLFP) فراگیر است ، تاکنون ، تا آنجا که ما می دانیم ، کار کمی برای حل سراسری مسئله ی (GLFP) پرداخته شده در این مقاله و در [5] انجام شده است ، نویسنده ها متذکر شدند که مسئله ی (GLFP) در یک روش چند سقفی در این آثار
بسیار کم مورد بررسی و مطالعه قرار گرفته است . انگیزۀ تحقیق ما نیز بیشتر اثر Tuy , Hoai – Phuong می باشد . در این مقاله ، ما یک الگوریتم انشعاب – و – حد را برای حل سراسری مسئله ی برنامه ریزی کسری خطی تعمیم یافته (GLFP) با محدودیت های غیر خطی ارائه می کنیم که مدل آن کاربردهای بسیار متنوعی دارد . این الگوریتم با حل مسئله ی برنامه ریزی نامحدب کار می کند که معادل مسئله ی (GLFP) می باشد . ما در این الگوریتم توابع خطی با کران پایین (LLBFS) را از تابع هدف وتابع محدودیت مسئله ی در یک منطقه ی قابل قبول ایجاد می کنیم . سپس یک برنامه ریزی خطی داهلشی (Linoar
relaxation) به دست می آید که کران پایین مقدار مطلوب (بهینه) را فراهم می سازد . محاسبه ی اصلی شامل حل یک مجموعۀ متوالی از مسائل برنامه ریزی خطی می باشد ، که برای آنها الگوریتم سیمپلکس استاندارد در دسترس می باشد . و بالاخره نتایج تجربه ی عددی نشان می دهد که الگوریتم پیشنهادی با موفقیت برای حل مینیمم کلی (حداقل مطلق) مسئله ی (GLFP) در میکرو کامپیوتر استفاده می شود . سازماندهی این مقاله بدین ترتیب می باشد : در
بخش 2 ، نشان می دهیم که چگونه مسئله ی (GLFP) رابه مسئله ی برنامه ریزی نامحدب معادل تبدیل کنیم . در بخش 3 (LLBFS) را از تابع هدف و توابع محدودیت مسئله ی (Q) بوجود می آوریم ، و سپس برنامه ریزی خطی داهلشی مسئله (Q) به دست می آید . الگوریتم انشعاب – و – حد که در آن زیر مسائل داهلشی جای داده شده اند ، در بخش 4 تشریح می شود ، و تقارب (همگرایی) ان نشان داده می شود . برخی نتایج عددی در بخش 4 گزارش می شوند و بخش 5 نکات پایانی را ارائه می کند .
2 – برنامه ی نامحدب معادل
در این بخش ، نشان می دهیم که چگونه مسئله ی (GLFP) به یک مسئله ی برنامه ریزی نامحدب معادل تبدیل می شود که این مسئله ی برنامه ریزی نامحدب معادل شامل بردار 2T,x و متغیرهای کمکی می باشد که است . به منظور حل سراسری مسئله ی (GLFP) ، الگوریتم انشعاب و حد را می توان برای مسئله ی (Q) ، معادل مسئله ی (P) می باشد ، استفاده کرد .
فرض 1 : برای هر ، صادق است که اسکالرهای مثبت وجود دارند که در برای همه ی x های متعلق به منطقه ی قابل قبول صدق می کنند .
فرض کنید باشد و برابر را اینگونه تعریف کنیم :
و مجموعه
و بدون از دست دادن کلیت ، فرض کنید که باشد . سپس می توانیم مسئله ی برنامه ریزی نامحدب زیر را معادل با مسئله ی (GLFP) به دست آوریم:
که
نتیجه کلیدی هم ارزی برای مسائل (GLFP) و (P) با قضیه ی زیر ارائه می شود .
قضیه ی 1 . اگر یک جواب بهینه ی سراسری (جامع) برای مسئله ی (p) باشد ، پس و یک جواب بهینه ی جامع برای مسئله ی (GLFP) می باشد . برعکس ، اگر یک جواب بهینه ی سراسری (جامع) برای مسئله ی (GLFP) باشد ، پس یک جواب بهینه ی جامع برای مسئله ی (p) می باشد ، که می باشد .
برهان : فرض کنید یک جواب بهینه ی جامع برای مسئله ی (p) باشد . سپس برای هر می باشد .
این نتیجه می دهد که برای هر
بنابراین
برای هر ، هرگاه . آنگاه یک جواب بهینه ی جامع برای مسئله ی (p) می باشد و ، در این مسئله ، یک تابع هدف با مقداری برابر با دارد . چون یک جواب مطلوب جامع (سراسری) برای مسئله ی (p) می باشد ، نتیجه می گیریم که : (1)
از (1) و (2) به این نتیجه می رسیم : (3)
و برای هر . برای هر و و و و . به این نتیجه می رسیم که برای هر و و و می باشد . برای هر جواب قابل قبول x برای مسئله ی (GLFP) ، اگر و قرار دهیم و ، آنگاه یک جواب قابل قبول برای مسئله ی (p) می باشد و ، در این مسئله ، یک تابع هدف با مقداری برابر با h(x) دارد . چون یک جواب بهینه ی جامع برای مسئله ی (p) می باشد . این بدان معناست که برای هر جواب قابل قبول x برای مسئله ی (GLFP) ، داریم :
از فرمول (3) ، چون ، به این نتیجه می رسیم که یک جواب مطلوب جامع برای مسئله ی (GLFP) می باشد . برای نشان دادن گزاره (عبارت) عکس ، فرض کنید که یک جواب بهینه ی جامع برای مسئله ی (GLFP) باشد ، و هرگاه باشد و باشد ، و . آنگاه یک جواب قابل قبول با مقدار تابع هدف در مسئله ی (p) می باشد .
فرض کنید یک جواب قابل قبول برای مسئله ی (p) باشد . آنگاه برای هر و و و و می باشد . و برای هر و و و و می باشد . این بدان معناست که برای هر
بنابراین (4)
چون می باشد و یک جواب بهینه ی جامع برای مسئله ی (GLFP) می باشد و بنابراین . همراه با (4) به این نتیجه می رسیم که : (5)
از آنجا که و ، و و
از فرمول (5) و (6) به این نتیجه می رسیم :
بنابراین یک جواب مطلوب جامع برای مسئله ی (p) می باشد ، و برهان کامل می شود .
برای مسئله ی (p) ، چون فرض 1 برقرار می باشد ، ما از یک تبدیل متغیر نمایی استفاده می کنیم .
فرض کنید و و و و باشد
بردار را تعریف کنید
هرگاه باشد و هرگاه ، آنگاه بدون از دست رفتن عمومیت (کلیت) ، می توانیم مسئله ی p را دوباره به این ترتیب بنویسیم :
که
و ضریب ثابت واقعی (حقیقی) مثبت هستند ؛ یا عدد حقیقی اختیاری هستند .
از فرضیۀ 1 ، متوجه می شویم که ، به منظور حل سراسری مسئله ی (GLFP) ، ما در عوض ممکن است مسئله ی (Q) را به طور جامع (سراسری) حل کنیم . بعلاوه ، دیدن اینکه مقادیر بهینه ی سراسری مسئله ی (GLFP) و (Q) برابر هستند ، آسان می باشد . در ذیل کار اصلی حل سراسری برنامه ریزی (Q) می باشد .
3- برنامه ریزی داخل شی خطی
در این بخش مفهوم توابع کراندار خطی (LBFS) ارائه می شود تا برنامه ریزی داهلشی خطی مسئله ی (Q) را به وجود آورد . که می تواند کران های پایین مقدار بهینه را در الگوریتم انشعاب و حد به دست دهد .
1-3- توابع کراندار خطی
ما نیاز داریم تا توابع خطی با کران پایین تابع هدف و توابع محدودیت مسئله ی (Q) را که ساختار خاصی دارد ، بوجود آوریم . ما تابع را در نظر می گیریم . برای هر m ، از طریق به وجود آوردن توابع خطی با کران پایین (LBFS) و توابع خطی با کران بالا (LBFS) از توابع و به آسانی می توانیم LLBFS توابع و را به دست آوریم .
معلوم است که تابع ، یک تابع محدب درباره ی تک مغیر می باشد . هرگاه و به ترتیب LLBF و LUBF تابع را در بازه ی نشان دهند . آنگاه با تحدّب ، تابع LLBF به این ترتیب ارائه می شود :
که
بعلاوه ، LLBF برای موازی با می باشد ، بنابراین نقطه ی محمل مماسی در اتفاق می افتد ، و LLBF برابر است با
که تقریب مماسی در نقطۀ نامیده می شود . با فرمول (7) و (8) ، در نتیجه خواهیم داشت که :
برای .
داهلش خطی مسئله ی (Q) را می توان با تخمین کم هر تابع LLBF برای هر محقق کرد . این LLBF ها با تخمین کم هر عبارت تلویحاً تفکیک پذیر با یک تابع خطی ایجاد خواهند شد . بر طبق بحث بالا LLBF ها را می توان با روش زیر ایجاد کرد .
برای هر ، نمادهای زیر معرفی و عرضه می شوند :
طبق فرمول های (7) و (8) ، می توانیم LLBF و LVBF توابع بالا را به این ترتیب بدست آوریم :
در توابع در برای هر با صدق می کنند .
قضیۀ 2 : توابع ، ، را برای هر در نظر بگیرید ، سپس خطای ماکسیمال داهلش خطی با استفاده از به این ترتیب می باشد :
که
برهان : خطای داهلشی با استفاده از را می توان به این ترتیب نشان داد :
چون یک تابع مقعر در حدود برای هر می باشد ، پس خطای ماکسیمال (بیشینه) در نقطه ی روی می دهد و مقدار آن که با نشان داده می شود ، عبارت است از :
از سوی دیگر ، چون یک تابع محدب در حدود برای هر می باشد ، در اینصورت خطای ماکسیمال (بیشینه) که با نشان داده می شود ، در نقطۀ یا روی خواهد داد . چون
بنابراین . این برهان را کامل می کند .
2-3. برنامه ریزی داهلش خطی
با فرض و نشان دادن با ، LLBF مربوط به با برابر می شود ، ، . بوسیله ی قضیه ی 2 می توانیم مسئله ی برنامه ریزی داهلش خطی متناظر مسئله ی (Q) در را به این ترتیب بسازیم :
که
براساس underestimators های خطی ، هر نقطه ی قابل دسترس مسئله ی (Q) در زیر دامنه ی در مسئله ی قابل قبول (شدنی) است ؛ و مقدار تابع هدف برای مسئله ی کمتر یا برابر با مقدار آن برای مسئله ی (Q) برای تمام نقاط در می باشد . بنابراین مسئله ی یک کران پایین معتبر (قابل پذیرش) را برای حل مسئله ی (Q) در مجموع افزار فراهم کند . باید متذکر شویم که مسئله ی تنها حاوی محدودیت های ضروری می باشد تا همگرایی الگوریتم را تضمین کند .
4- الگوریتم و همگرایی آن
در این بخش یک الگوریتم انشعاب و حد پیشنهاد می شود تا مسئله ی (Q) را براساس روش داهلش خطی قبلی به طور جامع (سراسری) حل کنیم . این روش نیاز به حل یک دنباله از برنامه ریزی خطی داهلشی در مستطیل اولیه یا زیر مستطیل افزار شدۀ دارد تا اینکه یک جواب بهینه ی جامع بیابد . روش انشعاب و حد براساس افزار کردن مجموعه به ابر مستطیل های فرعی ، می باشد که هر کدام مربوط به یک گره از درخت انشعاب و حد می شود ، و هر گره با
یک زیر مسئله ی خطی داهلش در هر ابر مستطیل فرعی مرتبط می باشد . بنابراین ، در هر مرحله K از الگوریتم ، فرض می کنیم که یک مجموعه از گره های فعال (موثر) داریم که با نشان داده می شوند ، یعنی ، هر کدام با یک ابر مستطیل مرتبط هستند . برای هر گره ، ما یک کران پایین از مقدار بهینه ی مسئله ی (Q) را از طریق جواب مسئله ی محاسبه خواهیم کرد ، بنابراین کران پایین از مقدار بهینه ی مسئله ی (Q) در کل منطقه ی مستطیلی اولیه در مرحله ی K با حاصل می شود .
نکته از قضیۀ 2:می توانیم به این نتیجه برسیم که و وقتی که
