دانلود پایان نامه

به عدم قطعیت در دادههای ورودی و تحقق کامل مجموعه سناریوها داشته باشند.
جواب بهینهای که توسط مدل بهینه سازی پایدار ارائه میشود، پایدار141 نامیده میشود اگر چنانچه با تغییر دادههای ورودی، جواب ارائه شده حتی الامکان شدنی و نزدیک به جواب بهینه باقی بماند. که معمولاً این حالت را در ادبیات تحت عنوان پایداری جواب142 ارجاع میدهند.
یک جواب شدنی143، پایدار نامیده میشود اگر چنانچه با تغییرات کوچک در دادههای ورودی این جواب همچنان شدنی باقی بماند. که معمولاً این حالت را در ادبیات تحت عنوان پایداری مدل144 ارجاع میدهند.
برای توضیح بیشتر، یک فضای جواب برنامهریزی خطی دو متغیره را مطابق شکل 2-1 در نظر بگیرید. چنانچه پارامترهای مسئله مثل ضرائب فنی145 قطعی فرض شود، فضای جواب چیزی شبیه مستطیل سبز رنگ خواهد بود که در شکل تحت عنوان مرز اسمی146 نامگذاری شده است. در این حالت چنانچه ضرائب تابع هدف قطعی فرض گردد جواب بهینه جایی در محل برخورد ترازهای این تابع با فضای جواب بدست خواهد آمد و این جواب، جواب بهینه قطعی مسئله مورد بحث خواهد بود.

