[理学]关于图的H圈H通路.doc

关于图的H圈H通路陈业德（江西制造职业技术学院 330095） 摘要 本文给出了在图对应的矩阵上进行H圈变换和单向H通路变换，获得了图的最优H圈的充要条件，并给出了求最优H圈、最优H通路及最优单向H通路的计算方法。提供了一种实用的解“货郎担问题”和“排序问题”的有效方法。关键词 H圈变换 基本不等式 舍补法 最优H圈（货郎担问题） 最优H通路最优H通路不等式 单向H通路变换 最优单向H通路（排序问题） 自1859年，爱尔兰数学家Hamilton提出周游世界20个城市以来，图论中就有了H圈、H通路问题，如一个简单图是否有H圈，是否有H通路?如何求最优H圈，最优H通路及最优单向H通路等？直到目前都没有一个有效的解决办法，成了图论中的难题。目前使用的枚举法、路线修改法都无济于事，解决不了实际问题。本文给出在图对应的矩阵上进行H圈变换，对解决这些问题取得了较理想的结果。一 图的矩阵表示设G是P个顶点的简单连通无向图（以下都讨论这种图）。联接i j两顶点的边，用表示。当G赋权后，ei j 也表示此边上的权。若i j两点间没有边，用X表示，理解此边是一个很大的数。这样任何一个图都可以看成是一个完全图（用KP表示）。当图的顶点标定后，图G可以用一个上三角形矩阵表示。此矩阵与代数图论中的矩阵都不同，更无一般矩阵的性质。e i j称为矩阵的元素，i为行，j为列。脚码含i的元素称为矩阵的第i行列元素（实为过第i个顶点的边）。这种矩阵称为图对应的矩阵。例如（K6）对应的矩阵为： 图一（K6）矩阵对角线及右上角元素比较重要，统称为对角线元素。K6对应矩阵对角线元素为e 12 e 23 e 34 e 45 e 56 e 16 ；第三行列元素为e 13 e 23 e 34 e 35 e 36。二 图的H圈变换图G中由不同顶点不同边构成的圈称为初等圈（也称回路）。包含所有顶点的初等圈称为Hamilton圈，简称为H圈。若图G对应矩阵的对角线上都是非X元素，则这些元素构成图G的一个H圈。此时图G对应的矩阵，也称为该H圈对应的矩阵。例如K6对应的矩阵也就是H圈1-2-3-4-5-6-1对应的矩阵。又如K6 中H圈1-5-2-4-3-6-1对应的矩阵为：其实这都是按H圈顺序写出的矩阵。定义 设Q是G的一个H圈，用非Q上的m条边替换Q上的m条边，若能得到一个新的H圈，则称这一过程是图G的一个m元H圈变换，简称为m元H圈变换。这种m元H圈变换，在图对应的矩阵上进行，可以看成是用m个非对角线上的元素替换对角线上的m个元素，变换一次得一个新矩阵，对角线上得一个新H圈，新H圈与新矩阵1-1对应。这种H圈变换在Kp对应的矩阵上进行，仅用非对角线上元素替换对角线上元素，就有1/2（P-1）！1 个。三 在矩阵上进行二元H圈变换设Kp对应矩阵为A，则 e12 e13e1ie1i+1 e1je1j+1 e1pei-1i eii+1 eijeij+1 eip ei+1i+2ei+1jei+1j+1 ei+1pA = ej-1j ejj+1ejp ej+1j+2 ej+1pep-1p1 在A上，用非对角线上元素e i j e i +1 j+1 （i=1 2p-2，j=3 4p）替换对角线上元素e i i +1 e j j +1是一个二元H圈变换(替换元素下打点，被替换元素下划横线，以下同)。设变换后新矩阵为B，则B对角线上元素构成的H圈就是变换后的新H圈。2 在A上，用非对角线上元素e 1 i+1 e i p （i=2 3p-2）替换对角线上元素e 1 p e i i+1也是一个二元H圈变换。设变换后新矩阵为C，则C对角线上元素构成的H圈就是变换后的新H圈。 由A变成B记为AB，由A变成C记为AC，它们都统称为图G的二元H圈变换。由AB具体这样进行：将A的矩形块e1 i+1 ei i+1 ei j e1j列序颠倒，矩形块e i+1 j+1 ej j+1 ej p ei+1 p行序颠倒，三角块e i+1 i+2 ej-1 j ei+1 j的元素作关于斜边高的对称调换，其他元素不动，得矩阵B。由AC具体这样进行：将A的矩形块e1 i+1 ei i+1 e i p e1p列序颠倒，三角块e i+1 i+2 ep-1 p ei+1 p作关于斜边高的对称调换，其他元素不动，得矩阵C。这种矩阵上的二元H圈变换具有如下性质：性质1 在图对应的矩阵上进行二元H圈变换时，矩阵对角线上未被替换的元素，经过变换后，仍在对角线上。性质2 图的二元H圈变换可以在图对应的矩阵上连续进行，变换一次得一个新矩阵，对角线上得一个新H圈，新矩阵与新H圈一一对应。性质3 图对应矩阵中有X元素，X元素也可以进行H圈变换，X元与非X元一样对待。以上性质明显成立。性质4 若图G有H圈，则它的任一个H圈都可以变换到矩阵的对角线上。性质5 图的任一个m元H圈变换（m3）都可以在图对应的矩阵上连续用不超过m个二元H圈变换实现。四 基本H圈变换图的三元及三元以上的H圈变换与二元H圈变换一样，可以在图对应的矩阵上进行，也有类似性质，但都比较复杂。三元及三元以上的H圈变换，一般采用以下方法进行：先找出变换后所得的新H圈，再写出新H圈对应的矩阵，即为变换后所得新矩阵。图的m（m3）元H圈变换虽然复杂，但大多数m元H圈变换是由几个低元H圈变换合成的。例如K7中用e14 e57 e37 e26 e16替换H圈1-2-3-4-5-6-7-1中的e12 e34 e56 e67 e17 是一个五元H圈变换，但它是由一个二元H圈变换（用e16 e57 替换H圈1-2-3-4-5-6-7-1中的e56 e17 ）和一个三元H圈变换（用e14 e 26 e 37 替换H圈1-2-3-4-5-6-7-1中的e12 e 34 e 67）合成的。我们称这种H圈变换是合成的H圈变换，否则称为是基本的H圈变换。一个H圈变换如能分解成几个低元的H圈变换，则这个H圈变换是合成的，否则是基本的H圈变换。显然二、三元H圈变换都是基本H圈变换。进一步研究发现：对m元（m3）H圈变换，当m较大时，大部分m元H圈变换是合成的，而基本H圈变换随着m的增大急剧减少。五 H图若图G含有H圈，则称G是一个Hamilton图，简称H图。若图G对应矩阵的对角线上无X元，则G是一个H图。一个图是否是H图，到目前为止还没有一个好的判别方法。这里仅从H圈变换考虑这个问题。定理 G是H图的充要条件是G对应的矩阵经过若干次H圈变换后，对角线上无X元。证明 若G是H图，则G至少有一个H圈。由H圈变换性质，通过H圈变换可以把此H圈变换到矩阵的对角线上，即经过若干次H圈变换后，矩阵对角线上无X元。 3），在图对应的矩阵上检查也有规律，也很方便。这样图G的H圈1-2-3-P-1为最优H圈的必要条件是不等式组（）（）同时成立。同理作m（m4）元H圈变换，还可以得到更强的必要条件。3 基本不等式及最优H圈的充要条件 基本不等式设H圈1-2-3-P-1是图G的最优H圈，若用不在此H圈上的m（m3）条边 e r1r2 e r2 r3 e rmrm+1 替换最优H圈上的m条边ei i+1 ej j+1 e k k+1 是一个m元H圈变换,则同理有不等式: ei i+1 +ej j+1 +e k k+1 e r1r2 +e r2 r3 + +e rmrm+1 ()成立。若此m元H圈变换是基本H圈变换，则称此不等式()是此m元H圈变换所对应的m元基本不等式。否则此不等式是多余的，这是因为它可以由低元基本不等式相加得到。显然（）（）都是基本不等式。 最优H圈的充要条件定理四 图G的H圈1-2-3-P-1（记为Q*）为最优H圈的充要条件是所有m（m=2 3p）元基本不等式成立。证明 上述已证明。 e* ( 其中当ij=p 时， i+1 j+1看成1)，则此二元H圈变换可使矩阵A对角线上元素（除e*）构成的H通路更优； 同样，若用非对角线上元素e r1r2 e s1s2 e t1t2 替换对角线上元素 ei i+1 ej j+1 ek k+1是一个三元H圈变换，当e r1r2 et1 t2 ，e s1s2et1 t2 时，且满足不等式：（ei i+1 +ej j+1 + e k k+1）( e r1r2+ e s1s2) e* (其中当ij k=p时，i+1 j+1 k+1看成是1)，则此三元H圈变换也可使矩阵A对角线上元素（除e*）构成的H通路更优。同样还有很多类似的不等式，我们把这些不等式的相反不等式，统称为图G（或矩阵A）的最优H通路不等式。这些不等式在矩阵上检查方便。进一步研究表明，若矩阵A（除e*）无更优的H圈变换，且所有的最优H通路不等式都成立，则矩阵A对角线上元素（除e*）就构成图G的最优H通路。3 设图G有H通路，如何求它的最优H通路？下面也介绍二种方法。方法一 用H圈变换求最优H通路 写出图G对应的矩阵A； 按变换差大小，从大到小对矩阵A进行一系列H圈变换，把非对角线上边权和最小的元素变换到对角线上，同时把对角线上边权和大的元素调出，直到没有更优的H圈变换，最后得矩阵B； 用最优H通路不等式，对矩阵B进行检查。若矩阵B对角线上无X元，最优H通路不等式都成立，则矩阵B对角线上元素（除e*）就构成图G的最优H通路；若最优H通路不等式中的某一个不等式不成立，则作相应的H圈变换得矩阵C。检查矩阵C（除e*）是否有更优的H圈变换，若有则变换，若无则与矩阵B一样，用最优H通路不等式检查矩阵C。通过检查、变换、再检查，最后可求得图G的最优H通路。若对角线上有X元，则把所有X元都看成是同一个很大的数，与无X元一样进行计算。方法二 用舍补法求最优H通路 写出图G对应的矩阵A 与用舍补法求G的最优H圈一样进行，只要把最后一个舍补不做，改为舍去所在行列的二个（每行列一个）最大被选元素。 若剩下的（P-1）个被选元构成H通路，则此H通路就是G的一条较优H通路；若不构成H通路，则调整最后二个被舍去的元素，也同样可得G的较优H通路。 把所得H通路两端联起来，得一个H圈。写出此H圈对应的矩阵B，与方法一中的矩阵B一样检查、变换、再检查，最后可求得G的最优H通路。下面看一个例题：例5 已知K7的边权如下，求K7的最优H通路。eij j i 2 3 4 5 6 7123456 10 20 3 6 9 44 2 3 6 8 7 9 14 9 1 8 10 5 1 2解 下面用两种方法求解方法一 用H圈变换求最优H通路写出K7对应的矩阵A，对A进行二元H圈变换得矩阵B： 对矩阵B检查知：矩阵B对角线上元素构成K7的最优H圈。用最优H通路不等式检查，发现 所以作二元H圈变换（用替换）得矩阵C。再检查C发现，所以作三元H圈变换（用 替换 ）得矩阵D。检查D，发现有更优的H圈变换（用替换）得矩阵E。检查E，除e*(20)无更优的H圈变换，最优H通路不等式都成立，所以矩阵E对角线上元素（除e*(20)）构成K7的最优H通路。这些元素是e23(4) e26(6) e67(2) e57(1) e45(1) e14(3) ，它们构成的H通路为3-2-6-7-5-4-1。所以K7的最优H通路为3-2-6-7-5-4-1，其路长W=17。方法二 用舍补法求最优H通路写出K7对应的矩阵A，每行列选二个最小元素，按舍补差大小，由大到小，舍去e25(3)，再舍去e24(2) e56(5)补回e26(6)。最后一个舍补不做，直接舍去所在行列两个最大被选元 ，最后剩下6个被选元：，它们恰好构成H通路3-2-6-7-5-4-1。联此H通路两端点1、3，得H圈1-3-2-6-7-5-4-1。它们对应的矩阵恰好是方法一中的矩阵E。与方法一一样检查，知H通路3-2-6-7-5-4-1为K7的最优H通路，其路长W=17。另外，最大H通路在实践中也有应用。如何求最大H通路？求最大H通路与求最优H通路的思路和方法都是一样的，但计算时，要把大改小，小改大。具体如何计算在此就不累赘了。十 最优单向H通路（一）竞赛图的矩阵表示及最优单向H通路 设图G是简单有向连通图（即有向完全图，也称竞赛图，以下都讨论这种图），其顶点用1 2 P 标定后，i与j两顶点之间的边权用表示，当方向为时就用表示，当方向为时，则用表示。这样一个竞赛图就可以用一个上三角形矩阵表示，且一个竞赛图就对应一个矩阵。如图三对应矩阵为： 图 三连接图G中几个顶点的路称为通路。如果通路是单向的，称为单向通路。连接所有顶点的单向通路，称为Hamilton单向通路，简称为单向H通路。（以下通路、单向通路、单向H通路、单向H圈分别用W 表示，请注意与向量的区别）。边权和最小的称为最优。一个竞赛图是否有，1934年Redei已证明：一个竞赛图必有。但如何求最优， 到目前为止还没有一个有效的计算方法，而在实践中（如排序问题等）又经常要用到。下面介绍一个有效而实用的方法。（二） 变换设G是p个顶点的竞赛图，对应矩阵为A，对角线上元素（除）已构成。则：1在矩阵A中，若 构成， 也构成（当j=p时只要求 构成）；则用替换对角线上的元素 后，对角线上元素构成一条新的。设新的对应矩阵为B（实际是此把两端连接所得H圈对应的矩阵）则把A变换成B称为图G的变换(I)，记为。具体如下进行：在A中，三角块(1)不动，将矩形块(1)(2)位置对换，三角块(2)(3)位置对换，矩形块(3)转置，得矩阵B。2. 同样在矩阵A中，若 构成， 也构成（当i=1时，只要求 构成），则用 替换对角线上的元素 （都是所在行列对角线上元素，以上也同）后，对角线上元素也构成一条新的。设新的对应矩阵为C，则把A变换成C称为图G的变换()，记为。具体如下进行：在A中，将三角块(1)(2)位置对换，矩形块(1)转置，矩形块(2)(3)位置对换，三角块(3)不动，得矩阵C。变换()与变换()是对称的。以上两种变换看上去都是二元变换，实际上都是三元H圈变换，只是把通路两端连接的边省去没有考虑。二元H圈变换除个别外都不能成为变换。但大多数三元H圈变换都可能成为三元变换，因此应该熟悉三元H圈变换。特别是这些元素()作三元H圈变换，都可能成为变换。变换首先必须是H圈变换，三元或三元以上的H圈变换能否成为相对应的变换，只要检查被替换后对角线上元素的脚码是否能构成一条。若能构成，则此H圈变换就是变换。写出新对应的矩阵，即为变换后所得新矩阵。（三）求最优 如何求赋权竞赛图G的最优？可按以下步骤进行。 1. 写出图G对应的矩阵A 2. 在A上找一条初始（从矩阵A左上方开始，元素脚码追踪，左右相联，边追边记，不重复；不全就反向追踪没有出现的脚码；还不全就修正路线，直到全部脚码出现，即可得一。）并写出此对应的矩阵B，而此就在矩阵B的对角线上。 3. 对矩阵B进行一系列变换，（变换时矩阵上面同时写出与矩阵对应，也与矩阵最上行列元素对应的，有利于检查元素脚码和），把边权和小的元素调到对角线上，同时把对角线上边权和大的元素调出，按变换差（被替换元与替换元边权和之差）大小，从大到小逐个进行。若中途遇对角线上元素构成，则去掉对角线上最大元素，得一新的， 并写出此所对应的矩阵，继续进行变化。变换一次矩阵对角线上元素（除右上角元素）边权和减少一次，直到不能减少为止，得最后矩阵。（注意从不同的初始进行，结果可能不一样，所以中途应选几个不同的变换进行，比较每次结果。选取最优者。）这时最后矩阵对角线上元素（除右上角元素）构成的虽然不能肯定是最优， 但一定是较优。 4. 最后矩阵对角线上元素构成的是否是最优，与检查最优H圈一样，充分简化最后所得矩阵。若简化后的矩阵对角线上元素（除右上角元素都，而非对角线上元素都，则最后矩阵对角线上元素构成的（即矩阵上的）是最优。若最后矩阵对角线元素构成，则还应该用最优H通路不等式检查。否则在简化后的矩阵上再寻找更优的三元及三元以上的变换，直到得出最优为止。下面看一个实例。例6 （排序问题）有一台数控机床必须加工九种不同零件。加工零件后，再加工零件，中间需有间歇时间（要调整设备夹具、准备刀具、编写程序等），设间歇时间为（表示加工零件后再加工零件中间所需间歇时间，时，取时间短的，时间长的舍去）各零件加工转换具体间歇时间见下表（单位：小时），问怎样安排加工顺序，使总间歇时间最短？tij BjBi 解：以表示顶点i，表示边权，则加工不同零件之间的间歇时间和顺序可用一个竞赛图G表示(G不必划出)，这样本问题就转化为求竞赛图G的最优。具体这样进行：写出图G对应的矩阵A(见下面)；在矩阵A中找到再反向找到，这些元素构成初始,写出此所对应的矩阵B； 73 1 2 4 5 6 8 9= 检查B（从小元素开始，下同）：构成，也构成（这些元素的脚码和都由矩阵上面的确定，下同）所以用替换对角线上元素作变换()得矩阵C； 73 1 2 5 6 8 9 4 25 6 8 7 3 1 9 4检查C：构成，也构成，所以用替换对角线上元素作变换()，得矩阵D；检查D：知道用替换对角线上的是三元H圈变换，且对角线上元素的脚码25, 56, 68, 87, 73, 31, 19, 94中的56, 73, 31被替换元素的脚码53, 36, 71替换后，对角线上元素脚码为25, 53, 36, 68, 87, 71, 19, 94，它们构成一条：，写出此对应的矩阵E；检查矩阵E没有找到更优变换。对矩阵E充分简化得矩阵F。25 3 6 8 7 1 9 4 矩阵F对角线上的元素（除右上角）都，而非对角线上元素都，所以矩阵E对角线上元素（除右上角）构成图G的最优（即矩阵E上面的），因此图G的最优为。故最优加工顺序为。总间歇时间为17小时。十一 竞赛图的最优1、关于一个竞赛图一定有，但不一定有，一个竞赛图是否有，各书有不同论述，但最明显的是：若一个竞赛图某顶点的出度（或入度）为零，则此竞赛图一定没有，这是因为从这点起出不去（或回不来）。除了这种特殊情况，一般情况下竞赛图都有。2、变换设D是有的竞赛图，是D的一个，若用非上的m（2mp）条边，替换上的m条边，可以得到一个新的，这一过程称为图D的一个变换。设竞赛图D有，其对应的矩阵为A（也就是此H圈对应的矩阵）。在A上：用(1，4)替换对角线上的是一个三元H圈变换，若满足：A. 构成，B. 构成 C. 构成，则此三元H圈变换是一个三元变换。此三元变换实际上是变换(I)(II)，像变换一样，可以在矩阵上进行。用 当时，看成1，下同替换对角线上元素是三元H圈变换，若满足：A. 构成，B.构成，则此三元H圈变换是三元变换。用替换对角线上元素是三元H圈变换，若满足A.构成，B构成，则此三元H圈变换是三元变换。用(当,看成1)替换对角线上元素是三元H圈变换，若构成，则此三元H圈变换是三元变换。变换首先必须是H圈变换，二元H圈变换都不是变换，以上所列四种三元H圈变换，若满足所列条件，则都是变换。四元及四元以上的H圈变换是否是变换，只要看变换后元素脚码是否构成，若构成，则此H圈变换就是变换，写出新对应的矩阵，就完成了变换。3、如何求竞赛图的最优设D是有的赋权竞赛图。D中边权和最小的，称为D的最优。因为求最优H圈到目前为止都没有有效的计算方法，所以求最优就更没有好方法。下面用变换可比较有效地解决这一难题，具体如下进行（与求最优类似）写出对应矩阵A；在矩阵A上用追踪法找一初始，并写出此对应的矩阵B（在矩阵上同时写出此）；从矩阵B开始，做一系列调优变换，把边权和小的元素调到对角线上。按变换差大小，从大到小一次一次变换。变换一次，对角线上元素边权和减一次，直到不能减少为止。再从不同的初始进行，比较每次结果，选取最优者。每次变换可这样进行：在矩阵上先找出新的更优变换，写出新，再写出新对应的矩阵，即为变换后所得新矩阵。这样变换比利用矩阵变换更适用更好记忆，有一般性。最后所得矩阵对角线上元素构成的虽然不能肯定是最优的，但一定是较优。最后矩阵对角线上元素构成的是否是最优的，利用充分定理，与最优H圈一样检查。经过检查，变换、检查最后可以得到较理想结果。例7某汽车配件厂有一台设备必须加工一批不同零件，加工完这批零件后，再回到初始状态准备加工下一批同样的零件，生产轮回转。已知加工零件后，再加工零件，中间调整设备所需时间为(若舍去)，具体时间见下表(单元:小时)。问如何安排这批零件的加工顺序，加工完后调整设备回到初始状态，使一个生产轮回总的调整设备时间最短？tij2 3 4 5 6 7 8 912345678BjBi解：以为顶点，为边权得一竞赛图D。求一个加工顺序，使一个生产轮回总的调整设备时间最短，即要求图D的最优(与求最优不同的是加工完这批零件后，还要调整设备，回到初始状态)。具体如下进行：写出竞赛图D对应矩阵A；在A上找到初始并写出对应矩阵B。 1256473981 1234567891 1253647981 检查B发现用，替换对角线上元素，是更优的三元变换，变换后得新:，对应矩阵为C；BS=54CS=45 检查C发现用 替换对角线上元素是更优的三元变换，变换后得新:，对应矩阵为D；检查D发现用 替换对角线上元素是更优的三元变换，变换后得:，对应矩阵为E；检查E发现用替换162534798 1362594781 162539478 FS=29ES=39DS=41 对角线上元素是更优三元变换，变换后得新:1362594781，对应矩阵为F；检查F发现用替换对角线上元素是更优三元变换，变换后得新:1362759481对应矩阵为H；检查矩阵H无更优的变换。充分简化矩阵H，得矩阵J，矩阵J对角线上元素都0，而非对角线上元素都0，1362759481 JHS=15 所以矩阵H对角线上元素构成图D的最优，即矩阵H上面的:1362759481。故最优加工顺序为B1B3B6B2B7B5B9B4B8B1。一个生产轮回总的调整设备时间为15小时。十二 双向竞赛图的及（一）双向竞赛图有向图D称为双向竞赛图当且仅当D的任意两顶点，之间有且仅有两条互为反向的边。当方向为时，边权用表示，当方向为时，边权用表示。D的边权用两个数表示为()。这样一个双向竞赛图也可以用一个上三角形矩阵表示。这个矩阵就称为图D所对应的矩阵，其元素为。很明显双向竞赛图都有。（二）如何求双向竞赛图的最优、设D是一个赋权的双向竞赛图，如何求D的最优、，到目前为止还没有一个有效的计算方法，而在实践中又常有应用。其实求双向竞赛图的最优、比求竞赛图的最优、更容易，这是因为在作、变换时，选择的机会更多，更灵活，且初始、在图D对应矩阵的对角线上是现成的。(特别当二元H圈变换满足,构成,构成，或者构成，构成，则用替换或者用替换都可成二元、变换。此变换在矩阵上与二元H圈变换一样进行，只是变换时对角线上部分元素反向)。具体求法如下：1、求双向竞赛图的最优求双向竞赛图的最优与求竞赛图的最优类似，具体这样进行。写出双向竞赛图D对应矩阵A；在矩阵A的对角线上，有现成的初始:123P，同时在矩阵A的上面写出此。从矩阵A开始，进行一系列调优变换（一般先作二元H圈变换）。把边权和小的元素调到对角线上，直到没有更优的变换为止。再从不同的初始，进行变换，得到不同结果，选取最优者。最后所得矩阵对角线上元素（除右上角元素）构成的(即矩阵上面的)是否是最优的，与求竞赛图最优一样，进行检查，变换，检查，便可得到较理想结果。1 2 3 4 5 6 71234567例8一台设备必须加工7种不同的零件B1B2B7，加工零件Bi后再加上零件，中间需要调整设备，设调整设备时间为()具体时间见右表(单位：小时)。问如何安排这批零件的加工顺序，使总的调整设备时间最短？解：以为顶点，为边权，得双向竞赛图D，求最优排序即求双向竞赛图D的最优。具体如下进行：写出双向竞赛图D对应矩阵A；在矩阵A的对角线上有初始：1237并把此写到矩阵A的上边，与第一行列元素对齐(下同)；从矩阵A开始作下列调优变换，检查矩阵A，因为构成，也构成，所以用替换对角线上元素，作变换(I)，得矩阵，检查矩阵，因为构成，也构成，所以用替换对角线上元素，作变换(II)得矩阵C；检查矩阵C，因为构成，也构成，所用替换对角线上元素1234567 1267345 6731245 CW=14BW=23W=32，作变换(I)，得矩阵D；检查矩阵D，发现对角线上元素构成，去掉对角线上最大元素(或)得:2453671，其对应矩阵为E；检查矩阵E，无更优的变换，化简矩阵E得短阵F；检查矩阵F，对角线上元素(指的元素)都0，而非对角线上元素都0，所以矩阵E对角线上元素构成双向竞赛图D的最优，最优为2453671，2453671 2453671 6712453 FEDD 故这批零件最优加工顺序为B2B4B5B3B