فرابگیر

انجام پروژه دانشجویی، کامپیوتر، تحقیق در عملیات و آمار

حوزه فعالیت این سایت آموزش، مشاوره و انجام پروژه های دانشجویی در رشته های کامپیوتر و تحقیق در عملیات می باشد

بنیاد بیماری های نادر ایران

مطالب دسته: تصمیم گیری چند هدفه

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

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

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

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

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

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

 

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

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

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

توابع تعدیل

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

max fi(x)

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

      xi≥ ۰

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

Max f1(x)

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

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

xi≥ ۰

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

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

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

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

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

بطوری که :

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

Uj ≥ ۰ , λ۱i

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

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

λ۱i ≥ ۰ ; 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≤ ۲۵  :  g1

X1 , 2 ≥ ۰

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

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

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

Max: f1(x)= x1.x2

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

x1+x2≤ ۲۵  :  g1

X1 , X2 ≥ ۰

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

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

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

۰- ε۲*=-C          ->     ε۲*=C

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

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

و همچنین :

L/∂X1=x2– 2λ۱۲ ( x1 – ۴) – u1= 0

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

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

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

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

λ۱i=x2 ÷[ ۲(x1-4)] = x1 ÷ ۲x2

X2=√x1 (x1 – ۴)

(x1-4)2+x22 = C

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

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

ردیف اول) X2=√X1(x1 – ۴) → X1=→ X2 = 2.24     λ۱i=x2 ÷[ ۲(x1-4)] → ۲٫۲۴ ÷ [۲(۵-۴)]=۱٫۱۱۸  →۳٫۴۶ ÷[۲(۶-۴ )]=۰٫۸۶۶

x1 x2 λ۱۲ f1 f2
۵ ۲٫۲۴ ۱٫۱۱۸ ۱۱٫۱۸ ۶
۶ ۳٫۴۶ ۰٫۸۶۶ ۲۰٫۷۸ ۱۶
۷ ۴٫۵۸ ۰٫۷۶۴ ۳۲٫۰۶ ۲۹٫۹۷
۸ ۵٫۶۵ ۰٫۷۰۷ ۴۵٫۲۰ ۴۷٫۹۲
۹ ۶٫۷ ۰٫۶۷۱ ۶۰٫۳ ۶۹٫۸۹
۱۰ ۷٫۷۵ ۰٫۶۴۵ ۷۷٫۴۶ ۹۶
۱۱ ۸٫۷۷ ۰٫۶۲۷ ۹۶٫۴۷ ۱۲۵٫۹۱
۱۲ ۹٫۸ ۰٫۶۱۲ ۱۱۷٫۵۸ ۱۶۰
۱۳ ۱۰٫۸۲ ۰٫۶۰۱ ۱۴۰٫۶۱ ۱۹۸

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

L/∂εi=- λli∂

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

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

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

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

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

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


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

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

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

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

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

x1 x2 λ۱۲ f1 f2 w12
۵ ۲٫۲۴ ۱٫۱۱۸ ۱۱٫۱۸ ۶ ۱۰+
۶ ۳٫۴۶ ۰٫۸۶۶ ۲۰٫۷۸ ۱۶ ۹+
۷ ۴٫۵۸ ۰٫۷۶۴ ۳۲٫۰۶ ۲۹٫۹۷ ۷+
۸ ۵٫۶۵ ۰٫۷۰۷ ۴۵٫۲۰ ۴۷٫۹۲ ۵+
۹ ۶٫۷ ۰٫۶۷۱ ۶۰٫۳ ۶۹٫۸۹ ۲+
۱۰ ۷٫۷۵ ۰٫۶۴۵ ۷۷٫۴۶ ۹۶ ۰
۱۱ ۸٫۷۷ ۰٫۶۲۷ ۹۶٫۴۷ ۱۲۵٫۹۱ ۱-
۱۲ ۹٫۸ ۰٫۶۱۲ ۱۱۷٫۵۸ ۱۶۰ ۷-
۱۳ ۱۰٫۸۲ ۰٫۶۰۱ ۱۴۰٫۶۱ ۱۹۸ ۱۰-