شکل ‏21- فضای جواب شدنی مسئله برنامه ریزی خطی با ضرائب فنی غیرقطعی
حال تصور کنید که ضرائب فنی مسئله فوق دارای عدم قطعیت باشد. این فرض بدین معنی است که هرکدام از محدودیتهای مسئله که در حالت قبل مثل یک مرز ثابت و بصورت خطی با شیب ثابت عمل مینمود دیگر چنین نخواهد بود بلکه با توجه به عدم قطعیت در شیب خط مفروض، این محدویت همانند یک خط با شیبی نا معلوم حوالی شیب اسمی خود در نوسان است. نتیجه چنین فرضی برای تمام محدویت ها منجر به ایجاد فضائی شبیه مستطیلهای آبی شکل فوق میگردد که در اثر عدم قطعیت در شیب آن ها که معادل ضرائب فنی محدودیت هاست، بوجود میآید. در نتیجه فضای موجه مسئله که در حالت قبل یک مستطیل ثابت بود، تحت این فرض به شکلی نا منظم تبدیل خواهد شد که با خط مشکی پُررنگ در شکل فوق مشخص گردیده است. این فضای موجه جدید تحت عنوان فضای موجه هم ارز147 مسئله غیرقطعی، شناخته میشود. اولین و ساده ترین رویکرد این است که با تقریبات کاملاً ریسک گریزانه، یک فضای جوابی را تقریب بزنیم که مطمئن باشیم تحت هیچ شرایطی و با وقوع همزمان غیرمحتمل ترین رخدادها در مقادیر ضرائب فنی هیچگونه خللی به فضای جواب پیشنهادی وارد نمی گردد. این فضای موجه تقریبی در شکل 2-1 با یک شکل بیضی آبی رنگ درون مستطیل قبلی مشخص شده است. بدیهی است محل برخورد اولین بهترین تراز تابع هدف با بیضی فوق الذکر، جواب بهینه مسئله است (تقاطع خط تقریبی148 با بیضی). اما چند نکته مهم در مورد این جواب بهینه قابل ذکر است؛ اول اینکه مقدار جواب بدست آمده به شدت از مقدار واقعی جواب بهینه فاصله دارد و این از رویکرد ریسک گریزی این حل نشأت گرفته است و مطلوبیت جواب فوق را برای شرایط واقعی مسئله کاهش میدهد. ثانیاً این رویکرد هیچگونه احتمالاتی را برای جواب گزارش نمی دهد. چه بسا جوابهای بهتر و با احتمال ناچیزِ نقضِ موجهیت موجود باشد که تصمیم گیر در مقابل جواب بهتر، ریسک کم ناشی از احتمال نشدنی بودن آن را بپذیرد.
با این توضیحات هدف از رویکرد بهینه سازی پایدار ارائه مدلی از عدم قطعیت است که ریسک پذیری و ریسک گریزی تصمیمگیر را نیز به عنوان یک پارامتر وارد مدل نماید و جواب هایی را ارائه دهد که حاصل بالانس149 بین بهتر بودن جواب و احتمال نشدنی بودن آن باشد.
با جستجوی واژه پایدار در ادبیات موضوع میتوان به خیل وسیعی از مقالات با این رویکرد دست یافت. اما این واژه به واقع منحصر به یک رویکرد مشخص با ادبیات منحصر به فرد نیست. چرا که طبق تعاریف فوق هر مدلی که شرایط تعریف را احراز نماید میتواند پایدار نامیده شود. فلذا در این تحقیق سعی میشود تا رویکردهای مختلف پایدارسازی جواب بهینه مورد بررسی قرار گیرد و از حیث کارائی، سهولت مدلسازی، درجه غیرخطی بودن، احتمالی یا قطعی بودن، کنترل پذیری محافظه کاری150 و سایر عوامل مورد مقایسه قرار گرفته و در نهایت یک چارچوب کلی تصمیم گیری در شرایط و مقتضیات مسئله ای که قرار است در قالب این نوع بهینه سازی مدل گردد بدست آید.
از این رو در این تحقیق چهار نوع رویکرد متفاوت در اینگونه بهینه سازی ارائه میگردد.
2-4-2-1- بهینه‌سازی تصادفی پایدار151
بهینه‌سازی تصادفی پایدار یکی از متداولترین روشها در زمینه بهینه‌سازی و علم کنترل پس از سال 1990 میلادی است، و مساله بهینه‌سازی با پارامترهای غیرقطعی را مورد بررسی قرار میدهد. مولوی و همکاران152(1995) مدلی را برای بهینه‌سازی پایدار معرفی میکند که شامل دو نوع پایداری است: پایداری جواب (جواب در همه سناریوها تقریباً بهینه است) و پایداری مدل (جواب در تمامی‌سناریوها تقریباً شدنی است). تعریف “تقریباً” وابسته به مدل ساز است؛ تابع هدف مدل مورد نظر توابع جریمه کلی را هم برای پایداری مدل و هم پایداری جواب دارد و به منظور دستیابی به ارجحیت مدل‌کننده بین دو حالت فوق با استفاده از دو پارامتر وزن‌دهی می‌شود. روش بهینه‌سازی پایدار ارائه شده توسط مولوی و همکاران (1995) درحقیقت برنامه‌ریزی تصادفی را از طریق تعویض تابع هدف کمینه‌سازی هزینه مورد انتظار با تابعی که صریحاً تغییرپذیری هزینه را نشان میدهد، توسعه می‌دهد. در مدل پیشنهادی تحقیق حاضر از روش برنامهریزی تصادفی پایدار و توسعه آن به حالت دو هدفه بهره گرفته شده است بنابراین در ادامه فرم استاندارد این نوع برنامهریزی تشریح میگردد.

(‏2- 2)

(‏2- 3)

(‏2- 4)

