整数规划¶

整数规划是部分（或全部）决策变量均取整数的线性规划。全部决策变量均取整数的整数规划称为纯整数规划。如果整数变量只能取0-1两个值，则称为0-1整数规划。

整数规划的求解方法¶

求解整数规划目前有如下算法：

割平面法
分支定界法
隐枚举法（适用于求解0-1整数规划）
启发式算法

考虑如下形式的纯整数规划问题：

\[ \begin{aligned} & \max z=c^Tx \\ & s.t. \left\{ \begin{aligned} & AX \leq b \\ & X\geq 0 \end{aligned} \right . \end{aligned} \]

其中$A, b, x$均为整数。

割平面法¶

称消除整数约束的整数规划为松弛问题，割平面法首先需要求解松弛问题的最优解，设为$X^*$。通常情况下，$X^*$不是整数或不全是整数。单纯形表如下所示：

$1$

设单纯形表中的第$i$行对应的$b'_i$不为整数，对于这一行，有：

\[ x_i + \sum_{j=m+1}^n a'_{ij}x_j = b'_i \]

将$a'_{ij}, b'_i$划分为整数部分与小数部分，即：

\[ \begin{aligned} a'_{ij} &= \tilde a_{ij} + \alpha_{ij}, \; \tilde a_{ij} = \lfloor a'_{ij}\rfloor \\ b'_{i} &= \tilde b_{i} + \beta_{i}, \; \tilde b_{ij} = \lfloor b'_{i}\rfloor \end{aligned} \]

将这一行等式变形，得到：

\[ \beta_i - \sum_{j=m+1}^n\alpha_{ij}y_j = x_i - \tilde b_i + \sum_{j=m+1}^n \tilde \alpha_{ij}y_j \]

整数规划的条件要求等式右侧为整数，因此等式左侧同样需要为整数，则有$\beta_i - \sum_{j=m+1}^n\alpha_{ij}y_j + s_i = 0$，其中$s_i$为非负整数。

称方程

\[ \beta_i - \sum_{j=m+1}^n\alpha_{ij}y_j + s_i = 0 \]

为割平面方程，割平面方程作为约束条件，消去了非整数最优解，留下整数解。向松弛问题的最优单纯形表中加入割平面方程作为新的约束条件，继续求解线性规划即可得到整数规划的最优解。

分支定界法¶

先求解整数规划对应的松弛问题，并估计一个非最优的目标函数值作为记录的最优值。对于最优解中的非整数决策变量，选择其中一个$x_i$进行分支：

添加约束$x'_i \leq \lfloor x_i \rfloor$
添加约束$x'_i \geq \lceil x_i \rceil$

添加约束后重新求解线性规划，如果线性规划的解满足整数约束，则将目标函数值与记录的最优值相比较。如果目标函数更优，则更新最优值，否则停止向下探索（剪枝）。

分支可以采取深度优先搜索或广度优先搜索。

隐枚举法¶

考虑如下形式的0-1整数规划：

\[ \begin{aligned} & \max z=c^Tx \\ & s.t. \left\{ \begin{aligned} & AX \leq b \\ & x_i \in \{0, 1\} \end{aligned} \right . \end{aligned} \]

首先试探出一个可行解，对应的目标函数值作为记录的最优值$Z_0$，再枚举所有的可行解，若解的目标函数值超过最优值则更新最优值。

指派问题¶

指派问题是特殊的0-1整数规划问题，其目标是将$n$个工人在$n$个工作中分配，每个工人$i$在进行工作$j$时，都会产生成本$c_{ij}$，决策问题的目标是最小化总成本。记成本矩阵为

\[ A = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1n} \\ c_{21} & c_{22} & \cdots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{n1} & c_{n2} & \cdots & c_{nn} \end{bmatrix} \]

性质

若系数矩阵$A$的某一行或某一列减去分别减去一个常数$k$，不影响指派问题的解。

使用匈牙利算法求解整数规划问题。首先对系数矩阵先减去每行的最小值，再减去每列的最小值。从而每行、每列中至少出现一个零。定义“独立零”为系数矩阵中既不处于同一行、也不处于同一列的$0$的最大个数。

若“独立零”的个数等于方阵的维度，则得到指派问题的最优解，最优解的指派方案与独立零的位置分布相同。
若“独立零”的个数小于方阵的维度。首先找出方阵中能够覆盖所有零元素的最少直线数。在不被直线覆盖的元素中寻找最小值，将所在行或列减去这个最小值。然后对产生的负值进行调整，直到矩阵中不存在负值。结束后继续检查独立零的个数。