2-2- نحوه­ی برخورد با خروجی­های نامطلوب… 27

2-3- پیشینه: 28

جمع­بندی: 30

فصل 3- بررسی مدل­های DEA با داده­های نامطلوب… 32

3-1- مدل غیرخطی فار 34

3-1-1- اندازه کارایی خروجی هذلولوی افزایشی.. 35

3-1-2- اندازه کارایی تولید هذلولوی افزایشی.. 36

3-1-3- اندازه کارایی تولید هذلولوی معمولی.. 37

3-1-4- ویژگی­ها مدل فار 39

3-1-5- تبدیل به مدل خطی.. 39

3-2- شاخص عددی مالم­کوئیست­لیونبرگ… 40

3-3- مدل­های شعاعی.. 43

3-3-1- مدل شعاعی بر حسب مدل­های پایه­ای.. 43

3-3-2- مدل شعاعی بر حسب انتقال داده­ها 46

3-4- مدل­های بر حسب متغیرهای کمکی.. 49

3-5- مدل­های جهتی.. 51

3-6- مدل راسل.. 52

جمع­بندی 56

فصل 4- مطالعه موردی و رتبه بندی شاخص سلامت کشورها 59

4-1- شاخص توسعه انسانى.. 61

4-1-1- ضرورت تغییر نگرش در HDI 61

4-2- سلامت: 62

4-2-1- سازمان جهانی بهداشت WHO.. 63

4-2-2- جامعه تحت بررسی.. 64

4-3- داده­های مورد استفاده 64

4-3-1-امید به زندگی.. 64

4-3-2- شاخص مرتبط… 65

4-3-3- نیروی انسانی خدمات دهنده در حوزه سلامت… 69

4-4- تعریف ورودی و خروجی­ها 70

4-5- مدل­های استفاده شده 70

4-6- نتایج حاصل.. 70

جمع بندی 73

فصل 5- نتیجه­گیری و مطالعات آتی… 75

جمع­بندی 75

پیشنهاد ها برای مطالعه آتی.. 76

مراجع 78

منابع فارسی.. 78

منابع انگلیسی.. 78

نمادهای به کار رفته. 82

واژه­نامه انگلیسی به فارسی… 83

واژه­نامه فارسی به انگلیسی… 86

فهرست جداول

جدول ‏2‑1: داده. 26

جدول ‏2‑2: کارایی.. 27

جدول ‏2‑3: با دسترسی ضعیف… 26

جدول ‏2‑4: با دسترسی قوی.. 27

جدول ‏3‑1 مقادیر بهین مدل­های فار. 39

جدول ‏3‑2: نتایج حاصل از مدل­های بخش 3-3-2. 45

جدول ‏3‑3: نتایج حاصل از مدل شعاعی بر حسب انتقال. 48

جدول ‏3‑4: نتایج حاصل از مدل SBM… 51

جدول ‏3‑5: نتایج حاصل از مدل جهتی.. 52

جدول ‏3‑6: نتایج حاصل از مدل ERM… 54

جدول ‏4‑1: امید به زندگی در منطقه. 65

جدول ‏4‑2: داده های شاخص مرتبط.. 68

جدول ‏4‑3: داده­های مربوط به نیروی انسانی خدمات دهنده. 69

جدول ‏4‑4: نتایج حاصل از اجرای مدل­های DEA.. 70

جدول ‏4‑5: نتایج بدست آمده از اجرای مدل­ها 71

جدول ‏4‑6: نتایج حاصل از دسته­بندی.. 73

فهرست اشکال

شکل ‏1‑1: مجموعه امکان تولید. 5

شکل ‏1‑2: اشعه بیکران. 6

شکل ‏1‑3: اصل محدبی.. 6

شکل ‏1‑4: اصل دسترسی آزاد. 7

شکل ‏1‑5: مرز CCR.. 8

شکل ‏1‑6: تابع فاصله ورودی­محور. 14

شکل ‏1‑7: تابع فاصله خروجی­محور. 14

شکل ‏1‑8: شاخص مالم­کوئیست… 17

شکل ‏2‑1: اصل دسترسی­پذیر ضعیف… 22

شکل ‏2‑2: اصل دسترسی­پذیر قوی.. 23

شکل ‏2‑3: مجموعه امکان تولید با اصل دسترسی قوی.. 24

شکل ‏2‑4: مجموعه امکان تولید با اصل دسترسی ضعیف… 25

شکل ‏2‑5: تفاوت دو اصل.. 25

شکل ‏3‑1: مجموعه امکان تولید با دو اصل دسترسی­پذیر. 35

شکل ‏3‑2: نمودار تغییرات خروجی مطلوب به نامطلوب با استفاده از مدل غیرخطی فار. 37

شکل ‏3‑3: مجموعه امکان تولید ساخته شده با مدل شعاعی سیفورد. 47

فصل اول

 

پیش­­نیازها

 

 

فصل 1- پیش­نیازها

