我在前面的几篇博客中反复强调过，建立模型的过程是整个数学建模的重点、难点、核心，而求解的过程相对的就不是那么重要（并不是不重要），毕竟市面上有很多的开源和商业版求解器供我们求解特定数学模型。我们的主要任务就是将问题建模成这些特定类型的数学模型（比如线性规划、整数规划、二次规划等等）。在这个过程中，建模技巧至关重要。如决策变量的定义、约束条件变换等不合理将直接导致问题无法求解、或者降低求解速度。
整数规划的应用来源于两种方式：直接的和转化的。
直接的，一般比较简单，直接定义整数决策变量，建立约束条件即可。典型的问题是 投资决策 。

问题 ：
在一个三年的规划周期内，有五个项目可供选择，下表给出了每个项目可以带来的预期收益以及每年的支出（单位：百万元）

请问，在这个三年规划周期内应该选哪些项目？
建模过程
这个问题可以转化成对每个项目选择为“是/否”的决策，引入二值变量 \begin{aligned} &max \ \ z=20x_1+40x_2+20x_3+15x_4+30x_5 \\ &s.t. \\ &\ \ \ \ 5x_1+4x_2+3x_3+7x_4+8x_5\leqslant 25 \\ &\ \ \ \ x_1+7x_2+9x_3+4x_4+6x_5\leqslant 25 \\ &\ \ \ \ 8x_1+10x_2+2x_3+x_4+10x_5\leqslant 25 \\ &\ \ \ \ x_1,x_2,x_3,x_4,x_5=(0,1) \end{aligned} ​ m a x z = 2 0 x 1 ​ + 4 0 x 2 ​ + 2 0 x 3 ​ + 1 5 x 4 ​ + 3 0 x 5 ​ s . t . 5 x 1 ​ + 4 x 2 ​ + 3 x 3 ​ + 7 x 4 ​ + 8 x 5 ​ ⩽ 2 5 x 1 ​ + 7 x 2 ​ + 9 x 3 ​ + 4 x 4 ​ + 6 x 5 ​ ⩽ 2 5 8 x 1 ​ + 1 0 x 2 ​ + 2 x 3 ​ + x 4 ​ + 1 0 x 5 ​ ⩽ 2 5 x 1 ​ , x 2 ​ , x 3 ​ , x 4 ​ , x 5 ​ = ( 0 , 1 ) ​

在这一类问题中，会有许多服务装置为一些设备提供互相重叠的服务，其目标就是确定安装数量最好的装置来覆盖每一个设备满足服务需求。比如选址问题：几个污水处理厂可以建在不同地点，为不同的城市服务，当一个城市得到不同的污水处理厂的服务时就产生了重叠服务。
案例 ：
现代电网中使用无线接收器读取用户的读表仪器数据，生成电费账单。现在有8个接收器安放点，可服务于10个用户，每一个安放点可服务的用户信息如下：

如何设置最少数量的接收器服务于这10个读表仪器（对应10个用户）？
建模过程 ：
（1）决策变量：
\begin{aligned} &min \ \ z=\sum_{i=1}^{8}x_i \\ &s.t. \\ &\ \ \ \ x_1+x_4+x_8&\geq 1 \\ &\ \ \ \ x_1+x_2&\geq 1 \\ &\ \ \ \ x_1+x_2+x_5&\geq 1 \\ &\ \ \ \ x_6+x_7+x_8&\geq 1 \\ &\ \ \ \ x_3+x_7&\geq 1 \\ &\ \ \ \ x_3+x_5&\geq 1 \\ &\ \ \ \ x_3+x_4+x_6&\geq 1 \\ &\ \ \ \ x_5+x_8&\geq 1 \\ &\ \ \ \ x_6+x_7&\geq 1 \\ &\ \ \ \ x_i=(0,1), i=(1,2,..,8) \end{aligned} ​ m i n z = i = 1 ∑ 8 ​ x i ​ s . t . x 1 ​ + x 4 ​ + x 8 ​ x 1 ​ + x 2 ​ x 1 ​ + x 2 ​ + x 5 ​ x 6 ​ + x 7 ​ + x 8 ​ x 3 ​ + x 7 ​ x 3 ​ + x 5 ​ x 3 ​ + x 4 ​ + x 6 ​ x 5 ​ + x 8 ​ x 6 ​ + x 7 ​ x i ​ = ( 0 , 1 ) , i = ( 1 , 2 , . . , 8 ) ​ ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ​

固定费用问题通常包含两种费用形式：一种活动启动即会产生的固定费用，另一种是活动启动后产生的可变费用，这种可变费用与活动开展情况有关。

