روش تبادل و جانشینی

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

این روش به دنبال تعیین ضرایب ترجیحات تصمیم گیرنده است و نشان می دهد که تصمیم گیرنده به چه میزان هدف Fl  را به یک واحد هدف Fi ترجیح می دهد.

روش تبادل و جانشینی (SWT) شامل دو مرحله اصلی است :

  • توابع تعدیل Trade off Function
    • محاسبه جداگانه جواب ایده ال هریک از اهداف و ایجاد راه حل موثر با حل مدل جدید
  • توابع ارزش ضمیمه Surrogate worth Function
    • تجسس برای انتخاب یک راه حل ارجح ،از بین راه حل های موثری که از مجموعه ای از توابع ارزشی ضمیمه بدست آمده است.

مراحل اجرای روش تبادل و جایگزینی

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

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

 

توابع تعدیل

تحت شرایطی که توابع هدف و محدودیت ها به صورت زیر باشند :

max fi(x)

S.t:  gj(x)≤ 0 ; j= 1,2,…..,m

      xi≥ 0

ابتدا بر اساس محدودیت های موجود و با توجه به هر یک از توابع هدف ، بصورت جداگانه محاسبات را انجام داده و برای هر یک از آنها *f*, x1*, x2 ,…. را تعیین می نمائیم. سپس یکی از اهداف را به دلخواه ، نظیر هدف اول ، انتخاب نموده و سایر هدفها را به صورت محدودیت نشان میدهیم:

Max f1(x)

S.t: fi(x) ≥ εi ; i= 2,…..,k

gj(x)≤ 0 ; j= 1,2,…..,m

xi≥ 0

((در این مثال با توجه به آنکه هدف اول انتخاب شده و سایر اهداف به عنوان محدودیت تلقی گردیده اند ،i مربوط به سایر اهداف از هدف 2 شروع شده است.))

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

εi= fi*(x) – εi* ,  εi*> 0

با بکارگیری تابع دوگان لاگرانژ که بر اساس توابع هدف و محدودیت ها به صورت زیر خواهد بود، می توان مسئله را حل نمود :

L(x,u,λ)=f1(x)+∑λ1i(fi(x)-εi)- ∑ujgj(x)

بطوری که :

i= 2…….k   ,       j=1………m

Uj ≥ 0 , λ1i

 بر طبق قوانین ”کان تاکر“ در نقطه بهینه از تابع مورد نظر باید دو مورد زیر در نظر گرفته شود :

λ1i(fi(x)-εi )= 0

λ1i ≥ 0 ; i=2,3,…..,k

و همچنین بر اساس شرایط کان – تاکر بایستی :

L/∂Xi=0

Uj gj(x) = 0

بدین ترتیب می توان مجموعه ای از راه حلهای موثر را بدست آورد و وارد مرحله دوم شد.

(( در بحث توابع تعدیل λli مشخص کننده ارزش سایه ای برای تابع هدف lام به ازائ هر واحد تغییر در ei می باشد به همین دلیل به عنوان یک محدودیت الزامی حائز اهمیت ست.))


مثال تابع تعدیل

Max:f1(x)=x1.x2

Min:f2(x)= (x1-4)2+x22

S.t:  x1+x2≤ 25  :  g1

X1 , 2 ≥ 0

 بدین ترتیب ابتدا راه حل ایده آل هر یک از توابع هدف را ( در این مسئله دو تابع هدف ) بدست می آوریم. بر این اساس داریم :

F1*= 156.25   //  X1*= X2* = 12/5   F2* = 0       //   X1*= 4  ,    X2* = 0

سپس با انتخاب یکی از اهداف به دلخواه ،مدل جدید را تعیین می کنیم:

Max: f1(x)= x1.x2

S.t: -(x1-4)2-x22 ε2 = -C

x1+x2≤ 25  :  g1

X1 , X2 ≥ 0

توجه نمائید که :

ε2= f2*(x) – ε2*

و چون جواب ایده آل هدف دوم برابر با صفر است، در نتیجه:

0- ε2*=-C          ->     ε2*=C

لاگرانژین مسئله به صورت زیر است :

L= x1.x2 ++ λ12{-(x1-4)2-x22+ C }- u1 {x1+x2– 25}

و همچنین :

L/∂X1=x2– 2λ12 ( x1 – 4) – u1= 0

L/∂X2=X1 2λ12 x2 – u1= 0

U1g1(x)= u1 .( x1+x2– 25)=0

λ1i(fi(x)-εi )= λ12{-(x1-4)2-x22+ C }=0

  • در این مثال u1 .( x1+x2– 25)=0 که یا بایستی u1 برابر با صفر باشد و یا (25-x2+x1) برابر با صفر باشد و با توجه به محدودیت f2(x) ≥ ε2 ، اگر (25-x2+x1) برابر با صفر باشد،شرط مربوط به محدودیت f2(x) ≥ ε2 رعایت نخواهد شد ، بنابراین، در این مثال u1 برابر با صفر می باشد.
  • λ12 بزرگتر از یک می باشد ، پس نتایج به صورت زیر خواهد بود:

λ1i=x2 ÷[ 2(x1-4)] = x1 ÷ 2x2

X2=√x1 (x1 – 4)