بشر از ابتدا به دنبال سود بیشتر در کارهایش بوده و لذا هیچ­گاه به دنبال کم کردن ورودی عملیات خود نبوده است، ولی در گذر زمان سازمان­های مختلف کارهای مشابه­ هم انجام می­دادند، در نتیجه سازمان­ها برای سودآوری بیشتر و ایجاد رفاه در جامعه و همچنین باقی ماندن در فضای رقابت به دنبال کم کردن ورودی­ و افزایش خروجی­ها بودند، با گذشت زمان روش­های اندازه گیری بهره­وری به وجود آمد. در روش­های اولیه با استفاده از نسبت خروجی­ها بر روی ورودی­ها میزان کارایی و بهره­وری را اندازه گیری می کردند (کوپر و همکاران، 2007)، اما در این نوع روش­ها شاخص­های عددی از قبل برای هر ورودی و خروجی در نظر گرفته شده و با استفاده از شاخص­های عددی و روش­های رگرسیون آماری به محاسبه کارایی و بهره­وری می­پرداختند. در ادامه این پیشرفت­ها روش­های جدیدی برای محاسبه دو شاخص کارایی و بهره­وری ابداع شد که یکی از این روش­ها، روش­های تحلیل پوششی داده­ها (DEA)[1] می­باشد. فارل در سال 1957 در نظریه­ای برای اولین بار با استفاده از داده­ها روش ناپارامتریک تحلیل پوششی داده­ها را مطرح کرد، (فارل، 1957) تحلیل پوششی داده­ها با استفاده از اطلاعات واحد تحت بررسی (DMU)[2] و مدل­های ریاضی به محاسبه شاخص­های عددی می­پردازد، سپس با استفاده از همان شاخص­های بدست آمده دو شاخص کارایی و بهره­وری را محاسبه می­نماید و با توجه به ارزیابی امکان برنامه­ریزی را برای ما فراهم می­نماید. در مدل­های DEA هدف کاهش ورودی و افزایش خروجی و در نتیجه افزایش کارایی[3] می­باشد.

1-1- مفهوم بهره­وری[4]

1-1-1- بهره­وری

واژه بهره­وری به معنی باروری و سودمندی و استعداد تولیدی می باشد. اولین بار این واژه در مقاله­ای از کِس نی[5] ‎‎در سال ‎1766‎ استفاده شده است و‎ در سال ‎1833‎ میلادی فردی به نام لیتره[6] بهره وری راقدرت تولیدتعریف كرد(آذری، 1391ه.ش).

به عبارتی، بهره وری یعنی: قدرت تولیدی و باروری و مولد بودن (آذری، 1391ه.ش).

در اوایل قرن بیستم، بهره­وری را نسبت خروجی به یکی از عوامل تولید تعریف نمودند که این تعریف ساختار کاربردی­تری نسبت به تعاریف موجود داشت، در سال ‎1900‎ فردی به نام ارلی بهره وری را ارتباط بین بازده و وسایل بكار رفته ،برای تولید این بازده عنوان كرد. همچنین در ‎1950‎ سازمان همكاری اقتصادی اروپایی (OEEC)[7] ‎ ‎تعریف كامل­تری از بهره وری به این شرح ارائه داد و بهره وری را خارج قسمت بازده، به یكی از عوامل تولید دانست. بدین ترتیب با توجه به این كه بازده سازمان در ارتباط با سرمایه، سرمایه گذاری یا مواد خام و غیره مورد بررسی قرار گیرد؛ می توان از بهره وری سرمایه، بهره وری سرمایه گذاری، بهره وری مواد خام و … استفاده نمود (آذری، 1391ه.ش).

 

1-1- مقدمه …………………………………………………………………………………………………………..

2

1-2- دسته بندی کلی مسائل برنامه ریزی تسهیلات…………………………………………………….

2

1-3- دسته بندی مسائل برنامه ریزی تسهیلات کلاسیک………………………………………………

3

1-4- دسته بندی مسائل مکان یابی با نگرش نوین……………………………………………………….

4

1-5- مکان یابی وسایل سلسله مراتبی………………………………………………………………………..

5

1-6- تقسیم بندی مسائل سلسله مراتبی……………………………………………………………………..

8

1-6-1-تقسیم بندی نارولا…………………………………………………………………………………..

8

1-6-1-1- تسهیلات شامل متوالی…………………………………………………………………..

8

1-6-1-2- تسهیلات انحصار متوالی……………………………………………………………….

8

1-6-1-3- حالات دیگر………………………………………………………………………………..

8

1-6-1-4-شامل محلی………………………………………………………………………………….

9

1-6-1-5- شامل کلی…………………………………………………………………………………….

9

1-6-1-6- منحصر متوالی………………………………………………………………………………

9

1-6-2- تقسیم بندی شاهین، سورال……………………………………………………………………

9

1-6-2-1-الگوی جریان…………………………………………………………………………………

10

1-6-2-2- انواع خدمت…………………………………………………………………………………

10

1-6-2-3- ساختار فضایی……………………………………………………………………………..

11

1-6-2-4- تابع هدف…………………………………………………………………………………….

12

1-7- نواحی قابل کاربرد مکان یابی سلسله مراتبی……………………………………………………….

12

1-7-1- مراکز بهداشتی درمانی…………………………………………………………………………….

12

1-7-2- سیستم های جمع آوری و دفع زباله ………………………………………………………..

12

1-7-3- سیستم های تولید و توزیع……………………………………………………………………..

12

1-7-4- سیسستم های آموزشی……………………………………………………………………………

13

1-7-5- سیستم های خدمات رسانی اضطراری………………………………………………………

13

1-7-6- شبکه های ارتباطی…………………………………………………………………………………

13

فهرست مطالب

 

