第七章整数规划模型

第七章整数规划模型第一页，共六十八页，2022年，8月28日第七章整数规划模型整数规划模型在实践中有广泛的应用背景，例如著名的指派模型、背包模型、旅行售货员模型、排序模型以及地理六章中的截料模型等都是整数规划模型。整数规划模型（IntegerProgramming，简记IP）是一类要求变量为整数的规划模型。自从高莫瑞（R.E.Gomory）在1958年提出割平面法以后，整数规划才逐步成为一个独立的理论分支。将目标函数为线性函数，约束条件均为线性等式或不等式的整数规划模型称为整数线性规划模型（ILP），否则称为整数非线性规划模型（INLP）两类。若要求全部变量都去整数值，则称为纯整数规划模型（PureIP）或全整数规划模型（AllIP）；若只要求一部分变量取整数值，则称为混合整数规划模型（MixedIP）；若要求全部或部分变量只取0或1值。则称为0-1规划。由于整数非线性规划尚无一般解法，因此本文仅考虑整数线性规划模型及其解法，下文所提及的整数规划专指整数线性规划。第二页，共六十八页，2022年，8月28日§1整数规划模型及穷举法一、整数规划模型建立整数规划模型的过程也与建立线性规划模型一样，有“设立决策变量”、“明确决策目标函数”和“寻找限制条件”三个过程。例一（投资模型）某工厂有资金13万元，用于购置新机器，可在A、B两种机器中任意选购。已知机器A、B的购置费每台分别为2万元和4万元。该厂维修能力只能修7台机器B；若维修机器A，1台折算B为2台。已知1台机器A可增加产值6万元，1台B可增加产值4万元，问应购置机器A和B各多少台，才能使产值增加最多？解设购买机器A和B的台数分别为台，则模型为：第三页，共六十八页，2022年，8月28日用LINDO软件解的程序为：第四页，共六十八页，2022年，8月28日答案为：最优决策变量目标函数最优值为22。（跳跃式成本模型）设两种产品A和B每公斤价格为10元和7元，每公斤需要的加工工时为6小时和4小时，成本和工时的关系如图7.1所示，要求建立一整数规划模型，是利润最大。解设两种产品的产量分别为公斤，设工时在2000以内为第一范围，2000到3000小时为第二范围，3000到5000小时为第三范围。再设当工时在第j范围内时，（j=1，2，3）。则模型为：第五页，共六十八页，2022年，8月28日图7.1第六页，共六十八页，2022年，8月28日用LINDO软件解的程序为：第七页，共六十八页，2022年，8月28日二、穷举法

穷举法尽管往往不是有效的和常用的方法，但却是最自然想到和直观的方法，而对有些模型却是无可奈何的方法。有时通过对穷举法的研究，往往能够得到启发而产生新的方法。满足整数规划模型所有约束条件的可行解的集合，很多情况下是有限集合，这为穷举法的应用提供了可能。下面用穷举法求一个只有两个变量的整数规划模型的最优解。第八页，共六十八页，2022年，8月28日

例3用穷举法求例1中的整数规划模型的最优解：maxZ=s.t.为整数解图7.2给出了可行解的集合，共有十二个整数点（即对应到可行解），得整数规划的最优解最优值。即A，B两种机器分别购买3台和1台，产值最多增加22万元。第九页，共六十八页，2022年，8月28日11

0223345（2.5，2）图7.2整数规划模型与线性规划模型不同之处只在于增加了整数约束。不考虑整数约束得到的线性规划称为整数规划的线性松弛。第六章讲述了用图解法球线性规划模型的解，能否用它的线性松弛模型的最优解痉过去整或四舍五入第十页，共六十八页，2022年，8月28日得到整数规划模型的最优解呢？在上例中整数规划模型的最优解，线性松弛模型的最优解为，四舍五入得，不是不是可行解，自然也不是最优解；若将取整得，虽然是可行解，但它不是最优解。由此可见，刚刚的设想是行不通的，事实上整数规划模型的求解是难题，至今还没有有效的算法（即多项式算法）。

§割平面法和分支定界法一、割平面法

