资源描述：
《网络计划问题算法研究及其在实际中的应用【开题报告+文献综述+毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
毕业论文开题报告数学与应用数学网络计划问题算法研究及其在实际中的应用一、选题的背景与意义网络计划技术是随着现代科学技术和工业生产的发展而产生的，20世纪50年代后期出现于美国，目前在工业发达国家已广泛应用，成为一种比较盛行的现代生产管理的科学方法，可以运用计算机进行网络计划绘图、计算优化、分析和控制。许多国家将网络技术用于投标、签订合同及拨款业务；在资源和成本优化等方面应用也较多。美国、日本、德国和俄罗斯等国建筑业公认为是当前最先进的计划管理方法。由于这种方法主要用于进行规划、计划和实施控制，因此，在缩短建设周期、提高工效、降低造价以及提高生产管理水平方面取得了显著的效果。面对日益激烈的市场竞争,企业对市场的快速反应能力直接关系到企业发展的成败与兴衰。这就要求企业在竞标之时预算出产品的最短可行合同期;在施工制造之时工艺流程在时间上的安排要求工序紧密衔接,以求得最短的生产周期。由此运用而生了各种辅助软件及技术,网络计划技术便是其中一种。随着在建筑工程进度管理中应用的越来越广泛,网络计划技术的使用已经不局限于建筑行业。本文就网络计划技术在生产中的运用为例浅谈其组织与管理效力。在算法研究中，我们主要研究的是遗传算法。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法具有“生成+检测”的迭代过程。是一种群体型操作。操作以群体中的所有个体为对象。二、研究的基本内容与拟解决的主要问题：1.针对于网络计划问题的研究现状1.1国内学者研究1.2国外学者研究2.网络计划算法的研究2.1网络计划算法的优化模型2.2遗传算法模型32 3.实例分析3.1优化模型的实例分析3.2遗传算法模型的实例分析4.结论三、研究的方法与技术路线：查阅相关资料，找出网络计划问题算法研究及其在实际中的应用的实例。在指导老师的指导下完成论文。四、研究的总体安排与进度：2010．12—2010．01：查阅相关资料，并做些准备工作。12月19日前完成文献综述和开题报告并交学院审批。2010．01—2010．03：完成论文的基本思路和框架。2010．03—2010．04：4月15号前完成两篇外文的翻译.完成毕业设计（论文）初稿，交指导老师审批、修改。2010．04—2010．06：毕业论文定稿、修改、打印。五、参考文献：[1]《运筹学（修订版）》清华大学出版社2004.9[2]《遗传算法在最优网络计划中的应用》软件导刊2010.7[3]《网络计划在生产管理中的应用》一曙技术2010.4[4]《网络计划技术在招标工作中的应用》福建建设科技2009第6期[5]《网络计划工期优化的分析方法》信息技术教学与研究2010年第33期[6]《施工工程中网络计划的应用》山西建筑2010.3[7]《浅议网络计划技术在应用中存在的问题》电子商务[8]《浅议网络计划技术及其在生产中应用》移动电源与车辆2010年第1期[9]《模糊处理方法在网络计划技术优化问题中的应用》项目管理技术2010.6[10]《基于网络计划图的水电厂运行生产管理》水电厂自动化2010.8[11]《Developingaheuristicalgorithmfororderproductionplanningusingnetworkmodelsunderuncertaintyconditions》ScienceDirect2006[12]《GeneticAlgorithmforContinuousNetworkDesignProblem》ScienceDirect200732 32 毕业论文文献综述数学与应用数学网络计划问题算法研究及其在实际中的应用网络计划技术是随着现代科学技术和工业生产的发展而产生的，20世纪50年代后期出现于美国，目前在工业发达国家已广泛应用，成为一种比较盛行的现代生产管理的科学方法，可以运用计算机进行网络计划绘图、计算优化、分析和控制。许多国家将网络技术用于投标、签订合同及拨款业务；在资源和成本优化等方面应用也较多。美国、日本、德国和俄罗斯等国建筑业公认为是当前最先进的计划管理方法。由于这种方法主要用于进行规划、计划和实施控制，因此，在缩短建设周期、提高工效、降低造价以及提高生产管理水平方面取得了显著的效果.面对日益激烈的市场竞争,企业对市场的快速反应能力直接关系到企业发展的成败与兴衰。这就要求企业在竞标之时预算出产品的最短可行合同期;在施工制造之时工艺流程在时间上的安排要求工序紧密衔接,以求得最短的生产周期。由此运用而生了各种辅助软件及技术,网络计划技术便是其中一种。随着在建筑工程进度管理中应用的越来越广泛,网络计划技术的使用已经不局限于建筑行业。本文就网络计划技术在生产中的运用为例浅谈其组织与管理效力。（一）国外文献综述H.KhademiZare,S.M.T.和FatemiGhomi*,B.Karimi在文章中提出一个实际的以及适当的运算被提供在不确定的情况下为了分批生产计划。用不同的方法生产分批的产品计划正在面临不确定，因此特定的技术被要求来决定他们的产品计划纲要。结合模糊逻辑来定义产品计划以及不确定性的结果的网络模型是合适的工具来解决分批生产计划模型。在这篇论文中，每个活动的开始参量，每个活动的持续时间以及产品生产的网络循环被定义为三角模糊数，并且产品计划的结果被定义为模糊集合。在这片论文中，包括前面的模糊的CPM网络计算被呈现。这个运算的结果是一个模糊分批生产计划。这个方法比现在决定方法的生产计划纲要要更加实际，有很少的计算，有升级和改造的能力。ZHANGGuoqiang,LU32 Jian在文章中也提出了网络设计问题是由道路网络计划得以提升的。对于网络计划问题的算法的研究对于交通运输计划的工程实践是有实际重要的。这篇文章总结了网络设计问题并且解释了对于网络计划问题的算法的研究的复杂性和重要性。作为主要的研究学科，bi级别的程序的数学模型的结构特征已经对于连续的网络设计问题被分析。基于这个现代遗传算法，一个新的算法已经被设计出来特别的来解决连续网络设计问题。采用这个连续网络设计问题作为一个例子来确认，不仅算法有非常好的集合特征，而且算法的最好的解决方法是可信的。这篇文章的方法和观点也可以被应用于其他形式的连续网络设计问题。（一）国内文献王立可和孔大明（2010）提出网络计划技术既是一种科学的计划方法，又是一种有效的生产管理方法。目前水电厂运行生产方面，依然是依据历史经验进行管理。尝试应用网络计划技术分析丰满水电厂的运行生产管理，得到了统筹结果，为提高水电厂运行管理水平打下基础。唐凯和武富庆（2010）提出了针对施工问题，利用网络计划技术对施工作业的时间关系进行了描述。鉴于问题的复杂性，将网络转化成数学方法，建立双目标规划模型，同时采用了模糊数学方法，对模型目标函数进行模糊处理，进而实现对施工的时间、费用优化求解。程宁宁，毛历鹏，包继刚和马巨涛（2010）提出了网络计划技术是一种进度管理的有效技术。随着其在工程建设中应用的日益广泛与深入,它的应用延伸到了各个领域。本文介绍了网络计划技术的主要内容并以制造业的应用为例进行了浅析。丁新平，张怀亮，杨瑞提出了：实践证明，用网络计划技术来安排施工进度计划，在提高建筑企业施工管理水平缩短工期、提高劳动生产率和降低成本等方面效果显著。本文分析了我国网络计划技术应用存在的问题，并提出了一些有益的建议。马德慧（2010）提出了：结合自身工作实践，阐述了网络计划在施工过程中的必要性，对网络计划在实际施工时执行过程中的缺陷和不妥进行了分析与探讨，对其如何改进及进行调整提出了建议，以期更好地指导施工。32 倪洁提出了工期优化过程中主要问题是初始网络计划关键西路的判定及压缩过程中新关键路线的判定，针对现有方法计算量大，设计概念多，理解不便的缺点，在借鉴Dijkatra算法的基础上提出了一种新方法，给出关键线路的判定压缩过程中新关键路线的原理和步骤，最后结合算例加以说明。李少宏（2009）提出了由于业主对工程项目招标业务不熟悉，组织、管理工作不到位，导致招标工作无法按时完成。通过分析招标活动中各项工作的内在联系和规律，提出利用网络计划技术对招标活动进度控制，确保招标工作按时完成。安成莲（2010）提出了分析多品种、小批量生产的企业的特点，介绍网络计划在项目管理中的优势，重点介绍网络计划制定过程及要点梁国希（2010）介绍了遗传算法基本理论，并采用遗传算法进行最优网络计划求解。首先用遗传操作产生众多网络计划方案，然后借用图论方法筛选出各种可行的网络计划，随之计算各网络计划的适应度，最后根据“优胜劣汰”原则通过多次进化得出最优的网络计划。（三）总结国外的一些学者对于网络计划问题的研究是比较具体及详细的，但是对于实际应用方面还是存在着一定的不足。国内的许多学者为了弥补这一问题，在结合理论基础的前提下，加强了对于问题的实际分析使得网络计划问题更加的适用于各个方面。参考文献：[1]《运筹学（修订版）》清华大学出版社2004.9[2]《遗传算法在最优网络计划中的应用》软件导刊2010.7[3]《网络计划在生产管理中的应用》一曙技术2010.4[4]《网络计划技术在招标工作中的应用》福建建设科技2009第6期[5]《网络计划工期优化的分析方法》信息技术教学与研究2010年第33期[6]《施工工程中网络计划的应用》山西建筑2010.3[7]《浅议网络计划技术在应用中存在的问题》电子商务[8]《浅议网络计划技术及其在生产中应用》移动电源与车辆2010年第1期[9]《模糊处理方法在网络计划技术优化问题中的应用》项目管理技术2010.6[10]《基于网络计划图的水电厂运行生产管理》水电厂自动化2010.8[11]《Developingaheuristicalgorithmfororderproductionplanningusingnetworkmodelsunderuncertaintyconditions》ScienceDirect200632 [12]《GeneticAlgorithmforContinuousNetworkDesignProblem》ScienceDirect200732 本科毕业设计（20届）网络计划问题算法研究及其在实际中的应用摘 要【摘要】32 本文介绍了目前常用网络计划技术的算法，探讨了网络计划技术的各种运算模型，对于现有的算法进行一定的改善和优化。在日常生活中面对日益激烈的市场竞争,企业对市场的快速反应能力直接关系到企业发展的成败与兴衰，故往往有很多工程需要网络计划优化，本文应用于一些特定的实例中得出相应的最优结果，通过对于实例中算法的分析比较，给出一定的意见或者建议。【关键词】网络计划技术；国内外学者研究；生产应用；分析案例。32 Abstract【ABSTRACT】Thisarticledescribesthetechniquescurrentlyusedalgorithmofnetworkplanning,networkplanningtechniquediscussedavarietyofcomputingmodels,theexistingalgorithmsforsomeimprovementandoptimization.Intheirdailylivesfaceofincreasinglyfiercemarketcompetition,enterprisesonthemarket'srapidresponsecapabilityisdirectlyrelatedtothesuccessofenterprisedevelopmentandtheriseandfall,sothereareoftenmanyprojectsrequirenetworkplanningoptimization,thisappliestosomespecificexamplestodrawthecorrespondingOptimalresults,forinstancethroughtheanalysisandcomparisonofalgorithms,givesomeadviceorsuggestions.【KEYWORDS】Networkplanningtechnology;Nativeandforeignscholars;productionapplication;analysiscases32 目 录摘 要IIAbstractIII1针对于网络计划问题的研究现状11.1国内学者研究11.1.1发现的优势11.1.2意识到的问题11.1.3对提高网络计划技术的几点措施21.2国外学者研究31.2.1在不确定的情况下使用网络模型的计划对于分批生产的探索式运算的发展31.2.2遗传算法解决连续网络设计问题42网络计划算法的研究52.1网络计划算法的优化模型52.1.1工期优化52.1.2资源优化52.1.3时间和费用优化52.2遗传算法模型62.2.1基本概念72.2.2遗传算法特点73实例分析83.1施工项目进度计划分析83.1.1六时标注法网络计划运算103.1.2网络计划问题的优化算法113.1.3遗传算法解决道路设计问题133.2运算算法比较154结论16参考文献17致谢18附件1932 1针对于网络计划问题的研究现状1.1国内学者研究网络计划技术是随着现代科学技术以及工业生产的发展而产生的，最早于20世纪50年代后期出现于美国，目前在我国已经受到了广泛的关注，称为一种比较盛行的现代生产管理的科学方法，可以运用计算机进行网络计划绘图、计算优化、分析和控制。许多国家将网络技术用于投标、签订合同以及拨款等相关业务；在资源和成本的优化方面也较多。美国、日本、德国和俄罗斯等国建筑业公认为是当前最先进的计划管理方法。由于这种方法主要用于进行规划、计划和实施控制，因此，在缩短建设周期、提高工效、降低造价以及提高生产管理水平方面取得了显著的效果。1.1.1发现的优势我国应用网络计划技术是从20世纪60年代初期开始。著名科学家钱学森将网络计划方法引入我国，并在航天系统应用。著名数学家华罗庚在综合研究各类网络方法的基础上，结合我国实际情况加以简化，于1965年发表了《统筹方法平话》，为推广应用网络计划方法奠定了基础。近几年，随着科技的发展和进步，网络计划技术的应用也日趋得到工程管理人员的重视，且已去的可观的经济效益。如上海宝钢炼铁厂1号高炉土建工程施工中，应用网络法，缩短工期21%，降低成本9.8%。广州白天鹅宾馆在建设中，运用网络计划技术，工期比外商签订的合同提前四个半月，仅投资利息就节约1000万港元。为在我国推广普及网络计划技术，我国建设部公布了《工程网络计划技术规程》，以便统一技术术语、符号、代号和计算规范。特别近几年来，微机的普及和网络计划软件的不断更新换代。这些未在国内大范围推广网络计划技术创造了条件。【1】1.1.2意识到的问题1．应用普及率较低我国现有施工企业的企业素质差别很大，企业发展也很不平衡。江苏省是我国有名的建设大省，据2004年江苏省抽样统计结果显示：自2002年以来，房屋建筑工程施工总承包企业中，特、一级施工企业管理水平相对较高，应用网络计划技术组织施工面达70％以上；二级施工企业，应用网络计划技术组织施工面在40％左右l而三级及其他施工企业技术管理水平较差，应用网络计划技术组织施工面不足20％，且相互抄袭，粗制滥造。【2】32 2．网络计划执行中检查调整不够在网络计划执行过程中，由于外界因素影响而打乱原有计划的事时常发生。网络计划的实施管理应该是一个动态跟踪的过程，施工作业情况千变万化，任何一份网络计划，在实施过程中，都难免“破网”，因此，要随时掌握施工动态，检查计划的执行情况，主动调整资源投入，优化施工方案，这对保证计划目标的实现具有决定性的意义。3．应用深度不够网络计划技术的优点是把施工过程中的各有关工作组成了一个有机的整体，能全面而明确地反映出各项工作之间的相互制约和相互依赖关系。而当前施工网络计划的编制往往只能反映整个项目中各工作单元之间的相互搭接，并没有做到根据施工方法确定工作单元中各项工作之间的相互关系，编制深度不够，更谈不上网络计划的优化。4．网络计划技术与电脑技术结合程度还较低近年来随着计算机的普及及其性能的提高，计算机已逐渐应用到建筑领域的各个角落。无论是工程项目的造价控制、质量控制还是进度控制都离不开计算机作为辅助手段。其中进度控制管理又是项目管理的一项重点工作，因此，有必要将网络计划技术与电脑技术紧密结合起来以实现对项目的动态管理。1.1.1对提高网络计划技术的几点措施在我国，国家鼓励采用先进的科学技术和管理方法提高建设工程质量及其管理水平。如何提高施工企业网络计划技术的应用管理水平是一个急需解决的问题。要解决这个问题，应从源头抓起，并应规范建筑管理体制，更重要的是施工企业自身要从提高市场竞争力的高度，通过全面实施网络计划促进施工企业提高管理质量和水平。【3】1．规范建筑工程管理体制，为应用网络计划技术提供良好的环境(1)加强工程设计管理，合理确定建设工期。通过设立规章制度，提高工程设计的水平，尽量避免设计的频繁变更和建设工期的主观确定。(2)完善项目监理制度。工程监理在监督工程质量的同时，要对工程项目的进度进行监理，保证进度控制与质量控制、投资控制的一致性和协调性。(3)建立严格按网络进度计划拨付工程款的机制。工程款拨付与网络进度计划紧密结合，不仅提高了企业应用网络计划进行施工管理的自觉性，同时也促使网络计划编制更可行。为了实现这种结合，签订施工合同时，应将进度计划中的主要工作与工程款拨付建立对应关系。2．提高认识，注重实效(1)转变观念，充分认识应用网络计划技术的重要性32 将管理科学应用在建筑业发展上，对提高建筑综合效益来说具有特别重大的意义。施工管理中推广应用网络计划方法必将取得多快好省的全面效果，能进一步提高施工管理水平。对于这个问题，企业的领导应该有充分的认识，把应用网络计划技术提到一定的高度，逐步抛弃传统的凭直觉管理的方式，克服困难，投入一定的人力与资金，推动网络计划技术的应用。(2)采用易于直接控制的形式。对大中型工程的进度控制困难的，可在网络计划技术编制和调整进度计划后，转换成横遭图形式去实施，这种做法既有网络一样的严密性，又兼有横道图简单易懂的优点，减少网络计划实施中的阻力。(3)管理人员与技术人员要紧密结合。网络计划的编制与实施是建立在已知的施工方法基础之上的，施工管理人员除了熟知网络计划方法之外，还应了解各项工作的工艺及组织。根据网络计划技术的性质和特点，并非应用网络计划法就一定能任意缩短工期，它只限于给管理人员提供应在哪些工作上合理赶工以及工期与成本的关系等信息，从而使增加的费用最少，成本最低。因此，管理人员制定科学合理的进度控制计划必须与工程技术人员紧密结合。1.1国外学者研究网络计划问题起源于美国，美国政府于1962年规定，凡与政府签订合同的企业，都必须采用网络计划技术，以保证工程进度和质量。1974年麻省理工学院调查指出：“绝大部分美国公司采用网络计划编制施工计划”。目前，美国基本上实现了用计算机绘画、优化计算和资源平衡、项目进度控制，实现了计划工作自动化。以后又提出了新的网络计划技术，例如图示评审技术（GERT），风险评审技术（VERT）等等。【11】1.1.1在不确定的情况下使用网络模型的计划对于分批生产的探索式运算的发展分批生产计划是生产计划管理，产品的评估和选取的主要一部分。不合适和不真实的分批生产项目的生产计划将在现在的预算评估，资源计划以及供给中导致错误，并且在合同中强加惩罚以及在工程项目报告中的不平等以及等等。一个不合适的和分批生产的不真实的计划主要的原因是这些项目的生产计划的合适的技术却不用。分批生产项目的分批计划有特定的特点，这个特点从其他项目例如定义的不确定，工程持续时间以及结果，很多的循环和弹性以及要求特殊技术来决定这些产品的生产计划纲要的项目活动的非循环中分辨出他们。因此，不同的方法包括一步一步，水落，原型，螺旋，急流，平行的方法已经被提供对于分批的项目生产计划。在分批产品项目计划中，我们使用的确定网络技术例如CPM和稀少的随即网络的所有模型。32 使用网络的模糊模型和模糊集的高功能循环网络研究项目的规划合适的工具。这些网络和随机网络在其中随机参数与包括逻辑节点，分支和循环模糊模糊参数取代一样。在此，提出了一种新的方法解决发展循环模糊网络。在此方法中，输入参数包括项目活动网络，确定活动的模糊时间参数，为每个成员的活动程度，循环和循环发生的可能性模糊频率。为此目的，我们使用加法，乘法，最高和最低简单的规则。此方法的输出，包括为项目的生产阶段模糊的时间表。为了评估该方法的有效性和可靠性，它已被应用到循环随机和循环这给了更好的结果模糊网络理论的例子。另外这个方法已应用到实际订单的生产项目，所得结果与其他方法比较接近现实。这种方法的优点在确定性和随机性网络技术如下：1。像循环周期的随机模糊神经网络技术的技术能力有更多的过程中显示的项目，周期和弹性统筹规划，在实施过程中具有确定性网络比较少变化，特别是可能的活动。2。在这一技术，如项目完成时间输出参数是更真实模糊数。此外，这种技术减少了压力和控制项目的进度报告会议和更接近现实。3。较少的信息需求估计与随机方法和使用模糊逻辑参数估计的参数是比较接近现实。4。基金超过随机计算的模糊计算。5。电脑和升级能力，对随机方法的模糊方法和更多的现实生活中的应用。利用模糊数的活动和循环发生的可能性估计，活动时间，灵敏度分析，升级活动网络，成本评估和成果之间的比率估计是发给一提延长此方法。1.1.1遗传算法解决连续网络设计问题网络设计问题是由道路网络计划得以提升的。对于网络计划问题的算法的研究对于交通运输计划的工程实践是有实际重要的。国外很多学者总结了网络设计问题并且解释了对于网络计划问题的算法的研究的复杂性和重要性。作为主要的研究学科，bi级别的程序的数学模型的结构特征已经对于连续的网络设计问题被分析。基于这个现代遗传算法，一个新的算法已经被设计出来特别的来解决连续网络设计问题。采用这个连续网络设计问题作为一个例子来确认，不仅算法有非常好的集合特征，而且算法的最好的解决方法是可信的。【12】对于一个现存的交通网络，在一些新的连接和重建一些连接来提升数量分析的方法的容量的附加的过程中面临的问题被看作为网络设计问题。32 在现在的城镇交通计划的实际中，交通网络计划是一个重要的要用数量分析方法解决的。基于工程经验的基础，许多大量的纲要被计划者提出。这些纲要需要被评估，而且相对于比较好的会被采纳。虽然计划的方法有简单，便利，易于操作优点，但是它的缺点还是非常明显的。从全部计划的选出的最好的计划的质量依赖于可用计划的质量。并且可用的计划呗计划者个人的经验和主观的理解所局限。因此，有这种方法决定的最好的计划应该依靠非常强大的个人成就以及计划质量不能被有效得保证的运输计划者的主观作用。此外，这是非常困难来得到最好的计划，因为有效的计划的数量非常有限，但是可行的计划实际上非常多。在许多有限的计划而不是可行的计划中要选一个最正确的选择，可行的计划是得到真实的最好计划的阻碍，即使有效的计划是科学的和理性的，就像评估的方法是客观的。所以，很多理论研究关于网络设计问题将要克服那些城镇道路网络计划的局限来提升计划和设计的等级来获得计划道路网络的最大效率。网络计划问题对于道路网络计划和设计，以及旅行者行动的分析以及系统化的道路网络的运输效率的评估，这个是提供了一个复杂并且系统的分析工具对于运输网络计划。这里有一个对于运输计划的提升值得考虑的重要。连续网络计划问题是网络计划问题中相对比较复杂的一种形式，并且传统的最优化解法不能太有效的得出结论。随着一串运算的帮助和连续网络计划问题的特征的融合，国外很多学者讨论了遗传运算对于连续网络计划问题的解决以及对于连续网络计划问题的解决方法开启了一盏明灯。1网络计划算法的研究1.1网络计划算法的优化模型绘制网络计划图，计算时间参数和确定关键的线路，仅仅得到一个最初始计划的方案。然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善，最终得到进行网络计划优化。目标是综合考虑进度，合理利用资源，降低费用等等。【4】1.1.1工期优化如果网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度，缩短工程项目的完工工期。主要采取以下的措施，增加对关键工作的投入，一边缩短关键工作的持续时间，实现工期缩短。（1）采取技术措施，提高工效，缩短关键工作的持续时间，使得关键线路的时间缩短。（2）采取组织措施，充分利用非关键工作的宗时差，合理调配人力、物力和资金等资源1.1.2资源优化在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。在项目的工期不变的条件下，均衡地利用资源。实际工程项目包括工作繁多，需要投入资源种类很多，均衡地利用资源是很麻烦的事情，要用计算机来完成，为了建华计算，具体操作如下：1优先安排关键工作所需要的资源。32 1利用非关键工作的总时差，错开个工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。2在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当推迟工程的工期。实现错开高峰的目的。1.1.1时间和费用优化在编制网络计划时，要研究如何是完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需要的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间和费用优化要解决的问题。完成一个项目的费用可以分为两大类：1.直接费用。直接与项目的规模有关的费用，包括材料费用，直接生产工人工资等等。为了缩短工作的持续时间和工期，就需要增加投入，即增加直接费用。2.间接费用。间接费用包括管理费等。一般按照项目工期长度进行分摊，工期越短，分担的间接费用就越少。【5】一般项目的总费用与直接费用、间接费用、项目工期之间存在一定关系，可以用图1表示图中：T1—最短工期，项目总费用最高；T2—最佳工期T3—正常的工期当总费用最少工期短语要求工期时，这就是最佳工期。进行时间和费用优化时，首先要计算出不同工期下最低直接费用率，然后考虑相应的间接费用。费用优化的步骤如下：（1）32 计算工作费用增加率（增加率）。费用增加率是指缩短工作持续时间每一单位时间所需要增加的费用。按照工作的正常持续时间计算各关键工作的费用率，通常可表示为：（1）在网络计划图找出费用率最低的一项关键工作或者一组关键工作作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间，不能成为非关键工作。（2）同时计算相应的增加的总费用，然后考虑由于工期的缩短借鉴费用的变化，在这基础上计算项目的总费用。重复以上步骤，直到获得满意的方案为止。1.1遗传算法模型遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。1.1.1基本概念遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。【6】遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型:式中为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。遗传算法的基本运算过程如下: a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。32 d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。 f)终止条件判断:若tT，则以进化过程中所得到的具有最大适应度个体作最优解输出，终止计算。1.1.1遗传算法特点遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：①首先组成一组候选解；②依据某些适应性条件测算这些候选解的适应度；③根据适应度保留某些候选解，放弃其他候选解；④对保留的候选解进行某些操作，生成新的候选解。【7】 在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法还具有以下几方面的特点：(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。2实例分析2.1施工项目进度计划分析32 网络计划技术是建筑工程施工项目进度计划分析的有力工具，它用网络模型来表示建筑工程施工项目进度过程，对建筑工程施工项目的施工进度进行定量分析、判断，以及实施过程的调整和控制。网络的结构形式表示建筑工程施工项目活动内容及其相互关系，利用网络计划技术的一些算法，可以实现对工程项目中资源的合理安排、进度计划的编制、优化和控制等。【9】根据网络图和各项活动的作业时间，就可以计算出全部网络时间和时差，并确定关键路径。具体计算网络时问并不太难，但比较烦琐，要耗费很多的人力和时问。对此应用模糊数学方法与网络计划技术的结合，可使项目中的多目标优化问题变得相对简单。道路工程结构如图2所示，道路工程值如道路工程移入准备作业获得运输第一阶段第二阶段路面先头后续清除借土准备弃土区开设额外装备涵洞一级配料准备涵洞二级配料铲刮土方铲刮涵洞土方材料处理铺设图2在图2中我们可以清晰的看到完成道路工程所需要的每个步骤，而且在表1中我们根据实际操作以及市场成本价位列举了所有步骤的正常时间、紧凑时间以及差额和差价。本文会通过各种算法对道路工程进行网络优化运算。表1作业序号作业名称正常估算紧凑估算差额差价/（万元/d）时间/d成本/万元时间/d成本/万元时间/d成本/万元1先头移入5155150002额外装备获得15721080581.63涵洞获得308418901260.54一级配料获得202114276615清除1214815.641.60.432 6后续移入684122427第一阶段铲刮246820784102.58借土准备810512.432.40.89弃土区开设463913310装备运输1030734.534.51.511第一阶段土方1125835.8310.83.612第二阶段铲刮91862739313涵洞运输14261033.247.21.814二级配料运输218415108624415第二阶段涵洞1019621.442.40.616路面材料处理12131014210.517第二阶段土方7758.421.40.718路面铺设3535000总计525626.31.1.1六时标注法网络计划运算正常在没有进行网络计划运算的情景下，完成一项普通的道路工程所需要的时间应该是157天到221天之间，所需要的价钱在525万元到626.3万元。明显的可以看出，如果按照正常流程去完成工作无论是价钱还是时间都是不太能够让决策者满意的。那么，如果运用网络计划算法，在一定的时间内同时开展几项工作，虽然成本上没有太大的改变，但是会在时间上缩短相当长的时间。根据表1可以知道每一个步骤的具体时间以及价钱，如何能够更加机动灵活的利用空余时间，调配富余人员，提高操作效率，就需要对操作过程进行详细分析。对应操作需要的总时间相当于网络计划图上的总工期。关键线路指线路上所有工作持续时间总和最长的线路，关键线路的长度就是总工期。在网络计划中六时标注法是最常用的方法，如表2所示。ESEFTFLSLFFF表2六时标注法时间参数示意图ES为工作最早开始时间；EF为工作最早完成时间；LS为工作最迟开始时间；LF为工作最迟完成时间；TF为工作总时差；FF32 为工作自由时差。根据六时标注法可以结合表1数据所示，对于表1数据进行处理，得到表3，这样就可以对该道路工程进行成本、时间优化和计划。表3六时标注法运算结果作业序号估计时间/d开始完成浮时/d紧要作业最早开始时间（ES）最晚开始时间(LS)最早完成时间(EF)最晚完成时间(LF)工作总时差(TF)工作自由时差(FF)1502572021503151830330003030004200820288551257171920665121118707241719414320881135194324229411311535201010101518252830111141435254221292535344410101314302044440014212528464930151044445454001612464958613317754546161001836161646400根据表1、表3及图2，可将道路施工问题绘出作业先后关系网络图(图中数字为作业序号)，如图3所示。图3道路工程作业先后关系网络图32 412314567891013121116151718通过以上的数据分析，运用六时标注法可以得出结论，这个道路施工需要经过64天便可以完成，比起之前的最晚221天整整节省了三分之二的时间，但是成本并没有变化，依旧是最少的525万元。1.1.1网络计划问题的优化算法通过上例可以发现，虽然在施工过程中成本取的是最小的525万元，而且在时间上仅仅花了64天的时间，但是不一定满足决策者的需求，在日常生活中，很多决策者需要采用更少的时间进行一项任务，这样就可以节省出来更多的时间去完成其他项目，这样便可减少机会成本。那么很多学者便考虑所有步骤的时间都采取紧凑时间进行上例运算，便可得到最优化的结果，可是这样也会存在着成本过高的现象，在工作中，往往决策者会采取时间和成本都相对较少的策略去完成一个项目。于是可以利用模糊数学的方法，对于网络计划模型的标准化方程式进行模糊处理。分析计算符号说明：（1）表示网络的系数（i=1,2,3,……18；j=1，2，3，……18）。（2）表示作业i的费用，它与时间成关系（3）表示作业i的时间，表示第i作业的紧凑步骤时间，表示作业i的正常时间。（4）作业i紧凑步骤费用为，作业i的正常费用为（5）作业i的费用系数，为作业i的开始时间。32 对于模型的建立：目标是追求时间最短时的费用最小，也就是当时间最短时费用也最少的双优结果费用是关于时间的一元函数，具体变化为再有，为了判断时间先后，将生产计划网络进行数学化，也就是将网络赋数。当作业i与作业j有关系时，若是正向，则=1；若是反向的，则=-1；当作业i与作业j无直接关系是，那么=0.这样该矩阵A=()18*18与该又向图形成一一对应关系。由网络计划技术条件可知，作业i开始时间必定与作业j有联系，且属于改作业前面的所有作业均完成了，也就是于是建立双目标规划模型将多目标转化成但目标有两种方法：①两者之和最小；②两者之积最小。这两种方法都有其局限性，方法①中的量纲不同；方法②中的时间和费用数字差额太大，难以求出合理的优越点，因此采取模糊数学多目标规划理论来处理，以表示的无条件优化集将上述问题利用模糊数学多目标理论求解（运算过程略），得到最终结果为：最有结果：49天，最优费用：549.60万元。各作业时间如下表：32 作业12345678910时间515242086208417作业1112131415161718总时间时间89112161151491.1.1遗传算法解决道路设计问题要解决本题，首先必须实现图在计算机中的表示，在本文中采用两个二维表(二维数组)来实现图的表示。第一个二维表为点边表。用tabl来表示，它记录了每个点相关的边，tab1的第一个维的长度等于图中节点的个数．tabl的第二个维的长度等于图中拥有最大边数的节点的边数。问题中节点数为18。最大边数为6，二维表一则为tabl[18][6]。第二个二维表为边点表，用tab2来表示，它记录了每条边的起始节点和终止节点，用来表示边的方向，图中共有21条边，所以二维表二为tab[21][2]。遗传过程可由下面几个步骤表示：(1)编码表示：遗传算法的工作对象是字符串(个体)，用以传递计算信息。在本论文中，研究对象为网络图优化，每个个体表示一种优化方案。在编码中，个体采用以二进制字符串进行编码．通过单位长度字符串来表示每条边上缩短的工时。因为每条边上所能缩短的工时不同，所需二进制位长度也不相同。为统一处理，二进制编码单位长度取最大可缩短工时的二进制编码的长度来表示。个体编码长度等于单位长度乘于单位(边)个数。在本图中，最大缩短时间为12，所以要用4位二进制数来表示一条边。图中共有21条边，所以一个个体由28位二进制字符来表示。从左向右按照施工顺序依次编码如下：011000000000010111000100010000100010010000110001001101100011001100110100010000100010(2)群体：遗传过程中，每一代均由众多的个体(字符串)组成，成为群体。群体中个体的数目由用户指定，在本文中群体数目为50。遗传过程是新旧群体的迭代过程，旧的群体完成一系列遗传操作后成为新的群体，在新群体中既包含了旧一代中的优秀个体也包含了交换、突变生成的新的个体。本论文中为了提高群体的收敛性，保存优秀的个体，在每次迭代后增加了一个复制操作．若新一代个体中最大个体适应度小于上一代个体最大适应度，则旧一代最大适应度个体将代替新一代最小适应度个体。第0代的群体，用随机方法产生，在给定的合理方位用均匀分布的随机数任意产生初始个体，作为今后进行计算的基础。随着遗传计算的发展，群体中个体的品质(适应度)逐渐改善，不断产生新的优良个体。32 (3)纠错：由l，2的介绍可以发现单位字符串代表边上缩短的时间，而每条边可缩短的最大时间是不同的。在群体的初始化和遗传操作过程将会有一些不符合要求的个体产生。为了排除不合格个体，在程序中将添加纠错操作，增加了二维表tab3，里面记录了每条边可缩短的最大长度．当每次个体操作后，程序将执行检错操作，检查个体是否合格，若不合格，即大于最大可缩短数．则执行纠错操作。把不合格边改为可缩短的最大数。(4)适应度统计：在本文中，适应度大小f(x)为节省费用大小，它包含两部分a间接费用节省数，b特急工时增加费用，适应度大小为a-b．可以看出是一个最大值问题。在本文中假设间接费用为100万元，工期每缩短一天便可节省间接费用3万元。节省成本=间接费用节省数-特急工时增加的费用=节省时间×间接费用节省斜率-每条工序上节省的时间×每条工序特急费用成本斜率。其中间接费用节省斜率t和每条工序特急费用成本斜率T是固定值，可直接获得。在本文中，选取每个工序(每条边)上节省的时间进行编码．因此每条工序上节省的之间即每条边的编码值B，也可以直接获得。故适应度方程为因此只需求解节省时间数(即特急工时)。特急工时获得是通过建立了一个临时表，保存到每个点的天数，其中到每个点的天数由到这个点的边的边长加上这条边的前一个点的累计天数，当有几条接入边时，比较几个接入边的到该点的累计天数，取最大值，直到最末点，最末点即特急工时。在适应度的计算中，本文将目标函数设为最大值问题．但实际情况为费用越小越好，因此在计算的过程中省去了总费用与节省费用的差值。在运算之前，首先编写目标函数：function[sol,eval]=fitness(sol,options) x=sol(1); eval=x*a-B*T把上述函数存储为fitness.m文件并放在工作目录下(5)选择操作：本文中遗传算子中的复制、交换、突变的对个体的选取都是通过选择操作得到的，在程序中选择函数返回一个群体大小为种子的随机数，该返回数即被选中个体的位置数。新群体都将由选择操作在旧一代中选取，直至新群体被全部生成。(6)32 变异操作：在本文中，研究的对象为网络图，单位长度字符代表每条边上缩短的时间长度，为了使每条边被考虑到．因而采用了直接突变的方法。由于突变的量较大，涉及到每个字符，在设计中突变被贯穿在了复制和交换的每个字符的操作过程中，这样即可以节省代码，也提高了效率。(7)复制和交换操作：复制和交换操作在由选择操作选取的个体根据交换概率，通过随机数判断是否执行交换操作，如果执行交换操作，通过随机数获的交换点，执行交换操作。如果执行复制操作，则交换点设为最后一位，这样既节省了代码．又提高了效率。同时变异操作贯穿在复制与交换操作的每个位操作，完成遗传操作。(8)终止条件：本文采用两种终止条件联合作用来决定迭代何时终止：a．规定最大迭代代数，当迭代次数达到最大迭代代数时．停止迭代运算：b．控制最大适应度与平均适应度之间的偏差，通过在遗传运算前设定最大偏差§，当最大适应度与平均适应度之间的偏差小于或等于最大偏差§时，即停止迭代运算。通过以上两种终止条件联合采用，可及时、有效地得出合理运算结果。Matlab7．0中包含一个专门设计的遗传算法与直接搜索工具箱。使用该工具箱可以扩展优化工具箱在处理优化问题方面的能力，可以处理传统优化技术难以解决的问题，包括难以定义或不方便数学建模的问题，还可以解决目标函数复杂的问题，比如目标函数不连续或具有高度的非线性、随机性以及目标函数不可微的情况。根据以上八个步骤，采用Matlab7．0中的遗传算法运算10次，将相应的数据输入之后可得到以下数据：次数12345678910X14.574314.354714.469814.436714.269314.364514.482414.372614.323414.2464F(X)39.243739.245939.264339.134639.254139.147939.358739.258239.238639.3741故可节省的费用大小最优解为39万元。故通过遗传算法，通过考虑间接成本，所得到的最优成本为586万元，最优时间为50天。1.1运算算法比较通过对以上三种算法对于同一个事例的分析比较，可以看出每一种算法对于同一种情况都有其优缺点：32 （1）六时标注法的算法简便，容易上手，是在平日工作生活中更倾向于采用的方法，更加容易被广大的决策者所应用，但是相对于其他两种算法，所得到的结果并不是最优的结果，而且考虑的可能存在的参数少，在今后工作中的可变性大，在本文中，虽然可以得到相对最优的64天的时间，但是并没有考虑成本问题。（2）网络计划优化模型的算法相对来说有些难度，需要有一定的数学基础的决策者才可以完成，得到的结果相对来说是比较合理的，但是由于其难度大，并没有在日常生活中广泛应用，而且考虑的参数变量并不是非常的全面，在本文中，通过应用模糊数学将时间与成本模糊处理，得到优化的最优时间为49天，最优成本为549.6万元。（3）遗传算法的应用范围非常的广泛，无论是在道路设计还是优化工作流程中都是可以应用的，所得到的结果往往也是最优结果，对于参数变量考虑的因素也比以上两种算法要全面，但是由于其运算难度大，需要数学基础高，故并没有被很多的决策者使用，恰恰会第一时间被舍弃。在本文中，加入考虑了间接成本，使得考虑因素更加全面，故得到最优的结果为586万元和50天。1结论网络计划问题现在正在逐渐的被许多国家和地区的人民所接受，应用与非常广泛的范围，其应用性强，易操作的特点非常符合社会需求，通过以上对于各个模型的应用可以看出，无论是在道路设计问题还是在简化工作流程的方面，网络计划算法都起到了非常重要的作用。在本文中，通过对同一个实例的三种算法的探讨可以看出，现在对于网络计划问题的算法很多决策者并不能够完全掌握，应用于实际生活中的结果往往并不是最优结果。当然对于网络计划问题的算法研究还是需要通过以后的学习与探索去进一步的研究，毕竟目前的算法还不完善，还有许多问题还待解决。32 参考文献[1]《运筹学（修订版）》清华大学出版社2004.9[2]《遗传算法在最优网络计划中的应用》软件导刊2010.7[3]《网络计划在生产管理中的应用》一曙技术2010.4[4]《网络计划技术在招标工作中的应用》福建建设科技2009第6期[5]《网络计划工期优化的分析方法》信息技术教学与研究2010年第33期[6]《施工工程中网络计划的应用》山西建筑2010.3[7]《浅议网络计划技术在应用中存在的问题》电子商务[8]《浅议网络计划技术及其在生产中应用》移动电源与车辆2010年第1期[9]《模糊处理方法在网络计划技术优化问题中的应用》项目管理技术2010.6[10]《基于网络计划图的水电厂运行生产管理》水电厂自动化2010.8[11]《Developingaheuristicalgorithmfororderproductionplanningusingnetworkmodelsunderuncertaintyconditions》ScienceDirect2006[12]《GeneticAlgorithmforContinuousNetworkDesignProblem》ScienceDirect200732 附件遗传算法程序functionyouhuafunD=code;N=50; %Tunablemaxgen=50; %Tunablecrossrate=0.5;%Tunablemuterate=0.08;%Tunablegeneration=1; num=length(D);fatherrand=randint(num,N,3);score=zeros(maxgen,N);whilegeneration<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end));% 多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp;%%两点交叉% forkk=1:(N-2)/2% rndtmp=randint(1,1,num)+1;% tmp=A(1:rndtmp,kk);% A(1:rndtmp,kk)=B(1:rndtmp,kk);% B(1:rndtmp,kk)=tmp;% end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd [m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3);% fatherrand(ind)=tmp; 32 %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); fork=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(tmpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1;end%scoremaxV=max(score,[],2);minV=11*300-maxV;plot(minV,'*');title('各代的目标函数值');F4=D(:,4);FF4=F4-fatherrand(:,1);FF4=max(FF4,1);D(:,5)=FF4;saveDDataDfunctionD=codeloadyouhua.mat%propertiesF2andF3F1=A(:,1);F2=A(:,2);F3=A(:,3);if(max(F2)>1450)||(min(F2)<=900) error('DATApropertyF2exceedit''srange(900,1450]')end%getgrouppropertyF1ofdata,accordingtoF2valueF4=zeros(size(F1));forite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite;endD=[F1,F2,F3,F4];32 functionScoreN=scorefun(fatherrand,D)F3=D(:,3);F4=D(:,4);N=size(fatherrand,2);FF4=F4*ones(1,N);FF4rnd=FF4-fatherrand;FF4rnd=max(FF4rnd,1);ScoreN=ones(1,N)*300*11;%这里有待优化fork=1:N FF4k=FF4rnd(:,k); forite=1:11 F0index=find(FF4k==ite); if~isempty(F0index) tmpMat=F3(F0index); tmpSco=sum(tmpMat); ScoreBin(ite)=mod(tmpSco,300); end end Scorek(k)=sum(ScoreBin);endScoreN=ScoreN-Scorek;32