عنوان

صفحه

فصل دوم: مرور ادبیات و پیشینه تحقیق

 

2-1- مقدمه …………………………………………………………………………………………………………..

15

2-2- فرموله کردن یک مدل میانه عمومی خدمات سلسله مراتبی شامل متوالی……………….

19

2-3- فرموله کردن یک مدل مکان یابی سلسله مراتبی منحصرا متوالی……………………………

21

2-4- مساله مکان یابی بیشترین پوشش سلسله مراتبی………………………………………………….

22

2-5- پوشش حداکثری سلسله مراتبی با پوشش همه ی سطوح تقاضا……………………………

22

 

فصل سوم:مدل ریاضیپیشنهادی و حل آن

 

3-1- مقدمه……………………………………………………………………………………………………………

29

3-2- تعریف مسأله و مدل ریاضی……………………………………………………………………………

30

3-3- مثال عددی……………………………………………………………………………………………………

34

3-4- حل فرابتکاری……………………………………………………………………………………………….

36

3-5- تضاد بین تابع های هدف………………………………………………………………………………..

37

3-6- بهینه سازیچند معیاره……………………………………………………………………………………

37

3-7- ارتباط غالب …………………………………………………………………………………………………

37

3-8- مرز بهینه ……………………………………………………………………………………………………..

38

3-9- الگوریتم بهینه سازی انبوه ذرات(PSO) ………………………………………………………..

39

3-10- پنج قانون میلوناس برای هوش گروهی…………………………………………………………..

39

3-11- اصطلاحات موجود در الگوریتم…………………………………………………………………….

40

3-12- مراحل الگوریتم…………………………………………………………………………………………..

41

3-13- بهینگی پارتو……………………………………………………………………………………………….

42

3-13-1- مفهوم آرشیو پارتو……………………………………………………………………………….

42

3-13-2- بروز رسانی آرشیو جوابهای پارتو………………………………………………………….

43

3-14- نحوه تخصیص تابع برازندگی………………………………………………………………………..

43

3-15- رویکردPSO چندهدفه………………………………………………………………………………

44

3-16- شاخص های مقایسه………………………………………………………………………………….

44

فهرست مطالب

 

عنوان

صفحه

3-16-1- شاخص كیفیت……………………………………………………………………………………

45

3-16-2- شاخص پراكندگی………………………………………………………………………………..

45

3-17- مقدار دهی اولیه و نمایش جواب ها……………………………………………………………..

45

3-18- مراحل تکرار……………………………………………………………………………………………..

48

3-19- شرط توقف……………………………………………………………………………………………….

50

3-20- تئوری مجموعه فازی………………………………………………………………………………….

54

3-21- معرفی مسأله برنامه ریزی خطی فازی……………………………………………………………

56

3-22- مدل فازی………………………………………………………………………………………………….

60

3-23- دیفازی سازی…………………………………………………………………………………………….

60

3-24- مثال عددی برای مدل فازی………………………………………………………………………….

62

 

فصل چهارم: الگوریتم حل مسأله و نتایج محاسباتی

 

4-1- مقدمه……………………………………………………………………………………………………………

65

4-2- حل با استفاده از نرم افزار GAMS …………………………………………………………………….

66

4-3- تنظیم پارامترهای الگوریتم: روش سطح پاسخ (RSM) ……………………………………….

68

4-4- شاخص های اندازه گیری ………………………………………………………………………………

69

4-5- شاخص تعداد جواب های بهینه پارتو(NPS) …………………………………………………….

70

4-6- شاخص زمان حل بر حسب ثانیه (CPU Time) ………………………………………………….

73

 

فصل پنجم : نتیجه گیری و پیشنهادات برای تحقیقات آتی

 

5-1- مقدمه……………………………………………………………………………………………………………

76

5-2- نتیجه گیری……………………………………………………………………………………………………

76

5-3- پیشنهادات تحقیقات آتی…………………………………………………………………………………

77

منابع مآخذ……………………………………………………………………………………………………………..

79

پیوستها……………………………………………………………………………………………………………..

87

 

 

 

فهرست جداول

 

عنوان

صفحه

جدول 1-1 مثال برای سیستم خدمات بهداشتی و درمانی

5

جدول 2-1 مرور کلی بر روی مطالعات انجام شده

24

جدول 2-2 مرور کلی بر توابع هدف و محتوای مطالعات انجام شده

26

جدول 3-1 جدول تقاضای سطوح مختلف گره های تقاضا و تسهیلات موجود

35

جدول 3-2 جدول فواصل گره های تقاضا و تسهیلات موجود از نقاط کاندید

35

جدول 3-3 جدول هزینه ساخت و مطلوبیت تأسیس نقاط کاندید

35

جدول 3-4 جدول مقادیر متغیر ها

36

جدول 3-5 جدول مقادیر فازی تقاضا

62

جدول 4-1 جدول بازه های انتخابی برای تولید اعدادتصادفی هزینه ساخت برای سطوح مختلف

65

جدول 4-2 جدول نتایج از حل مسائل نمونه ای در نرم افزار GAMS

67

جدول 4-3 جدول پارامترها و سطوح آنها در الگوریتم MOPSO پیشنهادی

68

جدول 4-4 جدول پارامترهای تنظیم شده در الگوریتم MOPSO پیشنهادی

69

