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

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

Keywords:

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