首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【推荐阅读--R语言在最优化中的应用】用Rglpk包解决线性规划与整数规划 ​

【推荐阅读--R语言在最优化中的应用】用Rglpk包解决线性规划与整数规划 ​

作者头像
统计学家
发布2019-04-10 10:29:59
4.2K0
发布2019-04-10 10:29:59
举报

线性规划与整数规划

线性规划(linear programming)和整数规划(integerprogramming)的主要区别是决策变量的约束不同,其中线性规划的变量为正实数,而纯整数规划的变量为正整数。如果决策变量中一部分为整数,另一部分可以不取整数,则该问题为混合整数规划 (mixedinteger linear programming)。线性规划和整数规划都可以视为混合整数规划的特例,用矩阵和向量表示混合整数规划的数学模型如下:

R中,有很多包可以解决该问题,推荐 Rglpk包 (Theussl and Hornik, 2008),该包提供了到GLPK (GNU Linear Programming Kit) 的高级接口,不仅可以方便快速地解决大型的线性规划、整数规划、混合整数规划,并且用法非常简单。核心函数为Rglpk_solve_LP(),用法如下:

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

其中,obj为目标函数的系数,即模型中的向量C,mat为约束矩阵,即模型中的矩阵A,dir 为约束矩阵 A 右边的符(取"<"、"<="、"=="、">"或 ">="),rhs 为约束向量,即模型中的向量 b,types 为变量类型,可选”B”、”I” 或”C”,分别代表0-1整数变量,正整数和正实数,默认为正整数。max为逻辑参数,当其为 TRUE 时,求目标函数的最大值,为 FALSE 时 (默认)求目标函数的最小值。bounds 为 x 的额外约束,由模型 (1) 中向量l和u控制。verbose 为是否输出中间过程的控制参数,默认为FALSE。

例:

解:这是简单的线性规划问题,变量的类型没有特殊要求,即正实数。R代码及运行结果如下:

> obj<-c(3,1,3) > mat<-matrix(c(-1,0,1,2,4,-3,1,-3,2),nrow=3) > dir<-rep("<=",3) > rhs<-c(4,2,3) > types<-c("I","C","I") > Rglpk_solve_LP(obj,mat,dir,rhs,types,max=TRUE) $optimum [1] 29 $solution [1] 5.333333 3.000000 3.333333 $status [1] 0

$optimum为目标函数最大值

$solution为最优解

$status为逻辑变量,为0时表示求解成功

输出结果中,$optimum 为目标函数的最大值,$solution 表示决策变量的最优解,$status 为 0时,表示最优解寻找成功,非 0 时失败。本题中,$status 为0,表示最优解已经找到。x1,x2,x3的最优解分别为 0,6.666667,16.666667,此时目标函数取得最大值 76.66667。

我们发现 R在解决线性规划、整数规划、混合整数规划问题时,仅仅需要将模型转换为求解函数所需要的格式即可,并且几乎所有的约束都直接用矩阵、向量来表示,不必像LINGO 那样需要键入 X1、X2 之类的字符,当问题规模较大时,这优势显得格外突出。

求土豪打赏:

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2015-07-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器学习与统计学 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档