جدول 4-5 میانگین تعداد جوابهای نامغلوب در الگوریتم MOPSO پیشنهادی

70

جدول 4-6 زمان حل بر حسب ثانیه در نرم افزار GAMSو الگوریتم MOPSO پیشنهادی

73

فهرست شکل ها
عنوان	صفحه
شکل 1- 1 دسته بندی کلی مسائل برنامه تسهیلات	3
شکل 1- 2 دسته بندی مسائل مکان یابی با نگرش نوین	4
شکل 1- 3 یک مثال برای سیستم خدمات بهداشتی	5
شکل 1- 4 شکل مربوط به مثال شعبات پستی	6
شکل 1- 5 شکل مربوط به مثال شبکه راه ها	7
شکل 1- 6 الگوهای جریان	10
شکل 1- 7 انواع خدمت	11
شکل 1- 8 ساختار فضایی	11
شکل 2- 1 استقرار بهینه در یک مثال دو سطحی	21
شکل 3- 1 استقرار گره های تقاضا، تسهیلات موجود و مکان های کاندید	35
شكل 3-2 رابطه فضای جواب و ارتباط غالب	38
شكل 3-3 مراحل الگوریتم انبوه ذرات	42
شکل 3- 4 نحوه نمایش جوابها	46
شکل 3-5 نحوه تخصیص تقاضا به تسهیلات در ماتریس	46
شکل 3-6 کد گشایی الگوریتم حل	48
شکل 3-7 شبه کد حرکت هر ذره	49
شکل 3-8 شبه کد الگوریتم MOPSO پیشنهادی	50
شکل 3-9 فلوچارت الگوریتم MOPSO	51
شکل 3- 10 توزیع فازی مقدار تابع و اهداف فازی که توسط تصمیم گیرنده تأیید می شود	59
شكل 4-1 نمودار میانگین تعداد جوابهای نامغلوب در الگوریتم MOPSO پیشنهادی	71
شكل 4-2 نمودار جبهه پارتو برای مسأله نمونه اول	71
شكل 4-3 نمودار جبهه پارتو برای مسأله نمونه هفتم	71
شكل 4-4 نمودار جبهه پارتو برای مسأله نمونه پانزدهم	72
شكل 4-5 نمودار جبهه پارتو برای مسأله نمونه نوزدهم	72
فهرست شکل ها
عنوان	صفحه
شكل 4-5 نمودار جبهه پارتو برای مسأله نمونه بیست و دوم	72
شكل 4-5 نمودار زمان حل بر حسب ثانیه در نرم افزار GAMSو الگوریتم MOPSO پیشنهادی	74

فصل اول

مقدمه وکلیات تحقیق

1-1- مقدمه

برنامه ریزی تسهیلات که از مباحث مهم مهندسی صنایع است، در دو بخش عمده جایابی و طراحی را شامل می شود که مهمترین بخش طراحی، استقرار یا جانمایی و بخش های دیگر آن، حمل و نقل و طراحی ساختمان و تاسیسات است. منظور از تسهیلات هر مجموعه، شامل کارخانه، دانشگاه، بیمارستان و غیره است. در جایابی، به بررسی محل قرار گرفتن یک وسیله برای رسیدن به اهداف مورد نظر پرداخته می شود که برای تعیین محل آن، معیارهای مهمی مؤثرند. از جمله این معیار ها نزدیکی به جاده های اصلی، بازار مصرف، منابع تأمین مواد اولیه، در دسترس بودن نیروی انسانی مورد نیاز، شرایط محیطی، امکان توسعه، مقررات و قوانین دولتی و غیره است. در طرح استقرار قرار است نحوه قرار گرفتن اجزای یک وسیله برای رسیدن به بهترین بهره وری را تعیین شود. روش های زیادی تا کنون برای حل این گونه مسائل مطرح شده اند که از آن جمله می توان به برنامه ریزی ریاضی، استفاده از تصمیم گیری های چندگانه و غیره اشاره کرد.

یکی از مسائلی که باید در مراحل اولیه طراحی سیستم های صنعتی مورد توجه قرار گیرد، مسأله مکان یابی و استقرار تسهیلات است. مطالعه پیرامون مکان یابی صنعتی از دیدگاه جغرافیدانان و علمای علم اقتصاد همواره دارای اهمیت و اولویت بوده است. مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و … با چنین مسائلی سر و کار دارند. در واقع، تصمیمات مربوط به مکان یابی و استقرار، نه تنها درمسائل صنعتی، بلکه در مسائل گوناگونی در بخش های دولتی و خصوصی، اعم از صنعتی و غیر صنعتی ظاهر می شود. در بخش دولتی، تعیین مکان مراکز خدماتی، نظیر ایستگاه های پلیس راه، اورژانس، بیمارستان ها، ایستگاه های آتش نشانی و غیره، نیاز به اتخاذ چنین تصمیماتی دارد. لذا تصمیم گیری در مورد مکان یابی تسهیلات عمدتا از تصمیم گیری های بلند مدت و استراتژیک شرکت های بزرگ خصوصی و عمومی است و هزینه های بالای مربوط به جایابی و استقرار و راه اندازی تسهیلات، پروژه های مکان یابی را به سرمایه گذاری بلند مدت تبدیل کرده است. لذا موفقیت یا شکست مراکز تسهیلاتی در هرکدام از بخش های دولتی و خصوصی، بستگی کامل به مکان های انتخابی برای آنها دارد. بدین ترتیب، اهمیت مسآله مکان یابی و استقرار تسهیلات و ضرورت پرداختن بدان بر همگان روشن است.

