化工系统工程基础：2-3 不可分割子系统的切割

1、12 过程系统模拟的序贯模块法过程系统模拟的序贯模块法2.1 序贯模块法的基本原理序贯模块法的基本原理2.2 不可分割子系统的识别不可分割子系统的识别2.3 不可分割子系统的切割不可分割子系统的切割2.4 切割物流变量的收敛切割物流变量的收敛（常用数学方法）（常用数学方法）2.5 序贯模块法的应用举例序贯模块法的应用举例22.3 不可分割子系统的切割不可分割子系统的切割系统分析的基本步骤：系统分析的基本步骤：1）子系统识别：）子系统识别：将整个系统分隔成若干个相互不存在循环回路的独将整个系统分隔成若干个相互不存在循环回路的独立子系统，并确定各子系统的计算顺序。立子系统，并确定各子系统的计算顺序

2、。大系统大系统各级子系统，大型方程组各级子系统，大型方程组需同时求解的方程式需同时求解的方程式2）子系统切割：）子系统切割：对包含循环回路的子系统，确定需要事先假定的物对包含循环回路的子系统，确定需要事先假定的物流参数，确定合理的求解顺序。流参数，确定合理的求解顺序。3）组合各子系统，求解整个大系统）组合各子系统，求解整个大系统按大系统特性，将各个子系统的求解有机地结合起来，实现整个按大系统特性，将各个子系统的求解有机地结合起来，实现整个系统的优化目标系统的优化目标3n 选择选择切割切割回路上的循环流线，即给被选择的物流变量赋以回路上的循环流线，即给被选择的物流变量赋以假定值，实现回路中各单元

3、的序贯求解。假定值，实现回路中各单元的序贯求解。n 不可分割子系统的切割不可分割子系统的切割：通过选择若干切割流线，使子系：通过选择若干切割流线，使子系统中包含的所有简单回路均被切断。统中包含的所有简单回路均被切断。切割方案：通常是多解的。切割方案：通常是多解的。识别方案：唯一的。识别方案：唯一的。4不可分割子系统的切割问题是寻找不可分割子系统的切割问题是寻找最优切割集最优切割集的的优化问题优化问题。切割判据切割判据： 切割流线数量最少。切割流线数量最少。 切割流线的物流变量总数最少。切割流线的物流变量总数最少。 出于某种考虑，对各流线进行加权后，切割流线的加权出于某种考虑，对各流线进行加权后

4、，切割流线的加权和最小。权重的大小可以反映切割流线将引起的迭代收和最小。权重的大小可以反映切割流线将引起的迭代收敛的困难程度。敛的困难程度。 切割简单回路的总数最少。尽量避免一个简单回路多次切割简单回路的总数最少。尽量避免一个简单回路多次被切割，每个简单回路被切割一次最好。被切割，每个简单回路被切割一次最好。5n在信息流图上，在信息流图上，简单回路简单回路指的是从某一节点出发，沿流线指的是从某一节点出发，沿流线方向逐次通过不同的节点和流线，再回到原出发节点所形方向逐次通过不同的节点和流线，再回到原出发节点所形成的单向环路。成的单向环路。回路矩阵回路矩阵 系统共包括系统共包括 m 个简单回路，个

