BW Professional Cutter Expert www.tool-tool.com

碧威股份有限公司
www.tool-tool.com
轉述：
前面讨论的线性规划问题中，最优解可能是整数，也可能不是整 数，而在许多实际问题中都要求解答必须是整数，例如，所求的解是完成某任务需要的人数、 购买的机器台数、设备的维修次数等。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过四舍五入化整即可。但这常常是不行的，因 为化整后不见得是可行解，或虽为可行解，但不一定是最优解。
【例1】求解下面的规划问题：
max z= 2+ 3
+ ≤4.95
2+ ≤400
≥0，≥0
，都是整数
我们用图解法求解。在图5-1中，阴影部分是上述规划问题的可行域，其最优点为A（0，4.95），最优值为14.85。图中画"×"号的点是整数规划的 可行点，其最优点为B（0，4），最优值为12。若将A点四舍五入"凑整"为（5，0），则对于原问题而言已不是可行解。

图5-1
由上例可以看出，舍入化整的方法有时是行不通的，对于这一类问题必须进行专门的研究，即整数规划。
所谓整数规划，就是在一般的线性规划模型中再加上全部变量或部分变量只能取整数值的要求所得到的一类规划。其中，要求全部的变量都为整数的问题称为纯整数 规划（Pure Integer Programming）或称为全整数规划（All Intger Programming）；而仅要求一部分变量为整数的问题称为混合整数规划。整数规划中的一种特殊情形是0-1规划，它的变数取值仅限于0或1。
显然，整数线性规划的可行解集是相应的线性规划的可行解集的一个子集。很多实际问题都可以归结为整数规划问题，而解整数规划问题通常比解相应的线性规划问 题困难得多，因而研究整数规划的问题解法是很有意义的。本章介绍几种基本的解法。

第一节 分枝定界解法

在求解纯整数规划时，若可行域是有界的，容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以确定最优解。对于小型的问题，变量 数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。然而对于大型的问题，可行解的个数很多时，穷举法就行不通了。所以我们的方法一般是 仅检查可行的整数组合的一部分，就能定出最优的整数解。分枝定界解法（Branch and Method）就是其中的一个。
分枝定界法既可以求解纯整数规划问题，又可以求解混合整数规划问题。该方法是先求解整数规划相应的线性规划问题，如果其最优解不符合整数条件，则需要增加 新的约束，来缩小可行域，得到新的线性规划问题，再求解之……这样通过解一系列线性规划问题，最终得到原问题的整数最优解。
下面结合例题来说明分枝定界法的算法步骤。
【例2】用分枝定界法求解整数规划问题
max z=40+90
9+7≤56
7+20≤70 线性规划问题（0）
≥0, ≥0
, 都是整数

一、给定原问题的初始上界
不考虑" , 都是整数"这个条件，求解整数规划原问题相应的线性规划问题（0），得到：
=4.809，=1.817，z0=355.9
而原问题的目标函数最大值绝不会比z0更大，故令原问题的初始上界 为z0。
因上述 , 均不符合整数条件，故要继续求解。
一般来说，若问题（0）具有无界解，则停止求解，原问题也具有无界解。

二、给定原问题的初始下界
若容易得到原问题的一个明显的整数可行解，则可将其目标函数值做为原问题的初始下界 ；若不易得到一个整数可行解，可令 =-∞或待分枝定界法求出一个整数可行解后，再给出下界。给定 后，求解的目的仅在于寻找比 更好的原问题的目标函数值。
上述例题有一个明显的整数可行解x=（0，0）T，这时z=0，原问题的最大目标函数值绝对不会比它更小，故令 =0。
三、将一个线性规划问题分为两枝
从问题（0）的最优解中，任选一个不符合整数条件的变量，例如选=4.809，因为的最优整数解只可能是≤4或≥5，而绝不会在4和5之间。在问题（0）上增加约束条件≤4，构成一个分枝--问题（1）；在问题（0）上增加约束条件：≥5，构成另一个分枝--问题（2）。由问题（0）到问题（1）和问题（2），可行域缩小了，但没有丢掉原问题的任何一个整数可行解。由同一问题分解出的两个分枝，也称"一对分枝"。
下面，用图5-2中的阴影部分表示问题（0）的可行域R0，用图5-3中的两块阴影部分分别表示问题（1）、（2）的可行域R1，R2。