1-2- دسته بندی کلی مسائل برنامه ریزی تسهیلات

مسائل برنامه ریزی تسهیلات را به چهار دسته عمده مکان یابی، تخصیص و طراحی تقسیم می شود با ترکیب این مؤلفه ها مسائل مکان یابی-مسیریابی،مکان یابی-تخصیص به دست می آید. که در شکل (1-1) مشاهده می شود.

تخصیص

مکان یابی- تخصیص تسهیلات

مکان یابی

مکان یابی – مسیریابی تسهیلات

برنامه ریزی تسهیلات مسیریابی

چیدمان تسیهلات

طراحی جابه جایی مواد

طراحی ساختار

شکل 1- 1 دسته بندی کلی مسائل برنامه تسهیلات

1-3- دسته بندی مسائل برنامه ریزی تسهیلات کلاسیک

دسته بندی های کلاسیک مسائل مکان یابی عمدتا بر اساس موارد زیر بوده است:

مسأله مکان یابی تک وسیله/ چند وسیله

براساس خصوصیات وسایل جدید

مسأله مکان یابی با وسایل نقطه ای/ ناحیه ای

مسأله مکان یابی با وسایل ایستا/ پویا

براساس خصوصیات وسایل موجود

مسأله مکان یابی با وسایل با مکان قطعی/ احتمالی

مسأله مکان یابی با ارتباطات برون زا/درون زا

براساس نوع ارتباط وسایل موجود و جدید مسأله مکان یابی با ارتباطات ایستا/ پویا

مسأله مکان یابی با ارتباطات قطعی/ احتمالی

مسأله مکان یابی روی خط/ صفحه

4-2- ساختارمساله. 45

4-2-1- توصیفتابعبرونسپاری.. 49

4-3- مدلریاضیپیشنهادی.. 52

4-3-1- سادهسازیمدلپیشنهادی.. 54

4-4- الگوریتمژنتیک… 57

4-4-1- نمایشکروموزوم. 58

4-4-2- آغازسازی.. 59

4-4-3- ارزیابی.. 60

4-4-4- عملگرانتخاب.. 61

4-4-5- نخبهگرایی.. 62

4-4-6- عملگرتقاطع. 62

4-4-7- عملگرجهش… 68

4-4-8- معیارتوقف… 70

4-5-1- مسائلنمونه. 72

فصلپنجم : نتیجهگیریوپیشنهاداتآتی.. 84

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

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

مراجع.. 87

مراجعفارسی.. 88

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

Abstract 93

فهرست شکل ها

فصل سوم

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

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

 

فصل چهارم

شکل(4- 1).t– امینکروموزومهایصفرویک و . 58

شکل(4- 2).t– امینکروموزومهایعددصحیح و 59

شکل (4- 3). نحوهعملکردعملگرتقاطعنوع 1. 64

شکل (4- 4). فرآیندعملگرتقاطعنوع 2 برایکروموزوممکان . 65

شکل (4- 5). فرآیندعملگرتقاطعنوع 2 برایکروموزومتخصیص . 66

شکل (4- 6). فرآیندعملگرتقاطعنوع 3 برایکروموزوممکان 67

شکل (4- 7). فرآیندعملگرتقاطعنوع 3 برایکروموزومتخصیص . 67

شکل (4- 8). فرآیندعملگرجهشنوع 1 برایکروموزوممکان 68

شکل (4- 9). فرآیندعملگرجهشنوع 1 برایکروموزومتخصیص . 68

شکل (4- 10). فرآیندعملگرجهشنوع 2 برایکروموزوممکان 69

شکل (4- 11). فرآیندعملگرجهشنوع 2 برایکروموزومتخصیص . 69

شکل (4- 12). فرآیندعملگرجهشنوع 3 برایکروموزوممکان 69

شکل (4- 13). فرآیندعملگرجهشنوع 3 برایکروموزومتخصیص . 70

شکل (4- 14). فلوچارتالگوریتمژنتیکپیشنهادی.. 71

 

 

فهرست جداول

جدول (4- 1). مقادیرپارامترهایGA.. 73

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

جدول (4- 3). مقادیرپارامترهای و . 75

جدول (4- 4). مقادیرپارامتر . 75

جدول (4- 5). مقادیرپارامتر 76

جدول (4- 6). مقادیرپارامتر 77

جدول (4- 7). مقادیرپارامتر 78

جدول (4- 8). نتایجبدستآمدهبرایمثالنمونه. 78

جدول (4- 9). نتایجمحاسباتیبرایمسائلاندازهبزرگ.. 81

 

 

3-2-1- فاصله خط مستقیم یااقلیدسی.. 19

3-2-2- فاصله مجذورخط مستقیم یااقلیدسی.. 20

3-2-3- فاصله منهتن یامتعامد. 20

3-2-4- فاصله چبیشف.. 21

3-2-5- كوتاه ترین مسیر. 22

3-3- دسته بندی كلی مسایل برنامه ریزی تسهیلات.. 22

3-4- دسته بندی مسایل مكان یابی بانگرش سنتی.. 23

