目录

• 数学问题：线性规划问题
• • 程序设计
  • 结果分析
• 实际应用1：加工厂的生产计划
• • 设置未知数
  • 建立数学模型
  • 程序设计
  • 结果分析
• 实际应用2：油料加工厂的采购和加工计划
• • 设置未知数
  • 建立数学模型
  • 程序设计
  • 结果分析
• 遗留的问题
• • 钢管加工用料问题
  • 分析
  • scipy.optimize.linprog()的缺陷？

本博客参考：

1. 《python数学实验与建模》
2. 《MATLAB数学建模经典案例实战》

数学问题：线性规划问题

maxz=8x1−2x2+3x3−x4−2x5{x1+x2+x3+x4+x5≤400x1+2x2+2x3+x4+6x5≤8002x1+x2+6x3≤200x3+x4+55≤2000≤xi≤99,i=1,2,3,4x5≥−10max \ z=8x_1-2x_2+3x_3-x_4-2x_5\\ \left\{ \begin{aligned} &x_1+x_2+x_3+x_4+x_5\leq 400\\ & x_1+2x_2+2x_3+x_4+6x_5\leq800\\ &2x_1+x_2+6x_3\leq200\\ &x_3+x_4+5_5\leq200\\ &0\leq x_i\leq99,i=1,2,3,4\\ &x_5\geq-10\\ \end{aligned} \right. max z=8x1​−2x2​+3x3​−x4​−2x5​⎩⎨⎧​​x1​+x2​+x3​+x4​+x5​≤400x1​+2x2​+2x3​+x4​+6x5​≤8002x1​+x2​+6x3​≤200x3​+x4​+55​≤2000≤xi​≤99,i=1,2,3,4x5​≥−10​

程序设计

from scipy.optimize import linprogc=[-8,2,-3,1,2]
A=[[1,1,1,1,1],[1,2,2,1,6],[2,1,6,0,0],[0,0,1,1,5]]
b=[[400],[800],[200],[200]]
aeq=None
beq=None
bounds=((0, 99),(0, 99),(0, 99),(0, 99),(-10,None))
res=linprog(c=c, A_ub=A, b_ub=b, A_eq=aeq, b_eq=beq, bounds=bounds,)

运行结果

结果分析

从中我们看出，目标函数z的最大值应为823左右，此时决策变量x1−x5x_1-x_5x1​−x5​的值分别为[99,0,0.3,0,-10]

实际应用1：加工厂的生产计划

一家加工厂使用牛奶生产A,B两种奶制品，1桶牛奶经甲机器加工12小时得到3kgA，也可以经过乙机器8小时得到4kgB，根据市场需求，生产的A、B可以全部出售并且每kgA获利24元、每kgB获利16元。现在该工厂每天获得50桶牛奶供应，所有工人的最大劳动时间之和为480x小时，甲机器每天最多加工100kgA，乙机器加工不限量，请你为该工厂设计生产计划，使得每天的利润最大

设置未知数

假设每天用于生产A产品的牛奶为x1x_1x1​桶，用于生产B产品的牛奶为x2x_2x2​桶，每天的利润为zzz元，根据题意建立数学模型

建立数学模型

maxz=3∗24x1+4∗16x2{x1+x2≤5012x1+8x2≤8003x1≤100x1≥0,x2≥0max \ z=3*24x_1+4*16x_2\\ \left\{ \begin{aligned} x_1+x_2\leq 50\\ 12x_1+8x_2\leq800\\ 3x_1\leq100\\ x_1\geq0,x_2\geq0 \end{aligned} \right. max z=3∗24x1​+4∗16x2​⎩⎨⎧​x1​+x2​≤5012x1​+8x2​≤8003x1​≤100x1​≥0,x2​≥0​
转化为标准形式
minz=−3∗24x1−4∗16x2{x1+x2≤5012x1+8x2≤8003x1≤100x1≥0,x2≥0min \ z=-3*24x_1-4*16x_2\\ \left\{ \begin{aligned} x_1+x_2\leq 50\\ 12x_1+8x_2\leq800\\ 3x_1\leq100\\ x_1\geq0,x_2\geq0 \end{aligned} \right. min z=−3∗24x1​−4∗16x2​⎩⎨⎧​x1​+x2​≤5012x1​+8x2​≤8003x1​≤100x1​≥0,x2​≥0​

程序设计

from scipy.optimize import linprog
c=[-72,-64]
A=[[1,1],[12,8]]
b=[[50],[480]]
bounds=((0,100/3.0),(0,None))res=linprog(c=c, A_ub=A, b_ub=b, A_eq=None, b_eq=None, bounds=bounds) 

运行结果

结果分析

从上面我们可以看出，利润最大值在3360元左右，达到最大值时，A、B产品的牛奶日用量分别是20桶、30桶

实际应用2：油料加工厂的采购和加工计划

某加工厂加工一种油，原料为五种油（植物油1，植物油2、非植物油1，非植物油2、非植物油3），每种油的价格、硬度如图表所示，最终生产的成品将以150英镑/吨

每个月能够提炼的植物油不超过200吨、非植物油不超过250吨，假设提炼过程中油料没有损失，提炼费用忽略不计，并且最终的产品的硬度需要在（3-6）之间（假设硬度的混合时线性的）。根据以上信息，请你为加工厂指定月采购和加工计划

设置未知数

假设x1,x2,x3,x4,x5x_1,x_2,x_3,x_4,x_5x1​,x2​,x3​,x4​,x5​分别为每月需要采购的原料油吨数，x6x_6x6​为每个月加工的成品油吨数，根据题意建立数学模型

建立数学模型

maxz=−110x1−120x2−130x3−110x4−115x5+150x6{x1+x2≤200x3+x4+x5≤2508.8x1+6.1x2+2.0x3+4.2x4+5.0x5≤6x68.8x1+6.1x2+2.0x3+4.2x4+5.0x5≥3x6x1+x2+x3+x4+x5=x6xi≥0,i=1,2,3,...,6max \ z=-110x_1-120x_2-130x_3-110x_4-115x_5+150x_6\\ \left\{ \begin{aligned} x_1+x_2\leq 200\\ x_3+x_4+x_5\leq250\\ 8.8x_1+6.1x_2+2.0x_3+4.2x_4+5.0x_5\leq6x_6\\ 8.8x_1+6.1x_2+2.0x_3+4.2x_4+5.0x_5\geq3x_6\\ x_1+x_2+x_3+x_4+x_5=x_6\\ x_i\geq0,i=1,2,3,...,6 \end{aligned} \right. max z=−110x1​−120x2​−130x3​−110x4​−115x5​+150x6​⎩⎨⎧​x1​+x2​≤200x3​+x4​+x5​≤2508.8x1​+6.1x2​+2.0x3​+4.2x4​+5.0x5​≤6x6​8.8x1​+6.1x2​+2.0x3​+4.2x4​+5.0x5​≥3x6​x1​+x2​+x3​+x4​+x5​=x6​xi​≥0,i=1,2,3,...,6​

程序设计

from scipy.optimize import linprogc=[110,120,130,110,115,-150]
A=[[1,1,0,0,0,0],[0,0,1,1,1,0],[8.8,6.1,2.0,4.2,5.0,-6],[-8.8,-6.1,-2.0,-4.2,-5.0,3]]
b=[[200],[250],[0],[0]]
aeq=[[1,1,1,1,1,-1]]
beq=[[0]]
bounds=((0, None),(0, None),(0, None),(0, None),(0,None),(0,450))
# bounds=((0, None),(0, None),(0, None),(0, None),(0,None),(0,None))
res=linprog(c=c, A_ub=A, b_ub=b, A_eq=aeq, b_eq=beq, bounds=bounds)

运行结果

结果分析

从上面我们可以看到，五种原料油的采购量分别为[159.25,40.7407,0,250,0]（吨），此时总利润可以达到最大，约为17592英镑/月

笔者发现的一个没有用的小技巧：我们知道x6x_6x6​变量代表的是每个月的吨数，bounds参数设置决策变量的取值区间，当在bounds中对x_6的上界不加限制时，即（0,None）,模型返回的结果中仍然将x6x_6x6​收敛至450，你知道这是为什么吗？

遗留的问题

经过这么多的应用，我们已经大致明白了scipy.optimize.linprog()函数的使用过程，也惊叹于它的便利之处，但是不知道你是否能发现该函数的缺点？
我们来看下面一个问题

钢管加工用料问题

某零售商从钢管厂进货后将钢管切割后卖给客户，某次进货该零售商得到了若干1850mm长的原料钢管。现有一客户需要15根290mm、28根315mm、21根350mm、30根455mm的钢管。对于一个原料钢管有四种切割模式，每次切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品），为减少余料浪费，每种切割模式下的余料浪费不能超过100mm。（要完成该客户的需求，需要若干根原料钢管，可能用到四种切割模式，现规定使用频率最多的切割模式按照一根原料钢管价格的1/10收取加工费，使用频率次之的切割模式按照一根原料钢管价格的2/10收取加工费，依次类推）。现在求使得该零售商总费用最小的切割计划？

分析

仔细分析我们会发现，这个问题的线性规划和上面的两个实际问题有很大不同。

在上面的问题中，决策变量只有一种x1−xnx_1-x_nx1​−xn​，而且决策变量的系数的都是常数（比如x3+x4+x5≤250x_3+x_4+x_5\leq250x3​+x4​+x5​≤250中的每个自变量系数都是1）。但是在该问题中似乎有两种决策变量：切割模式的使用频次xix_ixi​、每种切割模式下对于一根原料钢管产生的成品钢管种类及数量rijr_{ij}rij​（i表示第i种切割模式，j表示第j种成品钢管）。

scipy.optimize.linprog()的缺陷？

这就让我们在列举约束条件时遇到了很大的困难，比如其中一个不等式是这样的∑i=14xi×r1i≥15(i=1...4)\sum^4_{i=1}x_i\times r_{1i}\geq15(i=1...4)∑i=14​xi​×r1i​≥15(i=1...4)，看到这里我们发现两个决策变量相乘，如果继续使用scipy.optimize.linprog()函数，参数A_ub怎么取？参数bounds到底该以谁作为决策变量？

现在我们似乎遇到了困难，实际上并不是linprog()函数的问题，因为函数就是用来求解线性规划问题的，而我们现在提出的这个问题是一个非线性规划问题，所以，要解决它我们需要“另辟蹊径”了！下一个博客我们将用另外一个第三方库解决这个问题