　　　　　（a）　　　　　　　　　（b）
四、分别求解上述一对分枝
一般而言，求解某个线性规划分枝时，可能出现以下几种情况：
1．无可行解。表示该分枝已查明，不再由此继续分枝。
2．得到整数最优解。表示该分枝已查明，不再由此继续分枝。
3．得到非整数最优解。
若其目标函数值z<z，则该分枝不可能含有原问题的最优解，由此继续分枝是不必要的，应该"剪枝"。
若z> ，则仍需由此继续分枝。当一对分枝都需要继续分解时，对极大化问题而言，一般将目标函数值较小的一枝暂且放下，留待以后处理，而沿着另一枝继续分解下去， 直到搜索完毕。然后，可将留待处理的那些分枝，按照"后进先出"的原则，依次取出进行搜索。按照以上的方法求解，有可能尽早得到一个整数可行解。
分别求解上述例题的一对分枝，有
问题（1）　　　问题（2）
z1=349 　　　　z2=341.39
=4 　　　　　=5
=2.1　　　　 =1.571
仍未得到完全的整数解。
五、修改原来的上、下界
1．修改下界。下界 一般是至今为止最好的整数可行解相应的目标函数值。因此，每求出一个新的整数可行解后，都要把新的z值与原来的下界比较，若新的z值更大些，则以它为新的下界。在整个分枝定界法的求解过程中，下界的值不断增大。
2．修改上界。每求解完一对分枝，都要考虑一下修改上界 的问题。新的上界应该小于原来的上界，而且是至今为止所有未被分枝的问题的目标函数值中最大的一个。在整个分枝定界法的求解过程中，上界的值不断减小。
例题中，初始上界为z0；求解完问题（1）、问题（2）之后，上界变为z1。

六、结束准则

上面是用图5-4表示例题的求解过程和求解结果。图中的"×"表示剪枝。该例题的求解顺序依次是：问题（0）、问题（1）、问题（2）、问题（3）、问题（4）、问题（5）、问题（6）。
如果用分枝定界法求解混合整数规划，则分枝的过程只针对有整数要求的变量进行，而不管连续变量的取值如何，其整个求解过程与纯整数规划的求解过程基本相同。
从以上的介绍可知，分枝定界法只需检查变量所有可行的组合中的一部分，即可确定最优解。

第二节 割平面法

割平面法是R·E·Gomory于1958年提出的一种方法，它既能求解纯整数规划问题，也可以求解混合整数规划问题。这个方法的基础仍然是用解线性规划 的方法去解整数规划问题。首先不考虑变量xi是整数这一条件，但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这个部分只包 含非整数解，没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点桥好是问题的最 优解。下面仍以第一节的例题问例，介绍割平面法的基本原理和步骤，重点是新约束的求法。
【例3】用割平面法求解整数规划问题
　　　　　　　　　maxz=40+90 ①
　　　　　　　　　+7≤56 ②
线性规划问题（0） 7+20≤70 ③
　　　　　　　　　≥0, ≥0 ④
　　　　　　　　　 , 都是整数 ⑤
求解过程如下：

一、由原问题构造线性规划问题（1）
应用割平面法之前，必须把问题（0）中原始约束条件的所有系数与常数变为整数，然后再化为标准型，这样得到线性规划问题（1）。
　　　　　　　　　min（-z）= -40-90 ⑥
　　　　　　　　　9+7+=56 ⑦
线性规划问题（1） 7+20+x4=70 ⑧
　　　　　　　　　≥0, （j=1，2，3，4） ⑨

二、求解线性规划问题（1）
用单纯形法的表格形式爱解，得最终表，见表5-1
表5-1

由表及式max z=-[min（-z）]可知，问题（0）的最优解A1点为
=630/131=4.809， =238/131=1.817， z1=355.9
因为没有得到整数解，故应引入新的约束。

