【R语言在最优化中的应用】lpSolve包解决 指派问题和指派问题

lpSolve 包和运输问题

运输问题(transportation problem) 属于线性规划问题，可以根据模型按照线性规划的方式求解，但由于其特殊性，用常规的线性规划来求解并不是最有效的方法。lpSolve包提供了函数lp.transport() 来求解运输问题，用法如下：

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

其中:

cost.mat为费用矩阵，

direction决定求最大值还是最小值(取"min"或"max")。

row.signs(产量约束符号，取"<"、"<="、"="、"=="、">" 或">=") 和row.rhs(产量约束数值)构成产量约束条件。

col.signs(销量约束符号，取"<"、"<="、"="、"=="、">" 或">=") 和col.rhs(销量约束数值)构成销量约束条件。

compute.sens为逻辑变量，决定是否进行灵敏度分析(默认为0，即不进行灵敏度分析)。

下面通过两个例子来说明该函数的用法

有三个造纸厂A1、A2 和A3，造纸量分别为16 个单位、10 个单位和22 个单位，四个客户B1、B2、B3 和B4 的需求量分别为8 个单位、14 个单位、12 个单位和14 个单位。造纸厂到客户之间的单位运价如表所示，确定总运费最少的调运方案。

解：总产量等于总销量，都为48 个单位，这是一个产销平衡的运输问题。R代码及运行结果如下:

1> library(lpSolve) 2 > costs <-matrix(c(4,2,8,12,10,5,4,3,11,11,9,6),nrow=3) #运费矩阵 3 > row.signs <- rep("=", 3) #各家造纸厂的产量恰好可以售完，故都取等号 4 > row.rhs <- c(16,10,22) #销量约束值 5 > col.signs <- rep("=", 4) #各家客户需求量恰好可以满足，故都取等号 6 > col.rhs <- c(8,14,12,14) #需求约束值 7 > res <-lp.transport(costs,"min",row.signs,row.rhs,col.signs,col.rhs) 8 > res #输出最小运费 9 Success: the objective function is 244 10 > res$solution #输出运输方案 11 [,1] [,2] [,3] [,4] 12 [1,] 4 0 12 0 13 [2,] 4 0 0 6 14 [3,] 0 14 0 8

第9 行输出结果表示问题成功解决，最少运费为244，第11 – 14 行为输出的运输矩阵，运送方案为: A1→B1 : 4 个单位，A1→B3 : 12 个单位，A2→B1 :4 个单位，A2→B4 : 6 个单位，A3→B2 : 14 个单位，A3→B4 : 8 个单位。

lpSolve 包和指派问题

指派问题(assignment problem) 属于0 - 1 整数规划，是一种特殊的整数规划问题。指派问题的标准形式(以人和事为例) 是：有n 个人和n 个事，已知第i 个人做第j 件事的费用为Cij (i; j = 1, 2,…n)，要求确定人和事之间的一一对应的指派方案，使完成n件事的总费用最少。

R中，lpSolve包提供了函数lp.assign() 来求解标准指派问题，其用法如下：

lp.assign(cost.mat,direction = "min", presolve = 0, compute.sens = 0)

其中，cost.mat 为指派问题的系数矩阵，其元素的意义根据实际情况而定，可以是费用、时间、成本等。direction 为逻辑变量，来决定求总费用的最大值还是最小值，默认求总费用的最小值。compute.sens决定是否进行灵敏度分析。

某商业公司计划开办5 家新商店。为了尽早建成营业，商业公司决定由5 家建筑公司分别承建。已知建筑公司Ai(i = 1, 2,…5) 对新商店Bj(j = 1,2, … 5) 的建造费用的报价(万元) 为cij(i; j = 1,2… 5)，如表3。该公司应对5 家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？

解：这是一个标准的指派问题。R代码及运行结果如下:

1 > library(lpSolve) 2 >x=matrix(c(4,7,6,6,6,8,9,9,7,9,7,17,12,14,12, 3 + 15,14,8,6,10,12,10,7,10,6),ncol=5)##指派问题的系数矩阵 4 > lp.assign(x) 5 Success: the objective function is 34 6 > lp.assign(x)$solution 7 [,1] [,2] [,3] [,4] [,5] 8 [1,] 0 0 1 0 0 9 [2,] 0 1 0 0 0 10 [3,] 1 0 0 0 0 11 [4,] 0 0 0 1 0 12 [5,] 0 0 0 0 1

从运行结果可以看出，最优解已经成功找到。由lp.assign(x)$solution 得知，最优指派方案是：A1 承建B3，A2 承建B2，A3 承建B1，A4 承建B4，A5 承建B5。这样安排能使总费用最少，为7 + 9 + 6 + 6 + 6 = 34 万元。

在实际应用中，常会遇到各种非标准形式的指派问题，有时不能直接调用函数，处理方法是将它们化为标准形式(胡运权, 2007)，然后再通过标准方法求解。同运输问题一样，LINGO 在解决指派问题时，也必须通过各种命令建立数据集、模型、目标函数、约束函数等，比较繁琐，相比之下，R两三句代码就可以快速解决问题，较之LINGO 软件，的确方便快捷了许多。