1、本科毕业设计（20届）网络计划问题算法研究及其在实际中的应用所在学院专业班级数学与应用数学学生姓名学号指导教师职称完成日期年月I摘要【摘要】本文介绍了目前常用网络计划技术的算法，探讨了网络计划技术的各种运算模型，对于现有的算法进行一定的改善和优化。在日常生活中面对日益激烈的市场竞争,企业对市场的快速反应能力直接关系到企业发展的成败与兴衰，故往往有很多工程需要网络计划优化，本文应用于一些特定的实例中得出相应的最优结果，通过对于实例中算法的分析比较，给出一定的意见或者建议。【关键词】网络计划技术；国内外学者研究；生产应用；分析案例。IIABSTRACT【ABSTRACT】THISARTICLEDE
2、SCRIBESTHETECHNIQUESCURRENTLYUSEDALGORITHMOFNETWORKPLANNING,NETWORKPLANNINGTECHNIQUEDISCUSSEDAVARIETYOFCOMPUTINGMODELS,THEEXISTINGALGORITHMSFORSOMEIMPROVEMENTANDOPTIMIZATIONINTHEIRDAILYLIVESFACEOFINCREASINGLYFIERCEMARKETCOMPETITION,ENTERPRISESONTHEMARKETSRAPIDRESPONSECAPABILITYISDIRECTLYRELATEDTOTHE
3、SUCCESSOFENTERPRISEDEVELOPMENTANDTHERISEANDFALL,SOTHEREAREOFTENMANYPROJECTSREQUIRENETWORKPLANNINGOPTIMIZATION,THISAPPLIESTOSOMESPECIFICEXAMPLESTODRAWTHECORRESPONDINGOPTIMALRESULTS,FORINSTANCETHROUGHTHEANALYSISANDCOMPARISONOFALGORITHMS,GIVESOMEADVICEORSUGGESTIONS【KEYWORDS】NETWORKPLANNINGTECHNOLOGYNAT
4、IVEANDFOREIGNSCHOLARSPRODUCTIONAPPLICATIONANALYSISCASESIII目录摘要IABSTRACTII1针对于网络计划问题的研究现状111国内学者研究1111发现的优势1112意识到的问题1113对提高网络计划技术的几点措施212国外学者研究3121在不确定的情况下使用网络模型的计划对于分批生产的探索式运算的发展3122遗传算法解决连续网络设计问题42网络计划算法的研究521网络计划算法的优化模型5211工期优化5212资源优化5213时间和费用优化522遗传算法模型6221基本概念7222遗传算法特点73实例分析831施工项目进度计划分析8311六
5、时标注法网络计划运算9312网络计划问题的优化算法11313遗传算法解决道路设计问题1332运算算法比较154结论16参考文献17致谢错误未定义书签。附件181针对于网络计划问题的研究现状11国内学者研究网络计划技术是随着现代科学技术以及工业生产的发展而产生的，最早于20世纪50年代后期出现于美国，目前在我国已经受到了广泛的关注，称为一种比较盛行的现代生产管理的科学方法，可以运用计算机进行网络计划绘图、计算优化、分析和控制。许多国家将网络技术用于投标、签订合同以及拨款等相关业务；在资源和成本的优化方面也较多。美国、日本、德国和俄罗斯等国建筑业公认为是当前最先进的计划管理方法。由于这种方法主要用
6、于进行规划、计划和实施控制，因此，在缩短建设周期、提高工效、降低造价以及提高生产管理水平方面取得了显著的效果。111发现的优势我国应用网络计划技术是从20世纪60年代初期开始。著名科学家钱学森将网络计划方法引入我国，并在航天系统应用。著名数学家华罗庚在综合研究各类网络方法的基础上，结合我国实际情况加以简化，于1965年发表了统筹方法平话，为推广应用网络计划方法奠定了基础。近几年，随着科技的发展和进步，网络计划技术的应用也日趋得到工程管理人员的重视，且已去的可观的经济效益。如上海宝钢炼铁厂1号高炉土建工程施工中，应用网络法，缩短工期21，降低成本98。广州白天鹅宾馆在建设中，运用网络计划技术，工
7、期比外商签订的合同提前四个半月，仅投资利息就节约1000万港元。为在我国推广普及网络计划技术，我国建设部公布了工程网络计划技术规程，以便统一技术术语、符号、代号和计算规范。特别近几年来，微机的普及和网络计划软件的不断更新换代。这些未在国内大范围推广网络计划技术创造了条件。【1】112意识到的问题1应用普及率较低我国现有施工企业的企业素质差别很大，企业发展也很不平衡。江苏省是我国有名的建设大省，据2004年江苏省抽样统计结果显示自2002年以来，房屋建筑工程施工总承包企业中，特、一级施工企业管理水平相对较高，应用网络计划技术组织施工面达70以上；二级施工企业，应用网络计划技术组织施工面在40左右
8、L而三级及其他施工企业技术管理水平较差，应用网络计划技术组织施工面不足20，且相互抄袭，粗制滥造。【2】2网络计划执行中检查调整不够在网络计划执行过程中，由于外界因素影响而打乱原有计划的事时常发生。网络计划的实施管理应该是一个动态跟踪的过程，施工作业情况千变万化，任何一份网络计划，在实施过程中，都难免“破2网”，因此，要随时掌握施工动态，检查计划的执行情况，主动调整资源投入，优化施工方案，这对保证计划目标的实现具有决定性的意义。3应用深度不够网络计划技术的优点是把施工过程中的各有关工作组成了一个有机的整体，能全面而明确地反映出各项工作之间的相互制约和相互依赖关系。而当前施工网络计划的编制往往只
9、能反映整个项目中各工作单元之间的相互搭接，并没有做到根据施工方法确定工作单元中各项工作之间的相互关系，编制深度不够，更谈不上网络计划的优化。4网络计划技术与电脑技术结合程度还较低近年来随着计算机的普及及其性能的提高，计算机已逐渐应用到建筑领域的各个角落。无论是工程项目的造价控制、质量控制还是进度控制都离不开计算机作为辅助手段。其中进度控制管理又是项目管理的一项重点工作，因此，有必要将网络计划技术与电脑技术紧密结合起来以实现对项目的动态管理。113对提高网络计划技术的几点措施在我国，国家鼓励采用先进的科学技术和管理方法提高建设工程质量及其管理水平。如何提高施工企业网络计划技术的应用管理水平是一个
10、急需解决的问题。要解决这个问题，应从源头抓起，并应规范建筑管理体制，更重要的是施工企业自身要从提高市场竞争力的高度，通过全面实施网络计划促进施工企业提高管理质量和水平。【3】1规范建筑工程管理体制，为应用网络计划技术提供良好的环境1加强工程设计管理，合理确定建设工期。通过设立规章制度，提高工程设计的水平，尽量避免设计的频繁变更和建设工期的主观确定。2完善项目监理制度。工程监理在监督工程质量的同时，要对工程项目的进度进行监理，保证进度控制与质量控制、投资控制的一致性和协调性。3建立严格按网络进度计划拨付工程款的机制。工程款拨付与网络进度计划紧密结合，不仅提高了企业应用网络计划进行施工管理的自觉性
11、，同时也促使网络计划编制更可行。为了实现这种结合，签订施工合同时，应将进度计划中的主要工作与工程款拨付建立对应关系。2提高认识，注重实效1转变观念，充分认识应用网络计划技术的重要性将管理科学应用在建筑业发展上，对提高建筑综合效益来说具有特别重大的意义。施工管理中推广应用网络计划方法必将取得多快好省的全面效果，能进一步提高施工管理水平。对于这个问题，企业的领导应该有充分的认识，把应用网络计划技术提到一定的高度，逐步抛弃传统的凭直觉管理的方式，克服困难，投入一定的人力与资金，推动网络计划技术的应用。32采用易于直接控制的形式。对大中型工程的进度控制困难的，可在网络计划技术编制和调整进度计划后，转换
12、成横遭图形式去实施，这种做法既有网络一样的严密性，又兼有横道图简单易懂的优点，减少网络计划实施中的阻力。3管理人员与技术人员要紧密结合。网络计划的编制与实施是建立在已知的施工方法基础之上的，施工管理人员除了熟知网络计划方法之外，还应了解各项工作的工艺及组织。根据网络计划技术的性质和特点，并非应用网络计划法就一定能任意缩短工期，它只限于给管理人员提供应在哪些工作上合理赶工以及工期与成本的关系等信息，从而使增加的费用最少，成本最低。因此，管理人员制定科学合理的进度控制计划必须与工程技术人员紧密结合。12国外学者研究网络计划问题起源于美国，美国政府于1962年规定，凡与政府签订合同的企业，都必须采用
13、网络计划技术，以保证工程进度和质量。1974年麻省理工学院调查指出“绝大部分美国公司采用网络计划编制施工计划”。目前，美国基本上实现了用计算机绘画、优化计算和资源平衡、项目进度控制，实现了计划工作自动化。以后又提出了新的网络计划技术，例如图示评审技术（GERT），风险评审技术（VERT）等等。【11】121在不确定的情况下使用网络模型的计划对于分批生产的探索式运算的发展分批生产计划是生产计划管理，产品的评估和选取的主要一部分。不合适和不真实的分批生产项目的生产计划将在现在的预算评估，资源计划以及供给中导致错误，并且在合同中强加惩罚以及在工程项目报告中的不平等以及等等。一个不合适的和分批生产的不
14、真实的计划主要的原因是这些项目的生产计划的合适的技术却不用。分批生产项目的分批计划有特定的特点，这个特点从其他项目例如定义的不确定，工程持续时间以及结果，很多的循环和弹性以及要求特殊技术来决定这些产品的生产计划纲要的项目活动的非循环中分辨出他们。因此，不同的方法包括一步一步，水落，原型，螺旋，急流，平行的方法已经被提供对于分批的项目生产计划。在分批产品项目计划中，我们使用的确定网络技术例如CPM和稀少的随即网络的所有模型。使用网络的模糊模型和模糊集的高功能循环网络研究项目的规划合适的工具。这些网络和随机网络在其中随机参数与包括逻辑节点，分支和循环模糊模糊参数取代一样。在此，提出了一种新的方法解
15、决发展循环模糊网络。在此方法中，输入参数包括项目活动网络，确定活动的模糊时间参数，为每个成员的活动程度，循环和循环发生的可能性模糊频率。为此目的，我们使用加法，乘法，最高和最低简单的规则。此方法的输出，包括为项目的生产阶段模糊的时间表。为了评估该方法的有效性和可靠性，它已被应用到循环随机和循环这给了更好的结果模糊网络理论的例子。另外这个方法已应用到实际订单的生产项目，所得结果与其他方法比较接近现实。这种方法的优点在确定性和随机性网络技术如下41。像循环周期的随机模糊神经网络技术的技术能力有更多的过程中显示的项目，周期和弹性统筹规划，在实施过程中具有确定性网络比较少变化，特别是可能的活动。2。在
16、这一技术，如项目完成时间输出参数是更真实模糊数。此外，这种技术减少了压力和控制项目的进度报告会议和更接近现实。3。较少的信息需求估计与随机方法和使用模糊逻辑参数估计的参数是比较接近现实。4。基金超过随机计算的模糊计算。5。电脑和升级能力，对随机方法的模糊方法和更多的现实生活中的应用。利用模糊数的活动和循环发生的可能性估计，活动时间，灵敏度分析，升级活动网络，成本评估和成果之间的比率估计是发给一提延长此方法。122遗传算法解决连续网络设计问题网络设计问题是由道路网络计划得以提升的。对于网络计划问题的算法的研究对于交通运输计划的工程实践是有实际重要的。国外很多学者总结了网络设计问题并且解释了对于网
17、络计划问题的算法的研究的复杂性和重要性。作为主要的研究学科，BI级别的程序的数学模型的结构特征已经对于连续的网络设计问题被分析。基于这个现代遗传算法，一个新的算法已经被设计出来特别的来解决连续网络设计问题。采用这个连续网络设计问题作为一个例子来确认，不仅算法有非常好的集合特征，而且算法的最好的解决方法是可信的。【12】对于一个现存的交通网络，在一些新的连接和重建一些连接来提升数量分析的方法的容量的附加的过程中面临的问题被看作为网络设计问题。在现在的城镇交通计划的实际中，交通网络计划是一个重要的要用数量分析方法解决的。基于工程经验的基础，许多大量的纲要被计划者提出。这些纲要需要被评估，而且相对于
18、比较好的会被采纳。虽然计划的方法有简单，便利，易于操作优点，但是它的缺点还是非常明显的。从全部计划的选出的最好的计划的质量依赖于可用计划的质量。并且可用的计划呗计划者个人的经验和主观的理解所局限。因此，有这种方法决定的最好的计划应该依靠非常强大的个人成就以及计划质量不能被有效得保证的运输计划者的主观作用。此外，这是非常困难来得到最好的计划，因为有效的计划的数量非常有限，但是可行的计划实际上非常多。在许多有限的计划而不是可行的计划中要选一个最正确的选择，可行的计划是得到真实的最好计划的阻碍，即使有效的计划是科学的和理性的，就像评估的方法是客观的。所以，很多理论研究关于网络设计问题将要克服那些城镇
19、道路网络计划的局限来提升计划和设计的等级来获得计划道路网络的最大效率。网络计划问题对于道路网络计划和设计，以及旅行者行动的分析以及系统化的道路网络的运输效率的评估，这个是提供了一个复杂并且系统的分析工具对于运输网络计划。这里有一个对于运输计划的提升值得考虑的重要。连续网络计划问题是网络计划问题中相对比较复杂的一种形式，并且5传统的最优化解法不能太有效的得出结论。随着一串运算的帮助和连续网络计划问题的特征的融合，国外很多学者讨论了遗传运算对于连续网络计划问题的解决以及对于连续网络计划问题的解决方法开启了一盏明灯。2网络计划算法的研究21网络计划算法的优化模型绘制网络计划图，计算时间参数和确定关键
20、的线路，仅仅得到一个最初始计划的方案。然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善，最终得到进行网络计划优化。目标是综合考虑进度，合理利用资源，降低费用等等。【4】211工期优化如果网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度，缩短工程项目的完工工期。主要采取以下的措施，增加对关键工作的投入，一边缩短关键工作的持续时间，实现工期缩短。（1）采取技术措施，提高工效，缩短关键工作的持续时间，使得关键线路的时间缩短。（2）采取组织措施，充分利用非关键工作的宗时差，合理调配人力、物力和资金等资源212资源优化在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的
21、问题。在项目的工期不变的条件下，均衡地利用资源。实际工程项目包括工作繁多，需要投入资源种类很多，均衡地利用资源是很麻烦的事情，要用计算机来完成，为了建华计算，具体操作如下1优先安排关键工作所需要的资源。2利用非关键工作的总时差，错开个工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。3在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当推迟工程的工期。实现错开高峰的目的。213时间和费用优化在编制网络计划时，要研究如何是完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需要的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间和
22、费用优化要解决的问题。完成一个项目的费用可以分为两大类1直接费用。直接与项目的规模有关的费用，包括材料费用，直接生产工人工资等等。为了缩短工作的持续时间和工期，就需要增加投入，即增加直接费用。2间接费用。间接费用包括管理费等。一般按照项目工期长度进行分摊，工期越短，分担6的间接费用就越少。【5】一般项目的总费用与直接费用、间接费用、项目工期之间存在一定关系，可以用图1表示图中T1最短工期，项目总费用最高；T2最佳工期T3正常的工期当总费用最少工期短语要求工期时，这就是最佳工期。进行时间和费用优化时，首先要计算出不同工期下最低直接费用率，然后考虑相应的间接费用。费用优化的步骤如下（1）计算工作费
23、用增加率（增加率）。费用增加率是指缩短工作持续时间每一单位时间所需要增加的费用。按照工作的正常持续时间计算各关键工作的费用率，通常可表示为（2）在网络计划图找出费用率最低的一项关键工作或者一组关键工作作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间，不能成为非关键工作。（3）同时计算相应的增加的总费用，然后考虑由于工期的缩短借鉴费用的变化，在这基础上计算项目的总费用。重复以上步骤，直到获得满意的方案为止。22遗传算法模型遗传算法（GENETICALGORITHM）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美
24、国MICHIGAN大学JHOLLAND教授于1975年首先提出来的，并出版了颇有影响的专著ADAPTATIONINNATURALANDARTIFICIALSYSTEMS，GA这个名称才逐渐为人所知，JHOLLAND教授所提出的GA通常为简单遗传算法（SGA）。7221基本概念遗传算法（GENETICALGORITHM）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则
25、。【6】遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题求函数最小值也类同，一般可以描述为下列数学规划模型式中为决策变量，为目标函数式，式22、23为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。遗传算法的基本运算过程如下A初始化设置进化代数计数器T0，设置最大进化代数T，随机生成M个个体作为初始群体P0。B个体评价计算群体PT中各个个体的适应度。C选择运算将选择算子作用于群体。选择的目的是把优化的个
26、体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。D交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。E变异运算将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体PT经过选择、交叉、变异运算之后得到下一代群体PT1。F终止条件判断若TT，则以进化过程中所得到的具有最大适应度个体作最优解输出，终止计算。222遗传算法特点遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为首先组成一组候选解；依据
27、某些适应性条件测算这些候选解的适应度；根据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。【7】在遗传算法中，上述几个特征以一种特殊的方式组合在一起基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法还具有以下几方面的特点1遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。2许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法
28、同时处理群体中的8多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。3遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。4遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。5具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。3实例分析31施工项目进度计划分析网络计划技术是建筑工程施工项目进度计
29、划分析的有力工具，它用网络模型来表示建筑工程施工项目进度过程，对建筑工程施工项目的施工进度进行定量分析、判断，以及实施过程的调整和控制。网络的结构形式表示建筑工程施工项目活动内容及其相互关系，利用网络计划技术的一些算法，可以实现对工程项目中资源的合理安排、进度计划的编制、优化和控制等。【9】根据网络图和各项活动的作业时间，就可以计算出全部网络时间和时差，并确定关键路径。具体计算网络时问并不太难，但比较烦琐，要耗费很多的人力和时问。对此应用模糊数学方法与网络计划技术的结合，可使项目中的多目标优化问题变得相对简单。道路工程结构如图2所示，道路工程值如在图2中我们可以清晰的看到完成道路工程所需要的每
30、个步骤，而且在表1中我们根据实际操作以及市场成本价位列举了所有步骤的正常时间、紧凑时间以及差额和差价。本文会通过各种算法对道路工程进行网络优化运算。表1作业序号作业名称正常估算紧凑估算差额差价/（万元/D）时间/D成本/万元时间/D成本/万元时间/D成本/万元1先头移入5155150002额外装备获得1572108058163涵洞获得30841890126054一级配料获得202114276615清除1214815641604道路工程移入准备作业获得运输第一阶段第二阶段路面先头后续清除借土准备弃土区开设额外装备涵洞一级配料准备涵洞二级配料铲刮土方铲刮涵洞土方材料处理铺设图296后续移入6841
31、22427第一阶段铲刮24682078410258借土准备8105124324089弃土区开设463913310装备运输103073453451511第一阶段土方1125835831083612第二阶段铲刮91862739313涵洞运输1426103324721814二级配料运输218415108624415第二阶段涵洞101962144240616路面材料处理12131014210517第二阶段土方775842140718路面铺设3535000总计5256263311六时标注法网络计划运算正常在没有进行网络计划运算的情景下，完成一项普通的道路工程所需要的时间应该是157天到221天之间，所需
32、要的价钱在525万元到6263万元。明显的可以看出，如果按照正常流程去完成工作无论是价钱还是时间都是不太能够让决策者满意的。那么，如果运用网络计划算法，在一定的时间内同时开展几项工作，虽然成本上没有太大的改变，但是会在时间上缩短相当长的时间。根据表1可以知道每一个步骤的具体时间以及价钱，如何能够更加机动灵活的利用空余时间，调配富余人员，提高操作效率，就需要对操作过程进行详细分析。对应操作需要的总时间相当于网络计划图上的总工期。关键线路指线路上所有工作持续时间总和最长的线路，关键线路的长度就是总工期。在网络计划中六时标注法是最常用的方法，如表2所示。ESEFTFLSLFFF表2六时标注法时间参数
33、示意图ES为工作最早开始时间；EF为工作最早完成时间；LS为工作最迟开始时间；LF为工作最迟完成时间；TF为工作总时差；FF为工作自由时差。根据六时标注法可以结合表1数据所示，对于表1数据进行处理，得到表3，这样就可以对该道路工程进行成本、时间优化和计划。表3六时标注法运算结果10作业序号估计时间/D开始完成浮时/D紧要作业最早开始时间（ES）最晚开始时间LS最早完成时间EF最晚完成时间LF工作总时差TF工作自由时差FF1502572021503151830330003030004200820288551257171920665121118707241719414320881135194324
34、229411311535201010101518252830111141435254221292535344410101314302044440014212528464930151044445454001612464958613317754546161001836161646400根据表1、表3及图2，可将道路施工问题绘出作业先后关系网络图图中数字为作业序号，如图3所示。图3道路工程作业先后关系网络图11通过以上的数据分析，运用六时标注法可以得出结论，这个道路施工需要经过64天便可以完成，比起之前的最晚221天整整节省了三分之二的时间，但是成本并没有变化，依旧是最少的525万元。312网络计划
35、问题的优化算法通过上例可以发现，虽然在施工过程中成本取的是最小的525万元，而且在时间上仅仅花了64天的时间，但是不一定满足决策者的需求，在日常生活中，很多决策者需要采用更少的时间进行一项任务，这样就可以节省出来更多的时间去完成其他项目，这样便可减少机会成本。那么很多学者便考虑所有步骤的时间都采取紧凑时间进行上例运算，便可得到最优化的结果，可是这样也会存在着成本过高的现象，在工作中，往往决策者会采取时间和成本都相对较少的策略去完成一个项目。于是可以利用模糊数学的方法，对于网络计划模型的标准化方程式进行模糊处理。分析计算符号说明（1）IJA表示网络的系数（I1,2,3,18；J1，2，3，18）
36、。（2）IF表示作业I的费用，它与时间成IT关系（3）IT表示作业I的时间，ITJ表示第I作业的紧凑步骤时间，ITZ表示作业I的正常时间。（4）作业I紧凑步骤费用为IJF，作业I的正常费用为IFZ（5）作业I的费用系数IC，ITB为作业I的开始时间。对于模型的建立目标是追求时间最短时的费用最小，也就是当时间最短时费用也最少的双优结果44123145678910131211161517181218MINTBT181IIFMINF费用是关于时间的一元函数，具体变化为）（IIIIIFFTJTCZ再有，为了判断时间先后，将生产计划网络进行数学化，也就是将网络赋数。当作业I与作业J有关系时，若是正向，则
37、IJA1；若是反向的，则IJA1；当作业I与作业J无直接关系是，那么IJA0这样该矩阵AIJA1818与该又向图形成一一对应关系。由网络计划技术条件可知，作业I开始时间ITB必定与作业J有联系，且属于改作业前面的所有作业均完成了，也就是J0AIIJMAXTTBTBJ于是建立双目标规划模型18MINTBT181IIFMINF），（）（1821JI00TBMAXFFI1JJ0AIIIIIIIIIIJTTTBTBTJTCZTZTTJ将多目标转化成但目标有两种方法两者之和最小；两者之积最小。这两种方法都有其局限性，方法中的量纲不同；方法中的时间和费用数字差额太大，难以求出合理的优越点，因此采取模糊数学
38、多目标规划理论来处理，以表示的无条件优化集INFSUPINFXFIIXFXFXFMIII）（将上述问题利用模糊数学多目标理论求解（运算过程略），得到最终结果为最有结果49天，最优费用54960万元。各作业时间如下表作业12345678910时间515242086208417作业1112131415161718总时间13时间8911216115149313遗传算法解决道路设计问题要解决本题，首先必须实现图在计算机中的表示，在本文中采用两个二维表二维数组来实现图的表示。第一个二维表为点边表。用TABL来表示，它记录了每个点相关的边，TAB1的第一个维的长度等于图中节点的个数TABL的第二个维的长度
39、等于图中拥有最大边数的节点的边数。问题中节点数为18。最大边数为6，二维表一则为TABL186。第二个二维表为边点表，用TAB2来表示，它记录了每条边的起始节点和终止节点，用来表示边的方向，图中共有21条边，所以二维表二为TAB212。遗传过程可由下面几个步骤表示1编码表示遗传算法的工作对象是字符串个体，用以传递计算信息。在本论文中，研究对象为网络图优化，每个个体表示一种优化方案。在编码中，个体采用以二进制字符串进行编码通过单位长度字符串来表示每条边上缩短的工时。因为每条边上所能缩短的工时不同，所需二进制位长度也不相同。为统一处理，二进制编码单位长度取最大可缩短工时的二进制编码的长度来表示。个
40、体编码长度等于单位长度乘于单位边个数。在本图中，最大缩短时间为12，所以要用4位二进制数来表示一条边。图中共有21条边，所以一个个体由28位二进制字符来表示。从左向右按照施工顺序依次编码如下0110000000000101110001000100001000100100001100010011011000110011001101000100001000102群体遗传过程中，每一代均由众多的个体字符串组成，成为群体。群体中个体的数目由用户指定，在本文中群体数目为50。遗传过程是新旧群体的迭代过程，旧的群体完成一系列遗传操作后成为新的群体，在新群体中既包含了旧一代中的优秀个体也包含了交换、突变生成
41、的新的个体。本论文中为了提高群体的收敛性，保存优秀的个体，在每次迭代后增加了一个复制操作若新一代个体中最大个体适应度小于上一代个体最大适应度，则旧一代最大适应度个体将代替新一代最小适应度个体。第0代的群体，用随机方法产生，在给定的合理方位用均匀分布的随机数任意产生初始个体，作为今后进行计算的基础。随着遗传计算的发展，群体中个体的品质适应度逐渐改善，不断产生新的优良个体。3纠错由L，2的介绍可以发现单位字符串代表边上缩短的时间，而每条边可缩短的最大时间是不同的。在群体的初始化和遗传操作过程将会有一些不符合要求的个体产生。为了排除不合格个体，在程序中将添加纠错操作，增加了二维表TAB3，里面记录了
42、每条边可缩短的最大长度当每次个体操作后，程序将执行检错操作，检查个体是否合格，若不合格，即大于最大可缩短数则执行纠错操作。把不合格边改为可缩短的最大数。4适应度统计在本文中，适应度大小FX为节省费用大小，它包含两部分A间接费用节省数，B14特急工时增加费用，适应度大小为AB可以看出是一个最大值问题。在本文中假设间接费用为100万元，工期每缩短一天便可节省间接费用3万元。节省成本间接费用节省数特急工时增加的费用节省时间间接费用节省斜率每条工序上节省的时间每条工序特急费用成本斜率。其中间接费用节省斜率T和每条工序特急费用成本斜率T是固定值，可直接获得。在本文中，选取每个工序每条边上节省的时间进行编
43、码因此每条工序上节省的之间即每条边的编码值B，也可以直接获得。故适应度方程为TBTAXF因此只需求解节省时间数即特急工时。特急工时获得是通过建立了一个临时表，保存到每个点的天数，其中到每个点的天数由到这个点的边的边长加上这条边的前一个点的累计天数，当有几条接入边时，比较几个接入边的到该点的累计天数，取最大值，直到最末点，最末点即特急工时。在适应度的计算中，本文将目标函数设为最大值问题但实际情况为费用越小越好，因此在计算的过程中省去了总费用与节省费用的差值。在运算之前，首先编写目标函数FUNCTIONSOL,EVALFITNESSSOL,OPTIONSXSOL1EVALXABT把上述函数存储为F
44、ITNESSM文件并放在工作目录下5选择操作本文中遗传算子中的复制、交换、突变的对个体的选取都是通过选择操作得到的，在程序中选择函数返回一个群体大小为种子的随机数，该返回数即被选中个体的位置数。新群体都将由选择操作在旧一代中选取，直至新群体被全部生成。6变异操作在本文中，研究的对象为网络图，单位长度字符代表每条边上缩短的时间长度，为了使每条边被考虑到因而采用了直接突变的方法。由于突变的量较大，涉及到每个字符，在设计中突变被贯穿在了复制和交换的每个字符的操作过程中，这样即可以节省代码，也提高了效率。7复制和交换操作复制和交换操作在由选择操作选取的个体根据交换概率，通过随机数判断是否执行交换操作，
45、如果执行交换操作，通过随机数获的交换点，执行交换操作。如果执行复制操作，则交换点设为最后一位，这样既节省了代码又提高了效率。同时变异操作贯穿在复制与交换操作的每个位操作，完成遗传操作。8终止条件本文采用两种终止条件联合作用来决定迭代何时终止A规定最大迭代代数，当迭代次数达到最大迭代代数时停止迭代运算B控制最大适应度与平均适应度之间的偏差，通过在遗传运算前设定最大偏差，当最大适应度与平均适应度之间的偏差小于或等于最大偏差时，即15停止迭代运算。通过以上两种终止条件联合采用，可及时、有效地得出合理运算结果。MATLAB70中包含一个专门设计的遗传算法与直接搜索工具箱。使用该工具箱可以扩展优化工具箱
46、在处理优化问题方面的能力，可以处理传统优化技术难以解决的问题，包括难以定义或不方便数学建模的问题，还可以解决目标函数复杂的问题，比如目标函数不连续或具有高度的非线性、随机性以及目标函数不可微的情况。根据以上八个步骤，采用MATLAB70中的遗传算法运算10次，将相应的数据输入之后可得到以下数据次数12345678910X145743143547144698144367142693143645144824143726143234142464FX392437392459392643391346392541391479393587392582392386393741故可节省的费用大小最优解为39万元
47、。故通过遗传算法，通过考虑间接成本，所得到的最优成本为586万元，最优时间为50天。32运算算法比较通过对以上三种算法对于同一个事例的分析比较，可以看出每一种算法对于同一种情况都有其优缺点（1）六时标注法的算法简便，容易上手，是在平日工作生活中更倾向于采用的方法，更加容易被广大的决策者所应用，但是相对于其他两种算法，所得到的结果并不是最优的结果，而且考虑的可能存在的参数少，在今后工作中的可变性大，在本文中，虽然可以得到相对最优的64天的时间，但是并没有考虑成本问题。（2）网络计划优化模型的算法相对来说有些难度，需要有一定的数学基础的决策者才可以完成，得到的结果相对来说是比较合理的，但是由于其难
48、度大，并没有在日常生活中广泛应用，而且考虑的参数变量并不是非常的全面，在本文中，通过应用模糊数学将时间与成本模糊处理，得到优化的最优时间为49天，最优成本为5496万元。（3）遗传算法的应用范围非常的广泛，无论是在道路设计还是优化工作流程中都是可以应用的，所得到的结果往往也是最优结果，对于参数变量考虑的因素也比以上两种算法要全面，但是由于其运算难度大，需要数学基础高，故并没有被很多的决策者使用，恰恰会第一时间被舍弃。在本文中，加入考虑了间接成本，使得考虑因素更加全面，故得到最优的结果为586万元和50天。164结论网络计划问题现在正在逐渐的被许多国家和地区的人民所接受，应用与非常广泛的范围，其
49、应用性强，易操作的特点非常符合社会需求，通过以上对于各个模型的应用可以看出，无论是在道路设计问题还是在简化工作流程的方面，网络计划算法都起到了非常重要的作用。在本文中，通过对同一个实例的三种算法的探讨可以看出，现在对于网络计划问题的算法很多决策者并不能够完全掌握，应用于实际生活中的结果往往并不是最优结果。当然对于网络计划问题的算法研究还是需要通过以后的学习与探索去进一步的研究，毕竟目前的算法还不完善，还有许多问题还待解决。17参考文献1运筹学（修订版）清华大学出版社200492遗传算法在最优网络计划中的应用软件导刊201073网络计划在生产管理中的应用一曙技术201044网络计划技术在招标工作中的应用福建建设科技2009第6期5网络计划工期优化的分析方法信息技术教学与研究2010年第33期6施工工程中网络计划的应用山西建筑201037浅议网络计划技术在应用中存在的问题电子商务8浅议网络计划技术及其在生产中应用移动电源与车辆2010年第1期9模糊处理方法在网络计划技术优化问题中的应用项目管理技术2010610基于网络计划图的水电厂运行生产管理水电厂自动化2010811DEVELOPINGAHEURISTICALGO
