【数学建模】第二章 整数规划

模型简介

定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。一般整数规划指整数线性规划（在线性规划模型中，变量限制为整数）。

分类

变量全限制为整数时，称纯（完全）整数规划。

变量部分限制为整数时，称混合整数规划。

特点

1. 原线性规划有最优解，当自变量限制为整数时，其整数规划解出现下述情况：

   • 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致
   • 整数规划无可行解
   • 有可行解（当然就存在最优解），但最优解值变差

2. 整数规划最优解不能按照实数最优解简单取整而获得

求解方法

纯或混合整数线性规划：分枝定界法、割平面法

求解“0-1”整数规划：隐枚举法（过滤隐枚举法、分枝隐枚举法）

指派问题（“0-1”规划特殊情形）：匈牙利法

各种类型规划：蒙特卡洛法

分枝定界法

总结用分枝定界法求整数规划（最大化）问题的步骤：

将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B

1. 解问题B可能得到以下情况之一：

   • B没有可行解，这时A也没有可行解，则停止

   • B有最优解并符合A的整数条件，B的最优解即为A的最优解，则停止

   • B有最优解，但不符合问题A的整数条件，记它的目标函数值为 $\overline{z}$

2. 用观察法找问题A的一个整数可行解，一般可取 x_j = 0 , j = 1 , … , n，试探，求得其目标函数值，并记作 $\underline{z}$ 。以 z^* 表示问题 A 的最优目标函数值；这时有

$$\underline{z} ≤ z^*≤ \overline{z}$$

​ 进行迭代

• 第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量 x_j 其值为 b_j ，以 [ b_j ] 表示小于 b_j 的最大整数。构造两个约束条件 x_j ≤ [ b_j ] 和 x_j ≥ [ b_j ] + 1

  将这两个约束条件，分别加入问题B，求两个后继规划问题 B₁ 和 B₂ 。不考虑整数条件求解这两个后继问题

  定界，以每个后继问题为一分枝标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界 $\overline{z}$ ，从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界 $\underline{z}$ ，若无作用 $\overline{z}$ 不变

• 第二步：比较与剪枝，各分支的最优目标函数中若有小于 $\underline{z}$ 者，则剪掉这枝，即以后不再考虑。若大于 $\underline{z}$ 且不符合整数条件，则重复第一步骤，一直到最后得到 $ z^* = \underline{z}$ 为止，得最优整数解

0 - 1 型整数规划

引入0-1变量的实际问题

投资场所的选定（相互排斥的计划）

这是个相互排斥的计划，x_i 是 0-1 变量，直接列式子就行

相互排斥的约束条件

如果有 m 个互相排斥的约束条件：

$$a_{i1}x_1+...+a_{in}x_n≤b_i\ \ i=1,2,...,m$$

为了保证这 m 个约束条件只有一个起作用，我们引入 m 个 0-1 变量 y_i （i = 1,2,..,m）和一个充分大的常数 M ，而下面这一组 m+1 个约束条件

$$a_{i1}x_1+...+a_{in}x_n≤b_i+y_iM\ \ i=1,2,...,m\tag{1}$$ $$y_1+...+y_m=m-1\tag{2}$$

符合上述的要求。因为由于（2）的限制，m 个 y_i 中只有一个能取 0 值，设 y_a = 0，代入（1），就只有 i = a 的约束条件起作用，而别的式子都是多余的。

关于固定费用的问题

某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令

x_j 表示采用第 j 种方式时的产量

c_j 表示采用第 j 种方式时每件产品的变动成本

k_j 表示采用第 j 种方式时的固定成本

采用各种生产方式的总成本分别为

$$P_j=\begin{cases} k_j+c_jx_j & 当x_j>0\\ 0 & 当x_j=0 \end{cases} \ \ j=1,2,3$$

引入0-1变量 y_j ，令

$$y_j=\begin{cases} 1 & 当采用第j种生产方式，即x_j>0时\\ 0 & 当不采用第j种生产方式，即x_j=0时 \end{cases}\tag{3}$$

（3）可以表述为3个线性约束条件

$$y_j\varepsilon≤x_j≤y_jM，j=1,2,3\tag{4}$$

其中$ \varepsilon $是一个充分小的正常数，$M$ 是一个充分大的正常数

目标函数

$$min\ z=(k_1y_1+c_1x_1)+(k_2y_2+c_2x_2)+(k_3y_3+c_3x_3)$$

解法之一：过滤隐枚举法

解0-1型整数规划，最容易想到的方法是穷举法，即检验变量取值为0和1的每一种组合，不过这种方法太复杂了，因此我们常使用隐枚举法，分枝定界法也是其中一种

有时这种方法并不适用，这时穷举法是必要的

举个栗子

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

可以用来解非线性规划问题

占坑，代码简单但是感觉有点不太理解

指派问题

指派问题在上一章中已经写过一次了，代码会在matlab总结中给出 写好代码放着……

分段线性函数