Center problem

صفحه 1:
ارلئه كننده: سيما شبيري 84125057 E- mail:simashobeiri@yahoo.co m 

صفحه 2:
۱ ‎bE a}‏ هت ‏افطراري ۳ ‏بیمارستان کتابفانه ‏رت مراکز آتش نشانی تسهیلات خدماتي مدارس مراكز اورزانس دفاتر صدور گذرنامه ‎0 

صفحه 3:
يننا ۲ نقاط تقاضا 100000 ع 0777 شعاع يوشش تابع هدف : حداقل كردن تعداد استقرار روات" )جديد بطوری که تمام نقاط تقاضا پوشش داده شوند. مسائل 0 یا 02۰ يك 0 تقاط تقاضا | بعلاوه ‎yLo} 1‏ ‎Ol aren erates‏ 0 سطع تقاضا در هر ره ‎CSB) SOLELE Seg 210)‏ ا لت تمامى نقاط تقاضا يوشش داده شود و بيشينه شعاع نیز مداقل شود. 210 en on Cnt eet ‏بطوريكه تعداد مناطق تحت يوشش مداكثر شود.‎ پو 

صفحه 4:
9 ‎he‏ ‏3 3 ‎Fer “ee‏ 0 مسائل وزن دمي نشده 

صفحه 5:
۳ هزینه جابجایی یا زمان CALE NU SCL SS WO VAC Renate sy ‏وجود دارد. اما در يك شبكه عمومى اينطور نيست.‎ 

صفحه 6:
ple Le ABCD EF ABCE 

صفحه 7:
Coverage Dis 3 8 0 g z 3 2 ‏ا‎ ‎5 ‎3 ‎a ‎£ Solution to Vertex P-C Coverage Distance 

صفحه 8:


صفحه 9:


صفحه 10:
پارامترهای محل 0 0 4 : تقاضای نقطه بام | ون 0 0 eel xX;= 34 2 ‏در غیر اینصورت‎ 1 17 00 / 

صفحه 11:
MINIMIZE Ww SUBJECT TO: S’Y,=1 7 2-۶ )6( 9 Vij ‏رف‎ ‎ete GY, ۶ ©) (©) 8 1- رغ ¥, =0 Vij ‏ك4‎ 

صفحه 12:
1. یکی از کره ها را به دلفواه انتغاب کنید و فواصل سایر کره ها را نسبت به آن بدست أوريد. 2 دورترين كره را يافته و آن را | بناميد. 3 ا کنید و آن را 26 بنامید. ‎SS tae Ute RRC BBLS ES emit Ral‏ يا استفاده از ماتريس ,ط- 6 

صفحه 13:
مل یک مه 1-جیه در ی انا شبکه درختي 

صفحه 14:
/ wd.) watt nd x 

صفحه 15:
‎by assumption‏ 8 > »تماما ‎a. <8 by assumption ‘2 Bbyeetnilon ‏واه‎ ‏و‎ ‎ 

صفحه 16:
لد مس دی 1. جواب بهينه 1--جدع0) را براى شبكه مورد نظر بيابيد. 2 كمانى را كه جواب بهينه كام قبل روى آن قرار گرفته را مذف کرده (اکر جواب بهینه روى يك كره قرار كرفته. يكى از دو كمانى را كه در مسير »بو 2ج قرار دارد را به دلقواه و 111000 ‏ا‎ TUM CORSON SE 1 UC) Fant Corer mayan U NaS 

صفحه 17:


صفحه 18:
مثال ساده از 1-6767 عنااموطم در شبکه درختي وزن دهي شده 12 0 رس ۳9 هل شبکه ‎3X =2(10- X)‏ 06 3 ie) EE el ‏م‎ ‏نا‎ 

صفحه 19:
بين كره هو 8 ‎ae aT‏ 0 Lory cyst) 0 10X=4(30-X) mp <8.57 ‏جسسسم‎ 2-1 بين كره 698 6X=4(30-X) ‏سوسس‎ X=12 mp 2-0 

صفحه 20:
Cire) racer acre) 3 رش ور وا 2 te CD) 03,201 -(ز ,0 ]بطاح 10,30 hd j) ايك كم (طحق) * 1 0, 28( < ‎a 0058‏ :فاصله مکان استقرار مهس" از گره ۵ 

صفحه 21:
نطو ‎es)‏ < و ‎ ‎828 72 ‎2647 61.75 109.09 145.83 178.09]170.53 93:33 ‎ 

