第4章 整数规划.ppt

第四章 整数规划,整数规划问题的提出,依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、0－1整数规划整数规划模型与一般的线性规划模型的区别仅在于：整数规划的变量要求部分的或全部的为整数例如：,,纯整数规划：如果所有决策变量都要求取整数，则称为“纯整数规划”,混合整数规划：如果仅有一部分的决策变量要求取整数，则称为“混合型整数规划”还有一种特殊情况， 0－1整数规划：所有决策变量仅限于取 0 或 1 两个整数，这种规划问题称为“0-1规划”,整数规划模型应用举例,排班问题（人力资源配置问题）,例：邮局每天需要的职工数因业务忙闲而异，据统计邮局一周内每天需要的人数如下表排班要符合每周连续工作5天，休息2天的规定问如何排班可使用人最少纯整数规划问题),解：设xi为第i天开始上班的人数：Min：z=x1+x2+x3+x4+x5+x6+x7s.t. x1 +x4+x5+x6+x7≥17 x1+x2 +x5+x6+x7≥13 x1+x2+x3 +x6+x7≥15 x1+x2+x3+x4+ +x7≥19 x1+x2+x3+x4+x5 ≥14 x2+x3+x4+x5+x6 ≥16 x3+x4+x5+x6+x7≥11 xi≥0 （ i=1,2,…,7）X=(1.3, 3.3, 2, 7.3, 0, 3.3, 5)T , z=22.3,X*=( 7, 5, 1, 8, 0, 2, 0)T , z=23,固定费用问题：见教材p69,(混合整数规划问题),0-1规划问题,投资问题,5个投资项目；600万元资金，投资受到约束：(1) 项目1、2和3至少一项被选中；(2) 项目3和4只能选一项；(3) 项目5选中的前提是1必须被选中。

问如何投资才能使收益最大？,投资问题的数学模型：0－1规划,设01变量为决策变量，即xi=1表示项目i被选中，xi=0表示项目i被淘汰，则模型可表示为,,背包问题,目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大 例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表假定允许携带的最大重量为25千克，试确定一最优方案背包问题的数学模型： 0－1规划,解：设01变量表示携带物品i，表示不携带物品i，则问题可写为可通过计算每一物品的重要性系数和重量的比值ci/ai来解决布点问题,共同目标：满足公共要求，布点最少，节约投资费用学校、医院、商业区、消防队等公共设施的布点问题例：某市6个区，希望设置最少消防站以便节省费用条件：必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场各区之间消防车行驶的时间见右表请确定设站方案布点问题的数学模型： 0－1规划,设01为决策变量，当表示i地区设站，表示i地区不设站这样根据消防车15分钟赶到现场的限制，可得到如下模型,,指派问题（分配问题）(Assignment Problem)假定有n项任务分配给n个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总效率为最高。

游泳运动员的选拔,例：甲乙丙丁是4名游泳运动员，他们各种姿势的100m游泳成绩见下表为组成一个4×100m混合泳接力队，怎样选派运动员，方能使接力队的游泳成绩最好？,解： 设i=1，2，3，4分别表示甲、乙、丙、丁；j=1，2，3，4分别表示仰泳、蛙泳、蝶泳、自由泳并设 xij= 0，表示 i 不参加 j 1，表示 i 参加 j据题意，此题的数学模型为：,,分配问题的数学模型：设xij=1分配第i人去完成第j 项任务， xij=0不分配第i人去完成第j 项任务 Min Z=  cijxij  xij =1 (j=1,2……n)  xij =1 (i=1,2……n) xij = 0或1 (i=1,2…..n; j=1,2……n),整数规划问题的求解方法,求解思路：既然整数规划是线性规划的一种特殊形式，求解只需性规划的基础上，通过舍入取整求解即可但实际上，两者却有很大的不同，通过舍入得到的整数解也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解举例说明例：设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。

用图解法求出最优解x1＝3/2, x2 = 10/3且有Z = 29/6,,,,,,,,,,,,x1,x2,,⑴,⑵,,3,3,(3/2,10/3),,,,,,,,,,,,,,,,,,,,,现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)显然，它们都不可能是整数规划的最优解按整数规划约束条件，其可行解肯定性规划问题的可行域内且为整数点 ，如图所示2,1,2,1,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法如此例中（2，2）（3，1）点为最大值，Z=4目前，常用的求解整数规划的方法有： 分枝定界法、割平面法； 隐枚举法、匈牙利法求解整数规划的分枝定界法,思路：分枝和定界两部分：分枝：切割可行域，去掉非整数点一次分枝变成两个可行域，分别求最优解；（由于非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化）定界：松弛问题最优解——上界；IP问题的任意可行解——下界，不断减小上界和增加上界，最终的最优解IP问题的最优解不优于LP问题的最优解）,,,,,,,,求解0-1整数规划的隐枚举法,对于0－1 规划问题，由于每个变量只取0，1两个值，可以用穷举法来求解，即将所有的0，1 组合找出，在满足可行要求的基础上使目标函数达到极值，就求得了最优解。