整数规划模型的割平面法由高莫瑞首创，称为高莫瑞割平面法（GomoryCuttingPlaneAlgorithm），以区别于后来其他割平面法。在整数规划模型中，去掉了第十一页，共六十八页，2022年，8月28日变量为整数的约束条件之后的模型称为原整数规划得像性松弛模型。高莫瑞割平面法的基本思想是在整数规划的线性松弛模型中逐次增加一个新约束（即割平面），它能割去圆松弛可行域中一块不含整数解的区域。逐次切割下去，直到切割最终得到松弛可行域的一个最优顶点即整数解为止。我们用例4结合图形来说明高莫瑞割平面法的思想及过程：例4用割平面法求下面的整数规划模型的最优解：

为整数第十二页，共六十八页，2022年，8月28日解图7.3作出了整数规划的线性松弛模型（记为）的可行解，其最优解为，增加新的约束条件：

得新模型，图7.4给出了的最优解为。第十三页，共六十八页，2022年，8月28日011223345011223345图7.3图7.4第十四页，共六十八页，2022年，8月28日此时，已经满足整数要求，但还不是整数，还需要增加新的约束条件：得新模型（），图7.5给出了的最优解为，已得原整数规划模型的最优解，易计算出最优值为55。第十五页，共六十八页，2022年，8月28日11223345图7.50新增加的约束条件必须满足下列两个条件：（1）不能割去满足条件的整数点（即整数可行解）。新的割平面的加入，使得可行解区域逐渐减小，割去的区域不能有整数可行解。（2）必须将前一次的最优解割去。将原整数规划模型的第十六页，共六十八页，2022年，8月28日最优解逐步暴露在可行解区域的顶点上。

割平面构造原理涉及到对偶单纯形法，在此不多加介绍。割平面法有很重要的理论意义，但在实际计算中没有分支定界效率高，且涉及到对分数的处理，因此几乎没有给予割平面法的软件。

二、分支定界法分支定界法的基本思想是根据某种规则将原整数规划模型的可行域分解为越来越小的子区域，并检查某各子区域内整数解的情况，直到找到最优的整数解或证明整数解不存在。根据整数规划模型性质的不同，存在许多的分支界定法以及分支界定的技巧，在此只对分支界定的一般原理作一简单的介绍。在介绍具体算法之前，以下几个重要的实事是容易理解的：第十七页，共六十八页，2022年，8月28日（1）如果求解一个整数规划的线性松弛模型时得到一个整数解，这个解一定也是整数规划模型的最优解。然而，求解实际模型时这种概率很小。（2）如果得到的解不是一个整数解，则最优整数解的目标值一定不会好于得到的线性松弛模型的最优解。因此线性松弛模型的最优解是整数规划模型最优值的一个界（对最大化模型为上界，对最小化模型为下界）。（3）如果在求解过程中已经找到一个整数解，则最优整数解一定不会劣于该整数解。因此它也是最优整数解的一个界（对最大化模型为下界，对最小化模型为上界）。如果用表示线性松弛模型的最优值，用表示已找到的最好整数解的目标值，为原整数规划第十八页，共六十八页，2022年，8月28日模型的最优值，表示下界，表示上界，则最优值一定满足以下关系：（对最大化模型）(对最小化模型)分支定界法定界法思想就是不断降低上界，提高下界最后使得下界等于上界，就可以搜索到最优整数解。分支定界法从求解线性松弛模型开始，将线性松弛模型的可行分成许多小的子区域，这一过程称为分支；通过分支和找到更好的整数解来不断修改模型的上下界，这一过程称为定界，这就是分支定界法的由来。以下对分支定界法的基本步骤进行简单的讨论（假定模型求极大值）。1.对给定的整数规划模型，放松整数约束，求解它的线性松弛模型的最优解，如果得到解释整数解，该解即为整数规划模型的最优解。否则，所得到的最优值可作为该第十九页，共六十八页，2022年，8月28日模型最优值的初始上界。最初下界一般认为负无穷。2.从任何一个模型或子模型中不满足整数要求的变量中选出一个进行分支处理。分支通过假如一对互斥的约束将一个（子）模型分解为两个受到更多约束的子模型，并强迫不为整数的变量进一步逼近整数值。例如，如果选中的变量=q，q的整数部分为k，则在一个子模型中增加约束为，在另一个子模型中增加的约束为。分支过程砍掉了在和之间的非整数区域，缩小了搜索的区域。每个子模型都是一个线性规划模型，如果它的最优解不满足整数要求，对该模型还必须继续向下进行分支，所有分支可以形成一个树形图。树形图上面为线性松弛模型，它有两个分支，每个分支又会有两个分支，焚之可以继续进行下去，直到找到一个有整数第二十页，共六十八页，2022年，8月28日