صفحه 22:
ع 8 ۵ 9006 26.67 61.76 109.09 145.83 178.09 17083 93.33 80.98 8128 

صفحه 23:
اام 0م 1 93.33 0.00, ضر # 2 0 178.09 145.83 109.09 89.38 8128 40.00 7467 12000 152.73 180.63. 173.64 0 

صفحه 24:
Prete eve) NC ae a mee 0 +20 ۹ Ba =MAX;(B;) 3 a, E72) (cr) 1۱ 2 ‏ل‎ i] Fa ast B =By . ‏غیر اینصورت اکر‎ « pete aac 2 000 0 (h+h) 

صفحه 25:
000 ‏و‎ a 1 ‏واه‎ yn Fea Cana EEC) D0 ae Pee كام دوم : 5 ‏ا‎ meena) ‏ا اها‎ 25017 D.> Df ost P(D)<P 51: @yla9 05 ORCS Canc RC ede eC Sno Cie eo Cae EL CE od ‏بود.‎ 

صفحه 26:


صفحه 27:
‎e Rial ey‏ یت لت ‎ ‎Min ‏م‎ 2 Oy 51: ‏ردره لم‎ ©) ts ‏لق‎ _ ‏ره‎ 21 @) 3 5 <P. 5 3 0 ‏در غير سرت‎ ‎0 32100 0 ‏در غیر اینصورت 9 

صفحه 28:
| Location of Center ‘Along Unk AB Location Of Contor Along Link AB. 385 GoD jKD 9 ow pyure oayia9s 

صفحه 29:
Location Of Center ‘tong Link AB A Location Of Canter ‘Along Unk AB. 

صفحه 30:
0 نمودارا1-1,...,5 , (إلا,)ا)0 در فاصله [ ذلا, دلا] 

صفحه 31:
aly, v,) =min{d(v, v,)+ 5, d(v, v,) + L- s} =min{P+s5Q+L- s} : در صورتي كه P=dv,v,) , Q=dv,Vv,) i P+t=Q+L- t= ‏خی‎ al 

صفحه 32:
۹0 0۳۹ 29 Ossst O<t<L= dyy)= Q+L-s t<s<L Lst= dy,vy)=P+s O<s<L 

صفحه 33:


صفحه 34:
را 5 با ‎w(Q+L- s)=w(B+s)‏ ‎w(P+s)=w(Q,+L- s)‏ ‎w(Q+L- s)=w(B+s)‏ ‎w(B+s) =w,(Q,+L- s)‏ ظزنا -2 + 140و ME ‏ا‎ 19 ۳۳۱ إلا + الآ 

صفحه 35:
EXAMPLE OF COMPUTING DISTANCE FUNCTION PARAMETERS, ۳۳ fi 494 0 Py 10 1 24 2 

صفحه 36:
در نقطه 3 بهاست۳ مستقر می شود. 

صفحه 37:
2 2 2 2 2 2 1 1 

صفحه 38:
‎cere ad OM RCC 1‏ صنو0 ‎5 Ca Seve e SSS Ro LURE eager eee ‎ ‎et ee ‏ال‎ corek ROL ean NUON ee O ۳ ‏24 با , 1و , 220 ور ان ‎Bigg SWAIY) > By SAY‏ 

صفحه 39:
i 2 

صفحه 40:
as 64 

صفحه 41:
0 1 Make hoReXs\ see} 212-65ع2 1)/6.5>0 -6.5( أنقطه ميانه ‎٠‏ 3.75 سصه 3.5 -*۰ 2 1 نس 7 ‎i 1‏ 3 1 3 1 Pe Oe ORE On ne Gad 6-2 

صفحه 42:
۳ 1)/3.5>0 -3.5( نقطه ميانه : 2.25 ###»ه 3 ,2 حل (72)3) با استفاده ازماتريس ضرايب زير 

صفحه 43:
كاه الال ۳-۰2۰ گام جوم: 3)/3.5>0 -3.5( كام م نقط مين , 325 سه )ل 23 ۳ i i ROC ONC ‏ا‎ CT ا ‎COC‏ ‏می توانید به مقالات زیر رجوع کنید: ات ‎eo nek (Cone)‏ :8 سداس 3-۳ ‎oma) ۱‏ سا (ores & Wohies (IP) 4. 0) Er) 

