运筹学08-整数规划.ppt

第八章 整数规划8.1 8.1 整数规划问题及其数学模型整数规划问题及其数学模型8.2 8.2 分支定界法分支定界法8.3 8.3 割平面法割平面法8.4 0-18.4 0-1整数规划整数规划8.5 8.5 指派问题指派问题一、整数规划问题的特征一、整数规划问题的特征 变量取值范围是离散的，经典连续数学中的理论和方法变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。一般无法直接用来求解整数规划问题。例例 某公司计划在某公司计划在m个地点建厂，可供选择的地点有个地点建厂，可供选择的地点有A1,A2Am，他们的生产能力分别是，他们的生产能力分别是a1,a2,am（假设生（假设生产同一产品）。第产同一产品）。第i个工厂的建设费用为个工厂的建设费用为fi(i=1.2m),又又有有n个地点个地点B1,B2,Bn 需要销售这种产品，其销量分别需要销售这种产品，其销量分别为为b1.b2bn。从工厂运往销地的单位运费为。从工厂运往销地的单位运费为Cij。试决定。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？总运输费用最省？8.1 整数规划问题及其数学模型二、整数规划的数学模型二、整数规划的数学模型纯整数规划纯整数规划：所有决策变量为非负整数；：所有决策变量为非负整数；全整数规划全整数规划：所有变量、系数和常数均为整数；：所有变量、系数和常数均为整数；混合整数规划混合整数规划：只有一部分决策变量为非负整数，其余：只有一部分决策变量为非负整数，其余变量可为非负实数；变量可为非负实数；0-1整数规划整数规划：所有决策变量只能取：所有决策变量只能取0获获1两个整数。两个整数。三、整数规划与线性规划的关系三、整数规划与线性规划的关系n从数学模型上看整数规划似乎是线性规划的一种特殊形从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。有时甚至不能保证所得倒的解是整数可行解。n目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：n分支定界法和割平面法；分支定界法和割平面法；n对于特别的对于特别的01规划问题采用隐枚举法和匈牙利法。规划问题采用隐枚举法和匈牙利法。例例：设整数规划问题如下：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题首先不考虑整数约束，得到线性规划问题（一般称为（一般称为松弛问题松弛问题）。）。用图解法求出最优解用图解法求出最优解x13/2,x2=10/3且有且有z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得可得到到4个点，即个点，即(1，3)(2，3)(1，4)(2，4)。显然，。显然，它们都不可能是整数规划它们都不可能是整数规划的最优解。的最优解。按整数规划约束条件，其按整数规划约束条件，其可行解肯定在线性规划问可行解肯定在线性规划问题的可行域内且为整数点。题的可行域内且为整数点。故整数规划问题的可行解故整数规划问题的可行解集是一个有限集，如图所集是一个有限集，如图所示。示。因此，可将集合内的整数点一一因此，可将集合内的整数点一一找出，其最大目标函数的值为最找出，其最大目标函数的值为最优解，此法为优解，此法为完全枚举法完全枚举法。8.2 分支定界法 基本思路基本思路 1、先不考虑整数约束，解、先不考虑整数约束，解(IP)的松弛问题的松弛问题(LP)，可能可能得到以下情况之一：得到以下情况之一：.若若(LP)没有可行解，则没有可行解，则(IP)也没有可行解，停止计也没有可行解，停止计算。算。.若若(LP)有最优解，并符合有最优解，并符合(IP)的整数条件，则的整数条件，则(LP)的最优解即为的最优解即为(IP)的最优解，停止计算。的最优解，停止计算。.若若(LP)有最优解，但不符合有最优解，但不符合(IP)的整数条件，转入的整数条件，转入下一步。下一步。为讨论方便，设为讨论方便，设(LP)的的最优解为：最优解为：2、定界：、定界：记记(IP)的目标函数最优值为的目标函数最优值为Z*,以以Z(0)作为作为Z*的的上界，上界，记为记为 Z(0)。再用观察法找的一个整数可行解再用观察法找的一个整数可行解 X，并并以其相应的目标函数值以其相应的目标函数值 Z作为作为Z*的的下界，记为下界，记为Z Z，也可以令也可以令Z，则有：则有：Z Z*3、分枝：、分枝：在在(LP)的最优解的最优解 X(0)中，任选一个不符合整数条件的中，任选一个不符合整数条件的变量，例如变量，例如xr=（不为整数），以不为整数），以 表示不超过表示不超过 的最的最大整数。构造两个约束条件大整数。构造两个约束条件 xr 和和 xr 1如此反复进行，直到得到如此反复进行，直到得到 Z Z*为止，即得最优解为止，即得最优解X*。将这两个约束条件分别加入问题将这两个约束条件分别加入问题(IP)，形成两个子形成两个子问题问题(IP1)和和(IP2)，再解这两个问题的松弛问题再解这两个问题的松弛问题(LP1)和和(LP2)。4、修改上、下界：按照以下两点规则进行。、修改上、下界：按照以下两点规则进行。.在各分枝问题中，找出目标函数值最大者作为新的上在各分枝问题中，找出目标函数值最大者作为新的上界；界；.从已符合整数条件的分枝中，找出目标函数值最大者从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。作为新的下界。5、比较与剪枝、比较与剪枝：各分枝的目标函数值中，若有小于各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，者，则剪掉此枝，表明此子问题已经探清，不必再分枝了表明此子问题已经探清，不必再分枝了;否则继续分枝。否则继续分枝。分支定界法是一种隐枚举方法（分支定界法是一种隐枚举方法（implicit enumeration）或或部分枚举方法，它不是一种有效的算法，是枚举方法基部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。其关键是分支和定界。础上的改进。其关键是分支和定界。例例 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0 X1，X2 取整数取整数s.t.分支定界法图解整数规划分支定界法图解整数规划松弛问题松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0该该整数规划松弛问题的解为：整数规划松弛问题的解为：（X1，X2）=（3/2，10/3）Z0=29/6松弛问题松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1，X2 0（3/2，10/3）Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1，X2 0LP2 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 1 X1，X2 0LP2：解解（1，7/3）Z2=10/3LP1：解解（2，23/9）Z1=41/9（3/2，10/3）Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1，X2 0LP2：解解（1，7/3）Z2=10/3LP1：解解（2，23/9）Z1=41/9LP11 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 3 X1，X2 0LP12 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1，X2 0LP12：解解（33/14，2）Z12=61/14（3/2，10/3）Z0=29/6LP2：解解（1，7/3）Z2=10/3LP12 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1，X2 0LP12：解解（33/14，2）Z12=61/14LP121 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 3 X2 2 X1，X2 0LP122 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1，X2 0LP121：解解（3，1）Z121=4LP122：解解（2，2）Z122=4LP1：解解（2，23/9）Z1=41/9LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11 无可无可行解行解LP122（2，2）Z122=4LP121（3，1）Z121=4#LP22（1，2）Z22=3LP21 无可无可行解行解#分支搜索法流程分支搜索法流程LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11 无可无可行解行解LP122（2，2）Z122=4LP121（3，1）Z121=4#分支定界法流程分支定界法流程3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解。获得最优解。初始表初始表最终表最终表例例 用分支定界法求解整数规划问题（单纯形法）用分支定界法求解整数规划问题（单纯形法）x1=13/4 x2=5/2 Z(0)=59/414.75 选选 x2 进行分枝，即增加两个约束，进行分枝，即增加两个约束，2 x2 3 有下式：有下式：分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6，将，将新加约新加约束条件加入上表计算。即束条件加入上表计算。即 x2+x5=2,x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2 Z(1)=14.5继续分枝，继续分枝，加入约束加入约束3 x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3 Z(2)=13.5 Z(2)Z(1)先不考虑先不考虑分枝分枝接接(LP1)继续分枝，加入约束继续分枝，加入约束 4 x1 3，有下式：有下式：分别引入松弛变量分别引入松弛变量x7 和和 x8，然后进行计算。然后进行计算。CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3x1=3,x2=2 Z(3)=13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP3CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1x1=4x2=1 Z(4)=14找到整数找到整数解，问题解，问题已探明，已探明，停止计算。停止计算。LP4树形图如下：树形图如下：LP1x1=7/2,x2=2Z(1)29/2=14.5LPx1=13/4,x2=5/2Z(0)59/4=14.75LP2x1=5/2,x2=3Z(2)27/2=13.5LP3x1=3,x2=2Z(3)13LP4x1=4,x2=1Z(4)14x22x23x13x14#8.3 割平面法二、计算步骤二、计算步骤1、用单纯形法求解、用单纯形法求解(IP)对应的松弛问题对应的松弛问题(LP)：.若若(LP)没有可行解，则没有可行解，则(IP)也没有可行解，停止计也没有可行解，停止计算。算。.若若(LP)有最优解，并符合有最优解，并符合(IP)的整数条件，则的整数条件，则(LP)的最优解即为的最优解即为(IP)的最优解，停止计算。的最优解，停止计算。.若若(LP)有最优解，但不符合有最优解，但不符合(IP)的整数条件，转入的整数条件，转入下一步。下一步。2、从、从(LP)的最优解中，任选一个不为整数的分量的最优解中，任选一个不为整数的分量xr,将最优将最优单纯形表中该行的系数单纯形表中该行的系数 和和 分解为整数部分和小数部分之分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：和，并以该行为源行，按下式作割平面方程：3、将所得的割平面方程作为一个新的约束条件置于最、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回纯形法求出新的最优解，返回1。例例：用割平面法求解整数规划问题：用割平面法求解整数规划问题解解：增加松弛变量：增加松弛变量x3和和x4，得到得到(LP)的初始单纯形表和最优的初始单纯形表和最优单纯形表单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/4此题的最优解为：此题的最优解为：X(1,3/2)Z=3/2 但不是整数最优但不是整数最优解，引入割平面。以解，引入割平面。以x2 为源行生成割平面，由于为源行生成割平面，由于 1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为生成割平面的条件为:也即：也即：将将 x3=6-3x1-2x2,x4=3x1-2x2 ,带入带入 中，中，得到等价的割平面条件：得到等价的割平面条件：x2 1 见下图。见下图。x1x233第一个割平面第一个割平面Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源为源行行生成割平面，其条件为：生成割平面，其条件为：用上表的约束解出用上表的约束解出x4 和和s1，将它们带入上将它们带入上式得到等价的割平面式得到等价的割平面条件：条件：x1 x2，见图：见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X=(1,1),Z=1,这也是这也是原问题的最优解。原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过程中始有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。算法。例例：用割平面法求解数规划问题：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表在松弛问题最优解中，在松弛问题最优解中，x1,x2 均为非整数解，由上表有：均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，考虑式子右以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：现选第二个式子，并将真分数移到右边得：引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表中，后得到下式，将此约束条件加到上表中，继续求解。继续求解。Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/601 x10100101x24010120 x3200113Z400001/2 得得到到整整数数最最优优解解，即即为为整整数数规规划划的的最最优优解解，而而且且此此整整数数规规划有两个最优解：划有两个最优解：X=(0,4),Z=4,或或 X=(2,2),Z=4。8.4 0-1整数规划例例 求解下列求解下列01 规划问题规划问题解解：对于：对于0 01 1 规划问题，由于每个变量只取规划问题，由于每个变量只取0 0，1 1两个值，两个值，一般会用穷举法来解，即将所有的一般会用穷举法来解，即将所有的0 0，1 1 组合找出，使目标组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。就能较快的求得最优解。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值 (1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 00(0.0.1)1 1 0 15(0.1.0)2 4 1 42(1.0.0)1 1 1 03(0.1.1)1 5(1.0.1)0 2 1 18(1.1.0)3(1.1.1)2 6由上表可知，问题的最优解为由上表可知，问题的最优解为 X*=(x1=1 x2=0 x3=1)由上表可知：由上表可知：x1=0 x2=0 x3=1 是一个可行解，为尽快找到是一个可行解，为尽快找到最优解，可将最优解，可将3 x12 x25 x3 5 作为一个约束，凡是目标作为一个约束，凡是目标函数值小于函数值小于5 的组合不必讨论，如下表。的组合不必讨论，如下表。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值 (0)(1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 0 00(0.0.1)5 1 1 0 15(0.1.0)-2(0.1.1)3(1.0.0)3(1.0.1)8 0 2 1 18(1.1.0)1(1.1.1)4以下讨论一般形式的以下讨论一般形式的0 01 1规划如何化为标准形式：规划如何化为标准形式：例例 求解下列求解下列01 规划问题规划问题解解：令：令 y1=x5,y2=x4,y3=x2,y4=x3,y5=x1 得到下式得到下式y1.y2.y3.y4.y5约束条件约束条件满足条件满足条件Z 值值 (1)(2)是是 否否(0.0.0.0.0 )0 0(1.0.0.0.0)1 -1(0.1.0.0.0)-1 1(0.0.1.0.0)-2 1(0.0.0.1.0)4 -48(1.1.0.0.0)0 0(1.0.1.0.0)-1 0所以，所以，Y*=（0.0.0.1.0），），原问题的最优解为：原问题的最优解为：X*（0.0.1.0.0），），Z*=8例例 求解下列求解下列01 规划问题规划问题解解：由于目标函数中变量：由于目标函数中变量x1,x2,x4 的系数均为负数，可作的系数均为负数，可作如下变换：如下变换：令令 x1 1 x1,x2=1-x2,x3=x3,x4=1-x4带入原带入原题中，但需重新调整变量编号。令题中，但需重新调整变量编号。令 x3=x1,x4=x2得得到下式。到下式。可以从可以从(1.1.1.1)开始试算，开始试算，x(3)(1.1.0.1)最优解。最优解。x(3)(1.0.1.0)是原问题的最优解，是原问题的最优解，Z*=-28.5 指派问题二、解题步骤：二、解题步骤：指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求解，规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立系数矩阵中独立 0 0 元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有 0 0 元元素的最少直线数。素的最少直线数。第第一一步步：变变换换指指派派问问题题的的系系数数矩矩阵阵（cij）为为(bij)，使使在在(bij)的各行各列中都出现的各行各列中都出现0元素，即元素，即 (1)从（从（cij）的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素；(2)再再从从所所得得新新系系数数矩矩阵阵的的每每列列元元素素中中减减去去该该列列的的最最小小元素。元素。第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其余为其余为0，这就得到最优解。找独立，这就得到最优解。找独立0元素，常用的步骤为：元素，常用的步骤为：(1)从从只只有有一一个个0元元素素的的行行(列列)开开始始，给给这这个个0元元素素加加圈圈，记记作作。然然后后划划去去 所所在在列列(行行)的的其其它它0元元素素，记记作作；这表示这列所代表的任务已指派完，不必再考虑别人了。这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给给只只有有一一个个0元元素素的的列列(行行)中中的的0元元素素加加圈圈，记记作作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 (3)反反复复进进行行(1)，(2)两两步步，直直到到尽尽可可能能多多的的0元元素素都都被被圈出和划掉为止。圈出和划掉为止。(4)若若仍仍有有没没有有划划圈圈的的0元元素素，且且同同行行(列列)的的0元元素素至至少少有有两两个个，则则从从剩剩有有0元元素素最最少少的的行行(列列)开开始始，比比较较这这行行各各0元元素素所所在在列列中中0元元素素的的数数目目，选选择择0元元素素少少的的那那列列的的这这个个0元元素素加加圈圈(表表示示选选择择性性多多的的要要“礼礼让让”选选择择性性少少的的)。然然后后划划掉掉同同行行同同列列的的其其它它0元元素素。可可反反复复进进行行，直直到到所所有有0元元素素都都已圈出和划掉为止。已圈出和划掉为止。（5）若）若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指派那么这指派问题的最优解已得到。若问题的最优解已得到。若m n,则转入下一步。则转入下一步。第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素。元素。(1)对没有对没有的行打的行打号；号；(2)对已打对已打号的行中所有含号的行中所有含元素的列打元素的列打号；号；(3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号；(4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；(5)对对没没有有打打号号的的行行画画横横线线，有有打打号号的的列列画画纵纵线线，这这就就得得到到覆覆盖盖所所有有0元元素素的的最最少少直直线线数数 l。l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第二二步步(4)，另另行行试试指指派派；若若 lm n，须须再再变变换换当当前前的的系系数数矩矩阵阵，以以找找到到n个个独独立立的的0元元素，为此转第四步。素，为此转第四步。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素。元素。在没有被直线覆盖的所有元素中找出最小元素，然后打在没有被直线覆盖的所有元素中找出最小元素，然后打各各行都减去这最小元素；打行都减去这最小元素；打各列都加上这最小元素（以保证各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。题仍相同。转回第二步。例例 有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二步，试指派：第二步，试指派：找到找到 3 3 个独立零元个独立零元素素 但但 m m=3 3 n=4第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(bij)以增加以增加0元素：没有被直线覆盖的元素：没有被直线覆盖的所有元素中的最小元素为所有元素中的最小元素为1，然后打，然后打各行都减去各行都减去1；打；打各各列都加上列都加上1，得如下矩阵，并转第二步进行试指派：，得如下矩阵，并转第二步进行试指派：000 0 00得到得到4 4个独个独立零元素，立零元素，所以最优解所以最优解矩阵为：矩阵为：Z=15例例115764戊戊69637丁丁86458丙丙9117129乙乙118957甲甲EDCBA费费 工作工作 用用人员人员-1-2 l=m=4 n=5 l=m=4 n=5 此问题有多个最优解此问题有多个最优解Z=28 三、非标准形式的指派问题三、非标准形式的指派问题 在实际应用中，常会遇到各种非标准形式的制派问题。一般的在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。处理方法是先将其转化为标准形式，然后再用匈牙利法求解。1.最大化指派问题最大化指派问题设最大化指派问题系数矩阵设最大化指派问题系数矩阵 C=(cij)，其其中最大元素为中最大元素为 m。令矩阵令矩阵 B=(bij)=(m-cij)，则则以以 B 为系数为系数矩阵的最小化指派问题和以矩阵的最小化指派问题和以 C 为系数矩阵的最大化指派问题有为系数矩阵的最大化指派问题有相同最优解。相同最优解。2.人数和事数不等的指派问题人数和事数不等的指派问题若若人少事多人少事多，则添加一些虚拟，则添加一些虚拟的的“人人”，其费用系数取，其费用系数取 0，若，若人多事少人多事少，则添加一些虚拟的，则添加一些虚拟的“事事”，其费用系数取，其费用系数取 0。3.一个人可做几件事的指派问题一个人可做几件事的指派问题若某个人可以做几件事，则若某个人可以做几件事，则将该人化作几个将该人化作几个“人人”来接受指派。这几个来接受指派。这几个“人人”做同一件事做同一件事的费用系数当然都一样。的费用系数当然都一样。4.某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题若某事一定不能由某人若某事一定不能由某人做，则可将相应的费用系数取为足够大的数做，则可将相应的费用系数取为足够大的数 M。例例 分配甲、乙、丙、丁去完成五项任务，每人完成各项分配甲、乙、丙、丁去完成五项任务，每人完成各项任务的时间如下表。由于任务多，规定其中有一人可兼完任务的时间如下表。由于任务多，规定其中有一人可兼完成两项任务，试确定总花费时间最少的分配方案。成两项任务，试确定总花费时间最少的分配方案。任务任务人人ABCDE甲甲59112217乙乙242311518丙丙14782212丁丁42216325解解：增加一人，其完成各项任务时间为该任务完成的最少：增加一人，其完成各项任务时间为该任务完成的最少时间：时间：任务任务人人ABCDE甲甲59112217乙乙242311518丙丙14782212丁丁42216325戊戊4丁丁7丙丙8丙丙3丁丁12丙丙例例 从甲、乙、丙、丁、戊五人中选四人去完成四项任务，从甲、乙、丙、丁、戊五人中选四人去完成四项任务，每人完成各项任务的时间如下表。规定每人只能完成一每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不项任务。由于某种原因，甲必须被分配一项任务，丁不承担第承担第4项任务，试确定总花费时间最少的分派方案。项任务，试确定总花费时间最少的分派方案。人人任务任务甲甲乙乙丙丙丁丁戊戊1 110231592 251015243 3155147154 420151368解解：增加虚设任务：增加虚设任务5，各人该项任务时间为，各人该项任务时间为0，某人不完成，某人不完成某任务时，取时间某任务时，取时间M（充分大的时间）：充分大的时间）：人人任务任务甲甲乙乙丙丙丁丁戊戊11023159251015243155147154201513685M0000第八章习题第八章习题3(3(选选2)2)、4 4(选选2)、8 8、11(11(电子版电子版)