4整数规划与指派问题

第4章整数规划整数规划的难度远大于一般线性规划hw24.1整数规划简介•要求所有xj的解为整数，称为纯整数规划•要求部分xj的解为整数，称为混合整数规划•对应没有整数解要求的线性规划称之为松弛问题•整数规划的解是可数个的，最优解不一定发生在极点•整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,,2,1,0,,2,1,),(..)(max(min)11且为整数hw3应用举例：背包问题◆目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大。◆例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。数据物品项目食品氧气冰镐绳索帐篷照相器材通信设备重量(千克)55261224重要系数201518148410hw4背包问题的数学模型◆解：设则问题可写为◆可通过计算每一物品的重要性系数和重量的比值来解决。最优解：只有帐篷落选，总重量24公斤。12345671234567max2015181484105526122425..011,2,,7iZxxxxxxxxxxxxxxstxi≤取或，7,,2,1,102542126255..104814181520max76543217654321ixxxxxxxxtsxxxxxxxzi或取ii0,1,表示不携带物品表示携带物品ixhw5应用举例：布点问题◆共同目标：满足公共要求，布点最少，节约投资费用。●学校、医院、商业区、消防队等公共设施的布点问题。◆例：某市6个区，希望设置最少消防站以便节省费用。条件：●必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。◆请确定设站方案。地点一区二区三区四区五区六区一区0二区100三区16240四区2832120五区271727150六区20102125140hw6布点问题的数学模型：根据消防车15分钟赶到现场的限制，可得到如下模型12345612126343454562min111..11Zxxxxxxxxxxxxxstxxxxxxx≥≥≥≥≥561011,,6ixxxi≥取或，12345612126343454562min111..11Zxxxxxxxxxxxxxstxxxxxxx≥≥≥≥≥561011,,6ixxxi≥取或，地区不设站表示地区设站表示ii0,1,ix解：设最优解：二、四两区设点hw76.2分枝定界法思路与解题步骤•只解松弛问题1、在全部可行性域上解松弛问题–若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程–若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分–构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程–设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况hw8分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5hw9分枝定界法步骤（目标函数极大化）：1°令活点集合Ω:={O}下界U:=－∞当前最好整数解:=φ(“O”代表原问题，下面的整数“k”代表子问题）2°若Ω=φ，则转7°否则，选择一个分支点k∈Ω，并从Ω中去掉点k3°解点k对应的松弛LPk问题，若此问题无解，则转2°4°若LPk的最优值zk≤U，则点k被剪枝，转回2°5°若LPk的最优解x(k)满足整数要求（此时一定有zkU）则当前最好整数解:=x(k)下界U:=zk转回2°6°若LPk的最优解x(k)不满足整数要求，则按的某个非整数分量生成点k的两个后代点，加到Ω中，转回2°7°若当前最好整数解=φ，U=－∞则原问题ILP无解，否则当前最好整数解就是原问题ILP的最优解，U就是最优值，计算停止。hw10分枝定界法举例例且为整数0,72134246)(max21212121xxxxxxxxxf解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23由x1=2.5得到两个分枝如下：且为整数问题0,2721342I46)(max211212121xxxxxxxxxxf且为整数问题0,3721342II46)(max211212121xxxxxxxxxxfhw11hw12分枝问题的松弛解问题I问题IIx123x29/41f(x)2122问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝既广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题hw13且为整数0,5.1645.143223)(max21212121xxxxxxxxxfhw14L0z=31/2(7/2,5/2)L1z=44/3(3,17/6)L2z=13(4,1/2)L11z=13(3,2)L12z=57/4(11/4,3)L121z=13(2,7/2)L122不可行31x41x22x32x21x31x可行（树叶）剪枝剪枝树叶hw156.5分配问题与匈牙利法例有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表，问如何分配任务使完成四项任务的总工时耗费最少？1,0,,2,11,,2,11)(min1111ijmiijmjijmimjijijxmjxmixxaxf任务工时ABCD人员人员甲109781乙58771丙54651丁23451任务1111hw16任务分配问题的数学模型模型中：xij为第i个工人分配去做第j项任务；aij为第i个工人为完成第j项任务时的工时消耗；{aij}mm称为效率矩阵mjijijixij,,2,1,01项任务个工人去做第不分配第项任务个工人去做第分配第•运输问题是任务分配问题的松弛问题•任务分配问题不但是整数规划，而且是01规划•任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的•任务分配是两部图的匹配问题，有著名的匈牙利算法hw17匈牙利法定理1如果从效率矩阵{aij}mm中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj，所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。证明：略定理2若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略匈牙利法的基本思路：•根据定理1变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在m个不同行不同列的零，就找到了最优解•若变换后的效率矩阵中覆盖零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零hw18匈牙利法的步骤：第一步：变换效率矩阵，使每行每列至少有一个零–行变换：找出每行最小元素，从该行各元素中减去之–列变换：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加()标记，并将其所在列划一条直线。若该行没有未标记零或有二个以上未标记的零，则转下一行检查，直到所有行检查完；hw19匈牙利法的步骤：2、逐列检查，若该列只有一个未标记的零，对其加()标记，并将其所在行划一条直线。若该列没有一个未标记的零或有二个以上未标记的零，则转下一列检查，直到所有列检查完；2210020112300023查检行逐（）22100201123)0(0023查检列逐（）（）hw203、重复1、2后，可能出现三种情况：a.每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij=1，其余的xij=0；b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用1、2中的方法继续标记;c.所有的零元素被直线划去，但(0)个数小于m.第三步：1、对情形b，打破僵局。在未标记的零之间的闭回路上,对零进行间隔标记(),并将其所在行或列划一条直线，直至所有零都被划去，或出现情况a，或情况c；匈牙利法的步骤（续）：hw21匈牙利法的步骤（续）：2、对情形c，进一步变换在未划线的元素中找最小者，设为对未被直线覆盖的各元素减去对两条直线交叉点覆盖的元素加上只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用定理111000202012000241第四步：抹除所有标记，回到第二步，重新标记。221002)0(1123)0(0)0(23hw22解优最匈牙利法的步骤（续）：答：最优分配方案为x13=x21=x34=x42=1，其余为0，即甲C，乙A，丙D，丁B，OBJ=20记标列局僵破打11000202012000241100020201200024（）1100020201200024（）（）（）（）1100020201200024（）记标隔间hw23解优最1100020201200024（）（）（）（）或201,11,141322413objxxxx例29131541116141381441579102行411425911005324100115780hw245911005324100115780列0500541100032450115280（）（）（）2（）321100054230113080（）（）（）（）最优解为:114432231xxxx其余为028objhw25打破僵局中，间隔标记零的例子4343963653275624853163754→3200830000050203710030101（）（）（）（）（）Obj=5+1+2+3+4=15，有多组解。hw26→3200830000050203710030101（）（）（）（）（）或Obj=3+1+2+6+3=15。4343963653275624853163754hw27关于匈牙利法的适用条件•要求所有aij0–若某些aij0，则利用定理1进行变换，使所有bij0•目标函数为min