بر اساس اطلاعات موجود در جدول و با ملاحظه نمودار ، مشخص است که ارجحیت تصمیم گیرنده به ازائ ۷۷٫۴۶ برای هدف اول و با ۹۶ برای هدف دوم و به ازائ لاندای معادل ۰٫۶۴۵ در نقطه بی تفاوتی است. (۰= w12) یعنی: W12(λ*۱۲=۰٫۶۴۵)=۰ و راه حل نهایی عبارت است از : 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)≤ ۰ ; j= 1,2,…..,m

xi≥ ۰

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

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

ادامه مطلب...

روش گرادیان

روش گرادیان

روش گرادیان در حل مسائل چندهدفه به گفرین (Geoffrion) منتسب است. این روش قادر به حل مسائل بهینه سازی خطی و غیرخطی است به شرطی که خبره بتواند تابع مطلوبیت کلی خود را از اهداف مسئله مشخص نماید.

الگوریتم گرادیان در قالب روش فرانک- ولف مطرح شده است. در روش فرانک- ولف حرکت از یک نقطه شدنی ( Xi ) شروع می شود و از آن جا به منظور دسترسی به یک جهت بهینه حرکت (di) به نقطه جدید (yi) می رسد به طوری که خواهیم داشت: ( di = (yi –  Xسپس باید مقدار بهینه حرکت ( λi) تعیین شود.


مقدار بهینه حرکت و نقطه مقصد

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

بهینه کنید: f (Xi + λi di )

s.to:  λi  ≥ ۰

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

نقطه مقصد مدل گرادیان

نقطه مقصد مدل گرادیان


مدل گرادیان برای حل یک مسئله K هدفه

max: U {f1 (x), f2 (x), …. fk (x)} = U (F)

s.t: x ∈ S   ;   s = {x | gi(x) ≤ ۰ ; i = 1, 2, …, m }

در این مدل توابع (f(x و (g(x به طور عینی معلوم است اما تابع مطلوبیت (U(F به طور ضمنی مد نظر است.

مفروضات استفاده از شرایط فرانک- ولف

  • مجموعه متشکل از محدودیت ها محدب و بسته (مرزدار) باشد
  • (U(F (تابع مطلوبیت توابع هدف) بر روی X مشتق پذیر و مقعر باشد
  • هر یک از توابع هدف مقعر باشد
  • مشتق جزئی تابع مطلوبیت نسبت به تابع هدف اول مثبت باشد که در نتیجه این تابع هدف به عنوان هدف مرجع تلقی می گردد

الگوریتم روش گرادیان

قدم یکم: نقطه شروع xi ∈ S را انتخاب نموده و قرار دهید i=1

قدم دوم: راه حل بهینه yi را به منظور جهت یابی برای حرکت بهبودبخش از مسئله زیر بیابید:

max: ∇x U = (f1 (xi), f2 (xi), …. fk (xi)) .  yi

s.t : yi ∈ S

بخش اساسی تعامل با خبره در همین جا است زیرا (U(F به طور عینی مشخص نیست و نیاز به کمک خبره دارد. فرض بر آن است که خبره قادر است تعدیل بین هر دو هدف از اهداف مسئله را به ازای یک راه حل مشخص برآورد کند. این نرخ حاشیه ای جایگزینی بین اهداف را می توان برای برآورد گرادیان از (U(F به کار برد. اثبات ریاضی این موضوع در ادامه ارائه شده است.

اثبات مدل گرادیان

مدل بهینه سازی با تقسیم بر یک عدد ثابت تغییری نمی کند به این دلیل تابع هدف مذکور را بر (U∂/∂Fi1)   تقسیم می کنیم.

ادامه اثبات مدل گرادیان

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

ادامه اثبات مدل گرادیان

ادامه اثبات مدل گرادیان

حال در ادامه جهت  بدست آوردن اوزان wij باید نرخ حاشیه ای جایگزینی بین اهداف اول و jام را به کمک خبره ارزیابی نمود بدین صورت که تعدیل بی تفاوتی خبره از تغییر بسیار کوچک در هدف اول Δf1 در مقابل تغییر لازم برای هدف jام را جویا شویم. یعنی تغییر در هدف اول به میزان Δf1 با ثابت نگه داشتن بقیه اهداف به استثنای هدف jام چه اندازه از این هدف را جبران خواهد نمود. این برآورد به صورت زیر است:

wij = Δf1/Δfj

قدم سوم: مقدار بهینه λi را از مدل روبرو محاسبه نمائید:

max: U {  F (Xi + λi di ) }

s.to: 0 ≤ λi ≤ ۱

برای انجام این برآورد باید از نظرات خبره استفاده کرد. برای این کار به دو طریق می توان عمل نمود:

  1. رسم نمودار
  2. رسم جدول
نمودار برآورد نظرات خبره

نمودار برآورد نظرات خبره

قدم چهارم: اختتام الگوریتم

از نظر تئوری پایان الگوریتم زمانی است که دو راه حل متوالی با یکدیگر یکسان شوند ولی این ایده آل به ندرت اتفاق می افتد. به همین دلیل نسبتی را به نام نسبت بهبودی تعریف می کنیم که یک معیار عملی برای پایان الگوریتم است:

شرط اختتام الگوریتم گرادیان

شرط اختتام الگوریتم گرادیان

 


مثال روش گرادیان

Max  f1(x)= – x1 – ۲ x2 – ۳ x3

       f2(x) = – x1 – ۲ x2 – x3

       f3(x) = -2×1 – x2 –x3

S . to :

        ۲×۱ + ۵×۲ + ۳ x3 ≥ ۳۰

        x1 + x2 + x3 ≥ ۱۸

        ۱۰×۱ + ۸×۲ + ۴ x3 ≥۴۰

        ۳×۱+۲×۲ ≥۲۰

         x1 , x2 , x3 ≥ ۰

انتقال یکم :

نقطه عملی) :قدم یکم)         x’ ∈ S    ->   x1= (2, 9, 7)   , i=1 ,  ε =۰٫۱۵

مفروضات مسئله:                 F0 = {F1(x1), F2(x1), F3(x1)}   ->  F0 = { (-41, -27, -20)

قدم دوم : (f1 در مقابل  f2)  {(-۴۱-۲۰ )   ,   ( -۲۷ + ۲ )    , ( -۲۰ )} = > w12=-(2/-20) = 0.1

قدم دوم : (f2 در مقابل  f3)  {(-۴۱)  ,   ( -۲۷ + ۲ )    , ( -۲۰- ۱۰ )}= > w13=-(2/-10) = 0.2    ->  w1=(0.1 , 1, 0.2)

 

 

محاسبه Y1, d1 ۰٫۱(-۱  ,  -۲    ,  -۳ ) Y1  +۱( -۱  ,  -۲  ,  -۱) Y1 +  ۰٫۲ ( -۲  , -۱  , -۱ ) Y

Y1={Y11 , Y21 , Y3}

Max: 0.1f1(Y1) + 1f2(Y1)+ 0.2 f3(Y1)

S.to Y1 ∈ S

S  فضای حاصل از محدودیتهای مسئله: Y1 = {0, 0, 10}    d1= = {(0 – ۲), (۰ – ۹),  (۱۰ – ۷)} = {-۲, – ۹, ۳}

 

مشخص نمودن بهینه : قدم سوم 

برای f1  داریم ( محاسبات برای ۰٫۲= λو  ۰٫۴= λو ۰٫۶= λو ۰٫۸= λ و اگر ۱= λ) :

-۱ ( ۲ + .۲ ( -۲ )) -۲ ( ۹ + .۲ ( -۹ ))-۳( ۷ + .۲ ( ۳ )) =-۳۸٫۸

-۱ ( ۲ + .۴ ( -۲ )) -۲ ( ۹ + .۴ ( -۹ ))-۳( ۷ + .۴ ( ۳ )) =- ۳۶٫۷

-۱ ( ۲ + .۶ ( -۲ )) -۲ ( ۹ + .۶ ( -۹ ))-۳( ۷ + .۶ ( ۳ )) =-۳۴٫۴

-۱ ( ۲ + .۸ ( -۲ )) -۲ ( ۹ + .۸ ( -۹ ))-۳( ۷ + .۸ ( ۳ )) =-۳۲٫۱

-۱ ( ۲ + ۱ ( -۲ )) -۲ ( ۹ + ۱ ( -۹ ))-۳( ۷ + ۱ ( ۳ )) =-۳۰

برای f2  داریم:

-۱ ( ۲ + .۲ ( -۲ )) -۲ ( ۹ + .۲ ( -۹ ))- ( ۷ + .۲ ( ۳ )) =-۲۳٫۶

-۱ ( ۲ + .۴ ( -۲ )) -۲ ( ۹ + .۴ ( -۹ ))- ( ۷ + .۴ ( ۳ )) =- ۲۰٫۲

-۱ ( ۲ + .۶ ( -۲ )) -۲ ( ۹ + .۶ ( -۹ ))- ( ۷ + .۶ ( ۳ )) =-۱۶٫۸

-۱ ( ۲ + .۸ ( -۲ )) -۲ ( ۹ + .۸ ( -۹ ))- ( ۷ + .۸ ( ۳ )) =-۱۳٫۴

-۱ ( ۲ + ۱ ( -۲ )) -۲ ( ۹ + ۱ ( -۹ ))- ( ۷ + ۱ ( ۳ )) =-۱۰

و برای f3   داریم :

-۲ ( ۲ + .۲ ( -۲ )) -۱ ( ۹ + .۲ ( -۹ ))- ( ۷ + .۲ ( ۳ )) =-۱۸

-۲ ( ۲ + .۴ ( -۲ )) -۱ ( ۹ + .۴ ( -۹ ))- ( ۷ + .۴ ( ۳ )) =- ۱۶

-۲ ( ۲ + .۶ ( -۲ )) -۱ ( ۹ + .۶ ( -۹ ))- ( ۷ + .۶ ( ۳ )) =-۱۳٫۸

-۲ ( ۲ + .۸ ( -۲ )) -۱ ( ۹ + .۸ ( -۹ ))- ( ۷ + .۸ ( ۳ )) =-۱۲

-۲ ( ۲ + ۱ ( -۲ )) -۱ ( ۹ + ۱ ( -۹ ))- ( ۷ + ۱ ( ۳ )) =-۱۰

۱=λ۱ ۰٫۸=λ۱ ۰٫۶=λ۱ ۰٫۴=λ۱ ۰٫۲=λ۱ ۰=λ۱
-۳۰ -۳۲٫۱ -۳۴٫۴ -۳۶٫۷ -۳۸٫۸ -۴۱ F1
-۱۰ -۱۳٫۴ -۱۶٫۸ -۲۰٫۲ -۲۳٫۶ -۲۷ F2
-۱۰ -۱۲ -۱۳٫۸ -۱۶ -۱۸ -۲۰ F3

در صورتی که ۰٫۴=λ مورد نظر خبره باشد: ( -۳۶٫۷    ,   –  ۲۰٫۲     ,   -۱۶   )

 به منظور انتقال به مرحله دوم باید محاسبه شود :

x2= ( X1 + λ۱ d1)

x2= 2+ 0.4  -۲=۱٫۲

x2= 9+ 0.4  -۹=۵٫۴

x2= 7+ 0.4  ۳=۸٫۲

x2= ( 1.2  ,   ۵٫۴   ,   ۸٫۷۸  ) ->  F ={ (-38.34)  , (  -۲۰٫۷۸  )  ,  ( -۱۶٫۵۸ ) }

قدم چهارم: کلیه گام ها مانند قبل تکرار می شود و مقدار ( -۴۷٫۶۳۶   , -۱۹٫۰۳۲     ,   -۱۷٫۴۲۲   ) = F2  بدست می آید. حال شرط خاتمه بررسی می شود که در صورت تصدیق میزان بهینگی الگوریتم از حرکت باز می ایستد.

شرط اختتام الگوریتم گرادیان

شرط اختتام الگوریتم گرادیان

از ε =۰٫۱۵ کمتر است پس در همین تکرار متوقف می شود.

ادامه مطلب...

روش معیار جامع (LP متریک)

روش معیار جامع (LP متریک)

—در روش معیار جامع بر خلاف روش های قبلی نیازی به اولویت بندی اهداف، وزن دهی، یا تبدیل اهداف به محدودیت نیست. روش معیار جامع، بسته به مورد، مجموع توان اول، دوم، …انحرافات نسبی اهداف از مقدار بهینه شان را حداقل می کند. در این روش، تابع هدف که همواره حداقل نمودن آن مورد توجه است به صورت زیر تعریف می شود:

حداقل سازی تابع هدف

حداقل سازی تابع هدف

ادامه مطلب...

تابع مطلوبیت

تابع مطلوبیت

تابع مطلوبیت

مطلوبیت در معنی ((رضایت خاطری که از مصرف کالاها و خدمات  نصیب مصرف کننده می گردد)). مطلوبیت ابتدا در فلسفه به کار گرفته شد، بنتهام آن را به معنی میل به ایجاد نفع بکار برد و استوارت میل این اصطلاح را در رفتارهای انسانی مطرح کرد بطوری که به مطلوبیت گرایان شهرت یافتند. با انتشار کتاب جونز (۱۸۷۳) نظریه بنتهام وارد اقتصاد شد و همچنین توسط مورگن اشترن (۱۹۹۵) به عنوان وسیله ای برای سنجش نتیجه حاصل از تصمیم به کار گرفته شد.

تعیین میزان مطلوبیت افراد برای کمک به تصمیم گیری در شرایط عدم اطمینان  نیومن و اشترن برای رتبه بندی قرعه ها از مطلوبترین و بدترین نتیجه حاصل از قرعه ها استفاده کردند به عنوان مثال اگر چهار قرعه زیر را با احتمالات مختلف با توجه به نظر (DM) داشته باشیم می توان به ترتیب رتبه بندی کرد:

(L3 <   L4 <   L2 < L1)

تعیین میزان مطلوبیت افراد

تعیین میزان مطلوبیت افراد

تعیین مطلوبیت پولی: مطلوبیت عایدی ri  را به صورت u(ri) نوشته می شود و مقدار pi در دو قرعه زیر بگونه ای تعیین می شود که بین این دو بی تفاوتی حاکم شود.

بیشترین عایدی با مطلوبیت یک و کمترین عایدی با مطلوبیت صفر و برای هر قرعه داریم

(EU=∑PIU(Ri

تعیین مطلوبیت پولی

تعیین مطلوبیت پولی


آکسیوم های مطلوبیت : در جهت ترجیحات شخصی DM

  1. سه گانگی: برای هر دو عایدیr1 و r2 یکی از موارد زیر درست است:DM یا r1 را به  r2 یاr2  را به r1 و یا بی تفاوت به هر دو است.
  2. انتقال پذیری: اگر شخصی r1 را به r2 و r2 را به r3 ترجیح دهد آنگاه r1 را به r3 ترجیح می دهد.
  3. پیوستگی: اگر تصمیم گیرنده r1 را به r2 و r2 را به r3 ترجیح دهد، آنگاه برای بعضی ازP ها (۱> P> 0)L2 ~ L1 است.
  4. استقلال: اگر تصمیم گیرنده بین r1 و r2 بی تفاوت باشد و r3 عایدی دیگری باشد آنگاه برای (۱> P> 0) L2 ~ L1
  5. احتمال نابرابر: اگر نتایج دو قرعهr1  و r2 باشد قرعه ای ترجیح داده می شود که دارای احتمال کسب عایدی بیشتری باشد.

تابع مطلوبیت چند شاخصه

هنگامیکه بیش از یک شاخص در ترجیحات موثر باشد آقایان raiffa&keeney (1976) معروفترین روش عملی برآورد از تابع مطلوبیت را پیشنهاد میدهند. روش آنان بر اساس تجزیه مساله به شاخصهای تشکیل دهنده آن بود و تعیین یک تابع مطلوبیت شرطی برای هر شاخص که این توابع شرطی به وسیله یکی از فرمهای زیر با یکدیگر ترکیب می شوند:

فرم جمع پذیر: (برای استفاده از آن احتیاج به شرط استقلال جمع پذیر داریم)

فرم جمع پذیر

فرم جمع پذیر

فرم حاصلضرب: (برای استفاده از آن احتیاج به شرط استقلال مطلوبیت متقابل داریم)

فرم حاصلضرب

فرم حاصلضرب

فرم ترکیبهای خطی چند گانه: (برای استفاده از آن فقط احتیاج به استقلال مطلوبیت داریم)

فرم ترکیبهای خطی چند گانه

فرم ترکیبهای خطی چند گانه

 به طوری که (uj (rj بین صفر و یک خواهد بود و (UJ (rj  یک تابع مطلوبیت شرطی است چنانچه:

  • Uj (rj0)=0 به ازای ارزشی همچون rj0
  • UJ(r*j)=1 به ازای ارزشی همچون r*j

خواص تابع مطلوبیت چند شاخصه

استقلال ترجیحی: شاخص x1 از شاخص x2 مستقل ترجیحی است اگر ترجیحات برای مقادیر شاخص اول به مقادیر شاخص دوم بستگی نداشته باشد.

استقلال ترجیحی دو به دو: شاخص x1 از شاخص x2 مستقل ترجیحی است اگر ترجیحات برای مقادیر شاخص اول به مقادیر شاخص دوم بستگی نداشته باشد و بر عکس٫ دو شاخص x1 از x2 از سایر شاخصها مستقل ترجیحی است اگر درجه ترجیح پیامدهای در برگیرنده تغییرات مربوط به سطح x1 و x2 به سطحی ثابت از سایر شاخصها بستگی نداشته باشد.

استقلال مطلوبیت: شاخص x1 از شاخص x2 استقلال مطلوبیت دارد اگر ترجیحات برای قرعه ها در میزان متفاوتی از سطح شاخص اول به مقادیر شاخص دوم بستگی نداشته باشد. استقلال مطلوبیت دو به دو: اگر x1 از x2 استقلال مطلوبیت داشته باشد و بالعکس

U(X1,X2)=K1U1(X1)+ K2U2(X2) + K3U1(X1) U2(X2)

استقلال جمع پذیر: شاخصهای X1 ,X2,……Xn مستقل جمع پذیرند اگر درجه ترجیح برای پیشامدهای تصادفی به توزیع های احتمال مشترک آنها وابسته نبوده و تنها به توزیع احتمال حاشیه ای آن بستگی داشته باشد.برای دو شاخص مستقل جمع پذیر داریم:

U(X1,X2)=K1U1(X1)+ K2U2(X2)

استقلال جمع پذیر

استقلال جمع پذیر


گامهای لازم برای تعیین مطلوبیت چندگانه:

  1. بررسی استقلال مطلوبیت دو به دو اگر دارند به گام ۲ اگر نه تعیین مطلوبیت چندگانه
  2. بررسی وضعیت استقلال جمع پذیر.
  3. محاسبه (U1(X1) و (U2(X2
  4. محاسبهK ها
  5. بررسی تابع مطلوبیت تعیین شده از نظر پیش بینی ترجیحات DM.

مثال تئوری تابع مطلوبت

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

Max f1(x) = 0.2 x1 + 0.7 x2

Max f2(x) = x2

s.to

۲×۱ + x2 <= 500

x1 + 2×2 <= 300

x1, x2 >=0

به منظور ارزیابی ترجیهات مدیریت شرکت دو مساله برنامه ریزی خطی زیر از طریق WINQSBحل می گردد:

مساله دوم                                                            مساله اول

Max f1(x) = 0.2 x1 + 0.7 x2                                                     Max f2(x) = x2

s.to                                                                                          s.to

۲×۱ + x2 <= 500                                                                       ۲×۱ + x2 <= 500

x1 + 2×2 <= 300                                                                       x1 + 2×2 <= 300

x1, x2 >=0                                                                                x1, x2 >=0

x1*=0  , x2*=150, z1*=105                                                     x1*=0, x2*=150, z2*=150

بدین ترتیب ملاحظه می گردد:

۰ <= Z1*<= 105

۰<= Z2*<= 150

برای بدست آوردن (U1(z1,z2  مراحل زیر را انجام می دهیم:

تابع مطلوبیت

تابع مطلوبیت


گام اول:بررسی استقلال شاخص های z1  وz2:

فرض می کنیم بازی های زیر برای تصمیم گیرنده دارای ارجحیت یکسان می باشند:

بررسی استقلال شاخص ها

بررسی استقلال شاخص ها

بررسی استقلال دو به دو شاخص ها:

بررسی استقلال دو به دو شاخص ها

بررسی استقلال دو به دو شاخص ها

بدین ترتیب مطلوبیت z1  از z2  مستقل است در صورتی که z2  نسبت به z1  نیز مستقل باشد می توان به گام بعدی رفت.


گام دوم : بررسی استقلال و جمع پذیری شاخص ها

بررسی استقلال و جمع پذیری شاخص ها

بررسی استقلال و جمع پذیری شاخص ها


گام سوم :محاسبه (u (z1  و   (u (z2

ابتدا بازی های بی تفاوتی را با DM  مطرح نموده و برای هر کدام از آن جهت دقت تابع مطلوبیت ۱۰ نقطه در نظر می گیریم.

بازی های بی تفاوتی

بازی های بی تفاوتی

همچنین به طور دلخواه مبدا را بدین صورت در نظر می گیریم: u1(0,0)=0       u1(1,1)=0 

برای  z1 از عدد۸۰  شروع می کنیم که فرضیهDM در بی تفاوتی است

اولویت محاسبه

U(z1)

Z1

۰

۰

۰

۸

۵۰% u( 2 0) + 50% u(0)= 16.6

۱۰

۷

۶۰% u( 40 )+ 40% u(0)=3 3.2

۲۰

۹

۷۰% u( 4 0) +30% u( 2 0)= 48.6

۳۰

۶

۷۰% u( 60 )+ 30% u(0)=5 5.4

۴۰

۲

۶۰%u(105 )+40% u (0)=60

۵۰

۵

۸۰% u( 70 ) +20% u( 50 )= 79.2

۶۰

۳

۶۰% u(1 05 ) + 40% u( 50 )=8 4

۷۰

۴

۹۰%u( 90 )+10%u( 50 )= 91.5

۸۰

۱

۹۵% u(1 05 ) + 5% u (0) = 95

۹۰

۰

۱۰۰

۱۰۵

برای  z2 از عدد ۱۳۵  شروع می کنیم که فرضیه DM در بی تفاوتی است

اولویت محاسبه

U(z2)

Z2

۰

۰

۰

۸

۵۰% u(30) + 50% u(0)=18

۱۵

۷

۶۰% u(60)+ 40% u(0)=35

۳۰

۹

۷۰% u(60) +30% u(30)=46

۴۵

۶

۷۰% u(90)+ 30% u(0)=55

۶۰

۲

۶۰%u(150 )+40% u (0)=60

۷۵

۵

۸۰% u(105) +20% u(75)=78

۹۰

۳

۶۰% u(135) + 40% u(75 )=82

۱۰۵

۴

۹۰%u(135)+10%u(75)=88

۱۲۰

۱

۹۵% u(150 ) + 5% u (0) = 95

۱۳۵

۰

۱۰۰

۱۵۰

با استفاده از نرم افزار Eviews تابع مطلوبیت را محاسبه می نماییم:

x1>=0               ۲x1+x2<=500

x2>=0               x1+2x2<=300

u1(f1)=a1(1-eb1f1)      u2(f2)=a2(1-eb2f2)

a1=139.857          b1=-0.01263      a2=127.25   b2=-0.010167

u1 (z1) = 139.857(1-e0.01263z1)  u2 (z2) = 127.25 (1-e-0.010167z2)


گام چهارم :تعیین مقادیر K1, K2, K3

فرض می کنیم DM  مقادیر K1=0.7  و K2=0.6  را در نظر گرفته است لذا چون مجموع هر سه k  باید برابر ۱ گردد مقدار ۰٫۳-=(K3 = (۱-۰٫۷-۰٫۶ تعیین می گردد.

بهترین و بدترین مقدار تابع

بهترین و بدترین مقدار تابع

K2= 0.3     ,   ۱- K2= 0.7

K3+K2+K1=1  K3= 1- K1+ K2   → →    K3= 1- 0.6+ 0.3=0.1

U(z1,z2) = 0.7 u1(z1,0)+0.6 u2(z2,0)-0.3u3(z1,0)*u2(z2,0)

U (z1, z2) = 0.7 *(139.857(1-e0.01263z1))+0.6(127.25 (1-e-0.010167z2))-0.3(139.857(1-e0.01263z1)* 127.25 (1-e-0.010167z2)


گام پنجم: محاسبه مقدار U

حال با حل کرده معادله فوق و اعمال محدودیت ها x1  و x2  بهینه تابع را با استفاده از نرم افزار WINQSB  بدست می آوریم:

U (x1, x2) = 0.7 *(139.857(1-e0.01263×1)) + 0.6(127.25 (1-e-0.010167×2))-0.3(139.857(1-e0.01263×1)* 127.25 (1-e-0.010167×2)

U (x1, x2) = -5164.79+5175.36 x+5209.46 y-5218.7 x y

S.to:        ۲X1 + X2≤ ۵۰۰

               X1 + 2 X2≤ ۳۰۰

                 X1, X2 ≥ ۰

X1*

X2*

F1(x*)

F2(x*)

U(x1,x2)

۲۵۰

۰

۵۰

۰

۵۴۰۰

ادامه مطلب...