整数线性规划-课件

第第5章章整数整数线性性规划划第第1节节 整数线性规划问题的提出整数线性规划问题的提出第第2节节 分支定界解法分支定界解法第第3节节 割平面解法割平面解法第第4节节 0-1型整数线性规划型整数线性规划第第5节节 指指 派派 问问 题题第第1节整数整数线性性规划划问题的提出的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming)，简称ILP，整数线性规划是最近几十年来发展起来的规划论中的一个分支。整数线性规划中如果所有的变数都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)；如果仅一部分变数限制为整数，则称为混合整数计划(mixed integer linear programming)。整数线性规划的一种特殊情形是0-1规划，它的变数取值仅限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。现举例说明用前述单纯形法求得的解不能保证是整数最优解。例1某厂拟用集装 箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱，可使获得利润为最大?表5-1现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为：max z=20 x1+10 x2 5x1+4x224 2x1+5x213 (5.1)x1，x20 x1，x2整数 它和线性规划问题的区别仅在于最后的条件。现在我们暂不考虑这一条件，即解(以后我们称这样的问题为与原问题相应的线性规划问题)，很容易求得最优解为:x1=4.8，x2=0，max z=96但x1是托运甲种货物的箱数，现在它不是整数，所以不合条件的要求。是不是可以把所得的非整数的最优解经过“化整”就可得到合于条件的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件(关于体积的限制)，因而它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80.非整数的最优解在C(4.8，0)点达到。但当x1=4，x2=1(这也是可行解)时，z=90。图中画(+)号的点表示可行的整数解。凑整的(5，0)点不在可行域内，而C点又不合于条件。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值z=96-90=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。由上例看出，将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。第第2节分支定界解法分支定界解法在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就像在图5-1中画出所有“+”号的点那样，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。在例1中，变量只有x1和x2由条件，x1所能取的整数值为0、1、2、3、4共5个；由条件，x2所能取的整数值为0、1、2共3个，它的组合(不都是可行的)数是35=15个，穷举法还是勉强可用的。对于大型的问题，可行的整数组合数是很大的。例如在本章第5节的指派问题(这也是整数线性规划)中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过21018，如果一一计算，就是用每秒百万次的计算机，也要几万年的功夫，很明显，解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分支定界解法(branch and bound method)就是其中的一个.分支定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由Land Doig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。设有最大化的整数线性规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作；而A的任意可行解的目标函数值将是z*的一个下界。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小和增大，最终求到z*。现用下例来说明：例 2求解A max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 (5.2)x1，x20 x1，x2整数 解解 先不考虑条件，即解相应的线性规划B,(见图5-2)，得最优解x1=4.81，x2=1.82，z0=356 可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作z0=。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作 =0，即0z*356分支定界法的解法首先注意其中一个非整数变量的解，如x1，在问题B的解中x1=4.81。于是对原问题增加两个约束条件x14，x15可将原问题分解为两个子问题B1和B2(即两支)，给每支增加一个约束条件，如图5-3所示。这并不影响问题A的可行域，不考虑整数条件解问题B1和B2，称此为第一次迭代。得到最优解为：图5-3 x14，x15显然没有得到全部变量是整数的解。因z1z2，故将 改为349，那么必存在最优整数解，得到z*，并且0z*349继续对问题B1和B2进行分解因z1z2，故先分解B1为两支。增加条件x22者，称为问题B3；增加条件x23者称为问题B4。在图5-3中再舍去x22与x33之间的可行域，再进行第二次迭代。解题的过程都列在图5-4中。图5-4从以上解题过程可得到，用分支定界法求解整数线性规划(最大化)问题的步骤为：将要求解的整数线性规划问题称为问题A，将与它相应的线性规划问题称为问题B。(1)解问题B，可能得到以下情况之一。B没有可行解，这时A也没有可行解，则停止。B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。B有最优解，但不符合问题A的整数条件，记它的目标函数值为进行迭代第一步：分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件xjbj和xjbj+1将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，第二步：比较与剪支各分支的最优目标函数中若有小于 者，则剪掉这支(用打表示)，即以后不再考虑了。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，n。用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。(2)用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，n，试探，求得其目标函数值，并记作 。以z*表示问题A的最优目标函数值；这时有第第3节割平面解法割平面解法整数线性规划问题的可行域是整数点集（或称格点集），割平面解法的思路是：首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线性规划问题，若得到非整数的最优解，然后增加能割去非整数解的线性约束条件(或称为割平面)使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。这个方法是R.E.Gomory提出来的，所以又称为Gomory的割平面法。以下只讨论纯整数线性规划的情形，现举例说明。例例3 3 求解目标函数 max z=x1+x2 约束条件：-x1+x21 3x1+x24 (5-3)x1，x20 x1，x2 整数 如不考虑条件，容易求得相应的线性规划的最优解：x1=34，x2=74，max z=104它就是图5-5中域R的极点A，但不合于整数条件。现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R的一个极点，如在域R上求解，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键就是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。下面仍就本例说明：在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束：-x1+x2+x3 =1 3x1+x2 +x4=4 不考虑条件，用单纯形表解题，见表5-2。表5-2从表5-2的最终计算表中，得到非整数的最优解：x1=3/4，x2=7/4，x3=x4=0，max z=5/2不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。就可以得到整数的最优解。可从最终计算表中得到非整数变量对应的关系式：为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 然后将整数部分与分数部分分开，移到等式左右两边，得到：现考虑整数条件要求x1、x2都是非负整数，于是由条件、可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在等式右边的()内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所代替；即-3x3-x4-3 这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。引入松弛变量x5，得到等式-3x3-x4+x5=-3将这新的约束方程加到表5-2的最终计算表，得表5-3。表5-3从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算选择x5为换出变量，计算将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。注意：新得到的约束条件-3x3-x4-3 如用x1、x2表示，由、式得3(1+x1-x2)+(4-3x1-x2)3x21这就是(x1，x2)平面内形成新的可行域，即包括平行于x1轴的直线x2=1和这直线下的可行区域，整数点也在其中，没有切割掉。直观地表示在图5-7中。但从解题过程来看，这一步是不必要的。图5-7现把求一个切割方程的步骤归纳为：(1)令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到其中iQ(Q指构成基变量号码的集合)K kK(K指构成非基变量号码的集合)(2)将bi和ik都分解成整数部分N与非负真分数f之和，即bi=Ni+fi，其中0fi1ik=Nik+fik，其中0fik1 (5-5)而N表示不超过b的最大整数。例如：若b=2.35，则N=2，f=0.35若b=-0.45，则N=-1,f=0.55代入(5-4)式得(3)现在提出变量(包括松弛变量，参阅例3的注)为整数的条件(当然还有非负的条件).这时，上式由左边看必须是整数，但由右边看，因为0fi1，所以不能为正，即这就是一个切割方程。由(5-4)式，(5-6)式，(5-7)式可知：切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。-43-43-42-42-40例：用割平面法求解整数规划问题例：用割平面法求解整数规划问题解：增加松弛变量解：增加松弛变量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 ,带入带入x1x233第一个割平面第一个割平面得到等价的割平面条件：得到等价的割平面条件：x2 1,见下图。见下图。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,这这也也是原问题的最优解。是原问题的最优解。有有以以上上解解题题过过程程可可见见，表表中中含含有有分分数数元元素素且且算算法法过过程程中中始始终终保保持持对对偶偶可可行行性性，因因此此，这这个个算算法法也也称称为为分分数数对对偶割平面算法。偶割平面算法。第第4节0-1型整数型整数线性性规划划0-1型整数线性规划是整数线性规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0-1变量，或称二进制变量.xi仅取值0或1这个条件可由下述约束条件所代替。xi1,xi0，整数它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题，再研究解法。注：如果变量xi不是仅取值0或1，而是可取其他范围的非负整数，这时可利用二进制的记数法将它用若干个0-1变量来代替。例如，在给定的问题中，变量x可任取0与10之间的任意整数时，令x=20 x0+21x1+22x2+23x3.这时，x就可用4个0-1变量x0，x1，x2，x3来代替。4.1 引入0-1变量的实际问题1.投资场所的选定相互排斥的计划例例4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai(i=1，2，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?解题时先引入0-1变量xi (=1,2，7)于是问题可列成：例题例题 某单位有某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；之间必须选择一项且仅需选择一项；B和和D之间需选择也仅需选择一项；又由于之间需选择也仅需选择一项；又由于C和和D两项目密切相关，两项目密切相关，C的实施必须的实施必须以以D的实施为前提条件，该单位共筹集资金的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，万元，问应该选择哪些项目投资，使期望收益最大？使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E5962解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3 x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：632.相互排斥的约束条件在本章开始的例1中，关于运货的体积限制为5x1+4x224 (5-9)今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x245 (5-10)这两条件是互相排斥的。为了统一在一个问中，引入0-1变量y，令于是(5-9)式和(5-10)式可由下述的条件(5-11)式和(5-12)式来代替：5x1+4x224+yM (5-11)7x1+3x245+(1-y)M (5-12)其中M是充分大的数。读者可以验证，当y=0时，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而是多余的。当y=1时(5-12)式就是(5-10)式，而(5-11)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。如果有m个互相排斥的约束条件(型)：i1x1+i2x2+inxnbi，i=1，2，,m为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,，m)和一个充分大的常数M，而下面这一组m+1个约束条件i1x+i2x2+inxnbi+yiM，i=1,2,，m (5-13)y1+y2+ym=m-1 (5-14)就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取0值，设yi*=0，代入(5-13)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。例题例题3 （固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件（固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。定一个生产计划，使总收益最大。产品产品 单件耗量单件耗量资源资源123资源量资源量A248500B234300C123100单件可变费用单件可变费用456固定费用固定费用100150200单件售价单件售价81012解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助应的固定费用是否发生。下面借助0-1变量解决这个困难变量解决这个困难67设设xj是第是第j种产品的产量，种产品的产量，j=1,2,3,再设再设则问题的整数规划模型为：则问题的整数规划模型为：M为很大的正为很大的正数数68 01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。例一、求解下列01 规划问题 解：对于01 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，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第第5章章整数整数线性性规划划第第5节指指 派派 问 题在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。例7 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少?表5-7类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij0(i,j=1,2，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令 当问题要求极小化时数学模型是：显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最优。约束条件说明第j项任务只能由1人去完成；约束条件说明第i人只能完成1项任务。满足约束条件的可行解xij也可写成表格或矩阵形式，称为解矩阵。如例7的一个可行解矩 指派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1当然可用整数线性规划，0-1规划或运输问题的解法去求解，这就如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。指派问题的最优解有这样性质，若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到zb=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。以下用例子来说明指派问题的解法。第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。(1)从系数矩阵的每行元素减去该行的最小元素；(2)再从所得系数矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。行列都有零元素2.特点 （1）给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij0，因此必有最优解()。（2）指派问题是一种特殊的平衡运输问题，由于模型结构的特殊性（看作每个产地的产量均为1，每个销地的销量均为1），故可用更为简便的匈牙利算法进行求解。（3）若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。这条性质可用如下语言来解释这条性质可用如下语言来解释82对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数dj），也不影响其最优指派。将效率矩阵C=(Cij)nn变换后，得到新的效率矩阵(bij)nxn，其中 bij=Cij+ti+dj （对所有的i,j）83解题步骤：第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：任务人员ABCD甲215134乙1041415丙9141613丁78119有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982 对于求最大化的指派问题（即求 ）,可采用构造新的效率矩阵(MCij)nxn，其中M=maxCij，（显然MCij0），将其转化为 则所得到的最优解就是原问题的最优解。事实上 由于nM为常数，因此，使Z取得最小的最优解就是使Z取得最大的最优解。87以上讨论的指派问题是效率矩阵的行数等于列数，即m+n的情况。当mn时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。n-m行当mn时四、非平衡的指派问题四、非平衡的指派问题88