تحقیق در عملیات ( Operation Research)

بهینه سازی

دانلود رایگان پروژه بررسی پیچیدگی الگوریتم سیمپلکس و مثال KLEE-MINTY
نویسنده : دکتر نعمت اله تقی نژاد - ساعت ۳:٢٤ ‎ب.ظ روز دوشنبه ۱٦ بهمن ۱۳٩۱
 

 

 

تجربه کار با الگوریتم سیمپلکس نشان داده است که حل یک LP به شکل استاندارد با n متغیر و m محدودیت جواب بهینه ای دارد که معمولا قبل از بررسی 3m جواب پایه موجه پیدا می شود.

     اما این موضوع کلیت ندارد. مثال KLEE-MINTY این مساله را نشان می دهد. قبل از بررسی مثال KLEE-MINTY مثال زیر را بررسی می کنیم که در آن باید هر جواب پایه موجه قبل از پیدا شدن جواب بهینه امتحان شود.

 

Max     z=2n-1x1+2n-2x2+…+2xn-1+xn

      s.t

                 x1                                ≤ 5

                4 x1+x2                                 52

                2nx1+2n-1x2+...+4xn-1+xn ≤5n

الگوریتم سیمپلکس در مثال KLEE-MINTY (یک lp با n (n=2,3,..) متغیر تصمیم و n محدودیت)  2n-1جواب پایه موجه را قبل از یافتن جواب بهینه امتحان میکند.

 

دانلود فایل 1

دانلود فایل 2

 


 
 
 



backgroundcolor= class=#2f57a2width:230px; padding-top: 5px;td width=logo