MIT:The Analytics Edge 笔记08－线性优化

MIT课程 15.071x The Analytics Edge 第八单元的学习记录。

Linear Optimization

第八单元的主题是线性优化。

1.理论

线性优化

线性优化，其实是用Excel／LibreOffice求解一个简单的多元1次多项式的最大值。
使用LibreOffice是这样做的：

在单元格中填写多项式和约束条件。
选取Tools->Solver，指定多项式，以及各种约束条件，当然也要选择［Linear Solver］这个方法。
点击［Solve］就可以得到结果啦。

在Excel中，需要在option - addin - Excel addin 选择加载solver addin，这样才会在data菜单栏中显示出solver按钮。

sensitivity analysis

sensitivity analysis用来展示，结果是如何随数据（变量／约束条件）的变化而变化的。
shadow prices：表示当需求增加时，将（总量增加量／需求增量）的值定义为影子价格。

如图，纵坐标和横坐标表示两种不同的需求。暗红色阴影表示可能的取值范围。
如果不断提高需求R，从100到125到150，影子价格都保持不变；但是如果需求提高到170，影子价格就会发生变化。
如果不短提高需求D，从150到100，影子价格都为0，总量也不变。

影子价格有可能在需求增加的一个范围内保持不变。也有可能一直为0。

2.实战

当然，用R也能解决这样的问题。

# 先安装pkg
install.packages("lpSolveAPI")
library(lpSolveAPI)

# 创建模型
# 说明：
# 第一个参数是约束条件的个数。
# one capacity constraint: 载客量有一个最大值（飞机座位数）
# two demand constraints : 每种票价的数目（regular seats／discount seats）都有一个最大值
# 所以这个参数的取值是3
# 第二个参数是变量的个数。
# decision variables : 我们有两种票价（regular seats／discount seats）
# 所以这个参数的取值是2

AirlineSimple = make.lp(3,2)
# 创建出来的AirlineSimple是这样子的：
Model name: 
            C1    C2         
Minimize     0     0         
R1           0     0  free  0
R2           0     0  free  0
R3           0     0  free  0
Kind       Std   Std         
Type      Real  Real         
Upper      Inf   Inf         
Lower        0     0         

# 那下面我们就来指定多项式和约束条件
# 最终的效果是这样的：
# max         617*R + 238*D
# subject to    1*R +   1*D <= 166
#               1*R    +   0*D <= 100
#               0*R +   1*D <= 150    

# 特别注意：执行顺序，set.objfn()不能放在前面，我被坑了。。。
# 指定约束条件（跟效果竖着对比着看）
set.column(AirlineSimple, 1, c(1,1,0))
set.column(AirlineSimple, 2, c(1,0,1))
set.constr.type(AirlineSimple, c("<=","<=","<="))
set.rhs(AirlineSimple, c(166,100,150))
# 指定两个变量的参数
set.objfn(AirlineSimple, c(617,238))
# 默认的是最小值，我们改为最大值
lp.control(AirlineSimple,sense='max')

# 这样就创建好了：
Model name: 
            C1    C2         
Maximize   617   238         
R1           1     1  <=  166
R2           1     0  <=  100
R3           0     1  <=  150
Kind       Std   Std         
Type      Real  Real         
Upper      Inf   Inf         
Lower        0     0

# 变量的取值是上面最后两行Upper和Lower，可以通过函数set.bounds()来修改

# 现在可以来运行了
# 如果正确运行，返回值是0
solve(AirlineSimple)
# 查看取得的最大值
get.objective(AirlineSimple)
# 查看取最大值时，两个变量的取值
get.variables(AirlineSimple)

# JFK 从DFW中转，到LAX的场景
# 有8个约束条件，6个变量：
AirlineConnecting = make.lp(8,6)
set.column(AirlineConnecting, 1, c(1,1,1,0,0,0,0,0))
set.column(AirlineConnecting, 2, c(1,1,0,1,0,0,0,0))
set.column(AirlineConnecting, 3, c(1,0,0,0,1,0,0,0))
set.column(AirlineConnecting, 4, c(1,0,0,0,0,1,0,0))
set.column(AirlineConnecting, 5, c(0,1,0,0,0,0,1,0))
set.column(AirlineConnecting, 6, c(0,1,0,0,0,0,0,1))
set.constr.type(AirlineConnecting, rep("<=",8))
set.rhs(AirlineConnecting, c(166,166,80,120,75,100,60,110))
set.objfn(AirlineConnecting, c(428,190,642,224,512,190))
lp.control(AirlineConnecting,sense='max')

# 模型稍微有点大
Model name: 
        C1    C2    C3    C4    C5    C6         
Maximize   428   190   642   224   512   190         
R1           1     1     1     1     0     0  <=  166
R2           1     1     0     0     1     1  <=  166
R3           1     0     0     0     0     0  <=   80
R4           0     1     0     0     0     0  <=  120
R5           0     0     1     0     0     0  <=   75
R6           0     0     0     1     0     0  <=  100
R7           0     0     0     0     1     0  <=   60
R8           0     0     0     0     0     1  <=  110
Kind       Std   Std   Std   Std   Std   Std         
Type      Real  Real  Real  Real  Real  Real         
Upper      Inf   Inf   Inf   Inf   Inf   Inf         
Lower        0     0     0     0     0     0

solve(AirlineConnecting)
get.objective(AirlineConnecting)
get.variables(AirlineConnecting)