系统工程导论习题解答.doc 14页

'习题1.某油田产量为Q吨/年，分别供应A、B、C、D四个城市，各城市每年的原油需求量分别为10、50、5、35吨。油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。问如何安排运送计划最为经济？试建立此问题的数学模型。45673281油田ACBD通路12345678允许流量4010204040701840单位运输费用10804010357040852.某冷饮店要制定七八月份的日进货计划。该品质的冷饮进货成本为每箱30元，销售价为50元，当天销售后每箱可获利20元。如果剩一箱，由于冷藏及其它原因要亏损10元。今年的市场情况不清楚，但有前两年同期120天的日销售资料如表所示。试问今年平均每天进多少箱为好？日销售量（箱）完成销售的天数100241104812036130123.试将下列线性规划问题化为标准型。4.试写出下列线性规划问题的对偶问题。-14- 1.某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。问该厂应生产A、B两种产品各多少千克才能使总利润最大？请用单纯形法求解。产品资源消耗量/kg资源AB资源限制量煤94360电力45200劳动力310300利润7122.设有如图所示的网络图，计算网络图中各节点的最早、最迟时间，并求出关键路线。13524ABGFDHEC4771053233.从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中顶点1为油田，顶点8为原油加工厂，弧权为相应路段的管道长度，应如何铺设管道，才能使油田到原油加工厂的管道总长最短？试用标号算法确定其最短距离及其相应的路线。754595416764412345678-14- 习题解答1.某油田产量为Q吨/年，分别供应A、B、C、D四个城市，各城市每年的原油需求量分别为10、50、5、35吨。油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。问如何安排运送计划最为经济？试建立此问题的数学模型。45673281油田ACBD通路12345678允许流量4010204040701840单位运输费用1080401035704085解：设各条通路要安排的全年运油总量分别为xj（j=1,2,…,8）。本问题的目标为总运输费用最小，即首先，考虑各城市需求量约束，则有其次，总供应量不能超过油田产量，即再次，各条通路的运量不能超过其允许流量，则有故该问题的数学模型为-14- 1.某冷饮店要制定七八月份的日进货计划。该品质的冷饮进货成本为每箱30元，销售价为50元，当天销售后每箱可获利20元。如果剩一箱，由于冷藏及其它原因要亏损10元。今年的市场情况不清楚，但有前两年同期120天的日销售资料如表所示。试问今年平均每天进多少箱为好？日销售量（箱）完成销售的天数概率值1002424/120=0.21104848/120=0.41203636/120=0.31301212/120=0.1合计1201.0解：先根据前两年的销售数据，确定不同日销售量的出现概率值，如上表所示。再根据每天可能的销售量，计算不同进货方案的收益值，并编成如下所示的决策表。销售结局利润（元）方案100箱C1P(C1)=0.2110箱C2P(C2)=0.4120箱C3P(C3)=0.3130箱C4P(C4)=0.1100箱A12000200020002000110箱A21900220022002200120箱A31800210024002400130箱A41700200023002600最后由公式计算各销售方案的期望利润值，则U(A1)=2000×0.2+2000×0.4+2000×0.3+2000×0.1=2000U(A2)=1900×0.2+2200×0.4+2200×0.3+2200×0.1=2140-14- U(A3)=1800×0.2+2100×0.4+2400×0.3+2400×0.1=2160U(A4)=1700×0.2+2000×0.4+2300×0.3+2600×0.1=2090故最优方案可见，日进货120箱的计划方案A3的期望利润值最大，应选为最优方案。1.试将下列线性规划问题化为标准型。解：令且、在第一个约束条件中引入松弛变量x4，第二个约束条件中引入剩余变量x5，第三个约束条件两边同乘以-1，同时将目标函数变为求最大值，整理可得2.试写出下列线性规划问题的对偶问题。解：令且、将第二个约束条件两边同乘以-1，第三个约束条件转化为两个不等式，则原问题可改写为-14- 由原问题与对偶问题的关系，可得相应的对偶问题为1.某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。问该厂应生产A、B两种产品各多少千克才能使总利润最大？请用单纯形法求解。产品资源消耗量/kg资源AB资源限制量煤94360电力45200劳动力310300利润712解：设产品A、B的产量分别为x1、x2千克，则上述安排生产计划问题的数学模型为将模型标准化，可得表1初始单纯形表cj712000θiCBXBbx1x2x3x4x50x336094100900x420045010400x53003[10]00130σj712000-14- 表2x5替换为x2后的单纯形表cj712000θiCBXBbx1x2x3x4x50x324039/5010-2/5400/130x450[5/2]001-1/22012x2303/101001/10100σj17/5000-6/5表3x4替换为x1后的单纯形表cj712000θiCBXBbx1x2x3x4x50x384001-78/2529/25—7x1201002/5-1/5—12x224010-3/254/25—σj000-34/25-13/25表3最后一行的所有检验数σj都已为负或零，这表示目标函数值已不可能再增大，于是得到最优解且相应的最优值（即工厂的最大总利润）f*=428。1.设有如图所示的网络图，计算网络图中各节点的最早、最迟时间，并求出关键路线。13524ABGFDHEC477105323解：第一步：计算各节点的最早时间，并将结果记入图中各节点左下方的方框“□”中第二步：计算各节点的最迟时间，并将结果记入图中各节点右下方的三角框“Δ”中-14- 第三步：确定关键线路如图所示，网络图中、、、为关键节点，、、为关键工序，则由A—D—G即为网络图的关键线路。13524ABGFDHEC4771053230044379916161.从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中顶点1为油田，顶点8为原油加工厂，弧权为相应路段的管道长度，应如何铺设管道，才能使油田到原油加工厂的管道总长最短？试用标号算法确定其最短距离及其相应的路线。754595416764412345678解：用最短路标号算法求解时，首先给顶点1标上P类标号，即P(1)=0，其余顶点标上T类标号，且T(j)=∞（j=2,…,8）。第一步与顶点1直接相连且又为临时标号的顶点是2和3，则将这两个顶点的T类标号改为T(2)=min{T(2)，P(1)+l12}=min[∞，0+4]=4-14- T(3)=min{T(3)，P(1)+l13}=min[∞，0+6]=6在所有的T类标号中，T(2)=4最小，于是令P(2)=4，即顶点2获得固定标号；第二步与顶点2直接相连且又为临时标号的顶点是4和5，则将它们的T类标号改为T(4)=min{T(4)，P(2)+l24}=min[∞，4+5]=9T(5)=min{T(5)，P(2)+l25}=min[∞，4+5]=9在所有的T类标号中，T(3)=6最小，于是令P(3)=6；第三步与顶点3直接相连且又为临时标号的顶点是4和5，则将它们的T类标号改为T(4)=min{T(4)，P(3)+l34}=min[9，6+4]=9T(5)=min{T(5)，P(3)+l35}=min[9，6+7]=9在所有的T类标号中，T(4)=T(5)=9最小，于是令P(4)=P(5)=9；第四步与顶点4、5直接相连且又为临时标号的顶点是6和7，则将它们的T类标号改为T(6)=min{T(6)，P(4)+l46，P(5)+l56}=min[∞，9+9，9+4]=13T(7)=min{T(7)，P(4)+l47，P(5)+l57}=min[∞，9+7，9+6]=15在所有的T类标号中，T(6)=13最小，于是令P(6)=13；第五步与顶点6直接相连且又为临时标号的顶点是7和8，则将它们的T类标号改为T(7)=min{T(7)，P(6)+l67}=min[15，13+5]=15T(8)=min{T(8)，P(6)+l68}=min[∞，13+4]=17在所有的T类标号中，T(7)=15最小，于是令P(7)=15；第六步与顶点7直接相连且又为临时标号的顶点只有8，则将它的T类标号改为T(8)=min{T(8)，P(7)+l78}=min[∞，15+1]=16显然应令P(8)=16，即终点（顶点6）获得固定标号，算法到此结束，则顶点1到顶点8的最短距离为16，其固定标号值如图所示。75459541676441234567804139691516要找出从顶点1到顶点8的最短路线，可从顶点8反向逆算。与顶点8直接相连的是顶点6和顶点7，而顶点8与顶点6、顶点7固定标号之差分别为3和1，与顶点8直接相连的弧中只有弧（7,8）的弧权为1，则顶点8之前的是顶点7。类似地，可推算出油田到原油加工厂管道的最短路线为1→2→5→7→8，其最短距离均为16。-14- 附录1.要做100套钢架，每套由长为2.9m，2.1m和1.5m的圆钢各一根组成。已知原料长7.4m，试问该如何下料使所用的原料最省？解：方法一：一种简单的想法是在每根原料上截取2.9m，2.1m和1.5m的圆钢各—根，这样每根原料剩下0.9m的料头。为了做100套钢架，要用原料100根，料头总数为90m。现在可以考虑下面如表所示的几种原料套截方案来进行合理套截，以节省原料。/长度/m方案下根数料ⅠⅡⅢⅣⅤ2.91212.12211.53123合计7.47.37.27.16.6料头00.10.20.30.8为了得到l00套钢架，需要混合使用各种下料方案。设各下料方案所截剩的料头为f，各方案下料的原材料根数分别为x1、x2、x3、x4、x5，则根据表中所示的方案，可列出以下数学模型方法二：各种可能的下料方案如表所示。方案ⅠⅡⅢⅣⅤⅥⅦⅧ需求量A2111100根B21321100根C113234100根总用料7.37.16.57.46.37.26.66.0—料头0.10.30.901.10.20.81.4—原料数x1x2x3x4x5x6x7x8f设所用原材料总数为f根，第j种下料方案所用原料数为xj根，则由题意可得通过分析上述表格，发现其中的方案Ⅲ、Ⅴ、Ⅶ、Ⅷ的料头过长，不经济，如果把它们舍弃，对剩下四种方案进行搭配，仍然可以满足题意，因此将上述模型简化为（保持变量下标不变）-14- 1.从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中v1点为油田，v9点为原油加工厂，弧权为相应路段的管道长度，应如何铺设管道才能使管道总长最短？试用标号算法确定其最短距离及其相应的路线。42424v54v4v7v9v86442v6v3v264v1解：用最短路标号算法求解时，首先给顶点v1标上P类标号，即P(v1)=0，其余顶点标上T类标号，且T(vj)=∞（j=2,…,9）。第一步与顶点v1直接相连且又为临时标号的顶点是v2和v3，则将这两个顶点的T类标号改为T(v2)=min{T(v2)，P(v1)+l12}=min[∞，0+4]=4T(v3)=min{T(v3)，P(v1)+l13}=min[∞，0+2]=2在所有的T类标号中，T(v3)=2最小，于是令P(v3)=2，即顶点v3获得固定标号；第二步与顶点v3直接相连且又为临时标号的顶点是v5和v6，则将它们的T类标号改为T(v5)=min{T(v5)，P(v3)+l35}=min[∞，2+4]=6T(v6)=min{T(v6)，P(v3)+l36}=min[∞，2+4]=6在所有的T类标号中，T(v2)=4最小，于是令P(v2)=4；第三步与顶点v2直接相连且又为临时标号的顶点是v4和v5，则将它们的T类标号改为T(v4)=min{T(v4)，P(v2)+l24}=min[∞，4+6]=10T(v5)=min{T(v5)，P(v2)+l25}=min[6，4+6]=6在所有的T类标号中，T(v5)=T(v6)=6最小，于是令P(v5)=P(v6)=6；第四步与顶点v5和v6直接相连且又为临时标号的顶点是v7和v8，则将它们的T类标号改为T(v7)=min{T(v7)，P(v5)+l57}=min[∞，6+4]=10T(v8)=min{T(v8)，P(v5)+l58，P(v6)+l68}=min[∞，6+2，6+4]=8在所有的T类标号中，T(v8)=8最小，于是令P(v8)=8；第五步与顶点v8直接相连且又为临时标号的顶点只有v9，则将它的T类标号改为T(v9)=min{T(v9)，P(v8)+l89}=min[∞，8+4]=12-14- 在所有的T类标号中，T(v4)=T(v7)=10最小，于是令P(v4)=P(v7)=10；第六步与顶点v4和v7直接相连且又为临时标号的顶点只有v9，则将它的T类标号改为T(v9)=min{T(v9)，P(v7)+l79}=min[12，10+2]=12显然应令P(v9)=12，即终点（顶点v9）获得固定标号，算法到此结束，则顶点v1到顶点v9的最短距离为12。由顶点v9反向逆算，可推算出油田到原油加工厂管道的最短路线为v1v3v5v7v9或v1v3v5v8v9，相应的油田管道最短距离均为12。1.已知系统可达性矩阵为试利用可达性集合和先行集合进行区域划分和级间划分，并建立结构模型。解：（1）区域划分根据可达性矩阵可列出如下表格：111,21121,22233,4,5,63344,5,63,4,64,6553,4,5,6,7,85564,5,63,4,64,675,77,8785,7,888根据，可分为两个区域（2）级间划分由上表可知，根据可知属于第一级元素。将从矩阵中去除，可重新列出如下表格：22222-14- 33,4,63344,63,4,64,6464,63,4,64,66777,87787,888由上表，根据可知，属于第二级元素。将从矩阵中去除，再重新列出如下表格：3333388888由上表，根据可知，属于第三级元素。综上所述，该系统分为三级，从底层至顶层分别为；；。（3）建立结构模型按照区域划分写成如下分块对角化的形式：从上述改写后的M矩阵可见，的相应行和列的矩阵元素完全一样，则削减6行6列，故其缩减矩阵由缩减矩阵，可得-14- 先从矩阵中找出第一级和第二级元素之间的关系，其中，可知、、间有、、的关系。然后去除的行和列，再找第二级和第三级元素之间的关系，从中可以看出，，即、的关系。最后以为矩阵元素，可得结构矩阵根据结构矩阵可绘制出如下所示的系统多级递阶结构图-14-'