رویکرد استوار در مسائل جایابی و تخصیص با داده های غیر قطعی

رویکرد استوار در مسائل جایابی و تخصیص با داده های غیر قطعی

اسلاید 1: رویکرد استوار در مسائل جایابی و تخصیص با داده های غیر قطعیاستاد راهنما : جناب آقای دکتر تیموریارائه دهنده: احسان جهانی

اسلاید 2: فهرستمفاهیم عدم قطعیت و لزوم به کار گیری روش استوار 1مساله جایابی و تخصیص نقاط لجستیکی2چند رویکرد استوار در حل مساله3معرفی مساله، متغیر ها و پارامتر ها4فرمولاسیون مدل5

اسلاید 3: Contentsمدل سازی با نرم افزار GAMS 6جواب های مدل7نتیجه گیری8فهرستwww.Win2Farsi.com

اسلاید 4: -در این تحقیق، مساله جایابی و تخصیص نقاط لجستیکی در حالت گسسته در شرایطی که داده ها در شرایط عدم قطعیت هستند مورد بررسی قرار می گیرد.-بدین منظور از رویکرد بهینه سازی استوار(Robust Optimization) استفاده شده است. زیرمجموعه های زیادی از این رویکرد می تواند مورد استفاده قرار گیرد، در این مقاله رویکرد regret مورد بررسی قرار گرفته است. چکیدهwww.Win2Farsi.com

اسلاید 5: چکیده-برای حل مدل قطعی ارائه شده و مدل استوار برای حالت غیر قطعی در سایز مساله کوچک از نرم افزار GAMS استفاده شده است و نتایج در انتها آورده شده است.- در ادامه و در مسائلی با سایز بزرگ می توان از الگوریتم های فراابتکاری مانند ژنتیک الگوریتم در حل این مساله استفاده نمود. www.Win2Farsi.com

اسلاید 6: مفاهیم عدم قطعیت و لزوم به کار گیری روش استوار اهمیت موضوع از آنجا روشن ترمی شود که:1- اکثر اطلاعات مورد استفاده در بهینه سازی، در واقعیت بیشتر از نوع غیر قطعی هستند که موارد زیر از دلایل این موضوع است:اندازه گیری، تخمین خطاهای ناشی از عدم توانایی اندازه گیری دقیق ،شرایط محیطی،فرآیند های تکنولوژیکی، خطاهای پیاده سازی که از عدم توانایی پیاده سازی جواب دقیق ناشی می شود.2- در واقعیت هم، میزان اندکی انحراف از مقدار واقعی ممکن است باعث شود جواب ما را از حالت بهینه خارج کند و شاید حتی بی معنا شود. با توجه به 2 مورد مطرح شده در بالا از لزوم کاربرد روش Robust Optimization روشن تر می شود.www.Win2Farsi.com

اسلاید 7: مفاهیم عدم قطعیت و لزوم به کار گیری روش استوار - موضوع و ایده اصلی در تمام این مسائل بهینه سازی با داده های غیر قطعی است. - موضوع بهینه سازی تصادفی(Stochastic Optimization) از مدت ها قبل و از زمان Dantzing مطرح بوده است ولی موضوع مطرح شده در بهینه سازی استوار با بهینه سازی تصادفی متفاوت است.- موارد اصلی بررسی شده در بحث به دو دسته کلی زیر تقسیم می شوند: 1-داده غیر قطعی چیست و چگونه می توان آن را دسته بندی نمود. 2-چگونه می توانیم روش های مرسوم بهینه سازی مرسوم را برای داده های غیرقطعی نیز به کار ببریم.www.Win2Farsi.com

