فصل سوم

 

ارائه مدل ریاضی و الگوریتم های پیشنهادی… 28

 

3-1- مقدمه. 29

 

3-2- تعریف مساله. 30

 

3-2-1-  فرضیات مساله. 31

 

3-2-2-  پارامترهای مساله. 32

 

3-2-3- متغیر های تصمیم مساله. 33

 

3-2-4- استراتژی های موجود مساله. 35

 

3-2-5- همگن سازی.. 37

 

3-2-6- خطی سازی مدل ریاضی.. 41

 

3-2-7- مثال.. 44

 

3-3- الگوریتم ژنتیک… 46

 

3-3-1- نمایش کروموزوم. 47

 

3-3-2- آغاز سازی.. 47

 

3-3-3- ارزیابی.. 49

 

3-3-4- معیار توقف… 49

 

3-3-5- نخبه گرایی.. 50

 

3-3-6- عملگر تقاطع.. 50

 

3-3-6-1- عملگر تقاطع نوع 1. 50

 

3-3-6-2- عملگر تقاطع نوع 2. 51

 

3-3-7- عملگر جهش…. 52

 

3-3-7-1- عملگرجهش نوع 1. 53

 

3-3-7-2- عملگرجهش نوع 2. 53

 

3-3-8- انتخاب… 54

 

3-3-9- معیار توقف… 54

 

3-4- آزادسازی لاگرانژ. 56

 

3-4-1- مقدمه. 56

 

3-4-2- مراحل الگوریتم آزاد سازی لاگرانژ. 56

 

3-4-3- شرط توقف… 57

 

3-4-4- رویه انجام الگوریتم آزاد سازی لاگرانژ. 57

 

فصل چهارم

 

نتایج محاسباتی… 60

 

4-1- مقدمه. 61

 

4-2- مسائل نمونه. 62

 

فصل پنجم

 

نتیجه گیری و پیشنهادات آتی… 71

 

5-1- نتیجه گیری.. 72

 

5-2- پیشنهادات آتی.. 72

 

مراجع فارسی… 73

 

مراجع لاتین.. 74

 

پیوست الف… 78

 

تشریح الگوریتم ژنتیک…. 78

 

1- ویژگی های الگوریتم ژنتیك… 79

 

2- واژگان الگوریتم ژنتیك… 80

 

3- ساختار كلی الگوریتم ژنتیك… 81

 

4- مفاهیم کلیدی الگوریتم ژنتیک… 83

 

4-1- كدینگ… 84

 

4-2- ایجاد جمعیت اولیه. 84

 

4-3- عملگرهای الگوریتم ژنتیك… 85

 

4-3-1- عملیات تقاطع.. 85

 

4-3-2- عملیات جهش…. 86

 

4-3-3- مکانیسم نمونه‌گیری.. 86

 

4-4- تابع برازش…. 88

 

 

4-5- استراتژی برخورد با محدودیتها 88

 

4-5-1- استراتژی ردی.. 88

 

4-5-2- استراتژی اصلاحی.. 88

 

4-5-3- استراتژی جریمه‌ای.. 89

 

Abstract. 90

 

 

 

فهرست جداول
فصل دوم:

 

جدول( 2- 1). خلاصهای از ادبیات موضوع. 7

 

جدول( 2- 2). عوامل موثر در تصمیمات مکان یابی.. 17

 

فصل سوم:

 

جدول (3- 1) . تعداد متغیر در مدل خطی و غیر خطی.. 43

 

جدول( 3- 2). تعداد محدودیت در مدل خطی و غیر خطی.. 43

 

جدول( 3- 3). مقادیر پارامتر برای . 44

 

جدول( 3- 4). مقادیر پارامتر برای ….. 44

 

جدول( 3- 5). مقادیر پارامتر برای …. 44

 

جدول( 3- 6). نتایج محاسباتی مثال نوعی.. 45

 

جدول( 3- 7). روش بهینه سازی گرادیان.. 59

 

 

 

فصل چهارم:

 

جدول(4- 1). مقادیر پارامترهای الگوریتم ژنتیک… 62

 

جدول(4- 2). نتایج محاسبات برای اندازه کوچک… 65

 

جدول(4- 3).  نتایج محاسبات برای اندازه کوچک… 66

 

جدول(4- 4). مقایسه نتایج مثال نوعی.. 69

 

 

 

فهرست شکل­ها
فصل دوم:

 

شکل( 2- 1). دسته بندی کلی مسائل برنامه ریزی تسهیلات[1]. 25

 

شکل( 2- 2). دسته بندی نوین مسائل مکان یابی [1]. 27

 

 

 

فصل سوم:

 

شکل( 3- 1). روند آغازسازی.. 48

 

شکل( 3- 2). روند ارزیابی.. 49

 

شکل( 3- 3). فلوچارت الگوریت ژنتیک… 55

 

 

 

فصل چهارم:

 

شکل(4- 1).  نمودار Gapهای بدست آمده از الگوریتم ژنتیک و الگوریتم آزاد سازی لاگرانژ. 68

 

شکل(4- 2).  نمودار سرعت همگرای الگوریتم ژنتیک… 70

 