三、求一个切割方程
切割方程可以由上述最终表上的任一个含有非整数基变量的约束等式演变而来，因而切割方程不是唯一的。
1．在上述最终表中，任选一个非整数基变量所在的约束等式。
由最终表可知，，两个基变量都不是整数，可任取其一。如，选所在的约束等式，使它演变出切割方程。该约束等式为
-7/131 +9/131 x4=238/131 ⑩
2．将⑩式左端各非基变量的系数及右端的常数都分解成一个整数与一个非负真分数之和。于是有
+（-1+124/131） +（0+9/131）x4=（1+107/131） ⑾
3．通过移项对上式重新组合。
只把⑾式中各非基变量的系数为非真分数的部分留在左端，其余各项均移到右端，并将右端变成两项：一项是常数项中的非负真分数，另一项是右端其它项之和，这里的"右端其它项"包括：常数项中的整数部分、基变量项和具有整数系数的各非基变量项。本例将⑾式变为
124/131 +9/131 x4=107/131+（1- + -0 x4） ⑿
4．分析⑿式并得到切割方程。
因为要求，都是非负整数，又根据⑦、⑧可知，，x4也都是非负整数（否则，应在引入附加变量，x4之前，将不等式两端同乘以适当常数，使原始约束条件中所有系数与常数都为整数）。
在⑿式中，容易看出，左端、右端都大于等于零。因各变量均为非负整数，故⑿式右端的第2项是整数项，又因右端≥0，故⑿式右端的第2项只能是0或正证书，不可能是负整数，因此有
124/131 +9/131 x4≥107/131 ⒀
为了方便后面的计算，避免引入人工变量，把⒀式两端同乘以（-1）， 再加上附加变量x5，化为等式约束，得
-124/131 -9/131 x4+ x5=-107/131
⒁式即所求的切割方程。
当需要用，表示切割方程时，可由约束条件⑦、⑧得
=56-9-7 ⒂
x4=70-7-20 ⒃
把⒂、⒃式代入⒀式，得
9+8≤57 ⒄
引入附加变量x5，得到
9+8+x5=57 ⒅
上述⒁、⒄、⒅式均可做为第一个切割方程。
这里对上面介绍的求切割方程的方法小结如下。
（1）设xBi是线性规划问题的最终表上第i行约束式的基变量，其值为非整数。由最终表可得
　　　　　　⒆
其中，j∈J，J为非基变量下标的集合。
（2）将bi和aij都分解为整数部分F与非负真分数部分f之和，即
bi=Fi+ fi （0≤fi <1） ⒇
aij=fij+ fij （0≤fij <1） (21)
(3)将⒇、(21)代入⒆式中得

即

因为

四、构成线性规划问题（2）并求解
在线性规划问题（1）的基础上，增加第一个切割方程，构成线性规划问题（2），可用单纯形法或对偶单纯形法求出最优解。
求解问题（2）时，可以在问题（1）的最终表的基础上，增加切割方程⒁的数据，得到第二次迭代表（见表5-2），用对偶单纯形法迭代一次，即可得到最优解A2点为：
=145/31=4.677， =231/124=1.863，=107/124=1.863， z1=355.9

我们也可以在线性规划问题（1）的基础上，增加第一个切割方程⒅，构成问题（2）。另外，如果采用图解法求解线性规划问题，则可以在问题（0）的基础上，增加第一个切割方程⒄，以构成问题（2）。
从表5-2可知，问题（2）仍未得到整数解，故应返回步骤三，继续求第二个切割方程继续求第二个切割方程。
根据表5-2的最终表，选择基变量所在的约束等式，由它演变出第二个切割方程。基变量所在的约束等式为
+9/124x4-7/124x5=231/124 (23)
即
9/124x4+ 117/124x5=107/124+(1- -0x4+ x5) (24)
分析(24)式可知
9/124x4+ 117/124x5≥107/124 (25)
(25)式即为第二个切割方程，有⒅式可得
x5=57- 9- 8 (26)
把⒃、(26)式代入式，得
9+ 9≤58 (27)
(27)式即是用，表示的第二个切割方程。

五、图解法结果
上述例题的图解法结果如图5-5所示。图中，凸集A1BEC是线性规划问题（0）的可行域，也是问题（1）的可行域，最优点是约束直线②与③的交点A1。在问题（0）的基础上增加第一个切割方程⒄，构成问题（2），第一个切割方程⒄切去了ΔA1AA2，使问题（2）的可行域缩小为凸集A2ABEC，最优点为A2。在问题（2）的基础上增加第二个切割方程(27)，构成问题（3），第二个切割方程(27)切去了ΔA2AA3，使问题（3）的可行域缩小为凸集A3ABEC，最优点为A3。继续迭代，当得到整数最优解时，一定是点（4，2）（由第一节已知，本例的整数最优解为=4，=2，z=340）到了最终的可行域的边界上且成为一个顶点。

