物流运输管理7

第七章物流运输优化与决策第一节物流运输服务选择决策一、物流运输方式选择的原则二、基于物流总成本比较的运输方式选择三、承运人的选择与评价一、物流运输方式选择的原则（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则二、基于物流总成本比较的运输方式选择基于运输成本与库存成本的总成本分析方法：表7-1各种运输方式的基本参数表7-2各种运输方式成本计算结果运输方式费率R(元/件)时间T(天)年运送批次平均存货量Q/2铁路0.12110100000驮背0.15142046500公路0.252042000航空1.424020250成本类型计算公式铁路运输驮背运输公路运输航空运输运输成本RD70000105000140000980000在途库存ICDT/3653624662416448630134521工厂存货ICQ/2900000418500378000182250仓库存货I(C+R)Q/2903000420593380520190755总成本223546611857379848211387526三、承运人的选择与评价（一）影响承运人选择的主要因素1．运输成本2．运输时间和运输时间的可靠性3．可到达性4．服务能力5．安全性（二）承运人的评价方法综合因素加权求和法表7-3承运商评估报告示例承运人：_____时期:_____最高分评价标准承运人分数备注13满足接货时间表1313满足搬运109运输时间910运输时间一致性77费率53附加费1高的住宅搬运5运营比率396.5％增长4收益性33索赔频率33索赔解决310账单错误79跟踪能力711设备可用性l无平台装货卡车100总分72第二节货物运输调配决策一、多起迄点间的直达运输二、存在中间转运的物资调配一、多起迄点间的直达运输（一）产销平衡的运输问题1．产销平衡运输问题数学模型2．求解方法单纯形法、表上作业法a1a2amb1b2bnCijXij供应地需求地minjijijXCZ11min图7-1多点之间的物资运输调拨问题示意图（二）产销不平衡的运输问题1．总产量大于总销量：则增加一个假想的销地Bn+1，其销量为：2．总销量大于总产量：则增加一个假想的产地Am+1，其产量为：njjmiinbab111miinjjmaba111njjmiiba11miinjjab11二、存在中间转运的物资调配（一）问题描述t1t2tmb1b2bnCkijXkij供应地需求地a1af中转站图7-2有中间转运的物资运输调拨问题（二）数学模型目标函数为：约束条件为：（1）配送量生产能力的限制：k=1，2，…，f；（2）流通中心发送能力的限制：i＝1，2，…，m；（3）满足零售店需求量：j=1，2，…，n；（4）变量非负：minjkijkijfkXCZ111minnjkkijmiaX11njikijfkitX1fkjkijmibX110kijX（三）求解方法运输问题表上作业法：[例7-2]表7-4各点间运输单位费用ABEFCDA013461214B130761312E470388F663078C121387017D141288170表7-5需求和供应量确定准则转运问题中点的性质在运输表中的供应值在运输表中的需求值供应点起始供应+总供应总供应转运点总供应总供应需求点总供应起始需求+总供应空点0起始供应－起始需求表7-6最终运输表ABEFCD空列供应A0134612140500B1307613120550E4703880350F6630780350C1213870170350D1412881700350需求35035035035048048090第三节物流运输线路的优化一、起迄点不同的单一路线优化二、起迄点重合的单一路线优化一、起迄点不同的单一路线优化归结为运筹学中的最短路径问题图7-3从起点到终点的运输网络图651214B11C1D11EA1B221C2B31C31D22511261041311398105216动态规划方法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段531368766835342138223335526643437597681310912131618该点到G点的最短距离（一）动态规划法651214B11C1D11EA1B221C2B31C31D225112610413113981052阶段4321图7-4多阶段划分52871220141919（二）Dijkstra方法[例7-3]OABCDET225417443175起点终点OABCDET225417443175起点终点图7-5运输网络图19E.W.Dijkstra算法（标号算法）算法基本思路分析：（逐步向外搜索）52165828997221210∞∞∞∞∞∞∞∞2527511121210575667991010633xy起点到该点的最短距离起点到该点的最短距离的上界（二）Dijkstra方法[例7-3]OABCDET225417443175起点终点OABCDET225417443175起点终点图7-5运输网络图0∞∞∞∞∞∞02542944487714813表7-8Dijkstra算法步骤表步骤P标号点与P点直接相连的T标号点相应的总距离第n个最近点最小总距离最新连接1OA2A2OA2OACB42+2=4CB44OCAB3ABCDEE2+7=94+3=74+4=8E7BE4ABEDDD2+7=94+4=87+1=8DD88BDED5DETT8+5=137+7=14T13DTA起点90B13834866C9084E96D1564875F12050132IH48G150126126J终点二、物流运输的优化模型按货物的自然流向组织货物合理的物流运输是市场经济规律的客观要求，它直接决定着物流的效率与效果。为了制定在产销平衡条件下的运量规划方案，必须建立数学模型，运用数学方法来解决。三、单纯形法对于运输问题，一般采用单纯形法求解，具体方法和步骤已在前面介绍过，这里不再列述。经验表明，当起运站和目的地都多于5个时，用其它方法求解比较困难或繁琐，最好用单纯形法求解。四、图表分析法图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表找出产销之间经济合理的商品运输路线。五、图上作业法1．运输线路不成圈的图上作业法2．运输线路成圈的图上作业法运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，如表9-22所示。表9-22成圈运输线路的图上作业法的步骤步骤详述去段破圈确定初始运输方案就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法，即可得到初始运输方案。检查有无迂回现象因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果圈内和圈外流向的总长度都不超过全圈总长度的1/2，那么，全圈就没有迂回现象了，这个线路流向图就是最优的，对应的就是最优运输方案。否则转向第三步。重新去段破圈，调整流向在超过全圈总长1/2的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。如果全圈存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的1/2，则不存在迂回现象，此方案为最优运输方案。(13)(18)36最小树问题与网络设计树（Tree）和最小树树是图论中一类重要的图，实际中很多系统的结构都是树。树——连通且不含圈的图，简记为T。树的性质：（1）在树中，任意两个顶点间必有且仅有一条链；（2）在树中，在不相邻的顶点中添加一条树枝，则恰好得到一个圈；（3）在树中，任意去掉一条树枝，就变成分离图；（4）设T是棵有n个顶点的树，则T的树枝数为n-1；（5）一棵树至少有两个悬挂点；（6）树是连通且边数最少的图。37最小树问题树（Tree）和最小树树的权——若Tk是加权图G的一棵树，则树T的全部边的权之和称为树Tk的权，记为（Tk）=（e）；eTk最小树——T*是加权图G的一棵最小树，即（T*）=min{(Tk)}最小树问题树（Tree）和最小树破圈法，避圈法求最小支撑树：图G1542453134421512最小支撑树T最小支撑树T1212112123121123案例：几家石油公司准备联合建设一个输油管道来连接西南地区、东南地区和中西部地区的城市，网络图如下图所示，其中各个城市之间的英里数显示在各个分支上。确定用最少距离的管道连接10个城市的管道系统并计算出需要使用多少英里的管道。29108745631丹佛奥马哈得梅因印第安纳波利斯阿尔伯克基俄克拉何马城小石城纳什维尔圣路易斯堪萨斯城400490520450750240310580210120250250235340260270320260340练习：我校拟设立一个网络将主要的校园建筑与计算机中心连接起来提高网络服务。一些电缆需要埋到地下，主要利用现有的电缆通道来架设。如下网络显示了节点1计算机中心与不同建筑物之间连接的各个分支及其距离，试确定网络中可以连接所有建筑物的最小树及需要的总的电缆长度。291087456311214111386984882114523539127564829581028018631138208921056271832769371645743网络流（Flow）与最大流问题最大流问题是一类应用极为广泛的问题，如运输网络中的人流、车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。20世纪50年代Ford–Fulkerson建立的“网络流理论”，是网络应用的重要组成部分。一、基本概念1．容量网络：（1）容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量。记为:C（vi，vj）或Cij，也常记为bij。（2）容量网络：对所有的弧都给出了容量的有向网络，记为D=（V，A，C）或D=（V，A，B）。（1）流：①弧上的流——网络中加在弧上的负载量。记为fij或xij。②图上的流——加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数）。记为f={f（vi，vj）}={fij}2．流与可行流（2）零流：若网络上所有弧上的流均为0，即对所有的i和j，都有fij=0，则称相应的图上的流为零流。(,)(,)()0,()ijjiijAjiAvfisffistvfit（3）可行流：在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的图上的流。即0≤fij≤cij;其中f为网络中从起点s到终点t的流量。问：零流是不是可行流？3．割（割集、截集）：设V为网络中所有顶点的集合，将V剖分为两个子集和，满足:SSStSsVSSSS称弧集为分离起点和终点的的割集。组成割集的各条弧容量之和称为割容量（截量），所有割集中容量最小的割集称为最小割。),(SS4、弧的分类（1）在可行流f={fij}中，按流量的特征分有：①饱和弧——fij=cij②非饱和弧——fijcij③零流弧——fij=0④非零流弧——fij0（2）在容量网络中从起点vs到收点vt的一条链中，按弧的方向分①前向弧——与链的方向一致的弧。前向弧全体记为μ+；②后向弧——与链的方向相反的弧。后向弧全体记