5、简单回路，n 条流线。条流线。 表示简单回路表示简单回路 i 中包含流线中包含流线 j； 表示简单回路表示简单回路 i 中不包含流线中不包含流线 j 。 nmijaA 1 ija0 ija6 36151421ssssssss简单回路：简单回路：回路中任一单元只经回路中任一单元只经过一次。过一次。L1 = 1，2，5L2 = 1，2，3，4L3 = 3，6回路矩阵回路矩阵s1 = L1，L2s2 = L1，L2s3 = L2，L3s4 = L2s5 = L1s6 = L27流线流线( (列列) )的集合：的集合： Ri 中各流线共同构成简单回路中各流线共同构成简单回路 Li回路回路( (行行)

6、)的集合：的集合： Cj 中的简单回路都含有流线中的简单回路都含有流线 Sj 流线流线 Sj 覆盖覆盖（cover）了集合了集合Cj中各回路中各回路( (行行) ) 只要找到一个流线只要找到一个流线( (列列) )集合，它能覆盖回路矩阵集合，它能覆盖回路矩阵A中的所中的所有回路有回路( (行行)可行切割集可行切割集 1 ijjiaSR 1 ijijaLC回路矩阵回路矩阵8对于回路对于回路 i ，至少存在，至少存在一项一项 aij 与与 xj 同时为同时为1，即：回路即：回路 i 必然被断开。必然被断开。1 基本切割法（基本切割法（ Basic Tearing Algorithm，BTA ）19

7、73年，年，T.K.Pho & L.Lapidus，把优化理论应用于切割集的选择，把优化理论应用于切割集的选择以以切割原则切割原则为判据为判据最小加权和判据最小加权和判据 jjjjjjjNjijNjjjssxssPNjxMixatsxsP 0 1 )( , 2 , 1 1or 0 , 2 , 1 1 .)( min 11不不切切割割流流线线切切割割流流线线的的权权值值流流线线其其中中：求取切割流线的加权和最小求取切割流线的加权和最小整数规划中的特殊问题整数规划中的特殊问题 “01规划规划”92 回路切割法（回路切割法（ Loop matrix method ）1966年，年，W.Lee

8、 & D.F.Rudd原则：切割流线数最少原则：切割流线数最少10 1 2 3 4 5 6 1 1 1 1 2 1 1 1 1 3 1 1 S1 S2 S3 S4 S5 S6 （2）找出只含一个非）找出只含一个非0元素的行，把其非元素的行，把其非0元素对应的列确定元素对应的列确定为切割流线，并从矩阵中为切割流线，并从矩阵中删去删去该列，及其非该列，及其非0元素对应的行。元素对应的行。（3）重复（）重复（1）（）（2），直至零矩阵。），直至零矩阵。（1）删去回路矩阵中不独立的列）删去回路矩阵中不独立的列 若：若： ，则，则 不独立，删去不独立，删去jkss ks 36252421ssss

9、ssss11回路矩阵法存在的问题：回路矩阵法存在的问题：如果再循环单元组十分庞大，应用回路矩阵法存在困难。如果再循环单元组十分庞大，应用回路矩阵法存在困难。1982年，年，Gundersen的研究实例：一个重水厂的研究实例：一个重水厂109 个过程单元个过程单元163 条流线条流线13746 个简单回路个简单回路回路矩阵回路矩阵 13746163，需要，需要 2.24 M 内存单元内存单元123 先导表法（先导表法（precursor list method）1972年，年，R.W.barkley & P.L.Motard原则：切割流线数量最少原则：切割流线数量最少ADBEC12345

10、67817654328信息流图信息流图信号流图信号流图（1）简化先导表：当某节点只有一个先导节点时，用先）简化先导表：当某节点只有一个先导节点时，用先导节点代替该节点，并将该节点从先导表中剔除；导节点代替该节点，并将该节点从先导表中剔除；（2）选择含有自环的流线作为切割流线；）选择含有自环的流线作为切割流线；（3）重复（）重复（1）（）（2）。）。13切割步骤：切割步骤：节点 (流线) 先导 1 1 4 4 1 7 5 1 4 7 5 7 节 点(流 线 )先 导11 44151 4节点(流线)先导1151节点 (流线) 先导 1 1 7(6,8)切割切割71(4)1(5)切割切割1STOP1

11、(2,3)ADBEC12345678先先化简化简，再利用回路搜索法，再利用回路搜索法14ABCDEFGHIJ15ABCDEFGHIJ1234567891011121316ABCDEFGHIJ1234567891011121317ABCDEFGHIJ12345678910111213184 动态规划法动态规划法原则：切割流线的变量数最少原则：切割流线的变量数最少基本思路：动态规划的思想，是将一个整体的、难解决的问题化基本思路：动态规划的思想，是将一个整体的、难解决的问题化为一系列基本性质相同，但比较容易求解的单一问题。为一系列基本性质相同，但比较容易求解的单一问题。任何一个过程系统都有两个极限状

12、态：任何一个过程系统都有两个极限状态：n初始状态初始状态，对应于未经切割的原始系统，对应于未经切割的原始系统n终止状态终止状态，对应于已经切断所有回路的系统，对应于已经切断所有回路的系统在初始状态和终止状态之间，有很多中间状态，它们对应于切断在初始状态和终止状态之间，有很多中间状态，它们对应于切断不同回路的组合。不同回路的组合。19例：例： 流线上括号内的数字流线上括号内的数字 表示该流线的变量数表示该流线的变量数P。 2 4 3 3 2 9 2 1 0 0 0 1 1 00 1 0 0 1 1 10 0 1 0 0 1 10 0 0 1 0 1 0 7654321P DCBASSSSSSS物

13、流变量物流变量 解：解：（1）识别简单回路：）识别简单回路：4个。个。 构造回路矩阵。构造回路矩阵。20（2）确定回路切断可能存在的方案。）确定回路切断可能存在的方案。初始状态：无回路被切断的状态，状态号为初始状态：无回路被切断的状态，状态号为0；终止状态：所有终止状态：所有4个回路均被切断的状态，状态号为个回路均被切断的状态，状态号为15；中间状态：中间状态：14个，分别包括不同的切断状态，个，分别包括不同的切断状态， 切断一个回路（状态号切断一个回路（状态号1，2，4，8） 切断两个回路（状态号切断两个回路（状态号3，5，6，9，10，12） 切断三个回路（状态号切断三个回路（状态号7，1

14、1，13，14）。）。状态号状态号 切断回路切断回路 状态号状态号 切断回路切断回路 状态号状态号 切断回路切断回路 状态号状态号 切断回路切断回路0 0无无4 4C C8 8D D1212C,DC,D1 1A A5 5A,CA,C9 9A,DA,D1313A,C,DA,C,D2 2B B6 6B,CB,C1010B,DB,D1414B,C,DB,C,D3 3A,BA,B7 7A,B,CA,B,C1111A,B,DA,B,D1515A,B,C,DA,B,C,D21（3）作状态图）作状态图初始状态经一次切断可达的中间状态或最终状态初始状态经一次切断可达的中间状态或最终状态 22最优切割方案是：最

15、优切割方案是：S1，S4和和S7。 全部切断物流的方案全部切断物流的方案23动态规划法的步骤动态规划法的步骤n递推公式递推公式 lBqEpEpqql Min所有状态所有状态所有流股所有流股 状态数状态数、的成本的成本流股流股状态时的最优成本状态时的最优成本状态时的最优成本状态时的最优成本 qpllBqqEppE LqMpM 合集符号合集符号的一个流股集合的一个流股集合含有流股含有流股时最优切断流股集合时最优切断流股集合状态状态时最优切断流股集合时最优切断流股集合状态状态 lLqqMppM初始条件：初始条件： 000ME245 信息网络分解的可及向量法孙登文法信息网络分解的可及向量法孙登文法原理

16、：借鉴原理：借鉴1985年周理提出的网络分解法，将每个节点按节点度递降排列，年周理提出的网络分解法，将每个节点按节点度递降排列，引入可及向量和局部相邻矩阵概念，判断节点间是否有通路及回路，并确引入可及向量和局部相邻矩阵概念，判断节点间是否有通路及回路，并确定切割流线和节点计算序列。定切割流线和节点计算序列。优点：数学概念明确，步骤简洁，易于编程实现。优点：数学概念明确，步骤简洁，易于编程实现。特点：无需将流程的分解分为两个层次，此方法直接对整个流程的信息流图特点：无需将流程的分解分为两个层次，此方法直接对整个流程的信息流图（用相邻矩阵）进行处理，从所有流线中识别出应予以切割的流线，并排（用相邻

17、矩阵）进行处理，从所有流线中识别出应予以切割的流线，并排出对各个单元进行求解的顺序。对于流线有权、无权问题，均可以解决。出对各个单元进行求解的顺序。对于流线有权、无权问题，均可以解决。25n 基本概念基本概念（1）节点度）节点度 dd+d-ACBD451236流出流出某节点流线数目某节点流线数目相邻矩阵相邻矩阵行行和和流入流入某节点流线数目某节点流线数目相邻矩阵相邻矩阵列列和和节点初始序列：节点度节点初始序列：节点度递降递降 DCBA1001121220101210011010010010dddDCBAdDCBA26（2）逆线，逆线区间）逆线，逆线区间逆线：初始序列中，节点指向节点度逆线：初始

18、序列中，节点指向节点度递增递增方向的流线称为节点的逆线。方向的流线称为节点的逆线。逆线区间：逆线终点与始点之间的初始序列部分（包括终点与始点）。逆线区间：逆线终点与始点之间的初始序列部分（包括终点与始点）。其中所含节点个数其中所含节点个数k，称为逆线区间的，称为逆线区间的长度长度。（3）局部相邻矩阵）局部相邻矩阵 逆线区间节点流线构成子图逆线区间节点流线构成子图k阶相邻矩阵，阶相邻矩阵， 即：即：局部相邻矩阵局部相邻矩阵 P按节点度递降排列节点按节点度递降排列节点ACBD451236节点初始序列：节点度节点初始序列：节点度递降递降 DCBA27（4）可及向量）可及向量可及向量：可及向量： 其中

19、：其中：121 1,k-,iPVVii kjpvvljilklij, 1 )(11 单位行向量单位行向量时，时， )0 , 0 , 1( 00 Vi28例：例：节点初始序列节点初始序列A B C D E FBCDE 逆线区间逆线区间 k4可及向量：可及向量：0001000011000010EDCBEDCBP )0 , 0 , 0 , 1()1 , 1 , 0 , 0()0 , 0 , 1 , 0()0 , 0 , 0 , 1(2312010 PVVPVVPVVV29n 无权图举例无权图举例（christensen-Rudd图）图）初始相邻矩阵初始相邻矩阵H：ABCDE1101112221201

20、010110000201001100100200110ddddEDCBAdEDCBAH节点度：节点度：按节点度排列初始序列：按节点度排列初始序列：A E C B D30AECBD解：解：（1）E无逆线无逆线（2） （CE无逆线）无逆线） CA逆线逆线逆线区间：逆线区间：A E C，k3AEC 001000100P)1 , 0 , 0( )0 , 0 , 1(010 PVVV113v有回路有回路C A为切割流线为切割流线H中，将中，将a31 0ABCDE31继续：继续：（3） BC逆线逆线逆线区间：逆线区间：CB，k2 0100P)0 , 0( )0 , 1(010 PVVV012 v无回路无回

21、路区间序列调整为：区间序列调整为：B C初始节点序列变为：初始节点序列变为：A E B C DAECBDCB)0 , 1(10 VVVC B终点子序列终点子序列 始点子序列始点子序列AEBCD32继续：继续：（4）继续检查节点）继续检查节点B，B对对A，E无逆线无逆线（5） DE逆线逆线逆线区间：逆线区间：E B C D，k4 0001100001001010P)1 , 0 , 1 , 0( )0 , 0 , 0 , 1(010 PVVV114 v有回路有回路D E为切割流线为切割流线H中，将中，将a45 0EBCDAEBCD33继续：继续：（6）得到切割流线集：）得到切割流线集：C A，D

22、E节点计算序列：节点计算序列：A E B C D这一结果与用先导表法计算结果相同。这一结果与用先导表法计算结果相同。34方法步骤：方法步骤：a) 根据初始相邻矩阵计算各节点的节点度，按逆序构造节点初始序列。根据初始相邻矩阵计算各节点的节点度，按逆序构造节点初始序列。b) 初始序列第二个节点起，逐个检查节点与其前面节点间有无逆线。有逆线，初始序列第二个节点起，逐个检查节点与其前面节点间有无逆线。有逆线，按按c)、d)、e)处理；否则，继续检查至序列的最后一个节点。处理；否则，继续检查至序列的最后一个节点。c) 写出逆线区间对应的局部相邻矩阵。写出逆线区间对应的局部相邻矩阵。d) 递推计算可及向量

