type
status
date
slug
summary
tags
category
icon
password
Property
什么是 0-1 规划？
0-1 整数规划是一类特殊的整数规划，变量的取值只能是 0 或 1。
0-1 变量可以描述开关、取舍、有无等逻辑关系、顺序关系，可以处理背包问题、指派问题、选址问题 、计划安排、线路设计 、人员安排等各种决策规划问题。进而，任何整数都可以用二进制表达，整数变量就可以表示为多个 0-1 变量的组合，因此任何整数规划都可以转化为 0-1 规划问题来处理。0-1 规划问题与运筹学中的很多经典问题也都有紧密联系。
在数学建模学习中，0-1 规划主要用于求解互斥的决策问题、互斥的约束条件问题、固定费用问题和分派问题。
0-1 规划的分类及建模方法
规划问题的数学模型包括决策变量、约束条件和目标函数，围绕这三个要素都可能存在互斥的情况，从而导出不同类型的0-1规划问题，其建模方法也有差别。
互斥的决策问题
互斥的决策问题，是指决策方案、计划互斥，如决定投资项目、确定投资场所、选择投产产品等。
例如，双十一的促销活动，淘宝、京东、拼多多要求店铺二选一，最多只能选择参加一家平台，否则可能会被封杀，这是典型的互斥决策问题。
背包问题就是经典的互斥决策问题。给定一组 个物品，每种物品 的价值为 、重量/体积为 ，背包所能容纳的总重量/总容量为（B），如何选择其中若干种物品（每种物品选 0 个或 1 个），使得物品的总价值最高？
背包问题的建模方法如下：
定义决策变量为：
定义目标函数为：
很多应用问题都可以用上述的背包问题数学模型来表达，例如：
- 有个项目，每个项目所需投资额为，投产后的利润为 ，投资总限额为 B，求利润最大的投资方案
- 处理器能力有限，任务很多，如何选择使处理器的效用最大
互斥的约束问题
互斥的约束问题，是指具有多个互斥的约束条件，这些约束条件只有一个起作用。
例如，货物运输有车运或者船运两种运输方式可供选择，已知采用车运的约束条件和船运的约束条件，必须且只能选择其中一种运输方式。这两个约束条件互斥，有且只有一个起作用，这是可以引入一个 0-1变量来处理。
一般地，设有 个互斥的约束条件：
该类问题的建模方法，为了保证只有一个约束条件起作用，可以引入一个充分大的常数和个 0-1 变量表示约束是否起作用：
于是可以构造新的个约束条件：
由于足够大，新的约束条件就能保证只有的约束条件起作用，而其它约束条件都不起作用。
固定费用问题（Fixed cost problem）
固定费用问题，是指求解生产成本最小问题时，总成本包括固定成本和变动成本，而选择不同生产方式会有不同的固定成本，因此总成本与选择的生产方式有关。
固定费用问题，实际上是互斥的目标函数问题，对于不同的生产方式具有多个互斥的目标函数，但只有一个起作用。固定费用问题不能用一般的线性规划模型求解。
一般地，设有 种生产方式可供选择，采用第 种方式时的固定成本为 、变动成本为 、产量为 ，则采用各种生产方式的总成本分别为：
该类问题的建模方法，为了构造统一的目标函数，可以引入 个 0-1 变量 表示是否采用第 种生产方式：
于是可以构造新的目标函数和约束条件：
是一个充分大的常数。
指派问题
分配 个人去做 件工作，每人只做一件工作，每件工作只有一个人做，已知每个人做每件事的用时为 ，如何安排才能使花费的总时间最少。
引入 0-1 变量 ：
指派问题的数学模型就可以描述为：
在此基础上，还可以衍生出新的问题：
- 分配 个人去做 件工作，已知每个人做每件事的用时，当 （不限定每人工作的件数）、 （不限定每件工作的参与人数）时，如何安排使花费的总时间最少。
- 分配 个人去做 件工作，已知每个人做每件事的用时，如果允许某人完成自己的工作后去帮助别人，如何安排使花费的总时间最少。
0-1 规划的求解方法
目前 0-1 规划问题并没有通用、高效、精确的求解方法，常用的方法或是针对特殊问题，或是近似方法。
隐枚举法（Implicit enumeration）
求解 0-1 规划问题的思路，首先是穷举法，遍历决策变量的所有的组合，求出目标函数的最优值。随着问题规模的增大，变量的组合成指数增长，穷举法就不可能实现了。
隐枚举法是通过反复构造过滤条件，不断删除比当前解差的解集，并把优于当前最优解的结果作为新的最优解，再以新的最优解构造新的过滤条件，如此反复直到求出最优解。
隐枚举法通过过滤条件对穷举法进行改进，可以较快地求出最优解。分支定界法也是一种隐枚举法。
蒙特卡洛法（Monte Carlo）
既然对较大规模问题无法穷举，无法获得数学意义上的最优解，那么另一个思路就是随机搜索。于是大名鼎鼎、无所不能的蒙特卡洛法出场了。
蒙特卡洛法是一类随机方法的统称，也称随机取样法。顾名思义，蒙特卡洛法就是大量地对决策变量随机取值——如果能在满足约束条件的前提下随机取值就更好了，通过比较其目标函数值来不断获得更好的解，最后就能得到近似的最优解。
蒙特卡洛法的特点是，可以在随机采样上计算得到近似结果，采样越多，越近似最优解 ，但无法保证得到的结果是不是全局最优解。可以证明，在一定的计算量的情况下，蒙特卡洛法可以获得较好的满意解。
启发式算法（Heuristic algorithms）
设计高效的启发式算法解决实际问题，是解决 0-1 规划问题的另一个思路。
启发式算法通常是以问题为导向的，没有一个通用的框架，根据具体问题的特殊结构来识别启发性信息，构造启发式优化过程来高效地寻找近似最优解。
启发式算法获得的近似最优解，通常是局部最优解。而且，启发式算法的解需要借助其他方法来评估其质量，并且在实际应用中不能保证为各种算例稳定地生成接近全局最优的可行解。
近似算法（Approximation algorithms）
近似算法与启发式算法是不同的，近似算法往往通过巧妙的设计，得到的解是在全局最优解的某个邻域范围之内，或一定比例范围内。近似算法的解可以用严格的数学证明是“比较好”的，因而被认为是有保证的。
PuLP 求解 0-1 规划问题
例题 1：
公司有 5 个项目被列入投资计划，各项目的投资额和预期投资收益如下表所示（万元）：
项目 | A | B | C | D | E |
投资额 | 210 | 300 | 100 | 130 | 260 |
投资收益 | 150 | 210 | 60 | 80 | 180 |
公司只有 600万元资金可用于投资，综合考虑各方面因素，需要保证：
（1）项目 A、B、C 中必须且只能有一项被选中；
（2）项目 C、D 中最多只能选中一项；
（3）选择项目 E 的前提是项目 A被选中。
如何在上述条件下，进行投资决策，使收益最大。
定义决策变量为：
定义目标函数为：
例题 2：
某服装厂可以生产 A、B、C 三种服装，生产不同种类服装需要租用不同设备，设备租金、生产成本、销售价格等指标如下表所示
服装种类 | 设备租金 | 材料成本 | 销售价格 | 人工工时 | 设备工时 | 设备可用工时 |
单位 | （元） | （元/件） | （元/件） | （小时/件） | （小时/件） | （小时） |
A | 5000 | 280 | 400 | 5 | 3 | 300 |
B | 2000 | 30 | 40 | 1 | 0.5 | 300 |
C | 2000 | 200 | 300 | 4 | 2 | 300 |
如果各类服装的市场需求都足够大，服装厂每月可用人工时为 2000h，那么应该如何安排生产计划使利润最大？
可以用固定费用问题的数学模型来描述问题了：
设 为是否生产第种服装， 是 变量：
数学模型就可以表达为：
如果问题非常复杂，例如变量数量很多，约束条件复杂，逐个定义变量、逐项编写目标函数与约束条件的表达式，不仅显得重复冗长，不方便修改对变量和参数的定义，而且在输入过程中容易发生错误。因此，我们希望用字典、列表、循环等快捷方法来进行变量定义、目标函数和约束条件设置
选址问题
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
例如投资场所的选址：企业要在 m 个候选位置选择若干个建厂，已知建厂费用、运输费及 n 个地区的产品需求量，应如何进行选址。
选址问题是运筹学中经典的问题之一，选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的，选址问题也是数模竞赛的热点问题。
选址是重要的长期决策，选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等，从而影响到利润和市场竞争力，选址问题的研究有着重大的经济、社会和军事意义。
选址问题有四个基本要素：设施、区域、距离和优化目标。
设施
选址问题中所说的设施，在具体题目中可以是工厂、仓库、服务站等形式。
区域
选址问题中所说的区域，在具体题目中可以是工厂、车间的内部布局，也可以是给定的某个地区、甚至空间范围。
按照规划区域的特征，可以分为连续选址问题和离散选址问题。连续选址问题，设施可以布局在区域内的任意位置，就要求出最优选址的坐标；离散选址问题，只能从若干候选位置中进行选择，运筹学中的选址问题通常是这类离散选址问题。
距离
选址问题中所说的距离，是指设施到服务对象之间的距离，在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解，通常就是连接顶点的边的权值。
当问题所关注的是设施到服务对象之间的距离时，如果问题给出的不是顶点之间的距离，而是设施的位置坐标，要注意不是只有欧式距离，对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。
优化目标
选址问题要求选择最好的选址位置，但选址位置只是决策变量，选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短，这才是优化问题的目标函数。
按照目标函数的特点，可以分为：中位问题，要求总成本最小；中心问题，服务于每个客户的最大成本最小；反中心问题：服务于每个客户的最小成本最大。
常见选址问题
P-中位问题（P-median problem）
P-中位问题，假设有个候选服务站和个需求点，要从个候选服务站中选择个，使所有需求点到最近的服务站的加权距离的总和最小。需求点的权值，通常是指该需求点的需求量。
这是一个MinSum问题，定义决策变量为选中的服务站，将各需求点匹配到最近的服务站：
可以建立数学模型如下：
其中： 为服务站， 为需求点， 为需求点 的需求量， 为需求点 到服务站 的距离。
P-中心问题
P-中心问题，假设有个候选服务站和个需求点，要从个候选服务站中选择个，使任一需求点到最近的服务站的最大距离最小。
这是一个 MinMax 问题，需要最小化任何需求点与其邻近设施点的最大距离。P-中位问题追求总和最小，可以理解为发展经济总量优先；P-中心问题关注最差个体的最好结果，可以理解为优先进行扶贫。
定义决策变量 为选中的服务站， 将各需求点匹配到最近的服务站：
可以建立数学模型如下：
其中：为服务站，为需求点，为需求点到服务站的距离。如果只求需求点到最近的服务站的最大距离，则 ；如果要求任一需求点到最近的服务站的最大运费，则 为需求点的需求量，即加权最大距离。
集合覆盖问题
覆盖模型适用于一些特殊场景，例如消防中心、救护车、巡逻车等应急设施的区位选址问题。覆盖问题分为集合覆盖问题（Set covering problem）和最大覆盖问题（Maximal covering problem）。
集合覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站的最少个数或建设费用最小的问题。假设有 N 个候选服务站和 M 个需求点，已知每个服务站的服务范围（或服务容量），要从 N个候选服务站中选择若干个，使所有需求点得到服务（到所属服务站的距离或时间小于给定的临界值），服务站的个数最少或成本最小。
定义参数为每个服务站的覆盖范围：
定义决策变量为选中的服务站：
可以建立数学模型如下：
其中：为服务站，为需求点，为服务站的建设费用（最少个数问题中不需要考虑）， 是覆盖需求点 的候选服务站的集合。
最大覆盖问题
最大覆盖问题研究在已知服务站的数目和服务半径的条件下，如何设立 个服务站使得可接受的服务需求最大的问题。
定义决策变量 为选中的服务站：
可以建立数学模型如下：
其它选址问题
带固定费用和容量限制的选址问题
服务站建站的固定费用和服务站的容量（能力）限制这两个因素具有很强的实际意义，经常作为基本选址问题的深化研究课题。
无容量限制的固定费用下的选址问题，就是去掉服务站个数的约束，并将固定建站费用加到 P-中位问题的目标函数上。
选址分配问题
选址分配问题类似于 P-中位问题，有 m 个服务站需要选址，n 个已知位置的顾客分配给不同的设施，已知每个服务站的能力和每个顾客的需求，要求服务站的选址和顾客对服务站的分配，使顾客与所分配服务站的距离总和最小。
随机选址问题
服务站的运行时间、建设成本、需求点位置、需求数量等全部或部分参数是不确定的，但服从某种随机分布。
动态选址问题
研究未来若干时间段内服务站的最优选址问题，在不同时间段内动态选址模型的参数是变化的，但在某一时间段内模型参数是确定的。
竞争选址问题
研究考虑市场上存在两个以上同类产品或服务的提供者，或服务站提供多个产品或服务。
选址问题的求解算法与编程实现
设施选址问题通常是是 NP 问题，不存在多项式时间算法。常用的近似解法有：
线性规划舍入算法，相当于整数规划问题的求解算法。首先给出原问题的整数规划模型，然后求解相应的线性规划松弛问题得到分数最优解，根据可行要求对分数最优解进行改造，构造原问题的整数可行解。
原始对偶算法，首先找到对偶问题的一个可行解，再根据该对偶可行解构造原始问题的整数可行解，不断调整对偶问题的可行解，直到找到最优解为止。
局部搜索算法：给定初始可行解，定义适当的邻域，通过引入恰当的调整策略，在邻域中得到改进的可行解，依次迭代，直到调整策略不能改进为止
启发式算法或随机优化算法。
指派问题
游泳队中 A、B、C、D 四名运动员组成 4x100米混合泳接力队，运动员各种泳姿的成绩如下表所示 （单位：秒）：
队员\项目 | 自由泳 | 蛙泳 | 蝶泳 | 仰泳 |
A | 56 | 74 | 61 | 63 |
B | 63 | 69 | 65 | 71 |
C | 57 | 77 | 63 | 67 |
D | 55 | 76 | 62 | 62 |
如何安排 A、B、C、D 四名运动员的泳姿，才最有可能取得好成绩？
引入 0-1 变量：
指派问题的数学模型就可以描述为：
其中：
消防站的选址问题
例题 2：某城市有 8 个区，每个区最多建一个消防站，拟建设消防站到各区的最长时间如下表所示。现要求任何区域发生火警时，消防车能在 10分钟内赶到。在此条件下尽量减少消防站数量，应该在哪几个区建设消防站？
区域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | 7 | 12 | 18 | 20 | 24 | 26 | 25 | 28 |
2 | 14 | 5 | 8 | 15 | 16 | 18 | 18 | 18 |
3 | 19 | 9 | 4 | 14 | 10 | 22 | 16 | 13 |
4 | 14 | 15 | 15 | 10 | 18 | 15 | 14 | 18 |
5 | 20 | 18 | 12 | 20 | 9 | 25 | 14 | 12 |
6 | 18 | 21 | 20 | 16 | 20 | 6 | 10 | 15 |
7 | 22 | 18 | 20 | 15 | 16 | 15 | 5 | 9 |
8 | 30 | 22 | 15 | 20 | 14 | 18 | 8 | 6 |
建模分析
首先判断这是一个集合覆盖问题，要求从 8 个候选消防站中选择若干个，在所有需求点得到服务的时间都小于临界值 10分钟的条件下，选择消防站的数量最少。本问题不考虑各候选站点建设费用的差异，即不带权重。
定义参数 为每个消防站的覆盖范围：
由拟建消防站到各区的最长时间表可以得到参数
区域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | 1 1 | 0 | 0 1 | 0 2 | 0 3 | 0 4 | 0 5 | 0 6 |
2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
8 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
定义决策变量 为选中的服务站：
可以建立数学模型如下：
