05-整数规划问题

• 整数规划问题：

$$\begin{array}{rl}\mathrm{minimize}& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{ subject to }& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}⩾0\\ & \mathbf{x}\in {\mathbb{Z}}^n\end{array}$$

割平面法

• 思路：通过增加约束条件，把由单纯形法得到的非整数解从可行集中去掉，新增的约束条件不去除可行集中的整数解。通过不断增加约束条件，直到得到一个整数最优解。

• 计算步骤：

  1. 按照正常单纯形法计算最后一张单纯形表；
  2. 最优解非整数解时，如果解的第 $x_i$ 分量不是整数解，那么利用单纯形表的第 $i$ 行构造割平面方程：第 $i$ 行的非整数部分$a_{i,j}$，新引进的人工松弛变量 $x_t$ ,构造方程 $\Sigma (a_{i,j}-\left[a_{i,j}\right])x_i-x_t=b_i-\left[b_i\right]$ ,放到单纯形表里当成新约束。
  3. 重复一二步骤直到最优解里没有非整数解。

割平面法计算实例

计算实例|课程PPT

$$\begin{array}{rlr}\mathrm{maximize}& 3x_1+4x_2& \\ \text{ subject to }& 3x_1-x_2⩽12x_1,x_2⩾0& \\ & 3x_1+11x_2⩽66x_1,x_2\in \mathbb{Z}& \end{array}$$

计算实例2|课程PPT

分支定界法

• 思路：假设 $x_j$ 是一个非整数分量，借助 $x_j$ 将原规划问题分解成两个整数规划，再判断最优解在哪个分支上，舍弃另外一个分支，重复步骤直到得到最优解。

• 步骤：

  1. 根据原命题得到最优解，最优解里含有非整数向量 $x_i$ ,且实数值 $t_1$ 是不超过 $x_i$ 的最小整数，构造约束条件 $x_i⩾t_1+1$ 构造 ${\mathbf{P}}_1$ 问题和构造约束条件 $x_i⩽t_1$ 得到 ${\mathbf{P}}_2$ 问题。
  2. 在原 ${\mathbf{P}}_0$ 问题中得到一个可行解 $x_0$ ，放到新问题 ${\mathbf{P}}_1$和问题 ${\mathbf{P}}_2$ 中计算

分支定界法计算实例

计算实例|课程PPT