例如，在生产某种产品之前需要购买一台机器，这台机器的费用是固定费用，与生产多少产品无关，同时，一旦买了机器，劳动力和原材料所耗费用就与生产产品的数量成正比总费用函数可以表示为：
\begin{aligned} x &\leqslant Mw,\\ x &\geqslant \varepsilon-M(1-w),\\ w&=(0,1). \end{aligned} x x w ​ ⩽ M w , ⩾ ε − M ( 1 − w ) , = ( 0 , 1 ) . ​
总费用函数的分段表示可转化为：
\begin{aligned} C(x)=Fw+cx \\ s.t.=\begin{cases} x&\leqslant Mw ,\\ -x&\leqslant M(1-w)-\varepsilon, \\ w&=(0,1). \end{cases} \end{aligned} C ( x ) = F w + c x s . t . = ⎩ ⎪ ⎨ ⎪ ⎧ ​ x − x w ​ ⩽ M w , ⩽ M ( 1 − w ) − ε , = ( 0 , 1 ) . ​ ​

我们知道经典的几类数学模型的约束条件是并列关系，但实践中根据约束建立数学关系时常出现“or”关系和“if-then”关系。我们以例子来说明约束条件变换方法。
案例
Jobco 公司需要在一台机器上进行三项加工，下表给出了每项工作的处理以及应交工日期c 将第一项工作开始处理时的日期定为0，应交工日期从0 算起。

这个问题的目标是求使得延期处罚最少的工序处理方案。
（1）定义决策变量
\begin{aligned} x_j&= \text{工作j 的开始日期（按天计算，从0 开始计算）} \\ y_{ij}&=\begin{cases} 1 &\text{若工作i在工作j之前处理}\\ 0 &\text{若工作i在工作j之后处理} \\ \end{cases} \end{aligned} x j ​ y i j ​ ​ = 工作 j 的开始日期（按天计算，从 0 开始计算） = { 1 0 ​ 若工作 i 在工作 j 之前处理 若工作 i 在工作 j 之后处理 ​ ​
（2）建立合适形式的数学约束条件
约束条件有两个。
第一个约束 ：一台机器同时只能处理一项工作，所以三项工作任意两项之间都不能有时间交叉。
假设工作 \begin{aligned} M{y_{1,2}}+x_1-x_2&\geqslant 20 \\ -My_{1,2}+x_2-x_1&\geqslant 5-M \\ M{y_{1,3}}+x_1-x_3&\geqslant 15 \\ -My_{1,3}+x_3-x_1&\geqslant 5-M \\ M{y_{2,3}}+x_2-x_3&\geqslant 15 \\ -My_{2,3}+x_3-x_2&\geqslant 20-M \\ x_1+s_1^--s_1^+&=5-1 \\ x_2+s_2^--s_2^+&=20-2 \\ x_3+s_3^--s_3^+&=15-3 \\ x_1,x_2,x_3,s_1^-,s_1^+,s_2^-,s_2^+,s_3^-,s_3^+ \geqslant 0 \\ y_{1,2},y_{1,3},y_{2,3}=(0,1) \end{aligned} M y 1 , 2 ​ + x 1 ​ − x 2 ​ − M y 1 , 2 ​ + x 2 ​ − x 1 ​ M y 1 , 3 ​ + x 1 ​ − x 3 ​ − M y 1 , 3 ​ + x 3 ​ − x 1 ​ M y 2 , 3 ​ + x 2 ​ − x 3 ​ − M y 2 , 3 ​ + x 3 ​ − x 2 ​ x 1 ​ + s 1 − ​ − s 1 + ​ x 2 ​ + s 2 − ​ − s 2 + ​ x 3 ​ + s 3 − ​ − s 3 + ​ x 1 ​ , x 2 ​ , x 3 ​ , s 1 − ​ , s 1 + ​ , s 2 − ​ , s 2 + ​ , s 3 − ​ , s 3 + ​ ⩾ 0 y 1 , 2 ​ , y 1 , 3 ​ , y 2 , 3 ​ = ( 0 , 1 ) ​ ⩾ 2 0 ⩾ 5 − M ⩾ 1 5 ⩾ 5 − M ⩾ 1 5 ⩾ 2 0 − M = 5 − 1 = 2 0 − 2 = 1 5 − 3 ​

这是一个混合整数线性规划模型。

注意 ：目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

根据整数规划不同的情形可以采用不同的算法，大致如下：

（1）分枝定界法—可求纯或混合整数线性规划。
（2）割平面法—可求纯或混合整数线性规划。
（3）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（4）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（5）蒙特卡洛法（随机取样法）—求解各种类型规划。

[1].《运筹学导论（基础篇）》；
[2].《数学建模算法与程序》，司守奎；
[3].《matlab数学建模经典案例实战》。