پژوهنده (مجله پژوهشي دانشگاه علوم پزشك ي شهيد بهشتي) تاريخ دريافت مقاله: 9/11/87 سال چهاردهم، شماره 4، پي در پي 70، صفحات 191 تا 198 تاريخ پذيرش مقاله: 21/5/88 مهر و آبان 1388

طراحي مدلي استوار براي مكانيابي واحدهاي خدمات بيمارستاني و كارايي آنها
محمد جواد فيضاللهي1، اميرحسين شكوهي2*، محمد مدرس يزدي3، محمد جعفر تارخ4

دانشجوي دكتراي مهندسي صنايع، دانشگاه صنعتي شريف
كارشناس ارشد مهندسي صنايع، دانشگاه صنعتي خواجه نصيرالدين طوسي
استاد، دانشكده صنايع، دانشگاه صنعتي شريف
-9904225050

دانشيار، دانشكده صنايع، دانشگاه صنعتي خواجه نصيرالدين طوسي چكيده
سابقه و هدف: مساله چيدمان واحدها در محلهاي مختلف بيمارستانها به منظور كاهش هزينههاي ناشي از جابهجايي افراد، بيمـاران وتسهيلات موجب تلاشهاي بسياري از سوي محققان براي ساخت مدلهاي بهينه سازي چيدمان واحدها با هدف كاه ش هزينـه هـا شـدهاست. اين در حالي است كه عدم قطعيت موجود در دنياي پيرامون يا در نتايج حاصل از اين تلاشها ديده نميشود و يا به علـت اعمـالاين محدوديت، مدلهاي غيرخطي پيچيدهاي شكل گرفتهاند كه قابل اعمال به مسايل بهينهسازي نمي باشند. لذا هدف از ايـن تحقيـقارائه طراحي مدل مكانيابي استوار در برابر دادههاي غيرقطعي است كه داراي كارايي قابل قبولي باشد.
مواد و روش ها: طراحي اين مدل به روش اكتشافي و با كمك توسعه مدلهاي رياضي با نگرش بهينهسازي استوار صورت گرفـت و بـرمبناي سه شاخص مسافت، جريان و ارزش جريانهاي بين واحدهاي بيمارستاني بنا نهاده شد و در راسـتاي كمينـه كـردن هزينـههـايناشي از اين سه شاخص گام بر ميدارد.
يافته ها: مدل طراحي شده قابليت پيادهسازي در يك واحد بيمارستاني را داراست و توانايي مواجه به عدم قطعيت موجود در اين گونـهتصميمگيريها را دارد. علاوه بر اين دو مهم، پيچيدگي مدل توسعه داده شده نسبت به مدل اوليه در حد قابل قبولي است و امكان بـهكارگيري آن با تمامي روشهاي حل ابتكاري امكانپذير است.
1268731734566

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

نتيجهگيري: به نظر ميرسد مدل استوار طراحي شده براي مكانيابي واحدهاي بيمارستاني عملي است و با توجه به اهميت آن، تجربه واقعي آن در يك بيمارستان توصيه ميشود.
واژگان كليدي: چيدمان واحدها، تصميمگيري، مساله تخصيص درجه دو، بهينهسازي استوار.
3269955834

مقدمه1
يكي از مسائل مديريتي مهـم در طراحـي همـه سيـستمهـايتوليدي و خدماتي از جمله بيمارستانها، مكـانيـابي واحـدهايداخلي آنها است (2،1). اين مشكل كه بـه نـوعي يـك مـسالهبهينهسازي است در تمامي مجموعههاي صنعتي، كـشاورزي وپزشكي به گونههاي مختلف وجود دارد و محققان بـيش از 40 سال است كه براي حل آن مدلهاي زيادي طراحي كردهانـد وراه حل هاي مختلفي براي آن ارائه داده اند (2). در حال حاضـراين مهم در بيمارستانها بر اساس نظر، سليقه و تجربه مـديرانانجام مي گيرد و اگر به صورت صحيح و بهينـه انتخـاب نـشود

