2 整数规划

理论基础¶

定义¶

数学规划中的变量（部分或全部）限制为整数时，称为整数规划。

线性规划中的变量（部分或全部）限制为整数时，称为整数线性规划。

不加特殊说明，一般指整数线性规划。

分类¶

纯（完全）整数规划：变量全限制为整数
混合整数规划：变量部分限制为整数

可能的情况¶

原线性规划有最优解
1. 原线性规划最优解全为整数：整数规划最优解与线性规划最优解一致
2. 整数规划无可行解
  
  例：
  
  \[ \begin{array}{l} \min z = x_1 + x_2 \, \\ \text{s.t.} \left\{ \begin{array}{l} 2x_1 + 4x_2 = 5 \,, \\ x_1 \geqslant 0, \, x_2 \geqslant 0 \,. \\ \end{array} \right. \end{array} \]
  
  最优实数解为 \(x_1=0\)，\(x_2=\dfrac{5}{4}\)，\(\min z=\dfrac{5}{4}\)，对应整数规划无可行解。
3. 整数规划有最优解，但由于原线性规划最优解不满足整数约束条件，故整数规划最优解优解值变差
  
  例：
  
  \[ \begin{array}{l} \min z = x_1 + x_2 \, \\ \text{s.t.} \left\{ \begin{array}{l} 2x_1 + 4x_2 = 6 \,, \\ x_1 \geqslant 0, \, x_2 \geqslant 0 \,. \\ \end{array} \right. \end{array} \]
  
  最优实数解为 \(x_1=0\)，\(x_2=\dfrac{3}{2}\)，\(\min z=\dfrac{3}{2}\)，但整数规划最优解为 \(x_1=1\)，\(x_2=1\)，\(\min z=2\)。 2. 整数约束使得可行域变化较大，整数规划最优解与线性规划最优解相差较大

求解方法¶

分支定界法——求纯或混合整数线性规划
割平面法——求纯或混合整数线性规划
隐枚举法——求解“0-1”整数规划
1. 过滤隐枚举法
2. 分支隐枚举法
匈牙利法——求解“0-1”整数规划
蒙特卡洛法——求解各种类型规划（非线性也可解）

只有整数线性规划可以使用算法精确计算，非线性规划只能用近似算法如蒙特卡洛法来进行求解。

简单的求解示例

0-1型整数规划¶

是整数规划中的特殊情形，变量 \(x_j\) 的取值只能为 \(0\) 或 \(1\)。

\(x_j\) 被称为0-1变量或二进制变量。

0-1型整数规划的约束条件形式为：

\[ 0 \leqslant x_j \leqslant 1 \text{且} x_j \in \mathbb{Z} \]

与一般的整数规划的条件形式一致。

有一些有各种情况需要分别讨论的数学规划问题，可以通过引入0-1变量，将其统一在一个问题中进行讨论。

下面是几种引入0-1变量的实际问题：

背包问题¶

有 10 件货物要从甲地运送到乙地，每件货物的重量(单位：吨)和利润(单位：元)如下表所示

物品	1	2	3	4	5	6	7	8	9	10
重量(t)	6	3	4	5	1	2	3	5	4	2
利润(元)	540	200	180	350	60	150	280	450	320	120

但由于只有一辆最大载重为 30t 的货车能用来运送货物，所以只能选择部分货物进行运送。

要求确定运送那些货物，使得运送这些货物的总利润最大。

记

\[ x_i = \left\{ \begin{array}{ll} 1,&\text{运送了第}i\text{件货物}\,, \\ 0,&\text{未运送第}i\text{件货物}\,. \end{array} \right. \]

记 \(w_i\) 表示第 \(i\) 件货物的重量，\(p_i\) 表示第 \(i\) 件货物的利润，则可以将问题写成如下形式：

\[ \begin{array}{l} \displaystyle \max \quad \sum_{i=1}^n p_i x_i \\ \displaystyle \text{s.t.} \left\{ \begin{array}{l} \displaystyle \sum_{i=1}^n w_i x_i \leqslant 30 \,, \\ x_j \in \mathbb{Z} \,, \\ 0 \leqslant x_j \leqslant 1 \,, \\ j = 1,\ldots,10 \,. \end{array} \right. \end{array} \]

转成可用的标准型

\[ \begin{array}{l} \displaystyle \min \quad -\sum_{i=1}^n p_i x_i \\ \displaystyle \text{s.t.} \left\{ \begin{array}{l} \displaystyle \sum_{i=1}^n w_i x_i \leqslant 30 \,, \\ x_j \in \mathbb{Z} \,, \\ 0 \leqslant x_j \leqslant 1 \,, \\ j = 1,\ldots,10 \,. \end{array} \right. \end{array} \]

相互排斥的约束条件¶

引入充分大正实数¶

如有两种运输方式可供选择，但只能选择其中一种，或者用车运输，或者用船运输。二者约束条件分别为 \(5x_1 + 4x_2 \leqslant 24\) 和 \(7x_1 + 3x_2 \leqslant 45\)，二者相互排斥。

当前问题的约束条件为：

\[ 5x_1 + 4x_2 \leqslant 24 \,\text{或}\, 7x_1 + 3x_2 \leqslant 45 \]

可以通过引入0-1变量 \(y\) 与一个充分大的正实数 \(M\)，其中 \(y\) 定义如下：

\[ \left\{ \begin{array}{l} 1,\text{当采取船运方式时} \,, \\ 0,\text{当采取车运方式时} \,. \end{array} \right. \]

可将约束条件改写为

\[ \left\{ \begin{array}{l} 5x_1 + 4x_2 \leqslant 24 + yM \,, \\ 7x_1 + 3x_2 \leqslant 45 + (1-y)M \,, \\ y \in \mathbb{Z} \,, \\ 0 \leqslant y \leqslant 1 \,. \end{array} \right. \]

其思想是，倘若 \(M\) 前的系数不为 \(0\)，则不等式右端的约束变量充分大，使得当前约束条件近似失效，从而使得两个相互排斥的约束条件之中只有一个条件生效。

如果有 \(m\) 个互相排斥的约束条件

\[ a_{i1}x_1 + \cdots + a_{in}x_n \leqslant b_i, i=1,2,\ldots,m \]

引入 \(m\) 个0-1变量 \(y_i\) 以及一个充分大的正实数 \(M\)

\[ y_i = \left\{ \begin{array}{l} 1, \text{第}i\text{个约束生效} \,, \\ 0, \text{第}i\text{个约束不生效}\,. \end{array} \right. (i=1,2,\ldots,m) \]

则可以将约束条件改写为

\[ \left\{ \begin{array}{l} a_{i1}x_1 + \cdots + a_{in}x_n \leqslant b_i + (1-y_i)M, i=1,2,\ldots,m \,, \\ y_1 + \cdots + y_m = 1 \,, \\ y_i \in \mathbb{Z} \,, \\ 0 \leqslant y_i \leqslant 1 \,. \end{array} \right. \]

保证 \(m\) 个 \(y_i\) 中只有一个能取 \(1\)，使得只有一个约束条件生效，其余的都是多余的。

不引入充分大正实数¶

例如相互排斥的约束条件

\[ x_1 = 0 \text{或} 500 \leqslant x_1 \leqslant 800 \]

可改写为

\[ \left\{ \begin{array}{l} 500y \leqslant x_1 \leqslant 800y \,, \\ y \in \mathbb{Z} \,, \\ 0 \leqslant y \leqslant 1 \,. \end{array} \right. \]

固定费用的问题(Fixed Cost Problem)¶

例如，某工厂生产某种产品，有几种不同的生产方式可供选择，但是每种方式除了生产每件产品的成本外，还有一定的固定费用需要考虑进去。我们希望通过合理选择生产方式来控制成本至最低，其中的固定费用不可忽略。假定现在有 \(n\) 种方式可供选择，令：

\(j=1,\ldots,n\) 表示第 \(j\) 种生产方式
\(x_j\) 表示第 \(j\) 种生产方式的产量
\(c_j\) 表示第 \(j\) 种生产方式每件产品的成本
\(k_j\) 表示第 \(j\) 种生产方式的固定成本费用

可以得到各种生产方式的总成本为

\[ P_j=\left\{ \begin{array}{ll} k_j + c_jx_j \,, & \text{当} x_j>0 \,, \\ 0 \,, & \text{当} x_j = 0 \,, \\ j = 1,\ldots,n \,. \end{array} \right. \]

为了统一为一个问题进行讨论，引入0-1变量 \(y_j\)、充分小正实数 \(\varepsilon\) 、充分大正实数 \(M\)，其中

\[ y_i = \left\{ \begin{array}{ll} 1 \,, \text{当采用第}i\text{种生产方式}, & \text{即} x_i>0 \text{时}\,, \\ 0 \,, \text{当不采用第}i\text{种生产方式}, & \text{即} x_i=0 \text{时}\,, \\ j = 1,\ldots,n \,. \end{array} \right. \]

于是得到目标函数以及新的约束条件

\[ \begin{array}{l} \displaystyle \min z=\sum_{i=1}^n(k_iy_i + c_ix_i) \\ \text{s.t.} \left\{ \begin{array}{l} y_j\varepsilon \leqslant x_j \leqslant y_j M \,, \\ y_j \in \mathbb{Z} \,, \\ 0 \leqslant y_j \leqslant 1 \,, \\ j = 1,\ldots,n \,. \end{array} \right. \end{array} \]

上式限制：\(x_j>0\) 时 \(y_i\) 只能取 \(1\)；\(x_i=0\) 时 \(y_i\) 只在取 \(0\) 时才有意义。

*遗留的问题¶

充分大的正实数 \(M\) 究竟应该取多大？
充分小的正实数 \(\varepsilon\) 究竟应该取多小？

指派问题¶

拟分配 \(n\) 人去做 \(m\) 个任务，每人做且仅做一项任务，且每项任务的完成时间都是固定的，设第 \(i\) 人去做 \(j\) 项工作，需花费 \(c_{ij}\) 单位时间，问如何分配工作才能使工人花费时间最少？

给出一个指派问题的实例，只需要给出一个矩阵 \(\boldsymbol{C}=(c_{ij})_{i\times j}\) ，称为指派问题的系数矩阵。

引入0-1变量

\[ x_{ij}=\left\{ \begin{array}{l} 1 \,, \text{第}i\text{人做第}j\text{项工作} \,, \\ 0 \,, \text{第}i\text{人不做第}j\text{项工作} \,, \\ i = 1,\ldots,n \,, \\ j = 1,\ldots,m \,. \end{array} \right. \]

则目标函数表示为

\[ \min \quad \sum_{i=1}^n\sum_{j=1}^m c_{ij}x_{ij} \]

约束条件需要简单讨论一下。

如果 \(n=m\)，则每个人都做一项任务，且每项任务都有一个人做，不存在人或任务空着的情况。

\[ \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^n x_{ij} = 1 \,, \sum_{i=1}^n x_{ij} = 1 \,, \\ x_{ij} \in \mathbb{Z} \,, \text{且} 0 \leqslant x_{ij} \leqslant 1 \,, \\ i,j = 1,\ldots,n \,. \end{array} \right. \]

如果 \(n>m\)，则可能有人没有任务可做。因此可能对于一个人来说，所有的 \(x_{ij}\) 都为 \(0\)，即固定 \(i\) 时，\(\displaystyle \sum_{j=1}^m x_{ij}\) 可能为 \(0\)。

\[ \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^m x_{ij} \leqslant 1 \,, \sum_{i=1}^n x_{ij} = 1 \,, \\ x_{ij} \in \mathbb{Z} \,, \text{且} 0 \leqslant x_{ij} \leqslant 1 \,, \\ i,j = 1,\ldots,n \,. \end{array} \right. \]

如果 \(n<m\)，则可能有任务没有人做。因此可能对于一个任务来说，所有的 \(x_{ij}\) 都为 \(0\)，即固定 \(j\) 时，\(\displaystyle \sum_{i=1}^n x_{ij}\) 可能为 \(0\)。

\[ \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^m x_{ij} = 1 \,, \sum_{i=1}^n x_{ij} \leqslant 1 \,, \\ x_{ij} \in \mathbb{Z} \,, \text{且} 0 \leqslant x_{ij} \leqslant 1 \,, \\ i,j = 1,\ldots,n \,. \end{array} \right. \]

求解方法¶

匈牙利算法
拍卖算法
……

蒙特卡洛法（随机取样法）¶

蒙特卡洛法也称计算机随机模拟方法，源自世界著名赌城——摩纳哥的Monte Carlo。

蒙特卡洛法是基于对大量事件的统计结果来实现一些确定性问题的计算方法。

代码实现¶

使用 Python，方法见计算思维-概率论的Python计算实现-蒙特卡洛模拟

计算机求解¶

Matlab 求解¶

Matlab 标准型¶

Matlab 中，整数规划问题的标准形式为：

\[ \begin{array}{l}\displaystyle \min _x \quad \boldsymbol{f}^\mathrm{T}\boldsymbol{x} \,, \\ \text{s.t.} \left\{ \begin{array}{l} x_i \in \mathbb{Z} \,, \text{其中} i \in \text{intcon} \,, \\ \boldsymbol{A} \cdot \boldsymbol{x} \leqslant \boldsymbol{b} \,, \\ \text{Aeq} \cdot \boldsymbol{x} = \text{beq} \,, \\ \text{lb} \leqslant \boldsymbol{x} \leqslant \text{ub} \,. \end{array} \right. \end{array} \]

其中：

\(\boldsymbol{f},\boldsymbol{x},\boldsymbol{b},\text{beq},\text{lb},\text{ub},\text{intcon}\) 为列向量
\(\boldsymbol{A},\text{Aeq}\) 为矩阵

`intlinprog` 函数¶

[x, fval] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)

其中：

参数
- f 为目标函数的系数向量（最小值形式）
- intcon 为决策向量应取整数值的分量的索引的集合
- A，b 为不等式约束的变量系数矩阵和常数项矩阵
- Aeq，beq 为等式约束的变量系数矩阵和常数项矩阵
- lb，ub 为决策变量的下界和上界
返回值
- x 为决策变量组成的决策向量
- fval 返回目标函数的最优值

求解示例¶

背包问题¶

Python 求解¶

使用 `pulp` 库进行建模¶

import pulp

创建问题¶

problem = pulp.LpProblem("<问题名称>", <问题类型>)

<问题类型> 有两种可选
- pulp.LpMinimize 即最小化问题
- pulp.LpMaximize 即最大化问题

定义决策变量¶

x = pulp.LpVariable(name="x(变量名称)", lowBound=下界, upBound=上界, cat=<变量类型>)

<变量类型> 有三种
- pulp.LpInteger 整数变量
- pulp.LpContinuous 连续变量
- pulp.LpBinary 二元变量（0-1变量）

2 整数规划

理论基础¶

定义¶

分类¶

可能的情况¶

求解方法¶

0-1型整数规划¶

背包问题¶

相互排斥的约束条件¶

引入充分大正实数¶

不引入充分大正实数¶

固定费用的问题(Fixed Cost Problem)¶

*遗留的问题¶

指派问题¶

求解方法¶

蒙特卡洛法（随机取样法）¶

代码实现¶

计算机求解¶

Matlab 求解¶

Matlab 标准型¶

intlinprog 函数¶

求解示例¶

背包问题¶

Python 求解¶

使用 pulp 库进行建模¶

创建问题¶

定义决策变量¶

`intlinprog` 函数¶

使用 `pulp` 库进行建模¶