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

بهینه سازی

روش کارمارکار ( Karmarkar Method )
نویسنده : دکتر نعمت اله تقی نژاد - ساعت ۳:۱٧ ‎ب.ظ روز یکشنبه ٢٩ بهمن ۱۳٩۱
 

روش کارمارکار

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

زمان اجرای الگوریتم کارمارکار از مربته چندجمله ای است که در مقایسه با زمان اجرای الگوریتم سیمپلکس از مرتبه نمایی بسیار سریعتر می باشد و بر آن ارجعیت دارد . در آزمایش های انجام شده این روش تا 50 برابر سریعتر از روش سیمپلکس می باشد.

روش کارمارکار را اخیرا فرماندهی نیروی هواییی آمریکا برای تعیین مسیر و نوع هواپیما مور نیاز به کار گرفته است. این LP ، صد و پنجاه هزار متغییر تصمیم و 12 هزار محدودیت دارد که با روش کارمارکار در کمتر از 1 ساعت حل می شود.

همچنین شرکت دلتا نیز اخیرا روش کارمارکار را برای برنامه ریزی ماهانه مجموعه ای از 7000 خلبان و 400 هواپیما انتخاب کرده است. آنان انتظار دارند تا پایان پروژه میلیونها دلار در هزینه ها صرفه جویی کنند. 

 توضیحات در مورد این روش بیش از این مقدار است، در ادامه چندین پروژه از معرفی این روش و همگرایی و ... آن برای دانلود قرار داده ایم:

دانلود روش کارمارکار 1

دانلود روش کارمارکار 2 

دانلود روش کارمارکار 3  

 


 
 
 



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