本章主要介绍求整数规划问题的割平面法分枝定界法以及解01规划.doc

本章主要介绍求整数规划问题的割平面法、分枝定界法以及解0—1规划的隐枚举法。基本要求为： 1.熟悉整数规划问题的特征。 2.了解割平面算法。 3.会应用分枝定界算法求简单的整数规划问题。 4.能用隐枚举法求简单0—1规划问题的解。 第一节　整数规划问题的基本概念 一．关于整数规划 Integer, Programming）,简称IP，整数规划是近二十年发展起来的规划论中一个重要分枝。 整数规划中如果所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；如果仅一部分变量限制为整数，则称为混合整数规划，整数规划中有一个特殊的情形是0—1规划，它的变量取值仅限于0或1。现举例说明用前述单纯形法求得的解不能保证是整数最优解。 例题1 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运所受限制如下表所示： 货 物 体积 每箱（米3） 重量 每箱（百斤） 利润 每箱（百元） 甲 5 2 20 乙 4 5 10 托运限制 24 13 ? 先不考虑整数约束的条件，求解相应的线性规划问题，得最优解为：x1= 4.8，x2= 0 ，z0= 96。 如将x1= 4.8，x2= 0凑整为x1= 5， x2= 0，就不是可行解；若将x1= 4.8舍去尾数0.8，就变为x1= 4，x2= 0是可行解但不是最优解，因为最优解是x1= 4，x2= 1。由此看来，非整数解“凑整”的方法容易想到，但常常得不到整数最优解，甚至根本不是可行解。因此有必要对整数规划的解法进行专门研究。 Zc=96 Zd=90 二．整数规划问题的图解法 Zr=70 通过上图可以看出，对于目标函数为max型的整数规划问题，若不考虑整数约束求出的最优解（称为连续解）对应的目标函数值为Zc ，用整数规划求出的整数解最优解（称为离散解）对应的目标函数值为Zd ，一个连续解凑整后对应的目标函数值为Zr ，则三者之间有如下关系（这是后面分枝定界算法中是否终止分枝的一个重要的判别条件,也就是常说的“定界”）。 Zr ≤ Zd ≤ Zc 另外，还会看到，越靠近最优连续解（坐标点）的整数点，越有可能是整数最优解。这就对下面算法中设定分枝条件提供了思路，那就是从最接近最优连续解的整数开始分枝，比较容易求得最优解。 O [ bk /] bk/ [bk /]+1 设bk/是连续最优解的一个非整数分量，xk= bk/，那么最接近bk/ 的整数是：?[bk/] 和 [bk/] +1 分别沿着比[bk/]小或比[bk/] +1大的两个方向有哪些信誉好的足球投注网站最优整数解。这个过程就相当于在bk/处分枝，构造了xk≤[bk/] 和xk≥[bk/] +1两个约束条件，加入到初次获得非整数解的最优单纯形表中求解，求解方法当然是我们以前学过的对偶单纯形法。 分枝定界算法 先不考虑整数约束的条件求出相应的线性规划问题的最优解， 如果这个解满足已定的整数约束，它就是整数规划问题的最优解。 如果有一个或多个整数约束未被满足，就任选一个应是整数而不 是整数解的变量xk，设它的解是bk/，不是整数，定义[ bk/ ] 是 小于bk/ 的最大整数，将原问题分成两枝。一枝是原问题约束条 件加xk≤[ bk/]构成，另一枝是原问题约束条件加xk≥[ bk/ ]+1 构成。解这两个分枝的新线性规划问题。对不满足原问题整数约 束的新问题，再按上述办法进行新的分枝，直到发生下面所说的 情况才停止分枝。我们仍用 例2来说明算法求解过程。 例题：求解 ： 解：先不考虑整数约束的条件，解相应的线性规划问题，得最优 解为 　　x1= 4.81 x2= 1.82 z0= 356 x1=4.83, x2=1.82 z0=356 x1=4 , x2=2.1 z1=349 x1=1.42, x2=3 z0=327 x1=5.44, x2=1. z0=308 x1=5, x2=1.57 z0=341 x1=4, x2=2 z0=340 分枝过程： 割平面算法 这个方法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑变量xi是整数这一条件，但增加线性约束条件（用几何术语，称为割平面）从原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是支持怎样找到适当的割平面（不见得一次就找到），使切割后最终得到这样的可行域，它的一个有整数坐标的极点（顶点）恰好