کنفرانس بین المللی محاسبات نرم

صفحه اصلی / چهارمین کنفرانس بین المللی محاسبات نرم

ارائه یک الگوریتم ابتکاری برای حل مدل برنامه ریزی اعداد صحیح مسئله ترتیب خطی

نویسندگان :

امین اسکندری¹

1- دانشگاه شیراز

کلمات کلیدی :

ترتیب خطی، برنامه ریزی صحیح، الگوریتم های ابتکاری

چکیده :

مسئله ترتیب خطی یک مساله بهینه سازی کلاسیک است که می تواند برای مدل سازی مسایل زیادی در حوزه های مختلف مورد استفاده قرار بگیرد. برای نمونه می توان به نظریه گراف، زمان بندی ماشین و نظریه رای گیری اشاره نمود ، که بسیاری از آنها کاربردهای عملی دارند. در پژوهشهای جدید، از روش های ابتکاری مبتنی بر برنامه ریزی صحیح برای مسایل NP-hard استفاده زیادی شده است. در این تحقیق یک روش حل ابتکاری مبتنی بر برنامه ریزی صحیح برای مساله ترتیب خطی ارائه می شود. روش به این صورت است که ابتدا شرط صحیح بودن متغیر ها حذف می شود و مساله به یک مساله خطی تبدیل می شود. سپس یک جواب شدنی اولیه برای مساله خطی پیدا می شود. برای هر پاسخ شدنی مدل خطی یک همسایگی تعریف می شود و به کمک یک مدل صحیح به دنبال دیگر پاسخ ها در آن همسایگی می گردد. در نهایت نتایج اجرای الگوریتم بر روی داده های شبیه سازی شده ارائه شده است. در اجرای الگوریتم بر روی نمونه های ایجاد شده از مساله مشاهده می شود الگوریتم می تواند جواب های مناسبی تولید کند که اختلاف زیادی با جواب بهینه نداشته باشد.