استاد راهنما: دکتر ایرج مهدوی
استاد مشاور: مهندس صابر شیری پور
 
فصل تابستان 1391
برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

فهرست رئوس مطالب
فصل اول- مقدمه و کلیات تحقیق

مقدمه ………………………………………………………………………………………………………………. 10
کلیات تحقیق و ساختار پایان نامه ………………………………………………………………………….13
فصل دوم- ادبیات و پیشینه تحقیق

مقدمه ………………………………………………………………………………………………………………. 15
ادبیات موضوعی …………………………………………………………………………………………………16
پیشینه تحقیقات انجام شده ………………………………………………………………………………….17
2-3-1 روند تحقیقات انجام شده ……………………………………………………………………………………21

فصل سوم- روش تحقیق

مقدمه …………………………………………………………………………………………………………… 25
فواصل در مسائل برنامه ریزی تسهیلات …………………………………………………………… 26فاصله خط مستقیم یا اقلیدسی …………………………………………………………………………. 26
فاصله مجذور خط مستقیم یا اقلیدسی ……………………………………………………………… 27
فاصله منهتن یا متعامد ……………………………………………………………………………………. 28
فاصله چبیشف …………………………………………………………………………………………….. 29
کوتاهترین مسیر …………………………………………………………………………………………… 30
مسائل مکانیابی میانه با انواع فاصله ………………………………………………………………… 31
فرآیند تحقیق ………………………………………………………………………………………………. 34تعریف ساده ای از مساله ……………………………………………………………………………… 34
وضعیت دو نقطه نسبت به هم در حضور مانع ………………………………………………… 35
کوتاهترین فاصله بین دو نقطه در حضور مانع ………………………………………………… 38مانع به صورت ثابت …………………………………………………………………………….. 38
مانع به صورت متحرک …………………………………………………………………………. 40
فصل چهارم- محاسبات و یافته های تحقیق

مقدمه …………………………………………………………………………………………………….. 44
محاسبه امید فاصله بین دو نقطه در حالت shadow ……………………………………. 45
محاسبه امید فاصله بین دو نقطه در حضور مانع احتمالی در حالت کلی …………. 48
متغییر های واسط ……………………………………………………………………………………. 51
مدل ریاضی مسئله ………………………………………………………………………………….. 54
محدوده امید فاصله بین دو نقطه در مدل …………………………………………………… 55
وارد نمودن انتگرال به لینگو ……………………………………………………………………. 57
الگوریتم ژنتیک ……………………………………………………………………………………… 59تعریف الگوریتم ژنتیک …………………………………………………………………….. 59
مزایا و برتریهای الگوریتم ژنتیک ……………………………………………………….. 61
معایب الگوریتم ژنتیک …………………………………………………………………….. 64
گذری بر ژنتیک طبیعی …………………………………………………………………….. 65
واژگان الگوریتم ژنتیک …………………………………………………………………….. 70
ساختار کلی الگوریتم ژنتیک ……………………………………………………………… 71
کروموزوم ……………………………………………………………………………………….. 73
ایجاد جمعیت اولیه …………………………………………………………………………… 75
اعمال ژنتیک ……………………………………………………………………………………. 76عملگر جهشی …………………………………………………………………………… 77
عملگر تقاطعی ……………………………………………………………………………79
انتخاب چرخه رولت ……………………………………………………………………….. 81
استراتژی برخورد با محدودیت ها …………………………………………………….. 82
مثال ………………………………………………………………………………………………….. 83
فصل پنجم- نتیجه گیری و پیشنهادات

نتیجه گیری …………………………………………………………………………………………. 87
پیشنهادات آتی …………………………………………………………………………………….. 88
پیوست – فهرست منابع و مواخذ ………………………………………………………………………. 89

چکیده انگلیسی ……………………………………………………………………………………………….. 91

فهرست جداول
جدول 1-1 روند تحقیقات علمی و مقالات انجام شده در زمینه مکانیابی در حضور مانع …….21

جدول 4-1 مختصات تسهیلات موجود …………………………………………………………. 83

جدول 4-2 وزن بین تسهیلات موجود با جدید ………………………………………………..83

جدول 3-4 وزن بین تسهیلات جدید با جدید …………………………………………………83

جدول 4-4 داده های مانع خطی ………………………………………………………………….. 83

جدول 4-5 مقایسه نتایج الگوریتم ژنتیک ……………………………………………………… 84

جدول 4-6 نتیجه حل مثال …………………………………………………………………………. 84

فهرست تصاویر و نمودارها
شکل 3-1 فاصله اقلیدسی در صفحه ……………………………………………………………….26

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

شکل 3-3 وضعیت های مختلف دو نقطه نسبت به هم در حضور مانع خطی ………36

شکل 3-4 فاصله بین دو نقطه در حالت shadow …………………………………………… 39

شکل 3-5 تابع فاصله در حضور مانع خطی در حالت xj  > xi …………………………. 42

شکل 3-6 تابع فاصله در حضور مانع خطی در حالت xj  < xi …………………………. 42

شکل 4-1 دو نقطه در حالت shadow …………………………………………………………… 47

شکل 4-2 مدل تئوری داروین ……………………………………………………………………… 71

شکل 4-3 ساختار کروموزوم ……………………………………………………………………….. 76

شکل 4-4 عملگر Mutation …………………………………………………………………………..81

شکل 4-5 عملگر Crossover …………………………………………………………………………82

شکل 4-6 مکان استقرار تسهیلات مثال 4-9 ………………………………………………….. 87

فصل اول – مقدمه و کلیات تحقیق

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

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

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

فرضیاتی که برای مسئله تعریف می نماییم به قرار زیر می باشد:

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