《第六章-整数线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章-整数线性规划ppt课件.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目运 筹 学(Operations Research)认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目Chapter6 整数线性规划整数线性规划 6.1 整数线性规划问题的提出整数线性规划问题的提出6.2 分支定界解法分支定界解法6.3 割平面解法割平面解法6.4 0-1型整数线性规划型整数线性规划6.5 指派问题指派问题本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page 3认识到了贫困户贫困的根
2、本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.1 整数线性规划问题的提出Page 4认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.1.1.1.整数规划（整数规划（整数规划（整数规划（interger programminginterger programming,简称简称简称简称IPIP）要求部分或全部决策变量取整数值的规划问题称为整数规划。要求部分或全部决策变量取整数值的规划问题称为整数规划。变量限制为整数的线性规划则称为整数线性规划（interger linea
3、r programming，简称ILP）。6.1 整数线性规划问题的提出整数线性规划问题的提出2.2.整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：（1 1）纯整数线性规划（）纯整数线性规划（pure interger linear programming）：）：全部决策变量都必须取整数值的整数线性规划。全部决策变量都必须取整数值的整数线性规划。（2 2）混合整数线性规划）混合整数线性规划(mixed interger linear programming)：决策变量中仅有部分取整数值的整数线性规划。决策变量中仅有部分取整数值的整数线性规划。（
4、3 3）0-10-1型整数线性规划型整数线性规划(0-1 interger linear programming)：决策变量只能取值决策变量只能取值0 0或或1 1的整数线性规划。的整数线性规划。Page 5认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目一般地，整数线性 规划问题的数学模型为 （）3.1.1整数规划与线性规划在形式上相差不多,但是由于整数规划的解是离散的正整数,实质上它属于非线性规划.若去掉整数规划的整数约束为整数,则该规划就变成了一个线性规划,一般称这个线性规划为该整数规划的松弛问题.Page 6认识到了
5、贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.1 某某厂厂拟拟用用集集装装箱箱托托运运甲甲乙乙两两种种货货物物，每每箱箱的的体体积积、重重量量、可可获获利利润润以以及及托托运运所所受受限限制制如如表表所所示示。问问两两种种货货物物各各托托运多少箱，可使获得利润为最大运多少箱，可使获得利润为最大?6.1 整数线性规划问题的提出整数线性规划问题的提出货物货物体积（体积（m3/箱）箱）重量（重量（100kg/箱）箱）利润（百元利润（百元/箱）箱）甲甲5220乙乙4510托运限制托运限制24m31300kgPage 7认识到了贫困
6、户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：解：该问题和该问题和LP问题的区别仅在于最后一个约束条件问题的区别仅在于最后一个约束条件(5)(5)。现在先解由现在先解由(1)(1)(4)(4)构成的线性规划问题构成的线性规划问题(称这样的问题称这样的问题为与原问题相应的线性规划问题为与原问题相应的线性规划问题)。6.1 整数线性规划问题的提出整数线性规划问题的提出x1甲货物的托运箱数；甲货物的托运箱数；x2乙货物的托运箱数；乙货物的托运箱数；这就是一个这就是一个(纯纯)整数线性规划问题，数学模型为：整数线性规划问题，数学模型为：P
7、age 8认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目易求得相应的线性规划问题的最优解为易求得相应的线性规划问题的最优解为6.1 整数线性规划问题的提出整数线性规划问题的提出目前得到的最优解不是整数，所以不合条件目前得到的最优解不是整数，所以不合条件的要求。的要求。是是不不是是可可以以把把所所得得的的非非整整数数最最优优解解经经过过“化化整整”就就可可得得到到合合于条件于条件的整数最优解呢的整数最优解呢?不满足条件不满足条件，因而它不是可行解因而它不是可行解Page 9认识到了贫困户贫困的根本原因，才能开始对症下药，然后
8、药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.1 整数线性规划问题的提出整数线性规划问题的提出这当然满足各约束条件，因而是可行解，但不是最优解。这当然满足各约束条件，因而是可行解，但不是最优解。Page 10认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 图图中中画画(+)(+)号号的的点点表表示示可可行行的的整整数数解解。凑凑整整得得到到的的(5，0)点点不不在在可可行行域域内内，而而C C点点又又不不合合于于条条件件。为为了了满满足足题题中中要要求求，表表示示目目标标函函数数的的z的的等等值值线
9、线必必须须向向原原点平行移动，点平行移动，直直到到第第一一次次遇遇到到带带“+”+”号号B点点(x1=4，x2=1)为为止止。这这样样z的的等等值值线线就就由由z=96变变到到z=90，差差值值为为z=96-90=6，表表示示利利润润的的降降低，这是由于变量的不可分性低，这是由于变量的不可分性(装箱装箱)所引起的。所引起的。6.1 整数线性规划问题的提出整数线性规划问题的提出Page 11认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.2 设整数规划问题：设整数规划问题：解：首先不考虑整数约束，得到线性规划问题（一般
10、称为松解：首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。弛问题）。6.1 整数线性规划问题的提出整数线性规划问题的提出用图解法求出最优解为用图解法求出最优解为：Page 12认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目现求整数解现求整数解(最优解最优解):):如用如用舍入取整法可得到舍入取整法可得到4 4个点即个点即(1，3),(2，3),(1，4),(2，4)。显显然都不可能是整数规划的最然都不可能是整数规划的最优解优解。x1x233(3/2,10/3)按整数规划约束条件，其按整数规划约束条件，其可行解肯定
11、在线性规划问题的可可行解肯定在线性规划问题的可行域内且为整数点行域内且为整数点。故整数规划。故整数规划问题的可行解集是一个有限集，问题的可行解集是一个有限集，如右图。其中如右图。其中(2,2),(3,1)(2,2),(3,1)点的点的目标函数值最大，即为目标函数值最大，即为z=4。6.1 整数线性规划问题的提出整数线性规划问题的提出Page 13认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目整数规划整数规划IP与线性规划与线性规划LP解的性质解的性质:如果如果LP的最优值在其可行域的最优值在其可行域T的某个顶点上达到的某个
12、顶点上达到,则相应则相应的的IP最优值最优值,在在T中去掉不含整数点的区域后的中去掉不含整数点的区域后的T*中的整数中的整数点上达到点上达到.对于求最大化对于求最大化(最小化最小化)问题问题,LP最优解对应的目标函数值最优解对应的目标函数值,是相应的是相应的IP最优解对应的目标函数值的上界最优解对应的目标函数值的上界(下界下界).Page 14认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.穷举法：穷举法：可以设想可以设想,整数规划的可行解集一定是具有确定整数规划的可行解集一定是具有确定数目的点阵数目的点阵,然后搜索这些
13、点然后搜索这些点,比较目标函数值的大小比较目标函数值的大小,从而从而求得最优解求得最优解.如例如例6.22.隐枚举法（隐枚举法（Implicit EnumerationImplicit Enumeration）：只检查变量取值：只检查变量取值的组合的一部分的方法。的组合的一部分的方法。Page 15认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.2 分支定界解法Page 16认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目整数线性规划问题的求解方法整数
14、线性规划问题的求解方法：1.分支定界法分支定界法（branch and bound method）可用于解纯整数或混合整数规划问题。可用于解纯整数或混合整数规划问题。2.割平面法割平面法 可用于解纯整数或混合整数规划问题。可用于解纯整数或混合整数规划问题。3.隐枚举法隐枚举法求解求解“0-1”整数规划：整数规划：过滤隐枚举法；过滤隐枚举法；分枝隐枚举法。分枝隐枚举法。4.匈牙利法匈牙利法解决指派问题（解决指派问题（“0-1”规划特殊情形）规划特殊情形）。目前所流行的求解整数规划的方法，往往只适用于整数线性目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一
15、切整数规划。规划。目前还没有一种方法能有效地求解一切整数规划。6.2 分支定界解法分支定界解法Page 17认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.2 分支定界解法分支定界解法6.2.1 6.2.1 分支定界法的思想：分支定界法的思想：分支定界法的思想：分支定界法的思想：考虑最大化整数规划问题考虑最大化整数规划问题A，与它相应的线性规划记为问题，与它相应的线性规划记为问题B。从解问题从解问题B开始，若其最优解不符合开始，若其最优解不符合A的整数条件，那么的整数条件，那么B的最优目标函数必是的最优目标函数必是A的最
16、优目标函数值的最优目标函数值z*的上界的上界，记，记作作 ；而；而A的任意可行解的目标函数值将是的任意可行解的目标函数值将是z*的一个下界的一个下界 。分分支支定定界界法法就就是是将将B的的可可行行域域分分成成子子区区域域(称称为为分分支支)的的方方法法，逐步减小逐步减小 和增大和增大 ，最终求到，最终求到z*。Page 18认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例 求解求解（A）（B）6.2103.580Bx2x1Z=0Z*Z0=356B 的最优解：的最优解：X1=4.81X2=1.82Z0=356Page 2
17、0认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（1）求整数规划）求整数规划IP的相应的的相应的LP的最优解；的最优解；若若LP无可行解，则无可行解，则IP也没有可行解；也没有可行解；若若LP有最优解且满足整数要求，则即为有最优解且满足整数要求，则即为IP的最优解的最优解;若若LP有最优解但不满足整数要求，则转下一步；有最优解但不满足整数要求，则转下一步；（2）进行迭代：）进行迭代：分支与定界：分支与定界：在在LP的最优解中任选一个非整数解的变量的最优解中任选一个非整数解的变量 xi=b,在在LP问题中加上约束：问题中加上
18、约束：6.2.2 6.2.2 分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：6.2 分支定界解法分支定界解法组成两个新的组成两个新的LP问题，称为分枝。问题，称为分枝。Page 21认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目求各分支解和目标值，求各分支解和目标值，定界定界：原问题是求最大值时，各分支最优目标值中最大的为新上界；原问题是求最大值时，各分支最优目标值中最大的为新上界；符合整数条件的分支中目标值最大的为新下界，若无整数分支，符合整数条件的分支中目标值最大的为新下界，若
19、无整数分支，若若z0，可令，可令z=0（求（求min问题，与之相反）。问题，与之相反）。比较与剪枝：比较与剪枝：检查所有分枝的解及目标函数值，检查所有分枝的解及目标函数值，若上界等于若上界等于下界，则停止；否则剪去小于下界的分支，对于大于下界的分下界，则停止；否则剪去小于下界的分支，对于大于下界的分支继续重复（支继续重复（2），直到找到最优解（目标值优的先分支），直到找到最优解（目标值优的先分支）。6.2 分支定界解法分支定界解法Page 22认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目序号序号分支问题分支问题1 1分支
20、问题分支问题2 2说明说明1无可行解无可行解无可行解无可行解原问题无可行解原问题无可行解2无可行解无可行解整数解整数解此整数解为最优解此整数解为最优解3无可行解无可行解非整数解非整数解对问题对问题2 2继续分支继续分支4整数解整数解整数解整数解较优的为最优解较优的为最优解5整数解，优整数解，优于问题于问题2 2非整数解非整数解问题问题1 1为最优解为最优解6整数解整数解非整数解，非整数解，优于问题优于问题1 1问题问题1 1停止分支，继续停止分支，继续对问题对问题2 2分支分支7非整数解非整数解非整数解非整数解继续分支继续分支,较优的先分较优的先分一些原则一些原则Page 23认识到了贫困户贫
21、困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.3 求解整数规划问题求解整数规划问题6.2 分支定界解法分支定界解法解：解相应的线性规划解：解相应的线性规划B，得最优解得最优解而而x1 1=0，x2 2=0是问题是问题A的一个整数可行解，这时的一个整数可行解，这时z=0是是z*的的一一个下界，记作个下界，记作可见它不符合整数条件可见它不符合整数条件。这时这时z0是问题是问题A的最优目标函数值的最优目标函数值z*的上界，记作的上界，记作Page 24认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度
22、重视，已经展开了“精准扶贫”项目6.2 分支定界解法分支定界解法Page 25认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目分分支支：问问题题B的的解解中中有有一一个个非非整整数数变变量量x1 1=4.81。则则在在原原问问题题中中增加分别两个约束条件：增加分别两个约束条件：x1 14和和x1 15，将将B分解为分解为B1和和B2。x1 146.2 分支定界解法分支定界解法(1)分支与定界分支与定界 x1 15Page 26认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开
23、了“精准扶贫”项目仍然不考虑整数条件约束，解问题仍然不考虑整数条件约束，解问题B1和和B2，得到最优解为：，得到最优解为：定界：定界：显然没得到全部整数解。显然没得到全部整数解。问题问题B1问题问题B2x1=4x1=5x2=2.1x2=1.57z1=349z2=3416.2 分支定界解法分支定界解法那么必存在最优整数解，且那么必存在最优整数解，且 Page 27认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目分分支支：因因z1z2，故故先先分分解解B1为为两两支支。B1增增加加条条件件x22称称为问题为问题B3；B1增加条件
24、增加条件x23称为问题称为问题B4。6.2 分支定界解法分支定界解法（2）分支与定界分支与定界Page 28认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目求解问题求解问题B3和和B4，得到，得到定界：定界：显然问题显然问题B3已得到整数解。已得到整数解。z3 3=340=340，故将故将问题问题B3问题问题B4x1=4x1=1.42x2=2x2=3z3=340z4=327而它大于而它大于z4=327=327，所以问题，所以问题B4没有必要分解。没有必要分解。那么必存在最优整数解，且那么必存在最优整数解，且6.2 分支定界解
25、法分支定界解法Page 29认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目分支：分支：继续对问题继续对问题B2进行分支，进行分支，B2增加条件增加条件x21称为问题称为问题B5；B2增加条件增加条件x22称为问题称为问题B6。问题问题B5问题问题B6x1=5.44无可行解无可行解x2=1z5=3086.2 分支定界解法分支定界解法（3 3）分支与定界）分支与定界故最优解为故最优解为x1 1=4=4和和x2 2=2，最优值为最优值为z*=340.Page 30认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年
26、来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 解题过程 6.2 分支定界解法分支定界解法Page 31认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.4 用分枝定界法求解用分枝定界法求解:解解:先求对应的先求对应的LP问题问题用图解法得到最优解：用图解法得到最优解：6.2 分支定界解法分支定界解法Page 32认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1010B的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC
27、6.2 分支定界解法分支定界解法Page 33认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目10 x2oABCB1B234B1:X=(3,7.6),z1=34.8B2:X=(4,6.5),z2=35.56.2 分支定界解法分支定界解法Page 34认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目10 x1x2oABCB1B2134B21:X=(4.33,6),z3=35.3366.2 分支定界解法分支定界解法Page 35认识到了贫困户贫困的根本原因，才
28、能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目10 x1x2oACB1346B211:X=(4,6),z5=34B212:X=(5,5),z6=355B66.2 分支定界解法分支定界解法Page 36认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 上述分枝过程可用下图表示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：B:X=(3.57,7.14),Z0=35.7B1:X=(3,7.6)Z1=34.8B2:X=(4,6.5)Z2=35.5x13x14B
29、21:X=(4.33,6)Z3=35.33x26B211:X=(4,6)Z5=34B212:X=(5,5)Z6=35x14x15B22无可行解无可行解x276.2 分支定界解法分支定界解法Page 37认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.2 分支定界解法分支定界解法例例6.4 用分枝定界法求解整数线性规划问题：用分枝定界法求解整数线性规划问题：解解 step1 确定与问题确定与问题A对应的松弛线性规划问题对应的松弛线性规划问题BPage 38认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来
30、国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 step2 先求出先求出问题问题B B的最优解为的最优解为:6.2 分支定界解法分支定界解法可见它不符合整数条件可见它不符合整数条件。这时这时z0是问题是问题A的最优目标函数值的最优目标函数值z*的上界，记作的上界，记作而而x1 1=0，x2 2=0是问题是问题A的一个整数可行解，这时的一个整数可行解，这时z=0是是z*的的一一个下界，记作个下界，记作Page 39认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 6.2 分支定界解法分支定界解法(1)分支与定界分支与定界问
31、问题题B的的解解中中有有一一个个非非整整数数变变量量x2 2=2 6/17。于于是是在在原原问问题题中中增增加加两两个个约约束束条条件件：x2 22和和x2 23，将将原原问问题题分分解解为为B1和和B2(即两支即两支)。B1的最优解的最优解B2的最优解的最优解Page 40认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 6.2 分支定界解法分支定界解法(2)分支与定界分支与定界问问题题B1的的解解中中有有一一个个非非整整数数变变量量x1 1=4.2。于于是是在在原原问问题题中中增增加加两两个个约束条件：约束条件：x1 1
32、4和和x1 15，将原问题分解为，将原问题分解为B11和和B12(即两支即两支)。B11的最优解的最优解B12的最优解的最优解Page 41认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目(3)分支与定界分支与定界理理论论上上对对B12继继续续分分支支，即即使使再再分分支支，最最优优目目标标函函数数值值也也不会超过不会超过14.14.6.2 分支定界解法分支定界解法所以最优解所以最优解Page 42认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.5 指
33、派问题Page 43认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目指派问题指派问题例 指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 44认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目整数规划的特点及应用整数规划的特点及应用设 数学模型如
34、下：要求每人做一项工作，约束条件为：Page 45认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人，约束条件为：变量约束：一个可行解Page 46认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.5.1 6.5.1 指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：设设n个人被分配去做个人被分配去做n件工作，件工作，规定每个人只做一件工作，规定每个人只做一件工作，每件工作只有一个人去做
35、每件工作只有一个人去做。已知第。已知第i个人去做第个人去做第j件工作的效率件工作的效率（或时间、费用）为（或时间、费用）为Cij(i=1，2n;j=1.2n)并假设并假设Cij 0。问应如何分配才能使总效率（或时间、费用最小）最高？问应如何分配才能使总效率（或时间、费用最小）最高？设决策变量设决策变量 6.5 指派问题指派问题Page 47认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目指派问题的数学模型为：指派问题的数学模型为：6.5 指派问题指派问题cij效率矩阵/系数矩阵解矩阵标准的指派问题是一类特殊的整数规划问题，又
36、是特殊的0-1规划问题和特殊的运输问题。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1955年W.W.Kuhn利用匈牙利数学家D.Konig关于矩阵中独立零元素的定理,提出了解指派问题的一种算法,习惯上称之为匈牙利解法。匈牙利解法匈牙利解法 匈牙利解法的关键是指派问题最优解的以下性质：若从指若从指派问题的系数矩阵派问题的系数矩阵C=（cij）的某行（或某列）各元素分别减）的某行（或某列）各元素分别减去一个常数去一个常数k，得到一个新的矩阵，得到一个新的矩阵C=（cij)，则以，则以C和和C为系为系数矩阵的两个指派问题有相
37、同的最优解。数矩阵的两个指派问题有相同的最优解。（这种变化不影响约束方程组，而只是使目标函数值减少了常数k，所以，最优解并不改变。）对于指派问题，由于系数矩阵均非负，故若能在在系数矩阵中找到n个位于不同行和不同列的零元素（独立的0元素），则对应的指派方案总费用为零，从而一定是最优的。作变换，其不变性是最优解Page 49认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目指派问题与匈牙利法指派问题与匈牙利法克尼格定理克尼格定理克尼格定理克尼格定理 :如果从分配问题效率矩阵如果从分配问题效率矩阵cij的每一行元素中分别减去的每一行
38、元素中分别减去(或加上或加上)一个常数一个常数ui，从每一列中分别减去，从每一列中分别减去(或加上或加上)一个常数一个常数vj，得到一个新的效率矩阵，得到一个新的效率矩阵bij，则以，则以bij为效率矩阵的分配为效率矩阵的分配问题与以问题与以cij为效率矩阵的分配问题具有相同的最优解。为效率矩阵的分配问题具有相同的最优解。Page 50认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.5.2 6.5.2 指派问题的求解步骤：指派问题的求解步骤：1.1.变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)，使
39、使在在(bij)的的各各行行各各列列中中都出现都出现0 0元素，即元素，即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2.2.进行试指派，以寻求最优解。进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素为素为1，其余为其余为0，这就得到最优解。，这就得到最优解。6.5 指派问题指派问题Page 51认识
40、到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目找独立找独立0 0元素，常用的步骤为：元素，常用的步骤为：从从只有一个只有一个0元素的行元素的行开始，给该行中的开始，给该行中的0元素加圈元素加圈，记作，记作。然后。然后划去划去 所在列的其它所在列的其它0元素元素，记作，记作；这表示该列；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。后一行。从从只有一个只有一个0元素的列元素的列开始（开始（画画的不计的不计在内），给该列中在内），给该列中的的0元素加圈，记
41、作元素加圈，记作；然后；然后划去划去 所在行的所在行的0元素元素，记作，记作，表示此人已有任务，不再为其指派其他任务了。依次进行表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。到最后一列。6.5 指派问题指派问题Page 52认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目若仍有没有划圈的若仍有没有划圈的0 0元素，且元素，且同行同行(列列)的的0 0元素至少有两个元素至少有两个，比较比较这行各这行各0 0元素所在列中元素所在列中0 0元素的数目元素的数目，选择，选择0 0元素少元素少这个这个0 0元素元素加圈
42、加圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后。然后划掉划掉同行同列同行同列的其它的其它0 0元素元素。可反复进行，。可反复进行，直到所有直到所有0 0元素元素都已圈出和划掉为止都已圈出和划掉为止。若若元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么，那么这指派问题的这指派问题的最优解最优解已得到。若已得到。若m n,则转入下一步。则转入下一步。6.5 指派问题指派问题Page 53认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.14 6.14 已知四人分
43、别完成四项工作所需时间如下表，已知四人分别完成四项工作所需时间如下表，求最优分配方案。求最优分配方案。任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁781196.5 指派问题指派问题Page 54认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：解：1 1）变换系数矩阵，增加）变换系数矩阵，增加0 0元素元素.2 2）试指派（找独立）试指派（找独立0 0元素）元素）.独立独立0 0元素的个数为元素的个数为m=4,m=n=4.最优指派方案即为甲负责最优指派方案即为甲负责D工作，工作，乙负责乙
44、负责B工作，丙负责工作，丙负责A工作，丁工作，丁负责负责C工作。总的工作时间最少工作。总的工作时间最少为为4491128。6.5 指派问题指派问题Page 55认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.3.用最少的直线通过所有用最少的直线通过所有0 0元素。其方法：元素。其方法：对对没有没有的行的行打打“”；对已打对已打“”的行中所有含的行中所有含元素的列元素的列打打“”；再对打有再对打有“”的列中含的列中含 元素的行元素的行打打“”；重复重复、直到直到得不出新的打得不出新的打号号的行、列为止；的行、列为止；对对没
45、有打没有打号的行号的行画横线，有画横线，有打打号的列号的列画纵线，这就得到覆盖画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数 l。注注：l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2 2步，另行试指派；步，另行试指派；若若 lmn，表表示示还还不不能能确确定定最最优优指指派派方方案案，须须再再变变换换当当前前的系数矩阵，以找到的系数矩阵，以找到n个独立的个独立的0 0元素，为此转第元素，为此转第4 4步。步。6.5 指派问题指派问题Page 56认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视
46、，已经展开了“精准扶贫”项目定理定理6.3 6.3 设矩阵设矩阵C C中含有中含有0 0元素，那么划去元素，那么划去C C中所有中所有0 0元素所需元素所需的最少直线数等于的最少直线数等于C C中独立中独立0 0元素的个数。元素的个数。例例 下列矩阵中，最少下列矩阵中，最少3 3条直线覆盖了所有条直线覆盖了所有0 0元素，因此可判定元素，因此可判定矩阵有矩阵有3 3个独立个独立0 0元素。元素。Page 57认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.4.变换矩阵变换矩阵(bij)以增加以增加0 0元素元素在在没有被
47、直线通过的所有元素中找出最小值没有被直线通过的所有元素中找出最小值，没有被直线通，没有被直线通过的所有元素过的所有元素减去减去这个最小元素；这个最小元素；直线交点处直线交点处的元素的元素加上加上这这个最小值。新系数矩阵的最优解和原问题仍相同。转回第个最小值。新系数矩阵的最优解和原问题仍相同。转回第2 2步。步。6.5 指派问题指派问题Page 58认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例6.15 6.15 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别
48、记作A、B、C、D。现有甲、乙、丙、丁四人，。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？所示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁59826.5 指派问题指派问题Page 59认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：解：1 1）变换系数矩阵，增加）变换系数矩阵，增加0 0元素元素.52 2）试指派（找独立）试指派（找独立0 0元素）
49、元素）.找到找到 3 个独立零元素个独立零元素 但但 m=3 n=46.5 指派问题指派问题Page 60认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3 3）作最少的直线覆盖所有）作最少的直线覆盖所有0 0元素元素.独立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个
50、最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派6.5 指派问题指派问题Page 61认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目000 0 00试指派试指派得到得到4 4个独立零元素，个独立零元素，所以最优解矩阵为：所以最优解矩阵为：即完成即完成4 4个任务的总时间最少个任务的总时间最少为为：241+8=156.5 指派问题指派问题Page 62认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例