اسلاید 8: مفاهیم عدم قطعیت و لزوم به کار گیری روش استوار - در بهینه سازی تصادفی(Stochastic optimization) داده ها، مقادیری غیر قطعی فرض می شوند که به صورت تصادفی حضور دارند و در ساده ترین حالت این اطلاعات تصادفی از توزیع پیشرفته آماری خاصی پیروی می کنند. در بسیاری از موارد توزیع شناخته شده نیست.در این بحث احتمال اینکه محدودیتی برقرار باشد مطرح است.- این گونه مسائل تا حدودی به نظر می رسد که نسبت به Robust Optimization محدودتر باشد. در کل، اگر داده های غیر قطعی از طبیعت تصادفی برخوردار بودند و توانستیم توزیع احتمال مربوط به داده ها را کشف کنیم و حاضر به تحمل هزینه خطای احتمالی در محدودیت ها شدیم این روش کاربرد خواهد داشت. با توجه به شروط مطرح شده می توان دریافت که فضای حل ما محدود می شود. هر دو موضوع Robust Optimizationو Stochastic Optimization مکمل یکدیگر هستند و معایب و مزایای مربوط به خود را دارند ولی Robust Optimization حالت کلی تری از مسائل بهینه سازی را دربر می گیرد.www.Win2Farsi.com

اسلاید 9: مروری بر ادبیات موضوع1963: مسئله جایابی-تخصیص تسهیلات توسط Cooper مطالعه شد وسپس Hakimi آن رادر طراحی شبکه به عنوان ابزاری قدرتمند بکار برد.1967: مشاهدات نشان دادند که عوامل اولیه انتخاب مکان،به ترتیب اهمیتشان،موجود بودن نیروی انسانی،مکان و نزدیکی به بازار بودند.در دهه 1970:تمایل به سمت فعالیتهای آگاهانه کسب و کار که افزایش اهمیت ملاحظات غیراقتصادی در تعیین موقعیت را به همراه داشت ،صورت گرفت.1972: ملاحظات اولیه ای از قبیل ملاحظات محیطی ،کیفیت نیروی انسانی وغیره گزارش داده شد.Revelle :نشان داد که قوانین دولتی شامل کنترل آلودگی ،فرصتهای یکسان و فعالیتهای مثبت وحفظ منابع و زیبا گرایی می تواند در انتخاب مکان نقش داشته باشد.1982:Murtagh&niwattisyamong مسئله جایابی-تخصیص ظرفیت داده شده را پیشنهاد کردند،که به عنوان یکی از تحقیقات بسیار مهم در این زمینه به شمار می آیند.www.Win2Farsi.com

اسلاید 10: مروری بر ادبیات موضوع- ضمنا ،تحقیقات قابل ملاحظه ای در زمینه تئوری مسئله جایابی-تخصیص انجام شد.این قضیه دال بر این است که این مسئله یک مسئله NP hard است. بنابراین رویکردهای حل بسیاری برای مدلهای متفاوت در دهه های اخیر پیشنهاد شده است.Logendran&terrel- مسئله جایابی-تخصیص را در حضور تقاضای احتمالی برای ماکزیمم کردن سود خالص بکار بردند.-مدلهای احتمالی برای توصیف بسیاری از موقعیتها کافی نبودند،در جاهایی که توزیعهای احتمالی تقاضاهای مشتریان نامعلوم یا نسبتا معلوم بودند.- برای مثال:برای ساختن تعدادی شرکت آبرسانی در مناطق جدید برای سرویس دهی به مشتریان جدید که تقاضاهایشان نه به طور دقیق مشخص است ونه سوابق گذشته ای در دست است،اما می توان این تقاضاها را توسط کلماتی از قبیل زیاد،کم و یا عادی بیان کرد،در اینگونه موارد تئوری مجموعه فازی بهتر می تواند برای اینچنین اطلاعات مبهمی بکار رود.Zadeh :تئوری مجموعه فازی را مطرح کرد و به طور وسیعی در مسائل بکار گرفته می شود.Zhou&liu :مسئله جایابی –تخصیص ظرفیت داده شده با تقاضاهای فازی مشتریان را مدلسازی کردند.www.Win2Farsi.com

اسلاید 11: مساله جایابی و تخصیص نقاط لجستیکی-موضوع SCM از مسائل اساسی و مهم در سیستم های توزیع کالا محسوب می شود و در این راستا مسئله توزیع کالا به واسطه نقاط لجستیکی که در آنها کالا بعد از رسیدن به این نقاط از نقاط تامین، به نقاط تقاضا فرستاده می شوند از اهمیت خاصی برخوردار است، بررسی می شود.تغییر این نقاط پس از انتخاب نهایی مستلزم هزینه گزافی است.- جهت انتخاب این نقاط باید عوامل زیر را از قبیل: سیستم توزیع، ظرفیت های ارسال و دریافت، هزینه های ارسال، هزینه های ثابت احداث نقطه لجستیکی و ... را در نظر داشت.بسیاری از این پارامترها که بر سیستم تاثیر گذار است به صورت غیر قطعی در مساله ظاهر می شوند. اگر این پارامتر ها را به قطعی در نظر بگیریم ممکن است جواب های غیر معقول بدست آید و باعث هدر دادن منابع سیستم شود. www.Win2Farsi.com