*نويسنده مسئول مكاتبات: اميرحسين شكوهي؛ تهران، دانشگاه صنعتي خواجـهنصيرالدين طوسي، دانشكده مهندسي صنايع.
[email protected] :پست الكترونيك
تبعاتي نظير هزينههاي پنهـان جابـهجـايي، اسـتفاده كمتـر ازتجهيزات بيمارستاني، سرمايهگذاريهاي كاذب و حتي به خطر افتادن جان بيماران را به همراه خواهد داشت (3).
در دو دهه گذشته تحقيقات زيادي براي طراحي بهينـه مراكـزدرماني، بيمارستانها و كيلينيكها صورت گرفتـه اسـت (5،4).
برخي از محققان به بررسي مفاهيم و كليات برنامهريزي منـابعبيمارستاني از ديـدگاه مـديريت عمليـات پرداختـهانـد (7،6).
برخي پژوهشگران نيز بيمارستان و منابع آن را به عنـوان يـكسيستم صف پيچيده در نظر گرفتهاند و از رويكرد شبيهسـازيگسسته پيشامد به طراحي، تخصيص منابع، چيدمان و تحليـلآن پرداخته اند (8). پپونيس و زيمرينگ در مقاله خود طراحـيچيدمان بيمارستان را مورد توجه قرار دادهاند (9).
بدينسان يكي از اولويتهاي پژوهشي ايـن اسـت كـه بـه واقـعمكانيابي واحدهاي بيمارستاني چگونه انجام ميگيرد؟ يكي ازكاملترين مدل هاي رياضي مكانيابي واحدها، مـدل تخـصيصدرجهي دو (QAP) است كه اولين بار توسط فرانـسيس ارائـهشد و به عنـوان مـدل پايـه در بـسياري از تحقيقـات طراحـيچيـدمان مـورد اسـتفاده قـرار گرفـت (2). الـشافعي از مـدل تخصيص درجه دو بـراي طراحـي چيـدمان بيمارسـتان بهـرهجست (10). اما در مورد واحدهاي خدماتي بيمارسـتاني يـكخلا اطلاعاتي وجود دارد و از طرفي به علت شرايط خاصي كـهبر سيستم هاي بيمارستاني حاكم است مدلهاي موجـود دارايكاستيهايي است . آرگـ وت عـدم قطعيـت در دادههـاي وروديبراي مسا ئل طراحي و مديريتي بيمارستانها را مورد توجه قـرارداده و به نقد مدلهاي قطعي استفاده شده بـراي ايـن مـسائل پرداخته است (11).
با توجه به عدم قطعيت بسيار زياد در جريانهاي مواد، بيماران،تجهيزات و امكانات و غيره در مراكز درمـاني، در ايـن تحقيـق
ب راي طراح ي چي دمان و مك ان ي ابي واح ده اي خ دمات بيمارستاني و كارايي آن يك مدل تخـصيص درجـه دو اسـتوار(RQAP) توسعه داده شده و كارايي آن با شـبيهسـازي مـوردارزيابي قرار گرفته است.

مواد و روش ها
اين تحقيق به روش اكتشافي و بر پايه توسعه مدلهاي بهينهسازي رياضي تخصيص درجه دو بنا نهاده شده است.
شاخصهاي مورد نظر در مدلسازي در برگيرنده جريان بين واحدهاي بيمارستاني، فواصل بين واحدها و وزن يا درجه اهميت هر يك از جريانهاست. هدف بهينهسازي كمينهكردن مجموع حاصلضرب اين سه شاخص است كه در قالب يك مدل تخصيص درجه دو ارائه گرديده است.
به طور كلي خصوصيات مدل QAP به گونهاي است كه توانايي مواجه با فضاي غيرقطعي را ندارد لذا به منظور توسعه اين مدل در راستاي به كارگيري در مكانيابي واحدهاي بيمارستاني، از رويكرد بهينهسازي استوار بهره گرفته ميشود.
با توجه به آن كه مدل QAP در دسته مسائل بهينهسازي گسسته قرار ميگيرد به منظور توسعه آن از دستاوردهاي برتسيمس و سيم استفاده ميشود (22،12).
براي بررسي تجربي مساله RQAP، در حالتيكه ميزان جريان بين واحدهاي مختلف غيرقطعي است، يك بيمارستان با 8 واحد بيمارستاني و 8 محل استقرار را مورد بررسي قرار ميگيرد. محلهاي استقرار به صورت دقيق مشخص بودند و به صورت تصادفي از يك مستطيل به طول 200 و عرض 100 انتخاب ميشوند. از روي اين انتخاب ماتريس فاصله بين محلها بدست ميآيد. مقدار اسمي جريان بين واحدها يك عدد تصادفي در بازه [350 و50] ميباشد، همچنين عدم قطعيت اين جريانها برابر 20% مقدار اسميشان فرض شد. دو مساله الف و ب را با ويژگيهاي فوق ميسازيم.
با توجه به اين كه در اين مساله 8 واحد بيمارستاني فرض
⎛ ⎞8
⎜ ⎟= 28
شده است بنابراين 2⎠⎝ داده غيرقطعي در مساله وجود دارد (جداول 1 و 2). لذا مساله را ميتوان براي درجههاي محافظهكاري (Γ) صحيح مختلف در بازه [28،0] حل كرد. حل مساله فوق براي 0=Γ معادل با در نظر نگرفتن عدم قطعيت در دادهها و حل مساله QAP با مقادير اسمي براي ميزان جريان مواد بين واحدهاي بيمارستاني است.
همچنين حل مساله استوار به ازاي 28=Γ معادل سويستر است كه بسيار محافظهكارانه عمل ميكند (15). براي Γ هاي صحيح مختلف در بازه [15،0] مسايل الف و ب را حل كرده و احتمال كمتر بودن مقدار تابع هدف از مقدار تابع هدف استوار و همچنين درصد افزايش در تابع هدف را به صورت تابعي از Γ در دو حالت الف و ب رسم كرديم. براي بدست آوردن احتمال مذكور، مدل را 10000 بار شبيهسازي كرده و نسبت دفعاتي را كه در آنها جواب بدست آمده از جواب استوار كمتر باشد، بدست آورديم.

