运筹学-北京邮电大学4

第四章整数规划整数规划的难度远大于一般线性规划©管理与人文学院忻展红1999，424.1整数规划简介•要求所有xj的解为整数，称为纯整数规划•要求部分xj的解为整数，称为混合整数规划•对应没有整数解要求的线性规划称之为松弛问题•整数规划的解是可数个的，最优解不一定发生在极点•整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,,2,1,0,,2,1,),(..)(max(min)11且为整数34.2整数规划的分枝定解法4.2.1思路与解题步骤•只解松弛问题1、在全部可行性域上解松弛问题–若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程–若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分–构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程–设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况4表4.2.1分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的整数解进行比较，结论如情况454.2.2分枝定界法举例例4.1.1且为整数0,72134246)(max21212121xxxxxxxxxf解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23由x1=2.5得到两个分枝如下：且为整数问题0,2721342I46)(max211212121xxxxxxxxxxf且为整数问题0,3721342II46)(max211212121xxxxxxxxxxf6表4.2.3分枝问题的松弛解问题I问题IIx123x29/41f(x)2122问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当有很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题74.6任务分配问题例4.6.1有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？1,0,,2,11,,2,11)(min1111ijmiijmjijmimjijijxmjxmixxaxf任务工时ABCD人员人员甲109781乙58771丙54651丁23451任务11118任务分配问题的数学模型模型中：xij为第i个工人分配去做第j项任务；aij为第i个工人为完成第j项任务时的工时消耗；{aij}mm称为效率矩阵mjijijixij,,2,1,01项任务个工人未分配去做第当第项任务个工人分配去做第当第运输问题是任务分配问题的松弛问题任务分配问题不但是整数规划，而且是01规划任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的任务分配是两部图的匹配问题，有著名的匈牙利算法下面介绍一种适合手算的算法(出自清华教科书)94.6.1清华算法定理1如果从效率矩阵{aij}mm中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj，所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。证明：略定理2若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略清华算法的基本思路：•根据定理1变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在m个不同行不同列的零，就找到了最优解•若覆盖变换后的效率矩阵零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零10清华算法的步骤：例4.6.1第一步：变换效率矩阵，使每行每列至少有一个零–行变换：找出每行最小元素，从该行各元素中减去之–列变换：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；11清华算法的步骤：例4.6.12、逐列检查，若该列只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查检列逐查检行逐3、重复1、2后，可能出现三种情况；a.每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij=1；b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用1.2中的方法继续标记。4、打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记()；采用这种方法直至所有零都被标记，或出现情况a，或情况c。12清华算法的步骤：例4.6.1c.所有零都已标记，但标有()的零的个数少于m；开始划线过程：对没有标记()的行打对打行上所有其它零元素对应的列打再对打列上有()标记的零元素对应的行打重复，直至无法继续对没有打的行划横线，对所有打的列划垂线221*0*02)0(1123)0(*0)0(23划线后会出现两种情况：(1)标记()的零少于m个，但划有m条直线，说明矩阵中已存在m个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到b重新标记；(2)少于m条直线，到第三步；13清华算法的步骤：例4.6.1第三步：进一步变换；在未划线的元素中找最小者，设为对未被直线覆盖的各元素减去对两条直线交叉点覆盖的元素加上只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用定理1221*0*02)0(1123)0(*0)0(2311000202012000241第四步：抹除所有标记，回到第二步，重新标记；14解优最列逐行逐记标11)0(*0)0(2*02*012)0(*0)0(24清华算法的步骤：例4.6.111000202012000241答：最优分配方案为x13=x21=x34=x42=1，其余为0，即甲C，乙A，丙D，丁B，OBJ=20110002020120*0)0(24记标列110*00202*012)0(*0)0(24局僵破打221*0*02)0(1123)0(*0)0(23156020504003010200局僵破打4.6.2关于清华算法的适用条件•要求所有aij0–若某些aij0，则利用定理1进行变换，使所有bij0•目标函数为min型–对于max型目标函数，将效率矩阵中所有aij反号，则等效于求min型问题；再利用定理1进行变换，使所有bij0，则可采用清华算法打破僵局时选择不当的结果：结果仅出现3个标记()，但却划出4条线，说明什么？！602*0504*00301*02*0)0(局僵破打6*02*05)0(4*00301*02*0)0(局僵破打6*02*05)0(4*0*03)0(1*02*0)0(局僵破打16线性规划有关的英文词汇•Operational/operationsresearch运筹学•Linearprogramming线性规划Feasibledomain可行域•Convexset凸集Basicfeasiblesolutions基础可行解•Simplexalgorithm单纯型法Pivot主元Pivoting主元变换•Revised,dualsimplexalgorithm修正、对偶单纯型法•Relativecost相对成本(机会成本)Shadowprice影子价格•Slack,Surplus,Artificialvariable松弛，剩余，人工变量•Unbounded,Infeasible,Degeneratesolution无界解,无可行解,退化解•Duality对偶性Primal,dualproblem原问题，对偶问题•Complementaryslackness互补松弛Sensitivityanalysis灵敏度分析•Ttransportationproblem运输问题•Assignmentproblem任务分配(指派)问题•Bipartitematching两部图匹配Hungarianmethod匈牙利算法