图5-5

六、割平面法的重要性质
可以证明，割平面法有如下两个重要性质。
性质1：割平面法割去了整数规划原问题相应的线性规划问题的最优解。
性质2：割平面法未割去整数规划原问题的任一可行解，即未割去其相应的线性规划问题的任一整数可行解。
在实际应用中，割平面法有些情况下收敛迅速，而另一些情况下又可能收敛很慢。因此，求解整数规划问题时，可以先选用割平面法，如不能内在适当次数内收敛于最优解，则换成分枝定界法或其它方法来求解。

第三节 0-1型整数规划

0-1型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1，这时xi称为0-1变量，或称二进制变量。可以引入0-1变量的实际问题很多，如相互排斥的计划，相互排斥的约束条件等等。
【例4】某公司拟在市东、西、南三区建立门市部，拟议中有7个位置（点），Ai（i=1，2，…，7）可供选择。规定：
在东区，由A1，A2，A3三个点中至多选两个；
在西区，由A4，A5两个点中至少选一个；
在南区，由A6，A7两个点中至少选一个；
如选用Ai点，设备投资估计为bi元，每年可获利润估计为Ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？

解0-1规划一般采用一种隐枚举法。这种解法的基本思路是从所有变量等于0出发，依次指定一些变量为1，直至得到一个可行解，它就是至今为止最好的可行 解。此后，依次检查变量等于0或1的某些组合，对至今为止最好的可行解不断加以改进，最终获得最优解。隐枚举法与穷举法有着根本的区别，它不需要将所有的 变量组合一一枚举。实际上，在得到最优解时，很多可行的变量组合并没有被枚举，只是通过分析、判断，排除了它们是最优解的可能性。也就是说，它们被隐含枚 举了。故此法叫隐枚举法。
0-1规划数学模型的标准形式为：

下面结合例题介绍求解0-1规划的隐枚举法。
【例5】求解如下的0-1规划问题：
min z= 4+ 3+ 2
2-5+3≤4
4+ + ≥3
+ ≥1
xi=0或1，（j=1，2，3）
一、把0-1规划的数学模型化成标准形式：
min z= 4+ 3+ 2
Q1=4-2-5+3≥0
Q2=-3+4++≥0
Q3=-1++≥0
xi=0或1，（j=1，2，3）
求解过程参见图5-6

二、判断无约束下最优解（0，0，0）T即节点1是否是可行解？
显然，（0，0，0）T是约束下的最优解，若它能使各约束式得到满足，则它必是0-1规划原问题的最优解。
本例中把（0，0，0）T代入各约束式，得
Q1=4≥0
Q2=-3
Q3=-1
我们称无约束下最优点（0，0，0）T为节点1，现已知节点1不是可行解。
三、判断由节点1继续分枝，能否得到可行解？
判断的方法是：在各个不满足的约束中，令每个正系数的变量都为1，看是否可使原来不满足的约束都变为满足。如是，则由节点1继续分枝下去，可能得到可行解；如否，则不必由节点1再分枝下去，因为节点1不可能引出可行解。
本例中，原来有Q2、Q3约束式不满足。在Q2中，令===1，得Q2=5>0；在Q3中，令==1，得Q3=1>0，故令一些变量为1可使两个不满足的约束都变为满足，这说明从节点1分枝可能得到可行解。
从节点1分枝的目的，是为了得到第一个可行解。
四、欲分枝，必须从某个不满足的约束的系数为正值的变量中，选择一个自由变量作非自由变量。
所谓自由变量，就是没有规定其特定值（0与1中的一个）的变量，而被赋予特定值（0与1中的一个）的变量称为非自由变量。
在节点1处，、、均为自由变量，可从中挑选一个，挑选的原则是： =1应使所有约束离可行性的总距离为最小。
本例中，若令=1（==0），则
Q1=2，其离可行性的距离用0表示；
Q2=1，其离可行性的距离用0表示；
Q3=-1，其离可行性的距离用1表示；
因此，若令=1，则所有约束离可行性的总距离为1。
同理可得，若=1（==0），则所有约束离可行性的总距离为2；若=1（==0），则所有约束离可行性的总距离为0。
因此，选作非自由变量，可使所有约束离可行性的总距离为最小。
五、从节点1分枝，规定非自由变量=1，得到节点2。
规定非自由变量=1，自由变量==0，得到节点2。检验节点2，它满足各约束，是可行解，得到z=2，这是至今为止得到的最好的可行解相应的目标函数值。
六、由节点2退回到节点1，从节点1再分枝：规定非自由变量=0，得到节点3。
　　规定非自由变量=0，自由变量==0，得到节点3。检验节点3，不是可行解。
　　七、在已得到至今为止最好的可行解的情况下，判断各节点是否继续分枝？
　　判断的准则是：若继续分枝可能得到比至今为止最好的可行解更好的可行解，则继续分枝；否则，便停止分枝。
　　1．由可行解节点2是否继续分枝？
　　由节点2继续分枝，意味着在保持非自由变量=1的基础上，令原来为0的某个其它变量等于1，而这样只会增加目标函数的值，不会得到比z=2更小的值，故由节点2不再继续分枝，即由节点2可能得到的所有的解已被隐枚举了。
　　2．由不可行解节点3是否继续分枝？
　　由节点3继续分枝的目的，不是为了得到一般的可行解，而是要得到优于z=2的可行解。
　　要继续分枝，首先必须有一个符合某些条件的自由变量的下标集合T，以便从中挑出一个作非自由变量。对节点3而言，非自由变量是，自由变量，，那么，的下标是否都能进入T集合呢？因为此前已求出至今为止最好的目标函数值z=2，故只有那些可能使问题优于z=2的可行解的自由变量才能进入T，而不是当前所有自由变量均属于T。那么，自由变量要进入T，必须满足哪些条件呢？
　　条件之一：该变量在不满足的某个约束中有一个正的系数；
　　条件之二：该变量在目标函数中的系数应小于w，

