资源描述
Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,运输路线及运输方案的确定,运输路线类型,1,2,3,4,5,小结,运输方案的选择,装载技术,1,知识回顾：,不合理的运输形式：,对流运输、迂回运输、过远运输、重复运输、无效运输、运力选择不当。,配送：,是指在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动,。,配,+,送,（近距离的运输）,2,运输线路类型,运输线路的选择事关效益。,要求：时间短、费用省、效益好。,运输线路类型按装卸特点,点,（装运点）对,点,（卸货点）,直送式,点,对,多,分送式,多,对,多,配送式,3,运输线路类型,运输线路按装载及路线特点分为：,一、往复式行驶线路,是指在货物的运送过程中车辆在,两个物流节点之间往返,运行的线路形式。有,3,种形式：,单程有载往复式行驶线路,回程部分有载往复式行驶线路,双程有载往复式行驶线路,4,运输线路类型,二、环形式行驶线路,环形式行驶线路是指车辆在由,若干个物流结点组成,的,封闭回程路上作连续单向运行,的行驶线路。车辆在环形式行驶线路上行驶时，,一个周转内至少完成两个运次的货物运送工作。,简单环形式、交叉或三角形式和复合环形式,等。,当配送车辆无法组织回程货物时，为了提高车辆的里程利用率，可组织环形式行驶线路。,车辆在环形式行驶线路上运送货物时，,应尽量使其空驶行程之和小于载货行程之和，最大限度地组织车辆有载运行，以其里程利用率达到最高为最佳准则。,5,简单环形式 交叉环形 复合环形式,6,配送线路类型,三、汇集式行驶线路,汇集式行驶线路是,指车辆沿分布于运行路线上各物流结点依次完成相应的装卸作业,，且,每次的货物装（卸）量均小于该车核定载货量，直到整个车辆装满（卸空）后返回出发点的行驶线路。,主要有三种形式：,分送式。,车辆沿运行线路上各物流结点依次卸货，直到卸完所有待卸货物返回出发点。,收集式,（。车辆沿运行线路上各物流结点依次装货，直到装完所有待装货物返回出发点。,分送,收集式。,车辆沿运行线路上各物流结点分别或同时装、卸货物，直到完成对所有待运货物的装卸作业返回出发点。,7,运输线路类型,小结：,选择合适的配送线路有利于提高配送运输的效率，降低成本。,8,车辆集装技术,一、配送车辆的装货问题,一般用运筹学中的动态规划知识解决。,原理：,设车辆的额定载货量为,G,，可用于配送种不同的货物，货物的质量分别为,W,，,W,，,W,。每一种货物分别对应于一个价值系数，用,P,，,P,，,P,表示，它表示货物价值、运费等。设,X,表示第,K,种货物的装入数量，则装货问题可表示为：,F,（,X,）,P,k,X,k,W,X,G,X,（，,，）,9,车辆集装技术,用运筹学中动态规划思想求解步骤：即把每装入一件货物作为一个阶段，把装货问题转化为动态规划问题。,动态规划问题求解过程是从最后一个阶段开始由后向前推进，由于装入货物的先后次序不影响最优解，所以我们的求解过程可从第一阶段开始，由前向后逐步进行。,具体步骤如下：,第一步：装入第种货物,X,件，其最大价值为：,F,（,W,）,P,X,其中，,X,G/W,，方括号表示取整数。,10,车辆集装技术,第二步：装入第种货物,X,件，其最大价值为：,F,（,W,）,P,X,F,（,W,W,X,）,其中，,X,G/W,.,第步：装入第种货物,X,件，其最大价值为：,F,(W),P,X,F,(W,W,X,),其中，,X,G/X,11,车辆集装技术,下面举例说明求解过程：例：载货量为的载货汽车，如表所示，运输种机电产品，其质量分别为，试问如何配装才能充分利用货车的运载能力？,12,车辆集装技术,二、配装理货注意事项,（）为了减少或避免差错，尽量把外观相近、容易混淆的货物分开装载；,（）重不压轻，大不压小，轻货应放在重货上面，包装强度差的应放在包装强度好的上面；,（）不将散发臭味的货物与具有吸臭性的食品混装；,（）尽量不将散发粉尘的货物与清洁货物混装；,（）切勿将渗水货物与易受潮货物一同存放；,（）包装不同的货物应分开装载，如板条箱货物不要与纸箱、袋装货物堆放在一起；,13,车辆集装技术,（）具有尖角或其他突出物的货物应和其他货物分开装载或用木板隔离，以免损伤其他货物；,（）装载易滚动的卷状、桶状货物，要垂直摆放；,（）货与货之间，货与车辆之间应留有空隙并适当衬垫，防止货损；（）装货完毕，应在门端处采取适当的稳固措施，以防开门卸货时，货物倾倒造成货损或人身伤亡；（）尽量做到“后送先装”。,14,车辆集装技术,（）装货完毕，应在门端处采取适当的稳固措施，以防开门卸货时，货物倾倒造成货损或人身伤亡；,（）尽量做到“后送先装”。,15,运输方案的选择,共三种类型,直送式运输,-,指由一个供应点对一个客户的专门送货,。,分送式运输,-,一对多,配送式运输,-,多对多,16,运输方案的选择,-,直送式运输,直送式运输,-,指由一个供应点对一个客户的专门送货。,直送式运输的基本条件,-,其需求量接近于或大于可用车辆的额定载质量，需专门派一辆或多辆车一次或多次送货。,直送运输的物流优化问题,最短线路问题,。,17,运输方案的选择,-,直送式运输,位势法,解决物流网络中的最短线路问题。,已知物流网络如图，各结点分别表示为,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,、,I,、,J,、,K,，各结点之间的距离如图所示，试确定各结点间的最短线路。寻找最短线路的方法、步骤如下：,第一步：,选择货物供应点为,初始结点,，并取其位势值为“零”即,V,第二步：,考虑与点直接相连的所有线路结点。设其初始结点的位势值为,V,，则其终止结点的位势值可按下式确定：,V,V,L,式中,：,L,-,点与点之间的距离。,18,运输方案的选择,第三步：从,所得到的所有位势值中选出最小者,，,此值即为,从初始结点到该点的最短距离,，,将其标在该结点旁的方框内，,并用箭头标出该联线,，,以此表示从点到点的最短线路走法。,19,运输方案的选择,第四步：重复以上步骤，直到物流网络中所有的结点的位势值均达到最小为止。,最终，各结点的位势值表示从初始结点到该点的最短距离。带箭头的各条联线则组成了从初始结点到其余结点的最短线路。分别以各点为初始结点，重复上述步骤，即可得各结点之间的最短距离。,20,运输方案的选择,K,C,11,10,13,5,6,8,10,12,10,7,9,8,11,4,14,8,A,B,D,G,F,I,J,H,E,2,6,21,运输方案的选择,-,位势法举例,例：在物流网络图中，试寻找从供应点,A,到客户,K,的最短线路。解：根据以上步骤，计算如下：,（）取,V,；,（）确定与,A,点直接相连的所有结点的位势值：,V,V,L,V,V,L,V,V,L,V,V,L,22,运输方案的选择,（）从所得的所有位势值中选择最小值,V,，并标注在对应结点,E,旁边的方框内，并用箭头标出联线,AE,。即：,min,V,V,V,V,min,V,（）以,E,为初始结点，计算与之直接相连的,D,，,G,，,F,表的位势值（,如果同一结点有多个位势值，则只保留最小者）。,V,V,L,V,V,L,V,V,L,23,运输方案的选择,-,直送式运输,（）从所得的,所有剩余位势值,中,选出最小者,，并标注在对应的结点,F,旁，同时用箭头标出联线,AB,，,即：,V,，,V,，,V,，,V,，,V,，,V,。,（）,以,B,点为初始结点，,与之直接相连的结点有,D,、,C,，它们的位势值分别为和。,从所得的所有剩余位势值中取最小，,即：,，,V,。将最小位势值标注在与之相应的,D,旁边的方框内。,如此继续计算，可得最优路线如图所示，由供应点,A,到客户,K,的最短距离为。,24,运输方案的选择,-,直送式运输,K,C,11,10,13,5,6,8,10,12,10,7,9,8,11,4,14,8,A,B,D,G,F,I,J,H,E,2,6,13,8,0,5,15,7,17,24,9,20,图从,A,出发的最优线路图,6,25,运输方案的选择,-,分送式运输,分送式配送,是指由,一个供应点对多个客户,的,共同送货。,前提条件：所有客户的,需求量总和不大于一辆车的额定载重量,。,常用解决法：,里程节约法,26,运输方案的选择,-,分送运输,-,节约法,（二）节约法的基本思想,如图所示，设,P,为配送中心，分别向用户,P,和,P,送货。,P,到,P,和,P,的距离分别为,d,和,d,，两个用户,P,、,P,之间的距离为,d,，,送货方案只有两种，即配送中心,P,向用户,P,、,P,分别送货,和配送中心,P,向用户,P,、,P,同时送货,，如图：,P,i,P,j,P,o,P,i,P,j,P,o,方案,方案,b,27,比较两种配送方案：,方案）配送距离为：,d,d,d,；,方案）的配送线路为：,d,d,d,d,i,同时送货比分别送货节约的距离为：,S,d,d,d,总之，,在汽车载货能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多，里程节约量越大,，配送线路越合理。,28,运输方案的选择,-,分送运输,-,节约法,例：设配送中心,P,向,10,个客户,P,(,，,10),配送货物。其配送网络图见图,14,。配送中心有，,2,两种车辆可供调配。试制订最优的配送方案。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,4,5,7,8,3,7,4,5,3,10,9,5,2,4,4,11,8,9,5,7,6,2,6,4,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,29,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,4,5,7,8,3,7,4,5,3,10,9,5,2,4,4,11,8,9,5,7,6,2,6,4,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,30,运输方案的选择,-,分送运输,-,节约法,解：,1,）计算最短距离：,P,36=minp03+p06,p53+p56,=min15,16,=15,31,运输方案的选择,-,分送运输,-,节约法,解：,2,）计算节约里程：,S,35,=P,03,+P,05,-P,35,=7+8-9=,6,32,运输方案的选择,-,分送运输,-,节约法,3,）将节约,Sij,进行分类，按从大到小的顺序进行分类：,序号,路线,节约里程,序号,路线,节约里程,1,P1P2,15,13,P6P7,5,2,P1P10,13,13,P7P8,5,3,P3P2,11,13,P8P9,5,4,P3P4,10,16,P1P4,4,4,P4P5,10,16,P9P2,4,6,P1P9,9,16,P6P8,4,6,P5P6,9,19,P5P2,3,6,P9P10,9,19,P4P6,3,9,P1P3,8,21,P7P9,2,9,P10P2,8,22,P3P10,1,11,P4P2,7,22,P5P7,1,12,P3P,5,6,22,P6P9,1,33,4,）确定配送路线。从分类表中，按节约里程的大小顺序，组成线路图。,（,1,）按节约里程的大小，连接,P1P12,、,P10,、,P2P3,得线路,A,。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,7,8,3,7,4,5,3,5,2,4,4,线路,A,送货量,3.6T,9,5,7,8,6,4,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,34,4,）（,2,）修正方案,1,，在剩下的,Sij,中，最大的是,S34,和,S45,，全部放入线路,A,中，则超过，考虑均衡问题，不放入,A,中，连接,P4P5,得线路,B,。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,7,8,8,7,4,3,5,2,4,4,线路,A,送货量,3.6T,9,5,7,8,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,线路,B,送货量,1.8T,35,4,）（,3,）修正方案,2,，在剩下的,Sij,中，最大的是,S19,和,S56,，此时,P1,已经属于线路,A,，如果将,P9,放入,A,中，则超载。故将,P6,并入,B,中，得修正方案,3,。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,7,8,8,7,4,3,5,2,4,4,线路,A,送货量,3.6T,9,5,7,8,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,线路,B,送货量,3.3T,36,4,）（,4,）修正方案,3,，在剩下的,Sij,中，继续修正，可将,P7,并入线路,B,。得修正方案,4,。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,7,7,4,3,5,2,4,4,线路,A,送货量,3.6T,9,5,7,8,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,线路,B,送货量,3.9T,37,4,）（,5,）最终方案，在剩下的,Sij,中，,P8P9,无法并入,AB,中,剩下的连接,P8P9,，组成新线路,C,。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,6,7,7,4,3,5,4,4,线路,A,送货量,3.6T,9,5,7,8,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,线路,B,送货量,3.9T,线路,C,送货量,1.3T,38,最终方案：用,3,辆车,配送线路,A,：,P0-P3-P2-P1-P10-P0,使用一辆,4T,车。,配送线路,B,：,P0-P4-P5-P6-P7-P0,使用一辆,4T,车。,配送线路,C,：,P0-P8-P9-P0,使用一辆,2T,车。,配送距离：,80km,配送车辆：,2t,车,1,辆,+4t,车,2,辆。,39,思考：,在前一种做法中，如果将,P4,加入到线路,A,中，所得配送方案如何呢？,40,如果将,P4,加入到线路,A,中，所得配送方案见下图：,配送距离：,80km,，用,4T,车,2,辆，,2,吨车,1,辆。,P,0,P,2,P,3,P,1,P,10,P,5,P,4,P,6,P,7,P,8,P,9,7,8,7,4,3,5,2,4,4,线路,A,送货量,3.6T,9,5,5,8,6,10,（,1.4,）,（,0.6,）,（,1.5,）,（,0.8,）,（,0.4,）,（,1.5,）,（,0.6,）,（,0.8,）,（,0.7,）,（,0.5,）,图：,2-14,配送网络图,线路,B,送货量,3.5T,线路,C,送货量,1.3T,41,运输方案的选择,-,配送式运输,-,表上作业法,配送式运输：,是指由多个供应点向多个客户的送货运输。,又称为供销平衡问题,常用解决方法：,图上作业法,表上作业法,42,（一）图上作业法,原则：,1,、不成圈的图，就近供应，先支线后干线，无对流。,2,、有圈破圈，无对流，使圈内外流向总路程小于或等于该圈总流程的一半。,43,分三种情形：,1,、非圈线状图,先端点由外向内，逐步使各收发点之间产销平衡，且无对流。,2,、环状图：破圈转化为,1,的情形。且满足（使圈内外流向总路程小于或等于该圈总流程的一半。 ）,内圈：顺时针的流量组成,外圈：逆时针的流量组成,3,、有圈有线：去线成环转化为,2,的情形，求解。,44,1,、不成圈（树状、线状）,原则：,就近供应，先支线后干线。,无对流则为最优方案。,45,例,9-4,，某种商品有,3,个产地,A1A2A3,调运到,4,个收货地,B1-B4,。发货量分别为,4,、,10,、,8,吨，收货量分别为,8,、,5,、,3,、,6,吨。已知各点的距离及交通图，如何调运是总的吨公里数最小。,8,8,3,5,4,10,6,20,4,8,10,5,15,A1,A2,A3,B3,B1,B2,B4,A1,B3,B4,A1,B3,A2,B4,A1,B3,B2,A2,B4,A1,B3,A3,B2,A2,B4,A1,B3,B1,A3,B2,A2,B4,A1,B3,46,解：,1,、列出产销平衡表：,2,、调运：先端点，由外向内，调运,3,、检查有无对流。无则是最优方案。,总吨公里,=4x10+4X8+5X5+1X32+3X15+5X4=194,47,调运情况图：,8,8,3,5,4,10,6,20,4,8,10,5,15,（,4,）,（,5,）,（,3,）,（,1,）,（,5,）,（,6,）,B1,A3,B2,A2,B4,A1,B3,48,2,、调运路线成圈图,成圈的最优调运图必须同时满足：,1,、无对流，,2,、任意回路中，顺时针流向的弧长的总长不超过该回路总长的一半；,3,、任意回路中，逆时针流向的弧长的总长不超过该回路总长的一半；,步骤：,1,、作出调运平衡表,2,、破圈变成树状图，任意安排无对流的初始可行的调运方案。,3,、检验是否满足条件,2,和,3,，是则是最优方案。否则调整，转,4,。,4,、调整已有的调运方案。找出不合要求的内圈或外圈流向弧中流量最小的弧去掉；然后依次调整各点的流量，使供需平衡，得到一个新的可行方案，转,3,。重复直至最优。,5,、填写最优平衡表。,49,2,、调运路线成圈图,例：某商品的发点和收点,4,个，成环状。见下图，如何规划出调运方案，使吨公里数最小。,A2,20,5,20,35,5,20,25,30,280,165,180,118,118,317,349,252,165,A4,A1,A3,B1,B3,B2,B4,50,解：,1,、列出产供销平衡表,2,、破圈（通常去掉最长边）变成树状图，作出一个没有对流的调运图,初始调运方案,20,5,20,35,5,20,25,30,280,165,180,118,118,317,349,252,165,（,5,）,（,15,）,（,20,）,（,5,）,（,20,）,（,10,）,（,5,）,B4,B1,B2,B3,A4,A3,A1,A2,51,3,、检验是否最优。,上圈中：周长的一半,=371.5,；,L,上内,=180,；,L,上外,=283,；均小于周长的一半。,下圈中：周长的一半,=690.5,；,L,下内,=283,；,L,下外,=749,；其中,L,下外,周长的一半。不是最优方案。,20,5,20,35,5,20,25,30,280,165,180,118,118,317,349,252,165,（,5,）,（,15,）,（,15,）,（,5,）,（,20,）,（,10,）,（,5,）,B4,B1,B2,B3,A4,A3,A1,A2,52,4,、调整方案,在有迂回的下圈中，超过全周一半的流向中，找出运量最小的边（,A3B1,）丢弃，并补回原来丢弃的边。得到新的树形图。再得出新的规划方案。,20,5,20,35,5,20,25,30,280,165,180,118,118,317,349,252,165,（,5,）,（,20,）,（,15,）,（,5,）,（,15,）,（,15,）,（,5,）,B4,B1,B2,B3,A4,A3,A1,A2,53,5,、对新方案进行检查：,上圈中：周长的一半,=371.5,；,L,上内,=0,；,L,上外,=283,；均小于周长的一半。,上圈中：周长的一半,=690.5,；,L,下内,=632,；,L,下外,=569,；小于周长的一半。,该方案是最优方案,。,20,5,20,35,5,20,25,30,280,165,180,118,118,317,349,252,165,（,5,）,（,20,）,（,15,）,（,5,）,（,15,）,（,15,）,（,5,）,B4,B1,B2,B3,A4,A3,A1,A2,54,6,、总吨公里,=15530,55,3,、调运路线有圈有线,方法：首先使直线上的收发量汇集在与环形的 交叉点上，简化成有圈图。然后用,2,的方法解。,56,（二）表上作业法,表上作业法的步骤：,第一步、依据实际情况列出调运货物的供需平衡表（即产销平衡表）和运价表,。,第二步、根据平衡表和运价表确定,1,个初始调运方案。,方法主要有：,1,、行列差额最大法、,2,、最小元素法,(),3,、左上角法、,4,、,Voge,（伏格尔法）,第三步：判定方案是否最优,;,如否，则调整方案、判定方案直至最优。,判定方法有,：,1,、闭回路法；,2,、位势法,57,第一步：确定初始基可行解,最小元素法、（,Vogel,）伏格尔法,最小元素法思路：,从单价中最小运价确定供应量，逐步次小，直至得到,m+n-1,个数字格。,58,最小元素法举例,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,59,最小元素法举例,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,最小元素法缺点,：会出现顾此失彼,（运费差额问题）,考虑运价差,60,罚数（即差额）,=,次小运价,-,最小运价,罚数（或差额）的解释：,差额大，则不按最小运费调运，运费增加大。,差额小，则不按最小运费调运，运费增加不大。,对差额最大处，采用最小运费调运。,Vogel,伏格尔法思路：,61,结合例,1,说明这种方法。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,行罚数,0,4-4=0,第一次,62,结合例,1,说明这种方法。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,行罚数,0,1,3-2=1,第一次,63,结合例,1,说明这种方法。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,行罚数,0,1,1,第一次,64,结合例,1,说明这种方法。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,行罚数,0,1,1,列,罚,数,4-2=2,2,1,5,3,第一次,65,结合例,1,说明这种方法。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,行罚数,0,1,1,列,罚,数,2,1,5,3,14,8,0,优先安排销地,，否则运价会更高,下次不考虑该列,第一次,66,第二次,结合例,1,说明这种方法。,行罚数,0,1,2,列,罚,数,2,1,3,优先安排销地,，否则运价会更高,8,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,14,8,0,0,6,下次不考虑该行,67,结合例,1,说明这种方法。,行罚数,0,1,列,罚,数,2,1,2,8,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,14,8,0,0,6,下次不考虑该列,8,0,2,第三次,68,结合例,1,说明这种方法。,行罚数,7,6,列,罚,数,1,2,8,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,14,8,0,0,6,8,0,2,4,12,0,下次不考虑该列,第四次,69,结合例,1,说明这种方法。,行罚数,0,0,列,罚,数,2,4,2,8,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,14,8,0,0,6,8,0,2,4,12,0,0,0,0,第五次,70,例,1,用伏格尔法得到的初始基可行解,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,4,8,14,8,12,2,目标函数值,用最小元素法,求出的目标函数,z=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,71,第三步：解的最优性检验,闭回路法,思路：计算空格（非基变量）的检验数,若令,则,如何求检验数？,分析：,运费的增量,即 增加,1,个单位,的检验数,=,相应的运费增量,72,闭回路法：,闭回路：,从已有的调运方案表的,每个空格,出发，存在,唯一一条,，,以该空格为起点,的，,以填有调运数量的方格,为,其它顶点,的闭合回路，称为该空格的闭回路。,注意,：它的每一个顶点都是行与列的转角点；每一条边都是水平或垂直的；每一行若有闭合回路的定点，则恰有,2,个。,检验数：,在某空格所对应的闭回路上，,从空格开始,，把,各顶点的运价依次设为“,+”,“-”,符号,，该闭回路上,所有运价,的,代数和,。就是它的检验数。记为,73,判定方法：,如果所有空格的检验数都是大于等于零的数，则该方案就是最优的。若有负的检验数，则不是最优的方案，表示在该空格的闭回路上调整运输量还可以使运费变小。,调整方法：,在负检验数的闭回路上进行。从该空格出发 ，沿闭回路，在各个奇数次转角点的各调运量中，挑选最小的量为调整量,a,；然后把奇数次转角点的量减去,a,，各偶次转角点则减去,a,，得到一个新方案。,对新的方案继续进行判定，调整直至最优为止。,注意：,当负检验数有两个以上时，选择,绝对值最大的负检验数所在的闭回路,作为具体的调整对象,。,74,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,75,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,2,1,76,检验数表,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,2,1,1,-1,10,12,表中的解不是最优解。,77,第四步：解的调整,调整位置（,2,，,4,）非空，回路角上的格至少为空，且保证数字的非负性。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,-1,（,-2,）,（,-2,）,（,+2,）,（,+2,）,78,调整后的解为：,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,12,14,4,8,2,2,0,9,1,12,此时的解为最优解。,有无穷多最优解,79,几点说明：,选择,绝对值最大的负检验数所在的闭回路,作为具体的,调整对象,；,在最优解的表中，,若有检验数,=0,，则该运输问题有无穷多最优解,；,迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化,。,为,保证,m+n-1,个非空格，需在上述的行或列中填入数字,0,。,80,81,多个配送供应点向多个客户的配送,常用方法：运费差额法得到较优化解。,1,、运费差额法（,vogel,）,原理,：先计算出,每一行和列的最低费用与次低费用的差额，然后从,差额最大的,行（或列）中挑,费用最低的项,，先满足其调运量，,依此类推，直至完成分配。,82,例：某配送中心要将济南、郑州、兰州三个工厂的钢材运到北京、上海、西安、杭州，其供应量和需求量（万吨）及运费（万元）如下表：,产量、需求量及运费表,83,说明：左边是运费表，右边是分配数量表。,从,左表中,算出行差额和列差额（用每一行或列的运费,次低值,减去,最低值,），从差额最大的行或列中找出对应的行或列的,最小值,；,在右边表,中,最先分配,。,84,解决步骤,：,1,、步骤一,：画出上表样式，左边是运费表，右边是分配数量表。,从左表中算出行差额和列差额（用每一行或列的运费次低值减去最低值），从差额最大的行或列中找出对应的行或列的最小值，在右边最先分配。,步骤一中，为,3,，,表示从郑州运,3,万吨至北京,。,2,、步骤二：,将步骤一中选中的列划去，重新按以上方法，找出表中行差最大的,7,，对应定位于表中运费最小的,2,，在右表中分配,7,（,10-3=7,），,表示从郑州向杭州运送,7,万吨。,85,86,3,、依次重复前面的做法，直至步骤五，算法结束。,87,练习：,车辆调度设计,现有一配送中心为八个零售商供货，各个零售商的需求量是,G,i,（吨），这些零售商由配送中心（标号是,0,）发出的,8,吨的载货车辆供应，具体数据如表,8-5,与,8-6,所示，把各点之间的距离作为成本考虑的主要因素，即,C,ij,=D,ij,(i,j=0,1,，,8),，求最优的配送路线。,表,8-6,配送中心与零售商之间的距离,88,89,解：,首先计算节约值：,S(i,j)= C,0i,+C,i0,+C,0,j,+C,j0,(C,0i,+C,ij,+C,j0,)=C,i0,+C,0j,C,ij,S(2,8)=C,20,+C,08,C,28,=60+80,75=65,；,S,（,1,3,）,=C,10,+C,03,C,13,=40+75,40=75,；,按照从大到小的顺序得表,8-6,，,然后计算,S(i,j),中，判断是否连接,i,和,j,。,最后根据表,8-68-8,，得到最优配送路线：,0-6-5-7-0,；,0-3-1-0,；,0-2-8-4-0,。,90,小结：三种配送线路优化问题,直送式（一对一）,最短路径,分送式（一对多）,节约法,配送式（多对多）,图上作业法（有三种情形）,表上作业法,91,92,
展开阅读全文