R语言与优化模型(一):线性规划、整数规划和运输问题

时间:2024-03-18 16:36:33

    


    从本期推送往后,louwill打算开一个用R语言实现数学建模基本算法和模型的系列。虽说目前数学建模领域大家用的软件工具都是Matlab或者Lingo,但在个人偏好的驱使下还是决定用自己擅长的R语言来实现数学建模算法。就首先从优化模型中简单的线性规划、整数规划以及多目标规划开始。R语言在针对各类优化模型时都能快速方便的求解,对运输问题、生产计划问题、产销问题和旅行商问题等都有专门的R包来解决。


R语言与优化模型(一):线性规划、整数规划和运输问题


    线性规划与整数规划的区别主要在于对决策变量的取值约束有所不同。线性规划的决策变量为正实数,而整数规划则要求决策变量为正整数。在R语言中,有众多相关的R包可以解决这两类问题,例如stat包中的optim、optimize函数,这里给大家推荐Rglpk包,Rglpk包用法简单,核心函数调用方便,对解决大型的线性规划和整数规划问题十分好用。

    Rglpk包的核心函数为Rglpk_solve_LP函数,其用法如下:

 Rglpk_solve_LP(obj,mat,dir,rhs,types=NULL,max=FALSE,bounds=NULL, verbose=FALSE)

    其中obj为目标函数系数,mat为约束矩阵,dir为约束符号,rhs为约束向量,types为变量类型,可选类型有“B”“I”“C”,分别代表0-1变量、正整数和正实数,max为逻辑参数,当其取TRUE 时求目标函数最大值,反之为最小值,bounds为决策变量的额外约束,verbose表示是否输出中间过程的的控制参数,默认为FALSE。

    看一个求解线性规划的例子:

library(Rglpk)
obj<-c(10,15,12)#目标函数系数
mat<-matrix(c(5,-5,2,3,6,1,1,15,1),nrow=3)#约束矩阵
dir<-rep("<=",3)#约束符号
rhs<-c(9,15,5)#约束向量
Rglpk_solve_LP(obj,mat,dir,rhs,max=TRUE)#求解
 
$optimum
[1] 42
$solution
[1] 0.200000 2.666667 0.000000

    求解过程清晰明了,比起专业的线性规划软件Lingo有过之而无不及。

    再看一例整数规划(0-1规划):

obj<-c(4,3,2)
mat<-matrix(c(2,4,0,-5,1,1,3,3,1),nrow=3)
dir<-c("<=",">=",">=")
rhs<-c(4,3,1)
types<-c("B","B","B")#指定变量类型,模型为0-1规划
Rglpk_solve_LP(obj,mat,dir,rhs,types,max=FALSE)

$optimum
[1] 2
$solution
[1] 0 0 1

    整数规划(0-1规划)和线性规划并无本质区别,所以在Rglpk中其实现函数一样,只是依靠types参数来控制两个模型的区别。

    

    运输问题为常见的线性规划问题,但Rglpk包并没有普适性。R针对运输问题、生产计划等问题有专门的R包lpSovle,其核心函数 lp.transport 用法如下:

lp.transport(costs.mat,direction="min",row.signs,row.rhs,
col.signs,col.rhs,presolve=0,compute.sense=0,integers=1:(nc*nr))

    其中cost.mat为运费矩阵,direction参数决定取最大值还是最小值,row.sign(产量约束符号)和row.rhs(产量约束向量)构成产量约束条件;col.sign(销量约束符号)和col.rhs(销量约束向量)构成销量约束条件,其余参数可忽略。

    例:使用lpSovle包求解6个生产点和8个销售点的最小费用运输问题。

R语言与优化模型(一):线性规划、整数规划和运输问题

library(lpSolve)
costs<-matrix(c(6,4,5,7,2,5,2,9,2,6,3,5,6,5,1,7,9,
2,7,3,9,3,5,2,4,8,7,9,7,8,2,5,4,2,2,1,5,8,3,7,6,4,
9,2,3,1,5,3),nrow=6)#运费矩阵
row.signs<-rep("<=",6)#产量约束符号
row.rhs<-c(60,55,51,43,41,52)#产量约束向量
col.signs<-rep("=",8)#销量约束符号
col.rhs<-c(35,37,22,32,41,32,43,38)#销量约束向量
res<-lp.transport(costs,"min",row.signs,row.rhs,col.signs,
                 col.rhs)

res
Success: the objective function is 664
res$solution
    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0   19    0    0   41    0    0    0
[2,]    0    0    0   32    0    0    0    1
[3,]    0   12    0    0    0    0   39    0
[4,]    0    0    0    0    0    6    0   37
[5,]   35    6    0    0    0    0    0    0
[6,]    0    0   22    0    0   26    4    0

    由R输出结果可知6个生产点8个销售点的最小运费为664,相应的运送方案为A1→B2:19个单位,A1→B5:41个单位,A2→B4:32个单位,A2→B8:1个单位,A3→B2:12个单位,A3→B7:39个单位,A4→B8:37个单位,A5→B1:35个单位,A5→B2:6个单位,A6→B3:22单位,A6→B6:26个单位,A6→B7:4个单位。

    



R语言与优化模型(一):线性规划、整数规划和运输问题
R语言与优化模型(一):线性规划、整数规划和运输问题
扫码关注数据科学家养成记