式中的z是至今为止最好的目标函数值，S是非自由变量的下标的集合。本例中w=2-c3=2-2×0=2。在节点3处变量，均满足上述条件之一，但均不满足条件之二，故T=Φ，即由节点3继续分枝不可能得到比z=2更好的目标函数值了，因此，由节点3不再分枝。
　　至此，各节点都已查明，都没有必要继续分枝了，故得到0-1规划的最优解：=0，=0，=1，目标函数最小值为2。
　　本例中，在节点3处，T是空集，故由节点3不再分枝。对一般问题而言，若T非空集，则分别令T中各个变量为1，找出T中使所有约束离可行性的总距离最小的变量（象在节点1处曾经做过的那样），然后把下标j从集合中消去，加入到集合S中，可继续分枝。这样，一直进行到不可能或不必要再继续分枝为止。

　　　　　　　　　　　第四节 指派问题

　 　实际中经常会遇到这样的问题：有n项不同的任务，恰好有n个人可承担这些任务。由于每个人的专长不同，故各人完成不同任务所需的资源（比如时间）也不一 样。问应指派哪个人去完成哪项任务，可使完成n项任务所需的总资源最少？这样一类问题就称为指派问题，或者分配问题（Assignment Problem）。

　　一、指派问题的数学模型
　　首先设0－1变量：
　　　　　　　1表示指派第i个人去完成第j项任务
　　令 =
　　　　　　　0表示不指派第i个人去完成第j项任务
　　用表示第i个人完成第j项任务所需要的资源数。这里，变量共n×n个，与价值系数一一对应。
　　

表示：每个人必须且只能承担一项任务。从以上数学模型可知，指派问题是特殊的0-1规划问题，也是特殊的线性规划运输问题。利用指派问题的特点，有更简便的解法求解这类问题，它就是匈牙利法。

　　二、匈牙利法的基本原理
　　匈牙利法是美国数学家Kuhn提出的一种新颖而又简便的解法，又称画圈法，它是针对目标要求极小化问题提出的。匈牙利法的关键是如何实现系数矩阵具有一组处于不同行又不同列的0元素，并保证以画圈标记的0元素的个数等于矩阵的阶数。以下是两个重要定理：
　　1．指派问题最优解的性质
　　"假设［］是指派问题的价值系数矩阵，现将它的某一行（或某一列）的各个元素都减去一个常数κ（κ可为正，也可为负），得到矩阵［］。那么，以［］为价值系数矩阵的新的指派问题的最优解与原指派问题的最优解相同，但其最优值比原来减小κ"
　　利用上述性质，可使原价值系数矩阵变换为含有很多0元素的新系数矩阵，而其最优解保持不变。在系数矩阵［］中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。若能在系数矩阵［］中得到n个独立的0元素，则令解矩阵［］中对应这n个独立0元素的变量取值为1，其它变量取值为0，就可以得到原指派问题的最优解。
　　2关于矩阵中0元素的定理
　　"系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。"该定理是匈牙利数学家狄·考尼格证明的，指派问题的匈牙利法也是因此而命名。
　　三、匈牙利法的求解步骤
　　我们结合一个例题来说明匈牙利法的求解步骤。
　　【例6】有一份中文说明书需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需的时间如表5-4所示。问应指派何人去完成何工作，使所需时间总量最少？

