数学建模网络优化

1、2011甘肃农业大学第八届大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： a 我们的参赛报名号为（如果赛

2、区设置报名号的话）： 所属学校（请填写完整的全名）： 甘肃农业大学 参赛队员 (打印并签名) ：1. 周小雄 2. 崔起飞 3. 杨慧珍 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 5 月 29 日赛区评阅编号（由赛区组委会评阅前进行编号）：摘要本文研究的是工程施工工期的优化问题，使用了网络优化模型，通过对网络关键路径的分析和改进，采用两种方法进行求解并比较结果，得到了工程最短工期和公司利润最大情况下的最优施工方案。对于问题一，根据各个任务之间的联系，绘制了双代号网络图，采用用点代表事件，点之间的有向线段代表任务，虚线段代表先决关系的虚工作，虚工作的耗时为0, 清楚的表

3、示出了任务之间的施工进程。第二问求解时，本文采用的方法一是建立工期最短的目标方程和以先行后继关系为约束的条件，将问题转换为最优解问题；方法二是通过求解工程各个事件的最早开始和最迟开始时间，得到最后一个事件的完成时间则为工程最短工期。两种方法求解出的结果相同，工程最短工期均为64周。在问题二的基础上，问题三需要在公司利润最大化的情况下缩短工期，方法一在问题二的基础上改变了目标函数为公司利润，以缩短关键路径为手段。在缩短关键路径时，涉及到关键路径可能改变问题，对此，本文将目标函数设置成总周期的减少除去额外费用，这样避免了在求解过程中易出现的非关键路径的缩短而浪费资源的情况，也解决了关键路径可能改变

4、的问题，同样将问题转换为了最优解问题。在方法二中，先假设对关键路径进行缩短，关键路径不发生改变。再联系缩短任务耗时所需的成本分析工程该如何缩短工期，最终得到最优施工方案。将最优施工方案检验，发现缩短周期后关键路径并没有发生改变。两种方法求得的结果相同，公司最大利润为8.7万元，工程工期缩短到54周。整个问题最大的困难就是缩短时间可能发生的关键路径的改变从而引起的错误判断，本文模型最大的优势就是由于适当的设置了目标函数，从而避免了这个问题的发生。通过两种方法比较使用进行求解，以及不同方法的相互验证，确保了施工方案的最优化和公司利益的最大化。关键词：双代号网络图、最优解、关键路径、最大获利一、问题

5、重述某市政府决定修建一个小型体育馆，通过竞标，一家本地建筑公司获得此项工程，并且希望尽快完成工程。表中列出了工程中的主要任务，时间以周计算。有些任务只有在某任务完成后才能进行。需要解决的问题是： 问题一：绘制各任务间的关系图。 问题二：工程最早完成时间。 问题三：市政府希望能够提前完工，为此向建筑公司提出工期每缩短一周，则可支付3万元奖励。为缩短工期，建筑公司需要雇用更多的工人，并租借更多设备（表中额外支出部分）。设计施工方案使建筑公司的获利最大。二、基本假设1. 题中所给的完成各项工程任务的时间是准确不变的，不受各种自然、非自然因素的影响。2. 所有工程任务需要且必须在满足先决条件的情况下即

6、可立即开始。3. 每周额外支出费用是指工期每缩短一周所支出的费用。4. 缩短施工时间的任务在除额外支出费用外的原来的总施工费用不变。5. 市政府希望尽早完成工程，建筑公司以在利益最大的情况下也以尽早完成工程为目标。三、符号说明与名词解释3.1符号说明：表示第个事件，；：表示事件的开始时间，；：是事件间最长任务完成的时间，；：完成任务的最短完成时间，；：任务可能减少的完成时间，；：任务每缩短一周所需的额外费用，；：任务的持续时间，；：任务的延缓时间，；：任务可以缩短的最大工时，；：各个事件之间的结构矩阵；：各个事件之间的关系矩阵；：任务可以开始的最早时间，；：任务可以完成的最早时间，；：任务在不

7、增加耗时的情况下可以开始的最迟时间，；：任务在不增加耗时的情况下可以完成的最迟时间，；：在不需要提前完工的前提下，最早完成此工程的时间；：在需要前提完工和公司获利最大的前提下，最早完成此工程的时间。3.2名词解释1. 关键路径：关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。2. 直接前驱：每项任务对应的一组必须在该任务开始之前完成的任务。3. 直接后继：每项任务对应的一组必须在该任务完成之后才能开始的任务。4. 事件：事件的意义是表示以它为后继的任务已经完成，以它为前驱的任务可以开始。四、问题分析4.1问题一本文把所有任务按先决条件的相互关系绘制成

