تحقیق در مورد بهینه سازی سراسری برنامه ریزی کسری خطی تعمیم یافته با محدودیت های غیر خطی

word قابل ویرایش
28 صفحه
18700 تومان

بهینه سازی سراسری برنامه ریزی کسری خطی تعمیم یافته با محدودیت های غیر خطی

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

ضربی خطی ، برنامه ریزی چند جمله ای و غیره – در منطقه ی قابل قبول نامحدب . ابتدا یک مسئله به دست می آید که معادل مسئله ی (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:می توانیم به این نتیجه برسیم که و وقتی که

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
word قابل ویرایش - قیمت 18700 تومان در 28 صفحه
سایر مقالات موجود در این موضوع

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

word قابل ویرایش
25 صفحه
18700 تومان
بهینه سازی پیوسته الگوریتم سیمپلکس برای مسائل برنامه ریزی کسری تکه ای – خطیتعمیم های روش شناخته شده سیمپلکس برای برنامه ریزی خطی در دسترس می باشد . که این روش برای حل مسائل مربوط به برنامه ریزی تکه ای خطی و برنامه ریزی کسری خطی به کار می رود. در این مقاله از روش سیمپلکس برای برنامه های خطی ، برنامه های تکه ای ...

دانلود مقاله کاربرد برنامه ریزی خطی در تحلیل سیستمی بهره برداری و تخصیص بهینه آب در منابع آب مخازن سدها

word قابل ویرایش
8 صفحه
21700 تومان
چکیدهامروزه منابع آب در زمره گنجینههای عظیم بشری بهشمار میآیند که لازمه بهرهبرداری از آنها با توجه به نیازهای پر-شمار، کمبودها و محدودیتهای موجود در استفاده از این منابع، اعمال قوانین و مدیریت بهینه بهرهبرداری میباشد. از آنجا که بخش کشاورزی عمدهترین مصرفکننده آب در ایران است، بنابراین مدیریت و بهرهبرداری بهین ...

مقاله مدلسازی تغذیه بهینه نظامیان با استفاده از برنامه ریزی خطی و مطالعه موردی جمعیت هدف

word قابل ویرایش
17 صفحه
27700 تومان
دسته بندی : مقالات گوناگون
مدلسازی تغذیه بهینه نظامیان با استفاده از برنامهریزی خطی و مطالعه موردی جمعیت هدف چکیده با توجه به نقش کلیدی نیروهای مسلح در امنیت کشور، پیروی از رژیمهای غذایی با کیفیت بالا و اطمینان از تامین تمامی نیازمندیهای تغذیهای به منظور حفظ سلامت نظامیان از اهمیت ویژهای برخوردار است. به منظور بهدست آوردن الگویی بر ...

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

word قابل ویرایش
5 صفحه
27700 تومان
دسته بندی : مقالات گوناگون
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست *** بررسی روش زوتندیک در مسایل برنامه ریزی خطی چکیده یکی از مهمترین مسایل علم ریاضی برنامه ریزی خطی و کاربردهای آن می باشد. برای حل این گونه مسایل الگوریتم های نقطه درونی از سال 1984 مورد استفاده قرار گرفته اند. در این مقاله سعی می شود ایدۀ ز ...

مقاله بکارگیری برنامه ریزی آرمانی خطی(LGP ) در فرآیند تحلیل سلسله مراتبی فازی(FAHP )برای اولویت بندی عوامل مطالعه موردی: شرکت گاز استان کرمانشاه

word قابل ویرایش
28 صفحه
27700 تومان
دسته بندی : مقالات گوناگون
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست *** بکارگیری برنامه ریزی آرمانی خطی(LGP )در فرآیند تحلیل سلسله مراتبی فازی(FAHP )برای اولویت بندی عوامل مطالعه موردی: شرکت گاز استان کرمانشاه چکیده: فرآیند تحلیل سلسله مراتبی (AHP) برای کاربردهایی نظیر اولویت بندی و وزن دهی عوامل در علوم مختل ...

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

word قابل ویرایش
24 صفحه
27700 تومان
دسته بندی : مقالات گوناگون
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***   بکارگیری برنامه ریزی خطی چند هدفه فازی در برنامه ریزی تولید ادغامی چکیده: مقاله فوق کاربردی از برنامه ریزی خطی چند هدف فازی (FMOLP) جهت حل مسائل تصمیم گیری برنامه ریزی تولید ادغامی چند محصولی، در محیط فازی است. مدل پیشنهادی سعی ...

مقاله تحلیل و بررسی مباحث برنامه ریزی خطی

word قابل ویرایش
14 صفحه
27700 تومان
دسته بندی : مقالات گوناگون
تحلیل و بررسی مباحث برنامه ریزی خطی چکیده : پژوهش عملیاتی (تحقیق در عملیات) یا علم مدیریت، با علم تصمیم و کاربرد آن در ارتباط است. علم مدیریت را می توان به عنوان شاخه ای از حوزه مدیریت قلمداد کرد که رویه عقلایی، منطقی، سیستماتیک و علمی را در تحلیل فرآیند مدیریت و مسائل مدیریتی بکار می گیرد. پژوهش عملیاتی را ...

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

word قابل ویرایش
11 صفحه
27700 تومان
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست *** بهینه سازی سرمایه گذاری در ماشینهای کشاورزی با استفاده از مدل برنامه ریزی خطی چکیده اختصاص بهینه سرمایه، ماشین ها و ادوات کشاورزی و استفا ده صحیح از آنها از مسائل مهم سرمایه گذاری در بخش کشاورزی است. مدل های برنامه ریزی ریاضی می تواند ابز ...