اسلاید 12: مساله جایابی و تخصیص نقاط لجستیکی-فلسفه استواری در راستای توصیف عدم حساسیت سیستم به نوسانات پارامترها مطرح شده است. قابل ذکر است که این نوسانات اجتناب ناپذیر است.در راستای نیل به این هدف پارامتر های مدل به صورت سناریو های گسسته مختلف ارائه می شود و هدف از مدل استوار بهینه سازی، بدست آوردن جواب بهینه مدل با توجه به تمامی این سناریو ها است و بدست آوردن جوابی است که در تمام شرایط بهینه استوار است. - پارامتر های مدل و فرمولاسیون مدل جایابی و تخصیص در حالت گسسته در قسمت مثال عددی آورده شده است.www.Win2Farsi.com

اسلاید 13: چند رویکرد استوار در حل مسالهVariability Modelرویکردهای بررسی استوارRegret ModelMinimax Modelwww.Win2Farsi.com

اسلاید 14: Regret Model www.Win2Farsi.com

اسلاید 15: Variability Model www.Win2Farsi.com

اسلاید 16: Minimax regretرویکرد بعدی که مطرح می شود Minimax regret است که ملاک آن انتخاب نقطه ای است که تابع ضرر ناشی از انتخاب نقاط خطا حداقل شود. دلیل آن هم این است که تقاضا و سایر عوامل قطعی نیستند و همواره درصدی خطا وجود دارد. با این رویکرد بیشترین خطا را حداقل خواهیم کرد. برای این منظور مجموعه ای از تقاضا ها را تحت سناریو های مختلف و در بازه های مختلف در نظر می گیریم و بر اساس حداقل حداکثر هزینه حمل و نقل محاسبات را پی می گیریم. www.Win2Farsi.com

اسلاید 17: تعریف مساله- مساله مورد بررسی به صورت زیر فرض می شود که در آن 5 نقطه تامین برای ارسال محصولات در نظر می گیریم که محصولات که به 3 دسته تقسیم می شوند در مسیر رسیدن به نقاط تقاضا باید از این نقاط لجستیکی بگذرند.تعداد مطلوب این نقاط 2 در نظر گرفته می شود که از میان 4 نقطه موجود انتخاب می شود. تعداد نقاط مقصد یا تقاضا 6 در نظر بگیرید. این مساله تحت 2 سناریو مطرح می شود. www.Win2Farsi.com

اسلاید 18: تعریف مسالهwww.Win2Farsi.com

اسلاید 19: تعریف مسالهwww.Win2Farsi.com

اسلاید 20: مدل سازی مساله  www.Win2Farsi.com

اسلاید 21: مدل سازی مسالهتوضیح معادلات:معادله 1: مشخص کننده تابع هدف است که میانگین هزینه کلی در تمام سناریو ها استمعادله 2: تابع هدف متناظر با هر سناریو s معین می کند.معادله 3: تعادل در رسیدن و خارج شدن کالا در نقطه لجستیکی j معادله 4:معین می کند که تقاضا کالاها در نقطه تقاضا k ام برآورد شودمعادله 5: تضمین می کمد که میزان ارسال کالا از هر نقطه ارسال، از یک میزان خاص تجاوز نکند.معادله 6: محدودیت فضا و ظرفیت در هر نقطه لجستیکی j ام برای ذخیره و ارسال کالا به نقاط تقاضامعادله 7: تعداد نقاط لجستیکی، محدود به عدد خاصی است.معادله 8: جواب شدنی مدل شرط Robust بودن را تامین می کند.www.Win2Farsi.com

