اولین مدل مکان یابی هاب در محیط رقابتی ، مدل ماریانو[۳۳] و همکاران در سال ۱۹۹۹ است که هدف آن جذب مشتری (جریان) بوده بطوریکه مکان یابی جدید هاب باعث کاهش هزینه های جاری(فاصله، زمان) بین مبدا و مقصد می شود[۲۳]. این مدل تعداد متغیرها ومحدودیت ها را در مقایسه با مدلهای پوششی موجود ،کاهش می دهد. برند واگنر[۳۴] در سال ۲۰۰۸ با ارئه ی دو نوع تغییر در مدل ماریانو وهمکاران ،باعث شد جواب بهینه سریعتر بدست آید[۲۴]. ایزلت[۳۵] وماریانو در سال ۲۰۰۹ مدل ماریانو وهمکاران را توسعه دادند ویک مدل غیرخطی که سهم بازار[۳۶] را توسط تابع بهره وری[۳۷] بیشینه می کند ارائه دادند که تابع بهره وری شامل زمان،هزینه وجذابیت[۳۸] می باشد[۲۵]. در سال ۲۰۱۰ ، گلاره[۳۹] وهمکاران یک مدل برنامه ریزی خطی عدد صحیح امیخته شبکه هاب را در یک محیط رقابتی ارائه دادند که هدف آن بیشینه کردن سهم بازار از طریق کاهش هزینه های حمل ونقل و زمان سرویس می باشد[۲۶].
۲-۵- استواری[۴۰]، مفهوم و نقش آن در تحقیق در عملیات
در این بخش در ابتدا به جدیترین تعریف از دیدگاه یک صاحب نظر به نام روی[۴۱] در حوزه تحقیق در عملیات اشاره و سپس طبقه بندی کلی از مدل های کلاسیک این بحث درحوزه مدل سازی ریاضی اشاره خواهد شد:
روی(۲۰۱۰) دراین تعریف بحث چند معنی بودن واژه ی استواری را مطرح می نماید و بر این اعتقاد است که چند معنی بودن می تواند ناشی از موقعیت یا شرایط باشد. ایشان بیان داشته که در حالت کلی مفهوم یا تفکر استواری می تواند با مفاهیمی چون:
انعطاف پذیری[۴۲]
ثبات ، پایایی، پایداری[۴۳]
حساسیت[۴۴]
عدالت و انعطاف پذیری[۴۵]
ارتباط داشته باشد. با این توصیف تعریف ایشان از واژه ی استوار به شرح ذیل است:
استوار صفتی است که به ظرفیتی برای پایداری تخمین های مبهم[۴۶]و یا نقاط نامشخص[۴۷] به منظور ممانعت از اثرات نامطلوب تنزل ویژگی هایی که مورد نظر است و باید آن را حفظ کرد، اطلاق می شود.
مسایل تصمیم گیری اغلب به علت عدم دقت، تغییر پذیری مستمر و ناتوانی در دیدن وقایع آینده با عدم اطمینان هایی موجه هستند . نویسندگان بسیاری بحث استواری را مورد تحقیق و بررسی قرار داده و نتیجه کار آن ها منجر به حوزه تحقیقاتی وسیعی شده است [۲۷] .
بحث استواری مدل از مباحث بسیار مهمی بوده که در اخلاق در مدل سازی و متعاقباً اخلاق در تحقیق در عملیات نیز مطرح می باشد. اگر مدل ها استوار باشند، خطر بکار گیری اشتباه یا استفاده غلط آن بسیار کمتر خواهد شد و استواری به این مفهوم است که خروجی مدل نباید خیلی نسبت به مقادیر دقیق پارامتر ها و ورودی های مدل حساس باشد [۲۸] .
بحث استواری با واژه هایی چون عدم قطعیت یا عدم اطمینان، عدم دقت، تغییر پذیری مستمر همراه است و به عبارتی استواری و مدل های مربوطه به منظور مقابله با عدم اطمینان و واژه های مشابه مورد استفاده قرار می گیرد . اگر چه روش های دیگری چون برنامه ریزی احتمالی و تحلیل حساسیت در مقابله با عدم اطمینان وجود دارد.
به لحاظ تاریخی بهینه سازی در شرایط غیر قطعی در اواخر دهه ۱۹۵۰ شروع شد و هم در زمینه تئوری و هم در زمینه الگوریتم به سرعت پیشرفت کرد. رویکرد های زیادی برای بهینه سازی در شرایط غیر قطعی مورد استفاده قرار گرفته است که از آن جمله : کمینه کردن امید ریاضی، کمینه کردن انحراف از آرمان ها ، کمینه کردن بیشترین هزینه ها را می توان نام برد. در این میان می توان سه رویکرد اصلی را متمایز کرد :
جهت دانلود متن کامل این پایان نامه به سایت jemo.ir مراجعه نمایید.
برنامه ریزی احتمالی[۴۸]
برنامه ریزی فازی[۴۹]
برنامه ریزی پویای احتمالی[۵۰]
در اواسط دهه ۱۹۵۰ دانتزیک برنامه ریزی احتمالی را به عنوان یک رویکرد، برای مدل کردن عدم قطعیت دادها معرفی کرد سه مشکل اصلی برای این رویکرد وجود دارد :
شناخت توزیع دقیق دادها و در نتیجه عددی کردن سناریو هایی که از این توزیع ها عدد می گیرند، درعمل دشوار است.
محدودیت های شانس ، ویژگی محدب بودن مساله اصلی از بین می برد و بر پیچیدگی آن به مقدار زیاد می افزاید
ابعاد مدل بهینه سازی بدست آمده به صورت نجومی با زیاد شدن تعداد سناریو ها افزایش می یابد . که چالش های محاسباتی عمده ای را موجب می گردد.
رویکردی که در سال های اخیر برای مقابله با عدمقطعیت داده ها ، بسط داده شده است ، بهینه سازی استوار است که در آن به بهینه سازی درهنگام رخ دادن بد ترین موارد پرداخته می شود که ممکن است منجر به یک تابع هدف کمینه کردن ماکسیمم شود. دراین رویکرد به دنبال جواب های نزدیک به بهینه ای هستیم که با احتمال بالایی موجه هستند . به عبارت دیگر با کمی صرف نظر کردن از تابع هدف، موجه بودن جواب بدست آمده را تضمین می کنیم . البته در مورد عدم قطعیت در ضرایب تابع هدف با کمی صرف نظر کردن از مقدار تابع هدف بهینه ، به دنبال جوابی هستیم که با احتمال بالایی جواب های واقعی بهتر از آن جواب باشند [۲۹].
به طور کلی در برنامه ریزی قطعی فرض می شود ، داده های ورودی به طور مشخص و معادل با مقادیر اسمی هستند. این نگرش تاثیر عدم اطمینان را روی کیفیت و موجه بودن مدل مد نظر قرار نمی دهد. در حقیقت داده هایی که مقادیر متفاوی را از مقادیر اسمی شان اختیار می کنند، ممکن است منجر به این مساله شوند که تعدادی از محدود یت ها نقض گردند و جواب بهینه ممکن است مدت طولانی بهینه نمانده یا حتی موجه بودن آن از بین برود این بحث خواسته ای طبیعی را به ذهن متبادر می سازد که روش های حلی طراحی و ارائه شوند که در مقابل عدم اطمینان داده ها ایمنی ایجاد کنند. این روش ها حل استوار نامیده می شوند ([۳۰]و[۳۱]و[۳۲])
اولین گام و تحقیق در این مورد از سویستر[۵۱] ارائه گردید که یک مدل برنامه ریزی خطی را برای تولید جوابی که برای همه داده های متعلق به مجموعه محدب موجه است، ارائه کرد . مدل مذکور جواب هایی ارائه می کند که در قبال بهینگی مساله اسمی به منظور اطمینان از استواری، به شدت محافظه کارانه عمل می کند. بدین معنی که در این رویکرد برای اطمینان از استوار بودن جواب، به مقدار زیادی از بهینگی مساله اسمی دور می شود . در این مدل هر داده ورودی می تواند هر مقداری از یک بازه[۵۲] را بگیرد ([۳۳] و [۳۰]و[۳۱]و[۳۲] ).
پس از گام هایی مهم دیگری به طور مستقل در توسعه بهینه سازی استوار توسط بن تال و نمیروسکی ، ال قاووی و لبرنت ، صورت گرفته است . بن تال و نمیروسکی و ال قاووی با فرض اینکه داده ها در مجموعه بیضوی دارای عدم قطعیت هستند به محافظه کاری بیش از حد نیز توجه داشته و روش های کارایی برای حل مسائل بهینه سازی محدب در شرایط عدم قطعیت داده ها ارائه نموده اند ، اما با توجه به اینکه فرمول بندی های استوار بدست آمده در روش های این محققان ، مساله در جه دو مخروطی[۵۳] می باشند، این روش ها نمی توانند به طور مستقیم برای مسائل بهینه سازی گسسته ، کارا باشند.
علاوه بر حقیقات مذکور که مبتنی بر نوسان پارامتر ها در یک بازه است تحقیقات دیگری در زمینه مدل سازی ریاضی انجام شده است .از جمله این تحقیقات می توان به تحقیق مالوی و همکاران ۱۹۹۵ که مبتنی بر مفهوم سناریو است اشاره کرد که در ادامه آن را به طور کامل توضیح می دهیم[۳۴] . از تحقیقات دیگر در حوزه استواری به برنامه ریزی استوار فازی می توان اشاره کرد که همه یا برخی از محدودیت های دارای پارامتر های از جنس فازی هستند.
۲-۵-۱- مدل استوار مبتنی بر سناریو
مالوی و همکاران ۱۹۹۵ ، در تحقیقی به عنوان بهینه سازی استوار [۵۴](RO) سیستم هایی با مقیاس بزرگ[۵۵] به بحث بهینه سازی استوار مسایل برنامه ریزی ریاضی با داده های نامطمئن می پردازند این بهینه سازی مرتبط با مسائلی است که جنس داده های آن از نوع سناریو باشد.
ایشان در این تحقیق بیان می دارند که در کاربرد های تحقیق در عملیات، مدل های برنامه ریزی ریاضی با داده های نوسانی[۵۶] خطا دار و ناکامل مورد استفاده است . مواجهه با این نوع داده ها از طریق تحلیل حساسیت با برنامه ریزی احتمالی با مشکلاتی مواجه می باشد همچنین برای حالتی که مقادیر داده ها مساله توسط مجموعه ای از سناریو ها توصیف شود ( در مقایسه با تخمین های نقطه ای ) از برتری های مدل پیشنهادی سخن به میان می آورند . از نظر ایشان دو تعریف مهم در حوزه مدل استوار وجود دارد، یعنی جواب استوار و مدل استوار که در ذیل به هر یک اشاره می شود:
یک جواب برای مدل بهینه سازی ، جوابی استوار نامیده می شود . اگر آن جواب برای همه سناریوهای داده های ورودی مدل نزدیک به بهینه باقی بماند. و همچنین مدلی استوار است که تقریباً برای همه سناریو های داده های ورودی موجه باشد.
با توجه به این مفاهیمو تعاریف ایشان یک فرموله بندی مدل عمومی که بهینه سازی استوار می شود، را توسعه دادند. واضح است که در این مدل بین استواری جواب واستواری مدل تضاد و تعارض وجود دارد . در این تحقیق بینه سازی استوار و روش های سنتی تحلیل حساسیت و برنامه ریزی خطی احتمالی مورد مقایسه قرار می گیرد، مدل بهینه سازی استوار ارائه شده توسط محققین ( مالوی و همکاران ) برای کاربرد هایی از دنیای واقعی نشان داده شده اند.
ایشان بیان می دارند که در حقیقت هنگامی که دانشمندان تحقیق در عملیات[۵۷] در تلاش هستند تا مدلی از سیستم دنیای واقعی بسازند، با مساله داده های نوسانی، ناکامل و خطا دار مواجه می شوند. در حقیقت در کاربرد دنیای کسب و کار ،داده های نوسانی رایج و متداول می باشند. نرخ بازگشت های مالی، تقاضای محصول ، هزینه سوخت مثلای هایی نمونه از داده های مدل هستند که معمولا با برخی توزیع های احتمالی شناخته می شوند در حوزه های علوم اجتماعی، مهندسی وعلوم فیزیک و … نیز داده های نوسانی قابل مشاهده است. در مقابل در مدل های برنامه ریزی ریاضی عموماً فرض می شوند، داده ها قطعی هستند و مدل ها به وسیله بهترین حدس[۵۸] مقادیر نامطمئن یا مقادیر میانگین و یا در بدترین حالت[۵۹]حل می شوند. اما این راه حل ها در مواجهه با داده های نامطمئن کفایت نمی کنند . برای مثال بریج[۶۰] در سال ۱۹۸۲ اثبات کرده است هنگامی که مسائل را به لحاظ مقادیر میانگین یا متوسط برای داده ها حل می کنیم ، خطاهای زیادی رخ می دهد[۳۵] . فرموله بندی مساله در حالت بدبینانه یا بدترین حالت نیز موجب می شود که خیلی محافظه کارانه عمل کنیم و موجب می شود که به جواب های گران و پرهزینه ای دست یابیم .
تصویر درباره جامعه شناسی و علوم اجتماعی
دانشمندان مدیریت به منظور سازش بین داده های دنیای واقعی و قلمرو برنامه ریزی ریاضی از تحلیل حساسیت استفاده نموده اند. هدف از این نوع بررسی های پس از حل ، پی بردن و کشف اثر نگرانی های داده ها در قبال خروجی های مدل می باشد. چنین بررسی های پس از حل از نوع واکنشی هستند یا اصطلاحاً خاصیت واکنش پذیری دارند.
مالوی و همکاران (۱۹۹۵) معتقدند که روش پیشگیرانه[۶۱] مورد نیاز می باشد. به عبارتی ایشان معتقدند که به جای استفاده از روش های واکنشی مثل تحلیل حساسیت از روش های پیشگیرانه استفاده شود. بنابراین باید مدل هایی طراحی و مدل سازی شوند که در مقایسه با مدل های برنامه ریزی کلاسیک نسبت به داده های مدل کمتر حساس باشند. یکی از مدل ها، برنامه ریزی خطی احتمالی است اما رویکردی که توسط مالوی و همکاران در این خصوص ارائه شده است، بهینه سازی استوار نامیده می شود این روش از مفهوم برنامه ریزی آرمانی در راستای توصیفی مبتنی بر سناریو از داده های مساله عمل می کند و کمتر نسبت به تغییر در داده ها حساس است. این روش اگر چه دارای محدودیت هاییاست اما نسبت به برنامه ریزی خطی احتمالی مزایایی دارد و به طور کلی کاربردی تر است.
درحالت کلی در مواجهه با مدل های بهینه سازی ما با دو بخش مجزا مواجه هستیم :
بخش ساختاری :که ثابت است وفاقد هرگونه نویزو پارازیت درداده های ورودی آن میباشد.
بخش کنترل : که تابع دستخوش داده های نویزی و نوسانی است.
قبل از ارائه مدل مالوی و همکاران دو مجموعه از متغیرها می بایست تعریف شود:
XϵRn1: بیانگر بردار متغیرهای تصمیم و مشروط به تحقیق یافتن ( عملکرد )[۶۲] پارامتر های نامطمئن نیستند. این ها در حقیقت متغیرهای طراحی[۶۳] ( تخصیص ) هستند.
YϵRn2: بیانگر متغیرهای تصمیم کنترل[۶۴] است که مستعد تنظیم پارامتر های نامطمئن هستند مقادیر بهینه این متغیرها وابسته به تحقیق یافتن پارامتر های نامطمئن و مقادیر بهینه متغیرهای طراحی هستند.
مدل LP بهینه سازی به صورت زیر است:
رابطه (۲-۴)
۱ Minimize cT x + dT y
۲ Subject to Ax=b
۳ Bx +Cy =e
۴ x,y 0
۵ XϵRn1, YϵRn2
معادله ۲ بیانگر محدودیت ساختاری[۶۵] است که ضرایب آن ثابت و فاقد هر گونه نویز و نوسان هستند. معادله ۳ بیانگر محدودیت های کنترل[۶۶] هستند ضرایب این محدودیت ها در بر گیرنده حالت نویزی و نوسانی هستند و معادل ۴ بیانگر اطمینان از بردارهای نامنفی می باشد.
به منظور تعریف مساله بهینه سازی استوار مجموعه ای از سناریو ها بدین شکل تعریف می شوند:
=Ω {۱,۲,۳,….,s}
متناسب با هر سناریوsϵΩ و مجموعه {ds ,Bs,Cs ,es} از تحقیق یافتن را می توان مرتبط دانست و احتمال رخداد هر سناریوPs می باشد.
جواب بهینه مدل ریاضی فوق به لحاظ بهینگی ، استوار خواهد بود اگر به ازای هر تحقیق یافتن سناریو نزدیک به بهینه باقی بماند و این استواری جواب[۶۷] نامیده می شود.
جواب همچنین در قبال موجه بودن[۶۸] استوار است، اگر جواب به ازای هر تحقق یافتن از S تقریبا مواجه باشد، این استواری مدل[۶۹] نامیده می شود.
غیر محتمل است که جواب برای مدل (۲-۴) برای همه سناریو های sϵΩهم موجه و هم بیهنه باشد. به عبارتی در یک مدل لازم است که مبادله[۷۰] بین استواری مدل و استواری جواب قابل بررسی و قابل سنجش باشد. مدل بهینه سازی ارائه شده در بخش بعد روشی را برای سنجش این مبادله ارائه می کند.
صورت کلی مدل بهینه سازی استوار مالوی و همکاران به شرح ذیل است:
رابطه (۲-۵)
Minimize σ(x,y1,y2,….,ys) + ω
Subject to Ax=b
Bsx + Csys + Zs= es for all s ϵΩ
x , ysfor all s ϵΩ
در مدل استوار (۲-۵) مجموعه {y1,y2,….,ys} مجموعه ای از متغیرهای کنترل برای هر سناریوs ϵΩاست همچنین {?۱ ,?۲ ,…,?s }مجموعه ای از بردارهای خطا است که نا موجهی مجاز در محدودیت های کنترل تحت سناریو ی s را اندازه گیری می کنند . با توجه به سناریو های چند گانه، تابع هدف =cT x + dT yمتغیر تصادفی است که مقدارξ=cT x + dTsys را با احتمال Ps می گیرد. مبادله بین استواری جواب و استواری مدل به کمک مفهوم تصمیم گیری چند معیاره[۷۱] تعیین می شود . در حقیقت مدل بهینه سازی استوار فوق قادر است میزان این مبادله را بسنجد .
در فرموله بندی برنامه ریزی خطی احتمالی مقدارمیانگین ( )=σمورد استفاده قرار می گیرد. اما در مدل استوار فوق که بهینه سازی استوار نامیده می شود، عبارتσ(۰) به صورت عبارتی غیر خطی لحاظ می شود و در حقیقت این مدل استوار مبتنی بر سناریو کاربردی از مدل برنامه ریزی غیر خطی احتمالی[۷۲] [۳۶]و [۳۴] می باشد.
عبارت دوم در تابع هدف {?۱ ,?۲ ,…,?s }یک تابع جریمه موجه بودن است که به منظور جریمه کردن نقض و تخطی از محدود یت های کنترل با توجه به برخی از سناریو ها مد نظر قرار می گیرد . نقض از محدودیت های کنترل به این مفهوم است که جواب غیر موجه برای یک مساله در برخی از سناریو های حاصل سنجیده می شود. به کمک وزنωتوازن و مبادله بین استواری جواب ( که توسط واژه σ(۰)سنجیده می شود) و استواری مدل (که توسط P(0) سنجیده می شود) می تواند تحت فرایند تصمیم گیری چند معیاره مدل شوند. برای نمونه اگر ۰=ωباشد تابع هدف عبارتσ(۰) را حداقل می کند و جواب ممکن است غیر موجه شود در حالیکه اگر به ωمقدار نسبتا بزرگی تخصیص یابد هزینه بیشتری را به دنبال خواهد داشت ([۳۶] ، [۳۴]و [۳۷]).
در خصوص یافتن شکل مناسبσ(۰) وP(0) می توان تحقیقات مالوی وهمکاران [۳۴] ، مالوی و روزینسکی [۳۷] و یوولی [۳۸] رجوع کرد.
واژه ی σ(x,y1,y2,….,ys)به وسیله مالوی وهمکاران ارائه شده شامل مقدار میانگینσ(۰) و بعلاوه مقدار ثابت ضریب در واریانس آن است، به طوری که دایم :
رابطه (۲-۶)
σ(x,y1,y2,….,ys)=