23、，并检查其最后一个元素的值。递推计算可及向量，并检查其最后一个元素的值。l 如果如果 ，那么由图论可及矩阵的性质知道，从逆线终点至始点有，那么由图论可及矩阵的性质知道，从逆线终点至始点有 i 步通路，也即逆线必属于一个由步通路，也即逆线必属于一个由 i+1条流线构成的回路。因此，此逆线条流线构成的回路。因此，此逆线为切割流线，并将初始相邻矩阵中该流线对应的元素改为为切割流线，并将初始相邻矩阵中该流线对应的元素改为0。l 如果如果 ，则继续计算可及向量，则继续计算可及向量 ，如果对于，如果对于 ，都，都有有 ，那么此逆线区间上不存在回路，转去步骤，那么此逆线区间上不存在回路，转去步骤e)。1 i

24、kv0 ikv1 iV1, 2 , 1 ki0 ikv35方法步骤：方法步骤：e)求和向量求和向量V：定义定义 ，其中，其中V的第的第j个元素个元素 。检查检查V的每一个元素的每一个元素Vj，按，按Vj1出现的先后顺序（从出现的先后顺序（从j1起），将起），将对应的节点排成一行，这是以逆线的终点为首、终点的输出对应的节点排成一行，这是以逆线的终点为首、终点的输出流线逐步可达的那些节点的序列，称为终点子序列。流线逐步可达的那些节点的序列，称为终点子序列。按按Vj 0出现的先后顺序，将对应的节点排成另一行，则称为始点出现的先后顺序，将对应的节点排成另一行，则称为始点子序列。把终点子序列接在始点子序