而隐枚举法是在此基础上进行了改进：通过加入过滤条件，减少穷举法的计算量，从而能较快地找到最优解也可以认为隐枚举法的实质就是分枝定界法例1、求解下列0－1 规划问题,完全枚举法:,,隐枚举法:（加入过滤条件，计算目标值看是否满足过滤条件；若满足过滤条件，再判断其是否可行，从而减少了部分计算量过滤条件为任意整数可行解及其目标函数值x1=x2=x3=1, z=5,不可行,z=3, 可行,z= -5, 可行,z=2, 可行,z=10,不可行,,,,x1=0,x3=0,x2=0,z= -3, 可行,,,,z=8, 可行,,z=0, 可行,x2=0,x3=0,x3=0,x3=0,隐枚举法——分枝定界法求解思路,,1、按照一定的规律进行分枝，得到各变量的所有组合,2、定界：以整数可行解及其目标函数值为下界，及时剪掉不必要的分枝为了能合理并及时地剪掉分枝，减少计算量，我们希望各分枝是按目标值由大到小的顺序出现（对于目标求最大的0-1规划），因此可以先将0-1型整数规划变成统一形式（标准形式），具体要求如下：（1）目标函数求极大化 对于目标函数为Min z的极小化问题，令z′=-z，使其变为目标函数为Max z′的极大化问题。

2）目标函数中所有变量的系数都为正数如果目标函数中变量xj的系数为负数，令xj′=1-xj，把模型中的xj用xj′代换3）变量的排列顺序按变量在目标函数中的系数值从小到大排列如：将例1化为标准形式：,x2 =x3′=x1=1, z=10,不可行,z=5, 不可行,z=3, 可行,z=0, 可行,z=2, 可行,,,,x2=0,x1=0,x3′=0,z=8, 可行,,,,z=-3, 可行,,z=-5, 可行,x3′=0,x1=0,x1=0,x1=0,观察标准化后各分枝的目标值大小：,x2 =x3′=x1=1, z=10,不可行,z=5,,z=2,,,,,x2=0,x1=0,x3′=0,z=8, 可行,z=8,,,及时剪枝：,第一层不可行，需要分枝：,标准化后，隐枚举法的计算量进一步减少隐枚举法步骤：,1、标准化后，先令所有变量都为1，计算目标值，并检验其是否可行若可行，则已经是0-1规划的最优解；若不可行，则需要分枝（分枝方法如前例图中所示） 2、分别计算各分枝的目标值，并检验其是否可行若可行，则得到一个下界，以它为过滤条件，及时剪去未满足下界的分枝对于目标值大于下界，且不可行的分枝，还需要继续分枝。

3、最后，不必要的枝被及时剪去，剩下的唯一的枝即为0-1规划的最优解例2 用隐枚举法求解下列0-1型整数规划问题 Max z=8x1+2x2-4x3-7x4-5x5 3x1+3x2+x3+2x4+3x5≤4 5x1+3x2-2x3-x4+ x5≤4 xj=0或1，j=1,2,…,5,,令 x3′=1-x3, x4′=1-x4, x5′=1-x5，得 Max z=2x2+4x3′+5x5′+7x4′+8x1-16 3x2- x3′- 3x5′- 2x4′+3x1≤-2 ① 3x2+2x3′- x5′+ x4′+5x1≤6 ② x2, x3′,x5′,x4′,x1 =0或1,,x2 =x3′=x5′= x4′=x1=1, z=10,不可行,z=6,不可行,z=5,不可行,z=3,不可行,z=2,不可行,,,,,,x2=0,x1=0,x3′=0,z=8,不可行,x5′=0,x4′=0,x2 =x3′=x5′= x4′=x1=1, z=10,不可行,z=6,不可行,z=5,不可行,z=3,不可行,z=2,不可行,,,,,,x2=0,x1=0,z=4, 可行,,x3′=0,x3′=0,,,z=8,不可行,x5′=0,x4′=0,Z=4,x2 =x3′=x5′= x4′=x1=1, z=10,不可行,z=6,不可行,z=5,不可行,z=3,不可行,z=2,不可行,,,,,,x2=0,x1=0,z=4, 可行,,x3′=0,x3′=0,,,z=8,不可行,,x5′=0,x5′=0,,z=1,z=-2,,x4′=0,x4′=0,,Z=4,x2 =x3′=x5′= x4′=x1=1, z=10,不可行,z=6,不可行,z=5,不可行,z=3,不可行,z=2,不可行,,,,,,x2=0,x1=0,z=4, 可行,,x3′=0,x3′=0,,,z=8,不可行,,x5′=0,x5′=0,,z=1,z=-2,,x4′=0,x4′=0,,最优解为x2=0，x3′=0，x5′=1，x4′=1，x1=1。

于是，原问题的最优解为z*=4，x1*=1，x2*=0，x3*=1-0=1，x4*=1-1=0，x5*=1-1=0,练习1 、求解下列0－1 规划问题,首先将原整数规划变为统一形式：,x2′= x1 = x4′= x5=x3=1, z=11,不可行,z=9,不可行,z=8,不可行,z=7,不可行,z=6,不可行,,,,,,x1=0,x3=0,x2′=0,z=10,不可行,x4′=0,x5=0,x2′= x1 = x4′= x5=x3=1, z=11,不可行,z=9,不可行,z=8,不可行,z=7,不可行,z=6,不可行,,,,,,x1=0,x3=0,z=8, 不可行,,x2′=0,x1=0,z=10,不可行,,x4′=0,x4′=0,。