wen Python小白的数学建模课-04.整数规划
整数规划与线性规划的差别只是变量的整数约束。
问题区别一点点，难度相差千万里。
选择简单通用的编程方案，让求解器去处理吧。
『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。
1. 从线性规划到整数规划
1.1 为什么会有整数规划？
线性规划问题的最优解可能是分数或小数。整数规划是指变量的取值只能是整数的规划。
这在实际问题中很常见，例如车间人数、设备台数、行驶次数，这些变量显然必须取整数解。
整数规划并不一定是线性规划问题的变量取整限制，对于二次规划、非线性规划问题也有变量取整限制而引出的整数规划。但在数学建模问题中所说的整数规划，通常是指整数线性规划。
根据对变量的不同情况，整数规划又可以分为：
- 完全整数规划，全部变量都要求是整数；
- 混合整数规划，部分变量要求是整数；
- 0-1整数规划，变量的取值只能是 0 或 1；
- 混合0-1规划，部分变量的取值只能是 0 或 1。
0-1整数规划 是非常重要也非常特殊的整数规划，需要在另外的文章进行讨论。
1.2 四舍五入就能得到整数解吗？
整数规划问题与线性规划问题的区别只是增加了整数约束。这看上去好像只要把线性规划得到的非整数解舍入化整，就可以得到整数解，并不是多么复杂的问题。
但是问题并没有这么简单。化整后的解不仅不一定是最优解，甚至不一定是可行解的——线性规划的最优解，取整后可能就不满足约束条件了。
那么，不要按四舍五入取整，而是向满足约束条件的方向取整，是不是就可以呢？这是很好的想法，通常这样可以获得可行解，但却不一定是最优解了。
因此，整数规划问题比线性规划复杂的多，以至于至今还没有通用的多项式解法，也就是说算法复杂度与问题规模成指数关系（NP问题）。还没有意识到与问题规模指数关系意味着什么吗？就是那个在象棋棋盘上放麦子，每格比前一格加倍的故事。
问题区别一点点，难度却相差千万里。小白与学霸，差距其实并不大。
欢迎关注 『Python小白的数学建模课 @ Youcans』，每周更新数模笔记
Python小白的数学建模课-01.新手必读
Python小白的数学建模课-02.数据导入
Python小白的数学建模课-03.线性规划
Python小白的数学建模课-04.整数规划
Python数模笔记-PuLP库
Python数模笔记-StatsModels统计回归
Python数模笔记-Sklearn
Python数模笔记-NetworkX
Python数模笔记-模拟退火算法
2. 整数规划的求解方法
2.1 分支定界法（Branch and bound）
分支定界法的基本思想是把原问题（整数规划问题）转换为一个个线性规划问题来处理，并在求解这些线性规划问题的过程中不断追踪原问题的上界（最优可行解）和下界（最优线性松弛解）。
分支定界法把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标上界，称为定界。每次分枝后，对于超出已知可行解集目标值的那些子集不再进一步分枝，就可以删减很多子集，这称为剪枝。
数学课代表的说法是：设有最大化的整数规划问题 A，先解与之相应的线性规划问题 B，若 B 的最优解不符合 A 的整数条件，则 B 的最优目标函数必是 A 的最优目标函数 z 的上界，记为 z2，而 A 的任意可行解的目标函数值将是 z 的一个下界 z1。分支定界法就是将 B 的可行域分成子区域（分支）的方法，逐步减小 z2 和增大 z1，最终求到 z*。
分支定界法是一个迭代算法，随着迭代过程不断更新上界和下界，直到上界和下界非常接近时结束。通常设置 Gap < 0.1%，就可把当前的最优可行解近似为问题的全局最优解了。因此，分支定界法的“收敛” 不是分析意义上的而是算法意义上的，优化结果是近似解而不是精确解。
分支定界法不用区分完全整数规划与混合整数规划，算法便于实现，但计算量比较大。
2.2 割平面法（Cutting plane）
割平面法的基本思路是先求解普通线性规划问题的最优解，再对非整数解添加约束条件使可行域缩小，如此反复求解添加了约束条件的普通线性规划问题，直到得到整数解。
也就是说，先不考虑整数约束条件，直接求解松弛问题的最优解，如果满足整数条件就结束了，如果不满足整数条件，就在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件称为割平面，对松弛问题的可行域割一刀，割去松弛问题的部分非整数解。经过有限次的反复切割，必定可在缩小的可行域的一个整数极点上达到整数规划问题的最优解 。
割平面法的计算量比较小，但对问题的结构及求解的要求较高，算法比较复杂。
2.3 整数规划的编程方案
在各种算法的介绍和评价中，有时会说“算法比较简单，编程比较容易”。对此小白千万不要当真。不论分支定界法还是割平面法，小白不要说自己按照算法步骤一步步编程实现，就是给你现成的程序估计你也看不懂的。这很正常，就算大神也没几个人能看懂哪怕是自己写出来的算法。
但是如果给你程序也不会使用，那就是问题了。不幸的是，这是数学建模学习和参赛中经常遇到的问题：有了调试好的程序，例程运行结果也正常，但换个问题仍然不会使用。
这并不是你的错。程序有漏洞，接口不标准，文档对不上，教程说不清，这就是你所拿到的例程。你的错误，是选择了这样的例程，或者说选择了这样的编程方案。
这也是本系列教程希望解决的问题。就拿线性规划、整数规划来说，算法还不是很复杂，第三方软件包也很丰富。但是，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.:egin{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}
]