3-5- دسته بندی مسایل مكا ن یابی بانگرش نوین.. 25

3-6- مسایل مکانیابی میانه باانواع فاصله. 26

3-7- تشریح الگوریتم ژنتیک…. 29

3-7-1- مفاهیم کلیدی الگوریتم ژنتیک… 30

3-7-1-1- كدینگ… 30

3-7-1-2- ایجادجمعیت اولیه. 31

3-7-1-3- عملگرهای الگوریتم ژنتیک… 31

3-7-1-4- تابع برازش… 34

3-7-1-5- استراتژی برخوردبامحدودیتها 34

3-7-2- ساختاركلی الگوریتم ژنتیک… 36

4-1- مقدمه. 39

4-2- ساختارمساله. 40

4-2-1- محاسبه فاصله. 43

4-2-2- مکانیابی چندتسهیله چنددوره ای.. 45

4-2-3-مدل ریاضیپیشنهادی.. 46

4-2-3-1- مثال. 53

4-3- الگوریتم ژنتیک…. 57

4-3-1- نمایش كروموزوم. 57

4-3-2- آغازسازی.. 58

4-3-3- ارزیابی.. 59

4-3-4- معیارتوقف.. 59

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

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

4-3-6-1- عملگرتقاطع نوعI60

4-3-6-2- عملگرتقاطع نوعII62

4-3-7- عملگرجهش… 64

4-3-8- انتخاب.. 65

4-5-1- مسایل نمونه. 67

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

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

مراجع فارسی.. 79

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

فهرست جداول

عنوان

صفحه

فصـل دوم:

فصـل سـوم:

جدول (3- 1). توابع فاصله بکارگرفته شده درمسایل مکانیابی [3]. 28

فصـل چهارم:

جدول (4- 1). اطلاعات تسهیلات موجود. 53

جدول (4- 2). وزن بین تسهیلات جدید. 53

جدول (4- 3). اوزان مابین تسهیلات موجودوجدید. 54

جدول (4- 4). مختصات گذرگاهها 54

جدول (4- 5). ظرفیت گذرگاهها 54

جدول (4- 6). مختصات مکانهای بهینه تسهیلات جدیددرمثال نمونه. 55

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

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

جدول (4- 9). نتایج محاسباتی برای اندازه بزرگ. 71

فهرست شکل­ها

عنوان

صفحه

فصـل سـوم:

شکل (3- 1). فاصله اقلیدسی درصفحه. 20

شکل (3- 2). مسیرهای مختلف متعامدبین و 21

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

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

فصـل چهـارم:

شکل (4- 1). تسهیلات موجودویک مانع خطی بادوگذرگاه. 43

شکل (4- 2).شرایط پدیداری. 44

شکل (4- 3). تقسیم فضای مساله به دونیم صفحه. 47

شکل (4- 4). مکان تسهیلات موجودوتسهیلات جدیددر 2 دوره. 56

شکل (4- 5). فلوچارت الگوریتم ژنتیک… 66

شکل (4- 6).مقدارgapالگوریتم ژنتیک دراندازه های متفاوت.. 72

شکل (4- 7). نمودارمقایسه زمان محاسباتیLingoوالگوریم ژنتیک دراندازه های متفاوت. 74

فصـل اول:
	کلیات تحقیق و ساختار پایان­نامه

1-1- مقدمه

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

در گونه­ای از مسایل میانه با محدودیت در قرار گیری^[7]و یا حركت^[8]مواجه هستیم.در دسته­ای از این نوع مسایل، نواحی وجود دارند كه تسهیل (یا تسهیلات) جدید نه می تواند در آنجا استقرار یابد و نه می تواند از میان آن عبور كند. این نواحی، نواحی با­مانع[9] نامیده می شوند.دریاچه ها، كوهستان­ها، مناطق نظامی، رودخانه ها و بزرگ راه ها ودر مقیاس كوچكتر، ماشین­آلات و واگن­های حمل مواد در كارخانجات، مثال­هایی از این نواحی می باشند.این مسایل در مقایسه با مسایل مكانیابی كلاسیك خیلی عملی­تر ونزدیك تر به دنیای واقعی می باشند، اما به­علت پیچید گی محاسباتی که این نوع مسایل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند. در برخی موارد با موانعی مواجه هستیم که عبور از آنها تنها از طریق چند گذرگاه[10]بر روی مانع خطیامکان پذیر می باشد. مدل پیشنهادی این تحقیق، یک مساله میانه با فواصل متعامد می­باشد، بطوری­که در ناحیه پیوسته یک مانع خطی افقی وجود دارد که بر روی آن تعدادی گذرگاه وجود دارد که ظرفیت هر یک از گذرگاه ها محدود می باشد. فرضیات مساله پیشنهادی بقرار زیر در نظر گرفته می­شوند:

1. با مساله مکان­یابی پیوسته میانه متعامد چند تسهیله با ظرفیت نامحدود برای تسهیلات جدید سرو کار داریم،

1. تعامل هم مابین تسهیلات جدید و جدید، و هم ما بین تسهیلات جدید و موجود برقرار است.

1. تابع فاصله از نوع متعامد می باشد.

1. تنها یک مانع خطی با تعدادی گذرگاه با مختصات های معین، در مدل وجود دارد.

5. مساله مکان­یابی چند دوره ای می­باشد.