صفحه 44:
منابع و مأفذ a Ra A ‏ا‎ (Ue leiod) Se ‏الي‎ eee ee UROL (ere) 

Center Problems س يما ش بيري:ارائه ک ننده 84125057 Email:simashobeiri@yahoo.co m خدماتي: ‏Min تابع هدف : يکي از انواع تقسيم بندي هاي تسهيالت اضطراري :تابع هدف : بيمارستان تسهيالت اضطراری مراکز آتش نشانی مراکز اورژانس محل گشت پليس راه ‏MinMax کتابخانه تسهيالت خدماتي مدارس دفاتر صدور گذرنامه مسائل Set Covering نقاط تقاضا داده های مسئله مناطق کانديدای استقرار فواصل يا زمان شعاع پوشش تابع هدف :حداقل کردن تعداد استقرار Facilityجديد بطوری که تمام نقاط تقاضا پوشش داده شوند. مسائل P-Centerيا MinMax داده های مسئله نقاط تقاضا مناطق کانديدای استقرار فواصل يا زمان تعداد )facility (p تابع هدف :استقرار تعداد ثابت pتسهيل جديد بطوريکه تمامی نقاط تقاضا پوشش داده شود و بيشينه شعاع پوشش نيز حداقل شود. مسائل Maximum Covering داده های Set Covering داده های مسئله بعالوه تعداد )facility (p سطح تقاضا در هر گره تابع هدف :استقرار تعداد ثابت pتسهيل جديد بطوريکه تعداد مناطق تحت پوشش حداکثر شود. انواع Problems Center شبکه هاي درختي (فاقد سيکل) مسائل وزن دهي شده مسائل وزن دهي نشده شبکه هاي Cyclic مسائل وزن دهي شده ‏center-1 ‏Absolute مسائل وزن دهي نشده ‏P-center ‏vertex ‏Absolute ‏vertex نمونه اي از شبکه درختي هزينه جابجايی يا زمان نمونه اي از شبکه عمومی :توجه در يک شبکه درختی بين هر دو گره مسير واحدی وجود دارد ،اما در يک شبکه عمومی اينطور نيست. نقطه تقاضا مثال حل مسئله با روش :Covering الزامًا جوابها يکتا نيستند.  برای اين شبکهAbsolute P-Center جوابهای بهينه )P=1,2,3,4,5( 1center 2center 3- cenetr 4- center مقايسه بين جوابهاي بهينه دو روش VertexوAbsolute ‏Vert ex Cent er ‏Absolut e Cent er 2 3 4 5 6 تعداد تسهيالت 1 حداکثر فاصله 16 14 12 10 8 6 4 2 0 5- center پارامترهای مدل ‏dij ‏hi :تقاضای نقطه iام ‏P :تعداد facilityبرای استقرار :فاصله بين نقطه تقاضای iو مکان استقرار facility jام متغير های تصميم اگر facilityدر مکان jام مستقر شود در غير اينصورت 1 0 ‏Xj  ‏Yij :کسری از تقاضای گره iام که بوسيله facilityمستقر شده در نقطه jتأمين می شود. ‏W :حداکثر فاصله بين يک نقطه تقاضا و نزديکترين facilityبه آن Vertex P-Center فرمول بندي مسائل MINIMIZE SUBJECT TO : W j Yij 1 (1) i j Xij P (2) (3) i, j (4) ii  (5) X j 0,1 j (6) Yij 0 i, j (7) Yij  X j i  d dijijY Yijij WW h jj الگوريتم center-1در يک شبکه درختي وزن دهي نشده .1يکی از گره ها را به دلخواه انتخاب کنيد و فواصل ساير گره ها را نسبت به آن بدست آوريد. .2دورترين گره را يافته و آن را e1بناميد. .3دورترين گره از گره e1پيدا کنيد و آن را e2بناميد. .4جواب بهينه مورد نظر در ميانه خط واصل e1و e2قرار دارد. يا استفاده از ماتريس B=bij حل يک مسئله center-1در يک شبکه درختي مکان استقرار استفاده از ماتريس B=bij 3 6 4 2 2 4 1  اثبات بهينگی جواب بدست آمده با اين روش الگوريتم center-2در يک شبکه درختي .1جواب بهينه Center-1را برای شبکه مورد نظر بيابيد. .2کمانی را که جواب بهينه گام قبل روی آن قرار گرفته را حذف کرده (اگر جواب بهينه روی يک گره قرار گرفته ،يکی از دو کمانی را که در مسير e1و e2قرار دارد را به دلخواه حذف کنيد) ،به دو زير شبکه می رسيم. .3حال برای هر قسمت مجددًا مسئله Center-1حل می کنيم که اين جوابها همان جواب مسئله Center-2است. الگوريتم center-2در يک شبکه درختي  در شبکه درختي وزن دهي شدهAbsolute 1-Center مثال ساده از hA 3 10 A hB 2 B حل شبکه: 3X 2(10 X ) hA 3 10 A hB 2 B 4 Z 12 بين گره Aو B ‏Z=90 ‏X=7.5 ‏Z=85.71 ‏X=8.57 ‏Z=120 ‏X=12 )10X=6(20-X بين گره AوC )10X=4(30-X بين گره BوC )6X=4(30-X روش کلی برای يافتن جواب بهينه hi hj X i j hi d(i, X ) hj d( j, X ) d(i, X )  d( X , j) d(i, j) hi d(i, X ) hj [d(i, j)  d(i, X )] hj d(i, j) d(i, X )  (hi  hj ) hi hj d(i, j)  ij  (hi  hj )  st MAX ij ( ij ) S از گرهFacility فاصله مکان استقرار: ht d(s,t) (ht  hs ) مثال hi hj d(i, j)  ij  (hi  hj ) hH 8 d(F, H)  (39) 16.4211 (hF  hH ) 19 F فاصله تا گره اگر هر نقطه تقاضا دارای يک مقداراضافی به عنوان هزينه يا زمان آماده سازی باشد. با هدف حداقل کردن }g( y) Max{h1d( y, v1)  1,..., hmd( y, vm)   m خواهيم داشت : ‏hi hj d(i, j)  hj i  hi j ‏ ij  ) (hi  hj )  st MAX ij ( ij )  st MAXij ( ij اگر،   pآنگاه vp در غير اينصورت اگر   st جواب مسئله Center-1خواهد بود. )  Max( st , p )  p Max( i آنگاه ‏htd(s,t)   t   s ) (h  h :فاصله مکان استقرار Facilityاز گره S الگوريتمي براي حل مسائل Vertex P-Centerدر يک شبکه کلي ‏ ‏ ‏H گام اول Dc (n  1) max ij  dij  :و اگر وزن دهی شده باشد DcH (n 1) max dij   max dij  ‏ i, j ‏ i ‏DcL 0 ‏ (DcL  DcH )  ‏Dc  گام دوم  : 2 ‏ ‏ گام سوم :مسئله Set Coveringبا شعاع پوشش Dcرا حل نماييد * گام چهارم :اگر P (Dc ) Pآنگاه Dc  DcH گام پنجم :اگر بود. در غير اينصورت Dc 1 DcL ‏H ‏L Dc Dcبه گام 2برگرد ،در غير اينصورت متوقف شو Dc ..مقدار بهينه خواهد مراحل اجراي الگوريتم Vertex 2-Center ‏A,E Set Covering مروری بر مدل مسئله Min  Xj S.T : aij  1 0 Xj  1 0 (1)  aij X j 1 (2) X j 0,1 (3) aij 0,1 (4) dijdhiji  D Dcc اگر در غير اينصورت . مستقر شودj در مکانfacility اگر در غير اينصورت  aij X j 1 کوتاهترين مسير بين Aو Bاز Bمی گذرد. کوتاهترين مسير بين Aو Bاز Aمی گذرد. Min(Max) Optimal Location w4d( y, v4 )  g( y) w5d( y, v5) wd( y, v ) 1  1 0  y 6 6  y 8 8  y 14 w4d( y, v4 ) w5d( y, v5) w5d( y, v5) w1d( y, v1) g(6) 18 , g(8) 18 ]v2 ,v3 [ در فاصلهd(x,vi) ، i=1,…,5،xنمودار 6 8 d( y, vi ) min{d(vi , vp )  s, d(vi , vq )  L  s} min{Pi  s,Qi  L  s} Pi d(vi , vp ) , Qi d(vi , vq ) Qi  L  Pi Pi  t Qi  L  t  t  2 در صورتي که: 0 s L t 0  d( y, vi ) Qi  L  s  0 s t  Pi  s  0 t L  d( y, vi )  Qi  L  s t s L   L t  d( y, v ) P  s 0 s  L i i  0  L Q  P  i i ti  2   L Qi  Pi   L  L Qi  Pi L  Pi  s d( y, vi )  Qi  L  s L  Qi  Pi 0 s ti ti s L wi (Pi  s) wi d( y, vi )  wi (Qi  L  s) wj (Pj  s) wj d( y, vj )  wj (Qj  L  s) 0 s ti ti s L 0 s tj t j s  L ti s' tj wi (Qi  L  s' ) wj (Pj  s' ) 0 s' ti , tj s'  L wi (Pi  s ) wj (Qj  L  s ) ti s' L , 0 s' tj wi (Qi  L  s' ) wj (Pj  s' ) ti s' tj wi (Pi  s' ) wj (Qj  L  s' ) tj s' ti wi (Qi  L)  wj Pj s wi  wj ti s' tj wj (Qj  L)  wi Pi s wi  wj tj s' ti ' ' ' ' يا نحوه محاسبه ti حل Vertex Centerيک شبکه عمومی در نقطه facility 3 مستقر می شود. نمونه ای از محاسبات برای يافتن Intersection Points wi (Qi  L)  wj Pj s wi  wj ti s' tj wj (Qj  L)  wi Pi s wi  wj tj s' ti ' ' Case 1 Case 2 قضايای مورد نياز در يافتن جواب بهينه در يک شبکه عمومیAbsolute 1-Center : Vertex and Intersection Point (VIP) قضيه.1 : را به صورت زير تعريف نماييد  pq و ipq : قضيه.2  ipq min wi d(vp , vi ), wi d(vq , vi )  pq max  ipq : i 1,..., m .[قرار نداردvp , vq ] روی کمانAbsolute 1-Center هيچ نقطه، g( yˆ) 18 15 20 ,  23 12 ,  34 24  ipq wi d( y, vi )   pq  g( y) y  [vp , vq ]  pq  g( yˆ) اگر حل Vertex 1-Centerبرای شبکه فوق Absolute حل مسأله به روش Q  q1, q2,..., qp   Q(z)  q1,..., qm  qj j  m&bj z حل Absolute 2-Centerدر يک شبکه عمومی ‏z 1,1.5,2,3,3.5,4,4.5,5,5.5,6,6.5 گام اولz 1, z 6.5 : گام دوم(6.5 1) / 6.5  0 : گام سوم :نقطه ميانه 3.75 : ‏z1  3.5 گام چهارم :حل ) CP(3.5با استفاده از ماتريس ضرايب زير ‏z 1, z 6.5 (6.5 1) / 6.5  0 3.75 ‏z1  3.5 )CP(3.5 :گام پنجم n1  2و  ( X1)  q12, q17و n1 2و z  3.5 :گام ششم t  2 مرحله دوم : گام گام گام اولz 1, z 3.5 : دوم(3.5 1) / 3.5  0 : سوم :نقطه ميانه 2.25 : گام چهارم :حل )CP(3 با استفاده از ماتريس ضرايب زير :گام پنجم n2  2و z  3 :گام ششم t  3 ‏z2  3 3.5 مرحله سوم : گام اول: گام دوم: گام 3 ‏z 3, z 3.5 (3.5 3) / 3.5  0 سوم :نقطه ميانه 3.25 : ‏z 1,1.5,2,3,3.5,4,4.5,5,5.5,6,6.5 .استقرار بهينه در q17و q12 با تابع هدف برابر 3.5می باشد در کتاب ) Daskin(1995به گونه ديگری اين الگوريتم ارائه شده است .برای مشاهده مراحل الگوريتم می توانيد به مقاالت زير رجوع کنيد: 2. Handler(1990).1 )Mirchandani & Handler (1979 مقاالت مرتبط ديگر : 2. Garfikel & Neebe & Rao(1977) .1 4. Martinich(1988).3 )Minieka(1970 )Kariv & Hakimi (1979 منابع و مآخذ 1. Network and Discrete Location ; Mark S. Daskin(1995) 2. Facility Layout and Location ; Richard L. Francis & John A.White (1974)