线性和整数编程 - R 实现
线性规划的R语言实现
R语言在针对各类优化模型时都能快速方便的求解,对运输问题、生产计划问题、产销问题和旅行商问题等都有专门的R包来解决。线性规划与整数规划的区别主要在于对决策变量的取值约束有所不同。线性规划的决策变量为正实数,而整数规划则要求决策变量为正整数。在R语言中,有众多相关的R包可以解决这两类问题,例如stat包中的optim、optimize函数,这里给大家推荐lpsolve包,lpsolve包用法简单,平移性好,核心函数调用方便,对解决大型的线性规划和整数规划问题十分好用。
1. R包lpSolve概述
lpSolve包专为求解线性规划问题的R包,与以前大家学习过的LINGO与MATLAB求解相仿。其核心函数为lp函数,其用法如下:
lp (direction = "min", objective.in, const.mat, const.dir, const.rhs,transpose.constraints = TRUE, int.vec, presolve=0, compute.sens=0, binary.vec, all.int=FALSE, all.bin=FALSE, scale = 196, dense.const, num.bin.solns=1, use.rw=FALSE)
参数Argument | 释义 | 中文解释 |
---|---|---|
direction | Character string giving direction of optimization: "min" (default) or "max." | 目标函数 "min" (缺省) or "max." |
objective.in | Numeric vector of coefficients of objective function | 目标函数系数 |
const.mat | Matrix of numeric constraint coefficients, one row per constraint, one column per variable (unless transpose.constraints = FALSE; see below) | 系数矩阵 |
const.dir | Vector of character strings giving the direction of the constraint: each value should be one of "<," "<=," "=," "==," ">," or ">=". (In each pair the two values are identical.) | 约束方向"<=" "=" ">=" |
const.rhs | Vector of numeric values for the right-hand sides of the constraints | 常数项 |
int.vec | Numeric vector giving the indices of variables that are required to be integer. The length of this vector will therefore be the number of integer variables. | 整数变量设置 |
compute.sens | Numeric: compute sensitivity? Default 0 (no); any non-zero value means "yes." | 灵敏度分析设置 |
binary.vec | Numeric vector like int.vec giving the indices of variables that are required to be binary | 0-1变量设置 |
all.int | Logical: should all variables be integer? Default: FALSE | 可设全部变量都取整数 |
all.bin | Logical: should all variables be binary? Default: FALSE | 可设全部变量都是0-1变量 |
2. 线性规划的R计算
2.1 线性规划示例
例1:一家公司希望最大化两种产品A和B的利润,分别以25美元和20美元的价格出售。每天有1800个资源单位,产品A需要20个单位,而B需要12个单位。这两种产品都需要15分钟的生产时间,并且可用的总工作时间为每天8小时。每种产品的生产数量应该是什么才能使利润最大化。
产品A | 产品B | 资源 | |
---|---|---|---|
资源1 | 20 | 12 | 1800 |
时间2 | 15 | 15 | 4800 |
利润 | 25 | 20 |
解:设生产两种产品的数量为\(x_1\),\(x_2\)
上述问题的目标函数是:
\(max(销售额)=max\) (25 \(x_1\) + 20 \(x_2\))
问题中的约束(资源和时间):
20\(x_1\) + 12 \(x_2\) <= 1800 (资源约束)
15\(x_1\) + 15 \(x_2\)<=4800 (时间约束)
数学模型(LP)为:
\begin{array}{l} \max z = 25{x_1} + 20{x_2} \\ s.t.\left\{ {\begin{array}{*{20}{c}} {20{x_1} + 12{x_2} \le 1800}\\ {15{x_1} + 15{x_2} \le 4800}\\\ {{x_1} \ge 0,{x_2} \ge 0} \end{array}} \right. \end{array}
例2:线性规划
#Set up problem: maximize
x1 + 9 x2 + x3
#subject to
x1 + 2 x2 + 3 x3 <= 9
3 x1 + 2 x2 + 2 x3 <= 15
x1>=0, x2>=0
2.2线性规划R求解
例1求解
library(lpSolve)
f.obj <- c(25, 20)
f.con <- matrix (c(20,12, 15,15), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(1800, 4800)
lp ("max", f.obj, f.con, f.dir, f.rhs)
lp1<-lp ("max", f.obj, f.con, f.dir, f.rhs)
lp1$solution
lp1$objval
lp ("max", f.obj, f.con, f.dir, f.rhs)
Success: the objective function is 3000
lp1$solution
[1] 0 150 #最优解
lp1$objval
[1] 3000 #最优值
例2求解
library(lpSolve)
f.obj <- c(1, 9, 1)
f.con <- matrix (c(1, 2, 3, 3, 2, 2), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(9, 15)
lp ("max", f.obj, f.con, f.dir, f.rhs)
lp2<-lp ("max", f.obj, f.con, f.dir, f.rhs)
lp2$solution
lp2$objval
lp ("max", f.obj, f.con, f.dir, f.rhs)
Success: the objective function is 40.5
lp2$solution
[1] 0.0 4.5 0.0 #最优解
lp2$objval
[1] 40.5 #最优值
3. 整数规划R计算
例3:使用lpSolve求解整数规划最大值
\begin{array}{l} \max z = 5{x_1} + 7{x_2} \\ s.t.\left\{ {\begin{array}{*{20}{c}} {{x_1} + 2{x_2} \le 16}\\ {2{x_1} + 3{x_2} \le 9}\\{{x_1} + {x_2} \le 8}\ \\{{x_1} \ge 0,{x_2} \ge 0} 且都是整数\end{array}} \right. \end{array}
library(lpSolve)
f.obj <- c(5,7)
f.con <- matrix(c(1,2,2,3,1,1), nrow=3,byrow=TRUE)
f.dir <- c('<=', '<=', '<=')
f.rhs <- c(16,9,8)
lp('max', f.obj, f.con,f.dir,f.rhs,all.int=TRUE)
求解结果如下
lp('max', f.obj, f.con,f.dir,f.rhs,all.int=TRUE)
Success: the objective function is 22
lp3<-lp('max', f.obj, f.con,f.dir,f.rhs,all.int=TRUE)
lp3$solution
[1] 3 1 #最优解都是整数
lp3$objval
[1] 22 #最优值
不加整数约束的解
lp('max', f.obj, f.con,f.dir,f.rhs)
Success: the objective function is 22.5
lp3<-lp('max', f.obj, f.con,f.dir,f.rhs)
lp3$solution
[1] 4.5 0.0
lp3$objval
[1] 22.5
参考文献
(【R语言在最优化中的应用】lpSolve包解决 指派问题和指派问题)[https://cloud.tencent.com/developer/article/1411788]
推荐阅读
-
R 语言实现,用于评估随机森林模型和重要预测变量的重要性
-
正负偏差变量 即 d2+、d2- 分别表示决策值中超出和未达到目标值的部分。而 di+、di- 均大于 0 刚性约束和目标约束(柔性目标约束有偏差) 在多目标规划中,>=/<= 在刚性约束中保持不变。当需要将约束条件转换为柔性约束条件时,需要将 >=/<= 更改为 =(因为已经有 d2+、d2- 用来表示正负偏差),并附加上 (+dii-di+) 注意这里是 +di、-di+!之所以是 +di,-di+,是因为需要将目标还原为最接近的原始刚性约束条件 优先级因素和权重因素 对多个目标进行优先排序和优先排序 目标规划的目标函数 是所有偏差变量的加权和。值得注意的是,这个加权和都取最小值。而 di+ 和 dii- 并不一定要出现在每个不同的需求层次中。具体分析需要具体问题具体分析 下面是一个例子: 题目中说设备 B 既要求充分利用,又要求尽可能不加班,那么列出的时间计量表达式即为:min z = P3 (d3- + d3 +) 使用 + 而不是 -d3 + 的原因是:正负偏差不可能同时存在,必须有 di+di=0 (因为判定值不可能同时大于目标值和小于目标值),而前面是 min,所以只要取 + 并让 di+ 和 dii- 都为正值即可。因此,得出以下规则: 最后,给出示例和相应的解法: 问题:某企业生产 A 和 B 两种产品,需要使用 A、B、C 三种设备。下表显示了与工时和设备使用限制有关的产品利润率。问该企业应如何组织生产以实现下列目标? (1) 力争利润目标不低于 1 500 美元; (2) 考虑到市场需求,A、B 两种产品的生产比例应尽量保持在 1:2; (3)设备 A 是贵重设备,严禁超时使用; (4)设备 C 可以适当加班,但要控制;设备 B 要求充分利用,但尽量不加班。 从重要性来看,设备 B 的重要性是设备 C 的三倍。 建立相应的目标规划模型并求解。 解:设企业生产 A、B 两种产品的件数分别为 x1、x2,并建立相应的目标计划模型: 以下为顺序求解法,利用 LINGO 求解: 1 级目标: 模型。 设置。 variable/1..2/:x;! s_con_num/1...4/:g,dplus,dminus;!所需软约束数量(g=dplus=dminus 数量)及相关参数; s_con(s_con_num);! s_con(s_con_num,variable):c;!软约束系数; 结束集 数据。 g=1500 0 16 15. c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(1);!第一个目标函数;!对应于 min=z 的第一小部分;! 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); !使用设置完成的数据构建软约束表达式; ! !软约束表达式 @for(variable:@gin(x)); !将变量约束为整数; ! 结束 此时,第一级目标的最优值为 0,第一级偏差为 0: 第二级目标: !求 dminus(1)=0,然后求解第二级目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(2)+dplus(2);!第二个目标函数 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标结果 @for(variable:@gin(x)); ! 结束 此时,第二个目标的最优值为 0,偏差为 0: 第三目标 !求 dminus(2)=0,然后求解第三个目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=3*dminus(3)+3*dplus(3)+dminus(4);!第三个目标函数。 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标约束条件; ! dminus(2)+dplus(2)=0; !第二个目标约束条件 @for(variable:@gin(x));! 结束 最终结果为 x1=2,x2=4,dplus(1)=100,最优利润为
-
矩阵范式和优化问题:解决线性和非线性编程问题
-
运筹学] 整数编程(整数编程问题解决方案的特点 | 整数编程问题和松弛问题示例)
-
[运筹学] 整数编程 ( 相关概念 | 整数编程 | 整数线性规划 | 整数线性规划的分类 )
-
MATLAB 解决线性规划(含整数规划和 0-1 规划)问题 [简单易懂]
-
整数编程问题的建模技术和求解方法汇总-3 求解方法
-
运筹学中的线性规划和整数规划
-
[运筹学] 整数编程 ( 相关概念 | 整数编程 | 整数线性规划 | 整数线性规划的分类 )
-
线性和整数编程 - R 实现