1、第五章 整数规划1 整数规划问题的提出2 分枝定界法3 割平面法4 0-1型整数规划5 指派问题第五章 整数规划（ 重点和难点 ）1、理解整数规划的数学模型2、了解整数规划模型的类型3、了解整数规划的求解方法4、掌握分枝的思想和步骤（ 重点和难点 ）5、理解割平面法的思想和步骤5、了解 0-1规划的隐枚举法6、掌握指派问题的数学模型和求解方法 （ 重点和难点 ）1 整数规划问题的提出 理解整数规划的数学模型 了解整数规划模型的类型 了解整数规划的求解方法 掌握分枝的思想和步骤 了解 0-1规划的隐枚举法 掌握指派问题的数学模型和求解方法背包问题一背有容量为 250 cm3的背包的小偷进入库房（
2、或某户人家或机房），他需要从若干物品中选择一定数量装入背包带走。可选的物品有 7种，其价值、体积及最大的数量入下表 :物品 1 2 3 4 5 6 7价 值 （元） 200 150 15 50 80 30 500体 积 （ cm3)数量5 5 2 6 12 2 42 15 18 14 8 4 1问小偷应如何选择物品才能使价值最大？令 xi表示小偷选择物品 i的数量 ， 则背包问题的数学模型为体积约束数量约束整数约束 例 1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表 5-1： 问两种货物各托运多少箱 ,可使利润最大 ?货 物 体 积 （每箱 M3)重量 (每
3、箱50kg)利 润 (每箱百元 )甲乙54252010托运限制 24 13问题分析 设 x1,x2分别为甲乙两种货物的托运箱数 (非负整数 ),则 Max z=20x1+10x2 5x1+4x224 2x1+5x2 13 x1， x20， x1， x2整数。求解线性规划的最优解得： x1=4.8， x2=0，Max z=96 。 四舍五入得 x1=5， x2=0， 但不是可行解，取整 x1=4，x2=0是可行解， z=80,是不是最优解呢？不是，因为可行解 x1=4， x2=1对应的 z=90。 那么，如何求整数规划的最优解，这就是本章的主要内容。什么是整数规划？ 1、一个线性规划如果有某些决
4、策变量是整数，则称为整数规划 （ Integer programming)； 2、 整数规划的类型：n纯整数规划；n混合整数规划；n0-1（整数）规划。整数规划的可行解，最优解 x232 +1 + + + + + 1 2 3 4 5 6 7 x12 分枝定界法n对于整数规划问题，如果是两个自变量则可以用 图解法 （要比线性规划难）。n当可行区域有界时，整数可行解的个数为有限个，因此，可把所有的整数可行解求出来，目标函数值最大者对应的可行解就为最优解，这种方法称为 枚举法 。n但是，当变量较多时，可行整数解的个数也很多，其计算量仍然很大。n例如指派 n人做 n件事的问题就有 n!个可行解，当n=10时，可行解超过 300万个，当 n=20时，可行解超过 2*1018个，枚举法就不行了。因此，下面要给出整数规划的 有效求解方法 。
