Center problem
اسلاید 1: Center Problems ارائه کننده: سيما شبيري 84125057 E-mail:simashobeiri@yahoo.com
اسلاید 2: يکي از انواع تقسيم بندي هاي تسهيلاتخدماتي:اضطراري:تابع هدف : تابع هدف : تسهيلات اضطراریتسهيلات خدماتيکتابخانهمدارسدفاتر صدور گذرنامهبيمارستانمراکز آتش نشانیمراکز اورژانسمحل گشت پليس راه
اسلاید 3: داده های Set Coveringبعلاوهتعداد facility (p)سطح تقاضا در هر گرهمسائل Maximum Coveringداده های مسئلهتابع هدف : استقرار تعداد ثابت p تسهيل جديدبطوريکه تعداد مناطق تحت پوشش حداکثر شود.مسائل Set Coveringتابع هدف : حداقل کردن تعداد استقرار Facilityجديد بطوری که تمام نقاط تقاضا پوشش داده شوند.داده های مسئلهنقاط تقاضامناطق کانديدای استقرارفواصل يا زمانشعاع پوششنقاط تقاضامناطق کانديدای استقرارفواصل يا زمانتعداد facility (p)مسائل P-Center يا MinMax داده های مسئلهتابع هدف : استقرار تعداد ثابت pتسهيل جديد بطوريکه تمامی نقاط تقاضا پوشش داده شود و بيشينه شعاع پوشش نيز حداقل شود.
اسلاید 4: انواع Problems Center شبکه هاي درختي (فاقد سيکل)شبکه هاي Cyclicمسائل وزن دهي شدهمسائل وزن دهي نشده مسائل وزن دهي شدهمسائل وزن دهي نشده vertexAbsoluteAbsolute1-centerP-centervertex
اسلاید 5: نمونه اي از شبکه درختينقطه تقاضاهزينه جابجايی يا زماننمونه اي از شبکه عمومیدر يک شبکه درختی بين هر دو گره مسير واحدی وجود دارد، اما در يک شبکه عمومی اينطور نيست.توجه :
اسلاید 6: حل مسئله با روش Covering:مثال الزاماً جوابها يکتا نيستند.
اسلاید 7:
اسلاید 8: 1- center2- center3- cenetr4- centerجوابهای بهينه Absolute P-Center برای اين شبکه(P=1,2,3,4,5)
اسلاید 9: مقايسه بين جوابهاي بهينه دو روش Vertex وAbsolute 5- center
اسلاید 10: پارامترهای مدل: فاصله بين نقطه تقاضای i و مکان استقرار facility jام : تقاضای نقطه iام: تعداد facility برای استقرارمتغير های تصميم 10اگر facilityدر مکان jام مستقر شوددر غير اينصورت: کسری از تقاضای گره i ام که بوسيله facility مستقر شده در نقطه j تأمين می شود.: حداکثر فاصله بين يک نقطه تقاضا و نزديکترين facility به آن
اسلاید 11: فرمول بندي مسائل Vertex P-Center(1)(2)(3)(4)(5)(6)(7)
اسلاید 12: الگوريتم 1-center در يک شبکه درختي وزن دهي نشدهيکی از گره ها را به دلخواه انتخاب کنيد و فواصل ساير گره ها را نسبت به آن بدست آوريد.دورترين گره را يافته و آن را e1 بناميد.دورترين گره از گره e1 پيدا کنيد و آن را e2 بناميد.جواب بهينه مورد نظر در ميانه خط واصل e1 و e2 قرار دارد.يا استفاده از ماتريس B=bij
اسلاید 13: حل يک مسئله 1-center در يک شبکه درختيمکان استقرار
اسلاید 14: استفاده از ماتريس B=bij 4621324
اسلاید 15: اثبات بهينگی جواب بدست آمده با اين روش
اسلاید 16: الگوريتم 2-center در يک شبکه درختي جواب بهينه 1-Center را برای شبکه مورد نظر بيابيد.کمانی را که جواب بهينه گام قبل روی آن قرار گرفته را حذف کرده (اگر جواب بهينه روی يک گره قرار گرفته، يکی از دو کمانی را که در مسير e1و e2 قرار دارد را به دلخواه حذف کنيد)، به دو زير شبکه می رسيم.حال برای هر قسمت مجدداً مسئله 1-Center حل می کنيم که اين جوابها همان جواب مسئله 2-Center است.
اسلاید 17: الگوريتم 2-center در يک شبکه درختي
اسلاید 18: مثال ساده از Absolute 1-Center در شبکه درختي وزن دهي شده حل شبکه :AB1010AB4
اسلاید 19: 10X=6(20-X)X=7.5Z=90بين گره Aو Bبين گره AوC 10X=4(30-X)X=8.57Z=85.71بين گره BوC 6X=4(30-X)X=12Z=120
اسلاید 20: Xijروش کلی برای يافتن جواب بهينه :فاصله مکان استقرار Facility از گره S
اسلاید 21: مثال
اسلاید 22:
اسلاید 23: فاصله تا گره F
اسلاید 24: اگر آنگاه،جواب مسئله 1-Center خواهد بود.اگر هر نقطه تقاضا دارای يک مقداراضافی به عنوان هزينه يا زمان آماده سازی باشد.در غير اينصورت اگر :فاصله مکان استقرار Facility از گره Sآنگاهبا هدف حداقل کردن خواهيم داشت :
اسلاید 25: الگوريتمي براي حل مسائل Vertex P-Center در يک شبکه کليگام دوم :گام سوم : مسئله Set Covering با شعاع پوشش را حل نماييدگام چهارم : اگر آنگاه در غير اينصورتگام پنجم : اگر به گام 2 برگرد، در غير اينصورت متوقف شو.. مقدار بهينه خواهد بود.گام اول : و اگر وزن دهی شده باشد
اسلاید 26: مراحل اجراي الگوريتم Vertex 2-CenterA , E
اسلاید 27: در غير اينصورتاگر1010در غير اينصورتاگر facility در مکان j مستقر شود.مروری بر مدل مسئله Set Covering(1)(2)(3)(4)
اسلاید 28: کوتاهترين مسير بين A و B از B می گذرد.کوتاهترين مسير بين A و Bاز A می گذرد.
اسلاید 29: Optimal LocationMin(Max)
اسلاید 30: نمودارd(x,vi) ، i=1,…,5،x در فاصله [ v2 ,v3]68
اسلاید 31: در صورتي که :
اسلاید 32:
اسلاید 33:
اسلاید 34: يا
اسلاید 35: نحوه محاسبه ti
اسلاید 36: در نقطه 3 facility مستقر می شود.حل Vertex Center يک شبکه عمومی
اسلاید 37: نمونه ای از محاسبات برای يافتن Intersection PointsCase 1Case 2
اسلاید 38: 1. قضيه Vertex and Intersection Point (VIP)قضايای مورد نياز در يافتن جواب بهينه Absolute 1-Center در يک شبکه عمومی :2.قضيه : و را به صورت زير تعريف نماييد :اگر ، هيچ نقطه Absolute 1-Center روی کمان قرار ندارد.
اسلاید 39: حل Vertex 1-Center برای شبکه فوق
اسلاید 40: حل مسأله به روش Absolute
اسلاید 41: گام اول:گام دوم: گام سوم: نقطه ميانه : گام چهارم : حلبا استفاده از ماتريس ضرايب زيرحل Absolute 2-Centerدر يک شبکه عمومیگام پنجم :گام ششم :ووو
اسلاید 42: گام اول:گام دوم: گام سوم: نقطه ميانه : گام چهارم : حلبا استفاده از ماتريس ضرايب زيرگام پنجم :گام ششم :ومرحله دوم :
اسلاید 43: گام اول:گام دوم: گام سوم: نقطه ميانه : استقرار بهينه در و با تابع هدف برابر 3.5 می باشد.3.53مرحله سوم :در کتاب Daskin(1995)به گونه ديگری اين الگوريتم ارائه شده است . برای مشاهده مراحل الگوريتم می توانيد به مقالات زير رجوع کنيد:1.Mirchandani & Handler (1979) 2. Handler(1990) مقالات مرتبط ديگر :1. Minieka(1970) 2. Garfikel & Neebe & Rao(1977)3.Kariv & Hakimi (1979) 4. Martinich(1988)
اسلاید 44: منابع و مآخذNetwork and Discrete Location ; Mark S. Daskin(1995)2. Facility Layout and Location ; Richard L. Francis & John A.White (1974)
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.