专栏首页机器学习与统计学【推荐阅读--R语言在最优化中的应用】用Rglpk包解决线性规划与整数规划 ​

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

线性规划与整数规划

线性规划(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 之类的字符,当问题规模较大时,这优势显得格外突出。

求土豪打赏:

本文分享自微信公众号 - 机器学习与统计学(tjxj666)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-07-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • R语言第二章数据处理(9)数据合并

    =========================================

    用户1359560
  • Python与PHP的对决:谁是工程师最喜欢和最讨厌的语言?

    为了弄清楚雇主对哪些编程技能最感兴趣,Hired 研究了求职者在到六周内收到的面试邀请数量。如下图显示,谷歌的 Go 语言是雇主最需要的编程语言技能,可能因为这...

    机器之心
  • 经验分享 | 如何写好数据分析师简历?

    我们要确定怎么样简历是一份好数据分析师简历呢?那我们就要涉及到如何评价一个好数据分析师?一般来说,优秀的数据分析师有着很好的表达能力,能通过在二分钟对自己工作内...

    用户2769421
  • R语言读入数据库的中英名词互译测试并计分脚本(考试用)

        1. 分子生物学中英文.csv,输入文件,两列,以tab键分隔的txt文本,没有列名

    用户1680321
  • R语言之可视化(21)令人眼前一亮的颜色包

    用户1359560
  • 2019年需要关注的区块链智能合约开发平台

    智能合约开发语言已经被Solidity统治了一段时间,它用于开发可以在以太坊虚拟机EVM上运行的智能合约。不过Solidity有一些严重的问题,包括算术溢出、类...

    用户1408045
  • 奇怪的编码问题

    今天使用R爬取数据的时候发现一个奇怪的问题,我将每个属性的数据先保存在vector中,然后再合并到data.frame中时,发现打印names时数据正常显示中文...

    用户2936342
  • R语言之可视化(23)高亮某一元素

    总结:假如需要高亮ggplot2中的某一元素时,首先需要新建一列,然后修改新建列中需要高亮的部分即可

    用户1359560
  • R语言之可视化(22)绘制堆积条形图

    经过这张图,我们可以初步得到的信息是:(1)T1到T4各个分期的患者总数(2)T1期男性患者的数目,T1女性患者的数目(3)其他分期男性或者女性的患者数目。

    用户1359560
  • 线性代数--MIT18.06(三)

    ,我们依然可以使用矩阵消元的形式来求解,只不过要比我们之前提到的矩阵消元多做一些消元而已,这就是Gauss-Jordan法。

    fireWang

扫码关注云+社区

领取腾讯云代金券