8、双代号网络图，以节点代表工程事件，以节点间的有向线段代表工程任务，绘制关系图。4.2问题二根据题意，本问是在不考虑缩短完成任务时间的情况下求解工程最短工期的问题，在第一问的基础上求解，即通过问题一转换为求解此网络图关键路径的问题，关键路径上所有任务的时间总和就是此工程最早完工时间。可以采用线性规划和网络最短路径两种方法求解。4.2问题三在第二问的基础上，第三问是一个计划网络优化问题。要想缩短工程工期，必须缩短关键路径上任务的耗时。但是由于任务施工时间的缩短可能导致关键路径的改变，从而可能引发非关键路径缩短而浪费资源的问题，于是本文通过增加松驰变量来表示可能缩短的周数，以工程总时间的缩短为另一变

9、量，通过设置目标函数为，从而避免了此问题的发生。依旧可通过两种方法的相互比较验证得到最优化的施工方案。五、模型建立5.1绘制工程双代号网络图本文重新把附录表一数据进行编码，将各任务用字母加下标代替，如附录表二所示，即表示第个任务。据此我们需要绘出整个工程的计划网络图。是由一个非空有限集合和中某些有序对集合构成的二元组，记为。其中是图的顶点集，即事件集合。是图的弧集，就表示第个任务，即任务集合，。图中即用、等表示事件，事件的意义表示前面的任务已经完成，后面的任务可以开始。任务用、表示，标在箭线上（箭头的方向表示先决关系），同时任务相应的完成时间标也标在对应箭线上。事件表示工程的开始，事件表示工程

10、的结束，虚线表示工时为0的虚构的任务，仅用于表示各事件间的前行后继关系。我们在建立计划网络时遵循以下规则：（1）任何任务在网络中用唯一的箭线表示，任何任务其终点事件的编号必须大于其起点事件。（2）两个事件之间只能画一条箭线，表示一项任务。（3）任何计划网络图应有唯一的最初事件和唯一的最终事件。（4）计划网络图不允许出现回路。（5）计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉。图一要求最早完成时间，即要求时间最短，和分别表示工程开始时间和工程结束时间。5.2问题二5.2.1使用lingo求解的数学模型对于事件和有关系式就是指事件之后的事件的发生时间必需大于或等于事件的

11、发生时间和事件与间的最长任务完成时间的和。由此可转化为数学规划问题约束条件：5.2.2使用matlab求解的数学模型本问还可以采用另一种思路求解，节点可以开始的最早时间是这个节点所有的紧前事件的最早开始时间加上其节点之间工程耗时的最大值，故得到如下等式： （5.3）而节点的最迟开始时间，应该是其紧后工作的最早开始时间减去其事件之间的工序耗时的最小值，即： （5.4）根据节点其最早开始时间为0的事实，通过式5.3和5.4可以求出所有活动的最早开始时间和最迟开始时间，而只要到达节点，整个工程就完成了，故节点的最早开始时间和最迟开始时间相等，等于整个工程的完成时间，故得到目标方程： （5.5）5.3

12、问题三5.3.1使用lingo求解的数学模型增加了变量表示任务的最短完成时间，表示任务可能减少的时间以及表示任务缩短一周需要增加的费用，表示优化后的完成周数。那么根据第一问的结果不优化前的最早完成时间为64周，我们设为计划网络优化后的完成时间。于是总的获利可表示为万元。目标为极大化。事件与间的关系应是事件的开始时间减去事件的开始时间应大于原来两任务间最长任务的完成时间的的减去可能缩短的时间，即。同时，可能减少的时间应满足。目标为极大化。由此可得到相应的数学规划问题：5.3.2使用关健路径求解的数学模型为了找到能使建筑公司获利的时间安排，需要根据问题二中的关键活动和关键路径。关键路径的总耗时直接

13、决定了整个工程项目的耗时，如果要想缩短总工期的耗时，必须缩短关健路径上的工程事件的耗时。在考虑经济效益的方面，缩短时间的前提是获得更大的经济效益，所以只对额外支出费用小于等于3万元的项目进行增加额外支出来缩短时间。从而可以实现在获得经济效益的同时而缩短工期。根据节点的最迟完成时间是工程完成时间的事实，分析可知，任务的延缓时间即为任务的最迟开始时间与最早开始时间的差值，即: (5.6)求得延缓时间后，通过分析同样可以求得公司获利最大前提下各任务工期是怎样提前的，即确定。最后得到在公司获利最大前提下，完成此工程的时间为： （5.7）公司最大利润为： ，由分析确定 (5.8)六、模型求解6.1问题二