最优解的分支或该分支不可行时为止。3.通过不断的分支和求解各个子模型的最最优解，不断修正最优值的上下界。上界通常由各分支最优值的最小值决定，下届则由已经能够找到的最好的整数解的目标值决定。求解任何一个子模型都有以下四种可能的结果：（1）子模型无可行解，此时无续向下继续分支。（2）子模型的最优解满足原整数规划模型变量整数约束，则不必向下继续分支。如果该整数解是目前得到的最好的整数解，则被记录下来，并用它的值作为新的下届。（3）子模型的最优值介于目前所得到的上下界之外，则无需继续向下进行分支。（4）最优解不满足原整数规划模型变量整数约束，最优值介于所得到的上下界之间，则该模型才有第二十一页，共六十八页，2022年，8月28日继续向下搜索的必要。4.直到每一个子模型均无需继续向下分支时，整数规划模型的最优解才找到。下面以例5用分支定界法求整数规划模型最优解的过程。例5用分支定界法求下列整数规划模型：为整数第二十二页，共六十八页，2022年，8月28日解求解该模型的线性松弛模型（记为），得到最优值=5.545，最优解为=1.477，=4.068（该模型可用线性规划的图解法，若多于两个变量，可用LINDO或MATLAB求解）。因为该模型失球最大化模型，整数规划模型的最优值不可能大于，也不可能小于负无穷，所以可令上界=5.545，下届。第二十三页，共六十八页，2022年，8月28日由于两个变量都不是整数，我们可以从中选择一个变量进行分支，假定选，要求变为整数，因此希望或者小于等于1，或者大于等于2。分支后形成两个子模型，子模型1增加约束，子模型2增加约束。（子模型1）第二十四页，共六十八页，2022年，8月28日(子模型2)子模型1的最优值为=5.333，最优解为=1，=4.333。该解还不是整数解，还应继续分支。由于子模型1中只有取值不是整数，应对进行分支。分支后又形成两个子模型3和4。子模型3是由子模型1架上约束形成的，子模型4页是由子模型1加上约束构成的。第二十五页，共六十八页，2022年，8月28日(子模型3)(子模型4)第二十六页，共六十八页，2022年，8月28日子模型3的最优值为=5，最优解为=1，=4，该解已经是整数解。所以子模型3无需向下继续分支，且新的下届可以计算如下：子模型4无可行解，所以子模型4也无需继续向下分支。子模型2的最优值为=4.5，最优解为=2，=2.5。此时最优值已小于下届5，故也无需继续向下分支。整数规划模型的最优解已经找到，=1，=4，最优值为5。为了清晰的描述求解的全过程，我们作出个子模型关系的树形图（图7.6）第二十七页，共六十八页，2022年，8月28日松弛模型子模型1子模型2子模型3子模型4无可行解第二十八页，共六十八页，2022年，8月28日三、两辆铁路平板车的装货问题这是1988年美国数模竞赛的B题，问题如下：有七种规格的包装箱要装到两辆平板车上去。包装箱的宽和高是一样的，但厚度t（以厘米计）及重量w(以千克计）是不同的。下表给出了每种包装箱的厚度，重量以及数量。每辆平板车有10.2米长的地方可用来装包装箱（像面包片一样），载重为40吨。由于地区货运的限制，对类包装箱的总数有一个特别的限制：这三类箱子所占的总空间（厚度）不能超过302.7厘米。包装箱类型t（厘米）48.752.061.372.048.752.064.0w（千克）200030001000500400020001000件数8796648

第二十九页，共六十八页，2022年，8月28日问题要求：设计一种装车方案，使剩余的空间最小。下面介绍一种解法。1.问题的假设。⑴包装箱不能能分割成较小的部分。10.2m图7.7第三十页，共六十八页，2022年，8月28日⑵所有的数据均是精确值，无任何测量误差。⑶给出的解，均可进行实际操作（装卸）。2.模型的建立以表示装到第j（j=1，2）辆铁路平板车上的类包装箱的个数（1≤i≤7）；表示类型为的包装箱的总件数；表示类型为的包装箱每件重量；表示类型为的包装箱每件厚度；S表示剩余的空间。我们的目的是使装车剩下的空间最小。为此我们的模型为

第三十一页，共六十八页，2022年，8月28日s．t．(平板车1的长度限制)(平板车2的长度限制)(平板车1的载重量限制)(平板车2的载重量限制)(类包装箱的件数限制)

（对、、三种型号包装箱长度的特别限制）为整数第三十二页，共六十八页，2022年，8月28日对上述整数线性规划问题，用分支定界法可以求得30个不同的解如下（没有利用的空间为0.6cm）箱子类型1234567123456743533004443030429120045051304253310454302041912104605120415332046430104091220470511040533304743000平板车1平板车2第三十三页，共六十八页，2022年，8月28日箱子类型1234567123456737431005053230370521050911203643110515322036052205191110354312052532103505230529110034431305353200329130055050303191310560502030913205705010平板车1平板车2第三十四页，共六十八页，2022年，8月28日平板车1平板车2箱子类型1234567123456727432006053130264321061531202543220625311025053306291000244323063531001643310715302015433207253010144333073530000790020800631007640008032330069003081063000664010813232005640208232310第三十五页，共六十八页，2022年，8月28日3.模型的分析现在，我们分析求得的解是否是最优解？考虑、、三种类型的箱子，它们有如下特别限制：、、类箱子的件数限制为（），记，，，并把已知的与（）代入，我们有

为整数

第三十六页，共六十八页，2022年，8月28日这个问题的解共有315个，其中使的最小值介于[292.2，302.7]的解有6个，列表如下：330302.1cm420298.8cm023296.0cm510295.5cm113292.7cm600292.2cm第三十七页，共六十八页，2022年，8月28日

可以看出对类型为、、三种类型的包装箱，在所占空间（厚度）不能超过320.7cm的限制下，两辆平板车只能装运302.1cm宽度的包装箱。此时类型和类型的包装箱各装3只，不装类型的包装箱。由

两辆平板车装运、、、四种类型的包装箱的空间厚度为1737.3cm。从而总的装运空间的厚度最多为302.1+1737.3=2039.4（cm）因此，装运的剩余空间至少为2040-2039.4=0.6（cm）因此，我们求得的30个解均为最优解。如果我们进一步要求这两辆车装运包装箱后，使得剩余空间相同，此时的解即为如下两个解：第三十八页，共六十八页，2022年，8月28日

注意到，最优解不装运类箱子。现在，如果我们进一步要求每一种类型的包装箱都必须装运一部分，从表中可以看出此时两辆平板车装运的~类型包装箱的只数分别为8、7、9、6、1、1、3。此时装完两辆平板车后，剩余的空间至少为2024-（292.7+1737.3）=10（cm）。平板车厚度重量第一辆10119.7340000790020第二辆10119.7330008006310第一辆10119.7330000690030第二辆10119.7340008106300第三十九页，共六十八页，2022年，8月28日

我们现在的目标函数是使平板车上没有利用的空间最少，当然也可以把目标函数定义为两辆平板车装运的包装箱的总重量最大，此时得到的解也将不同。§30-1规划及隐枚举法

只取0或1值的变量称为0-1变量。在实际生活中许多情况下的状态仅有两种，比如“开、关”，“上、下”，“投资该项目与不投资该项目”等等，通常要用到这种形式的变量来表示。将含有0-1变量的线性规划称为0-1规划。首先建立两个0-1规划模型。例6（装箱模型）某运输公司打算用一个在重30吨重的货物集装箱装运一批货物。这些货物的有关数据由下表给出。试问硬装哪几件货物，才能使获利最多？第四十页，共六十八页，2022年，8月28日

解当集装箱不装第i件货物时，令=0，否则令=1（i=1、2、3、4、5）。于是该模型为：货物编号12345重量（吨）20181654利润（百元）303520105s.t.

=0或1（j=1、2、3、4、5）第四十一页，共六十八页，2022年，8月28日

例7(投资模型)某公司拟在市东、西、南三区建立市部。拟议中7个位置（i=1~7）可供选择：在东区，由，，三个点中至多选两个；在西区，由，两个点中之少选一个；在南区，由，两个点中之少选一个；如果选用点，设备投资估计为元，每年可获利润为元，但投资总额不能超过B元。问应该选哪几个点可使年利润为最大？解当选点时，令，否则令（i=1~7）。则模型为：

第四十二页，共六十八页，2022年，8月28日

0-1规划是整数规划的特殊情况，可用前面介绍的方法求解，但有其变量取值的特性，它另有一种特殊的分值定界法——隐枚举法，它也是通过求解线性松弛模型来获得原整数规划模型的最优解的，不过这里恰好跟一般分值定界相反，是由放弃所有线性约束、只保留变量0-1约束而得到的。下面具体说明这种方法。隐枚举法要求0-1规划为下述标准形式：或第四十三页，共六十八页，2022年，8月28日其中，，约束条件必须为“”。当某一时，令，则

再令，原目标函数变为

从而使目标函数中个变量的系数变为非负数。或第四十四页，共六十八页，2022年，8月28日

隐枚举的解法思路与分值定界法有相似之处。利用变量只能取0或1进行分支。首先令全部变量取0值（当求最大值时，令全部变量取1值），检验解是否满足约束条件。若均满足，已得最优解；若不全满足，则令一个变量取值为0或1（此变量称为固定变量），将模型分成两个子模型，其余未被指定取值的变量称为自由变量。由于，因此自由变量为0与固定变量组成的子模型的解使目标值最小。经过几次检验后，或停止分支，或者将另一个自由变量转为固定变量，令其值为0或1，继续分支。如此继续进行，直至没有自由变量或全部子模型停止分支为止，就求出最优解。具体算法过程：第一步，将模型化为标准形式。第二步，令全部都是自由变量，且均取0值，第四十五页，共六十八页，2022年，8月28日检验解是否为可行解（即满足所有约束条件）。若是可行解，则一定为最优解；若不可行，进行第三步。第三步，将某一变量转为固定变量，令其取值为0或1，使该模型（子模型）分成两个子模型。其它变量均为自由变量，仍取0值。第四步，检查已有的子模型，若子模型满足下列条件之一，该子模型停止向下分支，继续检查其它子模型，直到所有子模型均检查完毕，转第五步；若有某一个子模型不满足下列四个条件，则转第三步。1.将自由变量均取0值与固定变量的值一起代入约束方程中，满足所有约束条件，则为可行解，该模型停止向下分支。

第四十六页，共六十八页，2022年，8月28日2.若自由变量取任意值时，都不满足某一约束条件，则该子模型无可行解，也停止向下分支。即将子模型固定变量的值代入约束条件方程中，令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，得到左端所能取得的最小值，若此最小值大于右端值，说明此子模型无可行解。3.将自由变量均取0值与固定变量的值一起代入目标函数，得到的目标值大于已求得的可行解的目标值，则该子模型一定无更好的可行解，也停止向下分支。4.所有变量均为固定变量，则该子模型停止向下分支。第五步，在所有可行解中目标值最小的解，即为最优解。第四十七页，共六十八页，2022年，8月28日例8求下列0-1规划最优解解将原模型记为，目标值，自由变量全取0值，显然不是可行解。不妨取作为固定变量，在中增加约束条件记为，增加记为。模型中，其它为自由变量，均取0值，此时为可行解，停止分支。目标或第四十八页，共六十八页，2022年，8月28日

值，因此，原模型的最优值的上界为8。模型不满足算法中停止的条件，需继续分支。将变为固定变量，于是模型分为两个分支和，继续考虑和。为了清晰的表达求解的过程，我们类似分值定界法，作出树形图（图7.8），图中黑体数字表示该变量为固定变量。

最优解为，最优值为。第四十九页，共六十八页，2022年，8月28日可行解，停止分支不可行，停止分支图7.8第五十页，共六十八页，2022年，8月28日可行解，停止分支不可行，停止分支目标值大于上界6，停止分支图7.8第五十一页，共六十八页，2022年，8月28日§4指派模型及匈牙利法一、指派模型

许多管理部门可能经常面临这样的问题：有若干项任务需要完成，又有若干对象能够完成其中的每项任务。由于每个对象的特点与能力不同，完成各项任务的效益也各不相同。又因任务性质的要求和管理上的要求等，应如何分配人员去完成所有任务，能使完成各项任务的总效益最佳或费用最小？这类问题就称之为指派问题或分配问题。在指派问题中，作如下假设：1.被指派的人数与任务的数目相等，为n。2.每个被指派的人员只完成一个任务，而且每一个任务必有一个人去完成。第五十二页，共六十八页，2022年，8月28日

3.第i个被指派的人去完成第j项任务的费用为。指派问题的模型为C=（）为n阶方阵，称为指派模型（P）的效益矩阵；若为（P）的最优解，则n阶方阵称为（P）的最优解方阵。事实上方阵X为一置换方阵，即该矩阵中的每一行、每一列只有一个“1”。第五十三页，共六十八页，2022年，8月28日

二、匈牙利法

解决指派模型的方法是匈牙利数学家考尼格提出的。因此得名匈牙利法。1.匈牙利法基本原理。匈牙利法基于下面两个基本性质：性质1设一个指派模型的效益矩阵为（）。若（）的第i行元素减去一个常数（i=1，2，…，n），第j列元素均减去一个常数（j=1，2，…，n），得到一个新的效益矩阵（），其中每一元素，则以（）为效益矩阵的最优解也是以（）为效益矩阵的指派模型的最优解。如果取（i=1，2，…，n）为第i行元素的最小值，（j=1，2，…，n）为第j列元素的最小值，则第五十四页，共六十八页，2022年，8月28日得到一个新的效益矩阵（）为非负矩阵（即所有元素均为非负数）。性质1说明可以通过求以（）为效益矩阵的指派模型的最优解得到原指派模型的最优解。直观地讲，求指派模型的最优解方阵就是在效益矩阵中找到n个元素，要求在不同行、不同列上，使这些元素之和最小。江、将这n个元素所在位置赋值为“1”，其它元素均为“0”，就得到最优解方阵。效益矩阵（）中最小元素为“0”，因此邱指派模型（P）的最优解又转化为在矩阵（）中找出n个在不同行、不同列上的“0”元素，就很容易的、构造出最优解矩阵。性质2若一方阵中的一部分元素为0，一部分元素为非0，则覆盖方阵内所有0元素的最少直线恰好等于那些位于不同行、不同列上的0元素的最多个数。第五十五页，共六十八页，2022年，8月28日此时存在两个问题：第一，当效益矩阵阶数n较大时，如何得知不存在n个位于不同行、不同列上的0元素，即如何得知覆盖方阵内所有0元素的最少直线数需要几条？第二，赋予实际背景的指派模型，总存在最优解。事实上任意一个指派模型均有最优解。当确切得知不存在n个位于不同行、不同列上的0元素时，如何进一步按性质1构造出新的效益矩阵，其中位于不同行、不同列上的0元素不断增加，直至达到几个？要解决第一个问题，我们需要引入两个定义和一些性质：定义1矩阵的积和式perA定义为：

第五十六页，共六十八页，2022年，8月28日其中（）取遍（1、2、…、n）的所有排列。积和式是矩阵的一个重要参数，在组合理论中经常将积和式与其他参数建立联系，它类似于矩阵的行列式，但又有很大的区别。行列式的计算方法有许多，但积和式的计算主要用拉普拉斯展开法，按某行（列）展开，直至到2阶。例如计算下列3阶矩阵的积和式时，按第一行展开，则转化为计算三个2阶矩阵的积和式。第五十七页，共六十八页，2022年，8月28日定义2称D为C的补矩阵。若，满足

性质3设C为指派模型（P）的效益矩阵，D为C的补矩阵，覆盖C中0元素所需要最小直线数为n的充要条件为。由性质3得知，当指派模型（P）的效益矩阵或由性质1所得效益矩阵对应的补矩阵D的积和式时，覆盖效益矩阵内0元素的最小直线数需要n条。因此性质3也可以称为效益矩阵迭代的终止条件。特别要指出的是当迭代终止时，，且性质4指派模型（P）最优解的个数等于perD。第五十八页，共六十八页，2022年，8月28日对于第二个问题，我们可以按如下的方法处理。当确切得知效益矩阵中不存在n个位于不同行、不同列上的0元素时，一定可以用少于n条直线将所有“0”元素覆盖。在未被直线覆盖的所有元素中，找出最小元素，记为△；所有未被直线覆盖的元素都减去△；覆盖线十字交叉处元素即同时被两条直线覆盖的元素都加上△，其余元素不变。这一过程相当于将效益矩阵的每一行的所有元素均减去△，同时将被直线覆盖的行（或列）上的所有元素均加上△。由性质1保证最优解矩阵不发生改变，同时在新的效益矩阵中位于不同行、不同列上的0元素个数得到增加。2.匈牙利方法步骤第一步，从下效