网站推广策略成功的案例,青岛网站制作推广平台,准备网站的工作,如何增加网站关键词库0-1 规划不仅是数模竞赛中的常见题型#xff0c;也具有重要的现实意义。
双十一促销中网购平台要求二选一#xff0c;就是互斥的决策问题#xff0c;可以用 0-1规划建模。
小白学习 0-1 规划#xff0c;首先要学会识别 0-1规划#xff0c;学习将问题转化为数学模型。
『…
0-1 规划不仅是数模竞赛中的常见题型也具有重要的现实意义。
双十一促销中网购平台要求二选一就是互斥的决策问题可以用 0-1规划建模。
小白学习 0-1 规划首先要学会识别 0-1规划学习将问题转化为数学模型。
『Python小白的数学建模课 Youcans』带你从数模小白成为国赛达人。 1. 什么是 0-1 规划
0-1 整数规划是一类特殊的整数规划变量的取值只能是 0 或 1。
0-1 变量可以描述开关、取舍、有无等逻辑关系、顺序关系可以处理背包问题、指派问题、选址问题 、计划安排、线路设计 、人员安排等各种决策规划问题。进而任何整数都可以用二进制表达整数变量就可以表示为多个 0-1 变量的组合因此任何整数规划都可以转化为 0-1 规划问题来处理。0-1 规划问题与运筹学中的很多经典问题也都有紧密联系。
在数学建模学习中0-1 规划主要用于求解互斥的决策问题、互斥的约束条件问题、固定费用问题和分派问题。0-1 规划是数模竞赛的常见题型国赛 B题经常有 0-1规划问题或可以转化为 0-1 规划问题。
0-1 规划的算法都比较复杂大规模问题一般没有精确解法。本文仍然使用 PuLP 工具包求解 0-1 规划问题该工具包的使用比较简单。建议本文读者重点关注 0-1 规划问题的分类及建模方法把握哪些问题是 0-1 规划问题是哪一类的 0-1 规划问题如何对这些典型问题进行建模。在此基础上才能调用 PuLP 函数进行求解。 欢迎关注『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. 0-1 规划的分类及建模方法
规划问题的数学模型包括决策变量、约束条件和目标函数围绕这三个要素都可能存在互斥的情况从而导出不同类型的0-1规划问题其建模方法也有差别。
2.1 互斥的决策问题
互斥的决策问题是指决策方案、计划互斥如决定投资项目、确定投资场所、选择投产产品等。
例如双十一的促销活动淘宝、京东、拼多多要求店铺二选一最多只能选择参加一家平台否则可能会被封杀这是典型的互斥决策问题。
背包问题就是经典的互斥决策问题。给定一组 n 个物品每种物品 i 的价值为 viv_ivi、重量/体积为 wiw_iwi背包所能容纳的总重量/总容量为B如何选择其中若干种物品每种物品选 0 个或 1 个使得物品的总价值最高
背包问题的建模方法如下
定义决策变量为 xi{0不选择第i个物品1选择第i个物品x_i \begin{cases} 0不选择第\;i\;个物品\\ 1选择第\;i\;个物品 \end{cases} xi{0不选择第i个物品1选择第i个物品 定义目标函数为 maxf(x)∑i1nvixis.t.:{∑iinwixi≤B,xi0,1max\;f(x) \sum_{i1}^n v_i x_i\\ s.t.:\begin{cases} \sum_{ii}^n w_i x_i \leq B, \\ x_i 0,1 \end{cases} maxf(x)i1∑nvixis.t.:{∑iinwixi≤B,xi0,1
很多应用问题都可以用上述的背包问题数学模型来表达例如
有 n个项目每个项目所需投资额为 wiw_iwi投产后的利润为 viv_ivi投资总限额为 B求利润最大的投资方案处理器能力有限任务很多如何选择使处理器的效用最大 2.2 互斥的约束问题
互斥的约束问题是指具有多个互斥的约束条件这些约束条件只有一个起作用。
例如货物运输有车运或者船运两种运输方式可供选择已知采用车运的约束条件和船运的约束条件必须且只能选择其中一种运输方式。这两个约束条件互斥有且只有一个起作用这是可以引入一个 0-1变量来处理。
一般地设有 m 个互斥的约束条件 ai1x1...ainxn≤bii1,...ma_{i1}x_1 ...a_{in}x_n \leq b_ii1,...m ai1x1...ainxn≤bii1,...m
该类问题的建模方法为了保证只有一个约束条件起作用可以引入一个充分大的常数 M 和 m 个 0-1 变量表示约束是否起作用 yi{0第i个约束不起作用1第i个约束起作用y_i \begin{cases} 0第 i 个约束不起作用\\ 1第 i 个约束起作用 \end{cases} yi{0第i个约束不起作用1第i个约束起作用
于是可以构造新的 m1 个约束条件 s.t.:{ai1x1...ainxn≤bi(1−yi)Mi1,...my1...ym1yi0,1s.t.:\begin{cases} a_{i1}x_1 ...a_{in}x_n \leq b_i (1-y_i)Mi1,...m\\ y_1 ... y_m 1\\ y_i 0,1 \end{cases} s.t.:⎩⎪⎨⎪⎧ai1x1...ainxn≤bi(1−yi)Mi1,...my1...ym1yi0,1
由于 M 足够大新的约束条件就能保证只有 y_i1 的约束条件起作用而其它约束条件都不起作用。 2.3 固定费用问题Fixed cost problem
固定费用问题是指求解生产成本最小问题时总成本包括固定成本和变动成本而选择不同生产方式会有不同的固定成本因此总成本与选择的生产方式有关。
固定费用问题实际上是互斥的目标函数问题对于不同的生产方式具有多个互斥的目标函数但只有一个起作用。固定费用问题不能用一般的线性规划模型求解。
一般地设有 m 种生产方式可供选择采用第 jjj 种方式时的固定成本为 KjK_jKj、变动成本为 cjc_jcj、产量为 xjx_jxj则采用各种生产方式的总成本分别为
minPj{kjcjxjxj≥00xj0,j1,...mmin\;P_j \begin{cases} k_j c_j x_jx_j \geq 0\\ 0x_j 0, j1,...m \end{cases} minPj{kjcjxj0xj≥0xj0,j1,...m
该类问题的建模方法为了构造统一的目标函数可以引入 m 个 0-1 变量 y_j 表示是否采用第 j 种生产方式 yj{0不采用第j种生产方式1采用第j种生产方式y_j \begin{cases} 0不采用第\;j\;种生产方式\\ 1采用第\;j\; 种生产方式 \end{cases} yj{0不采用第j种生产方式1采用第j种生产方式
于是可以构造新的目标函数和约束条件 minf(x)∑j1m(kjyjcjxj)s.t.:xj≤yjMj1,...mmin\;f(x) \sum_{j1} ^m (k_j y_j c_j x_j)\\ s.t.:\;x_j \leq y_j Mj1,...m minf(x)j1∑m(kjyjcjxj)s.t.:xj≤yjMj1,...m
M 是一个充分大的常数。 2.4 指派问题
分配 n 个人去做 n 件工作每人只做一件工作每件工作只有一个人做已知每个人做每件事的用时为cijc_{ij}cij如何安排才能使花费的总时间最少。
引入 0-1 变量 xijx_{ij}xij xi,j{0第i人不做第j件工作1第i人做第j件工作i,j1,...,nx_{i,j} \begin{cases} 0第\;i\;人不做第\;j\;件工作\\ 1第\;i\;人做第\;j\;件工作i,j1,...,n \end{cases} xi,j{0第i人不做第j件工作1第i人做第j件工作i,j1,...,n
指派问题的数学模型就可以描述为 minf(x)∑i1n∑j1n(cijxij)s.t.:{∑j1nxij1i1,...,n∑i1nxij1j1,...,nxij0,1i,j1,...,nmin\;f(x) \sum_{i1} ^n \sum_{j1} ^n (c_{ij} x_{ij})\\ s.t.:\;\begin{cases} \sum_{j1} ^n x_{ij} 1i1,...,n\\ \sum_{i1} ^n x_{ij} 1j1,...,n\\ x_{ij} 0,1i,j1,...,n \end{cases} minf(x)i1∑nj1∑n(cijxij)s.t.:⎩⎪⎨⎪⎧∑j1nxij1i1,...,n∑i1nxij1j1,...,nxij0,1i,j1,...,n
在此基础上还可以衍生出新的问题
分配 m 个人去做 n 件工作已知每个人做每件事的用时当 mn不限定每人工作的件数、mn不限定每件工作的参与人数时如何安排使花费的总时间最少。分配 m 个人去做 n 件工作已知每个人做每件事的用时如果允许某人完成自己的工作后去帮助别人如何安排使花费的总时间最少。 3. 0-1 规划的求解方法
目前 0-1 规划问题并没有通用、高效、精确的求解方法常用的方法或是针对特殊问题或是近似方法。
需要特别指出的是我们在数学建模的学习中会遇到越来越多的问题都没有通用、高效、精确的求解方法而是借助于计算机算法和程序来得到近似解。
3.1 隐枚举法Implicit enumeration
求解 0-1 规划问题的思路首先是穷举法遍历决策变量的所有的组合求出目标函数的最优值。随着问题规模的增大变量的组合成指数增长穷举法就不可能实现了。
隐枚举法是通过反复构造过滤条件不断删除比当前解差的解集并把优于当前最优解的结果作为新的最优解再以新的最优解构造新的过滤条件如此反复直到求出最优解。
隐枚举法通过过滤条件对穷举法进行改进可以较快地求出最优解。分支定界法也是一种隐枚举法。
3.2 蒙特卡洛法Monte Carlo
既然对较大规模问题无法穷举无法获得数学意义上的最优解那么另一个思路就是随机搜索。于是大名鼎鼎、无所不能的蒙特卡洛法出场了。
蒙特卡洛法是一类随机方法的统称也称随机取样法。顾名思义蒙特卡洛法就是大量地对决策变量随机取值——如果能在满足约束条件的前提下随机取值就更好了通过比较其目标函数值来不断获得更好的解最后就能得到近似的最优解。
蒙特卡洛法的特点是可以在随机采样上计算得到近似结果采样越多越近似最优解 但无法保证得到的结果是不是全局最优解。可以证明在一定的计算量的情况下蒙特卡洛法可以获得较好的满意解。
蒙特卡洛法的思想很简单看起来算法也很简单但实际上也涉及了深刻的数学理论算法理论与实践也都在不断的发展。
蒙特卡洛法不仅可以处理几乎所有的决策问题、优化问题而且在各种学科领域都得到了广泛的应用。这样的方法我们当然不能错过后文将专题进行讨论。
3.3 启发式算法Heuristic algorithms
设计高效的启发式算法解决实际问题是解决 0-1 规划问题的另一个思路。
启发式算法通常是以问题为导向的没有一个通用的框架根据具体问题的特殊结构来识别启发性信息构造启发式优化过程来高效地寻找近似最优解。
启发式算法获得的近似最优解通常是局部最优解。而且启发式算法的解需要借助其他方法来评估其质量并且在实际应用中不能保证为各种算例稳定地生成接近全局最优的可行解。
3.4 近似算法Approximation algorithms
本来不想在这里谈近似算法的只是为了说明启发式算法并不是近似算法。
近似算法与启发式算法是不同的近似算法往往通过巧妙的设计得到的解是在全局最优解的某个邻域范围之内或一定比例范围内。近似算法的解可以用严格的数学证明是“比较好”的因而被认为是有保证的。
3.5 0-1 规划问题的编程方案
总结 0-1 规划的求解方法就是没有通用、高效、精确的求解方法。
对于小白来说其实这样更简单不要操心学习哪种算法了我们还是用 PuLP 工具包来求解。 4. PuLP 求解 0-1 规划问题
不仅继续用 PuLP 工具包而且解题过程和编程步骤也与求解线性规划问题完全一致。
下面我们以一个简单的数学模型练习来讲解整个解题过程而不仅给出例程。
4.1 案例问题描述
例题 1 公司有 5 个项目被列入投资计划各项目的投资额和预期投资收益如下表所示万元
项目ABCDE投资额210300100130260投资收益1502106080180
公司只有 600万元资金可用于投资综合考虑各方面因素需要保证
1项目 A、B、C 中必须且只能有一项被选中 2项目 C、D 中最多只能选中一项 3选择项目 E 的前提是项目 A被选中。
如何在上述条件下进行投资决策使收益最大。 4.2 建模过程分析
定义决策变量为 xi{0不选择第i个项目1选择第i个项目x_i \begin{cases} 0不选择第\;i\;个项目\\ 1选择第\;i\;个项目 \end{cases} xi{0不选择第i个项目1选择第i个项目 定义目标函数为 maxf(x)150x1210x260x380x4180x5s.t.:{210x1300x2100x3130x4260x5≤600x1x2x31x3x4≤1x5≤x1xi0,1i1,...5max\;f(x) 150x_1210x_260x_380x_4180x_5\\ s.t.:\begin{cases} 210x_1300x_2100x_3130x_4260x_5 \leq 600\\ x_1 x_2 x_3 1\\ x_3 x_4 \leq 1\\ x_5 \leq x_1\\ x_i 0,1i1,...5 \end{cases} maxf(x)150x1210x260x380x4180x5s.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧210x1300x2100x3130x4260x5≤600x1x2x31x3x4≤1x5≤x1xi0,1i1,...5 4.3 模型求解的编程
模型求解用标准模型的优化算法对模型求解得到优化结果。模型求解的编程步骤如下
0导入 PuLP库函数 import pulp1定义一个规划问题 InvestLP pulp.LpProblem(Invest decision problem, sensepulp.LpMaximize)pulp.LpProblem 用来定义问题的构造函数。InvestLP是用户定义的问题名。 参数 sense 指定问题求目标函数的最小值/最大值 。本例求最大值选择 “pulp.LpMaximize” 。
2定义决策变量 对于问题 1 x1 pulp.LpVariable(A, catBinary) # 定义 x1A 项目x2 pulp.LpVariable(B, catBinary) # 定义 x2B 项目x3 pulp.LpVariable(C, catBinary) # 定义 x3C 项目x4 pulp.LpVariable(D, catBinary) # 定义 x4D 项目x5 pulp.LpVariable(E, catBinary) # 定义 x5E 项目pulp.LpVariable 用来定义决策变量的函数。‘x1’~‘x5’ 是用户定义的变量名。 参数 cat 用来设定变量类型’ Binary ’ 表示0/1变量用于0/1规划问题。
3添加目标函数 InvestLP (150*x1 210*x2 60*x3 80*x4 180*x5) # 设置目标函数 f(x)4添加约束条件 InvestLP (210*x1 300*x2 100*x3 130*x4 260*x5 600) # 不等式约束InvestLP (x1 x2 x3 1) # 等式约束InvestLP (x3 x4 1) # 不等式约束InvestLP (x5 - x1 0) # 不等式约束添加约束条件使用 “问题名 约束条件表达式” 格式。 约束条件可以是等式约束或不等式约束不等式约束可以是 小于等于 或 大于等于分别使用关键字、“和”。
5求解 InvestLP.solve()print(InvestLP.name) # 输出求解状态print(Status youcans:, pulp.LpStatus[InvestLP.status]) # 输出求解状态for v in InvestLP.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(Max f(x) , pulp.value(InvestLP.objective)) # 输出最优解的目标函数值solve() 是求解函数可以对求解器、求解精度进行设置。 4.4 Python 例程
# mathmodel06_v1.py
# Demo05 of mathematical modeling algorithm
# Solving 0-1 binary programming with PuLP.
# Copyright 2021 Youcans, XUPT
# Crated2021-06-02
# Python小白的数学建模课 Youcansimport pulp # 导入 pulp 库# 主程序
def main():# 投资决策问题# 公司现有 5个拟投资项目根据投资额、投资收益和限制条件问如何决策使收益最大。问题建模决策变量x1x50/1 变量1 表示选择第 i 个项目 0 表示不选择第 i 个项目目标函数max fx 150*x1 210*x2 60*x3 80*x4 180*x5约束条件210*x1 300*x2 100*x3 130*x4 260*x5 600x1 x2 x3 1x3 x4 1x5 x1x1,...,x5 0, 1InvestLP pulp.LpProblem(Invest decision problem, sensepulp.LpMaximize) # 定义问题求最大值x1 pulp.LpVariable(A, catBinary) # 定义 x1A 项目x2 pulp.LpVariable(B, catBinary) # 定义 x2B 项目x3 pulp.LpVariable(C, catBinary) # 定义 x3C 项目x4 pulp.LpVariable(D, catBinary) # 定义 x4D 项目x5 pulp.LpVariable(E, catBinary) # 定义 x5E 项目InvestLP (150*x1 210*x2 60*x3 80*x4 180*x5) # 设置目标函数 f(x)InvestLP (210*x1 300*x2 100*x3 130*x4 260*x5 600) # 不等式约束InvestLP (x1 x2 x3 1) # 等式约束InvestLP (x3 x4 1) # 不等式约束InvestLP (x5 - x1 0) # 不等式约束InvestLP.solve()print(InvestLP.name) # 输出求解状态print(Status youcans:, pulp.LpStatus[InvestLP.status]) # 输出求解状态for v in InvestLP.variables():print(v.name, , v.varValue) # 输出每个变量的最优值print(Max f(x) , pulp.value(InvestLP.objective)) # 输出最优解的目标函数值returnif __name__ __main__: # Copyright 2021 YouCans, XUPTmain() # Python小白的数学建模课 Youcans4.5 Python 例程运行结果
Welcome to the CBC MILP Solver
Version: 2.9.0
Build Date: Feb 12 2015 Result - Optimal solution foundInvest_decision_problem
Status youcans: Optimal
A 1.0
B 0.0
C 0.0
D 1.0
E 1.0
Max f(x) 410.0从 0-1 规划模型的结果可知选择 A、C、E 项目进行投资可以满足限定条件并获得最大收益 410万元。 5. 小结
对于小白学数模能识别哪些问题是 0-1 规划问题是哪种 0-1规划问题才能将问题描述转化为数学模型的表达形式。这是数模学习中最重要的内容。至于模型的求解对于算法能了解一些最好不求甚解也没关系先学会用工具包解决问题就可以了。从线性规划、整数规划到本文的 0-1 规划我们都选择了 PuLP 工具包。虽然这些问题的类型不同求解算法差别非常大但是 PuLp 工具包使用了一致的处理步骤定义问题、定义变量、定义目标函数和约束条件调用求解器求解。所以我们在求解不同问题时的编程方法和步骤如出一辙完全感受不到不同类型问题之间的巨大差异。这就是为什么在线性规划问题时不选择 Scipy 的原因这就是本系列课程的特点让小白能快速入门求解问题。对于更为复杂的问题PuLP 还提供了快捷方式可以结合 Python语言的循环和容器使用字典来创建问题我们下节再讲。
【本节完】 版权声明
欢迎关注『Python小白的数学建模课 Youcans』 原创作品
原创作品转载必须标注原文链接(https://blog.csdn.net/youcans/article/details/117463682)。
Copyright 2021 Youcans, XUPT
Crated2021-06-02 欢迎关注 『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数模笔记-模拟退火算法
