کارشناسی ارشد مدیریت از نگاهی دیگر
خرداد 5, 1398روش تحقیق تک آزمودنی
خرداد 8, 1398الگوریتم کارمارکار
بیشتر از ۳۰ سال است که الگوریتم کارمارکار (Karmarkar Algorithm) مطرح شدهاست.
با اینحال، به غیر از چند صفحه مختصری که با جستجوهای بسیار درمورد آن به فارسی میتوان پیدا کرد، مطلب زیادی راجع به آن در میان سایتهای فارسی مطرحنشدهاست.
البته در کتابهای متعددی به این موضوع به دقت پرداختهشدهاست که عبارتند از:
– کتاب تحقیق در عملیات پیشرفته تألیف خانم دکتر الفت و همکارن (۱۳۹۱)
– کتاب برنامه ریزی خطی و الگوریتم کارمارکار تألیف آقای دکتر آریانژاد (۱۳۷۱)
در سالهای ۱۳۹۶ و ۹۷ سئوالاتی از الگوریتم کارمارکار در درس تحقیق در عملیات پیشرفته برای آزمون دکتری رشته مدیریت صنعتی مطرح شد.
این سؤالات ضمن گوشزد الگوریتم کارمارکار، بررسی این الگوریتم را به طور مجزا واجب کرد.
در این مقاله که به مرور کامل میشود، تلاش خواهم کرد این الگوریتم را با جزئیات بررسی کنم.
سپس نکات آن را با زبانی ساده و با ذکر پیشنیازهای موردنیاز (درصورت لزوم) تحلیل کنم.
نویسنده: افشین صفایی
الگوریتم کارمارکار
مقدمه
بکارگیری روش سیمپلکس و پس از آن الگوریتم سیمپلکس تجدیدنظرشده، برای مدتها پس از کشف دانتزیک به عنوان تکنیکهای پایه و اساسی برای حل مسائل برنامه ریزی خطی مورداستفاده قرارگرفتهاند.
تجربه حل تعداد بسیار زیاد مسائل حلشده با الگوریتم سیمپلکس نشان داد که هزینه اجرایی (زمان اجرا) این الگوریتم بالاست.
با توجه به تعداد دورهایی که جدول سیمپلکس کامل و این الگوریتم اجرا میشود، نشان داده شدهاست که اگر تعداد متغیرهای مسئله برابر با n باشد، این هزینه محاسباتی متناسب با ۱٫۵n است.
علاوهبراین، اگر m تعداد محدودیتهای مسئله باشد تعداد عملیات لازم برای الگوریتم سیمپلکس در هر بار اجرای این الگوریتم متناسب با mn میباشد.
چنین برآوردی نشان میدهد که الگوریتم سیمپلکس یک الگوریتم چندجملهای زمانی برحسب n است.
ضمن اینکه، کلی و مینتلی (Klee and Minty) در سال ۱۹۷۲ با ارائه مسئلهای خاص از برنامهریزی خطی نشان دادند که در مواجهه با حالتهای خیلی خاص تعیین متغیرهای ورودی و خروجی در الگوریتم سیمپلکس ممکن است موجب شود، زمان محاسباتی این الگوریتم بشدت افزایش پیدا کرده و نمایی شود.
بنابراین، در حالت کلی زمان اجرای الگوریتم سیمپلکس را نه چندجملهای، بلکه باید نمایی دانست.
الگوریتم کارمارکار
با اینکه مطمئن هستم کسی که این مقاله را میخواند بحث زیر را میداند ولی با اینحال به اختصار ذکر نکته زیر خالی از لطف نیست.
در الگوریتم سیمپلکس، حل از یک نقطه آغازین که معمولاً مبداء مختصات است شروع میشود.
سپس نقاط گوشهای فضای محدب جواب یک به یک بررسی میشوند تا به جواب بهینه برسیم.
در میانههای دهه ۱۹۸۰ یک روش جدید برای حل مسائل برنامهریزی خطی پیشنهاد شد.
این روش پیشنهادی براساس کاری بود که تلاش میکرد الگوریتمهایی ایجاد کند که به جای بررسی نقاط گوشهای منطقه جواب، مسیرهایی در داخل فضای محدب و شدنی مسئله طی کنند.
البته باید اشاره کرد که در دهه ۱۹۵۰، کارهایی روی مسیرهای داخلی انجام شدند ولی نتوانستند جایگاه مناسب خود را پیدا کنند.
تا اینکه در ۱۹۷۹، خاچیان (Khachiyan) ثابت کرد که با استفاده از یک الگوریتم مسیر داخلی (Interior path algorithm)، میتوان تضمین کرد که یک مسئله برنامهریزی خطی را میتوان در زمانی چندجملهای (به جای زمان نمایی در الگوریتم سیمپلکس) حل کرد.
این اثبات، علاقهمندی به روشهای مسیر داخلی را مجدداً در دل پژوهشگران زنده کرد.
مقاله در حال تکمیل شدن است.
تا کنکور با شما هستیم… برای اطلاع از آخرین اخبار و مشاهده فیلمهای آموزشی دکتری به صفحه اینستاگرام دیجی درس مراجعه نمایید:
صفحه اینستاگرام دیجی درس، دانشگاهی در خانه
مطالعه مقالات زیر میتواند برای شما جذاب باشد:
برنامهریزی همتای استوار
خرید و دانلود محصولات آموزشی کنکور دکتری:
آمار دکتری
روش تحقیق دکتری
مدیریت تولید و عملیات
پاسخ تشریحی کنکور دکتری
بسته جمعبندی آمار کنکور دکتری
1 Comment
[…] سال ۱۳۹۷ یک سئوال از این مبحث مطرح شده است که در آن الگوریتم کار-مار-کار مطرح شده […]