整数规划课程.doc

第13章 整数规划 本章通过分析应用问题建立数学模型并求解，学习掌握整数规划及其求解的分枝定界算法以及应用MATLAB求解。加强从“模型的建立到求解”的数学建模重要过程的实验活动。补充知识，将介绍0—1规划及其求解的隐牧举算法，并介绍如何用MATLAB求解。 13.1 引例 现4有一节火车货车车厢，长10m，最大载重量为40t，可以运载7类货物包装箱。包装箱的长度和重量不同，但宽度高度相同且适合装车，每件包装箱不能拆开装卸。今有如表13-1所示货物，请给出装货方案，使总的价值最大。 表13-1 货物数据表 货物 长度(cm) 重量(t/件) 价值(千元) 件数 1 55 0.5 40 8 2 58 1.7 37 8 3 62.4 3 58 6 4 49 2.2 36 7 5 40.6 3 35 3 6 53.3 1 45 4 7 66 4 50 8 设xi代表该车厢装入第i类货物包装箱的件数。则易得如下数学模型 此模型与前面所讲的线性规划模型极为相似，所不同的是在此要求变量为正整数，此类优化问题称为整数线性规划。对于变量限定只取0或1的整数线性规划称为0-1线性规划。 13.2 基本理论介绍 整数规划是一类要求变量取值为整数的数学规划。若整数规划中目标函数和约束条件都是线性的，则称之为整数线性规划(integer linear programming，简记为ILP)。若只要求部分变量取整数，则称为混合整数规划。 13.2.1问题的表述 在一般的线性规划中增加限定：决策变量为整数，即为ILP问题： 标准形式为： 其中 13.2.2算法 求解ILP问题时，如果可行域是有界的，理论上可以用穷举法求解，对于变量个数较少时此法可行，但变量个数较多时这种穷举法往往是行不通的。到目前为止，还缺乏十分有效的算法。分枝定界法是应用的最为广泛的一种算法。分枝定界法是1960年初由Doig和Land等人提出来的，可用于求解纯整数规划和混合整数规划问题。分枝定界法比穷举法优越，它仅在一部分可行解的整数解中寻找最优解，计算量比穷举法小。当然，若变量个数很大，其计算量也相当大。 分枝定界法的基本思想如下。 首先不考虑ILP中变量的整数约束，求解相应的线性规划问题(LP): 若最优解中所有的变量都取整数，则已得到整数规划的最优解。否则，记它此时的目标函数值为f0、最优解为。这时若记f为ILP的最优目标函数值，则必有. 如果其中某一个值li不是整数，那么分枝：即分别求解如下两个子问题： 这样做，实际上是 将原约束区域中不含任何整数解的区域去掉，在剩下的约束区域寻找最优解。 分别以LP1和LP2后继子问题为一分枝并标明求解的结果，找出最优目标函数值最小者作为新的下界，替换f0。 应当指出子问题的最优目标值一定不会优于原问题的目标函数值。如果两个子问题的任何一个的解仍然不是整数，则继续选择一个非整数变量，将这个子问题再次分解为更下一级的子问题。 如果某一个子问题的最优解已满足变量为整数的要求，这就得到一个可行的整数解。将这个这个子问题的目标函数值记录下来，作为整数规划最优目标值的上界。从已符合整数条件的各分枝中，找出目标函数值为最小者作为新的上界f*，即有。 如果其他子问题在分枝过程中，尽管尚未获得整数解，但该子问题的目标函数值已超过这个上界，则这个分枝无须再分枝求解。这是因为即使继续分枝再得到一个整数解，这个解的目标函数值，一定会超过所得到的上界，从而不可能是最优解。因此，利用定界，可以终止许多不必要的分枝过程，此为剪枝。 如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则将较小的整数解的目标值代替原来的上界。因为上界越小，就可能删除更多不必要的分枝。 当所有最底层子问题出现以下三种情况之一时，分枝定界算法终止。 子问题无可行解； 子问题已获得整数解； 子问题的目标函数值超过上界。 我们用一个例子来说明上述过程。 例1：求解如下整数规划 解：先解相应的 得： 按条件将问题LP分解成如下子问题LP1和LP2并赋它们的下界为14.2。 求解LP1得：； 求解LP2得：； 可见，LP2可分成两个子问题LP3和LP4并赋他们下界为14.33。 求解LP3得：；求解LP4得：； 由于x3和小x4是原整数规划问题的可行解且，所以置f*=15为上界。 以下再将LP1分枝为如下LP5和LP6，并赋予它们下界14.33。 求解LP5得:； 求解LP6得:； 由于f5、f6f*=15，所以LP5和LP6都没有继续分枝求解的必要。至此求得最优解x*=x3=（0，5，0）或x*=x4=（1，4，0），最优目标函数值为f=f3=f4=