جدول 1- ماتريس فاصلهها و جريان در حالت الف ماتريس جريان
8 7 6 5 4 3 2 1
103 297 317 276 137 178 51 0 1
344 106 163 95 53 83 0 51 2
127 94 269 224 312 0 83 178 3
287 285 298 58 0 312 53 137 4
217 185 150 0 58 224 95 276 5
219 291 0 150 298 269 163 317 6
111 0 291 185 285 94 106 297 7
0 111 219 217 287 127 344 103 8
ماتريس فاصلهها
8 7 6 5 4 3 2 1
78 117 33 135 124 93 85 0 1
24 52 88 61 62 65 0 85 2
85 42 73 62 41 0 65 93 3
86 11 110 23 0 41 62 124 4
83 20 126 0 23 62 61 135 5
90 106 0 126 110 73 88 33 6
75 0 106 20 11 42 52 117 7
0 75 90 93 86 85 24 78 8
1268731734566

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

1268731734566

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

جدول 2- ماتريس فاصلهها و جريان در حالت ب ماتريس جريان
286
238 128
240 322 326 187
137 74 164 225
0 0
225 2
3
258 218 79 179 0 164 74 264 4
57 300 324 0 179 137 187 148 5
325 213 0 324 79 326 322 240 6
179 0 213 300 218 240 128 112 7
0 179 325 57 258 238 286 106 8
ماتريس فاصلهها
31 129 118 36 86 152 0 148 2
121 23 99 181 67 0 152 31 3
55 44 69 113 0 67 86 63 4
62 158 129 0 113 181 36 172 5
95 85 0 129 69 99 118 73 6
98 0 85 158 44 23 129 32 7
0 98 95 62 55 121 31 117 8
يافته ها
در اين روش كه تقريبي از بهينهسازي استوار با عدم قطعيت بازهاي است، فرض ميشود:
r%ij = rij +rˆijξij∀i j, , ∑ξij ≤Γ i j,
با اعمال اين روش بر روي مساله QAP مدل زير به دست ميآيد (فرمول A).
RQAPΓ
nnnnnn
min z =∑∑∑∑r d x xijrsirjs + max ∑ ∑∑rˆijd x xrsirjs
1783067-6900

i=1 j= = =1 r 1 s 1 {S S| ⊆J S,≤Γ} (i j, )∈S r= =1 s 1 s t. .
n
∑ xir =1,i =1,K,n
r=1
n
∑ xir =1,r =1,K,n
i=1
xir ={0,1 ,} i =1,K,n r =1,K,nكه اين مدل با مدل زير معادل است (فرمول B):
R Q A P ‘
zr dijr s x ir x jszp ij
i = 1 j = 1 r = 1 s = 1( i , j )∈ J s t. .
n
∑ x ir = 1,i = 1,K , n
r = 1 n
∑ x ir = 1,r = 1,K , n
i = 1
⎛ nnnn⎞ z 0 + p ij ≥ rˆij ⎜ ∑ ∑ d r s x ir x js + ∑ ∑ d r s x is x jr ⎟
⎝ r = 1s = 1r = 1s = 1⎠
p ij ≥ 0( i , j ) ∈ J
x ir = {0 ,1},i = 1,K , nr = 1,K , n

اثبات:
فرض كنيد به ازاي يك Γ و x* داده شده، داشته باشيم
(فرمول C):
nn
β(x*, )Γ = max ∑ ∑∑rˆijd x xrs*ir*js
1636111-4769

{S S| ⊆J S,≤Γ} (i j,)∈Sr= =1 s 1
پر واضح است كه (β(x*،Γ با جواب بهينه زير برابر است
(فرمول D):
*⎛ n n * * ⎞ β(x , Γ =) max ∑ z rij ijˆ ⎜∑∑ d rs x xir js ⎟
(i j,)∈J⎝ r =1s =1⎠
s t. .
(i j∑,)∈J zij ≤ Γ
0 ≤ zij ≤ 1(i j,) ∈ J
دوگان (فرمول D) به صورت زير است (فرمول E):
*⎧⎫ β(x ,Γ =)min ⎨z0Γ+ ∑ pij ⎬
⎩(i j, )∈J⎭
s t. .
⎛ nn**nn** ⎞ z0 + pij ≥ rˆij ⎜∑∑ d x xrsirjs +∑∑ d x xrsisjr ⎟
⎝ r= =1 s 1 r= =1 s 1 ⎠ pij ≥ 0 (i j, )∈ J
از آنجا كه جواب بهينه (فرمول C) با (فرمول D) و آن نيز با (فرمول E) برابر است، بنابراين مساله RQAPΓ به فرم زير در ميآيد (فرمول F).
nnnn⎧⎫ min z = ∑∑∑∑ r d x xijrsirjs + min ⎨z0Γ + ∑ pij ⎬
i=1j=1 r=1 s=1⎩(i j,)∈J⎭ s t. .
n
∑ xir = 1,i = 1,K , n
r =1
n
∑ xir = 1,r = 1,K , n
i=1
⎛ nnnn⎞ z0 + pij ≥ rˆij ⎜∑∑ d x xrsirjs + ∑∑ d x xrsisjr ⎟
⎝ r =1 s=1r =1 s=1⎠
pij ≥ 0(i j,) ∈ J
xir = {0,1 ,}i = 1,K , nr = 1,K , n
و از آن برابري RQAPΓ با RQAP’Γ نتيجه ميشود.
نتايج حاصل از كارايي مدل توسعه داده شده RQAP در مورد اشاره از قرار زير است:
جدول 3- نتايج حاصل از مدل استوار و شبيهسازي مساله QAP مدل الف
درصد افزايش مقدار بهينه احتمال سطح محافظت†
0 660600 0 0
0/014 669886 0 1
0/028 679049 0 2
0/041 687429 0 3
0/053 695541 0/0001 4
0/065 703353 0/0012 5
0/076 710982 0/0229 6
0/086 717346 0/1316 7
0/094 722941 0/3278 8
0/102 728198 0/5738 9
0/110 733390 0/8001 10
0/118 738396 0/9272 11
0/125 743280 0/9797 12
0/132 747954 0/9955 13
0/139 752495 0/9997 14
0/146 756995 1 15

Protection level مدل ب
درصد افزايش مقدار بهينه احتمال سطح محافظت†
0 937978 0 0
0/020 956482 0 1
0/034 970105 0 2
0/048 982806 0 3
0/060 993796 0/0002 4
0/071 1004854 0/0096 5
0/082 1014603 0/0179 6
0/092 1024311 0/1519 7
0/01 1032211 0/291 8
0/109 1040467 0/5624 9
0/114 1044603 0/8338 10
0/12 1050798 0/9338 11
0/131 1060658 0/976 12
0/133 1062826 0/9947 13
0/138 1067097 0/999 14
0/15 1078372 1 15
† Protection level

مشاهده مي شود كه اگر بخواهيم با احتمال بـالاي 99% مقـدارتابع هدف از مقدار تابع هدف اسـتوار كمتـر باشـد، در هـر دوحالت الف و ب كافي است كه 13= Γ باشد . در اين صورت بـهازاي 13= Γ تنها حـدود 13% بـه مقـدار تـابع هـدف افـزوده ميگردد. اين در حالي است كه به ازاي 28= Γ يا همان مـدلبيشمحافظهكار سويستر، 20% افزايش در تابع هدف مـشاهدهميگردد.

شكل 1- احتمال كمتر بودن مقدار تابع هدف از تابع هدف جواب استوار بر حسب سطح حفاظت گاما (Γ)

شكل 2- درصد افزايش در مقدار تابع هدف جواب استوار بر حسب سطح حفاظت گاما (Γ)

بحث
در اين تحقيق نشان داده شد كه مدل استوار تخصيص درجـهدو استوار طراحي شده قابليت پيادهسازي با كـارايي بـالا را درمكانيابي واحدهاي بيمارستاني داراست.
1268731734566Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

الشافعي در تحقيقات خود شرايط حاكم بر بيمارستان را قطعيدر نظر گرفته بود در حالي كه در واقعيت دادههاي مـورد نيـازبراي تصميم گيري غيرقطعـي مـيباشـند (2). لـذا در صـورتبهــرهگيــري از روش الــشافعي، در صــورت تغييــر انــدك در دادههاي پيش فرض، نه تنهـا نتيجـه ارائـه شـده ديگـر بهينـه نميباشد بلكه احتمال موجه نبودن آن بسيار زياد است زيرا بهمحض اينكه داده ها، مقاديري غير از مقادير اسمي خود بگيرند، ممكن است چنـدين محـدوديت نقـض شـود و جـواب بهينـهبدست آمده براي مقادير اسمي، ديگر بهينه و يـا حتـي موجـهنباشد. هنگامي كه دادههاي موجود در تابع هدف غيـر قطعـيباشند، با تغيير مقادير اسمي، بهينگي جواب بدست آمده برايمساله اسمي به خطر ميافتد و موقعي كه دادههاي مربوط بـهمحدوديتها قطعي نباشند، نگران موجه بودن جواب به دسـتآمده هستيم.
1268731734566Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

Downloaded from pajoohande.sbmu.ac.ir at 10:11 +0330 on Wednesday January 10th 2018

اين مشاهده به يك سوال طبيعي در طراحي رويكردهايي براييافتن جوابي بهينه كه در مقابـل عـدم قطعيـت دادههـا ايمـناست، منتج ميشود كه ايـن جـوابهـا را “اسـتوار (robust)” مينامند. براي تبيين اهميت استوار بودن جواب در كاربردهاي عملي، از يك مطالعه موردي كه توسط بن-تال و نميروفـسكي (12) ب ر روي ي ك م ساله بهين ه س ازي خط ي از كتابخان ه Net Lib انجام شده است، مطلب زير را نقل ميكنيم:
“در كاربرد هاي عملي برنامهريزي خطي، نميتوان امكان اين راناديده گرفت كه عدم قطعيت ناچيز در دادهها مي تواند جـواببهينه معمولي را از ديدگاه عملي، به طور كامل بي معني كند.” در روش هاي كلاسيك براي در نظر گرفتن عدم قطعيت دادههـااز رويكردهــاي تحليــل حــساسيت و برنامــه ريــزي احتمــالي (stochastic programming) بهره ميگيرند. در رويكرد اول متخصصها و مدلسازها در ابتدا از تاثير عدم قطعيـت دادههـابر روي مدل چشمپوشي كرده و متعاقبا براي صحه گذاشتن برجوابهاي بدست آمده از تحليل حساسيت استفاده ميكنند. اما تحليل حساسيت تنها ابزاري براي تحليل خـوب بـودن جـواباست و نميتوان از آن براي توليد جوابهاي استوار استفاده كرد .
علاوه بر آن انجام تحليل حساسيت توام در مدلهـايي كـه بـهتعداد زيادي داده غيرقطعي دارند، عملي نميباشد.
در اواسط دهـه 1950 دانتزيـگ برنامـهريـزي احتمـالي را بـهعنوان يك رويكرد براي مدل كردن عدم قطعيت دادهها معرفيكرد؛ اين رويكرد سناريوهايي با احتمالات مختلـف را بـراي رخدادن داده ها، فرض ميكرد (13). در اين رويكرد موجـه بـودنيك جواب با استفاده از محدوديتهاي شانس بيان ميشود. سه مشكل اصلي براي اين رويكرد وجود دارد: (الف) شناخت توزيعدقيق داده ها و در نتيجه عددي كردن سناريوهايي كـه از ايـنتوزيــعهــا عــدد مــي گيرنــد، در عمــل دشــوار اســت، (ب) محدوديتهاي شانس ويژگي محدب بودن مساله اصلي را از بينميبرد و بر پيچيدگي آن به مقدار زيادي ميافزايـد ، (ج) ابعـادمدل بهينه سازي بدست آمده به صورت نجومي با زيـاد شـدنتعداد سـناريوها افـزايش مـييابـد، كـه چالـشهاي محاسـباتيعمدهاي را موجب ميگردد.
رويكرد ديگري كه در سالهاي اخير براي مقابله با عدم قطعيتدادهها، بسط داده شده است، بهينهسازي استوار مـيباشـد . در اين رويكرد به دنبال جوابهاي نزديك به بهينهاي هستيم كه بااحتمال بالايي موجه باشند. به عبارت ديگر با كمي صـرف نظـركردن از تابع هدف، موجه بودن جواب بدست آمده را تـضمينميكنيم. البته در مورد عدمقطعيت در ضرايب تـابع هـدف، بـاكمي صرف نظر كردن از مقدار تـابع هـدف بهينـه، بـه دنبـالجوابي هستيم كه با احتمال بالايي جوابهـاي واقعـي بهتـر (در اينجا با توجه به تابع هدف كه كمينه كردن است، كمتر) از آنجواب باشند.
به منظور درك مساله تخصيص درجه دو، يك بيمارسـتان كـهدارايn واحد ميباشد، در نظر بگيريد كه براي آنها n محل ازقبل در پيشبيني شده است و ما ميتوانيم هر يك از واحدهـارا به يكي از اين مكانها تخصيص دهيم و ميزان جريـان بـين دو واحد i وj مقدار rij ميباشـد . فاصـله بـين دو محـلs و r برابر مقدار drs ميباشد. هدف اين است كه يك مدل براي اينمساله بسازيم به طوري كه كل حجم حملونقل بين واحدهايبيمارستاني كمينه شود.
توجه كنيد كه معيـار بهينـهسـازي بـا حاصلـضرب دو متغيـرتصميم مرتبط ميباشد و بنـابراين ، داراي فـرم كودراتيـك يـادرجه دو اسـت. همچنـين ايـن نكتـه قابـل توجـه اسـت كـهمحدوديتها همـان محـدوديتهاي مـساله كلاسـيك تخـصيصاست. بنابراين، اين مساله را مساله تخصيص درجه دو (QAP) مينامند.
QAP يك مدل كلاسيك در بهينهسازي گسسته است كه يكمدل مناسب براي خيلي از مسائل دنياي واقعي است. از جملهكاربردهـ اي آن در تعيـ ين محـ ل واحـ دهاي مختلـ ف دربيمارستانها است.
در حدود سال 1960 تلاشهاي تحقيقاتي زيادي براي حل ايـنمسائل با الگوريتمهاي بهينه سازي انجام شده است. اما با وجوداين همـه تـلاش هنـوز مـسالهQAP بـا بيـشتر از 15 تـا 20 تسهيل از لحاظ محاسباتي مهارناپذير است. مسالهQAP جزءآن دسته از مسائل بهينهسازي گسسته اسـت كـه بـه راحتـيفهميده مي شود و انتظار ميرود به سادگي حل شـود ولـي درواقعيت چنين نيست و حل آن بسيار دشوار است.
بايد توجه داشت كه مـدل فـوق در صـورتي معتبـر اسـت كـه دادههاي آن به صورت قطعي معلوم باشند. حال در نظر بگيريدكه ميزان جريان بين واحدهايr%ij مختلف غيرقطعي باشد؛ دراين صورت اعتبار كل مدل زير سوال ميرود. براي رويارويي بـااين عدم قطعيت از بهينهسازي استوار استفاده ميكنيم.
فرض كنيد بدانيم كه ميزان جريان بـين واحـدهـا متغيرهـاي
تصادفي مستقلr%ij هستند كـه در بـازه ⎦⎤r rij , ij +rˆij ⎣⎡ يـكتوزيع متقارن دارند. J مجموعه(i,j) هايي است كهr%ij بـرايآنها غيرقطعي ميباشد.
r%ij = rij +rˆijξ ξij ,0 ≤ ij ≤1∀i j, , ∑ξij ≤Γ
i j,
كه در آنξij يك متغير تصادفي بين صفر و يـك اسـت كـهنوسان در دادهها را نشان ميدهد. به اين حالت كه در آن همهعناصر بردار نوسان ξ ميتوانند در بازه [1،0] تغيير كنند.
در بهينه سازي استوار براي مساله تخصيص درجـه دو بـا عـدمقطعيت فوق به دنبال يافتن جوابي بوديم كه مقدار تابع هـدف
آن به ازاي همه مقادير ممكنr%ij ، كمتر از آن باشد. به عبارتديگر بـه دنبـال كمينـه كـردن بيـشترين مقـدار تـابع هـدف ميباشيم.
يكي از اين روشها، روش بهينهسازي استوار براي برنامـهريـزيخطي توس ط سويستر براي بار بود كه براي اول بار ارائه شد كهدر اين روش به بهينهسازي بد تـرين حالـت مـيپـردازيم، ايـنروش به شدت محافظهكارانه عمل ميكند (15).
طبق اين روش فرض ميشود كه براي همه دادههاي غيرقطعيبـدترين حالـت مـيتوانـد رخ دهـد. بـه عبـارت ديگـر همـه متغيرهايξij مي توانند بدون هيچ محـدوديتي در بـازه [0،1] تغيير كنند . از آنجا كه در بهينهسازي استوار، بدترين حالـت راميخواهيم بهينه كنيم، ميـزان جريـان بـين واحـدهـايi وj برابر (rij +rˆij ) گرفته و مساله QAP را حل ميكنيم.
اين رو ش كه محافظـهكارانـه تـرين روش بهينـهسـازي اسـتوار اســت، بــسيار ســاده بــوده و الگــوريتم هــاي فراابتكــاري (Meta heuristic) براي حل مساله QAP را مـي تـوان بـرايحل آن اسـتفاده كـرد؛ ولـي چـون بـدترين حالـت را در نظـر ميگيرد، به ميزان زيادي از مقدار تابع هدف كم ميكند لذا بهطوري كلي مطلوب نميباشد.
براي مقابله با عيب روش سويستر كه به شدت محافظـهكارانـهعمل مي كند، تلاشهاي زيادي صورت گرفته اسـت . بـن-تـال ونميروفـــسكي (17،16،12) و ال- قـــاوي (19،18) هركـــدام شيوههايي براي مقابله با ايـن امـر ارائـ ه كردنـد. امـا روشـهايپيشنهادي آنها خود داراي معايبي بود كه باعث سختتر شدنمساله استوار و عدم قابليت اعمال بر روي مسايل بهينـهسـازيبا متغيرهاي گسسته ميشد.
به طور خاص براي مسايل بهينهسازي گسسته، كووليس و يـو(20) يك چارچوب بهينهسازي گسسته استوار ارايه كـردهانـدكه به دنبال يافتن جوابي است كه عملكرد بدترين وضـعيت راتحـت مجموعـهاي از سـناريوهـا بـراي دادههـا كمينـه كنـد. متاسفانه تحت رويكرد آنها، همتاي استوار بـسياري از مـسائل بهينهسازي گسسته قابل حل در زمان چند جملهاي به مسايلNP-hard تبديل ميشوند. برتـسيمس و سـيم (22،12) يـكروش بهينه سازي استوار براي مسائل برنامه ريـزي خطـي ارايـهكردهاند كه ميزان محافظهكـاري آن قابـل تنظـيم اسـت و بـردرجه سـختي مـساله نمـيافزايـد . يكـي از مزايـاي ايـن روشقابليــــــــت اعمــــــــال آن بــــــــر روي مــــــــسايل بهينهسازي گسسته و همچنين بهينهسازي تركيباتي ميباشد.
در اين روش، كه عـدمقطعيـت در آن بودجـهاي اسـت، فـرض ميشود كه حداكثرΓ تا از ضرايب تابع هدف تغيير ميكند. به Γ سطح حفاظت ميگويند و يك عدد صحيح نامنفي كـوچكتر يا مساوي تعداد دادههاي غير قطعي در تابع هدف



قیمت: تومان

دسته بندی : پزشکی

دیدگاهتان را بنویسید