运筹学最短路径篇1
关键词教育装备；运筹学；运输
中图分类号：G40-057文献标识码：a
文章编号：1671-489X（2013）33-0014-03
在教育装备管理活动中，决策是一个多阶段、多步骤的分析判断过程，贯穿于教育装备管理活动的各个阶段，绝大多数教育领域的管理决策都是多阶段决策问题。教育装备运输线路的选择是教育装备管理中经常遇到的多阶段决策问题。由于运输线路的有限性、决策变量的动态性、最优方案的不稳定性等多种制约因素，各教育装备生产厂商如何根据现有交通条件选择最短的运输线路，将装备送达教育机构，使总的运输代价最小，属于典型的教育装备运输问题，是教育装备运筹学的重要研究内容之一[1-2]。本文以教育装备运输线路选择问题为具体研究对象，采用动态规划的原理及方法，结合实际案例，给出具体的数学模型和决策过程，从而有助于教育装备管理活动中的科学决策。
1动态规划的原理
1951年，美国数学家贝尔曼（RichardBellman）创立了解决过程优化问题的经典方法——动态规划，常用于解决多阶段决策问题（如最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题、生产过程最优控制问题等），是一种重要的管理决策技术[1-6]。多阶段决策是指将决策过程划分为一系列相互关联的阶段，在每个阶段均需做出相应的决策，上一个阶段的决策不仅会影响下一个阶段的决策，而且将影响整个决策过程。因此，每个阶段最优决策的选取，不仅要考虑当前阶段所取得的效果，而且要综合考虑各个阶段的决策所形成的总体效果。
作为解决多阶段决策问题的一种有效方法，动态规划在工程技术、社会经济、国防军事等领域应用广泛，并取得了显著成果，已经成为现代管理学中进行科学决策不可或缺的重要工具。动态规划的最大优势在于把一个多阶段决策问题转化为若干个单阶段最优化问题，并逐个求解所有单阶段最优化问题。因此，在采用动态规划的原理和方法求解多阶段决策问题时，必须具体问题具体分析，建立相应的数学模型。
求解步骤下面为动态规划方法求解多阶段决策问题的主要步骤。
1）划分阶段。按照时间、空间、变量等特征，将某一实际问题划分为若干个有序的阶段，通常采用i表示阶段变量。
2）确定状态和决策。根据无后效性原则，选择不同的状态表示各个阶段；并逐一确定阶段i的状态变量si、决策变量di及各自的取值范围。
3）撰写状态转移方程。根据上一阶段的状态si-1和决策di-1，可以导出本阶段的状态si，即写出状态转移方程t。
4）建立指标函数gi。得到实际问题的函数方程，即递推关系式。
5）求解最优指标值和最优策略。采用逆序算法，求出每个阶段的最优指标值及相应的最优策略。最后求得全过程的最优策略。
动态规划的逆序算法最优指标函数通常表示为：
...（1）
其中，“opt”表示最优化，通常指“取最大值”或“取最小值”；表示某种运算，通常指“和”运算或“积”运算；n表示阶段数。
根据最优化原理，将式（1）表示为递推关系式：
...（2）
利用式（2）可表示出最后一个阶段（第n个阶段）的最优指标函数为：
（3）
其中，fn+1（sn+1）称为边界条件，其取值根据实际问题确定。
已知边界条件fn+1（sn+1），利用式（3）可求得第n个阶段的最优指标函数fn（sn）；根据fn（sn），继续利用式（3）可求得第n-1个阶段的最优指标函数fn-1（sn-1）；根据fn-1（sn-1），进而可得第n-2个阶段的最优指标函数fn-2（sn-2）；……；依此递推，直至求得第1个阶段的最优指标函数f1（s1），从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。
2实例分析
下面以实际案例分析教育装备运输线路选择问题：
某教育装备厂商欲将装备由库房a运送至目的地e，从a不能直接到达e，必须经过3次停靠进行各种补充和休息：第一次停靠有两个可供选择的中转站，第二次停靠有三个可供选择的中转站，第三次停靠有两个可供选择的中转站。其运输路线图如图1所示，箭头表示单行线，旁边的数字表示距离（单位：百公里）。显然从a到e有多种运输路线，请选择最短的运输路线。
对于比较复杂的交通路线图来说，将所有可能的路线全部罗列出来，再比较它们的路程虽然可行，但并不可取。由最优化原理可知，最短路径有一个重要性质：如果由起点a经过B点和C点到达终点D是a到D的一条最短路径，则由B点经C点到达终点D一定是B到D的最短路径。因此，寻找最佳运输线路的方法为：从最后阶段开始，由后向前逐步递推求出各点到终点的最短路径，最后求得由始点到终点的最短运输线路。
按照动态规划的求解方法，将全过程划分为4个阶段，即阶段变量i=1，2，3，4，取过程在各阶段所处的位置为状态变量si，按动态规划的逆序算法求解。
1）当i=4时，由中间点D1到达目的地有一条路线可以选择，则
f4（s4=D1）=6
由中间点D2到达目的地有一条路线可以选择，则
f4（s4=D2）=7
因此，分别给D1和D2加上标号6和7，如图2所示。
2）当i=3时，由中间点C1到达下一阶段有两条路线可以选择，即选择D1或D2，则
，选择D1
由中间点C2到达下一阶段有两条路线可以选择，即选择D1或D2，则
，选择D2
由中间点C3到达下一阶段有一条路线可以选择，即选择D2，则
f3（s3=C3）=7+7=14，选择D2
因此，分别给C1、C2和C3加上标号15、13和14，如图2所示。
3）当i=2时，由中间点B1到达下一阶段有三条路线可以选择，即选择C1或C2或C3，则
，选择C2
由中间点B2到达下一阶段有两条路线可以选择，即选择C2或C3，则
，选择C2
因此，分别给B1和B2加上标号18和24，如图2所示。
4）当i=1时，由起点S到达下一阶段有两条路线可以选择，即选择B1或B2，则
，选择B1
因此，给a加上标号22。从而通过计算的反顺序追踪，得到最佳的运输线路，即一条从a到e的最短路径：aB1C2D2e（如图2中加粗线条所示），最短的运输距离是2200公里。图2中每个停靠站都有自己的标号，它表示从该站出发到目的地e的最短路径长度。
3总结
教育装备管理的多阶段决策优化问题是教育装备运筹学的重要研究内容之一，可以为教育装备的决策者或管理者提供合理有效的辅助决策支持方案。本文以教育装备运输线路选择问题为研究对象，结合实际案例，采用动态规划的理论及方法研究教育装备运输线路的最优化选择，探讨教育装备管理活动中的科学决策，并给出具体的求解算法和决策过程，从而定量地提供了可操作的决策理论和方法。
参考文献
[1]李慧.教育装备运筹规划[m].北京：北京大学出版社，
2010：36-85.
[2]陈庆华.装备运筹学[m].北京：国防工业出版社，2005：
103，122.
[3]winstonwL.运筹学：决策方法[m].北京：清华大学出版社，2004：214-235.
[4]winstonwL.运筹学：数学规划[m].北京：清华大学出版社，2004：490-542.
[5]焦宝聪，陈兰平.运筹学的思想方法及应用[m].北京：北京大学出版社，2008：63-68.
运筹学最短路径篇2
关键词：运筹学道路工程交通运输
中图分类号：C913.32文献标识码：a文章编号：
1引言
运筹学是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择使人们的工作在一定期限内收到最合理、最经济、最有效的效果。所谓科学的方法就是从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最佳规划、最优管理和最优控制，使每个局部都服从一个整体目标，做到人尽其才、物尽其用，以便发挥整体的优势，力求避免资源的损失和浪费。道路交通运输运筹学最主要的理论基础就是运筹学，运筹学既是一门理论科学，又是应用科学。运筹学所要解决的问题既是在既定条件下对系统进行全面规划、统筹兼顾，以期达到最优的目标。
2运筹学的特点
2.1主要使用数学方法
运筹学是一门以数学为主要工具、寻求各种实际问题最优方案的学科。它强调以量化为基础，使用许多数学工具和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期达到最佳效率和效益。
2.2最优化思想是核心
运筹学是采用科学步骤和数学方法来制订最优决策的科学。运筹学强调最优性，在数学的理论研究中，也常常是以对象的“最优”为目标，这种最优化思想有两层含义：“①指所讨论问题的结论“最优”；②指解决问题的方法“最优”。它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案。
2.3多学科交叉
运筹学思想能够解决实际中提出的决策问题，为决策者选择理想方案提供科学依据，同时它综合运用化学、物理学、计算机科学等学科的理论及方法，既提供量化因素，也进行定性分析，最终能向决策者提供建设性意见。
3运筹学在道路交通运输系统中的应用
3.1物资供应问题的最优化
高速公路的物资供应与管理，有其显著的特点：远离基地，无物资储备设施；所需材料品种少、数量大；大部分材料是就地取材，其竞争性强，各种关系复杂，难于处理；公路施工线长、点多，且具有临时性。面对这些特点，要保证供应，确保质量，降低成本，必须摸索出一套与之相应的供应管理办法。在此，我们主要讨论根据现有的交通网，制订一个使物资运到各消费地点而总运费要最小的调运方案。其数学模型为:
已知有个生产地点，，，…。可供应某种物资，其供应量（产量）分别为，有个销地，，，…，，其需要量分别为，从到运输单位物资的运价（单位）为。若用表示从到的运量，那么在产销平衡即的条件下，要求得总运费最小的调运方案，可求解以下数学模型
（，，…，）
（，，…，）
这就是产销平衡运输问题的数学模型。
(2)实际问题中产销往往是不平衡的，应将其化成产销平衡的问题。
当产大于销，即时，就要考虑多余的物资在哪一个产地就地存储的问题。此时只要增加一个假想的销地，该销地总需要量为而在单位运价表中从各产地到假想销地的单位运价为，就转化为一个产销平衡的问题。
同理，当销大于产时，也可以转化为一个产销平衡的问题。
(3)对产销平衡的运输问题，一般采用表上作业法来求解，其步骤为：
①确定初始基可行解。
一般采用“最小元素法”确定初始基可行解，该方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。用最小元素法得到的解必为基可行解，但未必是最优解。
②在表上计算空格的检验数，判别是否达到最优解。如是最优解，则停止计算，否则
转到下一步。
最优解判别的方法是计算空格（非基变量）的检验数。因运输问题的目标函数是要求实现最小化，故当所有的检验数大于0时，为最优解；当得到的表中还有负检验数，说明未得到最优解。一般用位势法求空格的检验数。
③确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。
一般选最最小的负检验数对应的空格为调入格，以该格为起点作闭路，从该空格开始，沿闭路在各处“+”“-”间隔标号，在所有标号处，选运量最小者为调整数，在标“+”号处加上，在标“-”处减去，把该空格改为数字格，把运量变为的格改为空格。
④重复②，③直到得到最优解为止。
3.2图论的应用
图论是一个古老的但又十分活跃的分支，在物流中的应用非常显著。其中最明显的应用体现在运输问题上，比如城市间的物资调运、车辆调度时运输路线的选择，为使某项任务完成的既快又好，各工序之间的衔接等。运用了图论中的最短路、最大流、最小费用最大流等知识，求解运输所需时间最少、路线最短、费用最省的路线等一系列实际问题。其中运用最多的是最短路和最大流问题。
最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题。其定义是：
给定一个赋权有向图()，记D中每一条弧上的权为。给定D中一个起点和终点，设p是D中从到的一条路，则定义路p的权是p中所有弧的权之和，记为，求一条从到的路，使
式中对D的所有从到的路取最小，则称为从到的最短路，为从到的最短距离。在一个图()中，求从到的最短路和最短距离的问题就称为最短路问题。
其次，许多系统包含了流量问题。例如，交通系统有车流量，控制系统有信息流等。这类问题主要是确定系统网络所能承受的最大流量以及如何达到这个最大流量。在运输网络的实际问题中，对于流有两个基本要求：1）每个弧上的流量不能超过该弧的最大通过能力（即该弧的容量）；2）中间点的流量为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
4结束语
运筹学作为一门应用实践的学科，专门研究交通管理中有限资源的计划、组织、分配、协调和控制，以期达到最佳效率和效益。现代交通管理所呈现的复杂性不是简单算术能解决的，运筹学理论是支撑现代交通管理的有效工具。交通事业的发展离不开运筹学的技术支持，运筹学的应用将会使交通运输管理更加高效。
参考文献：
[1]钱颂迪．运筹学[m]．北京：清华大学出版社，1990．
[2]王晶．运输布局学[m]．大连：大连海事大学管理学院(自编教材)，1995．
[3]沈志云．交通运输工程学[m]．北京：人民交通出版社，1999．
[4]傅家良．运筹学方法与模型[m]．上海：复旦大学出版社，2006．
[5]张慧．运筹学在交通运输管理中的体现及应用[J]．内蒙古科技与经济，2010．
[6]姜锋雷．运筹学在我国公路、铁路运输系统中的运用[J]．中国水运，2007．
运筹学最短路径篇3
关键词：高职院校Dijkstra算法标号法表格
Dijkstra算法是典型的最短路算法，用于计算一个顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的顶点很多，因此效率低。但Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构、图论、运筹学等。
给定一个带权有向图，其中每条边的权是一个非负实数。另外给定图中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法（标号法）是按各顶点与源点间的路径长度的递增次序，生成源点到各顶点的最短路径的算法，即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点到其他各顶点的最短路径全部求出为止。
关于最短路问题Dijkstra算法的教学，看上去不难，但老师讲授起来很费劲，学生学起来更加感觉困难。对此，不寻找恰当的教学方法，一味地啃书本是难以达到良好的教学效果的。往往还会致使学生厌学，从而对相关课程的学习失去兴趣。高职学生相对于其他普通本科院校的学生，在数学学习方面能力要弱一些，因此，高职院校的数学教师更应该注意寻找适合的教学方法来提高学生的学习兴趣，从而提高课堂教学效率。教师应改变过去“填鸭式”、“灌输式”的教学方法，充分发挥学生的主体作用，灵活运用启发式教学方法，激发学生思维和质疑，培养学生的创新精神和独立探讨问题的能力。要引导学生对问题多思考，多问几个“为什么”，抓住内容相关和相反的部分，对知识进行横向和纵向的比较，并掌握它们之间的内在联系和规律，培养学生系统而全面的思维方式。教师应鼓励学生主动发表自己的见解，互相探讨、启迪，培养学生勇于探索，敢于创新的精神，引导学生自主学习。此外，教学中还应注意确保学生有充分思考的时间，切实加强学生对问题的认识程度，让高职学生真正感受到对数学的学习并不是那么困难的事情，不断增强学习数学的成功感，增强学习信心，从而优化课堂教学效果。
。
各行的数据是怎么计算出来的呢？
例：用Dijkstra算法求下图从顶点到其余顶点的最短路。
参考文献：
［1］王信峰.计算机数学基础［m］.高等教育出版社，2009.
运筹学最短路径篇4
【关键词】高校经费资金筹措财务管理
一、引言
随着高校的扩招，我国高等教育也面临着资金短缺的难题，单一的政府拨款对高校今后的生存和发展是非常不利的，高校对经费不断增长的需要与资金的短缺相冲突，因此，积极争取政府的拨款、主动向社会筹措办学资金，从而逐渐形成多元化的筹资模式，以极大地满足高效自身的资金需求，进而有效促进高效的发展。我国当前普通高校的经费来源渠道正在逐渐呈现多元化，当然也凸显了很多的问题。
二、高校经费筹措的内涵
高校经费筹措，就是高校筹集办学资金的活动。例如：为湖区校友、企业的捐助而展开的游说活动，为得到学费、政府拨款及捐款等资金而主动开展的活动等，都属于经费筹措活动的范畴[1]。
三、高校经费筹措机制的概念和相关研究
准公共物品是指具有有限非竞争性或非排他性，既坚持公益性原则，又有经营性质的物品[2]。高等教育是准公共物品的一种。
教育经济学的高等教育成本分担理论中最为重要的原则为能力支付和利益获得两条原则。利益获得原则，是指从教育中获益的人应当为此支付一定的费用；能力支付原则，指支付费用的人也需要看其各自的能力予以支付[3]。
高等教育可以提供获利的机会促使高等教育投资的诱致性制度变迁形成[4]。我国政府对教育资金提供能力的下降，使得政府不得不下放资源分配的权力，也为其他资源主体提供了获利机会。
四、我国高校经费筹措机制分析
在高校筹集资金涉及很多方面，已经逐步发展成一门新学科。资金筹集的内容涵盖了多种学科知识领域，譬如怎样选择筹资运作模式、如何建立信用、怎样使用筹资专家以及如何确立筹资战略等；想要以最低的资金成本与财务风险，实现高校可用资金筹集的最大化，就必须对各个来源渠道的性质、资金来源的结构、筹集方式的成本及增减变化等正确认识和分析[5]。学校经费来自于很多方面，其中大部分包括：
（一）财政拨款
财政拨款指政府拨给高校用于高等教育方面的款项，其设计了各级政府拨款给各级别教育部门，各级别教育部门拨款给各级各类的学校。
社会捐赠：是社会对高校的捐赠与赞助，其主要是指法人实体及自然人等捐赠人，以对教育事业的资助为目的，自愿将其持有的财产捐赠给高校使用或管理的行为。社会捐赠的来源分为个人和企业，内容包含现金和实物，主要用途为学校建筑物的建造、图书设备的购置及科研活动需要等。
（二）学校融资
1.融资租赁，实质上是指与资产所有权相关的全部风险和转移，以及报酬的租赁，也被称为现代租赁或资本租赁，其所有权最终可能会转移，也可不转移。
2.Bot模式，是快速筹集高校基础设施建设所需资金的一种有效的模式，其有利于高校规模发展中“资金瓶颈”问题的有效解决，尤其有利于高校后勤的经营与管理。
3.银行信贷。主要是指高校为了获得教学、产业、科研等方面的有偿资金来源，而向银行借款的行为。据相关数据分析显示，当前只公办高校的银行贷款就已经高达1500-2000亿元[6]。高校以银行贷款方式进行资金筹措的方式主要有以下几种：（1）国内银行贷款；（2）国际金融组织贷款；（3）民间委托贷款；（4）信托资金贷款。
（三）学校事业收入
1.学生缴纳的学费。是个人或其家庭为了接受学校教育所必须支付的费用，主要包含学费、住宿费、代办费等杂费。
2.校办产业收入。作为高校经营收入的主要构成部分，可以为学校带来部分经济收入，有效缓解银行融资造成的压力。
3.置换资产。主要是对高校本身资产的经营所获取的用于学校建设的资金，比如：闲置资产的出让、设备出租、老校区的转卖以及技术的转让等。
（四）高校筹资优化选择
《高校筹资优化选择研究》一文运用层次分析原理（aHp）建立了高校筹资方式优化选择的数学决策建模，为高校筹资提供了一种切实可行的科学决策依据[7]。为了实现复杂问题的简单化、定性问题的定量化处理，其详细提出了问题的处理方法与过程，同时根据资金潜力、时间限制、资金成本及风险大小的考察标准等提出多种可能的筹资方式，并进行层次排序，以对各种筹资方式进行权重排序。
依据排序结果，领导者实施决策。需注意一点：筹资方案的优化如应用层次分析法，那么就需要综合分析高校的实际状况，成立不同类型的专家组，以有效实现多方面、多角度的筹资分析。之所以这样做是因为每个人对不同高校的不同实际情况会做出不同的判断，给出不同的判断值，所以会出现不同的排序结果。其最终目的是为了透彻了解问题矛盾，明确周边环境，获取科学的判断和正确的排序结果。
五、结论
首先，本文介绍高校经费筹措与运营机制的内涵以及选择原则，然后重点分析我国高校经费筹措与运营的现状，在此基础上进行比较，分析总结出我国高校经费筹措与运营机制的特点，指出高等教育经费的筹措应当向着多元化发展的趋势迈进，不断提升高校的融资能力，改变以往单一的筹资模式。
参考文献
[1]任华.高校筹资优化选择研究[D].南京：南京理工大学，2006.
[2]于蕴芳，张兆玮.从我国高等教育经费筹措方式看其发展出路[J].商业文化，2007（06）：229-230.
[3]范先佐.教育经济学[m].北京：人民教育出版社，1999.
[4]盛洪.现代制度经济学[m].北京：北京大学出版社，2003.
[5]代蕊华.美国高校的资金筹措及其启示[J].全球教育展望，2001（10）：71-73.
[6]王宪良.我国高校融资的困境及其解决路径[J].高教经费，2007（06）：39-41.
运筹学最短路径篇5
关键词：计划管理技术；室内装饰；工程项目
1、引言
戚安邦，张连营定义项目管理是运用各种相关知识、技能、方法与工具，为满足或超越项目有关的要求与期望，所开展的项目起始、计划、组织、控制和结束的管理活动。进度、
成本和质量是项目管理的三大控制目标，在室内装饰工程项目中业主往往标明所需装饰材料的特质甚至品牌，并对其质量有硬性标准，材料成本也有既定指标，在项目实施中主要控制要点集中在进度，通过充分的项目规划和进度安排合理配置人力资源是项目成功的关键。
2、主题背景分析
美国项目管理学会（pmi）认为项目进度计划的核心技术是网络计划技术，网络技术为现代生产提供了科学的管理方法，主要应用于制订规划、计划和实时监控，在缩短建设周期、提高工效，降低造价以及提高企业管理水平取得显著的效果。网络技术的基础工作为项目工作分解结构（wBS），依次进行项目活动定义wBS工作编码，估算活动历时，项目活动排序，绘制网络图，制订进度计划。白思俊指出制订进度计划最常用的方法有甘特图和关键路径法，甘特图的优点是简单、明了、直观，至今仍在项目管理中广泛应用，但是各活动之间的关系却没有充分表示出来，同时也没有指出影响项目进度的关键所在；关键路径法用网络图表示项目中各项活动的进度和它们之间的相互联系，并在此基础上进行网络分析，计算网络中各项活动时间，确定关键活动与关键路线，利用时差不断地调整与优化网络，以求得最短周期。关键路径法国内外众多学者进行了深人的研究在此不再穷举，在室内装修工程项目中更注重的是在关键路径限制下非关键路径利用时差在最合适的时候配置人力资源，确保室内工作场地宽敞畅通，以提高工作效率，利用非关键路径的时差通过可变甘特图平滑配置人力资源正是本文研究的重点。
3、利用非关键路径时差平衡人力资源配置的研究
室内装饰工程项目由于场地有限，工作界面重叠，空间和工作界面成为室内装饰工程的限制性资源，因此室内装饰工程作为普通工程项目除了通过关键路径法进行进度计划、更经济地压缩或延长工期之外还要充分利用非关键路径的时差平衡人力资源配置，科学利用空间和工作界面来提高工效。下面以普通民居的室内装饰工程项目为例，论述如何利用网络技术、关键路径法和甘特图技术平衡人力资源配置，达到提高空间利用率从而提高工作效率的方法。下面利用实际案例说明：
根据图工作分解结构：室内装饰工程项目工作先后关系，制作项目网络图确定关键路线；作出关键路径甘特图及人力资源配置图。
分析非关键路径：
由以上网络图显然可知非关键1320瓦工材料采购、1330木工材料采购、1340安装材料采购、1451墙面批灰工程、1430贴瓷片工程、1452墙面底漆工程、1420天花吊顶工程、1460水电安装工程，由于室内装修工程操作场地面非常有限，虽然1320瓦工材料采购、1330木工材料采购、1340安装材料采购在人力资源配置上用人不多，但是材料堆放会占用较大的
地方，也应作适当的调度安排尽可能达到时间刚刚的效果。1460水电安装工程在墙面底漆工程完成之后1470铺地板工程之前，该工程与1453墙面面漆工程天数相差2d可同时完工可考虑向关键路径环节1453让路；1451墙面批灰工程、1452墙面底漆工程、1420天花吊顶工程、1430贴瓷片工程属室内装饰的主要工程，科学配置人力资源充分利用操作界面正是本文研究的重点。本文采用绘制非关键路径的可变甘特图，使之与关键路径甘特图及人力资源配置图重叠统筹分析达到平衡人力资源配置的要求，从而充分利用操作场地提高效率缩短工期。
4、研究结论和创新
本文通过简单典型的例子研究利用非关键路径的时差进行人力资源的配置，通过对比关键路径甘特图和非关键路径可变甘特图，固定关键路径人员配置，利用可变甘特图的可调整范围进行统筹配置人力资源，达到平滑人力资源，充分利用操作场面，避免操作界面重叠，加快工作进度，提高效益。该方法简单、直观、效果明显，充分一发挥了网络图、甘特图、关键路径法等计划控制方法的优点，为室内装饰工程等场地受限，工作界面重叠的工程项目管理提供借鉴。
参考文献：
[1]白思俊.项目管理案例教程〔m].北京：机械工业出版社，2009
[2]戚安邦，张连营.项目管理概论[m].北京：清华大学出版社，2008.
运筹学最短路径篇6
关键词：最短路径；动态规划；C语言编程
中图分类号：tp311文献标识码：a文章编号：1009-3044（2013）09-2191-03
1概述
数学源于生活，又服务于生活.它是一门研究现实世界中的数量关系与空间形式的学科.当今社会，随着物质水平的不断提高，生活需求的不断扩大，自然资源的不断开发利用.像天然气管道铺设问题，厂区布局问题，旅行费用最小问题等都已成为我们平时经济生活中的普遍问题.它们其实都可以化归为最短路线问题，而最短路问题实质上是一个组合优化问题[1]。
动态规划方法主要是研究与解决多阶段决策过程的最优化问题，它将求解分成多阶段进行，不但求出了全过程的解，还能求出后部子过程的一组解，在求解一些生活实际问题时，更显其优越性。为了快速、简单的计算最短路径，节约运输时间与成本，该文利用动态规划的思想编写了C语言程序，解决物流运输过程中多地点的最短路径的选择问题。
2最短路径问题
2.1最短路径问题算法的基本思想
在求解网络图上节点间最短路径的方法中，目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径[2]。
Dijkstra算法是图论中确定最短路的基本方法，也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径，通常采用两种方法。一种方法是每次以一个结点为源点，重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法，其时间复杂度为[on3]，虽然与重复执行Dijkstra算法n次的时间复杂度相同，但其形式上略为简单，且实际运算效果要好于前者。
2.2最短路径问题算法的基本步骤[3]
这样经过有限次迭代则可以求出[v1]到[vn]的最短路线。
（2）Floyd算法的基本步骤
（3）动态规划算法基本步骤
我们将具有明显的阶段划分和状态转移方程的规划称为动态规划[1]。在解决多个阶段决策问题时采用动态规划法是一个很有效的措施，同时易于实现。
根据动态规划的基本概念，可以得到动态规划的基本步骤：1）确定问题的决策对象。2）对决策过程划分阶段。3）对各阶段确定状态变量。4）根据状态变量确定费用函数和目标函数。5）建立各阶段状态变量的转移过程，确定状态转移方程。
根据动态规划的基本模型，确定用动态规划方法解题的基本思路，是将一个[n]阶段决策问题转化为一次求解[n]个具有递推关系的单阶段的决策问题，以此来简化计算过程.其一般步骤如下：
用于衡量所选决策优劣的函数称为指标函数.指标函数有有阶段的指标函数和过程的指标函数之分.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的某种效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]来表示某一阶段的决策的最短路径。过程的指标函数是指从状态[xn（k=1，2，...，n）]出发至过程最终，当采取某种子策略时，按预定的标准得到的效益值。这个值既与[xk]本身的状态值有关，又与[xk]以后所选取的策略有关，它是两者的函数值，记作[dk，nxk，uk，xk+1，uk+1，…xn，un]。过程的指标函数又是它所包含的各阶段指标函数的函数。本文研究的过程的的指标函数是其各阶段指标函数的和的形式.当[xk]的值确定后，指标函数的值就只同k阶段起的子策略有关。对应于从状态[xk]出发的最优子策略的效益值记作[fkxk]，于是在最短路问题中，有[fkxk=mindk，n]。动态规划求解最短路径程序流程图如图2所示。
3最短路径态规划实际应用举例
设某物流配送网络图由12个配送点组成，点1为配送中心起点，12为终点，试求自终点到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离[4]。
首先用动态规划法来讨论图3的最短路径，由图可知：
1）集合[ξ4]中有点9、10、11，它们在一步之内可到达点12；
2）集合[ξ3]中有点6，7，8，它们不超过两步就可达到点12；
3）集合[ξ2]中包括点2、3、4、5，不超过三步就可到达点12；
4）集合[ξ1]中包括点1，不超过四步可到达点12；
按照动态规划法类推，得到最优路径长为16，径路通过点为1，2，7，10，12和1，3，6，10，12。
根据动态规划算法编写C语言计算程序[5][6]，计算得到实验结果如下图4所示：
由图4可以看出程序得到的结果与本文推出的结果一样。证明了本文编写的C语言程序是正确的。
4结束语
综上所述，用动态规划解决多阶段决策问题效率高，而且思路清晰简便，同时易于实现.我们可以看到，动态规划方法的应用很广泛，已成功解决了许多实际问题，具有一定的实用性。此种算法我们用动态规划思想来编程，并解决相应的问题，其在VC环境下实现，能方便快速的计算出到达目的地的最短距离及路径，节省更多的运输时间与成本。不过，该文只考虑了动态规划算法在生活中的简单运用，在实际生活中可能存在多个目的地或者更复杂的情况.因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际生活中，这有待于以后的继续研究。
参考文献：
[1]杜彦娟.利用动态规划数学模型求解最短路径[J].煤炭技术，2005（1）：94-95.
运筹学最短路径篇7
以零营运资金为目标，对企业的营运资金实行“零营运资金管理”的方法，已成为90年代以来企业财务管理中一项卓有成效的方法。在我国随着现代企业制度改革的深化和企业经营管理的加强，企业理财的重要性也与日俱增，因此，“零营运资金管理”的方法，对我国企业也有着十分重要的借鉴意义。
一营运资金的管理问题
营运资金，从会计的角度看，是指流动资产与流动负债的差额。会计上不强调流动资产与流动负债的关系，而只是用它们的差额来反映一个企业的偿债能力。在这种情况下，不利于财务人员对营运资金的管理和认识；从财务角度看营运资金应该是流动资产与流动负债关系的总和，在这里“总和”不是数额的加总，而是关系的反映，这有利于财务人员意识到，对营运资金的管理要注意流动资产与流动负债这两个方面的问题。
流动资产是指可以在一年以内可超过一年的营业周期内实现变现或运用的资产，流动资产具有占用时间短、周转快、易变现等特点。企业拥有较多的流动资产，可在一定程度上降低财务风险。流动资产在资产负债表上主要包括以下项目：货币资金、短期投资、应收票据、应收账款和存货。
流动负债是指需要在一年或者超过一年的一个营业周期内偿还的债务。流动负债又称短期融资，具有成本低、偿还期短的特点，必须认真进行管理，否则，将使企业承受较大的风险。流动负债主要包括以下项目：短期借款、应付票据、应付账款、应付工资、应付税金及未交利润等。
为了有效地管理企业的营运资金，必须研究营运资金的特点，以便有针对性地进行管理。营运资金一般具有以下特点：
1周转时间短。根据这一特点，说明营运资金可以通过短期筹资方式加以解决。
2非现金形态的营运资金如存货、应收账款、短期有价证券容易变现，这一点对企业应付临时性的资金需求有重要意义。
3数量具有波动性。流动资产或流动负债容易受内外条件的影响，数量的波动往往很大。
4来源具有多样性。营运资金的需求问题既可通过长期筹资方式解决，也可通过短期筹资方式解决。仅短期筹资就有：银行短期借款、短期融资、商业信用、票据贴现等多种方式。
财务上的营运资金管理着重于投资，即企业在流动资产上的投资额。因而，要了解“零营运资金管理”的基本原理，就要首先了解营运资金的重要性。
营运资金管理是对企业流动资产及流动负债的管理。一个企业要维持正常的运转就必须要拥有适量的营运资金，因此，营运资金管理是企业财务管理的重要组成部分。据调查，公司财务经理有60%的时间都用于营运资金管理。要搞好营运资金管理，必须解决好流动资产和流动负债两个方面的问题，换句话说，就是下面两个问题：
第一，企业应该投资多少在流动资产上，即资金运用的管理。主要包括现金管理、应收账款管理和存货管理。
第二，企业应该怎样来进行流动资产的融资，即资金筹措的管理。包括银行短期借款的管理和商业信用的管理。
可见，营运资金管理的核心内容就是对资金运用和资金筹措的管理。
二“零营运资金管理”的基本原理
“零营运资金管理”的基本原理，就是从营运资金管理的着重点出发，在满足企业对流动资产基本需求的前提下，尽可能地降低企业在流动资产上的投资额，并大量地利用短期负债进行流动资产的融资。“零营运资金管理”是一种极限式的管理，它并不是要求营运资金真的为零，而是在满足一定条件下，尽量使营运资金趋于最小的管理模式。“零营运资金管理”属于营运资金管理决策方法中的风险性决策方法，这种方法的显著特点是：能使企业处于较高的盈利水平，但同时企业承受的风险也大，即所谓的高盈利、高风险。具体表现为：
1丰富的收益。一般而言，流动资产的盈利能力低于固定资产，短期投资的盈利低于长期投资。如工业企业运用劳动资料（厂房、机器设备等）对劳动对象进行加工，生产一定数量的产品，通过销售转化为应收账款或现金，最终可为企业带来利润。因此，通常将固定资产称为盈利性资产。与此相比，流动资产虽然也是生产经营中不可缺少的一部分，但除有价证券外，现金、应收账款、存货等流动资产只是为企业再生产活动正常提供必要的条件，它们本身并不具有直接的盈利性。又因为短期负债对债权人来说偿还的日期短、风险小，所以要求的利率就低，而债权人的利率就是债务人的成本，因此，短期负债的资金成本小于长期负债的资金成本。
把企业在货币资金、短期有价证券、应收账款和存货等流动资产上的投资尽量降低到最低限度，可以减少基本无报酬的货币资金和报酬较低的短期有价证券，将这些资金用于报酬较高的长期投资，以增加企业的收益；同时减少存货可使成本下降；减少应收账款可降低应收账款费用以及坏账损失。大量地利用短期负债可降低企业的资金成本，而且短期负债的弹性大、办理速度快，能及时弥补企业流动资产的短缺。显然，由于降低了企业在流动资产上的投资，就可以使企业减少流动资金占用，加速资金周转，降低费用，从而可以增加企业盈利。
2潜在的风险。从风险性分析，固定资产投资的风险大于流动资产。由流动资产比固定资产更易于变现，其潜在亏损的可能性或风险就小于固定资产。当然，固定资产也可通过在市场上出售将其变为现金，但固定资产为企业的主要生产手段，如将其出售，则企业将不复存在。因此，除了不需用固定资产出售转让外，企业生产经营中的固定资产未到迫不得已时（如面临破产）是不会出售的。所以，企业固定资产的变现能力较低。企业在一定时期持有的流动资产越多，承担的风险相对越小；反之，企业持有的流动资产越少，所承担的风险也就越大。另外，大量地利用短期负债，同样也可能导致风险的增加。一般来说，短期筹资的风险要比长期筹资要大。这是因为：第一，短期资金的到期日近，可能产生不能按时清偿的风险。例如，企业进行一项为期三年的投资，而只有在第三年才能会有现金流入，这时企业如果利用短期筹资，在第一、第二年里，企业就会面临很大的风险，因为企业的投资项目还没有为企业带来收益。但如果企业采用为期五年的长期筹资的话，企业就会从容地利用该投资项目产生的收益来偿还负债了。第二，短期负债在利息成本方面有较大的不确定性。如果采用长期筹资来融通资金，企业能明确地知道整个资金使用期间的利？
根据上面的观点，“零营运资金管理”原理的应用将使用权企业面临较大的风险。首先，企业有延期风险，即企业在到期日不能偿还债务的风险。如果企业需要延期，但会由于一些无法预料的因素而不能延期，如当短期负债到期时，企业的经营善变坏，以至债权人不肯延期；或在延期时，正好赶上国家经济不景气，市场上资金私有制，而无法继续延期；其次，短期负债利率的具有很大的波动性，企业无法预测资金成本，也就无法控制利息成本；再次，企业为了减少应收账款，变信用销售为现金销售，可能会丧失客户，从而影响销售的增长。
尽管存在着高风险，但“零营运资金管理”仍不失为一种管理资金的有效方法。“零营运资金管理”在具体操作上，以零营运资金为目标，着重衡量营运资金的运用效果，通过营运资金与总营业额比值的高低来判断一个企业在营运资金管理方面的业绩和水准。由于“零营运资金管理”的基本出发点是尽可能地降低在流动资产上的投资额，因而营运资金在总营业额中所占的比重越少越好。这就是“零营运资金管理”的含义所在。“零营运资金管理”强调的是资金的使用效益。如果资金过多地滞留在流动资金形态上，就会使企业的整个盈利降低。简而言之，“零营运资金管理”就是将营运资金视为投入资金成本，要以最小的流动资产投入获取最大的销售收入。
三实现“零营运资金管理”的有效途径
为了企业能够实现“零营运资金管理”，同样要从流动资产和流动负债两个方面着手。对流动资产来说，就是要尽量减少在流动资产上的投资额，加速资金周转；对流动负债来说，则是要有畅通的筹措短期资金的渠道，以便满足企业的日常运作需求，同时也要考虑短期资金成本的问题。下面分别从两个方面论述：
降低营运资金在总营业额中所占的比重的有效途径是，加速货币资金的周转循环。根据货币资金周转循环周期的时间长短，可以预测企业对流动资金的需求量。例如，企业用货币资金来购买原材料，原材料被加工成产成品，一部分产成品，企业通过现销渠道又把它马上转变为货币资金；而其它的产成品，企业通过信用销售的渠道，把它变为应收账款，应收账款则需要一段时间才能收账变为货币资金。
通过上面的论述可以看出企业的运作情况对货币资金投资的影响。如果企业在生产产成品上花费较长的时间，那么企业就得增加货币资金投资。从原材料变成产成品，再完成产品销售所需要的这段时间，我们称为存货周转期。企业运作能给货币资金投资带来另一种影响的是企业的销售策略，如果企业是运用现销方式销售产品，那么企业就不需要保留很多货币资金；但如果企业有信用交易的话，那它就得需要有较多的货币资金投入。因为这里存在着应收账款周转问题。当然，企业也可在购买存货时欠账，这就是说企业要推迟付款，如果可欠很长时间的账，那么货币资金投资的需求量就减少，这段延迟付款的时间称为展延的应付账款周转期。一般来说，企业货币资金的周转公式为：
货币资金周转期=存货周转期+应收账款周转期-展延的应付账款周转期
从上面的公式，我们可以看出要想减少货币周转期，从而使流动资产上占用的货币资金减少，实现“零营运资金管理”，就得从存货管理、应收账款管理和应付账款管理三个方面着手。对于存货管理，一方面要加强销售，通过销售的增长来减小存货周转期；另一个方面要通过确定订货成本、采购成本以及储存成本计算经济批量，控制在存货上占用的资金，使之最小。对于应收账款管理，在信用风险分析的基础上，企业要制定合理的信用标准、信用条件和收账政策；通过这些措施来鼓励客户尽早交付货款，从而加速应付账款的周转。展延的应付账款的管理，一般来说，企业越是拖延付款的时间就越对企业有利，但由于延期付款可能引起企业的信誉恶化，所以企业必须通过仔细的衡量、比较多种方案后再做出决定，选择对企业最为有利的方案。
流动负债即企业的短期融资问题是企业进行“零营运资金管理”的另一个重要方面。企业要想得到短期资金主要有两条渠道：一个是商业信用，另一个是短期银行借款。
商业信用是指在商品交易中以延期付款或预收货款进行购销活动而形成的借贷关系，它是企业直接的信用行为。商业信用产生于商品交换之中，其具体形式主要是应付账款、应付票据、预收账款等。据有关资料统计，这种短期筹资在许多企业中达流动负债的40%左右，它是企业重要的短期资金来源。商业信用筹资有一定的优点：
（1）商业信用非常方便。因为商业信用与商品买卖同时进行，属于一种自然性融资，不用作非常正规的安排。而且不需办理手续，一般也不附加条件，使用比较方便；
（2）使用灵活且具有弹性，企业可根据某个时期内所需资金的多少，灵活掌握；
（3）若没有现金折扣，或者企业不放弃现金折扣，以及使用不带息的应付票据，则企业利用商业筹资并不产生筹资成本。
其主要缺点是：
（1）其期限较短，尤其是应付账款，不利于企业对资金的统筹运用；
（2）对应付账款而言，若放弃现金折扣，则需负担较高的成本。对应付票据而言，若不带息，可利用的机会极少，若带息则成本较高；
（3）在法制不健全的情况下，若公司缺乏信誉，容易造成公司之间相互拖欠，影响资金运转。
短期银行借款是企业根据借款合同向银行以及非银行金融机构借入的款项。在我国，短期银行借款是绝大多数企业短期资金的主要来源。我国目前短期银行借款的目的和用途可分为周转借款、临时借款、结算借款、贴现借款等。
短期很行借款的优点有：
（1）银行资金充足，实力雄厚，能随时为企业提供较多的短期贷款。对于季节性和临时性的资金需求，采用银行短期借款尤为方便。而那些规模大、信誉好的大企业，更可以较低的利率借入资金。
（2）银行短期借款具有较好的弹性，可在资金需要增加时借入，在资金需要减少时还款。
短期银行借款的缺点主要有：
（1）资金成本较高。采用银行短期借款成本比较高，不仅不能与商业信用相比，与短期融资券相比也高出许多。而抵押借款因需要支付管理和服务费用，成本更高。
（2）限制较多。向银行借款，银行要对企业的经营和财务状况进行调查以后才能决定是否贷款，有些银行还要对企业有一定的控制权，要企业把流动比率、负债比率维持在一定的范围之内，这些都有会构成对企业的限制。
企业筹集短期资金的渠道还有短期融资券、应交税金、应交利润、应付工资、应付费用、票据贴现等多种形式，但无论采用哪种筹资方式，都有其优点和缺点。为了能够实现“零营运资金管理”，企业的财务人员一定要在分析、比较的基础上，选择筹资组合，在尽可能多地使用流动负债的基础上，要注意企业的清偿能力，保证企业的信誉，这样才能给企业带来最大的收益。
四“零营运资金管理”中应注意的问题
目前，我国企业制度的改革正在进一步深化，金融体制改革已经起步，金融市场正在不断发展和完善，我国金融正逐步走向国际化，这是我国企业加强营运资金管理所面临的外部环境。从企业自身的经营状况来看，有相当数量的企业管理水准低下，经营不善，销售不畅，产品积压，资金短缺，这是我国企业进行营运资金管理所处的内部环境。在这种情况下，运用“零营运资金管理”的基本原理，我国企业可以从以下几个方面加强管理：
1改善企业的生产条件，缩短企业的生产时间。目前，大多数国有企业技术落后、设备陈旧，严重影响了产品的生产效率，延长了产品生产所用的时间，也就减慢了资金周转，使一部分不必要的资金被占用在生产领域中。因此，企业财务人员要在条件允许的情况下，尽可能的提供资金为企业选购先进设备，以此来加速营运资金周转。同时，也要严格的控制生产过程中在产品、半成品的数量，加强企业的成本核算与控制，使在产品、半成品等在各个工序间顺利地流转，减少生产过程的停滞。
2存货积压过多的企业，首先应从打开销售渠道上下功夫，在日趋激烈的市场竞争中，善于分析研究企业的市场环境，制定有利于促进销售增长的信用政策，扩大销售，提高企业的竞争能力。其次，在实施应收账款尽早收账的策略中，学会运用最佳现金折扣法，尽可能地使现金折扣所产生的边际利润刚好等于其边际成本，既促使客户尽早地付款，又可使企业为此付出的代价达到最低。
3灵活选择结算方式，保持资金畅通。由于我国的金融体制改革还没有完全展开，银行结算方式落后，结算秩序混乱，跨银行、跨系统地款项支付要受到银行限制，在很大程度上制约了资金的流动。而且，每到考核时点如季末、年末，各商业银行便千方百计地保护自己的存款，导致企业大量的货币资金被积压，形成一种不必要的沉淀资金，在一定程度上加剧了企业的资金紧张局面。因此只有灵活的选择转账、商业汇票等结算方式，才能更好地加速营运资金的周转，实现“零营运资金管理”。
4企业应重视加强对流动负债的管理，学会充分地利用短期资金融资方式，以缓解企业紧迫的资金短缺困扰。例如，企业本来要用长期资金来融资的一些项目，由于金融市场不景气，企业借不到长期资金，可以暂时利用短期资金，等到将来金融市场好转再用长期资金替代。当前企业可采用的短期融资方式主要是商业信用和银行短期借款。企业要注意充分发挥短期资金融资的优点，管好、用好短期资金，努力经营，增加盈利，保持企业良好的财务状况，尽可能地避免或降低短期资金融资的高风险。
综上所述，对企业的营运资金实行“零营运资金管理”，力求达到零营运资金的目标，其实质是提高资金的运用效益，以最小的投入，获取最大的产出，这一思路与投入产出理论中的“资源最佳配置”原则是一致的。因此，可以说“零营运资金管理”的基本原理和管理资金的思路，在我国企业财务管理的理论与实践中，具有一定的借鉴意义和实用价值，这一方法的应用前景值得我们去探讨和研究。
参考书目：荆新。《财务管理学》，中国人民大学出版社，1998年月12月第2版夏乐书。
《公司财务理财学》，中国政治经济出版社，1998年12月第1版张绍学。
《现代公司理财学》，四川大学出版社，1997年9月第1版罗福凯。
《公司财务管理》，青岛海洋大学出版社，1997年11月第1版尹书亭。
《现代企业理财学》，复旦大学出版社，1995年8月第1版谷祺。
《财务管理》，东北财经大学出版社，2000年月12月第3版[美]道格拉斯。k.爱默瑞。
《公司财务管理》，中国人民大学出版社，1999年11月第1版向平。
《浅谈“零营运资金管理”》，
《财会月刊》，1997年第8期毛付根。
《论营运资金管理的基本原理》，
《会计研究》，1995年第1期邱元荣。
运筹学最短路径篇8
【关键词】流动资金；管理；原因；对策
【中图分类号】F270.3【文献标识码】a【文章编号】1005-1074(2009)05-0137-01
资金是企业的“血液”，是企业赖以生存的根本。在企业的生产经营活动中，资金发挥着极其重要的作用。它从货币形态开始，经过储备、生产、销售等过程，最后回到货币形态，它即是生产过程的起点，也是生产过程的终点，其地位和作用不言而喻，如果资金短缺，那么企业就意味着“供血不足”或“缺血”就会严重影响其生存和发展，这是困惑企业的一道难题，也是我们管理人员的一块“心病”。
目前，资金困难状况在企业中普遍存在，就铁路企业来讲，上至铁路局，下至基层站段，都不同程度的存在着资金短缺状况，生产很难维持，甚至连工资都不能保证,造成这种状况的主要原因有：①由于运输支出的增长大大超出了运输收入的增长，使成本得不到补偿，造成企业连年亏损，致使大量的资金被占压，很难解放，这是造成资金短缺的一个主要原因。②库存材料积压造成了资金紧张，我国铁路物资储备一直实行材料厂、站段设库，尤其是运输部门，为了保证行车安全，对材料储备存在多多益善的思想，造成库存超储严重，浪费大量的资金。③导致目前企业资金紧张还有一个很重要的原因，即企业的内部管理差，资金管理松弛，造成生产经营中资金的大量损失、浪费和无效使用。资金严重紧缺和资金的无效占用并存是许多企业普遍存在的问题。许多企业在生产经营活动中，不注重管理，致使生产消耗过高、普遍设备闲置，大量在职人员处于停业、待业的闲置状态，造成材料、以及劳动力的浪费，造成资金的浪费，还有许多企业在资金的筹集和使用上缺乏科学的预测和决策，资金能否充分利用，资金使用中，占用在各种形态上的资金如何管理等问题上，缺乏一套科学而完善的措施和制度，许多环节凭经验、凭感觉来进行管理和决策，致使许多资金使用中大量出现高投入、低产出、投资分散、规模效益差等现象，造成资金的无效使用和大量浪费。加之从资金的投入到资金的回收，缺乏有效的协调机制，造成个环节各自为政，相互衔接差。这种资金使用的低质量和管理上的松弛，又加剧了资金的紧张状况。④盲目性投资，加剧资金紧张局面。许多企业在安排投资项目时，缺乏严格投资可行性研究，盲目上马新项目，随意挤占流动资金。往往由于项目投资资金预测不足，不得不对投资项目资金需求进行压缩，一些企业把投资资金的缺口又以拖欠的形式转化成流动资金紧张，由此而产生的债务链又使流动资金紧张进一步加剧。从整个国民经济的角度来讲，由于投资压缩和投资资金紧张而造成投资需求不足，又往往会造成投资品的积压和企业流动资金的进一步沉淀，将投资资金紧张转化为流动资金紧张，从而进一步延缓解了资金的周转速度，加剧了资金紧张的困难。资金缺乏的原因是多方面的，既有国家政策及外部经济环境方面的影响，也有企业自身资金管理不利的因素，要解决资金短缺的根本途径。
一要提高经济效益，增加资金来源。企业要生存要发展，唯一的出路要把自己定位在市场竞争的大海洋中，要立足市场，占领市场，提高市场的占有份额，搞好营销，多创收入，增加资金流入，增加资金积累，增加经济实力。二是在资金的运用上，注重资金需求预测，进行科学的事前控制，企业在对资金需求量进行科学预测的基础上，结合企业资金状况和筹资方式，来合理的筹集生产经营所需资金。预算作为一种控制机制和制度化的程序，是完善资金集中管理的有效模式，一个健全的企业预算制度实际上是企业完善的法人治理结构的体现，预算制度完备是企业生产经营活动有序进行的重要保证，也是企业进行监督、控制，审计、考核的基本依据。企业要切实改变目前财务预算形同虚设的状况，建立健全全面预算管理机制，对生产经营各个环节实施预算的编制、分析、考核制度，把企业生产经营活动中的资金收支纳入严格的预算管理程序之中，就必须做到量入为出、精打细算、科学理财、严格考核。同时，计算机网络技术的广泛运用，为资金的全面预算和及时结算提供了可能，从而使资金的集中管理成为可行。在预算安排和资金运用过程中做到协调和一致，提高和加强管理中的事前控制。在组织、安排基建、更改、运输等多项支出计划时，首先必须考虑并做到量入为出、以收定支。减少和防止由于支出计划与资金运用不协调现象而造成的资金供需不平衡的矛盾，以及各款源之间相互挤占挪用资金，失去计划的合理性、严肃性。三要强化资金调度，发挥资金中心的职能作用，集中和吸收各种闲散资金，把小钱变大钱，积蓄资金存量。启动各种沉淀资金，通过融通手段，充分发挥资金效能，内部之间经济来往通过结算中心结转，减少资金在途时间，提高资金使用效率，减低资金成本，资金中心采取有偿占用，提高资金利用率。四是加强应收、预付款的清理工作，组织成立强有力的清欠小组，制定积极的收账政策，落实收账责任制，运用法律手段，坚持不懈地开展清欠工作，解放资金，以缓解资金紧张局势。五要狠抓材料采购供应和储备管理，加速资金周转，把好材料采购关键，是管好资金的关键要加强物资的归口管理和集中采购，统一招标，统一订货、这样大批量的集中采购可以降低成本，同时对采购渠道也起到规范和净化的作用，材料供应部门发挥其职能作用，保证物资的随时供应，减少使用部门的库存储备，解放和活化资金。
运筹学最短路径篇9
关键词:消防最优路径Dijkstra算法动态规划优化LinGo
中图分类号:文献标识码:a文章编号:1007-9416(2010)05-0000-00
1课题研究的背景[3]和意义
2001―2008年我国化工企业共发生较大及其以上级别事故119起,其中,死亡510人,重伤105人,轻伤377人。从2001年到2008年我国化工企业较大及其以上级别事故发生总趋势为波动上升,且单事故中伤亡人数在逐渐增加。尤其是从2004年开始,化工企业较大及以上级别事故的发生数量居高不下。目前,我国正处于经济快速上升期,工业发展正在不断加快,化工企业的生产技术日趋复杂,势必导致事故的多发性以及事故危害的日趋严重。城市消防救援对减少事故的损失意义重大,但在实际工作中往往由于消防救援路程不畅等各种迟滞因素使得消防人员丧失了对事故早期救援的良好时机。因此,对消防救援中最优路径选择问题的研究很有必要。
2最短路径问题的基本理论
2.1传统Dijkstra算法概述
传统Dijkstra算法过程的具体描述如下:
1)如果(u,)之间没有直接存在弧,则置w(u,)为。S为已找到的从u出发的最短路径的终点的集合,初始状态为空集。那么,从起点u到图上其余各项点可能到达的最短路径长度的初值为d(u,)=w(u,),是与起点邻接的点。2)选择,使得d(u,)=min{d(u,)/∈V-S}。
3)修改从顶点V∈S出发到集合V-S任一顶点唯可达的最短路径长度,如果d(u,)+w(,)
2.2建立最优路径数学模型
在道路交通网中,综合考虑各种因素把各条道路的通过时间作为权值赋予相应的路段,就得到一个赋权图G(V,e),对每一边e=(,)对应权值为w(e),设p为从起点到终点的所有路径的集合,若R是G中从到的一条路,则R∈p,定义路R的权为R中所有边权之和,计为w(R),即w(R)=∑w(e)。求一条从到的最短路,即求从到的的一条权最小的路使w()=minw(R)就是救援最优路线的基本模型。
3针对Dijkstra算法和线性规划对具体算例的分析应用
3.1最短路径问题的数学模型和解决
如图3.1所示,假设e点发生了化学事故,消防部队接到报警信息后出发,如何选择最短的路程到达目的地?
解决思想:此例中我们可以把从S到e的行驶过程分成5个阶段,即Se,其中必至少有一条距离最短的路线。记d(X,Y)为交叉路口X和Y之间的直接距离(如果这两个路口之间没有道路直接相连,则可以认为直接距离无穷大),用L(X)表示出发地点S到路口X的最优行驶路线的路长。则可以建立模型:L(S)=0;L(X)=min{L(Y)+d(Y,X)},XS,YX。为了解决问题更加迅速,便于处理更加复杂的路网,采用LinGo软件处理这个问题。为了简洁起见,只给出程序的有效结果
3.2最大流问题
之前的例子只是单纯的考虑最短路径的问题,并没有考虑出警的警力资源和道路通行能力的因素。现在假设道路的通行能力有限制,而警力资源足够充足。如何保证最大的警力资源到达救援现场且不浪费多余的救援力量出警?现在请看图3.2:
位于S的消防部队接到e点发生化学事故的求援报警时,正处于交通高峰期,每个路段的通行最大流量有限制。假设我们的消防部队救援资源充足,如何保证最大的救援力量到达现场?如图所示,每个交叉口之间表明了在出警前得知的道路最大通行能力。建立数学模型:设最大流为,为点i到点j的流量,为点i到点j的最大容量。我们可以推导出最大流的数学规划表达式为:
根据数学规划表达式我们用LinGo软件求解最大流问题。
为了简洁直观,我们只保留有用的结果。Globaloptimalsolutionfound.
由程序运行结果知:能到达事故现场的最大救援力量为11,F(i,j)为该道路上的通行量。
上面的实际问题中,在交叉路口之间道路的质量,红绿灯和车流量等各种因素的影响下,通过单位长度的道路所花费的时间也各不相同。因此,除了考虑最大救援力量外,还需考虑最大救援力量全部到达的最小时间。如图3.3:括号内第一个数字是所在道路的通行最大流量,第二个数字是通过该道路的单位时间。设为弧上(i,j)上的流量,为弧(i,j)上的单位消耗时间,为弧(i,j)上的容量,d是节点i处的净流量,则最大资源的最小消耗时间的数学规划的表达式为:
当为网络的最大流是,数学规划表示的就是最大流的最小时间问题。
用LinGo软件求解该问题,运行结果如下:objectivevalue:116.0000
因此,最大救援力量全部到达的最小时间为116单位。
4结语
本文通过Dijkstra算法和动态规划的基本原理,针对消防救援工作中最短路径、最大救援力量、最佳救援时间等存在的一系列问题进行了层层深入研究,针对具体算例设计了数学模型并运用LinGo软件编写解决该类问题的通用程序来实现该数学模型。通过求解所得到的结果说明了该模型对消防救援工作选择最优路径,减少救援时间具有实际应用价值,可以帮助消防部队在接到报警后更好的利用较短时间分配救援力量和选择最佳的救援路径,以争取更多救援时间,取得更好救援效果,减少人员伤亡和财产损失。
参考文献
[1]卢开澄,卢华明.图论及其应用.(第二版).北京:清华大学出版社,1995.
[2]郭耀煌.运筹学与工程系统分析.北京:中国建筑工业出版社,1986.
运筹学最短路径篇10
关键词：车辆路径问题；启发式算法；优化
中图分类号：U116.2文献标识码：a
abstract：Vehicleroutingproblemisthecoreprobleminlogisticsmanagementandintheorganizationandoptimizationoftransportation，andisaclassiccombinatorialoptimizationprobleminoperationsresearch.thisarticlesystematicallysummarizedthecommonclassificationsandthebasicmodelofVRpproblems.andthroughreferringtoscholars'researchsituation，summarizedthecommonlyusedandefficientheuristicalgorithmsofsolvingVRpproblemsandthepresentsituationofthecorrespondingresearch.Finally，summarizedtheproblemsintheresearchofVRpproblemsanddiscussedthefutureresearchandthesolvingmethodsforVRpproblems.
Keywords：vehicleroutingproblem；heuristicalgorithm；optimization
0引言
随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题（VehicleRoutingproblem，VRp）是制约物流行业发展的一个关键要素，其研究也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件（如时间限制、车载容量限制、交通限制等）下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser[1]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的np-难题。
企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRp作为物流系统优化环节中关键的一环，其研究成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。
1车辆路径问题的分类与基本模型
VRp的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约束条件等，根据侧重点的不同，VRp可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更复杂的车辆路径问题。
由于VRp的约束条件不同引起了其分类多种多样，而不同类型的VRp其模型构造及求解算法有很大差别。VRp的一般数学模型为：
在上述模型中，式（1）表示目标函数，式（2）表示约束条件。其他VRp模型大致都是在此模型的基础上根据约束条件完善形成的。
2VRp的求解算法与研究现状
VRp的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研究者们主要把精力集中在如何构造高质量的启发式算法上，本文也主要讨论一些近年来研究比较多的启发式优化算法。针对VRp问题目前已提出了大量的启发式算法，其中研究较多的主要包括以下算法：
2.1遗传算法（Geneticalgorithm，Ga）
Ga是一种通过模拟生物进化过程来搜索最优解的方法，该方法通过对群体进行选择、交叉和变异等操作，产生代表新的解集的种群，根据个体适应度大小选择个体，通过迭代逐步使群体进化到近似最优解状态。但是该算法具有搜索速度慢、易早熟、总体可行解质量不高等缺点。
采用遗传算法研究VRp问题的研究现状包括：蒋波[2]设计了遗传算法求解以配送总成本最小为目标函数和带有惩罚函数的VRptw模型；赵辰[3]基于遗传算法求解了从生产中心到仓库之间的路径优化问题，设计了配送路径优化决策；张群和颜瑞[4]建立了多配送中心、多车型车辆路径问题混合模型，并采用一种新的模糊遗传算法求解该问题。
2.2模拟退火算法（Simulatedannealing，Sa）
Sa同禁忌搜索算法一样，也属于局部搜素算法，但是模拟退火算法是模仿金属加工中退火的过程，通过一个温度函数作为目标函数，使其趋于最小值，是一种基于概率的算法。
采用模拟退火算法研究VRp问题的研究现状包括：郎茂祥[5]研究了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等[6]提出了一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌[7]以模拟退火算法为基础，研究了单个集散点与多个客户之间的运输问题；mirabi和FatemiGhomi等[8]提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送中心VRp模型。
2.3蚁群算法（antColonyoptimization，aCo）
蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制可使蚁群算法的搜索向最优解靠近。
采用蚁群算法研究VRp问题的研究现状包括：马建华等[9]研究了基于动态规划方法的多车场最快完成车辆路径问题的变异蚁群算法；辛颖[10]通过对mmaS蚁群算法进行了三种策略的改造，指出蚁群算法可以找到相对较好的解和很强的鲁棒性；陈迎欣[11]针对蚁群算法的缺点，分别对信息素更新策略、启发因子进行改进，引入搜索热区机制，有效解决车辆路径优化问题；段征宇等[12]通过最小成本的最邻近法生成蚁群算法和局部搜索操作设计了一种求解tDVRp问题的改进蚁群算法。
2.4粒子群算法（particleSwarmoptimization，pSo）
pSo算法是通过对鸟群觅食行为的研究而得出的一种群体并行优化算法，它从随机解出发，通过迭代寻找最优解。蚁群算法具有容易实现、收敛速度快、精度高等优点，在多种优化问题上均取得了较好的效果。但是由于pSo算法是通过粒子之间的相互作用来寻找最优解，缺乏像遗传算法那样的变异机制，因而pSo算法容易陷入局部最优。
采用粒子群算法研究VRp问题的研究现状包括：马炫等[13]提出了一种基于粒子交换原理的整数粒子更新方法求解有时间窗约束的车辆路径问题；吴耀华和张念志[14]以处理集货或送货非满载带时间窗车辆路径优化问题为背景，提出了带自调节机制的局部近邻粒子群算法解决VRp问题。
2.5蝙蝠算法（Batalgorithm，Ba）
蝙蝠算法是剑桥大学学者Yang[15]于2010年提出的一种新型群智能进化算法，模拟自然界中蝙蝠通过超声波搜索、捕食猎物的生物学特性，是一种基于种群的随机寻优算法。截至目前，蝙蝠算法主要用于求解连续域的函数优化问题，只有少数学者将其用来求解离散型问题，具有很好的研究前景。
采用蝙蝠算法研究VRp问题的研究现状包括：马祥丽等[16]将蝙蝠算法应用于求解VRp问题，在蝙蝠速度更新公式中引入了惯性权重，对基本蝙蝠算法进行了改进，克服了基本蝙蝠算法的不足之处；马祥丽等[16]针对VRptw问题的具体特性重新定义了蝙蝠算法的操作算子，设计了求解VRptw问题的蝙蝠算法，并采用罚函数的方式对目标函数进行了简化求解。
3总结与展望
车辆路径问题由于约束条件的不同其分类多种多样，数学模型与求解算法也层出不穷。本文总结了近几年一些相关学者对VRp问题的研究和求解算法，通过较为系统地总结VRp问题，本文总结出以下当前研究存在的问题和今后可能的研究方向：
（1）研究目标太过理想化。目前学者研究VRp的研究过于注重成本最小和路径最短，大部分是单目标优化，而在实际应用中，配送的驾驶员也可能会因许多原因耽误计划的行程，顾客的需求各异甚至冲突，顾客满意度与企业成本最小化目标之间存在效益悖反的矛盾。今后的研究可以将成本、路程、驾驶员休息、顾客满意度等多个目标联合起来进行研究，并可以通过线性加权的方式进行综合求解。
（2）单个约束的VRp问题由于研究时间较长，现在已经研究的较为成熟，而且其应用局限也比较大，应该考虑将多个约束条件结合起来，建立符合实际的多约束条件的车辆路径问题，更好地解决企业的配送优化。
（3）虽然启发式算法具有全局搜索能力强，运算方便等优点，但是也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题。使用单一的群智能算法不是求解VRp的最有效算法，将两种和多种群智能算法结合起来研究车辆路径问题，取长补短，是今后应该考虑的问题；同时，应考虑寻求更多的智能优化算法来求解VRp问题。
参考文献：
[1]GB.Dantzig，JK.Ramser.thetruckdispatchingproblem[J].managementScience，1959，6（1）：80-91.
[2]蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京：北京交通大学（硕士学位论文），2010.
[3]赵辰.基于遗传算法的车辆路径优化问题研究[D].天津：天津大学（硕士学位论文），2012.
[4]张群，颜瑞.基于改进遗传算法的混合车辆路径问题[J].中国管理科学，2012，20（2）：121-128.
[5]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报，2005，20（5）：485-491.
[6]穆东，王超，王胜春，等.基于并行模拟退火算法求解时间依懒型车辆路径问题[J].计算机集成制造系统，2015，21（6）：1626
-1636.
[7]魏江宁，夏唐斌.基于混合模拟退火算法的多阶段库存路径问题研究[J].工业工程与管理，2015，20（3）：1-8.
[8]mmirabi，SmtFGhomi，FJolai.efficentstochastichybridheuristicsforthemulti-depotvehicleroutingproblem[J].RoboticsandComputer-integratedmanufacturing，2010，26（6）：564-569.
[9]马建华，房勇，袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法[J].系统工程理论与实践，2011，31（8）：1508
-1516.
[10]辛颖.基于蚁群算法的车辆路径规划问题求解研究[D].长春：吉林大学（硕士学位论文），2015.
[11]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012，29（6）：2031-2034.
[12]段征宇，杨东援，王上.时间依赖型车辆路径问题的一种改进蚁群算法[J].控制理论与应用，2010，27（11）：1557-1563.
[13]马炫，彭m，刘庆.求解带时间窗车辆路径问题的改进粒子群算法[J].计算机工程与应用，2009，45（27）：200-204.
[14]吴耀华，张念志.带时间窗车辆路径问题的改进粒子群算法研究[J].计算机工程与应用，2010，46（15）：230-235.
[15]YangXS.anewmetaheuristicbat-inspiredalgorithm[C]//nature-inspiredCoopreativeStrategiesforoptimization，2010：65