(‏2- 5)
که در آن x، بردار متغیرهای تصمیم‌گیری را نشان می‌دهد، که باید تحت عدم‌قطعیت پارامترهای مدل تعیین شوند. B و C ماتریس ضرایب فنی تصادفی و e بردار سمت راست را نشان میدهد. فرض کنید Ω={1,2,…,s} یک مجموعه محدود از سناریوها برای مدل‌کردن پارامترهای غیرقطعی باشد و برای هر سناریو ss Ω، زیرمجموعه {ds; Us; Vs; es} را داریم. احتمال وقوع هر سناریو برابر است با ps (∑s ps = 1).
توجه شود که یک سناریو مجموعه‌ای از داده‌های تحقق یافته در افق برنامه‌ریزی است. ضرایب نامشخص B, C, e می‌توانند برای هر سناریو s Ω به صورت Us, Vs و esدرنظر گرفته شوند. همچنین متغیر y، که یک متغیر کنترلی می‌باشد و زمانی که یک سناریو تحقق مییابد، میتواند به عنوان ys برای هر سناریو s نشان داده شود. به دلیل غیرقطعی بودن پارامتر، جواب مسئله ممکن است به ازای برخی سناریوها غیرموجه باشد. به این منظور s، غیر موجه بودن جواب را در سناریوی s نشان می‌دهد. اگر جواب شدنی باشد، s صفر خواهد بود، در غیراین‌صورت، صs با توجه به معادله (2-8) مقدار مثبت به خود می‌گیرد. یک مدل بهینه‌سازی تصادفی پایدار به فرم زیر فرمول‌بندی میشود:

(‏2- 6)

(‏2- 7)

(‏2- 8)

(‏2- 9)
اولین عبارت، پایداری جواب را نشان میدهد و خواسته تصمیم گیر برای دستیابی به کمترین هزینه را تحقق میبخشد و در عین حال درجه ریسک گریزی او را نشان می‌دهد در حالیکه عبارت دوم پایداری مدل را نشان میدهد و در واقع جواب هایی که نتوانسته اند تقاضا یا هر محدودیت فیزیکی دیگری نظیر ظرفیت در یک سناریوی مشخص را ارضا نمایند، جریمه مینماید. فرض کنید از ξ برای نشان دادن f (x, y)، که یک تابع هزینه یا سود است، استفاده ‌شود و ξs = f (x, ys).
اگر تابع سود یا هزینه ξs =f (x, ys) دارای واریانس قابل توجهی باشد به معنی یک تصمیم‌گیری پر خطر است. به عبارت بهتر، یک تغییر جزئی در پارامترهای غیرقطعی میتواند باعث تغییرات عمده در تابع هدف شود. مولوی و همکاران (1995) معادله ذیل را برای ارائه پایداری جواب بهکار برد

(‏2- 10)
که λ وزن نسبی پایداری جواب است و در واریانس جواب ضرب میشود و در واقع با افزایش مقدار λ از حساسیت جواب به تغییرات پارامترهای ورودی مدل تحت همه سناریوهای مفروض کاسته میشود.
همانطور که دیده میشود، یک عبارت درجه دوم در معادله (2-12) وجود دارد. یو و لی153 (2000) برای کاهش محاسبات و حذف عامل غیرخطی، قدر مطلق را به جای عبارت درجه دوم به کار بردهاند که به این صورت ارائه شده است:

(‏2- 11)
گرچه عبارت فوق یک تابع غیرخطی است ولی میتواند با تغییر متغیر و جایگزین نمودن دو متغیر نامفنی تبدیل به یک مدل برنامه‌ریزی خطی شود، توجیه این تساوی، یک تغییر ساده در متغیرها است و بر اساس لئونگ و همکاران154 (2007) ، میتوان آن را بصورت زیر بازنویسی کرد:

(‏2- 12)

(‏2- 13)

(‏2- 14)

این ساده سازی میتواند اینگونه تفسیر شود که از آن جاییکه ξs بزرگتر از ∑ssΩ psξs است، بنابراین θs = 0 است. درحالتیکه مقدار ∑ssΩ psξs بزرگ تر از ξs است، در نتیجه، θs = ∑ssΩ psξs – ξs.
عبارت دوم در تابع هدف ρ(δ1, δ2, …, δs)، تابع جریمه غیرموجه بودن است و برای جبران میزان تعدی از سمت راست محدودیت‌های کنترلی در برخی سناریوها بهکار میرود. در واقع تعدی از سمت راست محدودیت به معنای غیرموجه بودن آن محدودیت میباشد. این جریمه توسط ضریب ω کنترل میشود.
با توجه به این بحث تابع هدف میتواند به صورت زیر مدل شود:

