《整数规划 割平面法 分枝定界法.ppt》由会员分享，可在线阅读，更多相关《整数规划 割平面法 分枝定界法.ppt（16页珍藏版）》请在三一办公上搜索。
1、运 筹 学,整数线性规划,1 整数规划问题,在前面的线性规划问题中，它的解都假设为可以取连续数值。但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮数等等。为了满足整数解的要求，比较自然的简便方法似乎就是把用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾取整”处理。当然，这样做有时确实也是有效的，可以取得与整数最优解相近的可行整数解，因此它是实际工作中经常采用的方法。但是实际问题中并不都是如此，有时这样处理得到的解可能不是原问题的可行解，有的虽是原问题的可行解，但却不是整数最优解。（详见后面例1）。因而有必要专门研究只
2、取整数解的线性规划的解法问题。在一个线性规划问题中，如果它的所有决策变量都要求取整数时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混合整数规划，二者统称为整数规划。整数规划的一个特殊情形是0-1规划，它的决策变量取值仅限于0或1两个逻辑值。整数规划是近几年发展起来的规划论的一个分支。,下面我们举例说明对于整数规划问题，用“四舍五入”取整，或“舍尾取整”方法，是行不通的。例1 现有甲、乙两种货物拟用集装箱托运，每件货物的体积、重量、可获利润，以及集装箱的托运限制如下表：,试确定集装箱中托运甲、乙货物的件数，使托运利润最大。设x1,x2分别表示甲、乙货物托运的件数（整数），则该问题的数学
3、模型为：maxZ=20 x1+10 x2 5x1+4x224 2x1+5x213 x1,x20，整数,这里货物的件数只能是整数，所以这是一个纯整数规划。若先不考虑整数限制，可求得问题的最优解为：x1=4.8，x2=0，maxZ=96由于x1=4.8不符合整数要求，所以该解不是整数规划的最优解。是否可以将非整数解用“四舍五入”方法处理呢？事实上，如果将x1=4.8，x2=0近似为x1=5，x2=0，则该解不符合体积限制条件：5x1+4x224因而它不是最优解；那么用“舍尾取整”方法处理又如何呢？将x1=4.8，x2=0“舍尾取整”为x1=4，x2=0，显然满足各约束条件，因而它是整数规划问题的可
4、行解，但它不是整数最优解。因为它对应的目标函数值Z=80，而x1=4，x2=1这个解亦是可行解，但它对应的目标函数值Z=90。由此例看出，简单的处理方法常常得不到整数规划的最优解，甚至得不到可行解。如何求得这类问题的整数最优解呢？到目前为止，整数规划还没有一种很满意的和有效的解法。现在用以求解整数规划的方法基本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种方法割平面法和分枝定界法。,2 割平面法,割平面法是1958年美国学者R.E.Gomory提出的求解纯整数规划的一种比较简便的方法，其基本思想是：先不考虑变量的整数限制求解线性规划，如果得到的解不是整数解，则不断增加适当的约束，割掉
5、原可行域不含整数解的一部分，最终得到一个具有若干整数顶点的可行域，而这些顶点中恰有一个顶点是原问题的整数解。割平面法的基本步骤：步骤1 不考虑变量的整数限制，求解相应的线性规划问题，如果该问题无解，或最优解已是整数解，则停止计算，否则转下一步。步骤2 对上述线性规划的可行域进行“切割”，去掉不含整数解的一部分可行域，即增加适当的线性约束，然后转步骤1。,割平面法的关键在于如何确定切割方程，使之能对可行域进行真正的切割，而且切去部分不含有整数解点。下面讨论切割方程的求法。,设与整数规划相对应的线性规划最优解中基变量XBi=（B-1b)i不是整数，将最优单纯形表中该基变量对应的行还原成约束方程，即
6、 XBi+aijXj=（B-1b)i 将（B-1b)i，aij都分解成整数与非负真分数之和的形式，即（B-1b)i=Ni+fi 其中0 fi 1 aij=Nij+fij 其中0 fij 1 这里Ni、Nij是整数，将、代入，得 XBi+（Nij+fij）Xj=Ni+fi 即 XBi+NijXj-Ni=fi-fijXj 当诸Xi都是整数时，式左端是整数，所以右端亦应是整数，但右端是两个正数之差，且0 fi 1，fi-fijXj是小于1的整数，从,从而 fi-fijXj0 取式作为切割方程。因为任何整数可行解都满足这个方程，所以把它加到原问题的约束中，它能够对原可行域进行切割，而不会切割掉整数解。
7、,例3 用割平面法求解 maxZ=x1+x2-x1+x21 3x1+x24 x1,x20，整数,解：将问题标准化得 maxZ=x1+x2-x1+x2+x3=1 3x1+x2+x4=4 x1,x20 x1,x2 整数,不考虑条件，求解相应线性规划，结果见下表：,表中x1=3/4，不是整数，将表中第一行还原成方程，即 x1-1/4x3+1/4x4=3/4因为3/4=0+3/4，-1/4=-1+3/4，1/4=0+1/4所以有 x1-x3=3/4-3/4x3-1/4x4因而有切割方程：3/4x3+1/4x4 3/4 即 3x3+x4 3引入松弛变量x5，得方程-3x3-x4+x5=-3将新约束方程加
8、到原最优表下面（切割），求得新的最优解如下：,由于x1，x2的值已是整数，所以该题经一次切割已得最优解：x1=1，x2=1，最优值：Z=2,现在我们来看看切割方程 3x3+x4 3 的几何意义。例3对应的线性规划为 maxZ=x1+x2-x1+x21 3x1+x24 x1,x20,用图解法求得可行域D及最优解点A，见下图：,x2,x1,1,1,-1,0,-x1+x2=1,3x1+x2=4,A（3/4，7/4）,由标准化的约束方程组可得 x3=1+x1-x2 x4=4-3x1-x2代入切割方程 得 3（1+x1-x2）+（4-3x1-x2）3即 x21，将此切割方程 加入原约束中，就等于切掉原可
9、行域得A1B部分，如图。,B（1，1）,D,显然在A1B区域不含整数解点，对原可行域切割的结果是产生了一个新顶点B，用图解法在新的可行域（黄色）中可求得整数最优解恰是B（1，1）。,在求解实际问题中，割平面法经常会遇到收敛很慢的情况，但若和其它方法，如分枝定界法，联合使用，一般能收到比较好的效果。,3 分枝定界法,分枝定界法是求解整数规划的常用算法，既可用来解全部变量取值都要求为整数的纯整数规划，又可用以求解混合整数规划。该算法的基本思路是：先不考虑整数限制，求出相应的线性规划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分可行域，将可行域D分成D1、D2两部分（分枝），然后分别求解这
10、两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两部分，再求解D3与D4对应的线性规划，在计算中若已得到一个整数可行解X0，则以该解的目标函数值Z0作为分枝的界限，如果某一线性规划的目标值Z Z0，就没有必要继续分枝，因为分枝（增加约束）的结果所得的最优解只能比Z0 更差。反之若Z Z0，则该线性规划分枝后，有可能产生比Z0 更好的整数解，一旦真的产生了一个更好的整数解，则以这个更好的整数解目标值作为新的界限，继续进行分枝，直至产生不出更好的整数解为止。下面以实例来说明算法的步骤。,例2 求解下面整数规划 maxZ=40
11、 x1+90 x2 9x1+7x256 7x1+20 x270 x1,x20 x1,x2整数,解：先不考虑条件，求解相应的线性规划问题L，得最优解 x1=4.81，x2=1.82，Z0=356（见图）,x2,8,0,6,4,10,x1,9x1+7x2=56,7x1+20 x2=70,Z=40 x1+90 x2,该解不是整数解。选择其中一个非整数变量，如x1=4.81，对问题L分别增加约束条件：x14，x15将问题L分解为两个子问题L1，L2（分枝），也就是去掉问题L不含整数解的一部分可行域，将原可行域D变为D1、D2两部分（如图）。,4,D1,D2,因为没有得到整数解，所以继续对L1进行分解，
12、增加约束：x22，x23将L1分解成问题L3与L4，并求得最优解如下：,问题L3的解已是整数解，它的目标值Z3=340，大于问题L4的目标值，所以问题L4已无必要再分枝。但由于问题L2的目标值Z2大于Z3，分解L2还有可能产生更好的整数解，因此继续对L2分枝。增加约束 x21，x22将L2分解成问题L5与L6，并求解，结果如下：,问题L5的Z5=308 Z3=340，所以不必分解了；问题L6无可行解，于是可以断定问题L3的解：x1=4.00，x2=2.00即为最优整数解。,整个分枝定界过程如下图所示：,问题LZ0=356x1=4.81x2=1.82,问题L1Z1=349x1=4.00，x2=2
13、.10,问题L2Z2=341x1=5.00，x2=1.57,问题L3Z3=340 x1=4.00 x2=2.00,问题L4 Z4=327x1=1.42x2=3.00,问题L5Z5=308x1=5.44，x2=1.00,问题L6无可行解,x14,x15,x22,x23,x21,x22,Z=340,用分枝定界法求解整数规划的步骤可总结如下：步骤1：求解与整数规划相对应的线性规划L，若L无可行解，则整数规划也没有可行解，计算停；若L的最优解是整数解，则该解即为整数规划的最优解，计算停；若L的最优解不是整数解，则转步骤2。步骤2（分枝）在L的最优解中任选一个不符合整数条件的变量XBi，其值为（B-1b
14、)i，（B-1b)i 为小于（B-1b)i的最大整数，构造两个约束条件 XBi（B-1b)i 和XBi（B-1b)i+1将这两个约束条件分别加在问题L的约束条件上，形成两个子问题L1和L2，并求解L1和L2。步骤3（定界）取整数解中最大目标值为界限值Z(下界)，如果计算中尚无整数解，则取Z=-。检查分枝Li，若它的最优解不是整数解，且ZiZ，则重复步骤2，若ZiZ，则Li不再分枝。重复步骤2、步骤3，直至所有分枝都不能再分解为止，这时界限值Z对应的整数解即为原问题的最优解。用分枝定界法可解纯整数规划问题和混合整数规划问题。它比穷举法优越，因为它仅在一部分可行的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。,
