|
عنوان
|
ارتقاء روش نقطه درونی کارمارکار بر اساس تغییر بردار گرادیان
|
|
نوع پژوهش
|
پایان نامه
|
|
کلیدواژه‌ها
|
برنامه ریزی خطی _ روشهای نقطه درونی _ تابع پتانسیل _ مسئله ی پوشش مجموعه
|
|
چکیده
|
روشهای نقطه درونی یکی از روشهای مهم برای حل مسائل برنامه ریزی خطی هستند که در سالهای اخیر مورد توجه محققین قرار گرفته اند. یکی از مهمترین این روشها الگوریتم کارمارکار است، که یک روش نقطه درونی با پیچیدگی محاسباتی چند جمله ای بوده و جواب بهینه ی مسائل بزرگ را در صورت وجود می یابد. هدف اصلی این پایان نامه ارتقاء روش نقطه درونی کارمارکار برای دسته ی خاصی از مسائل برنامه ریزی خطی است، که این کار به دو صورت انجام گرفته است. در یک روش با ارائه پارامتر طول گام جدید و پیاده سازی آن بر روی آزاد شده ی مسائل پوشش مجموعه، نشان داده می شود که سرعت همگرایی این روش به مراتب بالاتر از سرعت همگرایی الگوریتم کارمارکار می باشد. در روش دیگر با ارائه ی استراتژی های مناسب، با استفاده از ساختار مسئله در بدنه ی الگوریتم، جهت حرکت جدیدی به گونه ای معرفی می شود که با حرکت در این جهت جدید تعداد تکرارها تا رسیدن به شرط توقف کارمارکار نسبت به الگوریتم کارمارکار کاهش می یابد. در نهایت دو روش فوق را تلفیق نموده، ثابت می شود الگوریتم ارتقاء یافته برای مسائل پوشش مجموعه از نظر سرعت همگرایی بهتر از الگوریتم کارمارکار عمل می کند.
|
|
پژوهشگران
|
فردین ساعد پناه (استاد مشاور)، فرهاد جنتی (استاد راهنما)، شهلا ایزدی (دانشجو)
|