数学建模网络优化

2011甘肃农业大学第八届大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）： 甘肃农业大学 参赛队员 (打印并签名) ：1. 周小雄 2. 崔起飞 3. 杨慧珍

日期： 2012 年 5 月 29 日

指导教师或指导教师组负责人 (打印并签名)：

赛区评阅编号（由赛区组委会评阅前进行编号）：

摘要

本文研究的是工程施工工期的优化问题，使用了网络优化模型，通过对网络关键路径的分析和改进，采用两种方法进行求解并比较结果，得到了工程最短工期和公司利润最大情况下的最优施工方案。

对于问题一，根据各个任务之间的联系，绘制了双代号网络图，采用用点代表事件，点之间的有向线段代表任务，虚线段代表先决关系的虚工作，虚工作的耗时为0, 清楚的表示出了任务之间的施工进程。

第二问求解时，本文采用的方法一是建立工期最短的目标方程和以先行后继关系为约束的条件，将问题转换为最优解问题；方法二是通过求解工程各个事件的最早开始和最迟开始时间，得到最后一个事件的完成时间则为工程最短工期。两种方法求解出的结果相同，工程最短工期均为64周。

在问题二的基础上，问题三需要在公司利润最大化的情况下缩短工期，方法一在问题二的基础上改变了目标函数为公司利润，以缩短关键路径为手段。在缩短关键路径时，涉及到关键路径可能改变问题，对此，本文将目标函数设置成总周期的减少除去额外费用，这样避免了在求解过程中易出现的非关键路径的缩短而浪费资源的情况，也解决了关键路径可能改变的问题，同样将问题转换为了最优解问题。在方法二中，先假设对关键路径进行缩短，关键路径不发生改变。再联系缩短任务耗时所需的成本分析工程该如何缩短工期，最终得到最优施工方案。将最优施工方案检验，发现缩短周期后关键路径并没有发生改变。两种方法求得的结果相同，公司最大利润为8.7万元，工程工期缩短到54周。

整个问题最大的困难就是缩短时间可能发生的关键路径的改变从而引起的错误判断，本文模型最大的优势就是由于适当的设置了目标函数，从而避免了这个问题的发生。通过两种方法比较使用进行求解，以及不同方法的相互验证，确保了施工方案的最优化和公司利益的最大化。

关键词：双代号网络图、最优解、关键路径、最大获利

1

一、问题重述

某市政府决定修建一个小型体育馆，通过竞标，一家本地建筑公司获得此项工程，并且希望尽快完成工程。表中列出了工程中的主要任务，时间以周计算。有些任务只有在某任务完成后才能进行。需要解决的问题是： 问题一：绘制各任务间的关系图。 问题二：工程最早完成时间。

问题三：市政府希望能够提前完工，为此向建筑公司提出工期每缩短一周，则可支付3万元奖励。为缩短工期，建筑公司需要雇用更多的工人，并租借更多设备（表中额外支出部分）。设计施工方案使建筑公司的获利最大。

二、基本假设

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

因素的影响。

2. 所有工程任务需要且必须在满足先决条件的情况下即可立即开始。 3. 每周额外支出费用是指工期每缩短一周所支出的费用。

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

5. 市政府希望尽早完成工程，建筑公司以在利益最大的情况下也以尽早完成工

程为目标。

三、符号说明与名词解释

3.1符号说明

vi：表示第i个事件，i?1,2...13；

xi：表示事件vi的开始时间，i?1,2...13； tij：是事件(vi,vj)间最长任务完成的时间，i,j?1,2...13；

mi：完成任务i的最短完成时间，i?1,2...18； yi：任务i可能减少的完成时间，i?1,2...18； ci：任务i每缩短一周所需的额外费用，i?1,2...18； di：任务ei的持续时间，i?1,2...18； bi：任务ei的延缓时间，i?1,2...18；

fi：任务ei可以缩短的最大工时，i?1,2...18； A：各个事件之间的结构矩阵； X：各个事件之间的关系矩阵；

ESi：任务ei可以开始的最早时间，i?1,2...18；

2

EFi：任务ei可以完成的最早时间，i?1,2...18；

LSi：任务ei在不增加耗时的情况下可以开始的最迟时间，i?1,2...18； LFi：任务ei在不增加耗时的情况下可以完成的最迟时间，i?1,2...18；

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

T'：在需要前提完工和公司获利最大的前提下，最早完成此工程的时间。 3.2名词解释

1. 关键路径：关键路径是指网络终端元素的元素的序列，该序列具有最长的总

工期并决定了整个项目的最短完成时间。

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

3. 直接后继：每项任务对应的一组必须在该任务完成之后才能开始的任务。 4. 事件：事件的意义是表示以它为后继的任务已经完成，以它为前驱的任务可

以开始。

T四、问题分析

4.1问题一

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

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

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

工程总时间的缩短?奖励资金—任务缩短时间?额外支出费用，

从而避免了此问题的发生。依旧可通过两种方法的相互比较验证得到最优化的施工方案。

五、模型建立

5.1绘制工程双代号网络图

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

据此我们需要绘出整个工程的计划网络图G。G是由一个非空有限集合V和V中某些有序对集合E构成的二元组，记为G?(V,E)。其中V?{v1,v2...v13}是图G的顶点集，即事件集合。E?{e1,e2..e18}是图G的弧集，ei就表示第i个任务，即任务集合，。

3

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

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

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

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

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

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

（3）任何计划网络图应有唯一的最初事件和唯一的最终事件。 （4）计划网络图不允许出现回路。

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

图一

要求最早完成时间，即要求x13?x1时间最短，x13和x1分别表示工程开始时间和工程结束时间。 5.2问题二

5.2.1使用Lingo求解的数学模型

对于事件vi和vj(j?i)有关系式

xj?xi?tij

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

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

4

本文来源：https://www.bwwdw.com/article/73k2.html