页数:158页文件大小:3.98 MB来源: 运输管理ppt课件
本课件讲授物流运输决策,先说明运输决策的过程与主要环节,比较五种运输方式的技术经济特征并给出选择标准与成本权衡方法,再依次展开运输调运决策的产销平衡模型、运输路线的选择与优化方法,以及运输工具的选择与更新决策。
第7章运输决策7.1运输方式选择7.2运输调运决策7.3运输路线选择和优化7.4运输工具配置优化.复习思考
学习目标了解物流运输决策的过程;熟悉决策中的主要环节;掌握运输方式的选择、运输线路的确定、运输服务商的选择;了解运输优化的概念、内容、作用;掌握运输优化的方法,特别是图上作业法、表上作业法,并能用这些方法解决实际问题。
7.1运输方式的选择
一般来讲,影响运输方式选择的因素可以分成两种类型。一种类型是不可变因素:运输物品的种类,运输量,运输距离;另一种类型是可变量因素:运输时间;运输成本。
2.选择运输方式应考虑的宏观环境
(1)经济环境或社会环境的变化,给物流活动带来了过去未曾有过的许多制约,如石油等能源物资的涨价或供应限制,这一制约直接影响到物流业最重要的生产运输工具。目前,物流业正在设法确保石油供应渠道,开发节能搬运工具,研究并采用效率高的运输系统。
4.运输的小批量化
在货主加强物流管理后,原材料和成品的库存量不断降低。企业原则上是作业开始之前才让原材料或商品进厂,作业结束后立即让产品或商品出厂,其中间过程为运输时间。换言之,即运输活动被置于货主的业务流程之中。因此不只是要求运输速度快,而且要求及时准确。因此,货主对运输工具进行选择时,要重视运输方式的准确性和灵活性。
(1)出现了以节能省力为目的,使每一个运输批量投入的劳动力和燃料趋于最少的搬运工具大型化。
7.1.2运输方式的比较与选择
如果从运输能力、货物送达速度、适用范围、可达程度、能源消耗、运输成本、包装要求、受环境影响程度、占用土地数量、大气污染等10项主要指标予以比较并排序。
7.1.3运输方式的选择标准
基本的成本权衡
如果不将运输服务作为竞争手段,那么能够使该运输服务的成本与该运输服务水平导致的相关间接库存成本之间达到平衡的运输服务就是最佳服务方案。
运输的速度和可靠性会影响托运人和买方的库存水平(订货库存和安全库存)以及他们之间的在途库存水平,速度慢、可靠性差的运输服务必将导致物流渠道中更多的库存。
例子:卡利奥箱包公司
铁路的平均运输时间为T=21天,每个存储点平均存储100000件行李箱包,箱包的平均价值C=30美元,库存成本I=30%/年。
据估计,运输时间从目前的21天每减少一天,平均库存水平可以减少1%。每年西海岸仓库卖出D=700000件箱包。公司可以利用以下运输服务:每年运输批次门到门运输时间(天)运输费率(美元/单位)运输服务方式10210.10铁路运输20140.15驮背运输2050.20卡车运输4020.40航空运输
卡利奥箱包公司对运输方式的评估计算表
卡利奥箱包公司对运输方式的评估计算表航空运输卡车运输驮背运输铁路运输计算方法成本类型(1.40)(700000)=980000(0.20)(700000)=140000(0.15)(700000)=105000(0.10)(700000)=70000RD运输成本(0.30)(30)(700000)(2)/365=34521(0.30)(30)(700000)(5)/365=86301(0.30)(30)(700000)(14)/365=241644(0.30)(30)(700000)(21)/365=363465ICDT/365在途库存(0.30)(30)(25000)(0.81)=182250(0.30)(30)(50000)(0.84)=378000(0.30)(30)(50000)(0.93)=418500(0.30)(30)(100000)=900000ICQ/2工厂库存(0.30
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
2.运输速度
例子:匹兹堡制造商的供应商选择
位于匹兹堡的一家设备制造商需要从两个供应商那里购买3000箱塑料配件,每箱配件的价格是100美元。目前,从两个供应商采购的数量是一样的。两个供应商都采用铁路运输,平均运输时间也相同。但如果其中一个供应商能够将平均交付时间缩短,那么每缩短一天,制造商将会将采购订单的5%(即150箱)转给这个供应商。如果不考虑运输成本,供应商每卖出一箱配件可以获得20%的利润。
各种运输方式下每箱配件的运输费率和平均运送时间已知如下:运送时间(天)运输费率(美元/箱)运输方式72.50铁路运输46.00卡车运输210.35航空运输
不同运输方式下供应商A的利润对比纯利
不同运输方式下供应商A的利润对比纯利(美元)运输成本(美元)毛利(美元)销售量(箱)运输方式262503750300001500铁路运输2730011700390001950卡车运输21712.523287.5450002250航空运输
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
7.2运输调运决策
企业在从事物流活动中,不可避免地要进行物资调运工作,如某时期内将生产基地的煤、钢铁、粮食等各类物资,分别运到需要这些物资的地区。根据各地的生产量和需求量及各地之间的运输费用,如何制定一个运输方案,使得满足需求情况下运输费用最小,这样的问题称为运输调运决策问题。
某物流公司从两个产地A1(内蒙)、A2(山西)将煤炭运往三个销地B1(北京)、B2(山东)、B3(上海),各产地的产量、各销地的销量、各产地运往各销地的每单位煤炭运费数据见下表,问:应如何调运煤炭可使总运输费用最小?产量B3B2B1销地产地200646A1300556A2500200150150销量解:此为产销平衡的运输问题(总产量=总销量)。设xij为从产地Ai(i=1,2)运往销地Bj(j=1,2,3)的运输量,x11x12x13x21x22x23则该问题的数学模型为
x23x22x21x13x12x11
x23x22x21x13x12x11产地约束111A=111销地约束111111
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
x23x22x21x13x12x11产地约束111A=111销地约束111111可以看出运输问题的系数矩阵有如下特征:(1)共有3+2行,分别表示各产地和销地;3×2列,分别表示各决策变量的系数列;(2)每列只有两个1,其余为0,分别表示只有一个产地和一个销地被使用,由xij的行列下标所决定,这是运输问题表上作业法的由来。
2、运输问题的数学模型一般地,产销平衡的运输问题可以表述为:设有m个地点(称为产地或发地)A1,A2,…,Am的某种物资调至n个地点B1,B2,…,Bn(称为销地或收地),各个产地需要调出的物资量分别为a1,a2,…,am单位,各个销地需要调进的物资量分别为b1,b2,…,bn单位,且各个发点的供应量之和等于各个收点的需求量之和。已知每个发点Ai到每个收点Bj的物资单位调运价格为cij。现问如何安排调运,才能使总运费最小。
供应量Bn…B2B1销地产地a1c1
供应量Bn…B2B1销地产地a1c1n…c12c11A1a2c2n…c22c21A2………………amcmn…cm2cm1Ambn…b2b1需求量设xij表示从产地Ai运往销地Bj的运量,x11x12x1nx21x22x2nxm1xm2xmn于是产销平衡运输问题的数学模型为:V:s.t.
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
bcmnxmn……cm2xm2cm1
bcmnxmn……cm2xm2cm1xm1…c2nx2n……c22x22c21x21c1nx1n……c12x12c11x11a11…11a21…11……am1…11b11…11b21…11…………bn1…11C=XT=A=pmn…pm2pm1…p2n…p22p21p1n…p12p11A==b平衡运输问题模型写成矩阵形式为:
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
在实际问题建立运输问题模型时,还会出现如下一些变化:1)有时问题表面看不是运输问题,但其仍要求费用最低或要求目标函数(利润或营业额)最大化,仍可看成运输问题;2)当某些运输线路上的能力有限制时,模型中可直接加入(等式或不等式)约束。运输问题的数学模型的特征运输问题是一类线性规划问题,其目标函数一般为求总运费的极小值。根据线性规划的有关理论,如果它的最优解存在,一定可以在基可行解中找到,因而需先考察运输问题约束方程组系数矩阵的秩r(A) .定理平衡运输问题模型的系数矩阵的秩r(A)=m+n-1。运输问题是特殊的线性规划,单纯形法仍适合于运输问题。为此还要了解运输问题基可行解的性质,为说明其基本可行解的特征,引入闭回路的概念。m+n个约束中有一个是多余的(因为其间含有一个平衡关系式),所以R(A)=m+n-1,即解的个变量中基变量为m+n-1个。
定义在平衡运输问题的决策变量表中
定义在平衡运输问题的决策变量表中,凡是能够排列成下列形式的xab,xad,xcd,xce, …,xst,xsb或xab,xcb,xcd,xed, …,xst,xat其中,a,d,s各不相同;b,c,t各不相同,称这些变量的集合为一闭回路,并将上式中的决策变量称为该闭回路的顶点。例如x13,x16,x36,x34,x24,x23;x23,x53,x55,x45,x41,x21等都是闭回路,这些决策变量就是闭回路的顶点。B6B5B4B3B2B1x16x15x14x13x12x11A1x26x25x24x23x22x21A2x36x35x34x33x32x31A3x46x45x44x43x42x41A4x56x55x54x53x52x51A5
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
根据闭回路可以看出其的一些明显特点,闭回路是一个具有如下条件顶点格子的集合:1)每一个顶点格子都是转角点;2)每一行(或列)若有闭回路的顶点,则必有两个顶点;3)每两个顶点格子的连线都是水平的或垂直的;4)闭回路中顶点的个数必为偶数。定理对于产销平衡运输问题的闭回路来说,具有下面结论:1)该问题m+n-1个变量构成基变量的充要条件是这些变量不包含任何闭回路;2)给定一组基变量,那么从决策变量表中可找出唯一一个从任意非基变量出发,经过基变量为顶点,又回到该非基变量的闭回路。事实上,闭回路是一个简化的局部调运方案,反映了全局调运方案是否最优。定理3.2给出了运输问题基本解的重要性质,为寻求运输问题的基本可行解提供了依据。与一般的线性规划问题有所不同,产销平衡的运输问题总是存在可行解,且目标函数值有界,故运输问题必有最优解。
表上作业法的主要步骤:第一步求一个初始基可行解,即确定初始调运方案。第二步检验当前可行方案是否最优,常用的方法有闭回路法和位势法,用这两种方法计算出检验数,从而判别方案是否最优第三步换基迭代(即调整运量)。选一个变量出基,对原运输方案进行调整得到新的调运方案,改进当前方案,常采用闭回路法。开始给出初始运输方案结束检验运输方案是否最优改进运输方案yesno(1)西北角法(2)最小元素法(3)差值(Vogel)法(1)闭回路法(2)位势法
1初始基可行解的确定确定初始可行解常用的方法有西北角法、最小元素法和差值(Vogel近似)法。
西北角法从产销平衡表的西北角(左上角)第一格开始,按集中供应的原则,依次安排调运量,即分析对应产地和销地的供需数量关系,尽最大可能满足需求,若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;接着从未被划线的运价中再找出西北角的方格,重复上述操作,如此进行下去,直至得到一个基本可行解。设某种产品有三个生产厂商A1、A2、A3,联合供应四个销地B1、B2、B3、B4,其供应量、需要量和单位产品的运输成本见下表,试求一调运方案。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A148291A2951047A3206563需求量西北角法确定出的初始调运方案为:由A1→B1运3;A1→B2运4;A2→B2运2;A2→B3运2;A3→B3运3;A3→B4运6,方案的运输总费用为
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
由A1→B3运7
由A1→B3运7;A2→B1运3;A2→B4运6;A3→B2运5;A3→B4运2,方案的运输总费用为最小元素法确定出的初始调运方案为:供应量B4B3B2B1销地产地711101312A1910141210A2712151114A3238753需求量
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
用最小元素法求例3.2运输问题的初始
用最小元素法求例3.2运输问题的初始调运方案。供应量B4B3B2B1销地产地7103113A148291A2951047A3206563需求量由A1→B3运4;A1→B4运3;A2→B1运3;A2→B3运1;A3→B2运6;A3→B4运3,方案的运输总费用为最小元素法确定出的初始调运方案为:
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
差值法(Vogel法)差值法又称为伏格尔法。最小元素法只考虑了局部的运输费用最小,有时为了节省某一处运费,可能会导致其他处运费很大,缺乏对整个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额,如果差额很大,就选最小运价先调运,不然就会增加总的费用。差额法考虑产地和销地最小和次小运价的差额,如果差额很大,就选最小运价先调运,不然就会增加总的费用。差值法的步骤如下:1)算出单位运价表各行各列中次小元素和最小元素的差额;2)在差额最大的行或列中的最小元素处填上尽可能大的调运数(若几个差额同为最大,则可任取其一);3)这时必有一列或一行调运完毕,在剩下的运价表中再求最大差额,进行第二次调运,直至最后调运完毕,就得到一个初始调运方案。
用差值法求例3.2的初始调运方案
用差值法求例3.2的初始调运方案。供应量B4B3B2B1销地产地7103113A148291A2951047A36563需求量25130115327672210810
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
用差值法求例3.2的初始调运方案
用差值法求例3.2的初始调运方案。供应量B4B3B2B1销地产地7103113A12548291A213951047A3366563需求量由A1→B3运5;A1→B4运2;A2→B1运3;A2→B4运1;A3→B2运6;A3→B4运3,方案的运输总费用为差值法确定出的初始调运方案为:
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
闭回路法根据单纯形法原理,要判断某个可行解是否为最优解,需要计算非基变量的检验数。用闭回路法求检验数时,对于给定的调运方案(基可行解),从非基变量xij(空格)出发作一条闭回路,并从xij(空格)开始将该闭回路上的顶点顺序编号(顺时针或逆时针均可),起点xij为零,依此类推。称编号为奇数的点为奇点,编号为偶数的点为偶点,则对应xij的检验数σij等于该闭回路上偶点处单位运价的总和与奇点处单位运价的总和之差,即σij=偶点处单位运价的总和-奇点处单位运价的总和求例3.4给出的可行解所对应的非基变量检验数。检验数的经济含义:当生产地Ai往销地Bj增运一个单位货物时所引起的总运输成本的变化数。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A13448291A213951047A3366563需求量0123
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A134148291A213951047A3366563需求量0123
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A1342148291A213951047A3366563需求量012345
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A1342148291A2113951047A3366563需求量0123
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A1342148291A2-1113951047A3366563需求量123450
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A1342148291A2-1113951047A336106563需求量1230
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地7103113A1342148291A2-1113951047A33126106563需求量注:如果全部检验数均为正数或零,则调运方案一定为最优方案;如果检验数中仍存在负数,则调运方案不是最优方案。
位势法位势法的步骤为:1)在产销平衡表中,即调运方案中增加ui行和vj列,但在相应的基变量格(即数字格中)不是填写调运量,而是填写相应的运价,写在格的左上角;2)令u1=0或vn=0,根据式cij-(ui+vj)=0(其中xij为基变量)依一定次序计算和,将结果填写在表中;3)将非基变量的运价填入相应格的左上角,根据式σij=cij-(ui+vj)(其中xij为非基变量)计算相应的检验数,将结果填入相应格,写在该格的右下角。应用位势法求例3.4给出的初始可行解所对应的非基变量的检验数。
uiB4B3B2B1销地产地1031
uiB4B3B2B1销地产地103113A1348291A21351047A336vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
uiB4B3B2B1销地产地u1=0
uiB4B3B2B1销地产地u1=0103113A134u2=-18291A213u3=-551047A336v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
uiB4B3B2B1销地产地u1=0
uiB4B3B2B1销地产地u1=0103113A1341u2=-18291A213u3=-551047A336v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
7.2运输问题的表上作业法uiB4B
7.2运输问题的表上作业法uiB4B3B2B1销地产地u1=0103113A13421u2=-18291A213u3=-551047A336v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
uiB4B3B2B1销地产地u1=0
uiB4B3B2B1销地产地u1=0103113A13421u2=-18291A2113u3=-551047A336v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
7.2运输问题的表上作业法uiB4B
7.2运输问题的表上作业法uiB4B3B2B1销地产地u1=0103113A13421u2=-18291A2-1113u3=-551047A336v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
uiB4B3B2B1销地产地u1=0
uiB4B3B2B1销地产地u1=0103113A13421u2=-18291A2-1113u3=-551047A33610v4=10v3=3v2=9v1=2vj
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
uiB4B3B2B1销地产地u1=0103113A13421u2=-18291A2-1113u3=-551047A3312610v4=10v3=3v2=9v1=2vj注:闭回路法的主要缺点是当变量个数较多时,寻找闭回路以及计算两方面都会产生困难。当运输问题的产地与销地很多时,空格的数目很多,用闭回路法计算检验数,要找很多的闭回路,计算量很大,而用位势法就简便得多。
3闭回路的调整当初始基本可行解非基变量的检验数出现负数时,便需换基迭代。具体步骤如下:1)若有两个和两个以上的负检验数时,一般选择其中最小的负检验数,以它对应的空格为调入格,以此格为出发点,作一闭回路,并从该空格出发,沿闭回路,将各顶点依次编号,空格编号为0。2)取奇点所在格中最小的运量(记为θ),然后在闭回路中偶点增加θ、奇点减少θ,得出新的调整方案。说明:重新计算空格的检验数。如果所有的检验数都为正数或零,那么求出的就是最优解,不然,重复上述过程。【练习】应用闭回路调整例3.4给出的初始可行解,并计算所对应的新的可行解非基变量的检验数。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A1342148291A2-1113951047A33126106563需求量0123
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地710
供应量B4B3B2B1销地产地7103113A12548291A213951047A3366563需求量
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
供应量B4B3B2B1销地产地7103113A1252048291A21123951047A3312696563需求量注:若闭回路的偶数顶点中同时有两个格以上运量为θ,则调整后其中一个变空格,其余填0。(保证基变量个数不变)
课堂练习求运输问题的最优调运方案供应
课堂练习求运输问题的最优调运方案供应量B4B3B2B1销地产地5013191815A13017151420A27022171225A3150\15040206030需求量
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
7.3运输路线选择和优化
1.确定运输路线运输路线的确定会直接影响到运输效果的好坏,关系着物资能否及时运到指定地点。此外,当运输费用是以吨·千米来计算时,运输路线的长短就直接关系着运输费用的多少。因此运输路线的选择也是物资调运规划的一个重要内容。
2.物流调运流量某项物资从m个产地或仓库(统称为发点),调运到”个需要地(称为收点),在指定调运方案时,要先画一个示意的交通图,表明收发点的的大致位置、收发量、交通路线长度(不必与实际长度成比例)。
7.3.2消除物流调运不合理现象
即同一物资在同一线路上的往返运输,如图7.3,2.迂回图7.4迂回运输图图7.5无迂回运输图图7.3消灭了对流的调运流量图
V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5,e6}其中e1=(v1,v1),e2= (v1,v2),e3=(v1,v3),e4= (v3,v4),e5= (v3,v4),e6=(v1,v4)对于边ek=(vi,vj),称vi,vj为边ek的端点,这时也称vi,vj相邻;若两条边有一个公共端点v,则称这两边相邻;若两端点之间多于一条边,称为多重边;若一条边的两个端点相同,则称此为环(自回路)。
点边序列中只有重复的点而无重复边的链称为简单链;点边序列中没有重复的点和重复边者称为初等链;首尾相接的链称为圈。简单链初等链圈
在各种各样的图中,有一类图极为简单却很实用,这就是树图。树、支撑树一个无圈的连通图称为树;若该连通图还是一个支撑子图,则称这棵树为支撑树,也叫生成树。【】六个城镇v1,v2,v3,v4,v5,v6的一个通信网图是一棵树,见下图。支撑树非支撑树
7.3.4最小树的算法——破圈法最常用的最小树的算法是由Kruskal(克鲁斯卡尔)给出的破圈和避圈法。破圈法的步骤1)在给定的赋权图上任找一个圈;2)在所找的圈中去掉一条权数最大的边(若有两条或两条以上边都是权数最大的边,那么就任意去掉其中一条);3)若所剩下的图中已经不含圈,则计算停止;否则,返回2)重新迭代计算。是否寻找一个圈余下图是否有圈结束破圈法求解步骤流程图丢掉权数最大的一条边得到一个新圈
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。
解:先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型。可见其中充满了圈,从中寻求最小树便成为解题的关键。此时图已不含圈,所得图即为最小树,亦即施工路线图,其权为13,加上A到煤气公司的1.5km,总共需铺设管道长度为14.5km,所需费用为14.5×1000×25=362500(元)。
7.3.5最小树的算法——避圈法避圈法也称为加边法,开始选一条最小权的边,以后每一步中,总从未被选中的边中选一条最小权的边,使之与已选的边不构成圈,直到所有的边都检验完,即可得最小树。(每步中,若有两条或两条以上的边都是权最小的边,则从中任选一条)。其步骤如下:1)在给定的赋权图上找一条权数最小的边;2)加入这条边,构建一个新图;3)若在新图中找到了n-1条边,则计算停止;否则,在原图中找一条与新图边相邻且权数最小的边,注意该边与新图现有的边不能构成圈,返回2)继续迭代计算。
7.3.6最短路问题最短路问题的一般提法是在给定网络图中找出任意两点间距离最短的一条路,可考虑有向图和无向图中的最短路。最短路问题是网络理论中应用最广泛的问题之一,许多优化问题可以使用这个模型,如管道铺设,设备更新,线路安排等。最短路问题最简单、最常用的求解方法是Dijkstra、Floyd算法。定义最短路给定一个网络图D=(V,A,W),记D中每一条弧aij=(vi,vj)上的权为wij。给定D中一个起点vs和终点vt,设P是D中从vs到vt的一条路,则定义路P的权是P中所有弧的权之和,记为w(P),即又若P*是D中vs到vt的一条路,且满足w(P*)=min{w(P)|P是vs到vt的路}则称P*为从vs到vt的最短路,是w(P*)从vs到vt的最短距离。在一个图D=(V,A,W)中,求从vs到vt的最短路或最短距离的问题称为最短路问题。
7.3.6.1最短路问题的Dijkstra算法Dijkstra算法于1959年提出,适用于求具有非负权的有向图中的最短路,是目前公认的求无负权网络最短路问题的最好算法。Dijkstra算法是一种标记法,它的基本思路是从起点vs出发,逐步向外探寻最短路,执行过程中,给每一个顶点vj标号(λj,lj),其中λj是正数,它表示获得此标号的前一来点的编号;lj或表示从起点vs到该点vj的最短路的权(称为固定标号,记为P标号),或表示从起点vs到该点vj的最短路权的上界(称为临时标号,记为T标号)。该方法的每一步是去修改T标号,并且把某一个具有T标号的点改变为具有P标号的点,从而使图D中具有P标号的顶点数多一个,这样经过有限步,就可以求出从vs到vt及各点的最短路,再根据每一点的第一个数λj反向追踪找出最短路径。Dijkstra算法的具体步骤:用P,T分别表示某个顶点的P标号、T标号,Si表示在第i步已具有P标号点的集合。
开始时,令i=0,S0={vs},λs=0,P(vs)=0,对每个vj≠vs,取T(vj)=+∞,λj=s,k=s。1)如果Si=V,算法终止。这时,对每个lj,=P(vj);否则转下一步。2)设vk是刚获得P标号的点,考察每个使(vk,vj)∈A且vj∈\Si的点vj,将T(vj)修改为T(vj)=min{T(vj),P(vk)+wkj} .如果T(vj)>P(vk)+wkj,则把T(vj)修改为P(vk)+wkj,把λj修改为k;否则不修改。3)令,其中。如果T(vji)< +∞,则把vji的T标号变为P标号,即令T(vji)=P(vji),令Si+1= Si∪{vji},k=ji,把i换成i+1,返回1);否则终止,这时对每一个vj∈Si,有l(vj) = P(vj);而对每一个vj∈\Si,有l(vj) = T(vj)。
(0,0)(1,+∞)(1,+∞)(1,+∞)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代1(i=1):考察与v1相邻的点v2,v3,v4,因(v1,v2)∈A,v2∈\S0,故把v2的临时标号修改为T(v2)=min{T(v2),P(v1)+w12}=min{+∞,0+3}=3这时λ2=1。
(0,0)(1,3)(1,+∞)(1,+∞)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代1(i=1):考察与v1相邻的点v2,v3,v4,因(v1,v2)∈A,v2∈\S0,故把v2的临时标号修改为T(v2)=min{T(v2),P(v1)+w12}=min{+∞,0+3}=3这时λ2=1。同理,得T(v3)=min{T(v3),P(v1)+w13}=min{+∞,0+5}=5,λ3=1T(v4)=min{T(v4),P(v1)+w14}=min{+∞,0+6}=6,λ4=1
(0,0)(1,3)(1,5)(1,6)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代1(i=1):考察与v1相邻的点v2,v3,v4,因(v1,v2)∈A,v2∈\S0,故把v2的临时标号修改为T(v2)=min{T(v2),P(v1)+w12}=min{+∞,0+3}=3这时λ2=1。同理,得T(v3)=min{T(v3),P(v1)+w13}=min{+∞,0+5}=5,λ3=1T(v4)=min{T(v4),P(v1)+w14}=min{+∞,0+6}=6,λ4=1其余点的T标号不变,在所有的T标号中,最小的为T(v2),于是将v2的标号改为P标号,
(0,0)(1,3)(1,5)(1,6)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代1(i=1):考察与v1相邻的点v2,v3,v4,因(v1,v2)∈A,v2∈\S0,故把v2的临时标号修改为T(v2)=min{T(v2),P(v1)+w12}=min{+∞,0+3}=3这时λ2=1。同理,得T(v3)=min{T(v3),P(v1)+w13}=min{+∞,0+5}=5,λ3=1T(v4)=min{T(v4),P(v1)+w14}=min{+∞,0+6}=6,λ4=1其余点的T标号不变,在所有的T标号中,最小的为T(v2),于是将v2的标号改为P标号,此时有S1= S0∪{v2}={v1,v2},λ2=1,P(v2)=3,i=1
(0,0)(1,3)(1,5)(1,6)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代2(i=2):这时v2为刚获得P标号的点,考察与v2相邻的点v3,v5,v6,因(v2,v3)∈A,v3∈\S1,故把v3的临时标号修改为T(v3)=min{T(v3),P(v2)+w23}=min{5,3+1}=4这时λ3=2。
(0,0)(1,3)(2,4)(1,6)(1,+∞)(1,+∞)(1,+∞)(1,+∞)迭代2(i=2):这时v2为刚获得P标号的点,考察与v2相邻的点v3,v5,v6,因(v2,v3)∈A,v3∈\S1,故把v3的临时标号修改为T(v3)=min{T(v3),P(v2)+w23}=min{5,3+1}=4这时λ3=2。同理,得T(v5)=min{T(v5),P(v2)+w25}=min{+∞,3+7}=10,λ5=2T(v6)=min{T(v6),P(v2)+w26}=min{+∞,3+4}=7,λ6=2
(0,0)(1,3)(2,4)(1,6)(1,+∞)(2,7)(2,10)(1,+∞)迭代2(i=2):这时v2为刚获得P标号的点,考察与v2相邻的点v3,v5,v6,因(v2,v3)∈A,v3∈\S1,故把v3的临时标号修改为T(v3)=min{T(v3),P(v2)+w23}=min{5,3+1}=4这时λ3=2。同理,得T(v5)=min{T(v5),P(v2)+w25}=min{+∞,3+7}=10,λ5=2T(v6)=min{T(v6),P(v2)+w26}=min{+∞,3+4}=7,λ6=2其余点的T标号不变,在所有的T标号中,最小的为T(v3),于是将v3的标号改为P标号,
(0,0)(1,3)(2,4)(1,6)(1,+∞)(2,7)(2,10)(1,+∞)迭代2(i=2):这时v2为刚获得P标号的点,考察与v2相邻的点v3,v5,v6,因(v2,v3)∈A,v3∈\S1,故把v3的临时标号修改为T(v3)=min{T(v3),P(v2)+w23}=min{5,3+1}=4这时λ3=2。同理,得T(v5)=min{T(v5),P(v2)+w25}=min{+∞,3+7}=10,λ5=2T(v6)=min{T(v6),P(v2)+w26}=min{+∞,3+4}=7,λ6=2其余点的T标号不变,在所有的T标号中,最小的为T(v3),于是将v3的标号改为P标号,此时有S2= S1∪{v3}={v1,v2,v3},λ3=2,P(v3)=4,i=2
(0,0)(1,3)(2,4)(1,6)(1,+∞)(2,7)(2,10)(1,+∞)迭代3(i=3):这时v3为刚获得P标号的点,考察与v3相邻的点v4,v6,因(v3,v4)∈A,v4∈\S2,故把v4的临时标号修改为T(v4)=min{T(v4),P(v3)+w34}=min{6,4+1}=5这时λ4=3。
(0,0)(1,3)(2,4)(3,5)(1,+∞)(2,7)(2,10)(1,+∞)迭代3(i=3):这时v3为刚获得P标号的点,考察与v2相邻的点v4,v6,因(v3,v4)∈A,v4∈\S2,故把v4的临时标号修改为T(v4)=min{T(v4),P(v3)+w34}=min{6,4+1}=5这时λ4=3。同理,得T(v6)=min{T(v6),P(v3)+w36}=min{7,4+2}=6,λ6=3
(0,0)(1,3)(2,4)(3,5)(1,+∞)(3,6)(2,10)(1,+∞)迭代3(i=3):这时v3为刚获得P标号的点,考察与v3相邻的点v4,v6,因(v3,v4)∈A,v4∈\S2,故把v4的临时标号修改为T(v4)=min{T(v4),P(v3)+w34}=min{6,4+1}=5这时λ4=3。同理,得T(v6)=min{T(v6),P(v3)+w36}=min{7,4+2}=6,λ6=3其余点的T标号不变,在所有的T标号中,最小的为T(v4),于是将v4的标号改为P标号,
(0,0)(1,3)(2,4)(3,5)(1,+∞)(3,6)(2,10)(1,+∞)迭代3(i=3):这时v3为刚获得P标号的点,考察与v3相邻的点v4,v6,因(v3,v4)∈A,v4∈\S2,故把v4的临时标号修改为T(v4)=min{T(v4),P(v3)+w34}=min{6,4+1}=5这时λ4=3。同理,得T(v6)=min{T(v6),P(v3)+w36}=min{7,4+2}=6,λ6=3其余点的T标号不变,在所有的T标号中,最小的为T(v4),于是将v4的标号改为P标号,此时有S3= S2∪{v4}={v1,v2,v3,v4},λ4=3,P(v4)=5,i=3
(0,0)(1,3)(2,4)(3,5)(1,+∞)(3,6)(2,10)(1,+∞)迭代4(i=4):这时v4为刚获得P标号的点,考察与v4相邻的点v6,v7,因(v4,v6)∈A,v6∈\S3,故把v6的临时标号修改为T(v6)=min{T(v6),P(v4)+w46}=min{6,5+3}=6这时λ6=3。同理,得T(v7)=min{T(v7),P(v4)+w47}=min{+∞,5+5}=10,λ7=4
(0,0)(1,3)(2,4)(3,5)(4,10)(3,6)(2,10)(1,+∞)迭代4(i=4):这时v4为刚获得P标号的点,考察与v4相邻的点v6,v7,因(v4,v6)∈A,v6∈\S3,故把v6的临时标号修改为T(v6)=min{T(v6),P(v4)+w46}=min{6,5+3}=6这时λ6=3。同理,得T(v7)=min{T(v7),P(v4)+w47}=min{+∞,5+5}=10,λ7=4其余点的T标号不变,在所有的T标号中,最小的为T(v6),于是将v6的标号改为P标号,
(0,0)(1,3)(2,4)(3,5)(4,10)(3,6)(2,10)(1,+∞)迭代4(i=4):这时v4为刚获得P标号的点,考察与v4相邻的点v6,v7,因(v4,v6)∈A,v6∈\S3,故把v6的临时标号修改为T(v6)=min{T(v6),P(v4)+w46}=min{6,5+3}=6这时λ6=3。同理,得T(v7)=min{T(v7),P(v4)+w47}=min{+∞,5+5}=10,λ7=4其余点的T标号不变,在所有的T标号中,最小的为T(v6),于是将v6的标号改为P标号,此时有S4= S3∪{v6}={v1,v2,v3,v4,v6},λ6=3,P(v6)=6,i=4
(0,0)(1,3)(2,4)(3,5)(4,10)(3,6)(2,10)(1,+∞)迭代5(i=5):这时v6为刚获得P标号的点,考察与v6相邻的点v5,v7,v8,因(v6,v5)∈A,v5∈\S4,故把v5的临时标号修改为T(v5)=min{T(v5),P(v6)+w65}=min{10,6+2}=8这时λ5=6。
为刚获得
(0,0)(1,3)(2,4)(3,5)(4,10)(3,6)(6,8)(1,+∞)迭代5(i=5):这时v6为刚获得P标号的点,考察与v6相邻的点v5,v7,v8,因(v6,v5)∈A,v5∈\S4,故把v5的临时标号修改为T(v5)=min{T(v5),P(v6)+w65}=min{10,6+2}=8这时λ5=6。同理,得T(v7)=min{T(v7),P(v6)+w67}=min{10,6+1}=7,λ7=6T(v8)=min{T(v8),P(v6)+w68}=min{+∞,6+9}=15,λ8=6
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(6,15)迭代5(i=5):这时v6为刚获得P标号的点,考察与v6相邻的点v5,v7,v8,因(v6,v5)∈A,v5∈\S4,故把v5的临时标号修改为T(v5)=min{T(v5),P(v6)+w65}=min{10,6+2}=8这时λ5=6。同理,得T(v7)=min{T(v7),P(v6)+w67}=min{10,6+1}=7,λ7=6T(v8)=min{T(v8),P(v6)+w68}=min{+∞,6+9}=15,λ8=6其余点的T标号不变,在所有的T标号中,最小的为T(v7),于是将v7的标号改为P标号,
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(6,15)迭代5(i=5):这时v6为刚获得P标号的点,考察与v6相邻的点v5,v7,v8,因(v6,v5)∈A,v5∈\S4,故把v5的临时标号修改为T(v5)=min{T(v5),P(v6)+w65}=min{10,6+2}=8这时λ5=6。同理,得T(v7)=min{T(v7),P(v6)+w67}=min{10,6+1}=7,λ7=6T(v8)=min{T(v8),P(v6)+w68}=min{+∞,6+9}=15,λ8=6其余点的T标号不变,在所有的T标号中,最小的为T(v7),于是将v7的标号改为P标号,此时有S5= S4∪{v7}={v1,v2,v3,v4,v6,v7},λ7=6,P(v7)=7,i=5
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(6,15)迭代6(i=6):这时v7为刚获得P标号的点,考察与v7相邻的点v8,因(v7,v8)∈A,v8∈\S5,故把v8的临时标号修改为T(v8)=min{T(v8),P(v7)+w78}=min{15,7+5}=12这时λ8=7。
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(7,12)迭代6(i=6):这时v7为刚获得P标号的点,考察与v7相邻的点v8,因(v7,v8)∈A,v8∈\S5,故把v8的临时标号修改为T(v8)=min{T(v8),P(v7)+w78}=min{15,7+5}=12这时λ8=7。其余点的T标号不变,在所有的T标号中,最小的为T(v5),于是将v5的标号改为P标号,
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(7,12)迭代6(i=6):这时v7为刚获得P标号的点,考察与v7相邻的点v8,因(v7,v8)∈A,v8∈\S5,故把v8的临时标号修改为T(v8)=min{T(v8),P(v7)+w78}=min{15,7+5}=12这时λ8=7。其余点的T标号不变,在所有的T标号中,最小的为T(v5),于是将v5的标号改为P标号,此时有S6= S5∪{v5}={v1,v2,v3,v4,v6,v7,v5},λ5=6,P(v6)=8,i=6
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(7,12)迭代7(i=7):这时v5为刚获得P标号的点,考察与v5相邻的点v8,因(v5,v8)∈A,v8∈\S6,故把v8的临时标号修改为T(v8)=min{T(v8),P(v5)+w58}=min{12,8+6}=12这时λ8=7。其余点的T标号不变,在所有的T标号中,最小的为T(v8),于是将v8的标号改为P标号,
(0,0)(1,3)(2,4)(3,5)(6,7)(3,6)(6,8)(7,12)迭代7(i=7):这时v5为刚获得P标号的点,考察与v5相邻的点v8,因(v5,v8)∈A,v8∈\S6,故把v8的临时标号修改为这时λ8=7。其余点的T标号不变,在所有的T标号中,最小的为T(v8),于是将v8的标号改为P标号,此时有S7= S6∪{v8}={v1,v2,v3,v4,v6,v7,v5,v8}=V,λ8=7,P(v8)=12,i=7,结束。l(vj)=P(vj),其中vj∈S7。特别地l(v8)=P(v8)=12,P*(v1,v8)=v1→v2→v3→v6→v7→v8
例求如图网络中v1至v7的最短路
例求如图网络中v1至v7的最短路,图中数字为两点间距离。v5v1v3v6v4v2v7255233575711
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
例子:阿马里洛与沃思堡之间行车最短路线
德克萨思州德阿马里洛和沃思堡之间的高速公路网示意图如下,节点之间的每条链上都标有相应的行车时间,节点代表公路的连接处。
1234567981090分钟138
1234567981090分钟13834866153488490132841201324860150126126阿马里洛沃思堡俄克拉荷马城1109得到最短路线为:125910最短时间为384分钟
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
2、网络计划技术的应用准备网络计划一般用在复杂的项目管理中,网络计划必须做好下列准备工作:1)确定计划目标网络计划的目标是多个方面和综合的目标,正是这个特点决定了网络计划的复杂性。一般按照不同的要求可以分成三类:一是时间要求;二是资源要求;三是费用要求。2)项目任务活动的分解将整个项目根据技术上的需要分解为若干个互相独立的可执行的活动,通常把这种互相独立的活动称为工序或作业。3)确定各工序的衔接顺序明确各项工序之间的先后逻辑关系。工序之间存在执行的先后顺序关系,如需先完成A工序才能进行B工序,则称A为B紧前工序,B为A紧后工序,列出工序明细,以便建立整个项目的网络图以表示各项工序之间的相互关系。
网络计划分析法又称统筹法、关键路线法或计划评审法,其基本原理是将组成系统的各项任务的各个阶段和先后顺序,通过网络形式统筹规划。7.3.4运输线路优化
4)确定各个工序时间确定各项工序所需的时间、人力、物力,一般将完成工序所需要的时间称为工时。后面三项准备工作一般以工序明细表或作业明细表的形式给出,这些工作应该在管理活动中完成,本章默认这个作业明细表已经获得,所有分析都在这个前提下进行。某企业进行新产品研发的作业明细表工时(周)紧前工作工作内容工作工时(周)紧前工作工作内容工作3F制定生产计划G4/市场调研A2B,G筹备设备H10/资金筹备B8B,G筹备原材料I3A需求分析C5H安装设备J6A产品设计D2G调集人员K8D产品研制E1I,J,K准备开工投产L2C,E制定成本计划F
网络计划的有关概念1)项目(Project):也叫做工程,它是一项科学科研、建筑工程、生产任务以及较复杂的工作。2)工序和事项:网络图中的箭线表示项目的工序;节点称为事项(事件),代表一个工序开始或结束的时刻。某个工序的完成需要一定的时间与资源,事项不需要时间或所需时间忽略不计。3)网络图:是由工序和事项组成的具有一个发点和收点的有向赋权图,发点表示整个计划的开始,收点表示整个计划的结束。网络图有两种编制方法:一种是箭线法(双代号法),用节点表示事项用箭线表示工序的网络图(Activity-on-Arrow,简记为AOA),它由工序、节点和路线三部分组成;一种是节点法(单代号法),用箭线表示事项用节点表示工序的网络图(Activity-on-Node,简记为AON)。根据需要,网络图可以分为总图、分图和工序流程图。
4)路线:在网络图中,从发点(最初事项)到收点(最终事项)由各项工序衔接组成的一条有向路。在网络计划分析中,最关注的是消耗时间最多的路,也就是完成整个项目所需要的时间,这个时间叫做工期,并将这样的路叫做关键路线,关键路线上的工序称为关键工序。某项目由8道工序组成,工序明细表见右表。分别用箭线法和节点法绘制该项目的网络图。时间(天)紧前工序工序名称代号序号40/基础工程A150A构建安装B230B屋面工程C320B专业工程D425C装修工程E520D地面工程F650B设备安装G720E,F,G试运行H8
解:箭线法网络图如下图所示,图中节点表示事项:A40B50G50H20C30D20E25F20从事项1到事项7有3条路线,最长的路线为1→2→3→4→6→7,其完成时间为165天,是整个项目的完工工期,这条路线也是该网络图的关键路线,工序A、B、C、E、H都是关键工序。节点法网络图如下图所示,图中箭线描述了工序之间的紧前和紧后关系,节点表示工序。A40B50G50H20C30D20F20E25双代号AOA和单代号AON这两种网络图并没有本质的区别,各有其优缺点。AOA在我国应用较多,比较难画,要引入虚工序;现实交流大家用AOA较多,因为AOA的表达方式更为清晰,手工较易分析,获得信息更多。相对而言,AON在国外应用较多,更容易绘制和掌握,项目管理软件Project的网络图绘制原理就是AON,特别在网络图发生一些改变时较易调整。本章主要介绍双代号网络图的绘制和分析方法。
3、网络计划图的绘制方法网络计划图是一种表示一项工程中各道工序的先后、衔接关系以及所需要时间的图解模型。这种模型要求从整体的、系统的观点出发,全面地统筹项目中人、机、物等资源,并考虑各项活动之间相互依存的内在逻辑关系而绘制。网络图的绘制一般都先画草图,再逐步调整。一般有两种方法:顺推法和逆推法。顺推法是指从项目距开工事项开始依次确定各道工序之间的先后顺序,并从开工事项画到完工事项为止;逆推法是指从工程完工事项开始依次确定各道工序之间的先后顺序,并从完工事项画到开工事项为止。双代号网络图又称箭头图,由带箭头的线和点组成,箭线表示工作(或工序,活动),节点表示事项。工作是完成整个任务的各个局部任务,需要一定的时间与资源,事项与工作相比,它不需要时间或所需要时间可以忽略不计。例如某工作A可以表示为:A15
平行工序指在同样两个事项点之间进行的作业,交叉工序指一项作业不必全部完工才开始下一道工序,而是前道工序完成一部分,就可以继续下一个工序。平行和交叉工序在绘制网络图中要引入虚工序进行调整,在绘制网络图中要特别留意。ABCABCEF两件或两件以上的工作交叉进行时,称为交叉工作。如作业A与作业B分别挖沟和埋管子,那么它们的关系可以是挖一段埋一段,不必等沟全挖好后再埋,这就可以用交叉工作来表示,这时可以把这两件工作各分为几段,如A=A1+A2+A3,B=B1+B2+B3,将这些作业拆分,就转变为上面熟悉的网络图表示方法,见下图。A1A2B1A3B2B3
在绘制网络图时还要注意:工序最好画成水平方式;最好能感觉出一条网络图的水平主线,可选择包含工序最多的一条路作为水平主线,然后调整其他工序的位置;给事项编号应在网络草图绘制完后进行,以便于阅读和计算。某项目由10道工序组成,工序明细表见下表,试绘出网络图。紧后工序所需时间工序代号工序紧后工序所需时间工序代号工序J18F6B,C,D,E60A1I30G7J45B2J15H8F10C3J25I9G,H20D4/35J10H40E5
网络计划主要有CPM和PERT两种方法,他们的区别就在于工序完工时间的估计有所不同。网络图绘制完成后,下一步的工作就是计算网络时间参数,网络时间参数的计算的前提是估计出工序完工时间,他们用作业明细表的工时数据来估计。设网络图共有n个事项,记为1,2,…,n,其中1为项目开工事项,n为项目完工事项,并用t(i,j)或tij表示起点、终点事项分别是i、j工序完工时间。5、工序完工时间的估计CPM采用单一时间计算,即各道工序的时间参数仅参考一个数值,估计时以完成工序的最大作业时间为准,通常就是作业明细表中的工时。PERT方法采用三时法计算工序完工时间,即预先估计三个时间,a为最乐观时间,指顺利完成工序的最短时间;b为最悲观时间,指考虑了最坏条件下完成工序的最长时间;m为最可能时间,指正常条件下完成工序的最可能时间,三种时间发生的概率别为1/6、1/6、4/6,则完工时间的期望值和方差为
项目工序明细见下表
项目工序明细见下表。1)计算各工序完工时间的期望值和方差;2)绘制项目的网络图。方差期望值工序的三种时间紧前工序工序bma753/A1698/B14118/C642BD543AE18168C,DF282018B,EG523326B,EH322518B,EI181512F,G,IJ252111F,GK解:1)根据三时计算公式计算工序完工时间期望值和方差:2)绘制项目的网络图
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
:在保证该事项j所有紧后作业都不延误的前提下,该事项所有紧前作业的最迟结束时间。递推公式为::在保证该事项j所有紧前工序都能够完成的前提下,从该事项开始的各项作业最早开始时间。递推公式为:6、网络时间参数的计算网络时间参数主要包含事项时间参数、工序时间参数两大类,其中有最早开始时间、最迟结束时间、时差等时间参数。
事项时间参数事项时间参数有三个:1)最早开始时间tE(j)2)最迟结束时间tL(j)将计算出来的最早开始时间,写在各事项的指定位置,并用“
:工序(i,j)的最早开始时间为tES(i,j),所以其最早结束时间为tEF(i,j)=tES(i,j) +t(i,j):工序(i,j)的起点是事项i,所以其最早开始时间应为事项i的最早时间,即tES(i,j)=tE(i)将计算出来的最迟结束时间,写在各事项的指定位置,并用“△”括起来。3)事项的时差R(i)
工序时间参数工序时间参数包括六个参数:1)工序(i,j)的最早开始时间tES(i,j)2)工序(i,j)的最早结束时间tEF(i,j):工序(i,j)的终点是事项j,所以其最迟结束时间应为事项j的最迟时间,即tLF(i,j)=tL(j)3)工序(i,j)的最迟结束时间tLF(i,j)
:指在不影响总工期,即不影响其紧后作业最迟开始时间的前提下,工序最早开始时间可推迟开始的一段时间,以表示工序安排上可以机动的时间。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j):工序(i,j)的最迟结束时间为tLF(i,j),所以其最早结束时间为tLS(i,j)=tLF(i,j)-t(i,j)4)工序(i,j)的最迟开始时间tLS(i,j)5)工序(i,j)的总时差R(i,j)或Rij:指在不影响紧后作业最早开始时间前提下,从工序最早开始时间算起可推迟开始的时间。r(i,j)=tE(j)-tEF(i,j)6)工序(i,j)的单(自由)时差r(i,j)或rij将在网络图中总时差为零的工序称为关键工序,表明在时间安排上没有机动,由关键工序组成的从起点到终点的路线称为关键路线;最早开始时间与最迟结束时间相等的事项所连成的路线也是关键路线。
5.3网络时间参数的计算【】按照期望作业时间计算例5.7网络图的时间参数,并指出关键路线。KJIHGFEDCBA工序FGFGIBEBEBECDAB///紧前工序2015253521154411105期望解:首先计算网络图的事项时间参数。1)从左向右逐步计算事项最早时间参数tE(j)得整个工程的完成时间,即工期为51。2)从右向左逐步计算事项最迟时间参数tL(j)
5.3网络时间参数的计算根据各事项的时差可以确定出关键路线接着计算网络图的工序时间参数:
5.3网络时间参数的计算K(6
5.3网络时间参数的计算K(6,8)J(7,8)I(5,7)H(5,8)G(5,6)F(3,6)E(2,5)D(4,3)C(1,3)B(1,4)A(1,2)工序2015253521154411105工时tEStEFtLStLFRr关键工序
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
7资源的合理配置工程的可用资源在一般情况下都是有限的,完成工序的正常时间和正常成本都是在固定资源条件下估算出来的,如工序在正常情况下需要15人5台设备20天完成,总成本是5万元。在一定条件和范围内,工序的时间、资源和成本三者之间相互制约和相互转化。先进的施工设备能够节约工序时间,减少施工人员和工资,但同时也增加了设备投资。根据项目实施的实际情况和具体要求,因地制宜、因时制宜,对项目进行资源合理配置,也是网络优化的重要任务之一。资源的合理配置大致有几个方面,一是资源一定,如何组织、安排和调配资源保证项目按期完成;一是资源不足时,如何协调内部资源和采取应急措施保证项目按期完成;一是资源、时间和成本的整体调整和系统优化。这里仅通过一个人力资源安排的实例说明其原理。
【】工程各工序的时间和资源需求见下表。成本斜率压缩最大时间成本(万元)时间(天)每天需要人数紧前工序工序应急正常应急正常20270308105/A1021501306812AB10313010071020BC10150406712AD152805081020BE0060603310CEF4486709137EG1)绘制网络计划图,按正常时间计算项目完工期,按期完工最多需要多少人?2)保证按期完工,如何采取应急措施,使得总成本最小又使得总人数最少,对网络计划进行优化分析。
解:1)绘制网络图,计算网络图的时间参数,见下图,项目完工期为40天,关键工序是A、D、E和G,非关键工序是B、C和F,他们的总时差都是9,也是他们的全部机动时间。项目所需人数的计算方法首先安排关键工序的人员,然后对非关键路线的工序的开始时间进行调整,尽可能避开关键工序的用工高峰,最后各条路线上同一时间施工的最多人数就是项目所需人数。为便于解释问题,对计划的资源配置使用时间坐标网络图更为方便,也叫资源负荷图。时间坐标网络图是网络图和横道图(甘特图)相结合的一种网络图,他兼具了网络图的逻辑性和横道图的直观性,横坐标为项目进度时间,纵坐标为工序,绘制方法见下图。
人人非关键工序最迟结束时间非关键工序
4038363432302826242220181614121086425人A12人B20人C12人D20人E10人F7人G71740人24人5人人非关键工序最迟结束时间非关键工序最早开始时间关键工序的时间
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
从上图可看出,如果非关键工序都按最早时间开始,第1天到第10天是用工低谷期,总共需5人;第11天到第28天是用工高峰期,第19天到第27天为40人,按此计划施工需要40人,显然这个方案很不经济。网络时间参数的计算为管理者提供了调整和优化网络计划的依据,减少施工人员就是利用非关键工序的时间差“削峰填谷”,调整非关键工序的开始时间,如果条件许可,某些非关键工序还可以分段作业、交叉作业,均衡利用资源。将工序B按最早时间开始,工序C、F按最迟时间开始,调整后最多需要32人,见下图。
人人非关键工序最迟结束时间非关键工序
4038363432302826242220181614121086425人A12人BC20人12人D20人EF10人7人G172720人24人5人人非关键工序最迟结束时间非关键工序最早开始时间关键工序的时间
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
2)从上图中可以看出,只有1天需要32人,对计划整体优化可考虑以下几个方案。首先对工序B或E采取应急措施,缩短工序时间1天,能够使总人数降到27人,从表可知,工序B一天的应急成本比工序E低,所以工序B缩短1天,第17天完工,增加成本10万元;第二,如果项目完工期推迟1天的成本比工序B的应急成本低,也可以考虑对关键工序E推迟1天开始,即第19天开始,项目完工期41天;第三,人员并没有得到均衡利用,在某个时间段内就可以利用富裕的资源到关键工序,缩短关键工序时间,而在用工高峰期时将缩短的关键工序时间用到其他工序上;第四,均衡利用资源,综合评价与审核。当资源、时间和成本相互可以替代时,制定转化标准,反复调整和优化网络计划,获得满意的计划方案。网络计划技术不是单纯的编制网络图和计算时间参数,更重要的是对网络计划进行调整和优化,得到项目合理的决策方案。
在现实生活中,有各种性质的指派问题。例如,有若干项工作需要分配给若干人(或部门)来完成;有若干项合同需要选择若干个投标者来承包;有若干班级需要安排在若干教室上课等等。诸如此类的问题,它们的基本要求是在满足特定的指派要求条件下,使指派方案的总体效果最佳。某厂拟派4个维修小组去维修4台机车,他们相应的完成工作所需时间cij(i,j=1,2,3,4)由右表给出。如何给每个小组安排工作才能使完成任务的总时间最少。7.3.5物流资源分配优化指派问题也称分配或配置问题,是资源合理配置或最优匹配问题。指派问题通常划分为标准和非标准的指派问题。1、指派问题的引入4321机车小组41315211514410213161493911874解:该指派问题是安排维修小组去维修机车,其决策变量为
4321机车小组x14x13x12x
4321机车小组x14x13x12x111x24x23x22x212x34x33x32x313x44x43x42x414该问题的数学模型为:任务约束人员约束
本页源文本为表格或公式被展平后的字符,行列结构无法安全还原,已按原文保留,建议对照原课件图片核对数值关系。
2、指派问题的求解指派问题既是一类特殊的整数规划问题,又是特殊的运输问题,因此可以用多种相应的解法来求解,然而这些解法都没有充分利用指派问题的特殊性质,有效地减少计算量,直到1955年库恩(W. W. Kuhn)提出的匈牙利法才有效地解决了指派问题。3、匈牙利法的理论基础独立零元素组在效率矩阵中,有一组在不同行不同列的零元素,称为独立零元素组,其每个元素称为独立零元素。已知效率矩阵求其独立零元素组。
解:可行解{c12=0,c24=0,c31=0,c43=0}是一个独立零元素组,c12=0,c24=0,c31=0,c43=0分别称为独立零元素;{c12=0,c23=0,c31=0,c44=0}也是一个独立零元素组,而{c14=0,c23=0,c31=0,c44=0}就不是独立零元素组.根据上述对效率矩阵中零元素的分析,将效率矩阵中出现的独立零元素组中零元素所处的位置,在决策变量矩阵中令相应的xij=1,其余的xij=0,就可找到指派问题的一个最优解,如例3.14。
问题:在有的问题中效率矩阵中独立零元素的个数不够n个,这样就无法求出最优指派方案,需作进一步的分析,首先给出下述定理。定理3.3设指派问题的效率矩阵为C=[cij]n×n,若将该矩阵的某一行(或某一列)的各个元素都减去同一常数k(k可正可负),得到新的效率矩阵C’=[c’ij]n×n,则以C’为效率矩阵的新的指派问题与原指派问题的最优解相同。推论若将指派问题的效率矩阵每一行或每一列分别减去各行或各列的最小元素,则得到新指派问题与原指派问题有相同的最优解。定理3.4效率矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
匈牙利法求解步骤第一步:变换效率矩阵,将各行各列都减去当前各行、各列中最小元素。第二步:标记新矩阵的独立零元素。1)行检验对变换后的效率矩阵进行逐行检验,若某行只有一个未标记的零元素时,用“*”将该零元素做标记,然后将被标记的零元素所在的列的其它未标记的零元素用“×”将该零元素标记。2)列检验与行检验过程类似,对进行了行检验的矩阵逐列进行检验,对每列只有一个未被标记的零元素,用“*”将该零元素做一标记,然后将该元素所在行的其他未被标记的零元素打“×”将该零元素标记。重复上述列检验,直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。
这时可能出现以下三种情况:①每一行均有标记“*”出现,“*”的个数m恰好等于n;②存在未标记的零元素,但他们所在的行和列中,未标记过的零元素均至少有两个;③不存在未被标记过的零元素,“*”的个数m<n。3)试指派若情况①出现,则可进行试指派:令“*”记号的决策变量取值为1,其他决策变量取值均为零,得到一个最优指派方案,停止计算。若情况②出现,则对每行、每列的其它未被标记的零元素任选一个,加上标记“*”,即给该零元素标记“*”,然后给同行、同列的其它未被标记的零元素加标记“×”,然后再进行行、列检验,可能出现情况①或③,出现情况①就会得到最优指派,停止计算。若情况③出现,则要转入下一步。第三步:作最少直线覆盖当前所有零元素。
1)对新矩阵中所有不含“*”元素的行打√;2)对打√的行中,所有零元素所在的列打√;3)对所有打√列中标记“*”元素所在行打√;4)重复上述2),3)步,直到不能进一步打√为止;5)对未打√的每一行划一直线,对已打√的每一列划一纵线,即得到覆盖当前0元素的最少直线数。第四步:对矩阵未被直线覆盖过的元素中找最小元素,将打√行的各元素减去这个最小元素,将打√列的各元素加上这个最小元素(以避免打√行中出现负元素),这样就增加了零元素的个数,返回第二步。求解例3.12和例3.13
解:故可得到指派问题的最优解X,这样安排能使总的维修时间最少,维修时间为z=4+4+9+11=28(小时)。
故可得到指派问题的最优解X,这样安排能使总的建造费用最少,建造费用为z=7+9+6+6+6=34(万元)。
7.4运输工具配置优化
服务机构越大,顾客越方便。如果服务机构过小,便不能满足顾客需要,并使服务质量降低,影响服务机构的信誉,还可能导致失去顾客或经营亏损。
7.4.2合理选择运输工具
运输工具的评价尺度定为以下四项:经济性(F1);迅速性(F2);安全性(F3);便利性(F4)。
由于货物形状、价格、交货日期、运输批量和收货单位各不相同,这些运输工具的评价尺度标准也必然有差异。假设尺度标准分别是W1、W2、W3、W4,则运输工具的综合评价值(F)可表示为:
现在可供选择的运输工具有:火车(R)、汽车(T)、船(S),其各综合评价值分别用F(R)、F(T)、F(S)表示,则:
(2)经济性(F1)的计量化
(3)迅速性(F2)的计量化
运输工具的迅速性用从发货地到收货地所需时间(或天数)来表示。所需时间越多,则迅速性越低,这是不利因素。设各运输工具所需时间数为H(R)平均值为:运输工具迅速性的相对值是:
(4)安全性(F3)的计量化运输工具的安全性,要根据过去一段时间内货物的破损率(有时为实验数据)等,实行计量化较为合适。破损率越高,安全性越低,这是不利因素。设各运输工具破损率为D(R)、D(T)、D(S),其平均值为:运输工具安全性的相对值是:F3(R)=D(R)/DF3(T)=D(T)/DF3(S)=D(S)/D
(5)便利性(F4)的计量化
设各运输工具的时间差为V(R)V(T)V(S),则平均值为:表示运输工具便利性的相对值为根据以上结果,得出各运输工具综合评价值应该是:所以,我们应该选择F(R)、F(T)、F(S)中最大值的
复习思考
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}