　　　　　2．进行试指派，以寻求最优解
　　　经过第一步变换后，系数矩阵中每行每列中都已有了0元素；但需要找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵中［］的元素为1，其余为0，这就得最优解。当n 较小时，可用观察法、试探法去找到n个独立0元素。若n 较大时，就必须按一定的步骤去找，常用的步骤为：
　　（l）从只有一个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

可见m=n=4，所以得最优解为：[]=

经一次运算即得每行每列都有有0元素的系数矩阵，再按上述步骤运算，得到

　　　　①

　　这里◎的个数m=4,而n=5；所以解题没有完成，这时应按以下步骤进行。
　　3．首先，作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行。
　（1）对没有◎的行打√号；
　（2）对已打√号的行中所含0元素的列打√号；
　（3）再对所有打√号的列中的含有◎元素的行列打√号；
　（4）重复2、3直到得不出新的打√号的行列为止。
　（5）对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。
　　令这直线数为l。若l

　　由解矩阵得最优指派方案：
　　　　　甲--B，乙--D，丙--E，丁--C ，戊--A。
　　本例还可以得到另一最优指派方案：
　　　　　甲--B，乙--C，丙--E，丁--D，戊--A。
　　所需总时间为minz=32。
　　当指派问题的系数矩阵经过变换得到了同行和同列中都有两个或两个以上0元素时，就可以任选一行（列）中某一个0元素，再划去同行（列）的0元素。这时会出现多重解。
　　以上讨论限于极小化的指派问题。对极大化的问题，即求

可令 =M-
其中M是足够大的常数（如选Cij中最大元素为M即可），这时系数矩阵可变换为
B=[]
这时≥0,符合匈牙利法的条件。目标函数经变换后，即解

BW碧威股份有限公司針對客戶端改善切削方式、提供專業切削CNC數控刀具專業能力、製造客戶需求如：Cutting tool、切削刀具、HSS Cutting tool、Carbide end mills、Carbide cutting tool、NAS Cutting tool、Carbide end mill、Aerospace cutting tool、Carbide drill、High speed steel、Milling cutter、Core drill、鎢鋼銑刀、航太刀具、鎢鋼鑽頭、高速剛、鉸刀、中心鑽頭、Taperd end mills、斜度銑刀、Metric end mills、公制銑刀、Miniature end mills、微小徑銑刀、鎢鋼切削刀具、Pilot reamer、領先鉸刀、Electronics cutter、電子用切削刀具、Step drill、階梯鑽頭、Metal cutting saw、金屬圓鋸片、Double margin drill、領先階梯鑽頭、Gun barrel、Angle milling cutter、角度銑刀、Carbide burrs、滾磨刀、Carbide tipped cutter、銲刃刀具、Chamfering tool、倒角銑刀、IC card engraving cutter、IC晶片卡刀、Side cutter、側銑刀、NAS tool、DIN tool、德國規範切削刀具、Special tool、特殊刀具、Metal slitting saws、Shell end mills、滾筒銑刀、Side and face milling cutters、Side chip clearance saws、交叉齒側銑刀、Long end mills、長刃銑刀、Stub roughing end mills、粗齒銑刀、Dovetail milling cutters、鳩尾刀具、Carbide slot drills、Carbide torus cutters、鎢鋼圓鼻銑刀、Angeled carbide end mills、角度鎢鋼銑刀、Carbide torus cutters、短刃平銑刀、Carbide ball-noseed slot drills、鎢鋼球頭銑刀、Mould cutter、模具用刀具、BW微型渦流管槍、Tool manufacturer、刀具製造商等相關切削刀具、以服務客戶改善工廠加工條件、爭加競爭力。

歡迎尋購～～～