Page 136 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

2. 整数规划无可行解。
例 原线性规划为

其最优实数解为 ，而对应的整数规划无可行解
3. 有可行解 ( 当然就存在最优解），但最优解值变差。
例 原线性规划为

若限制为整数，得 x 1 =1，x 2 =1，minz=2。
（二）整数规划最优解不能按照实数最优解简单取整而获得。
求解方法分类：

1. 分枝定界法可求纯或混合整数线性规划。
2. 割平面法—可求纯或混合整数线性规划。
3. 隐枚举法—求解“0 － 1”整数规划。
①过滤隐枚举法；

②分枝隐枚举法。
4. 匈牙利法一解决指派问题 (“0 － 1”规划特殊情形）。
5. 蒙特卡洛法一求解各种类型规划

第二节 0~1 整数规划的模型

0-1 型整数规划是整数规划中的特殊情形，它的变量 xj；仅取值 0 或 1。这

时 xj；称为 0-1 变量，或称二进制变量。xj 仅取值 0 或 1 这个条件可由下述约束
条件 为整数所代替，是和一般整数规划的约束条件形式一致的。
在实际问题中，如果引人 0 － 1 变量，就可以把有各种情况需要分别讨论的数学

规划问题统一在一个问题中讨论了。下面介绍引 l 人 0 － 1 变量的实际问题。

一、相互排斥的约束条件

有两种运输方式可供选择，但只能选择一种运输方式，或者用车运输，或者

126