第5章整数规划课件

第五章

整数规划1第五章

整数规划1§1整数规划的数学模型一、整数规划的数学模型整数规划(IntegerProgramming简记IP)要求一部分或全部决策变量必须取整数的规划问题2.松驰问题(SlackProblem)不考虑整数约束，由余下的目标函数和约束条件构成的规划问题(也称伴随规划)3.整数线性规划(ILP)若松驰问题是一个线性规划问题2§1整数规划的数学模型一、整数规划的数学模型整数规划(In§1整数规划的数学模型一、整数规划的数学模型整数线性规划数学模型的一般形式为：中部分或全部取整数3§1整数规划的数学模型一、整数规划的数学模型整数线性规划数§1整数规划的数学模型一、整数规划的数学模型整数线性规划分为：纯整数LP——PureIntegerLinearProgramming混合整数LP——MixedIntegerLinearProgramming0-1型整数LP——Zero-OneIntegerLinearProgramming4§1整数规划的数学模型一、整数规划的数学模型整数线性规划分§1整数规划的数学模型二、整数规划举例例1：某厂生产A1和A2两种产品，需要经过B1，B2，B3三道工序加工，单件工时和利润以及各工序每周工时限额见下表，问工厂应如何安排生产，才能使总利润最大？B1B2B3利润A10.30.20.325A20.70.10.540工时限制2501001505§1整数规划的数学模型二、整数规划举例例1：某厂生产A1和§1整数规划的数学模型二、整数规划举例解：设工厂每周生产A1产品x1件，A2产品x2件。则该问题的数学模型为：且取整数值6§1整数规划的数学模型二、整数规划举例解：设工厂每周生产A§1整数规划的数学模型二、整数规划举例例2：见书P130例17§1整数规划的数学模型二、整数规划举例例2：见书P130§1整数规划的数学模型三、整数规划解的特点1.整数规划问题的可行解集合是它的松驰问题可行解集合的一个。2.整数规划问题最优解的目标函数值松驰问题最优解的目标函数值。3.对松驰问题最优解中非零分量取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。子集不优于8§1整数规划的数学模型三、整数规划解的特点1.整数规划问题例1:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱24139例1:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获解：设

分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题。其数学模型为:（1）10解：设分别为甲、乙两种货物的托运箱数.则这是一个若暂且不考虑

取整数这一条件。则(1)就变为下列线性规划:（2）将式(2)称为(1)的松驰问题，解(2)得到最优解:（3）但它不满足(1)的整数要求。因此它不是(1)的最优解。11若暂且不考虑取整数这一条件。则(1)就变为下列线若取X1=(5,0)T，它不满足(1)中的约束条件1。

若取X2=(4,0)T，X2是(1)的可行解,但它却不是(1)的最优解。

因为当X2=(4,0)T

时,Z=80,当X3=(4,1)T时,Z′=90>Z,即松驰问题的最优解通过“舍零取整”得到的X1,X2都不是(1)的最优解。因此通过松驰问题最优解的“舍零取整”的办法,一般得不到原整数规划问题的最优解。12若取X1=(5,0)T，它不满足(1)中的约束条件1。k0

={(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l)}将C点“舍零取整”后得到的X1=(5,0)T不在K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点。松驰问题(2)的可行域K如图,(4.8,0)(4,0)则原整数规划(1)的可行域K0应是K中有限个格点(整数点）的集合。图中“*”为整数点(格点)。例2：见书P132例413k0={(0,0),(0,1),(0,2),(1,0),(由于整数规划问题(1)可行解的个数较少，故可用“穷举法”来求解,即将

K0中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解。取=0,1,2,3,4其组合最多为15个(其中有不可行的点)。=0,1,2但对大型问题，这种组合数的个数可能大得惊人!如在指派问题中，有n项任务指派n个人去完成，不同的指派方案共有n!种。当n=20时，这个数超过2×1018。如果用穷举法每一个方案都计算一遍，就是用每秒亿次的计算机，也要几十年。14由于整数规划问题(1)可行解的个数较少，故可用“穷举法”来求显然“穷举法”并不是一种普遍有效的方法。因此研究求解整数规划的一般方法是有实际意义的。自20世纪60年代以来，已发展了一些常用的解整数规划的算法，如各种类型的割平面法、分枝定界法、解0-1规划的隐枚举法、分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果。

15显然“穷举法”并不是一种普遍有效的方法。因此研究求解整数规划§2解纯整数规划的割平面法割平面法在1958年由R.E.Gomory首先提出。一、割平面法的思想若松驰问题的最优解不满足整数约束，就设法在问题上增加一个约束，把包含这个非整数解的一部分可行域从原来的可行域中割掉，但不割掉任何一个整数可行解，这个新增加的约束条件就称为割平面约束或Gomory约束。16§2解纯整数规划的割平面法割平面法在1958年由R.E.且为整数p(3/4,7/4)****q(1,1)17且为整数p(3/4,7/4)****q(1,1)17二、割平面法步骤1.解松驰问题的最优解；2.若X*的所有分量均为整数，则满足整数约束，X*即为整数规划的最优解。若存在X*的某个分量为小数，则选取分数部分最大的分量，构造新的约束条件；3.将新的约束条件加入松驰问题中，形成一个新的线性规划，对这个新的线性规划求解；4.若新的解满足整数约束，则此解为整数规划的最优解，否则重复第2，3步，直到获得最优解为止。18二、割平面法步骤1.解松驰问题的最优解；18三、新约束条件的构造在松驰问题的最优单纯形表中，m个约束方程可表示为：其中Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。19三、新约束条件的构造在松驰问题的最优单纯形表中，m个约束方程三、新约束条件的构造若不是整数，其对应的约束方程：分解和成两部分，一部分是不超过该数的最大整数，另一部分是余下的正小数。即：20三、新约束条件的构造若不三、新约束条件的构造且为整数且为整数构造新的约束条件为：割平面约束21三、新约束条件的构造且为整数且为整数构造新的约束条件为：割平四、新增约束条件的性质性质1：原松驰问题的非整数最优解不满足新增约束条件。性质2：原松驰问题的整数可行解均满足新增的约束条件，也就是说，整数可行解始终保留在每次形成的线性规划的可行域中。22四、新增约束条件的性质性质1：原松驰问题的非整数最优解不满足下面说明新增约束：能够“割掉”松驰问题中的非整数可行解。证明：设X*为松驰问题的最优解，将其代入新增约束有：，（因非基变量取值为0）这与矛盾，即X*不满足新增约束。注：经验表明若从最优单纯形表上选择具有最大小数部分的非整数分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。23下面说明新增约束：证明：设X*为松驰问题的最优解，将其代入新例1：用割平面法求解整数规划且为整数解：引入松驰变量x3，x4，将问题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下：24例1：用割平面法求解整数规划且为整数解：引入松驰变量x3，xcj1100CBXBbx1x2x3x411x2x17/43/401103/4-1/41/41/400-1/2-1/2割平面约束为：引入松驰变量x5，得割平面方程：x1,x2的最大分量均为3/4，不妨选取x2，得：25cj1100CBXBbx1x2x3x41x27/4013/4cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/400100-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3000-1/3-2/326cj11000CBXBbx1x2x3x4x51x27/401例2：用割平面法求解整数规划且为整数解：引入松驰变量x3，x4，x5，将问题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下：27例2：用割平面法求解整数规划且为整数解：引入松驰变量x3，xcj3-1000CBXBbx1x2x3x4x53-10x1x2x413/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7割平面约束为：引入松驰变量x6，得割平面方程：28cj3-1000CBXBbx1x2x3x4x53x113/7cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/7029cj3-10000CBXBbx1x2x3x4x5X63x11cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x510-53100001000-1/2-21/20010000113/211-7/200-5/70-3/7030cj3-10000CBXBbx1x2x3x4x5X63x11cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4割平面约束为：引入松驰变量x7，得割平面方程：31cj3-10000CBXBbx1x2x3x4x5X63x11cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x715/45/27/4-3/41000001000001000-1/4-1/21/4-1/4000101-5/4-11/2-3/4-1/400001000-1/40-17/4032cj3-100000CBXBbx1x2x3x4x5x6x73cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-400000-4-1上表中给出的最优解x=(1,2,4,3,1,0,0)已满足整数约束，因而，原整数规划问题的最优解为：x1=1,x2=2,maxz=133cj3-100000CBXBbx1x2x3x4x5x6x73*****34*****34§3分枝定界法

在20世纪60年代初LandDoig

和

Dakin

等人提出了分枝定界法。由于该方法灵活且便于用计算机求解，所以目前已成为解整数规划的重要方法之一。分枝定界法既可用来解纯整数规划，也可用来解混合整数规划。

分枝定界法的主要思路是首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则：

增加新约束——缩小可行域;

将原整数规划问题分枝——分为两个子规划,再解子规划的伴随规划；

通过求解一系列子规划的伴随规划及不断地定界。最后得到原整数规划问题的整数最优解。

35§3分枝定界法在20世纪60年代初LandDoig例1：某公司计划建筑两种类型的宿舍。甲种每幢占地0.25×103m2,乙种每幢地0.4×103m2。该公司拥有土地3×103m2.计划甲种宿舍不超过8幢，乙种宿舍不超过4幢。甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元。问该公司应计划甲、乙两种类型宿舍各建多少幢时，能使公司获利最大?36例1：某公司计划建筑两种类型的宿舍。甲种每幢占地0.25×1解：设计划甲种宿舍建

幢,乙种宿舍建

幢,则本题数学模型为:这是一个纯整数规划问题,称为问题

。将(1)中约束条件的系数全化为整数,改为：（1）37解：设计划甲种宿舍建幢,乙种宿舍建幢,则本题数学这然后去掉整数条件,得到问题

的伴随规划(2),称之为问题（2）38然后去掉整数条件,得到问题的伴随规划(2),称之为（84(5.6,4)求解问题

,得到最优解及最优值：3984(5.6,4)求解问题,得到最优解及最优值：1.计算原问题

目标函数值的初始上界因为问题

的最优解不满足整数条件,因此

不是的最优解,又因为

的可行域

问题

的可行域

,故问题

的最优值不会超过问题

的最优值。即有：因此可令

作为

的初始上界

。即：一般说来,若问题

无可行解,则问题

也无可行解,停止计算。若问题

的最优解

满足问题

的整数条件,则

也是问题

的最优解,停止计算。401.计算原问题目标函数值的初始上界因为问题2.计算原问题

目标函数值的初始下界若能从问题

的约束条件中观察到一个整数可行解，则可将其目标函数值作为问题

目标函数值的初始下界，否则可令初始下界Z=-∞。给定下界的目的，是希望在求解过程中寻找比当前

更好的原问题的目标函数值。对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0。问题

的最优目标函数值决不会比它小,故可令

=0.412.计算原问题目标函数值的初始下界若能从问题3.增加约束条件将原问题分枝当问题

的最优解

不满足整数条件时,在

中任选一个不符合整数条件的变量。如本例选

，显然问题

的整数最优解只能是

或

,而绝不会在5与6之间。因此当将可行域

切去

部分时,并没有切去

的整数可行解。可以用分别增加约束条件

及

来达到在

切去

部分的目的。

切去

后就分为

及

两部分,即问题

分为问题

及问题

两枝子规划。

423.增加约束条件将原问题分枝当问题的最优解不满问题问题则问题

的可行域为

见图。43问题问题则问题的可行域为见图。84(5.6,4)K1K256解为:解为:(5,4)(6,3.75)4484(5.6,4)K1K256解为:解为:(5,4)(6问题

的解

是整数最优解,它当然也是问题

的整数可行解,故

的整数最优解同时问题

也被查清,成为“树叶”。因为

,不满足整数条件,故问题

分别增加约束条件：及。建立相应的伴随规划——问题

与45问题的解是整数最优解,它当然也是问题问题问题它们的可行域分别为因为

，问题

无可行解，此问题已是“树叶”，已被查清。46问题问题它们的可行域分别为因为，问题无84B1K263K3求解问题

,得到最优解(7.2,3)4784B1K263K3求解问题,得到最优解(7.2,3因为

,不满足整数条件,故问题

分别增加约束条件：及。建立相应的伴随规划——问题

与问题问题48因为,不满足整数条件,故问题分84B1B263K37K5K6解为:(7,3)(8,2.5)4984B1B263K37K5K6解为:(7,3)(8,2.5当解完一对分枝后,得到

因此所有分枝均已查明。故已得到问题

的最优解:或故该公司应建甲种宿舍7幢、乙种宿舍3幢;或甲种5幢、乙种4幢时,获利最大，获利为130万元。50当解完一对分枝后,得到问题问题问题问题问题问题问题不可行51问题问题问题问题问题问题问题不可行51分枝定界法步骤:第1步:将原整数线性规划问题称为问题

。去掉问题的整数条件,得到伴随规划问题

。第2步:求解问题

,有以下几种可能:(l)

没有可行解,则

也没有可行解,停止计算。(2)

得到

的最优解,且满足问题

的整数条件,则

的最优解也是

的最优解,停止计算。(3)得到不满足问题

的整数条件的

的最优解,记它的目标函数值为

,这时需要对问题

(从而对问题

)进行分枝，转下一步。52分枝定界法步骤:第1步:将原整数线性规划问题称为问题。去第3步:确定初始上下界

与

以

作为上界

，观察出问题

的一个整数可行解,将其目标函数值记为下界

。若观察不到,则可记

=-∞，转下一步。 第4步:将问题

分枝在

的最优解

中,任选一个不符合整数条件的变量

,其值为

,以

表示小于

的最大整数。构造两个约束条件：53第3步:确定初始上下界与以作为上界，观将这两个约束条件分别加到问题

的约束条件集中,得到

的两个分枝:问题

与

。对每个分枝问题求解,得到以下几种可能:(1)

分枝无可行解——该分枝是“树叶”。(2)求得该分枝的最优解,且满足

的整数条件。将该最优解的目标函数值作为新的下界

,该分枝也是“树叶”。(3)求得该分枝的最优解,且不满足

的整数条件,但其目标函数值不大于当前下界

,则该分枝是“枯枝”需要剪枝。54将这两个约束条件分别加到问题的约束条件集中,得到对每(4)求得不满足

整数条件的该分枝的最优解,且其目标函数值大于当前下界

,则该分枝需要继续进行分枝。若得到的是前三种情形之一,表明该分枝情况已探明,不需要继续分枝。若求解一对分枝的结果表明这一对分枝都需要继续分枝，则可先对目标函数值大的那个分枝进行计算，且沿着该分枝一直继续进行下去，直到全部探明情况为止。再返过来求解目标函数值较小的那个分枝。55(4)求得不满足整数条件的该分枝的最优解,且其目标函第5步:修改上、下界

修改下界

：每求出一次符合整数条件的可行解时,都要考虑修改下界

,选择迄今为止最好的整数可行解相应的目标函数值作下界

。(2)修改上界

：每求解完一对分枝,都要考虑修改上界

上界的值应是迄今为止所有未被分枝的问题的目标函数值中最大的一个。在每解完一对分枝，修改完上、下界

和后,若已有

此时所有分枝均已查明,即得到了问题

的最优值求解结束。56第5步:修改上、下界修改下界：每求出一次符合整数条件若仍有

,则说明仍有分枝没查明，需要继续分枝,将需要进行分枝的问题称为问题B0，回到第4步。57若仍有,则说明仍有分枝没查明，需要继续分枝,将P138例6A(3/2,10/3)z=29/6B(2,23/9)z=41/9C(1,7/3)z=10/358P138例6A(3/2,10/3)z=29/6B(2,23P138例6C(1,7/3)z=10/3D(33/14,2)z=61/14E(3,1)z=4F(2,2)z=459P138例6C(1,7/3)z=10/3D(33/14,2§40-1型整数规划一、0-1型整数规划的概念0-1型整数规划是整数规划的特殊情形，它的变量xj仅取值0或1，这时xj称为0-1变量（或二进制变量，逻辑变量）。xj仅取0或1，可表示为：它和一般的整数规划的约束条件在形式上是一致的。为整数P130例2在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论。60§40-1型整数规划一、0-1型整数规划的概念0-1型整二、引入0-1变量的实际问题1.投资场所的选定——相互排斥的计划例1:某公司拟在市东、西、南三区建立门市部。拟议中有7个位置A1,…，A7可供选择。规定:在东区：由A1,A2,A3三个点中至多选两个；在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。如选用Ai点，设施投资估计为bi元，每平方米可获利润估计为Ci元，但投资总额不能超过B元，问应选择哪几个点可使年利润最大？61二、引入0-1变量的实际问题1.投资场所的选定——相互排斥的解：引入0-1变量，令：点被选用点不被选用于是问题的数学模型为：(i=1,2,…,7)62解：引入0-1变量，令：点被选用点不被选用于是问题的数学模型二、引入0-1变量的实际问题2.相互排斥的约束条件或为了统一在一个问题中，引入0-1变量y，则上述约束条件可改写为：其中M是充分大的数。P142例763二、引入0-1变量的实际问题2.相互排斥的约束条件或为了统一二、引入0-1变量的实际问题3.固定费用问题P143例84.工件排序问题P144例9(略)64二、引入0-1变量的实际问题3.固定费用问题P143例84三、0-1型整数规划的过滤隐枚举法设0-1型整数规划：解的步骤：(1)列出n个分量的2n种组合，算出相应的目标函数值。(2)X*为任一组合，判断X*是否满足所有约束条件，若满足则转下一步，否则舍弃该组合。65三、0-1型整数规划的过滤隐枚举法设0-1型整数规划：解的步三、0-1型整数规划的过滤隐枚举法解的步骤：(3)设Z*=CX*，将Z≥Z*作为过滤条件。(4)对其它组合，若不满足过滤条件，则舍弃；对满足过滤条件的，看其是否满足所有约束，不满足舍弃。设满足所有约束的组合为X',将Z'=CX'作为新的过滤条件。(5)检查所有可能的组合，最终可得最优解。66三、0-1型整数规划的过滤隐枚举法解的步骤：(3)设Z*=C例2：求解0-1型整数规划(a)(b)(c)(d)注：为了进一步减少运算量，对于最大化（最小化）问题，常按目标函数中各变量系数从小到大（从大到小）的顺序重新排列各变量，以使最优解可能较早出现。67例2：求解0-1型整数规划(a)注：为了进一步减少运算量，对例3：求解0-1型整数规划(a)(b)(c)68例3：求解0-1型整数规划(a)68四、0-1型整数规划的分枝定界解法解的步骤：(1)目标函数极小化，约束条件为≥。(2)目标函数系数非负化。(3)目标函数中，变量按系数从小到大排列，约束条件中各变量的排列顺序也做相应变化。(4)令所有变量为零，检查约束条件是否满足，若满足此解即为最优解，否则转下一步。69四、0-1型整数规划的分枝定界解法解的步骤：(1)目标函数极四、0-1型整数规划的分枝定界解法解的步骤：(5)按在目标函数中排列顺序（从左到右）依次令各变量分别取“0”或“1”，将问题分为两个子问题，各自检查是否满足约束条件，若满足，则保留所有可行解中目标函数值最小的分枝进行定界，将可行解中目标函数值大的分枝剪去。若不满足，则对目标函数值较小的分枝优先进行下一步分枝。直到所有分枝均检查清楚为止。这时保留下来的分枝即为最优解。70四、0-1型整数规划的分枝定界解法解的步骤：(5)按在目标函例4：用分枝定界法求解0-1型整数规划例5：用分枝定界法求解0-1型整数规划71例4：用分枝定界法求解0-1型整数规划例5：用分枝定界法求解注：当发生下列三种情况之一时，该分枝不再继续往下分，或保留或剪枝(1)该分枝为可行解，这时应保留所有可行解中目标函数值最小的分枝，将可行解中目标函数值大的分枝剪去。(2)不管是否为可行解，分枝目标函数值已超过保留下来的可行解的目标函数值的分枝剪去。(3)当该分枝中某些变量的值已确定的情况下，其余变量不管取什么值都无法满足一个或几个约束时，即该分枝无可行解，实行剪枝。72注：当发生下列三种情况之一时，该分枝不再继续往下分，或保留或§5指派问题一、指派问题的标准形式及其数学模型在现实生活中，有各种性质的指派问题，如，有若干项工作需要分配给若干人来完成；有若干项合同需要选择若干个投票者来承包；有若干班级需要安排各教室上课等。指派问题的标准形式是：有n个和n件事，已知第i做第j件事的费用为cij(i,j=1,2,…,n)，要求确定人和事之间的一一指派方案，使完成这n件事的总费用最少。73§5指派问题一、指派问题的标准形式及其数学模型在现实生活§5指派问题一、指派问题的标准形式及其数学模型一般称矩阵为指派问题的效率矩阵（coefficientmatrix）矩阵C中，第i行中各元素表示第i个人做各事的费用；第j列各元素表示第j事由各人做的费用。74§5指派问题一、指派问题的标准形式及其数学模型一般称矩阵§5指派问题一、指派问题的标准形式及其数学模型令：i,j=1,2,…,n指派问题的数学模型为：(a)(b)(c)(d)每件事有且只有一个人去做每个人做且只做一件事75§5指派问题一、指派问题的标准形式及其数学模型令：i,j§5指派问题一、指派问题的标准形式及其数学模型对于问题的每一个可行解，可用解矩阵来表示：矩阵每列元素中有且只有一个

，以满足约束条件

。矩阵每行元素中有且只有一个

，以满足约束条件

。指派问题有

可行解。11(b)(c)n!76§5指派问题一、指派问题的标准形式及其数学模型对于问题的§5指派问题二、指派问题的匈牙利解法指派问题是0-1规划的特例，也是运输问题的特例，因此可用整数规划或运输问题的解法求解，然而这就如同用单纯形法解运输问题一样是不够合算的，利用指派问题的特点可有更简便的解法——匈牙利解法。匈牙利解法的基本原理就是效率矩阵的任一行(或列)减去(或加上)任一常数对原指派问题的最优解不会发生影响。77§5指派问题二、指派问题的匈牙利解法指派问题是0-1规划§5指派问题三、匈牙利解法的一般步骤(1)变换系数矩阵先对各行元素分别减去本行中的最小元素；再对各列元素分别减去本列中的最小元素；这样，系数矩阵中每行及每列中至少有一个零元素，同时不出现负元素。(2)在变换后的系数矩阵中确定独立零元素若独立零元素有n个，则已得出最优解；若独立零元素少于n个，则转下一步。(3)作能覆盖所有零元素的最少直接数目的直线集合78§5指派问题三、匈牙利解法的一般步骤(1)变换系数矩阵(§5指派问题三、匈牙利解法的一般步骤(1)变换系数矩阵先对各行元素分别减去本行中的最小元素；再对各列元素分别减去本列中的最小元素；这样，系数矩阵中每行及每列中至少