اسلاید 22: مراحل حل مسالهاگر طرح تخصیص مورد نظر بتواند محدودیت استوار بودن را ارضا کند، تابع کل را بر اساس احتمال رخداد این طرح محاسبه کنیدبرای هر یک از حالات Zs را محاسبه کنیدتمام حالات تخصیص ممکن را در نظر بگیرید و لیست کنیدگام 1گام 2گام 3بهترین جواب بهینه را در میان این تخصیص ها که بتواند معادله استوار بودن را بسازد پیدا کنیدگام 4www.Win2Farsi.com

اسلاید 23: مدل قطعیsets i supply /1,2,3,4,5/ j logistic /1,2,3,4/ k demand /1,2,3,4,5,6/ t product/1,2,3/tabled(k,t) the demand should be satisfied at each demand node k and each product t 1 2 3 1 250 250 600 2 200 100 400 3 550 50 700 4 650 100 500 5 100 200 400 6 250 50 300;tableq(i,t) the capacity of the supply node i to send product t 1 2 3 1 500 200 500 2 400 100 600 3 200 150 600 4 500 150 700 5 400 50 500;www.Win2Farsi.com

اسلاید 24: tablec1(i,j,t) the cost of sending product t to logistic node j from supply node i 1 2 31.1 20 30 251.2 20 30 251.3 20 30 251.4 20 30 252.1 20 30 252.2 20 30 252.3 20 30 252.4 20 30 253.1 20 30 253.2 20 30 253.3 20 30 253.4 20 30 254.1 20 30 254.2 20 30 254.3 20 30 254.4 20 30 255.1 20 30 255.2 20 30 255.3 20 30 255.4 20 30 25;www.Win2Farsi.com

اسلاید 25: tablec2(j,k,t) the cost of sending product t to demand node j from logistic node j 1 2 31.1 20 30 251.2 20 30 251.3 20 30 251.4 20 30 251.5 20 30 251.6 20 30 252.1 20 30 252.2 20 30 252.3 20 30 252.4 20 30 252.5 20 30 252.6 20 30 253.1 20 30 253.2 20 30 253.3 20 30 253.4 20 30 253.5 20 30 253.6 20 30 254.1 20 30 254.2 20 30 254.3 20 30 254.4 20 30 254.5 20 30 254.6 20 30 25;www.Win2Farsi.com

اسلاید 26: parametersw(j) fixed cost of constructing the logistic node j / 1 20000 2 30000 3 35000 4 25000/;parametersL(j) the operation capacity constraint of each logistic node j / 1 5000 2 6600 3 5000 4 4500/;tabler(j,t) the unit capacity of each logistic node j from product t 1 2 3 1 2 2 2 2 2 2 2 3 2 2 2 4 2 2 2;variables x(i,j,t) y(j,k,t) zs z u;www.Win2Farsi.com

اسلاید 27: positive variable x,ybinary variable u;equationscostequalflow(j,t)logistic(j)supply(i,t)demand(k,t)tedad;cost.. z =e=sum((i,j,t),c1(i,j,t)*x(i,j,t))+sum((j),w(j)*u(j))+sum((j,k,t),c2(j,k,t)*y(j,k,t));equalflow(j,t).. sum((i),x(i,j,t)) =e= sum((k),y(j,k,t));demand(k,t).. sum((j),y(j,k,t)) =g= d(k,t);supply(i,t).. sum((j),x(i,j,t)) =l= q(i,t);logistic(j).. sum((t),r(j,t)*(sum((i),x(i,j,t)))) =l= L(j)*u(j);tedad.. sum((j),u(j)) =l= 2;model MIP /all/;solve MIP using MIP minimizing z;Display u.l, u.m;display x.l;display y.l;www.Win2Farsi.com

اسلاید 28: نتایج حل مدل عددیx412=150y232=50x223=600y242=100x313=400y123=400x323=200y133=500x413=700y143=500x113=500y153=400x513=500y163=300y213=600y233=200www.Win2Farsi.com

اسلاید 29:  www.Win2Farsi.com

اسلاید 30: کارهای آتیدر ادامه می توان رویکرد Minimax Regret به جای رویکرد حاضر استفاده نمود.در انتها با زیاد شدن فضای حل می توان از روش های فراابتکاری استفاده نمود.www.Win2Farsi.com

اسلاید 31: با تشکر از توجه شما!