如何用Python解决最优化问题?

看书的时候刚好发现一个案例——要求优化投放广告渠道的资源,以最大化产品咨询量。

现有5个广告投放渠道,分别是日间电视、夜间电视、网络媒体、平面媒体、户外广告,每个渠道的效果、费用及限制如下表所示:

注:案例来自《活用数据:驱动业务的数据分析实战》,作者陈哲

比如日间电视这个渠道,每做一次投放需要费用1000元,可以触达2000个用户(曝光量),带来咨询量600个(也可以看做app下载量等目标产出),该广告渠道最多投放14次。

除了表格中的限制条件外,还要求:

  • 电视广告至少投放20次(包括日间和夜间);
  • 触达用户数(曝光量)不少于10万;
  • 电视广告投入费用不超过3万元;

现在公司总共给到4万的营销费用,要求咨询量能最大化。

这是一个线性规划问题,即在有限的资源(约束条件)下如何使效用(线性目标函数)最大化。

注:关于线性规划更多可参考https://www.math.ucla.edu/~tom/LP.pdf

把5个广告渠道各自能使用的次数作为决策变量,分别用

来表示

那么,现在要优化的目标函数是

约束条件:

  • 电视广告投放至少20次,

  • 用户曝光量至少10万,
  • 电视广告费用不超过3万,
  • 总广告费用不超过4万,
  • 投放次数为正整数,且

注:在《活用数据》一书中,对该优化问题的求解过程用Excel进行了演示,感兴趣的朋友可以参考书中内容。

以下用Python来完成对该线性规划问题的求解,比较常用的两个模块是:

  • scipy.optimize.linprog https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
  • PuLP https://pythonhosted.org/PuLP/index.html

因为事先就安装了Anaconda,所以先试试scipy模块下的scipy.optimize.linprog函数来跑数据。

函数的参数说明(如下截图)

调用该函数需要注意的点:

  • 这个函数只做“最小化”的优化,如果要做“最大化”,在目标函数上取负值就行,本文中的例子就是要找“最大值”;
  • 等式和不等式两类约束条件是分开的,分别对应两组参数A,b(注意下标的含义);
  • 这里的不等式要求<=,如果约束条件中出现>=则在两边乘以-1以调换方向;
  • 注意在矩阵A中补齐参数为0的情况,比如一共5个决策变量,有个约束条件是-x1-x2<=-20,对应的参数array是[-1,-1,0,0,0];

话不多说,上代码

from scipy import optimize

# 需要优化的函数对应的参数list
c = [-600,-800,-500,-400,-300]

# 不等式对应参数矩阵
A = [[1000,2000,0,0,0]\
    ,[-1,-1,0,0,0]\
    ,[1000,2000,400,1000,100]\
    ,[-2000,-4000,-3000,-5000,-600]]

# 不等式对应的上界
b = [30000,-20,40000,100000]

#各参数的取值范围,
x1_bd = (0,14)
x2_bd = (0,8)
x3_bd = (0,40)
x4_bd = (0,5)
x5_bd = (0,50)

# 调用函数
optimize.linprog(c, A_ub=A, b_ub=b, bounds=[x1_bd,x2_bd,x3_bd,x4_bd,x5_bd])

输出的结果如下:

从message以及success那里都有提示,迭代终止且已经找到了最优值。

fun 就是优化得到的最大值(需要取绝对值),x 是达到最优值的时候各决策变量的取值。

不过,这里有个问题——那就是我们的决策变量“投放广告的次数”的取值为正整数,但是决策变量x3的取值是22.5,不是整数呢。scipy.optimize.linprog函数应该是不支持取整数值的操作的,怎么办?有一种方法是取22.5相邻的整数(也就是22或者23)带入原有程序中看哪种条件下值最优。

接下来出场的工具包是PuLP,PuLP的参数风格非常直观,不信?看代码:

from pulp import *

prob = LpProblem('营销优化问题',LpMaximize)

# 变量定义,注意最后的LpInteger,当设置该参数时,则该决策变量只能取整数
# 如果决策变量可以取小数,那就设置为LpContinuous
x1 = LpVariable('日间电视',0,14,LpInteger)
x2 = LpVariable('夜间电视',0,8,LpInteger)
x3 = LpVariable('网络媒体',0,40,LpInteger)
x4 = LpVariable('平面媒体',0,5,LpInteger)
x5 = LpVariable('户外广告',0,50,LpInteger)

# 需要优化的表达式
prob += 600*x1+800*x2+500*x3+400*x4+300*x5

# 约束条件
prob += 1000*x1 + 2000*x2 <= 30000, '电视广告费用不超过3万'
prob += x1+x2 >= 20, '电视广告至少20次'
prob += 1000*x1+2000*x2+400*x3+1000*x4+100*x5 <= 40000, '广告总费用不超过4万'
prob += 2000*x1+4000*x2+3000*x3+5000*x4+600*x5 >= 100000,'曝光人数不少于10万'

#lp文件保存该优化问题的信息,可以用文本编辑器打开
prob.writeLP("营销优化问题.lp")

# 执行计算
prob.solve()

# 如果成功得到了最优值,则会输出 Optimal
print(LpStatus[prob.status])

# 得到最优值时,各决策变量的取值,如果没有找到最优值,则输出None
for v in prob.variables():
    print(v.name, "=", v.varValue)

# 输出最优值,如果没有找到最优值,则输出None
print("最大咨询量为", value(prob.objective))

输出结果:

可以看到最优值为39200,对应的决策变量的取值均为整数。

PuLP的代码量看着虽然多,但是相对于scipy.optimize.linprog函数,PuLP的代码非常灵活,而且很直观,对参数取值是整数或者小数还有细分。如果要用Python来做线性规划问题,建议使用PuLP模块。

原文发布于微信公众号 - 数据分析1480(lsxxx2011)

原文发表时间:2019-05-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券