25、列之后，即可以把逆流子序列。把终点子序列接在始点子序列之后，即可以把逆流线转为顺流线，且不会产生新的逆线。线转为顺流线，且不会产生新的逆线。利用上述步骤把初始序列的节点全部检查并作相应处理以后，即得切利用上述步骤把初始序列的节点全部检查并作相应处理以后，即得切割流线集，同时也得到了节点计算序列。割流线集，同时也得到了节点计算序列。110 kVVVVijkijVV11V 36有权图方法步骤：有权图方法步骤：a) 按流线权输入系统的初始相邻矩阵，但按非零元素的个数计算节点的出度、入度及按流线权输入系统的初始相邻矩阵，但按非零元素的个数计算节点的出度、入度及节点度，按节点度递减构造节点初始序列。节点

26、度，按节点度递减构造节点初始序列。b) 初始序列第二个节点起，逐个检查节点与其前面节点间有无逆线。有逆线，按初始序列第二个节点起，逐个检查节点与其前面节点间有无逆线。有逆线，按c)、d)、e)处理；否则，继续检查至序列的最后一个节点。处理；否则，继续检查至序列的最后一个节点。c) 写出逆线区间对应的局部相邻矩阵写出逆线区间对应的局部相邻矩阵P。d) 递推计算可及向量，并检查其最后一个元素的值。递推计算可及向量，并检查其最后一个元素的值。如果如果 非零非零 ，那么此逆线区间存在回路，寻找权最小的有效切割流线。，那么此逆线区间存在回路，寻找权最小的有效切割流线。l 令令 （逆流线权）（逆流线权）l