14、6.1.1使用lingo求解采用lingo9.0软件进行规划求解。step1:将所有事件用形式表示，与相应作业时间并同输入程序；step2:确定目标函数，;step3:编程求解（程序见附录）。 求得结果给出了各任务开工时间。其中，表示任务（工地布置）的开工时间是第0周，表示任务的开工时间是第2周，表示任务的开工时间是第26周，等等。综合统计得下表。任务开工时间(周)任务开工时间（周）0432281852274626543763表一每个任务只要按要求得时间开工，则整个工程的最早完成时间为64周。6.1.2使用matlab 求解本问使用matlab求解的步骤如下建立各个几点的结构矩阵，其元素表示节

15、点和节点之间的工程项目。如果节点和节点之间没有工程项目，取的值为0，否则取工程项目的耗时。于是得到了结构矩阵：建立关系矩阵，其中的元素表示各个节点之间是否有项目连接： 得到13个事件节点的关系矩阵：根据结构矩阵和关系矩阵，结合公式（5.3）和（5.4），我们就可以得到各个节点时间的最早开始时间和最迟开始时间。程序见附录。各个节点事件的最早开始时间和最迟开始时间见下表：节点事件最早开始时间最迟开始时间时间差000220181802727026371137370434302852245252046548545406363064640表二根据以上的结果可以得到节点事件的时间，即所有工程项目的完工的时

16、间为64周。如果某项任务有正的延缓时间，则该任务就有部分机动空间，即稍微迟一点开始也不会使工程完成时间增加。然而，如果某项任务的延缓时间为0，则增加该任务的耗时将必然使工程完成时间增加。因此，关键路径由延缓时间为0的任务组成，即如下节点组成了关键路径：关键路径所对应的关键活动为：6.1.3 结果比较 两种方法求解结果完全相同，最短工期为64周，工程任务开工时间安排见表一。6.2问题三6.2.1使用lingo求解对于第二问我们引入了一个参数，用以表示任务的最短完成时间。的求解由原来的完成时间减去相应任务的最大缩短时间。step1:根据任务作业时间和最大缩短时间计算最短完成时间；step2:输入所

17、有任务和对应及，任务以有向线段的方式输入，且保证；step3:确定目标函数与约束条件；step4: 运行程序求解（程序见附录）。结果中的表示事件的开始时间，表示优化后的任务作业时间，表示任务缩短的时间。最后的结果表明公司最大可获利8.7万元，工程可缩短到57周完成。但由于任务的额外开支为3万元，正好等于缩短一周的收入，且任务在关键路径上，所以在用软件求解时未将其考虑为缩短时间的任务，于是分析得最好的结果是将任务的时间缩短到13周。综合得到表三计划：任务开始时间(周)完成时间(周)缩短时间(周)额外开支(万)2133915812.623823.431511.523110.836211.84773

18、4.8表三公司最大获利8.7万元，工程工期缩短至54周。6.2.2使用matlab和关键路径求解 通过对问题三的分析，可以得到需要对关键路径上的关键活动来缩短时间，使整体工期缩短，考虑到经济效益，只对额外支出少于3万元的进行选择性的缩短。在对工程缩短时，考虑到关键路径可能发生改变，先假设工程时间缩短的同时，关键路径不发生改变。可以列如下表格进行计算：关键活动最大缩短时间每周额外支出单位（万）市政奖励-额外支出（万/周）是否进行缩短缩短周数（周）0-330是312.60.4是121.71.3是211.51.5是124.2-1.2否-0-31.61.4是30-总计盈利缩短时间3*0+1*0.4+2

19、*1.3+1*1.5+3*1.4=8.7万元10周表四通过列表计算，可以得到对大的缩短周期为10周，其中可以根据实际需要选择是否缩短，不影响盈利。体育馆建设的项目最早可以再54周完成。考虑到在对工程项目进行缩短的过程中，可能影响到关键路径的改变。需要对缩短后的关键路径进行验算。缩短时间后的结构矩阵：将得到的新矩阵带入到6.1.2中的程序中得到的节点事件最早开始时间最迟开始时间时间差00022015150232302331831310363602545204545039478474705353054540表五通过新的结构矩阵进行计算，可以得出总的工期为54周，与表格计算的结果一致。得出的关键路径

