حل مدل‌‌های برنامه‌ریزی خطی با استفاده از R

تحقیق در عملیات، شاخه‌ای میان‌رشته‌ای از ریاضی است که در بسیاری از رشته‌ها کاربرد دارد. تحقیق در عملیات، عموما به یافتن جواب بهینه‌ی یک مساله با استفاده از روش‌هایی چون برنامه‌ریزی ریاضی، آمار و طراحی الگوریتم‌ها می‌پردازد. در این پست قرار است به برنامه‌ریزی خطی، یکی از زیرمجموعه‌های برنامه‌ریزی ریاضی بپردازیم.

برای حل مسائل برنامه‌ریزی خطی، چند پکیج برای R توسعه داده شده که می‌توان برای حل مسائل کوچک، یا مدل‌هایی که در بعضی الگوریتم‌های خاص مانند الگوریتم تصمیم‌گیری LINMAP و یا Step method به آنها برمی‌خوریم رویشان حساب کرد. البته در نظر داشته باشید که برای مسائل بزرگ و پیچیده، R ابزار کندی است و بهتر است به همان نرم‌افزارهای تخصصی این شاخه مانند GAMS و LINGO رجوع شود. ساده‌ترین پکیجی که برای حل یک مساله بهینه‌سازی خطی در R وجود دارد پکیج linprog است. این پکیج با دستور زیر نصب می‌شود:

بعد از نصب پکیج، با این دستور آن را فعال می‌کنیم:

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

ورودی‌های این تابع به شرح زیر هستند:

cvec: بردار ضرایب تابع هدف

bvec: برداری شامل اعداد سمت راست (RHS)

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

maximum: در حالت عادی غیرفعال است و مساله یافتن مینیموم است، اگر مقدار آن را به TRUE تغییر دهید، مساله ماکسیموم‌سازی می‌شود.

const.dir: برداری شامل جهت محدودیت‌ها. این بردار در حالت پیشفرض، همه‌ی محدودیت‌ها را کوچکتر مساوی در نظر گرفته‌است. می‌توان با ضرب کردن محدودیت‌های بزرگتر مساوی در منفی یک، جهت آنها را به کوچکتر مساوی تغییر داد ولی اگر یکی از محدودیت‌های شما مساوی است، حتما باید این بردار را به صورت دستی وارد کنید. طول این بردار، با بردار bveck یکسان است.

نکته: نام محدودیت‌ها را باید با استفاده از توابع names و rownames به بردار cvec و ستون‌های ماتریس Amat بدهید.

مثال: فرض کنید مساله برنامه‌ریزی خطی زیر را می‌خواهیم حل کنیم:

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.

ورودی‌های مورد نیاز تابع را در R به وجود می‌آوریم:

با استفاده از تابع lpsolve مدل را حل می‌کنیم:

جواب بهینه‌ برابر ۲۱ به دست آمده و داده‌های تحلیل حساسیت و مقادیر Dual را نیز نمایش می‌دهد. پکیج linprog کمی کند است اما برای مسائل کوچک برنامه‌ریزی خطی با متغیرهای غیرصحیح مناسب است. برای حل مسائل برنامه‌ریزی عدد صحیح در R، باید از پکیج‌های دیگری استفاده نمود که در پست‌‌های بعدی با آنها آشنا خواهیم شد.

پی‌نوشت: مساله مورد نظر، از صفحه‌ی ۲۱۶ کتاب تحقیق در عملیات ۱ زاهدی‌سرشت گرفته شده است.

2 دیدگاه در “حل مدل‌‌های برنامه‌ریزی خطی با استفاده از R

    • از توجه شما ممنونم، یادگیری ماشینی هم جزء مباحثیه که ما قصد داریم در آینده درباره‌ش بنویسیم، اما فکر نمی‌کنم تا چند ماه آینده به اونجا برسیم.

دیدگاه‌تان را بنویسید: