R语言解决最优化问题-线性优化(LP)问题

优化是一种为所有可能的解决方案找到给定问题的最佳解决方案的技术。

由Kaizong Ye,Sherry Deng撰写

优化使用严格的数学模型来找出给定问题的最有效解决方案。

线性优化简介

要从优化问题开始,首先确定目标非常重要。目标是绩效的量化衡量。例如:最大化利润,最小化时间,最小化成本,最大化销售。

优化问题可分为两组

  1. 线性规划(LP):它也被称为线性优化,在这个问题中,目标是在数学模型中获得最佳结果,其中目标和所有约束是决策变量的线性函数。
  2. 二次规划(QP):在二次规划中,目标是决策变量和约束的二次函数,它们是变量的线性函数。二次函数也是一种非线性规划。

对于这篇文章,只解释了线性规划问题。


热门课程

R语言数据分析挖掘必知必会

面对扑面而来的数据浪潮,包含Google、Facebook等国际企业,都已采用R语言进行数据分析

探索课程

R中的线性优化:

R中可用于优化的常用包包括:

问题类型软件包函数
General (1-dimensional)Built-inoptimize()
General (n-dimensional)Built-inoptim()
Linear Programming (LP)lpsolvelp()
Quadratic Programming (QP)quadprogsolve.qp()
General InterfaceROIROI_Solve()

 一般优化问题的内置函数示例:

  • 这些程序的一般参数结构是:

例:

  • 定义目标函数
  • 优化功能
  • 检查优化是否收敛到最小
  • 最佳输入参数
  • 目标函数的价值至少

线性规划(LP)

线性编程表示为:

min c T   = min(c 1 x 1 + … + c n x n)

限制:

x> = B,x  > = 0

线性规划示例:

  • 一家公司希望最大化两种产品A和B的利润,分别以25美元和20美元的价格出售。每天有1800个资源单位,产品A需要20个单位,而B需要12个单位。这两种产品都需要4分钟的生产时间,并且可用的总工作时间为每天8小时。每种产品的生产数量应该是什么才能使利润最大化。

上述问题的目标函数是:

max(销售额)=max(25 x 1 + 20 x 2)

其中,
x 1是产品A的单位产生的
x 2是产品B的单位产生的
x 1和x 2也称为决策变量

问题中的约束(资源和时间):

20x 1 + 12 x 2 <= 1800(资源约束)
4x 1 + 4x 2 <= 8 * 60(时间约束)

解决R中的上述问题:

由于这是一个线性规划问题,我们将使用  lpsolve  package和  lp() 函数来找到最优解。lp() 函数的语法  是:

  • 方向控制是否最小化或最大化
  • 系数c被编码为矢量objective.in
  • 约束A作为矩阵const.mat给出,方向为const.dir
  • 约束b作为向量const.rhs插入

从上面的输出中,我们可以看到该公司应该生产45个产品A和75个产品B单位,以获得2625美元的销售额。

在制定目标函数和约束之后,我们可以扩展相同的方法来解决R中的其他LP问题。


可下载资源

关于作者

Kaizong Ye拓端研究室(TRL)的研究员。

本文借鉴了作者最近为《R语言数据分析挖掘必知必会 》课堂做的准备。

​非常感谢您阅读本文,如需帮助请联系我们!


 
QQ在线咨询
售前咨询热线
15121130882
售后咨询热线
0571-63341498