数学建模期末

问题一：整个工程需要多长时间完成？

问题二：整项工程至少要比原计划推迟多长时间？需支付额外费用为多少？

问题三：提供希望缩短工期周数和需支付额外费用的关系。

二、基本假设。

1. 题中所给的完成各项工程任务的时间是准确不变的，不受各种自然、非自然因素的影响。

2. 所有工程任务需要且必须在满足先决条件的情况下即可立即开始。

3. 每周额外支出费用是指工期每缩短一周所支出的费用。

4. 缩短施工时间的任务在除额外支出费用外的原来的总施工费用不变。

5. 建筑公司以在利益最大的情况下以尽早完成工程为目标。

三、符号说明与名词解释。

3.1符号说明。

表示第个事件，；

表示事件的开始时间，；

是事件间最长任务完成的时间，；

完成任务的最短完成时间，；

任务可能减少的完成时间，；

任务每缩短一周所需的额外费用，；

任务的持续时间，；

任务的延缓时间，；

任务可以缩短的最大工时，；

各个事件之间的结构矩阵；

各个事件之间的关系矩阵；

任务可以开始的最早时间，；

任务可以完成的最早时间，；

任务在不增加耗时的情况下可以开始的最迟时间，；

任务在不增加耗时的情况下可以完成的最迟时间，；

在不需要提前完工的前提下，最早完成此工程的时间；

在需要前提完工和公司获利最大的前提下，最早完成此工程的时间。

3.2名词解释。

1. 关键路径：关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。

2. 直接前驱：每项任务对应的一组必须在该任务开始之前完成的任务。

3. 直接后继：每项任务对应的一组必须在该任务完成之后才能开始的任务。

4. 事件：事件的意义是表示以它为后继的任务已经完成，以它为前驱的任务可以开始。

四、问题分析。

4.1问题一。

本文把所有任务按先决条件的相互关系绘制成双代号网络图，以节点代表工程事件，以节点间的有向线段代表工程任务，绘制关系图。

4.2问题二。

根据题意，本问是在不考虑缩短完成任务时间的情况下求解工程最短工期的问题，在第一问的基础上求解，即通过问题一转换为求解此网络图关键路径的问题，关键路径上所有任务的时间总和就是此工程最早完工时间。可以采用线性规划和网络最短路径两种方法求解。

4.2问题三。

在第二问的基础上，第三问是一个计划网络优化问题。要想缩短工程工期，必须缩短关键路径上任务的耗时。但是由于任务施工时间的缩短可能导致关键路径的改变，从而可能引发非关键路径缩短而浪费资源的问题，于是本文通过增加松驰变量来表示可能缩短的周数，以工程总时间的缩短为另一变量，通过设置目标函数为。

工程总时间的缩短*额外支出费用—，从而避免了此问题的发生。依旧可通过两种方法的相互比较验证得到最优化的施工方案。

五、模型建立。

5.1绘制工程双代号网络图。

本文重新把附录表一数据进行编码，将各任务用字母加下标代替，如附录表二所示，即表示第个任务。

据此我们需要绘出整个工程的计划网络图。是由一个非空有限集合和中某些有序对集合构成的二元组，记为。其中是图的顶点集，即事件集合。是图的弧集，就表示第个任务，即任务集合，。

图中即用、、等表示事件，事件的意义表示前面的任务已经完成，后面的任务可以开始。

任务用、、表示，标在箭线上（箭头的方向表示先决关系），同时任务相应的完成时间标也标在对应箭线上。

事件表示工程的开始，事件表示工程的结束，虚线表示工时为0的虚构的任务，仅用于表示各事件间的前行后继关系。

我们在建立计划网络时遵循以下规则：

1）任何任务在网络中用唯一的箭线表示，任何任务其终点事件的编号必须大于其起点事件。

2）两个事件之间只能画一条箭线，表示一项任务。

3）任何计划网络图应有唯一的最初事件和唯一的最终事件。

4）计划网络图不允许出现回路。

5）计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉。

图一。要求最早完成时间，即要求时间最短，和分别表示工程开始时间和工程结束时间。

5.2问题二。

5.2.1使用lingo求解的数学模型。

对于事件和有关系式。

就是指事件之后的事件的发生时间必需大于或等于事件的发生时间和事件与间的最长任务完成时间的和。

由此可转化为数学规划问题。

约束条件：5.2.2使用matlab求解的数学模型。

本问还可以采用另一种思路求解，节点可以开始的最早时间是这个节点所有的紧前事件的最早开始时间加上其节点之间工程耗时的最大值，故得到如下等式：

而节点的最迟开始时间，应该是其紧后工作的最早开始时间减去其事件之间的工序耗时的最小值，即：