چكیده
در این تحقیق یک مسئله مکان­یابی- تخصیص چندتسهیله ظرفیت دهی شده در محیط گسسته که با تقاضای برنولی مشتریان روبرو است، مورد بررسی قرار می­گیرد. هدف این مسئله احتمالی مکان­یابی- تخصیص تعیین مکان بهینه تسهیلات از میان مکان‌های بالقوه و تخصیص تمامی مشتریان به تسهیلاتی که مستقر شده­اند می­باشد، بطوریکه هزینه های ثابت برای استقرار تسهیلات و کل هزینه ارزش انتظاری استراتژی­ها کمینه شود. در این مسئله برای تصمیم گیری در مورد تقاضای مشتریان، با در نظر گرفتن دو استراتژی متفاوت فرمولبندی و مورد بررسی قرار گرفته است و در ادامه برای درک مسئله مذکور یک مثال عددی ارائه شده است.

 

نتایج محاسباتی این تحقیق، نشان می­دهدکه مسئله توسط نرم افزار بهینه سازی LINGO در اندازه­های بزرگ در زمان معقول به حل بهینه دست پیدا نمی­کند. به منظور نشان دادن کارائی مسئله در مقیاس­های بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک) پیشنهاد شد. الگوریتم فرا ابیکاری پیشنهادی با یک حد پایین کارا (آزاد سازی لاگرانژ) مقایسه می­شود.

 

مقدمه
یکی از مسایلی که باید در مراحل اولیه طراحی سیستم­های صنعتی مورد توجه قرار گیرد مسئله مکان­یابی- تخصیص[1]، که استقرار تسهیلات و تخصیص مشتریان به تسهیلات مستقر شده می­باشد، است. مطالعه پیرامون مکان بهینه از دیدگاه جغرافی­دانان و علمای علم اقتصادی همواره دارای اهمیت و الویت بوده است[1]. در ادبیات موضوع، مسایل مکان­یابی[2] و مکان­یابی – تخصیص مورد بحث قرار گرفتند و چند حالت از از این مسائل معرفی می­شوند. مانند مسئله ظرفیت­دهی[3] شده، مسئله بدون محدودیت ظرفیت[4] ، مسئله احتمالی[5] و مسائلی که تقاضایشان دارای توزیع برنولی[6] می­باشند. منظور از مکان­یابی، مجموعه­ای از اصول است که با توسل به آن مکان بهینه فعالیت­های (نقطه منطبق بر حداکثر سود یا حداقل هزینه) تعیین می­شود. تصمیم گیری در مورد مکان تسهیلات از اجزاء بحرانی در برنامه­ریزی استراتژیک شرکت­های بزرگ خصوصی و عمومی محسوب می­شود. مطالعه و تحقیق پیرامون مکان بهینه صنعتی همواره دارای اهمیت و الویت بسیار بوده است [2].

 

مسائل مکانیابی در فضای گسسته[7] شامل تعیین مکان یک یا چندین تسهیلات در یک یا چند مکان بالقوه است تا هزینه تأمین نیاز های مشتریان را کمینه کند. در­مسائل مکانیابی- تخصیص استقرار مجموعه­ای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار می­گیرد. در دنیای واقعی بسیاری از مسائل را می توان با استفاده از مدل­های مسائل مکان­یابی- تخصیص حل نمود­و به جواب بهینه ومعقولی دست یافت که با اجرای این مدل­ها از صرف هزینه­های اضافی می­توان جلوگیری کردو سود فراوانی بدست آورد [2].

 

در گونه­ای از مسائل مکان­یابی- تخصیص محدودیت در ظرفیت برای تسهیلاتی که وظیفه خدمت رسانی را  دارند وجود دارد. این محدودیت می­تواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و یا حتی محدودیت­های از قبیل ظرفیت معابر جهت دستیابی به تسهیلات موجود باشد. تقاضای مشتریان را می­توان در مسائل مکان­یابی- تخصیص بصورت احتمالی[8] و یا قطعی[9] در نظر گرفت. البته بدیهی است اگر بخواهیم خیلی دقیق با مسائل برخورد کنیم می­بابستی تمامی مسائل را بصورت احتمالی در نظر بگیریم که به خاطر پیچیدگی و گران بودن روش­های حل مسائل احتمالی و به فراخور نیاز های مسئله را بصورت قطعی در نظر می گیریم. در حالی که مسائل مکان­یابی- تخصیص با تقاضای احتمالی در مقایسه با مسائل مکان­یابی- تخصیص کلاسیک خیلی عملی­تر و نزدیک­تر به دنیای واقعی می­باشند، اما به علت پیچیدگی محاسباتی که این نوع مسائل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند. در این تحقیق مساله مکان یابی تسهیلات با تقاضای برنولی مورد بررسی قرار می گیرد. این تحقیق  شامل مسئله احتمالی مکان یابی گسسته است که هدف آن مکان یابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات باز می باشد. تابع هدف مینییم کردن جمع هزینه ثابت تسهیلات باز،  بعلاوه  ارزش انتظاری دیگر هزینه ها که شامل هزینه سرویس دهی، هزینه منابع برونسپاری وهزینه تقاضای برآورده نشده می­باشد. هدف از این تحقیق مکانیابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات می­باشد. در تحقیقات اخیر این مطلب مد نظر بوده  که اگر تسهیلی بیش از ظرفیت خود تقاضا داشته باشد از منابع برون سپار برای تامین تقاضای خود استفاده می کند. در حالی که ما در این تحقیق علاوه بر این حالت، حالت تقاضای برآورد نشده را در نظر می گیریم.