1. ظرفیت هر یک از گذرگاه ها در دوره های مختلف محدود می باشد.

7. هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی می­باشد.

7. مانع بر روی یک مسیر افقی قرار دارد.

1. تسهیلات موجود در مسیر مانع مستقر نیستند.

3 – 4 – 2 الگوریتم ژنتیک.. 33

3 – 4 – 2 – 1 مفاهیم کلیدی الگوریتم ژنتیک.. 34

فصل چهارم: ارایهمدل ریاضیو الگوریتمهای پیشنهادی.. 43

4-1 مقدمه.. 44

4 – 2 ساختار مساله.. 45

4 – 2 – 1 محاسبه فاصله انتظاری.. 48

4 – 2 – 1 – 1 پدیداری.. 50

4 – 2 – 1 – 2 اختلاف ناحیههای X و … 51

4 – 2 – 1 – 3 محاسبه فاصله افقی مورد انتظار در حالت . 53

4 – 2 – 1 – 4 محاسبه فاصله افقی مورد انتظار در حالت . 61

4 – 2 – 2 مدل ریاضی مساله.. 94

4 – 3 کران های بالا و پایین مساله مکان یابی با مانع.. 98

4 – 3 – 1 کران های پایین مساله.. 98

4 – 3 – 2 کران های بالای مساله.. 99

4 – 4 الگوریتم حل مساله.. 100

4 – 4 – 1 الگوریتم جستجوی الگوی هوک و جیوز.. 101

4 – 4 – 1 – 1 شروع.. 101

4 – 4 – 1 – 2 جستجوی اکتشافی.. 102

4 – 4 – 1 – 3 معیار توقف.. 102

4 – 4 – 2 الگوریتم ژنتیک.. 102

4 – 4 – 2 – 1 نمایش کروموزوم.. 103

4 – 4 – 2 – 2 شروع.. 103

4 – 4 – 2 – 3 ارزیابی.. 103

4 – 4 – 2 – 4 انتخاب.. 105

4 – 4 – 2 – 5 نخبه گرایی.. 105

4 – 4 – 2 – 6 عملگر تقاطع.. 105

4 – 4 – 2 – 7 عملگر جهش.. 105

4 – 4 – 2 – 8 معیار توقف.. 106

4 – 4 – 3 مثال.. 106

4 – 4 – 4 نتایج محاسباتی.. 108

فصل پنجم: نتیجهگیری و پیشنهادهایی برای پژوهشهای آتی.. 112

5 – 1 نتیجه گیری.. 113

5 – 2 پیشنهادهایی برای پژوهشهای آتی.. 113

فهرست مراجع.. 115

فهرست مراجع فارسی.. 116

فهرست مراجع لاتین.. 117

فهرست جدولها

جدول 4-1 تنظیمات الگوریتم PS. 102

جدول 4-2 مختصات تسهیلات موجود در مثال.. 107

جدول 4-3 اطلاعات جواب برای مثال.. 107

جدول 4-4 خلاصه ای از نتایج محاسباتی برای مسایل با اندازه کوچک 110

جدول 4-5 خلاصه ای از نتایج محاسباتی برای مسایل با اندازه متوسط و بزرگ 111

 

فهرست شکل ها

 

شکل 3-1 مسیرهای متعامد مختلف با طول یکسان بین و 21

شکل 3-2 فاصله اقلیدسی در صفحه.. 22

شکل 3-3 ساختار الگوریتم های جستجوی الگو.. 27

شکل 4-1 فضای مساله.. 46

شکل 4-2 چند مثال برای شیوه محاسبه …………… 48

شکل 4-3 عوامل موثر بر 50

شکل 4-4 افراز فضای شدنی مساله به چهار ناحیه.. 51

شکل 4-5 یک مثال از برای 55

شکل 4-6 یک مثال از برای 56

شکل 4-7 دو مثال از . 57

شکل 4-8 دو مثال از . 58

شکل 4-9 یک مثال از . 60

شکل 4-10 یک مثال از . 60

شکل 4-11 دو مثال از . 63

شکل 4-12 دو مثال از برای 64

شکل4-13 دو مثال از برای 65

شکل 4-14 دو مثال از برای 66

شکل 4-15 دو مثال از برای 67

شکل 4-16 دو مثال از برای 68

شکل 4-17 دو مثال از 69

شکل 4-18 دو مثال از . 71

شکل 4-19 دو مثال از . 72

شکل 4-20 دو مثال از . 73

شکل 4-21 دو مثال از . 74

شکل 4-22 دو مثال از . 75

شکل 4-23 دو مثال از . 76

شکل 4-24 دو مثال از . 77

شکل 4-25 دو مثال از . 78

شکل 4-26 دو مثال از . 79

شکل 4-27 دو مثال از . 80

شکل 4-28 یک مثال از . 82

شکل 4-29 یک مثال از . 85

شکل 4-30 یک مثال از . 87

شکل 4-31 یک مثال از . 89

شکل 4-32 یک مثال از . 91

شکل 4-33 یک مثال از . 92

شکل 4-35 مفروضات برای مثال و جواب بهینه ی آن.. 107

شکل 4-36 تابع هدف برای مثال.. 108

فصل اول

کلیات پژوهش و ساختار پایان نامه

1 – 1 مقدمه

