怎么做网站投票选举,ios开发软件,wordpress聚合页面,seo优化排名工具整数规划与线性规划的差别只是变量的整数约束。
问题区别一点点#xff0c;难度相差千万里。
选择简单通用的编程方案#xff0c;让求解器去处理吧。
『Python小白的数学建模课 Youcans』带你从数模小白成为国赛达人。 1. 从线性规划到整数规划
1.1 为什么会有整数规划难度相差千万里。
选择简单通用的编程方案让求解器去处理吧。
『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小白的数学建模课-05.0-1规划 Python小白的数学建模课-06.固定费用问题 Python小白的数学建模课-07.选址问题 Python小白的数学建模课-09.微分方程模型 Python小白的数学建模课-10.微分方程边值问题 Python小白的数学建模课-12.非线性规划 Python小白的数学建模课-15.图论的基本概念 Python小白的数学建模课-16.最短路径算法 Python小白的数学建模课-17.条件最短路径算法 Python小白的数学建模课-18.最小生成树问题 Python小白的数学建模课-19.网络流优化问题 Python小白的数学建模课-20.网络流优化案例 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。
maxf(x)10∗x19∗x2s.t.:{6∗x15∗x2≤6010∗x120∗x2≤1500≤x1≤8x2≥0max\;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} maxf(x)10∗x19∗x2s.t.:⎩⎪⎪⎪⎨⎪⎪⎪⎧6∗x15∗x2≤6010∗x120∗x2≤1500≤x1≤8x2≥0
进一步分析决策变量取值范围的约束条件由原料数量、工人数量的不等式约束可以推出 x1≤15x2≤7.5x_1 \leq 15\\ x_2 \leq 7.5 x1≤15x2≤7.5
对于问题 2可以通过增加投资来获得更多的原料投资额是一个新的变量。要注意的是此时目标函数虽然也是生产两种饮料的总利润但总利润不等于总收入而是总收入减去总成本在本例中就是要减去购买原料的投资。
maxf(x)10∗x19∗x2−x3s.t.:{6∗x15∗x2≤60x3/0.810∗x120∗x2≤1500≤x1≤150≤x2≤7.5x3≥0max\;f(x) 10*x_1 9*x_2 - x_3\\ s.t.:\begin{cases} 6*x_1 5*x_2 \leq 60 x_3/0.8\\ 10*x_1 20*x_2 \leq 150\\ 0 \leq x_1 \leq 15\\ 0 \leq x_2 \leq 7.5\\ x_3 \geq 0 \end{cases} maxf(x)10∗x19∗x2−x3s.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧6∗x15∗x2≤60x3/0.810∗x120∗x2≤1500≤x1≤150≤x2≤7.5x3≥0
对于问题 3 和问题 4区别只是不允许散箱明确提出了决策变量 x1、x2 的取值要取整数值所以是整数规划问题。 需要注意的是问题 4 中对增加的投资额即购买的原料数量并没有整数限制因此 x1、x2 的取值范围是正整数但 x3 的取值范围是正数这是一个混合整数规划问题。 还要说明的是对于问题 1 和问题 2虽然题目中没有明确要求生产甲、乙饮料的工人人数为整数但是人数也不可能是小数的那么这是不是也是整数规划问题呢 如果你能提出这个问题那么恭喜你你已经从小白升级为菜鸟了。 我的理解是这个问题怎么说都可以。如果要简化问题使用线性规划模型最好在问题假设中说一句假设甲乙饮料在同一车间先后生产只要允许甲乙饮料散箱生产即使根据产量所求出的工人数是小数也可以解释的通。如果你掌握了整数规划问题的求解那就先按线性规划建模再补充讨论工人人数也必须是整数的条件按整数规划建模求解这就是妥妥的获奖论文了。 3.2.3 模型求解
模型求解用标准模型的优化算法对模型求解得到优化结果。
在线性规划问题中已经讲过使用 PuLP 的求解步骤
0导入 PuLP库函数 import pulp1定义一个规划问题 ProbLP1 pulp.LpProblem(ProbLP1, sensepulp.LpMaximize) # 定义问题 1求最大值pulp.LpProblem 用来定义问题的构造函数。ProbLP1是用户定义的问题名。 参数 sense 指定问题求目标函数的最小值/最大值 。本例求最大值选择 “pulp.LpMaximize” 。
2定义决策变量 对于问题 1 x1 pulp.LpVariable(x1, lowBound0, upBound15, catContinuous) # 定义 x1x2 pulp.LpVariable(x2, lowBound0, upBound7.5, catContinuous) # 定义 x2pulp.LpVariable 用来定义决策变量的函数。‘x1’、‘x2’ 是用户定义的变量名。 参数 lowBound、upBound 用来设定决策变量的下界、上界可以不定义下界/上界默认的下界/上界是负无穷/正无穷。本例中 x1、x2 的取值区间分别为 [0,15]、[0,7.5]。 参数 cat 用来设定变量类型可选参数值‘Continuous’ 表示连续变量默认值、’ Integer ’ 表示离散变量用于整数规划问题、’ Binary ’ 表示0/1变量用于0/1规划问题。
对于问题 3 甲乙饮料产量 x1、x2 必须取整数是整数规划问题因此要设置变量类型为离散变量整数变量 x1 pulp.LpVariable(x1, lowBound0, upBound15, catInteger) # 定义 x1变量类型整数x2 pulp.LpVariable(x2, lowBound0, upBound7.5, catInteger) # 定义 x2变量类型整数3添加目标函数 ProbLP1 (10*x1 9*x2) # 设置目标函数 f(x)添加目标函数使用 “问题名 目标函数式” 格式。
4添加约束条件 ProbLP1 (6*x1 5*x2 60) # 不等式约束ProbLP1 (10*x1 20*x2 150) # 不等式约束添加约束条件使用 “问题名 约束条件表达式” 格式。 约束条件可以是等式约束或不等式约束不等式约束可以是 小于等于 或 大于等于分别使用关键字、“和”。
5求解 ProbLP1.solve()print(ProbLP1.name) # 输出求解状态print(Status:, pulp.LpStatus[ProbLP1.status]) # 输出求解状态for v in ProbLP1.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(F1(x) , pulp.value(ProbLP1.objective)) # 输出最优解的目标函数值solve() 是求解函数可以对求解器、求解精度进行设置。 PuLP默认采用 CBC 求解器来求解优化问题也可以调用其它的优化器来求解但需要另外安装。 3.3 Python 例程
# mathmodel05_v1.py
# Demo05 of mathematical modeling algorithm
# Solving integer programming with PuLP.
# Copyright 2021 Youcans, XUPT
# Crated2021-05-31
# Python小白的数学建模课 Youcansimport pulp # 导入 pulp 库# 主程序
def main():# 模型参数设置问题描述某厂生产甲乙两种饮料每百箱甲饮料需用原料6千克、工人10名获利10万元每百箱乙饮料需用原料5千克、工人20名获利9万元。今工厂共有原料60千克、工人150名又由于其他条件所限甲饮料产量不超过8百箱。1问如何安排生产计划即两种饮料各生产多少使获利最大2若投资0.8万元可增加原料1千克是否应作这项投资投资多少合理3若不允许散箱按整百箱生产如何安排生产计划即两种饮料各生产多少使获利最大4若不允许散箱按整百箱生产若投资0.8万元可增加原料1千克是否应作这项投资投资多少合理# 问题 1问题建模决策变量x1甲饮料产量单位百箱x2乙饮料产量单位百箱目标函数max fx 10*x1 9*x2约束条件6*x1 5*x2 6010*x1 20*x2 150 x1, x2 0x1 8此外由 x1,x20 和 10*x120*x2150 可知 0x27.5ProbLP1 pulp.LpProblem(ProbLP1, sensepulp.LpMaximize) # 定义问题 1求最大值x1 pulp.LpVariable(x1, lowBound0, upBound8, catContinuous) # 定义 x1x2 pulp.LpVariable(x2, lowBound0, upBound7.5, catContinuous) # 定义 x2ProbLP1 (10*x1 9*x2) # 设置目标函数 f(x)ProbLP1 (6*x1 5*x2 60) # 不等式约束ProbLP1 (10*x1 20*x2 150) # 不等式约束ProbLP1.solve()print(ProbLP1.name) # 输出求解状态print(Status youcans:, pulp.LpStatus[ProbLP1.status]) # 输出求解状态for v in ProbLP1.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(F1(x) , pulp.value(ProbLP1.objective)) # 输出最优解的目标函数值# 问题 2问题建模决策变量x1甲饮料产量单位百箱x2乙饮料产量单位百箱x3增加投资单位万元目标函数max fx 10*x1 9*x2 - x3约束条件6*x1 5*x2 60 x3/0.810*x1 20*x2 150x1, x2, x3 0x1 8此外由 x1,x20 和 10*x120*x2150 可知 0x27.5ProbLP2 pulp.LpProblem(ProbLP2, sensepulp.LpMaximize) # 定义问题 2求最大值x1 pulp.LpVariable(x1, lowBound0, upBound8, catContinuous) # 定义 x1x2 pulp.LpVariable(x2, lowBound0, upBound7.5, catContinuous) # 定义 x2x3 pulp.LpVariable(x3, lowBound0, catContinuous) # 定义 x3ProbLP2 (10*x1 9*x2 - x3) # 设置目标函数 f(x)ProbLP2 (6*x1 5*x2 - 1.25*x3 60) # 不等式约束ProbLP2 (10*x1 20*x2 150) # 不等式约束ProbLP2.solve()print(ProbLP2.name) # 输出求解状态print(Status youcans:, pulp.LpStatus[ProbLP2.status]) # 输出求解状态for v in ProbLP2.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(F2(x) , pulp.value(ProbLP2.objective)) # 输出最优解的目标函数值# 问题 3整数规划问题问题建模决策变量x1甲饮料产量正整数单位百箱x2乙饮料产量正整数单位百箱目标函数max fx 10*x1 9*x2约束条件6*x1 5*x2 6010*x1 20*x2 150x1, x2 0x1 8x1, x2 为整数此外由 x1,x20 和 10*x120*x2150 可知 0x27.5ProbLP3 pulp.LpProblem(ProbLP3, sensepulp.LpMaximize) # 定义问题 3求最大值print(ProbLP3.name) # 输出求解状态x1 pulp.LpVariable(x1, lowBound0, upBound8, catInteger) # 定义 x1变量类型整数x2 pulp.LpVariable(x2, lowBound0, upBound7.5, catInteger) # 定义 x2变量类型整数ProbLP3 (10 * x1 9 * x2) # 设置目标函数 f(x)ProbLP3 (6 * x1 5 * x2 60) # 不等式约束ProbLP3 (10 * x1 20 * x2 150) # 不等式约束ProbLP3.solve()print(Shan Status:, pulp.LpStatus[ProbLP3.status]) # 输出求解状态for v in ProbLP3.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(F3(x) , pulp.value(ProbLP3.objective)) # 输出最优解的目标函数值# 问题 4问题建模决策变量x1甲饮料产量正整数单位百箱x2乙饮料产量正整数单位百箱x3增加投资单位万元目标函数max fx 10*x1 9*x2 - x3约束条件6*x1 5*x2 60 x3/0.810*x1 20*x2 150x1, x2, x3 0x1 8x1, x2 为整数此外由 x1,x20 和 10*x120*x2150 可知 0x27.5ProbLP4 pulp.LpProblem(ProbLP4, sensepulp.LpMaximize) # 定义问题 4求最大值print(ProbLP4.name) # 输出求解状态x1 pulp.LpVariable(x1, lowBound0, upBound8, catInteger) # 定义 x1变量类型整数x2 pulp.LpVariable(x2, lowBound0, upBound7, catInteger) # 定义 x2变量类型整数x3 pulp.LpVariable(x3, lowBound0, catContinuous) # 定义 x3ProbLP4 (10*x1 9*x2 - x3) # 设置目标函数 f(x)ProbLP4 (6*x1 5*x2 - 1.25*x3 60) # 不等式约束ProbLP4 (10*x1 20*x2 150) # 不等式约束ProbLP4.solve()print(Shan Status:, pulp.LpStatus[ProbLP4.status]) # 输出求解状态for v in ProbLP4.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(F4(x) , pulp.value(ProbLP4.objective)) # 输出最优解的目标函数值returnif __name__ __main__: # Copyright 2021 YouCans, XUPTmain() # Python小白的数学建模课 Youcans3.4 Python 例程运行结果
Welcome to the CBC MILP Solver
Version: 2.9.0
Build Date: Feb 12 2015 ProbLP1
Status: Optimal
x1 6.4285714
x2 4.2857143
F1(x) 102.8571427ProbLP2
Status: Optimal
x1 8.0
x2 3.5
x3 4.4
F2(x) 107.1ProbLP3
Result - Optimal solution found
Status Shan: Optimal
Status: Optimal
x1 8.0
x2 2.0
F3(x) 98.0ProbLP4
Result - Optimal solution found
Status: Optimal
x1 8.0
x2 3.0
x3 2.4
F4(x) 104.6【本节完】 版权说明
欢迎关注『Python小白的数学建模课 Youcans』 原创作品
原创作品转载必须标注原文链接(https://blog.csdn.net/youcans/article/details/117419635)
Copyright 2021 Youcans, XUPT
Crated2021-05-31 欢迎关注 『Python小白的数学建模课 Youcans』 系列持续更新 Python小白的数学建模课-01.新手必读 Python小白的数学建模课-02.数据导入 Python小白的数学建模课-03.线性规划 Python小白的数学建模课-04.整数规划 Python小白的数学建模课-05.0-1规划 Python小白的数学建模课-06.固定费用问题 Python小白的数学建模课-07.选址问题 Python小白的数学建模课-09.微分方程模型 Python小白的数学建模课-10.微分方程边值问题 Python小白的数学建模课-12.非线性规划 Python小白的数学建模课-15.图论的基本概念 Python小白的数学建模课-16.最短路径算法 Python小白的数学建模课-17.条件最短路径算法 Python小白的数学建模课-18.最小生成树问题 Python小白的数学建模课-19.网络流优化问题 Python小白的数学建模课-20.网络流优化案例 Python小白的数学建模课-A1.国赛赛题类型分析 Python小白的数学建模课-A2.2021年数维杯C题探讨 Python小白的数学建模课-A3.12个新冠疫情数模竞赛赛题及短评 Python小白的数学建模课-B2. 新冠疫情 SI模型 Python小白的数学建模课-B3. 新冠疫情 SIS模型 Python小白的数学建模课-B4. 新冠疫情 SIR模型 Python小白的数学建模课-B5. 新冠疫情 SEIR模型 Python小白的数学建模课-B6. 新冠疫情 SEIR改进模型 Python数模笔记-PuLP库 Python数模笔记-StatsModels统计回归 Python数模笔记-Sklearn Python数模笔记-NetworkX Python数模笔记-模拟退火算法
