在各种算法的介绍和评价中,有时会说“算法比较简单,编程比较容易”。对此小白千万不要当真。不论分支定界法还是割平面法,小白不要说自己按照算法步骤一步步编程实现,就是给你现成的程序估计你也看不懂的。这很正常,就算大神也没几个人能看懂哪怕是自己写出来的算法。
但是如果给你程序也不会使用,那就是问题了。不幸的是,这是数学建模学习和参赛中经常遇到的问题:有了调试好的程序,例程运行结果也正常,但换个问题仍然不会使用。
这并不是你的错。程序有漏洞,接口不标准,文档对不上,教程说不清,这就是你所拿到的例程。你的错误,是选择了这样的例程,或者说选择了这样的编程方案。
这也是本系列教程希望解决的问题。就拿线性规划、整数规划来说,算法还不是很复杂,第三方软件包也很丰富。但是,Scipy 只能求解线性规划,不能求解整数规划,如果选择 Scipy 做线性规划,那在学整数规划时就要再学另一种工具包,二者的模型描述、函数定义、参数设置肯定也是不同的。接下来遇到非线性规划问题再学一种软件包,最后别说熟练掌握算法函数,连什么时候该用哪个 工具包都搞晕了。
闲话少说,我们还是用上节求解线性规划问题的 PuLP 工具包。
3. PuLP 求解整数规划问题
我们不仅继续用 PuLP 工具包,而且解题过程和编程步骤也与求解线性规划问题完全一致。
下面我们以一个简单的数学模型练习,来讲解整个解题过程,而不仅给出例程。
3.1 案例问题描述例题 1:
某厂生产甲乙两种饮料,每百箱甲饮料需用原料 6千克、工人 10名,获利 10万元;每百箱乙饮料需用原料 5千克、工人 20名,获利 9万元。
今工厂共有原料 60千克、工人 150名,又由于其他条件所限甲饮料产量不超过8百箱。
问题 1:问如何安排生产计划,即两种饮料各生产多少使获利最大?
问题 2:若投资0.8万元可增加原料1千克,是否应作这项投资?投资多少合理?
问题 3:若不允许散箱(按整百箱生产),如何安排生产计划,即两种饮料各生产多少使获利最大?
问题 4:若不允许散箱(按整百箱生产),若投资0.8万元可增加原料1千克,是否应作这项投资?投资多少合理?
3.2 建模过程分析
线性规划和整数规划类的问题的建模和求解,通常可以按问题定义、模型构建、模型求解的步骤进行。
3.2.1 问题定义问题定义, 确定决策变量、目标函数和约束条件。
决策变量是问题中可以在一定范围内进行变化而获得不同结果的变量。
对于问题 1,问题描述中说的很明确,希望通过改变甲、乙两种饮料的产量使总利润最大,甲、乙两种饮料的产量就是决策变量。
对于问题 2 则要注意,如果只看前一句,就是比较问题 1 与问题 2 的利润,还是把甲、乙两种饮料的产量作为决策变量。但要回答后一句“投资多少合理”,这就出现了一个新的变量“投资额”,因此对问题 2 要建立 3个决策变量:甲产量、乙产量和投资额。
目标函数是决策变量的函数,我们希望通过改变决策变量的值而获得目标函数的最大值或最小值,通常是总成本(最小)、总利润(最大)、总时间(最短)。
对于本案例,每个问题都是希望获得最大利润,目标函数都是总利润,问题是求目标函数即总利润的最大值。
约束条件是决策变量所要满足的限制条件。
约束条件 3 种情况:
一是不等式约束,例如题目指出共有原料 60千克、工人 150名,因此生产计划所用的原料、工人的需求不能大于题目中数值。
二是等式约束,本题没有等式约束条件。
三是决策变量取值范围的约束。
通常,题目隐含着决策变量大于等于 0 的条件,例如工人人数、原料数量都要大于等于 0。
另外,如果能通过分析前面的等式约束或不等式约束,得出决策变量的上限,将会极大的提高问题求解的速度和性能。后文将对此举例说明。
3.2.2 模型构建
模型构建, 由问题描述建立数学方程,并转化为标准形式的数学模型。
对于问题 1,目标函数是生产甲、乙两种饮料的总利润,约束条件是原料总量、工人总数的约束,而且原料、工人都要大于等于 0。
\[max\;f(x) = 10*x_1 + 9*x_2\\ s.t.:\begin{cases} 6*x_1 + 5*x_2 \leq 60\\ 10*x_1 + 20*x_2 \leq 150\\ 0 \leq x_1 \leq 8\\ x_2 \geq 0 \end{cases} \]