(‏2- 15)

2-4-2-2- بهینه سازی پایدار155 با پارامترهای بازه ای
بنتال و نمیرووسکی156 (2000) در پژوهشی که روی چندین مورد مطالعاتی از کتابخانه مسائل بهینه سازی خطی Net Library انجام دادهاند به این نتیجه رسیدند که در کاربردهای برنامهریزی خطی در دنیای واقعی، نمی توان این احتمال را که عدم قطعیتهای کوچک در داده ها میتواند جواب بهینه معمول را از نقطه نظر کاربردی کاملاً بیمعنی نماید، نادیده گرفت. از این رو بطور طبیعی گرایش به سمت ایجاد مدل هایی که بتواند جواب ها را حتی الامکان نسبت به عدم قطعیت دادهها ایمن نماید، رو به فزونی نهاد. اولین تلاش ها در این راستا توسط سویستر157(1973) صورت پذیرفت. او یک مدل بهینه سازی خطی را پیشنهاد داده است که در آن جواب بدست آمده به ازای تمامی مقادیر متعلق به یک مجموعه محدب، شدنی باقی میماند. مدل پیشنهادی او جواب هایی را تولید مینماید که بسیار محافظه کار هستند بدین معنی که قسمت عمدهای از بهینگی مسئله اسمی جهت تضمین پایداری آن قربانی میشود.
او مدل برنامهریزی خطی زیر را در نظر گرفته است:
P1: maximize c’x

subject to
(‏2- 16)
xj ≥ 0,

و فرض کرده که عدم قطعیت پارامتر aij را تحت تأثیر قرار میدهد. در روش بهینه سازی پایدار فرض بر این است که در سطر iام از معادله (2-16) تنها برخی از پارامترها مقید به شرط عدم قطعیت هستند و این مجموعه از پارامترها را با Ji نمایش میدهند. هر پارامتر aij که Ji jj را بصورت یک متغیر تصادفی محدود و متقارن مدل میکنند که تنها میتواند مقادیر بازه [āij−âij, āij+âij] را با مرکزیت āij، که مقدار اسمی نامیده میشود، اختیار نماید و âij میزان دقت برآورد را اندازه میگیرد.
او نشان میدهد که مسئله فوق معادل مسئله زیر است:

P2: maximize c’x
(‏2- 17)
s.t.

xj ≥ 0,

where.
سویستر (1973) در حقیقت بیشترین محافظت را انجام میدهد و در عمل نیز بسیار محافظه ک
ارانه است چراکه جوابی که به عنوان جواب بهینه پایدار ارائه میدهد در عمل بسیار بدتر از جواب بهینه مسئله اسمی است.
از مهمترین اقدامات شایان ذکر در این حوزه، تلاشهای مستقل دیگری است که توسط بنتال و نمیرووسکی (1998), (1999), (2000), ، القائویی و لبرت158 (1997) و القائویی و دیگران159 (1998) صورت گرفته است. اگر محافظه کاری جواب ها را مقایسه کنیم، این مدل ها با در نظر گرفتن برنامهریزی خطی همراه با عدم قطعیت بیضی شکل، مدلهای با محافظه کاری کمتری را ارائه داده اند. در واقع یک فضای جواب پایدار هم ارز160 مسئله اولیه را به فرم مسئله کوادراتیک مخروطی161 حل نموده اند. با انتخاب مناسب بیضی، از فرموله بندی آن میتوان برای تقریب منطقی تری از مجموعههای پیچیدهتر عدم قطعیت استفاده نمود. نتیجه مستقیم چنین فرموله بندی تبدیل مسئله خطی اولیه به فرم برنامهریزی غیر خطی محدب است که از نظر


دیدگاهتان را بنویسید