در مدیریت، اقتصاد، برنامه ریزی تولید، طراحی سیستم های صنعتی و غیره، به جوانب مختلفی برمی خوریم که مستلزم تصمیمات مکان یابی هستند. علاوه بر کاربردهای عملی این نظریه در اتخاذ تصمیمات بهینه، نظریه مکان یابی بخش جذاب و چالش برانگیزی از ریاضیات، با مجموعه ای رو به فزونی از مسایل است که الزاما خاستگاهی در دنیای واقعی ندارند.[1]

واژه مکان یابی بر مدلسازی و حل مسایلی اشاره دارد که به دنبال یافتن بهترین مکان برای استقرار مراکز و تسهیلات هستند. به عبارت دیگر، مکان یابی عبارتست از انتخاب جایی برای تسهیلات جدید، بهطوریکه هزینه تولید و توزیع کالا و خدمات کمینه شود.

سال 1909 را اغلب سال تولد نظریه مکان یابی می دانند. آلفرد وبر یکی از نظریهپردازهایی بود که در آن سال به ارایه نظریهای در زمینه مکان یابی و کمینه سازی هزینه ها پرداخت[2]. هزینه هایی که او در نظر گرفته بود، عمدتاً از نوع هزینه های حمل ونقل بودند.

بعدها طیف گسترده ای از انواع مسایل مکان یابی متناسب با اهداف پژوهش و با توجه به شرایط متفاوت موجود در فضای مساله مطرح شدند. چند نوع از مسایلی که در ادبیات مکان یابی پیوسته مطرح شدند عبارتند از مساله میانه[1]، مساله مرکز[2] و مساله مرکز- میانه[3].

در مساله میانه، هدف قرار دادن یک تسهیل جدید در صفحه است بهطوریکه مجموع کل هزینه انتقال بین تسهیل جدید و تسهیلات موجود کمینه شود.

از طرفی تقریبا در همه ی موقعیت های دنیای واقعی با انواع محدودیت ها و الزامها مواجه هستیم. در مدلسازی مکان یابی محدودیت ها میتوانند نواحی ممنوعه[4] باشند، یعنی نواحی ای که قراردادن تسهیلات در آن ها ممنوع، اما حمل و نقل در آن ها آزاد است. پارک ها و سایر مناطق حفاظت شده، یا نواحی ای که ویژگی های جغرافیاییشان، مانند شیب تند، ساخت تسهیلات مطلوب را در آنها ناممکن می کند، مثال هایی از نواحی ممنوعه هستند.

همچنین اغلب نواحی ای وجود دارند که نه تنها قراردادن تسهیل جدید در آنها ممنوع است، بلکه حرکت در آنها هم مستلزم هزینه بیشتری است، مانند دریاچه هایی که با قایق می توان از آنها عبور کرد. این نواحی را نواحی متراکم[5] گویند.

علاوه بر این، در بسیاری مناطق حرکت نیز کاملا ممنوع یا ناممکن است. این مناطق را مانع[6] می نامیم. مناطق نظامی، کوهستان ها، دریاچه ها، رودخانه های بزرگ، بزرگراه ها، یا در مقیاسی کوچکتر، مناطقی که در سطح یک کارخانه با ماشین های حجیم و نقاله های حمل مواد اشغال شده اند، نمونه هایی از موانع هستند. بدون در نظر گرفتن این موانع، نمی توان ادعا کرد که مدلسازی واقع بینانه ای انجام شده است.

مطلب قابل توجه دیگر اینست که مکان قرارگیری موانع میتواند بهصورت تصادفی باشد مانند یک واگن حمل مواد که در هر لحظه ممکن است در هرجایی از مسیرش در فضای کارخانه قرار گرفته باشد. تصادف ها یا ساخت و ساز و تعمیرات برنامه ریزی نشده خیابان های یک شهر که باعث انحراف و تاخیر در شبکه حمل و نقل می شوند، نمونه های دیگری از موانع احتمالی هستند. این حالت در سایر زمینه های پژوهشی، از جمله دانش روباتیک، مورد توجه است، زیرا در طراحی روبات ها لازم است به قابلیت آنها در اجتناب از تصادف با موانعی که احتمال می رود در مسیرشان قرار داشته باشند، اندیشیده شود.

ما در این پایاننامه مفهوم موانع احتمالی در نظریه مکان یابی توجه میکنیم ، و به مدلسازی ریاضی مساله ای می پردازیم که در آن سه مانع خطی احتمالی که مسیر حرکتشان بهصورت افقی است، در صفحه موجودند. در مساله ی مورد بررسی، مفروضات زیر در نظر گرفته شده اند:

• در مساله مکان یابی میانه مورد بررسی ظرفیت تسهیل جدید برای خدمت دهی به تسهیلات موجود نامحدود است.

• در مدلسازی این مساله از متر متعامد برای تعیین فواصل استفاده می شود.

• مساله برای کل افق برنامه ریزی در ابتدای دوره، سیاست گذاری می کند، یعنی مساله مکان یابی ایستا است.

• هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزنی نامنفی است.

• سه مانع با طول محدود در صفحه موجودند که از عرض آنها نسبت به طولشان صرف نظر شده است و بهصورت خط راست مدلسازی می شوند.

• موانع بر روی مسیرهای افقی با مختص y معین قرار دارند.

• مکان شروع موانع از توزیع یکنواخت با پارامترهای معین پیروی می کنند.