20、为：关键活动为：说明，经过对某些工程缩短后，仍然是关键路径，在缩短的过程中没有发生关键路径变化，即在工期缩短的过程中，每一周的时间缩短，都直接使整个工期缩短。由表四的结果，可知延缓时间为0的任务下标为：1，2，3，5，6，9，12，17，18，加快这些任务可以使得总工程能提前完成。但由题可知任务9提前一周完工的额外开支为4.2万元，大于奖励3万元，故不加快任务9。而任务2提前一周完工的额外开支为3万元，等于奖励3万元，若是出于考虑到实际生活中要临时雇用更多的工人及租用设备等问题，则不加快任务2；若只考虑让完工时间最短，则加快任务2。由于任务1，12，18的最大缩短时间为0，故这两项任务也不能加

21、快。综上所述，可以加快的任务有：。其中从不同的角度出发，任务可加快，也可不加快。经计算得在不加快任务的前提下：周。在加快任务的前提下：周。两种情况下可获得的额外利润都为:万元。6.2.3结果比较 两种方法求解出的结果完全相同，公司最大可获利8.7万元，工期缩短为54周，工程任务安排见表三。七、模型的评价和改进本文是工程施工工期的优化问题，采用了网络模型进行优化，使用了两种求解方法解出了模型的最优解，通过比较得到了最优施工方案。本文使用模型简单高效，求解方法合理。采用两种方法比较使用，相互验证，也保证了结果的最优性。不过，对于工程来说，很多重要因素例如非关键任务的最早开工时间、最迟开工时间等并未

22、给出，由此，进一步的优化可将非关键任务完成后的人员、资源转投入其余未完工的任务中，由此可加快项目进程。八、参考文献1 姜启源，谢金星，大学数学实验（第二版），清华大学出版社，北京，20102 韩中庚，数学建模方法及其应用，高等教育出版社，北京，20063 运筹学教材编写组，运筹学（第三版），清华大学出版社，北京，20074 魏宏博，惠晓滨，张凤鸣，一种求双代号网络图关键线路的简便矩阵算法，计算机工程与设计，第25卷，第7期，2004年7月 附录本问题数据附表：表格： 体育馆施工数据任务描述耗时先决任务最大缩短时间每周额外支出单位（万）1工地布置2没有02场地平整161333打地基9212.64

23、通路及其他道路网络8221.25底层施工10321.76主场地施工64,511.57划分更衣室2410.88看台电气布置2609顶部施工94,624.210照明系统5412.111安装阶梯看台3611.812封顶29013更衣室17014建造售票处7222.215第二通路44,1421.216 信号设施38,11,141617草坪与附属运动设施91231.618交付使用1170重新编号后的数据表：表格： 体育馆施工数据任务描述耗时先决任务最大缩短时间每周额外支出单位（万）工地布置20场地平整1633打地基912.6通路及其他道路网络821.2底层施工1021.7主场地施工6，11.5划分更衣室

24、210.8看台电气布置20顶部施工9，24.2照明系统512.1安装阶梯看台311.8封顶20更衣室10建造售票处722.2第二通路4，21.2信号设施3，16草坪与附属运动设施931.6交付使用10表二问题二matlab程序代码：%a为结构矩阵a=0 2 0 0 0 0 0 0 0 0 0 0 0; 0 0 16 0 0 0 0 0 0 0 0 0 0; 0 0 0 9 8 0 0 0 0 7 0 0 0; 0 0 0 0 0 10 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 2 0 0 0 0 5; 0 0 0 0 0 0 6 0 0 0 0 0 0; 0 0 0 0 0 0

25、 0 0 9 3 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 2 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 3; 0 0 0 0 0 0 0 0 0 0 0 9 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0; %x为关系矩阵x=0 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 1 1 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0 0 0 0 0 0; 0 0 0

26、 0 0 1 1 1 0 0 0 0 1; 0 0 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0;%es最早开始时间矩阵es=zeros(13,1);for inum=2:13 t=0; for jnum=1:inum if