根据节点其最早开始时间为0的事实，通过式5.3和5.4可以求出所有活动的最早开始时间和最迟开始时间，而只要到达节点，整个工程就完成了，故节点的最早开始时间和最迟开始时间相等，等于整个工程的完成时间，故得到目标方程：

5.3问题三。

5.3.1使用lingo求解的数学模型。

增加了变量表示任务的最短完成时间，表示任务可能减少的时间以及表示任务缩短一周需要增加的费用，表示优化后的完成周数。

那么根据第一问的结果不优化前的最早完成时间为64周，我们设为计划网络优化后的完成时间。于是总的获利可表示为万元。目标为极大化。

即。同时，可能减少的时间应满足。

目标为极大化。

由此可得到相应的数学规划问题：

5.3.2使用关健路径求解的数学模型。

为了找到能使建筑公司获利的时间安排，需要根据问题二中的关键活动和关键路径。

关键路径的总耗时直接决定了整个工程项目的耗时，如果要想缩短总工期的耗时，必须缩短关健路径上的工程事件的耗时。

在考虑经济效益的方面，缩短时间的前提是获得更大的经济效益，所以只对额外支出费用小于等于3万元的项目进行增加额外支出来缩短时间。从而可以实现在获得经济效益的同时而缩短工期。

根据节点的最迟完成时间是工程完成时间的事实，分析可知，任务的延缓时间即为任务的最迟开始时间与最早开始时间的差值，即：

求得延缓时间后，通过分析同样可以求得公司获利最大前提下各任务工期是怎样提前的，即确定。

最后得到在公司获利最大前提下，完成此工程的时间为：

公司最大利润为由分析确定 (5.8)

六、模型求解。

6.1问题二。

6.1.1使用lingo求解。

采用lingo9.0软件进行规划求解。

step1:将所有事件用形式表示，与相应作业时间并同输入程序；

step2:确定目标函数，;

step3:编程求解（程序见附录）。

求得结果给出了各任务开工时间。其中，表示任务（工地布置）的开工时间是第0周，表示任务的开工时间是第2周，表示任务的开工时间是第26周，等等。综合统计得下表。

表一。每个任务只要按要求得时间开工，则整个工程的最早完成时间为64周。

6.1.2使用matlab 求解。

本问使用matlab求解的步骤如下。

建立各个几点的结构矩阵，其元素表示节点和节点之间的工程项目。如果节点和节点之间没有工程项目，取的值为0，否则取工程项目的耗时。于是得到了结构矩阵：

建立关系矩阵，其中的元素表示各个节点之间是否有项目连接：

得到13个事件节点的关系矩阵：

根据结构矩阵和关系矩阵，结合公式（5.3）和（5.4），我们就可以得到各个节点时间的最早开始时间和最迟开始时间。

程序见附录。

各个节点事件的最早开始时间和最迟开始时间见下表：

表二。根据以上的结果可以得到节点事件的时间，即所有工程项目的完工的时间为64周。

如果某项任务有正的延缓时间，则该任务就有部分机动空间，即稍微迟一点开始也不会使工程完成时间增加。然而，如果某项任务的延缓时间为0，则增加该任务的耗时将必然使工程完成时间增加。因此，关键路径由延缓时间为0的任务组成，即如下节点组成了关键路径：

关键路径所对应的关键活动为：

6.1.3 结果比较。

两种方法求解结果完全相同，最短工期为64周，工程任务开工时间安排见表一。

6.2问题三。

6.2.1使用lingo求解。

对于第二问我们引入了一个参数，用以表示任务的最短完成时间。的求解由原来的完成时间减去相应任务的最大缩短时间。

step1:根据任务作业时间和最大缩短时间计算最短完成时间；

step2:输入所有任务和对应及，任务以有向线段的方式输入，且保证；

step3:确定目标函数与约束条件；

step4: 运行程序求解（程序见附录）。

结果中的表示事件的开始时间，表示优化后的任务作业时间，表示任务缩短的时间。最后的结果表明公司最大可获利8.7万元，工程可缩短到57周完成。

但由于任务的额外开支为3万元，正好等于缩短一周的收入，且任务在关键路径上，所以在用软件求解时未将其考虑为缩短时间的任务，于是分析得最好的结果是将任务的时间缩短到13周。综合得到表三计划：

表三。公司最大获利8.7万元，工程工期缩短至54周。

6.2.2使用matlab和关键路径求解。

通过对问题三的分析，可以得到需要对关键路径上的关键活动来缩短时间，使整体工期缩短，考虑到经济效益，只对额外支出少于3万元的进行选择性的缩短。在对工程缩短时，考虑到关键路径可能发生改变，先假设工程时间缩短的同时，关键路径不发生改变。

可以列如下**进行计算：表四。

数学建模期末

数学建模期末

数学建模期末作业

数学建模期末作业

其他用户还读了