网络优化数学建模论文实例

1摘要本文研究的是工程施工工期的优化问题，使用了网络优化模型，通过对网络关键路径的分析和改进，采用两种方法进行求解并比较结果，得到了工程最短工期和公司利润最大情况下的最优施工方案。对于问题一，在首先将问题转换为直观的AOE网络图模型，采用点代表事件，有向线段代表任务的有向网络图的方式，并且设置虚线段表明各任务的先决关系，清晰地表示出了任务的施工进程。求解时，本文采用的方法一是建立工期最短的目标方程和以先行后继关系为约束的条件，将问题转换为数学规划问题；方法二是通过求解工程各个任务的最早开始和最早完成时间，得到最后一个任务的最早完成时间则为工程最短工期。两种方法求解出的结果相同，工程最短工期为64周。在问题一的基础上，问题二需要在公司利润最大化的情况下缩短工期，方法一在问题一的基础上改变了目标函数为公司利润，以缩短关键路径为手段。在缩短关键路径时，涉及到关键路径可能改变问题，对此，本文将目标函数设置成总周期的减少除去额外费用，这样避免了在求解过程中易出现的非关键路径的缩短而浪费资源的情况，也解决了关键路径可能改变的问题，同样将问题转换为了数学规划问题。在方法二中，采用了求解出工程各个任务延缓时间的方法来确定工程的关键路径，再联系缩短任务耗时所需的成本分析工程该如何缩短工期，最终得到最优施工方案。两种方法求得的结果相同，公司最大利润为8.7万元，工程工期缩短到54周。整个问题最大的困难就是缩短时间可能发生的关键路径的改变从而引起的错误判断，本文模型最大的优势就是由于适当的设置了目标函数，从而避免了这个问题的发生。通过两种方法比较使用进行求解，以及不同方法的相互验证，确保了施工方案的最优化和公司利益的最大化。关键词:AOE网络、计划网络优化、关键路径、最大获利2一、问题重述某商业集团准备修建一个大卖场，通过竞标，一家建筑公司获得此项工程，并且希望尽快完成工程。表中列出了工程中的主要任务，时间以周计算。有些任务只有在某任务完成后才能进行。需要解决的问题是：问题一.工程最早完成时间。问题二.商业集团希望能够提前完工，为此向建筑公司提出工期每缩短一周，则可支付3万元奖励。为缩短工期，建筑公司需要雇用更多的工人，并租用更多设备（表中额外支出部分）。设计施工方案使建筑公司的获利最大。二、基本假设1.题中所给的完成各项工程任务的时间是准确不变的，不受各种自然、非自然因素的影响。2.所有工程任务需要且必须在满足先决条件的情况下即可立即开始。3.每周额外支出费用是指工期每缩短一周所支出的费用。4.缩短施工时间的任务在除额外支出费用外的原来的总施工费用不变。5.商业集团希望尽早完成工程，建筑公司以在利益最大的情况下也以尽早完成工程为目标。三、符号说明与名词解释3.1符号说明iv：表示第i个事件，1,2...13i；ix：表示事件iv的开始时间，1,2...13i；ijt：是事件(,)ijvv间最长任务完成的时间，,1,2...13ij；im：完成任务i的最短完成时间，1,2...18i；iy：任务i可能减少的完成时间，1,2...18i；ic：任务i每缩短一周所需的额外费用，1,2...18i；id：任务ie的持续时间，1,2...18i；ib：任务ie的延缓时间，1,2...18i；if：任务ie可以缩短的最大工时，1,2...18i；iES：任务ie可以开始的最早时间，1,2...18i；iEF：任务ie可以完成的最早时间，1,2...18i；3iLS：任务ie在不增加耗时的情况下可以开始的最迟时间，1,2...18i；iLF：任务ie在不增加耗时的情况下可以完成的最迟时间，1,2...18i；T：在不需要提前完工的前提下，最早完成此工程的时间；'T：在需要前提完工和公司获利最大的前提下，最早完成此工程的时间。3.2名词解释1.关键路径：网络节点元素的元素序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。2.直接前驱：每项任务对应的一组必须在该任务开始之前完成的任务。3.直接后继：每项任务对应的一组必须在该任务完成之后才能开始的任务。4.事件：事件的意义是表示以它为后继的任务已经完成，以它为前驱的任务可以开始。四、问题分析4.1问题一根据题意，本问是在不考虑缩短完成任务时间的情况下求解工程最短工期的问题。本文把所有任务按先决条件的相互关系绘制成单向AOE网络图，以节点代表工程事件，以节点间的有向线段代表工程任务，本问即被转换为了求解此网络关键路径的问题，关键路径上所有任务的时间总合就是此工程最早完工时间。可以采用线性规划和网络最短路径两种方法求解。4.2问题二在第一问的基础上，第二问是一个计划网络优化问题。要想缩短工程工期，必须缩短关键路径上任务的耗时。但是由于任务施工时间的缩短可能导致关键路径的改变，从而可能引发非关键路径缩短而浪费资源的问题，于是本文通过增加松驰变量来表示可能缩短的周数，以工程总时间的缩短为另一变量，通过设置目标函数为工程总时间的缩短奖励资金—任务缩短时间额外支出费用，从而避免了此问题的发生。依旧可通过两种方法的相互比较验证得到最优化的施工方案。五、模型建立5.1绘制工程计划网络图本文重新把附录表一数据进行编码，将各任务用字母加下标代替，如附录表二所示，ie即表示第i个任务。据此我们需要绘出整个工程的计划网络图G。G是由一个非空有限集合V和V中某些有序对集合E构成的二元组，记为(,)GVE。其中1213{,...}Vvvv是图G的顶点集，即事件集合。1218{,..}Eeee是图G的弧集，ie就表示第i个任务，即任务集合，。图中即用1v、2v、3v等表示事件，事件的意义表示前面的任务已经完成，后面的任务可以开始。4任务用1e、2e、3e表示，标在箭线上（箭头的方向表示先决关系），同时任务相应的完成时间标也标在对应箭线上。事件1v表示工程的开始，事件13v表示工程的结束，虚线表示工时为0的虚构的任务，仅用于表示各事件间的前行后继关系。我们在建立计划网络时遵循以下规则：（1）任何任务在网络中用唯一的箭线表示，任何任务其终点事件的编号必须大于其起点事件。（2）两个事件之间只能画一条箭线，表示一项任务。（3）任何计划网络图应有唯一的最初事件和唯一的最终事件。（4）计划网络图不允许出现回路。（5）计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉。图一要求最早完成时间，即要求131xx时间最短，13x和1x分别表示工程开始时间和工程结束时间。5.2问题一5.2.1使用Lingo求解的数学模型对于事件iv和jv()ji有关系式jiijxxt就是指iv事件之后的jv事件的发生时间必需大于或等于iv事件的发生时间和事件iv与jv间的最长任务完成时间的和。由此可转化为数学规划问题131minxx约束条件：,1,2...130,1,2...13jiijixxtijxi55.2.2使用Excel求解的数学模型本问还可以采用另一种思路求解，某项任务ie可以结束的最早时间是这项任务可以开始的最早时间加上其耗时，故得到如下等式：iiiEFESd（5.3）而某项任务i直到其所有前驱都完成之后才能开始，因此任务i可以开始的最早时间是其直接前驱最早完成时间中的最大值，即：max()iiESEF（5.4）这里的最大值是针对任务ie的所有直接前趋而言的。根据1v节点其最早开始时间为0的事实，通过式5.3和5.4可以求出所有活动的最早开始时间和最早完成时间，而只要到达13v节点，整个工程就完成了，故13v节点的最早开始时间即为整个工程的完成时间，故得到目标方程：13TES（5.5）5.3问题二5.3.1使用Lingo求解的数学模型增加了im变量表示任务ie的最短完成时间，iy表示任务ie可能减少的时间以及ic表示任务ie缩短一周需要增加的费用，d表示优化后的完成周数。那么根据第一问的结果不优化前的最早完成时间为64周，我们设d为计划网络优化后的完成时间。于是总的获利可表示为3*(64)*iidcy万元。目标为极大化3*(64)*iidcy。事件iv与jv()ji间的关系应是事件jv的开始时间减去事件iv的开始时间应大于原来两任务间最长任务的完成时间的ijt的减去可能缩短的时间iy，即jiijixxty。同时，可能减少的时间iy应满足0iijiytm。目标为极大化(3*)iiiycy。由此可得到相应的数学规划问题：max(3*)iiiycy..st0,,1,2...13,,,1,2...18jiiijiijiijiiixxytytmijxymi其中t而65.3.2使用Excel求解的数学模型为了找到能使建筑公司获利的时间安排，就要找出关键活动和关键路径。而明显在不增加任务耗时的情况下，某项任务i可以开始的最迟时间是这项任务可以结束的最迟时间减去其耗时，故得到如下等式：iiiLSLFd（5.8）稍加分析可知，某项任务i可以完成的时间是其所有后继节点最迟开始时间中的最小值，即：miniiLFLS（5.9）这里的最小值是针对任务ie的所有直接后继而言的。根据13v节点的最迟完成时间是工程完成时间的事实，通过式5.8和5.9可以求出所有活动的最迟开始时间和最迟完成时间。分析可知，任务ie的延缓时间即为任务ie的最迟开始时间与最早开始时间的差值，即:iiibLSES(5.10)求得延缓时间后，通过分析同样可以求得公司获利最大前提下各任务工期是怎样提前的，即确定if。最后得到在公司获利最大前提下，完成此工程的时间为：'iTTf（5.11）公司最大利润为：(3)if，i由分析确定(5.12)六、模型求解6.1问题一6.1.1使用Lingo求解采用Lingo9.0软件进行规划求解。step1:将所有事件用(,)ij形式表示，与相应作业时间并同输入程序；step2:确定目标函数，131minxx;step3:编程求解（程序见附录）。求得结果给出了各任务开工时间。其中，10x表示任务1e（工地布置）的开工时间是第0周，22x表示任务2e的开工时间是第2周，526x表示任务71015,,eee的开工时间是第26周，等等。综合统计得下表。任务开工时间(周)任务开工时间（周）71e08911,,eee432e213e283414,,eee1812e525e2716e4671015,,eee2617e546e3718e63每个任务只要按要求得时间开工，则整个工程的最早完成时间为64周。6.1.2使用Excel求解本问使用Excel求解的步骤如下：建立输入任务名称、标记、直接前趋、直接后继、耗时、最早开始时间、最早结束时间、最迟开始时间、最迟结束时间、延缓时间的表格（见附录表三），在相应表格中输入约束条件和目标函数的计算式，计算求解得到结果。故得到所有任务的最早开始和完成时间，如下表二：任务最早开始时间（周）最早完成时间（周）1e022e2183e18274e18265e27376e37437e26288e43459e435210e263111e4346812e525413e282914e182515e263016e464917e546318e6364表二故工程完成的最短时间为64周。6.1.3结果比较两种方法求解结果完全相同，最短工期为64周，工程任务开工时间安排见表一。6.2问题二6.2.1使用Lingo求解对于第二问我们引入了一个参数im，用以表示任务ie的最短完成时间。im的求解由原来的完成时间ijt减去相应任务的最大缩短时间。Step1:根据任务作业时间ijt和最大缩短时间计算最短完成时间im；Step2:输入所有任务ie和对应ijt及im，任务ie以有向线段的方式输入，且保证ji；Step3:确定目标函数与约束条件；Step4:运行程序求解（程序见附录）。结果中的ix表示事件i的开始时间，ijt表示优化后的任务作业时间，iy表示任务ie缩短的时间。最后的结果表明公司最大可获利8.7万