27、 从局部相邻矩阵从局部相邻矩阵P的主对角线以上的非零元素中，寻找满足不等式的主对角线以上的非零元素中，寻找满足不等式 的最小的元素的最小的元素 ，令，令 （切割）。（切割）。u计算可及向量，如果存在计算可及向量，如果存在 非零非零 ，则说明仍有回路存在，则说明仍有回路存在， 对应的流线不宜对应的流线不宜切割，恢复切割，恢复 原来的值。原来的值。kipp minikv), 3 , 2 , 1, 2 , 1,( minkjkijippki ijp0 ijpikvijpijp37u若（若（k-1）个）个 均为零，那么切割均为零，那么切割 对应流线可断开区间全部回路，恢复对应流线可断开区间全部回路，恢复 原来的值，并令原来的值，并令 。u继续寻找满足上述不等式的非零元素，重复操作，直至元素继续寻找满足上述不等式的非零元素，重复操作，直至元素 ，执行，执行e)。l和和 对应的流线可能不是最初查出的逆线，须将逆线区间的节点重新排序，使对应的流线可能不是最初查出的逆线，须将逆线区间的节点重新排序，使得区间中除切割流线外不存在其它逆线。将得区间中除切割流线外不存在其它逆线。将 置置0，执行，执行e)。如果如果 均为零，直接转入均为零，直接转入e)。e)求和向量求和向量V：定义定义 ，其中，其中V的第的第j个元素个元素 。