系统工程案例分析.doc

系统工程案例分析作业道路改造项目中的碎石运输段习升200605017001侯金鑫200605017002吴家旭200605017003刘孝臣200605017004 强宝菊 2006050170262010年01月21日摘要本问题是一个优化问题，在一个道路改造项目中，要我们设计碎石的运输方案，使修路的总费用最小。经过分析，我们将问题化为非线性优化问题，用Lingo进行求解。但随着临时码头和临时道路的增多，问题的变量变得很多，数据的值也很大，Lingo软件求解变得不稳定，为了提高结果的可信度，我们另用C+语言编程用全局搜索法求解，当两种方法求得结果十分接近时，我们才接受它。设运输方案中临时码头个数为，从引出的临时道路与AB的交点个数为，由于费用最少方案的、值很难确定，在寻找费用最少的方案时，只好先给出一些具体的、值，求出其最优布局和最小费用。我们共求了22个不同、值下的最小费用，发现随着、值的增大总费用一直在减少。其中当时（即83方案），费用在22个方案中最小。最小总费用为：S=16.53246 亿元通过对数据进行拟合及分析发现该值已比较接近理论最小费用值，所以我们将该方案定为近似最优方案。算出从、所取的碎石量分别为：，。之后我们用蒙特卡洛法对模型进行了检验。但进一步分析发现，上述近似最优方案并不十分符合实际，该方案中临时道路的总长度竟然长达千米。于是我们定义了抱怨系数来衡量各方案的实际可行性。不同方案的抱怨系数可以为决策者提供参考，同时，我们根据得到的抱怨系数和实际情况给出一个比较符合实际的方案，即31方案。其费用为：S=17.62621 亿元，碎石分配为：，。按照题中所给的数据进行建模计算，所得的结果为什么会不符合实际呢？在模型的进一步讨论中我们进行了分析，发现题中“运输1立方米碎石1km运费为20元”这一数据很不符合实际，这一数据过大导致的结果是：要想减少费用，就必须千方百计的减少碎石的运输路程，从而更多的修建临时道路。这就是我们难以找到理论最优方案的原因。通过分析我们将其改为10元后，重新计算，得到了最优解。一问题重述与分析1.问题重述在一平原地区需要修建一条长为200千米的直线公路AB，其修建所需的碎石可以由S1，S2 两个采石点提供，但运输碎石需要修建临时道路。同时此地区有一条河流，碎石也可以通过水路运输，但又得修建临时码头。问题要求我们寻找最优的碎石运输方案，使修建总费用最少。2.问题分析 首先要考虑的问题是采不采用水路运输即需不需要建临时码头。 我们通过计算发现，水路运输可以节省较大数目的费用，而修建码头的费用相对公路运费来说是很小的。根据模型计算的结果，应该修建码头。 确定最优方案的前提，是确定应该修建的码头数m，从引出的临时道路与AB的交点个数。这是一个十分复杂的问题，每增加一个临时码头或一条临时道路，前面的码头和临时道路的最优分布就会被打乱，必须重新用非线性规划模型求解。所以只能根据不同的m，n值，求出该条件下的最优分布和最小费用，再从中选取一个m-n方案作为近似最优解。在确定了m，n的值后，可以用非线性规划模型求出临时码头和道路的分布。临时码头数和道路数较多时，问题的变量有很多个，应用Lingo求解时发现结果变的不稳定，软件有时会陷入局部最优解，这使该条件下最优方案变得不十分可靠，为了提高方案的可信度，我们又用C+语言编程，用全局搜索的方法进行求解，并对结果进行蒙特卡洛检验 ，当前两种方算出结果很相近并通过蒙特卡洛检验时，我们才接受它。好的方案应该是符合实际的。实际修建过程中，将碎石运到铺设地点后，铺设过程也需要一定的费用，而题中将这部分费用忽略了。这是不符合实际的。另外，铺设临时道路或码头时，必须调用较多的人力，花费一定的时间，所以过多的修建临时道路或码头会影响AB段公路的修建，浪费较多的资源，使其工期增长，这样的方案即使理论算出费用是最少的，在实际中也不一定是可取的。题目中运输1立方米碎石1km运费为20元， 假设一辆车可以装5立方米碎石，则其运50公里就要5000元，这一数据过大导致的结果是：要想减少费用，就必须千方百计的减少碎石的运输路程，从而更多的修建临时道路。这就是我们难以找到最优方案的原因。在模型的进一步讨论中，我们将其改为10元后，再重新计算，得到了最优解。更有力的证明了题中的数据是不合实际的。二问题假设（1）石料的运输费用为一个来回的运输费用。（2）假设桥的造价接近正无穷，不宜为运输碎石而建造桥梁。（3）临时公路铺设费用不计。（4）临时道路铺设完马上可以通车，而且运输费与AB间道路的运输费用一致。（5）河流的宽度足够用于能够在两岸正对面建立两个码头，在计算时不计在河流宽度上的运输费。（6）地势平坦，图上距离即为实际距离。（7）临时道路都是以直线段的形式修建的。三符号说明 S 方案的最小费用 s1 第一个采石点s2 第二个采石点 m-n S1端修建m个码头，S2端有n个接入点 河流上从上往下第个码头 码头所对应的接入点 采石点对应的第个接入点 S1，S2的平衡点 s1所分配的碎石量 s2所分配的碎石量四模型建立与求解首先，我们定义了两个概念。其定义如下：接入点：即临时道路与AB公路的汇接点；平衡点：s1，s2所提供的碎石以平衡点为分界，平衡点左边由s1提供碎石，平衡点右边由s2提供碎石。其次，我们算出了上下游河流的曲线方程如下：m4的上游的抛物线方程为：,y = 100,m1,m2,m3,m4全在此抛物线上。m4的下游的抛物线方程为：, y = 100,m4,m5,m6,m7全在此抛物线上。为了确定是否需要建临时码头，需要算出建码头和不建的费用各是多少，对比后进行取舍。根据题中假设易有：总费用=碎石成本+运输费+码头建设费1. 不修建码头的情况（0-1 方案） （注：mn方案是指修m个临时码头，处修的临时道路与AB有n个接点）先考虑较简单的方案，此处我们不计河流对运输路线和费用的影响，且假设从s1、s2各修一条临时道路到AB上。设两条路与AB的接入点分别为A1(x1,100)、A2(x2,100)，平衡点为O（xo,100）如图（1）： 图（1）则:修临时道路的费用：: : 修AB段费用： 1） 运输费： 2）铺设费： 3）碎石成本：总费用 式中：， ， ，这是一个三变量的优化问题，用运筹学软件Lingo求出最优解为 最小费用：（元）2.修建两个码头的情况仍从较简单的情况开始考虑，假设只修建两个临时码头，处只修一条临时道路与AB相交（2-1方案），如图，设两码头分别为，其它同上。费用的计算方法与前类似；临时公路费用： ： : 修AB段费用：1） 运输费： 2）铺设费： 3）碎石成本：总费用 注： 表示与之间的曲线长。求得最优解为：, , ,其中与重合，为同一点。最小费用（元）。 与前面的01方案比较可发现，修建临时码头比不修建临时码头节省了将近3亿元，另外由于0-1方案的最小费用不会多于考虑河流不建码头的方案的最小费用。所以好的方案应该修建码头。3.再求2-2方案的最优布局。设各未知点的如图（3），求得的最优布局如图（4），发现仍有一码头在点，且与重合。图（3）图（4）各点坐标：，最小费用：S=17.98970 亿元。4. 多码头多临时道路模型（m-n方案）为了方便比较分析，我们取了不同的m、n值，用Lingo和全局搜索法求出了各种方案的最小费用。如表（一）：（单位：亿元、千米）方案临时路长度最小费用方案临时路长度最小费用方案临时路长度最小费用2162233185372622123947179897023185656178895931778201762621321395341704027332012431693959411095021720310421692211677303432298411670308511223571709430521820761666423532426961659428611518871703304621959141662396632565341655401711657251699277722239441659274732839321653146811798521697142822380711657139832980591651029表（一）另外，我们还算出24方案的总费用为：17.86555亿元。临时公路总长193.9059公里。由上表，83方案的费用最少，其具体路线图如下：图（5）其中各点坐标：C1、C2、C3：（19.887,115.521），C4（28.247,113.192）C5(38.509,109.588), C6(50,100), C7(74.442,79.817),C8(91.217,73.790), D2(10.602,100), D3(18.932,100), D4(28.165,100)D5(37.404,100), D6(50,100), D7(90.429,100), D8(110.331,100)O(131.971,100), A1(151.787,100), A2(170.731,100), A3(187.966,100)碎石分配为： ，五结果分析1. 从模型的结果我们可以看出，随着临时码头数目和临时道路的公里数的增多，总费用在不断的减少，很可惜，我们没有得到费用最小时的方案，但由表（一）可看出，每增加一段路或码头节省的费用已小于总费用的0.2%，说明结果已很接近理论最优解。对m3系列方案，以临时道路的总长度（千米）为横坐标，前后两方案最小费用的差值（亿元）为纵坐标，根据上表最后两 列数据进行曲线拟合。拟合图如下：图（6）由上图可看出，83方案的最小费用值确实已比较接近理想最小费用。2. 我们考虑到实际设计施工过程中碎石的开采、临时码头和道路的修建都需要花费较多的时间，并且可能造成较多的资源浪费。同时，在模型的求解过程中我们发现，一些方案的最小费用虽然较小，但其所修建的码头数和临时道路的公里数很大，如8-3方案，修建了8个临时码头，临时道路更长达298千米，我们认为此类方案的实际可行性值得怀疑。为了衡量各方案的实际可行性，我们定义了抱怨系数，其定义为：方案的抱怨系数：，其中=100000、即为建造一个临时码头的费用，为方案相对标准方案新增码头的个数；=4000+24000、为方案相对标准方案新增的临时道路长，即为长的临时道路的铺设费用（不考虑将碎石运到建路点的费用）；为方案相对标准方案节省的费用；分别为修建码头和道路的权，其值可根据实际情况人为给定。说明：我们定义的抱怨系数只给决策者提供一个参考，决策者可根据实际情况，给出不同的权值，算出各方案的抱怨系数，再结合方案的最小费用，确定实际可行的方案。考虑到建造码头和临时道路都是为了运输碎石，当公路建好了以后，这些设施都将可能成为累赘，但码头具有更实际的再利用价值。为了表现建造码头和建造临时道路对公路建造影响的不同，我们自己赋予它们不同的权值=3，=4。并以 2-1方案为标准，设其抱怨系数为0。下面给出了所求不同方案的抱怨系数：3-1方案： ，其中，。同理可得其它方案的抱怨系数，整理后的结果如下表：方案最小费用抱怨系数方案最小费用抱怨系数方案最小费用抱怨系数2-1185372602-217989700.4722-317889591.7653-117626210.0623-217040270.7323-316939592.1214-117203100.3064-216773031.1004-316703082.5425-117094300.4475-216664231.2935-316594283.0336-117033040.9206-216623961.5686-316554013.1467-116992771.1847-216592742.2397-316531464.0358-116971421.4978-216571392.6118-316510294.510表（二）由表（二）可看出,31方案的抱怨系数相对其它方案较小,且其费用也比较少,临时道路的总长度为77820千米,明显小于除2-1方案以外的其它方案，但2-1方案的最小费用明显多于3-1方案，所以我们认为，3-1方案是比较符合实际的。其具体路线图如下：图（7）最小费用S=17.62621（亿元）碎石分配为：，。六模型的检验在模型的求解过程中，我们既用了Lingo，又用C+编了全局搜索算法进行求解。但在变量多了以后，Lingo已变得不稳定，全局搜索也很难达到很高的精度，所以对结果进行检验是十分必要的。考虑到问题十分复杂，数据值很大，我们采用蒙特卡洛（Monte- Carlo）方法进行检验。该方法是一种应用随机数来进行计算机模拟的方法，检验的流程图如下：1111否否是代如目标函数产生随机数初始化：=0，=是返回值注：步骤2 是在各变量的取值范围内产生均匀分布的随机数。步骤3中，是目标函数，其中为所有自变量的向量表示。步骤7中， 用来控制算法的循环次数。 该方法得到的结果如下表（单位：亿元）：方案最小费用检验结果方案最小费用检验结果方案最小费用检验结果21185372619037232217981701853785231789059186356331176262117665413217040271748657331694059177347641172031018123774216773021770654431670408177015451170943017371215216664211735275531659529175451761170330417521056216623961736784631655501173671711699277177844272165927417478547316532461715328811697142174743382165713916997598316511291734527表（三）从检验结果可以看出，蒙特卡洛法得到的结果都比模型求得的最小方案大，差额为0.4亿元1亿元不等。因为蒙特卡洛法中变量的取值都是随机产生的，在变量数较多的时候，所有变量同时取最优解的几率很小，所以检验结果比计算结果大是正常的。每一方案的检验结果都比计算结果大，这也正说明我们所建的模型及求解方法是比较可