27、 x(jnum,inum)=0 if t<a(jnum,inum)+es(jnum,1) t=a(jnum,inum)+es(jnum,1); end end end es(inum,1)=t; end%ls最迟开始时间矩阵ls=zeros(13,1);ls(13,1)=es(13,1);for inum=12:-1:1 t=ls(inum+1,1); for jnum=13:-1:inum if x(inum,jnum)=0 if t>ls(jnum,1)-a(inum,jnum); t=ls(jnum,1)-a(inum,jnum); end end end ls(inum,1

28、)=t;end%s为寻找关键路径 s=find(ls-es)=0);问题二的lingo程序：model:sets:events/1.13/:x;operate(events,events)/1 2,2 3,3 4,3 5,3 10,4 6,5 6,5 7,5 8,5 13,6 7,7 9,7 10,8 13,9 11,10 13,11 12,12 13/:t;endsetsdata:t=2 16 9 8 7 10 0 0 2 5 6 9 3 1 2 3 9 1;enddatamin=x(13)-x(1);for(operate(i,j):x(j)>x(i)+t(i,j);end问题三li

29、ngo程序：model:sets:events/1.13/:x;operate(events,events)/1 2,2 3,3 4,3 5,3 10,4 6,5 6,5 7,5 8,5 13,6 7,7 9,7 10,8 13,9 11,10 13,11 12,12 13/:t,m,c,y;endsetsdata:t=2 16 9 8 7 10 0 0 2 5 6 9 3 1 2 3 9 1;c=0 3.0 2.6 1.2 2.2 1.7 0 0 0.8 2.1 1.5 4.2 1.8 0 0 0.6 1.6 0;m=2 13 8 6 5 8 0 0 1 4 5 7 2 1 2 2 6 1;

30、 enddatamax=3*(64-d)-sum(operate:c*y);for(operate(i,j):x(j)-x(i)+y(i,j)>t(i,j);n=size(events);x(n)-x(1)<d;for(operate:bnd(0,y,t-m);end求解结果： global optimal solution found. objective value: 8.700000 total solver iterations: 0 variable value reduced cost d 57.00000 0.000000 n 13.00000 0.000000 x(

31、 1) 0.000000 0.000000 x( 2) 2.000000 0.000000 x( 3) 18.00000 0.000000 x( 4) 26.00000 0.000000 x( 5) 26.00000 0.000000 x( 6) 34.00000 0.000000 x( 7) 39.00000 0.000000 x( 8) 28.00000 0.000000 x( 9) 48.00000 0.000000 x( 10) 42.00000 0.000000 x( 11) 50.00000 0.000000 x( 12) 56.00000 0.000000 x( 13) 57.0

32、0000 0.000000 t( 1, 2) 2.000000 0.000000 t( 2, 3) 16.00000 0.000000 t( 3, 4) 9.000000 0.000000 t( 3, 5) 8.000000 0.000000 t( 3, 10) 7.000000 0.000000 t( 4, 6) 10.00000 0.000000 t( 5, 6) 0.000000 0.000000 t( 5, 7) 0.000000 0.000000 t( 5, 8) 2.000000 0.000000 t( 5, 13) 5.000000 0.000000 t( 6, 7) 6.000

33、000 0.000000 t( 7, 9) 9.000000 0.000000 t( 7, 10) 3.000000 0.000000 t( 8, 13) 1.000000 0.000000 t( 9, 11) 2.000000 0.000000 t( 10, 13) 3.000000 0.000000 t( 11, 12) 9.000000 0.000000 t( 12, 13) 1.000000 0.000000 m( 1, 2) 2.000000 0.000000 m( 2, 3) 13.00000 0.000000 m( 3, 4) 8.000000 0.000000 m( 3, 5)

34、 6.000000 0.000000 m( 3, 10) 5.000000 0.000000 m( 4, 6) 8.000000 0.000000 m( 5, 6) 0.000000 0.000000 m( 5, 7) 0.000000 0.000000 m( 5, 8) 1.000000 0.000000 m( 5, 13) 4.000000 0.000000 m( 6, 7) 5.000000 0.000000 m( 7, 9) 7.000000 0.000000 m( 7, 10) 2.000000 0.000000 m( 8, 13) 1.000000 0.000000 m( 9, 1

35、1) 2.000000 0.000000 m( 10, 13) 2.000000 0.000000 m( 11, 12) 6.000000 0.000000 m( 12, 13) 1.000000 0.000000 c( 1, 2) 0.000000 0.000000 c( 2, 3) 3.000000 0.000000 c( 3, 4) 2.600000 0.000000 c( 3, 5) 1.200000 0.000000 c( 3, 10) 2.200000 0.000000 c( 4, 6) 1.700000 0.000000 c( 5, 6) 0.000000 0.000000 c( 5, 7) 0.000000 0.000000 c( 5, 8) 0.8000000 0.000000 c( 5, 13) 2.100000 0.000000 c( 6, 7) 1.500000 0.000000