حل مدل‌های برنامه‌ریزی عدد صحیح و MILP با استفاده از R

در مطلب قبلی، به حل یک مدل برنامه‌ریزی خطی با استفاده از پکیج linprog پرداختیم، کار با این پکیج ساده است اما همانطور که گفتیم، محدودیت‌‌هایی دارد و نمی‌تواند مسائل برنامه‌ریزی عدد صحیح یا مسائل برنامه‌ریزی مختلط (Mixed Integer Programming) را حل کند، برای این کار، به سراغ پکیج  دیگری به نام lpSolve می‌رویم. این پکیج را با دستور زیر نصب کنید:

تابع lp در این پکیج، مدل‌های برنامه‌ریزی خطی و برنامه‌ریزی خطی عدد صحیح را حل می‌کند. از این تابع باید به صورت زیر استفاده کنید:

direction: نوع مساله را مشخص می‌کند. مقادیری که باید به آن بدهید min و یا max هستند.

objective.in: برداری از نوع عددی شامل ضرایب تابع هدف

const.mat: ماتریسی شامل ضرایب محدودیت‌ها

const.dir: برداری که با آن  جهت محدودیت‌ها را مشخص می‌کنیم.

const.rhs : برداری شامل اعداد سمت راست.

transpose.constraints : اگر ماتریس ضرایب محدودیت‌‌ها را طوری وارد کرده‌اید که هر سطر شامل یک محدودیت است با این یکی کاری نداشته باشید و بگذارید روی TRUE بماند، اما اگر هر ستون شانل ضرایب یک محدودیت است مقدار آن را به FALSE تغییر دهید

compute.sens: اگر مقدار آن را از ۰ به یک عدد دیگر تغییر دهید محاسبات تحلیل حساسیت نیز انجام می‌شود.

int.vec و binary.vec: برای تعیین متغیرهایی که عدد صحیح یا باینری(صفر و یک ) هستند استفاده می‌شود.

all.int و all.bin: اگر یکی از آنها را برابر TRUE قرار دهید، مسئله به ترتیب به مسئله‌ی عدد صحیح یا مسئله صفر و یک تبدیل می‌شود.

scale: به طور پیشفرض روی ۱۹۶ قرار دارد اما باید آن را روی ۰ قرار دهید تا جواب صحیح به دست آید.

همان مسئله پست قبلی را دوباره مطرح و حل می‌کنیم:

maxZ= 5x_{1} + 4x_{2}\\ \\  \left\{\begin{matrix}  6x_{1} + 4x_{2} \leq 24\\  x_{1} + 2x_{2} \leq 6\\  -x_{1} + x_{2} \leq1\\  x_{2}\leq 2\\  x_{1},x_{2} \geq0  \end{matrix}\right.

با اجرای دستور lp، مقدار بهینه‌ی مسئله که برابر ۲۱ است به نمایش در می‌آید:

همانطور که می‌بینید مقادیر بهینه‌ی متغیرهای تصمیم به نمایش در نیامده است. برای همین بهتر است تابع را به این صورت استفاده کنیم تا خروجی آن به صورت یک لیست ذخیره شود:

حالا با استفاده از عملگر $ می‌توانیم به مقادیر مختلفی که در مورد جواب بهینه‌ی مساله محاسبه شده است دسترسی داشته باشیم:

همانطور که در کد بالا می‌بینید مقدار بهینه‌ی متغیر دوم ۱.۵ است که عددی اعشاری است. با استفاده از int.vec می‌توانیم این متغیر را به یک متغیر عدد صحیح تبدیل کنیم، برای استفاده از این قابلیت، باید برداری که شامل اندیس متغیرهایی صحیح است را در int.vec ذخیره کنیم بدیهی است که تعداد اعضای این بردار، برابر تعداد متغیرهای عدد صحیح خواهد بود. در اینجا اندیس متغیری که باید عدد صحیح شود ۲ است. برای همین int.vec را برابر ۲ قرار می‌دهیم.

استفاده از binary.vec هم به همین صورت است. فرض کنید یک مسئله داریم که متغرهای ۳،۷ و ۹ آن عدد صحیح و متغیرهای ۱، ۴ و ۵ آن صفر و یک هستند، در این صورت باید int.vec را برابر بردار شامل اعداد ۳، ۷ و ۹ و بردار binary.vec را برابر برداری شامل اعداد ۱،۴ و ۵ قرار دهید. دقت کنید که شمردن در R از یک شروع می‌شود نه صفر.

پکیج lpsolve به زبان c نوشته شده به همین دلیل پکیج نسبتا سریعی است. از طرف دیگر، می‌توان نتایج آن را به صورت یک لیست ذخیره کرد به همین دلیل برای استفاده در الگوریتمهایی که بخشی از آنها شامل حل سیمپلکس می‌شود بسیار مناسب است. در پست بعدی، با پکیجی دیگر در R که می‌تواند مسائل برنامه‌ریزی ریاضی را حل کند آشنا خواهیم شد و دو مسئله‌ی معروف کوله‌پشتی و هشت وزیر صفحه شطرنج را در R حل خواهیم کرد.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *