1、1第第3章章 整数规划整数规划ILP问题的概述问题的概述2整数规划概述整数规划概述 在线性规划问题中，所有的解都假设为具有连续在线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或带有小数点型的数值，即解可以是整数、分数或带有小数点的实数。的实数。但对于某些具体的问题，常要求最优解是整数的但对于某些具体的问题，常要求最优解是整数的情形。例如，所求的解是机器台数，完成工作的情形。例如，所求的解是机器台数，完成工作的人数或装货的车数等，这时，分数或小数的解答人数或装货的车数等，这时，分数或小数的解答就不符合要求。就不符合要求。为了满足整数解的要求，初看起来，似乎只要把为了满足整
2、数解的要求，初看起来，似乎只要把已求得的解经过已求得的解经过“舍入化整舍入化整”就可以，但这常常就可以，但这常常是不可行的。（因为化整后不见得是可行解。或是不可行的。（因为化整后不见得是可行解。或虽然是可行解，但不一定是最优解。）虽然是可行解，但不一定是最优解。）3整数规划概述整数规划概述 求最优整数解的问题，称为整数规划求最优整数解的问题，称为整数规划(Integer Programming)，简称为，简称为 IP。整数规划中，如果所有的变量都要求是非负整数，就称为整数规划中，如果所有的变量都要求是非负整数，就称为纯整数纯整数规划规划(Pure Integer Programming)或全整
3、数规划或全整数规划(All Integer Programming)。如果仅是其中一部分变量取值为整数，则称为如果仅是其中一部分变量取值为整数，则称为混合混合整数规整数规划划(Mixed Integer Programming)。如果变量只取如果变量只取0或或1，则称为，则称为0-1规划规划。由于变量限制为整数实质上一个非线性约束，如由于变量限制为整数实质上一个非线性约束，如0、1限制，限制，因此：整数规划问题的求解要比一般的线性规划困难得多。因此：整数规划问题的求解要比一般的线性规划困难得多。43.1 整数线性规划问题整数线性规划问题 整数规划是一类要求变量取整数值的数学规划。整数规划是一类
4、要求变量取整数值的数学规划。对于两个变量的整数规划，可以用图解法，但对于一般对于两个变量的整数规划，可以用图解法，但对于一般的整数规划问题，则需要专门的方法：割平面法、分枝的整数规划问题，则需要专门的方法：割平面法、分枝定界法、定界法、(隐枚举法、匈牙利法隐枚举法、匈牙利法)。本章的讲解将从图解。本章的讲解将从图解法开始，引出若干个启示后，再学习专门的方法。法开始，引出若干个启示后，再学习专门的方法。,2,1,0,),(,2,1,0.min1 IxxxRbRcnmAnJiIxxbAxtsxcTnmniT矩矩阵阵为为53.1.1 整数规划的典型问题举例整数规划的典型问题举例1.投资决策问题投资决
5、策问题某部门在今后五年中可用于投资的资金额为某部门在今后五年中可用于投资的资金额为B万元，万元，有有n(n 2)个项目，假定每个最多投资一次，第个项目，假定每个最多投资一次，第j个项个项目需资金目需资金bj万元，将会获利万元，将会获利cj万元，问如何投资使总万元，问如何投资使总利润最大。利润最大。2.承建宿舍问题承建宿舍问题某建筑公司建两类宿舍，甲占地某建筑公司建两类宿舍，甲占地0.25 103(m2)，乙，乙占地占地0.25 103(m2)，已购进地，已购进地3 103(m2)。计划甲。计划甲不超过不超过8幢，乙不超过幢，乙不超过4幢，问如何建使获利最大幢，问如何建使获利最大？3.旅行售货员
6、问题旅行售货员问题一推销员从一推销员从v0出发，再遍访出发，再遍访v1,v2,vn各一次，再各一次，再返回返回v0。从。从vi到到vj的差旅费为的差旅费为cij，如何使总费用最小。，如何使总费用最小。4.背包问题等背包问题等6例例1：某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备需要需要A、B两种材两种材料的消耗以及资料的消耗以及资源的限制，如右源的限制，如右表。表。问题：工厂应分问题：工厂应分别生产多少件甲、乙种仪器设备才别生产多少件甲、乙种仪器设备才能使工厂获利最多？能使工厂获利最多？甲乙资源限制材料 A32
7、10材料 B025单件获利1 万元1 万元解：解：目标函数：目标函数：Max z=x1+x2 约束条件：约束条件：s.t.3 x1+2 x2 10 2 x2 5 x1，x2 0 为整数为整数不考虑整数约束得到最优解：不考虑整数约束得到最优解：x1=1.667，x2 =2.5；z =4.167考虑整数约束得到最优解：考虑整数约束得到最优解：x1=2，x2 =2；z =4整数规划的最优目标值小于相应整数规划的最优目标值小于相应线性规划的最优目标值线性规划的最优目标值(相当于附加一个约束相当于附加一个约束)3.1.2 图解法求解及启示图解法求解及启示7例例2：某集装箱运输公司，箱型标准体积某集装箱运
8、输公司，箱型标准体积24m3，重量，重量13T,现有两种货物可以装运，甲货物体积现有两种货物可以装运，甲货物体积5m3、重量、重量2T、每件、每件利润利润2000元；乙货物体积元；乙货物体积4m3、重量、重量5T、每件利润、每件利润1000元，如何装运获利最多？元，如何装运获利最多？maxZ=2000 x1+1000 x2s.t.5x1+4x224 2x1+5x2 13 x1,x2 0且为整数且为整数解此解此LP问题，问题，得：得：X1=4.8，X2=0显然不是可行解显然不是可行解整数规划图解法整数规划图解法x1 1 2 3 4 5 6 7 231BAx2B（4，1）才是才是IP的最优解的最优
9、解8图解法的启示图解法的启示 整数规划与一般线性规划之间有联系，一般我们称不加整数规划与一般线性规划之间有联系，一般我们称不加上整数约束的问题为对应整数规划问题的松弛问题。其上整数约束的问题为对应整数规划问题的松弛问题。其解也有联系：解也有联系：两者之间的解不能简单的通过取整得到。如例两者之间的解不能简单的通过取整得到。如例2：A（4.8，0）点是）点是LP问题的可行解，不是问题的可行解，不是IP问题的可行问题的可行解，解，B（4，1）才是）才是IP的最优解，因此纯整数规划的可的最优解，因此纯整数规划的可行解就是可行域中的整数点；行解就是可行域中的整数点；非整数点不是可行解，对于求解没有意义，
10、故切割掉可非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化行域中的非可行解，不妨碍整数规划问题的优化 整数规划的最优目标值小于相应对于求最大问题，整数整数规划的最优目标值小于相应对于求最大问题，整数规划的最优目标值小于相应线性规划的最优目标值，对规划的最优目标值小于相应线性规划的最优目标值，对于求最小问题，线性规划的最优目标值是对应整数规划于求最小问题，线性规划的最优目标值是对应整数规划的下界。的下界。如果一般线性规划无解，则对应的整数规划也无解如果一般线性规划无解，则对应的整数规划也无解93.1.3：整数规划的模型：整数规划的模型10 请大家试着建立
11、该题的模型！1112131415整数规划问题的求解方法整数规划问题的求解方法3.2 Gomory 割平面法割平面法 3.3 分枝定界法分枝定界法1617181920O 1 2 3 4 5 6 7 8 9 105 4 3 2 1I(2,4)B(9.2,2.4)AD21O 1 2 3 4 5 6 7 8 9 105 4 3 2 1I(2,4)B(9.2,2.4)AD22O 1 2 3 4 5 6 7 8 9 105 4 3 2 1I(2,4)B(9.2,2.4)AD23X1 2X1 6X2 3X2 2X1 3X1 7X2 4X2 3P1P5P4P2P3P24253.2 割平面法割平面法263.2
12、割平面法割平面法（Cutting Place Approach）解法：解法：若若P0有最优，且为整数，则有最优，且为整数，则P达最优；达最优；若若P0有最优，但不为整，增加一个割平面条件；有最优，但不为整，增加一个割平面条件；若若P0无最优，则无最优，则P无最优。无最优。27割平面条件割平面条件 割平面条件：将由（割平面条件：将由（P0）得到的非整数）得到的非整数解恰在被割掉，而原来解恰在被割掉，而原来ILP的可行解（均的可行解（均为整数）都没有被割掉。为整数）都没有被割掉。然后得到然后得到LP问题（问题（P1），再判断它的解。），再判断它的解。如此循环，直到找到最优整数解。如此循环，直到找到
13、最优整数解。28例：例：max x2 s.t.3x1+2x2 6 -3x1+2x2 0 x1，x2 0，整数，整数-3x1+2x2=6x1x20-3x1+2x2=011223图解法：图解法：x2=1x1=x2293.3 分枝定界法分枝定界法（Branch and Bound Method）3031323334350 1 2 3 44 3 2 1x1x23637380 1 2 3 44 3 2 1x1x2394041X1 2X2 2X1 1X2 3P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=
14、111/104243 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p44 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2pP1454647 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2pP4484950X1 4X2 1X1 X2 2P1:(3,3/2)Z=9P4:(2,2)Z=10P2:无可行解无可行解P3:无可行解无可行解P:(10/3,4/3)Z=26/351 分枝定界法是分枝定界法是求整数规划的一种求整数规划的一种常用的有效的方法，常用的有效的方法，既能解决纯整数规既能解决纯整数规划的问题，也能解划的问题，也能解决混合整数规
15、划的决混合整数规划的问题。问题。练习：练习：Min f=-5Min f=-5x x1 1-4-4x x2 2s.t.3s.t.3x x1 1+4+4x x2 2 24 24 9 9x x1 1+5+5x x2 2 45 45 x x1 1,x x2 2 0 0 整数整数52第第3章章 整数规划整数规划本章要求本章要求 理解整数规划的含义与解的特殊性理解整数规划的含义与解的特殊性 掌握割平面法的思想和方法掌握割平面法的思想和方法 掌握分枝定界法的思想和方法掌握分枝定界法的思想和方法53补充内容补充内容 0-1规划问题的模型建构规划问题的模型建构54 某些特殊问题，只做是非选择，故变量设置某些特殊
16、问题，只做是非选择，故变量设置简化为简化为0或或1，1代表选择，代表选择，0代表不选择。代表不选择。例例 若用若用600万元投资万元投资5个项目，求利润最个项目，求利润最大的方案？大的方案？项目项目 投资额投资额项目收益项目收益约束条件约束条件210160 中选中选1项项300210 之中选之中选1项项15060选选必必先选先选1308026018055 解：解：0 当项目未被选中当项目未被选中 1 当项目被选中当项目被选中 max Z=160 x1+210 x2+60 x3+80 x4+180 x5 210 x1+300 x2+150 x3+130 x4+260 x5 600 X1+x2+x3=1 X3+x4=1 x5 x1 Xj=0或或1 j=1，2,5建模：设建模：设xj=
