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

بهینه سازی

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

سیمپلکس یک الگوریتم دارای ‌پیچیدگی زمانی از مرتبه ی نمایی (O(n2 است.

در حالی که پیچیدگی زمانی الگوریتم کارمارکار  (O(2n است .

در حالت کلی الگوریتم هایی که پیچیدگی آنها نمایی است ، پیشرفت تکنولوژی نمی تواند در حل مسأله هایی با اندازه های بزرگ ، کمک چندانی نماید. الگوریتم سیمپلکس با آنکه دارای پیچیدگی نمایی است ولی تجربه نشان داده که این الگوریتم در اغلب موارد حداکثر تا 3m تکرار به نقطه ی بهین خود می رسد به اصطلاح دارای Practical Complexity  است .

در این پروژه پیچیدگی الگوریتم سیمپلکس را بصورت جامع و دقیق مورد بررسی قرار داده ایم:

 

 دانلود رایگان فایل کامل پروژه

p style=


 
 
 



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