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

جولای

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

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

install.packages("linprog")

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

library(linprog)

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

solveLP( cvec, bvec, Amat, maximum = FALSE, const.dir = rep( "<=", length( bvec )),)

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

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 به وجود می‌آوریم:

cvec = c(5,4)
names(cvec) <- c("x1","x2")
amat <- matrix(c(6,4,1,2,-1,1,0,1),byrow = T,nrow = 4)
 amat
     [,1] [,2]
[1,]    6    4
[2,]    1    2
[3,]   -1    1
[4,]    0    1

colnames(amat) <- names(cvec)

amat
     x1 x2
[1,]  6  4
[2,]  1  2
[3,] -1  1
[4,]  0  1

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

> solveLP(cvec,bvec,amat, maximum = TRUE)


Results of Linear Programming / Linear Optimization

Objective function (Maximum): 21 

Iterations in phase 1: 0
Iterations in phase 2: 2
Solution
   opt
x1 3.0
x2 1.5

Basic Variables
    opt
x1  3.0
x2  1.5
S 3 2.5
S 4 0.5

Constraints
  actual dir bvec free dual dual.reg
1   24.0  <=   24  0.0 0.75      4.0
2    6.0  <=    6  0.0 0.50      2.0
3   -1.5  <=    1  2.5 0.00      2.5
4    1.5  <=    2  0.5 0.00      0.5

All Variables (including slack variables)
    opt cvec    min.c     max.c  marg marg.reg
x1  3.0    5  2.00000  6.000000    NA       NA
x2  1.5    4  3.33333 10.000000    NA       NA
S 1 0.0    0     -Inf  0.750000 -0.75        4
S 2 0.0    0     -Inf  0.500000 -0.50        2
S 3 2.5    0 -2.00000  0.400000  0.00       NA
S 4 0.5    0 -6.00000  0.666667  0.00       NA

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

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

برچسب ها : آموزش

منبع اصلی نوشتار زیر در این لینک قرار دارد

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