(x1-4)2+x22 = C

  • با توجه به محاسبات بالا [(λ1i=x2 ÷[ 2(x1-4)]  ،مقدار X1 بایستی بزرگتر از 4 باشد وگرنه مخرج کسر منفی یا صفر خواهد شد .و بر اساس λ1i= x1 ÷ 2x2 ،  مقدار x2 بایستی بزرگتر از صفر باشد ، وگرنه مخرج کسر صفر خواهد شد و چون λ12  نیز بزرگتر از یک است ، می توان نتیجه گرفت:                    x2>0 , x1>4

بدین ترتیب با جایگذاری موارد مذکور در معادلات بدست آمده می توان جدول زیر را تهیه نمود:

ردیف اول) X2=√X1(x1 – 4) → X1=→ X2 = 2.24     λ1i=x2 ÷[ 2(x1-4)] → 2.24 ÷ [2(5-4)]=1.118  →3.46 ÷[2(6-4 )]=0.866

x1 x2 λ12 f1 f2
52.241.11811.186
63.460.86620.7816
74.580.76432.0629.97
85.650.70745.2047.92
96.70.67160.369.89
107.750.64577.4696
118.770.62796.47125.91
129.80.612117.58160
1310.820.601140.61198

λ12 بدست آمده در جدول بالا نشان دهنده مقدار هدف 2 است که قابل جایگزین با یک واحد هدف 1 می باشد. و یا بطور کلی λli مقدار هدف l است که قابل جایگزین با یک واحد هدف i می باشد ، چرا که اگر مشتق تابع لاگرانژ را نسبت به iε نشان دهیم،خواهیم داشت :

L/∂εi=- λli∂

بجای L ∂ می توان fl(.) ∂ را جایگزین نمود در آن صورت خواهیم داشت :

fl(.)/∂εi=- λli∂

و چون محدودیت0< λ12 وجود دارد ، تحت شرایط  λ1i(fi(x)-εi)=0 ، بایستی fi(x)-εi)=0) باشد .در نتیجه  fi(x)=εi

در fl(.)/∂εi=- λli∂ میتوان fi(.)∂ را جایگزین ∂εi نمود . بنابر این خواهیم داشت :

fl(.)/∂fi(.)=λli∂-

لذا λli مقدار هدف l است که قابل جایگزین با یک واحد هدف i می باشد.


 

تابع ارزشی ضمیمه

در این مرحله باید از ترجیحات تصمیم گیرنده در ارتباط با تعدیل هر یک از اهداف نسبت به یک واحد از هدف دیگر( تحت شرایطی که سایر اهداف ثابت باشند)، مطلع شد و سپس ارجحیت های تصمیم گیرنده را بر روی یک مقیاس رتبه ای مدرج نمود. این مقیاس می تواند از اعدادی بین 10+ و 10- تشکیل شده باشد. بطوری که صفر مرکز بی تفاوتی برای تصمیم گیرنده خواهد بود.ارجحیت های اعلام شده توسط تصمیم گیرنده تابع ارزشی ضمیمه را تشکیل می دهند.

تابع ارزشی ضمیمه تابعی از نرخ تعدیل است که با (Wli) نشان داده می شود بطوری که :

  • اگر تعدیل λli واحد از fl بر یک واحد fi ترجیح داده شود :  Wli>0
  • اگر تعدیل λli واحد از fl بر یک واحد fi ترجیح داده نشود : Wli<0
  • اگر تعدیل λli واحد از fl بر یک واحد fi بی تفاوت باشد :   Wli=0

بدین ترتیب بایستی دامنه بی تفاوتی از تابع ضمیمه ((Wlili)) تعیین گردد. با توجه به مثال ذکر شده ، ارجحیت های تصمیم گیرنده بر روی مقیاس 10 الی 10- را به صورت زیر می توان نشان داد:

x1 x2 λ12 f1 f2 w12
52.241.11811.18610+
63.460.86620.78169+
74.580.76432.0629.977+
85.650.70745.2047.925+
96.70.67160.369.892+
107.750.64577.46960
118.770.62796.47125.911-
129.80.612117.581607-
1310.820.601140.6119810-

بر اساس اطلاعات موجود در جدول و با ملاحظه نمودار ، مشخص است که ارجحیت تصمیم گیرنده به ازائ 77.46 برای هدف اول و با 96 برای هدف دوم و به ازائ لاندای معادل 0.645 در نقطه بی تفاوتی است. (0= w12) یعنی: W12(λ*12=0.645)=0 و راه حل نهایی عبارت است از : X1*=10 X2*=7.75

روش تبادل و جایگزینی چند هدفه

تحت شرایطی که بیش از دو هدف وجود داشته باشد، تمام مراحل ذکر شده را برای سایر اهداف انجام داده و راه حل های مربوط به دامنه بی تفاوتی را تعیین می نمایند. در آن صورت برای تابع هدف مسئله خواهیم داشت :   {F*={f*1 , f*2 , …..f* بطوری که راه حل های بهینه بدست آمده بر اساس : Wli(λli)=0

حال با توجه به موارد بالا باید بتوان از بین راه حل های بدست آمده راه حل موثر را بدست آورد بطوری که با حل مدل بهینه زیر می توان جواب های نهائی را بدست آورد.

Max fl(x)

S.t: fi(x) ≥ f i * (x) ; i= 1,2,…..,k

gj(x)≤ 0 ; j= 1,2,…..,m

xi≥ 0

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

روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی روش تبادل و جانشینی

X
سوالی دارین؟