流股断裂方法三动态规划分解法课件.ppt

1、 流股断裂方法三：动态规划分解法流股断裂方法三：动态规划分解法 w 该法运用了运筹学动态规划中的穷举法选择断裂流股方案的组合，使断裂流股中变量的总和达到最少。w 1 动态规划分解法的基本思想：由于中间状态很多，即备选方案很多，那一个好；得先把所有方案排出来比较，最后确定。比较的标准：往往是试差变量个数 问题的初态最大循环系统 中间态各种打开环路方案的组合 终态无环系统w 动态规划分解法的应用举例：动态规划分解法的应用举例：例：问题：此最大再循环网系统有4个单元，7个流股，4个环路。求：切断流股哪些流股使环路全打开，且总成本 最小。123456（2）（2）（2）7（3）（3）（9）（4）1 2

2、3 4w 解题步骤：（1）由工艺流图 信息流图 （2）作环路矩阵：环 1 2 3 4 5 6 7 A 0 1 0 1 0 0 0 B 1 1 0 0 1 0 0 C 1 1 1 0 0 1 0 D 0 1 1 0 0 0 1流股成本B（L）2 9 2 3 3 4 2 B（L）：第L个流股的断裂成本。123456（2）（2）（2）7（3）（3）（9）（4）1234DCBA（3）考查所有中间状态，并作出状态指数表格。据排列组合原理：初态：四个循环回路一个也打不开。终态：四个循环回路全打开。16244434241404CCCCC)!(!nmnmCnm初态中间态终态w 状态指数：状态指数1248打开一

3、个环路ABCD状态指数35691012打开两个环路A，BA，CB，CA，D B，DC，D状态指数7111314打开三个环路A，B，CA，B，DA，C，DB，C，D状态指数01234567裂开环路无ABABCACBCABC状态指数89101112131415裂开环路DADBDABDCDACDBCDABCDw 4 用动态规划法选择最优断裂集合：用动态规划法选择最优断裂集合：由初态变至状态1是打开1个环，且是打开环A，由信息流图可见，打开A环时即可切断流股（4）也可切段流股（2）。但切断流股（4）的成本最小放在状态（1）右上角。右下角标出该路径的断裂流股集合。（0）（1）（4）E（q）34初态断裂流

4、股号 断裂流股集合最小成本E（p）状态1q：前一状态的最优成本。P：后一状态的最优成本。123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA流股号成本12293243536472（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）435462764,5（5）4,67（9）4,75（6）（6）（7）（6）21（10）55,7（12）2 3（1）（6）（5）流股号成本12293243536472（3）123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA状态指数1248打开的环路ABCD显然，分别断裂（4）,（5）,（6）,（7）流股，即分别打

5、开A，B，C，D环达到（1）,（2）,（4）,（8）状态。（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）4354627 6 4,5（5）4,67（9）4,75（6）（6）（7）（6）21（10）55,7（12）2 3（1）（6）（5）流股号成本12293243536472（3）123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA状态指数35691012打开两个环的A，BA，CB，CA，D B，DC，D进一步，在此基础上，若在已断裂（4）号流股的基础上继续断裂（5）号流股，则使A，B环同时打开，实现第（3）状态。w 在已断（4）号流股基础上断（6），则A

6、，C环同时打开，实现状态（5）。（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）4354627 6 4,5（5）4,67（9）4,75（6）（6）（7）（6）21（10）55,7（12）2 3（1）（6）（5）流股号成本12293243536472（3）123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA（7）状态指数35691012打开两个环的A，BA，CB，CA，D B，DC，Dw 在已断（4）号基础上断（7），则A，D环同时打开，实现状态（9）。（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）4354627 6 4,5（5）4,

7、67（9）4,75（6）（6）（7）（6）21（10）55,7（12）2 3（1）（6）（5）流股号成本12293243536472（3）123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA（7）状态指数35691012打开两个环的A，BA，CB，CA，D B，DC，Dw 在已断（5）号基础上断（6）或在已断（6）号基础上断（5），都能B，C环同时打开，实现状态（6）。同时，仅断开（1）号流股也可将B，C环同时打开，实现状态（6）。（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）4354627 6 4,5（5）4,67（9）4,75（6）（6）（7）（6

8、）21（10）55,7（12）2 3（1）（6）（5）流股号成本12293243536472（3）123456（2）（2）（2）7（3）（3）（9）（2）1234DCBA（7）（0）（4）（5）（6）（7）（1）（2）（4）（8）3（3）（5）435462764,5（5）4,67（9）4,75（6）（6）（7）（6）21（10）55,7（12）23（1）（6）（5）（7）1,45（11）4,5,7 8（13）3,4 5（14）1,3 4（15）1,4,77（2）（4）（7）（3）最优结果为打开1，4，7号流股，而断裂成本为7。若仅断裂2号流股，其断裂成本为9。双层图断裂法：双层图断裂法：w 1

9、 适用：系统模型方程已确立，方程个数小于变量个数时，合理选择设计变量及求解顺序，以达到求解容易的目的。w 2 双层图 例：已知一组模型方程组：f1（V1，V2，V3）=0 f2（V3，V4，V5）=0 f3（V4，V5，V6）=0 f4（V7，V8，V2）=0 w 此方程组，变量个数 n=8，方程个数 m=4。自由度 f=n m。变量节点方程节点f1 f2 f3 f4V1 V2 V3 V4 V5 V 6 V 7 V8w2 双层图的制作：f1（V1，V2，V3）=0 f2（V3，V4，V5）=0 f3（V4，V5，V6）=0 f4（V7，V8，V2）=03 双层图分解法求解方程组的求解思路：例：

10、w f1（V1，V2，V3）=0 f2（V3，V4，V5）=0 f3（V5，V6，V1）=0 双层图：f1 f2 f3 V1 V2 V3 V4 V5 V6 自由度=m n=6 3=3 双层图分解法利用双层图选择设定变量（断裂流股）：方案一，选V1，V3，V5为设定变量，则余下未知变量为V2，V4，V6。对应关系：根据f1对应求解V2，根据f2对应求解V4，根据f3 对应求解V6。w 该方案使方程求解容易，但V1，V3，V5不能任意选定，它们之间还有相互制约。w 方案二，选V2，V4，V6为设定变量，双层图变为：V2，V4，V6之间无制约。但余下的方程和变量之间有交叉关系，无法分开，只能联立求解

11、。f1 f2 f3V2 V4 V6f1 f2 f3V1 V3 V5f1（V1，V2，V3）=0f2（V3，V4，V5）=0f3（V5，V6，V1）=0w 方案三，选方案三，选V1，V4，V6为设定变量为设定变量：则：此时，双层图形成开链。若用逆序求解，易于解出。4 Lee选择设计变量的准则：设定变量的选择应使设计方程得到一个开链结构。即，使联立求解的方程个数达到最少。f1 f2 f3V2 V3 V5f1（V1，V2，V3）=0f2（V3，V4，V5）=0f3（V5，V6，V1）=0w 5 Lee选择设计变量的方法：选择设计变量的方法：例：例：某化工过程如图示，每个流股涉及质量流量q和组成c两个

12、变量，反应器还涉及反应器体积v及反应温度T两个参数，分离器涉及分离比s参数 12345q1,c1q2,c2q3,c3q4,c4q5,c5混合反应分离通过物料衡算建立描述该过程的数学方程混合槽：f1 q1q5-q2=0 总物料衡算f2 q1c1q5c5-q2c2=0 组分物料衡算反应器：f3 q2-q3=0 总物料衡算f4 q2c2q3c3 R(c3,T,V)=0 组分物料衡算分离器：f5 q3q4 q5=0 总物料衡算f6 q3c3q4c4 q5c5=0 组分物料衡算f7 S=c5/c4 分离比12345q1,c1q2,c2q3,c3q4,c4q5,c5混合反应分离共有独立方程数m=7，独立变

13、量数 n=13自由度=13-7=6w 该问题涉及方程m=7，变量n=13，自由度f=6，也就是设设计变量为计变量为6个。个。w 该问题的双层图如下：f7f1f2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSf1 q1q5-q2=0f7f1f2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSf2 q1c1q5c5-q2c2=0f7f1f2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSf3 q2-q3=0f7f1f2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSf4 q2c2q3c3 R(c3,T,V)=0选择设计变量的步骤如下：w 步

14、骤一：寻找具有一个局部度的节点（即只有一条连线的节点），如图中的 c1、V、S，T这几个节点。由于V，T两个节点同属f4，只能选择其中一个。所以第一步选出了c1、V、S，并将它们及与它们相关的方程f2、f4、f7,从双层图中去掉。f7f1f2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSf1f3f5f6q1q4c2q2c3q3c4c5q5Tw步骤二：将所选定的设计变量节点及与这些设计变量相关的方程节点从双层图中去掉。经过步骤二得到下图：由图可以看到，其中的节点c2，T与其他节点无关，称为局部度为零的节点，将所有局部度为零的节点选为设计变量。至此c2，T被选为设计变量。f7f1f

15、2f3f4f5f6c1q1q4c2q2c3q3c4c5q5VTSw 步骤三：在变化图的基础上重复步骤一、二，直至所有节点的局部度均为零，并将局部度为零的节点选为设计变量。w q1，c3 局部度为1，所以消去相应的q1、c3、f1、f6 及相关联系。则出现局部度为零的节点c4、c5，将c4、c5选为设计变量。f3f5q4q2q3c4c5q5f1f3f5f6q1q4c2q2c3q3c4c5q5Tc2Tq3c4c5q5q2，q4 局部度为1，所以消去相应的q2、q4、f3、f5 及相关联系。则出现局部度为零的节点q3、q5。将q3、q5选为设计变量。经过上面各步，共选出6个设计变量c2、T、c4、c5、q3、q5。至此，计算顺序也确定出来了。f3f5q4q2q3c4c5q5Tc2q3c4c5q5Tc2问题的求解顺序为：设定设定c4c5f7S设定q3 q5f5q4f6c3f4V设定q3f3q2f1q1f2c1设定q5c2 q5f1 q1q5-q2=0 f2 q1c1q5c5-q2c2=0f3 q2-q3=0f4 q2c2q3c3 R(c3,T,V)=0f5 q3q4 q5=0f6 q3c3q4c4 q5c5=0f7 S=c5/c4设定c2 T