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

习 题1. 某油田产量为Q吨/年，分别供应A、B、C、D四个城市，各城市每年的原油需求量分别为10、50、5、35吨。油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。问如何安排运送计划最为经济？试建立此问题的数学模型。45673281油田ACBD通路12345678允许流量4010204040701840单位运输费用10804010357040852. 某冷饮店要制定七八月份的日进货计划。该品质的冷饮进货成本为每箱30元，销售价为50元，当天销售后每箱可获利20元。如果剩一箱，由于冷藏及其它原因要亏损10元。今年的市场情况不清楚，但有前两年同期120天的日销售资料如表所示。试问今年平均每天进多少箱为好？日销售量（箱）完成销售的天数100241104812036130123. 试将下列线性规划问题化为标准型。4. 试写出下列线性规划问题的对偶问题。5. 某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。问该厂应生产A、B两种产品各多少千克才能使总利润最大？请用单纯形法求解。产品资源消耗量/kg资源AB资源限制量煤94360电力45200劳动力310300利润7126. 设有如图所示的网络图，计算网络图中各节点的最早、最迟时间，并求出关键路线。13524ABGFDHEC4771053237. 从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中顶点1为油田，顶点8为原油加工厂，弧权为相应路段的管道长度，应如何铺设管道，才能使油田到原油加工厂的管道总长最短？试用标号算法确定其最短距离及其相应的路线。754595416764412345678习题解答1. 某油田产量为Q吨/年，分别供应A、B、C、D四个城市，各城市每年的原油需求量分别为10、50、5、35吨。油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。问如何安排运送计划最为经济？试建立此问题的数学模型。45673281油田ACBD通路12345678允许流量4010204040701840单位运输费用1080401035704085解：设各条通路要安排的全年运油总量分别为xj（j =1, 2, , 8）。本问题的目标为总运输费用最小，即首先，考虑各城市需求量约束，则有其次，总供应量不能超过油田产量，即再次，各条通路的运量不能超过其允许流量，则有故该问题的数学模型为2. 某冷饮店要制定七八月份的日进货计划。该品质的冷饮进货成本为每箱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) = 20000.2+20000.4+20000.3+20000.1=2000U(A2) = 19000.2+22000.4+22000.3+22000.1=2140U(A3) = 18000.2+21000.4+24000.3+24000.1=2160U(A4) = 17000.2+20000.4+23000.3+26000.1=2090故最优方案可见，日进货120箱的计划方案A3的期望利润值最大，应选为最优方案。3. 试将下列线性规划问题化为标准型。解：令且、在第一个约束条件中引入松弛变量x4，第二个约束条件中引入剩余变量x5，第三个约束条件两边同乘以-1，同时将目标函数变为求最大值，整理可得4. 试写出下列线性规划问题的对偶问题。解：令且、将第二个约束条件两边同乘以-1，第三个约束条件转化为两个不等式，则原问题可改写为由原问题与对偶问题的关系，可得相应的对偶问题为5. 某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。问该厂应生产A、B两种产品各多少千克才能使总利润最大？请用单纯形法求解。产品资源消耗量/kg资源AB资源限制量煤94360电力45200劳动力310300利润712解：设产品A、B的产量分别为x1、x2千克，则上述安排生产计划问题的数学模型为将模型标准化，可得表1 初始单纯形表cj712000iCBXBbx1x2x3x4x50x336094100900x420045010400x530031000130j712000表2 x5替换为x2后的单纯形表cj712000iCBXBbx1x2x3x4x50x324039/5010-2/5400/130x4505/2001-1/22012x2303/101001/10100j17/5000-6/5表3 x4替换为x1后的单纯形表cj712000iCBXBbx1x2x3x4x50x384001-78/2529/257x1201002/5-1/512x224010-3/254/25j000-34/25-13/25表3最后一行的所有检验数j都已为负或零，这表示目标函数值已不可能再增大，于是得到最优解且相应的最优值（即工厂的最大总利润）f * = 428。6. 设有如图所示的网络图，计算网络图中各节点的最早、最迟时间，并求出关键路线。13524ABGFDHEC477105323解：第一步：计算各节点的最早时间，并将结果记入图中各节点左下方的方框“”中第二步：计算各节点的最迟时间，并将结果记入图中各节点右下方的三角框“”中第三步：确定关键线路如图所示，网络图中、为关键节点，、为关键工序，则由ADG即为网络图的关键线路。13524ABGFDHEC477105323 00 44 37 99 1616 7. 从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中顶点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 = 4T (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 = min9，6+4 = 9T (5 ) = min T (5 )，P (3) + l35 = min9，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 = min15，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。类似地，可推算出油田到原油加工厂管道的最短路线为12578，其最短距离均为16。附录1. 要做100套钢架，每套由长为2.9m，2.1m和1.5m的圆钢各一根组成。已知原料长7.4m，试问该如何下料使所用的原料最省？解：方法一：一种简单的想法是在每根原料上截取2.9m，2.1m和1.5m的圆钢各根，这样每根原料剩下0.9m的料头。为了做100套钢架，要用原料100根，料头总数为90 m。现在可以考虑下面如表所示的几种原料套截方案来进行合理套截，以节省原料。/长度/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根，则由题意可得通过分析上述表格，发现其中的方案、的料头过长，不经济，如果把它们舍弃，对剩下四种方案进行搭配，仍然可以满足题意，因此将上述模型简化为（保持变量下标不变）2. 从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿着如图所示的给定路线进行铺设，图中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 = min6，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 在所有的T类标号中，T (v4) = T (v7) = 10最小，于是令P (v4) = P (v7) = 10；第六步 与顶点v4和v7直接相连且又为临时标号的顶点只有v9，则将它的T类标号改为T (v9) = min T (v9)，P (v7) + l79 = min12，10+2 = 12 显然应令P (v9) = 12，即终点（顶点v9）获得固定标号，算法到此结束，则顶