第四运输路线优化课件

第四章第四章运输路线优化运输路线优化4.1 运输路线和时间安排的原则运输路线和时间安排的原则u运输路线的选择影响到运输设备和人员的利用，正确地运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：间的几个原则如下：1.1.将将相互接近的停留点的货物装在一辆车上运送，以便停相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；留点之间的运行距离最小化；u车辆的运输路线应将邻近的停留点串起来，以使停留点之间的车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。运输距离最小化，这样也就使总的路线上的运输时间最短。4.1 运输路线和时间安排的原则运输路线和时间安排的原则4.1 运输路线和时间安排的原则运输路线和时间安排的原则2.将集聚在一起的停留点安排同一天送货，要避免不是同将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；一天送货的停留点在运行路线上重叠；4.1 运输路线和时间安排的原则运输路线和时间安排的原则3.运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始。u运行路线从离仓库最远的停留点开始，送货车辆依次装载临近运行路线从离仓库最远的停留点开始，送货车辆依次装载临近这个关键停留点的一些停留点的货物，这辆货车满载后，再安这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。排另一辆货车装载另一个最远的停留点的货物。4.一辆货车顺次途径各停留点的路线尽量不交叉，要成泪一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴状。滴状。4.1 运输路线和时间安排的原则运输路线和时间安排的原则5.在多种规格车型的车队中，应优先使用载重量最大的货在多种规格车型的车队中，应优先使用载重量最大的货车。车。u在运输货物时，最好是使用一辆载重量大到能将路线上所在运输货物时，最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。务区停留点的总的运行距离或时间最小化。6.提货应混在送货过程中进行，而不要在运行路线结束后提货应混在送货过程中进行，而不要在运行路线结束后再进行。再进行。u提货应尽可能在送货过程中进行，以减少交叉路程量，而提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。在送货结束后再进行提货经常会发生路程交叉。4.1 运输路线和时间安排的原则运输路线和时间安排的原则7.对偏离集聚停留点路线远的单独的停留点可专门安排车对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货辆送货。u偏离集聚停留点少，特别是那些送货量小的停留点一般要偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。这些停留点送货是合理的。8.应当避免停留点工作时间太短的约束。应当避免停留点工作时间太短的约束。u停留点工作时间太短会迫使途经停留点的顺序偏离理想状停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。态。4.2 运输路线决策运输路线决策l尽管路线选择问题种类繁多，但可以归为尽管路线选择问题种类繁多，但可以归为三种基本类型：三种基本类型：起迄点不同的单一问题、起迄点不同的单一问题、多起迄点问题、起迄点重合的问题多起迄点问题、起迄点重合的问题。1、起迄点不同的单一问题、起迄点不同的单一问题最短路线法：逐点求最短路线最短路线法：逐点求最短路线【例例3】如图所示是一张公路运输网示意图，其中如图所示是一张公路运输网示意图，其中A是起点，是起点，J是终点，是终点，B、C、D、E、G、H、I是网是网络中的结点，结点与结点之间以线路连接，线路络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点示。要求确定一条从起点A到终点到终点J的最短的运输的最短的运输路线。路线。A起点起点BEIJ终点终点HFCDG8490841383481564813215090601321264812666120【练习练习】如图所示是一张公路运输网示意图，其中如图所示是一张公路运输网示意图，其中A是起点，是起点，I是终点，是终点，B、C、D、E、G、H是网络是网络中的结点，结点与结点之间以线路连接，线路上中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点要求确定一条从起点A到终点到终点I的最短的运输路线。的最短的运输路线。A起点起点BCDEFGHI终点终点20406060306050505050204530801002、起迄点重合的问题、起迄点重合的问题l物流管理人员经常遇到的一个路线选择问物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择，又常称题是始发点就是终点的路线选择，又常称为为“旅行推销员旅行推销员”问题。这类问题通常在问题。这类问题通常在运输工具是同一部门所有的情况下发生。运输工具是同一部门所有的情况下发生。对起迄点重合问题，有一种简单有效的方法对起迄点重合问题，有一种简单有效的方法扫描法扫描法 是是是是开始开始将所有的停留点位置画在地图上将所有的停留点位置画在地图上选择适当的车辆装载这个停留点的货物选择适当的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可通过仓库位置放置一直尺，直尺指向任何方向均可是是否否超超过过车车辆辆容容积积或或体体积积的限度的限度是否扫描完所有是否扫描完所有停留点停留点安排下一辆车装载货物，得到一条运行线路安排下一辆车装载货物，得到一条运行线路结束结束继继续续转转动动直直尺尺，扫扫描描到到下下一一个个停停留留点点，分分配配该该车车辆辆装载货物装载货物优优化化每每条条运运行行路路线线的的停停留留点点顺顺序序，以以求求运运行行距距离离最最小小化化否否否否扫描法扫描法l【例例】某公司从其所属的仓库用送货车辆到各客户点提货，某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载货车每次可运载1万件，完成一次运行路线一般需要一天万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。的顺序。扫描法扫描法4000400010001000300030002000200010001000200020002000200020002000200020003000300020002000300030003、多起迄点问题、多起迄点问题l如果有多个货源地可以服务于多个目的地如果有多个货源地可以服务于多个目的地时，那么我们面临的问题是，要指定为各时，那么我们面临的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。该问题常发生在目的地之间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户多个供应商、工厂或仓库服务于多个客户的情况下。的情况下。图上作业法图上作业法l图上作业法根据交通图的点和线的关系，把各种图上作业法根据交通图的点和线的关系，把各种路线归纳为道路不成圈（无圈）和道路成圈两类。路线归纳为道路不成圈（无圈）和道路成圈两类。l道路不成圈，就是没有回路的道路不成圈，就是没有回路的“树树”形路线，包形路线，包括直线、丁字线、交叉线、分支线等；括直线、丁字线、交叉线、分支线等；无圈的流无圈的流向图只要消灭对流，就近送货，就是最优流向图向图只要消灭对流，就近送货，就是最优流向图。l道路成圈，就是形成闭合回路的道路成圈，就是形成闭合回路的“环环”状路线，状路线，包括一个圈和多个圈；包括一个圈和多个圈；成圈的流向图要达到既没成圈的流向图要达到既没有对流，又没有迂回的要求才是最优流向图有对流，又没有迂回的要求才是最优流向图。道路不成圈道路不成圈l任何一张交通网络图，其线路分布形状可任何一张交通网络图，其线路分布形状可分成圈和不成圈两类，对于不成圈的交通分成圈和不成圈两类，对于不成圈的交通网络图，根据线性规划原理，物资调拨或网络图，根据线性规划原理，物资调拨或空车调运线路的确定可依据空车调运线路的确定可依据“就近调空就近调空”原则进行。原则进行。【例例4】有一种商品从有一种商品从A地运出地运出40吨，从吨，从B地运出地运出70吨，从吨，从C地运出地运出30吨，从吨，从D地运出地运出60吨，供给吨，供给a、b、c三地的数量分别为三地的数量分别为70吨、吨、80吨、吨、50吨，应用图上吨，应用图上作业法选择该商品的合理运输路线。作业法选择该商品的合理运输路线。ABCD调入量调入量a70b80c50调出量调出量40703060200运出运出 地地运入地运入地40707080506030BDCabcA403030206020ABCD调入量调入量a403070b206080c203050调出量调出量40703060200【例例5】设产地甲、乙、丙、丁产量分别为设产地甲、乙、丙、丁产量分别为70吨、吨、40吨、吨、90吨、吨、50吨；销地吨；销地A、B、C、D、E需求分别为需求分别为30吨、吨、70吨、吨、50吨、吨、60吨、吨、40吨，试求合理的运输方案。吨，试求合理的运输方案。ABCDE产量产量甲甲70乙乙40丙丙90丁丁50销量销量3070506040250销地销地产地产地703040507050乙乙丁丁甲甲CBA6090丙丙ED4050304050404070乙乙甲甲B10D403010ABCDE产量产量甲甲304070乙乙301040丙丙504090丁丁5050销量销量3070506040250道路成圈道路成圈l对于成圈的交通网络，只要先假设某两点间线对于成圈的交通网络，只要先假设某两点间线路路“不通不通”，将成圈问题化为不成圈问题考虑，将成圈问题化为不成圈问题考虑，这样就可得到一个初始的调运方案。这样就可得到一个初始的调运方案。l然后进一步作优化处理，其原则是：然后进一步作优化处理，其原则是：里圈、外里圈、外圈分别算，要求不过半圈长；如若超过半圈长，圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。应甩运量最小段；反复求算最优方案。【例例6】有某商品发送点有某商品发送点A、B、C、D四处，与四个接四处，与四个接收点收点a、b、c、d成圈状，其距离及供需量如表所示，成圈状，其距离及供需量如表所示，试求最优运输路线。试求最优运输路线。距离距离abcd产量产量A658080B180220150C9075170D6070100销量销量130100160110500接收地接收地发送地发送地150100CAD17016010011080130Babcd15020100109070100l根据图中箭头将内外圈货流里程汇总，检查是否超根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。过全圈长的一半。lL/2（220+180+65+80+70+60+75+90）/2420lL内内180+65+80+60+90445L/2lL外外75+70145L/2lL内内大于全圈长的一半，不是最优方案，应重新甩段大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段破圈，甩内圈运量最小区段a A，寻找最优方案。寻找最优方案。150100CAD17016010011080130Babcd130807090803020l计算内外圈长：计算内外圈长：lL/2（220+180+65+80+70+60+75+90）/2420lL内内180+80+60+90410L/2lL外外70+75+220365L/2l将上述运输结果填入平衡表：将上述运输结果填入平衡表：运量运量abcd产量产量A8080B13020150C8090170D7030100销量销量130100160110500接收地接收地发送地发送地【练习练习】某地区物资供销情况如图所示，现要求得物某地区物资供销情况如图所示，现要求得物资调运的最优方案。资调运的最优方案。3020502030607010020364523251823ABCDEFGHI30205020306070100202020802030304010ABCDEFGHIl根据图中箭头将内外圈货流里程汇总，检查是否超根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。过全圈长的一半。lL/2（45+23+25+18+23+36）/285lL内内25+18+2366L/2lL外外23+3659L/2l将上述运输结果填入平衡表：将上述运输结果填入平衡表：送货量送货量BCEGI产量产量A2020D2020F10302040100H303060销量销量3050207030200接收地接收地发送地发送地运量运量BCEGI产量产量A2020D2020F102070100H303060销量销量3050207030200接收地接收地发送地发送地l当运输路线有几个圈的情况，应逐圈检查并调整，当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。的最优方案。【练习练习】29006002000100057ABCDEFHI900130032001000G1500900900784575132743257554174J166K290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K距离距离ACEFGIJK销量销量B15008009003200D5009006009002900H10010009002000产量产量15001300900600100010009009008100发送地发送地接收地接收地表上作业法表上作业法l表上作业法是单纯形法在求解运输问题时的一表上作业法是单纯形法在求解运输问题时的一种简化方法。它包括以下步骤：种简化方法。它包括以下步骤：1.确定初始可行方案。方法比较多，一般希望方确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元法既简单，又尽可能接近最优解，常用最小元素法和伏格尔法。素法和伏格尔法。2.最优方案的判别。判别的方法是计算空格的检最优方案的判别。判别的方法是计算空格的检验数，常用闭回路法和位势法。验数，常用闭回路法和位势法。3.改进方案。常使用闭回路调整法进行调整以得改进方案。常使用闭回路调整法进行调整以得到最优的方案。到最优的方案。l【例例7】有某公司经销一产品，它下设三个加工厂，每日的产有某公司经销一产品，它下设三个加工厂，每日的产量分别为量分别为A17吨、吨、A24吨，吨，A39吨，该公司把这些产品吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为分别运往四个销售点。各个销售点每日销量为B13吨，吨，B26吨，吨，B35吨，吨，B46吨，已知从各工厂到各销售点的单吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足位产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。各销点的需要量的前提下，使总运费最少。B1B2B3B4A1311310A21928A374105销地销地加工厂加工厂最小元素法最小元素法B1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂314633B1B2B3B4A143A231A363销地销地加工厂加工厂l【例例8】编制被运输商品的产销平衡表和单位运输价格如下表编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小元素法求出最优运输方案的初始方案。所示，试用最小元素法求出最优运输方案的初始方案。ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂30010050010020025030050l【练习练习】最小元素法最小元素法123产量产量15181222411433674销量销量91011销地销地加工厂加工厂1011342l【练习练习】伏格尔法伏格尔法123产量产量15181222411433674销量销量91011销地销地加工厂加工厂413行差额行差额136列差额列差额11l【练习练习】123产量产量15181222411433674销量销量91011销地销地加工厂加工厂423行差额行差额13列差额列差额1110342伏格尔法伏格尔法l最小元素法的缺点是：为了节省一处的费用，最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。有时造成在其它处要多花几倍的运费。l伏格尔法考虑到，一产地的产品假如不能按伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就最小运费就近供应，就考虑次小运费，这就有一个差额，有一个差额，差额越大，说明不能按最小运差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运处，就应当采用最小运费调运。l【例例9】试用伏格尔求运输的最优方案。试用伏格尔求运输的最优方案。销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量365601125136行差额行差额列差额列差额销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量365625136行差额行差额列差额列差额0123销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量36562126行差额行差额列差额列差额01233销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量3656126行差额行差额列差额列差额7633521销地销地加工厂加工厂B1B2B3B4产量产量A17A24A39销量销量365663352112345产量产量11023159252510152430315514715204201513M830销量销量2020301025l【练习练习】伏格尔法，伏格尔法，M为无穷大的正数为无穷大的正数销地销地加工厂加工厂行差额行差额列差额列差额12255310542512345产量产量11023159252510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差额行差额列差额列差额1225105154252012345产量产量11023159252510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差额行差额列差额列差额12251051542520100l（有时在产销平衡表上填入一个运量后，在单位运价表上同时（有时在产销平衡表上填入一个运量后，在单位运价表上同时划去一行和一列，这时需要添一个划去一行和一列，这时需要添一个“0”，它的位置可在对应同，它的位置可在对应同时划去的那行或列的任一空格处）时划去的那行或列的任一空格处）12345产量产量11023159252510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差额行差额列差额列差额12951017252010202550012345产量产量125230320430销量销量2020301025销地销地加工厂加工厂25201020255002、最优方案的判别、最优方案的判别位势法位势法l使用位势法求出检验数，若检验数都不使用位势法求出检验数，若检验数都不为负数，则原方案为最优解，若有负检为负数，则原方案为最优解，若有负检验数存在，则负检验数所在空格需进行验数存在，则负检验数所在空格需进行调整。调整。l只有没有运量的空格处需要计算检验数。只有没有运量的空格处需要计算检验数。2、最优方案的判别、最优方案的判别位势法位势法l检验数的计算方法如下：检验数的计算方法如下：设有运量的格子数最多的行或列的位势设有运量的格子数最多的行或列的位势0有运量格子的运价行位势有运量格子的运价行位势+列位势列位势空格的检验数运价空格的检验数运价-（行位势（行位势+列位势）列位势）l【例例10】下面是用最小元素法的得出的运输方案，下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。试用位势法判断是否最优。B1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂314633l【例例10】下面是用最小元素法的得出的运输方案，下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。试用位势法判断是否最优。B1B2B3B4行位势行位势A1311310 A21 92 8A374 105 列位势列位势销地销地加工厂加工厂0310-1-529121-11012ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂3001005005050250250300l【练习练习】下面是用最小元素法的得出的运输方案，下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。试用位势法判断是否最优。ABCDE行位势行位势甲甲32 3 53乙乙331 34丙丙7842 2 丁丁5 4 77 8列位势列位势销地销地加工厂加工厂0547-25-4-5700-22301794213、改进方案、改进方案闭合回路调整法闭合回路调整法从负检验数所在格子出发找一条闭合回路，从负检验数所在格子出发找一条闭合回路，用水平或垂直线向前划，每碰到数字格可以用水平或垂直线向前划，每碰到数字格可以转转90度，然后继续前进，直到回到起始空格度，然后继续前进，直到回到起始空格为止。为止。并从出发格开始依次标上正负号。并从出发格开始依次标上正负号。将所有标有负号的转角格中的最小运量作为将所有标有负号的转角格中的最小运量作为调整数。调整数。各正号加上调整数，负号减去调整数。各正号加上调整数，负号减去调整数。l【例例11】使用闭合回路法对例使用闭合回路法对例10进行调整。进行调整。B1B2B3B4行位势行位势A1311310 A21 92 8A374 105 列位势列位势销地销地加工厂加工厂0310-1-529121-11012B1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂314633+-152ABCDE行位势行位势甲甲32 3 53乙乙331 34丙丙7842 2 丁丁5 4 77 8列位势列位势销地销地加工厂加工厂0547-25-4-5700-2230179421l【练习练习】使用闭合回路法对上一个练习题进行调整。使用闭合回路法对上一个练习题进行调整。ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂3001005005050250250300+-ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂3001504505050300250250+-l【例例12】试用伏格尔法求，并检验，得出最优运输试用伏格尔法求，并检验，得出最优运输方案。方案。1234供应量供应量A1067124B1610599C5410104销量销量5246销地销地加工厂加工厂费用费用1234供应量供应量A1067124B1610599C5410104销量销量5246销地销地加工厂加工厂费用费用行差额行差额14列差额列差额2115241234供应量供应量A1067124B1610599C5410104销量销量5246销地销地加工厂加工厂费用费用行差额行差额14列差额列差额23164411234供应量供应量A1067124B1610599C5410104销量销量5246销地销地加工厂加工厂费用费用行差额行差额14列差额列差额2344141234供应量供应量A1067124B1610599C5410104销量销量5246销地销地加工厂加工厂费用费用行差额行差额61列差额列差额2344142151234行位势行位势A106712B161059C541010列位势列位势销地销地加工厂加工厂费用费用414215010612-3-58-1973731234行位势行位势A106712B161059C541010列位势列位势销地销地加工厂加工厂费用费用414215+-+-1361234行位势行位势A106712B161059C541010列位势列位势销地销地加工厂加工厂费用费用41213601067-2-5111863841234行位势行位势ABC列位势列位势销地销地加工厂加工厂运量运量412136l最优运输方案如下最优运输方案如下l【练习练习】试用伏格尔法求，并检验，得出最优运输试用伏格尔法求，并检验，得出最优运输方案。方案。1234供应量供应量A1518191350B2014151730C2512172270销量销量30602040150销地销地加工厂加工厂费用费用1234供应量供应量A1518191350B2014151730C2512172270销量销量30602040150销地销地加工厂加工厂费用费用行差额行差额215列差额列差额5224601234供应量供应量A1518191350B2014151730C2512172270销量销量30602040150销地销地加工厂加工厂费用费用行差额行差额225列差额列差额522460301234供应量供应量A1518191350B2014151730C2512172270销量销量30602040150销地销地加工厂加工厂费用费用行差额行差额625列差额列差额52246030201234供应量供应量A1518191350B2014151730C2512172270销量销量30602040150销地销地加工厂加工厂费用费用行差额行差额25列差额列差额256030202010101234行位势行位势A15 181913 B201415 17 C2512 17 22列位势列位势销地销地加工厂加工厂费用费用015134116612814431234供应量供应量A50B30C70销量销量30602040150销地销地加工厂加工厂运量运量603020201010l最优运输方案如下最优运输方案如下l【练习练习】试用最小元素法求，并检验，得出最优运试用最小元素法求，并检验，得出最优运输方案。输方案。123供应量供应量A51312B24114C3674销量销量91011销地销地加工厂加工厂费用费用123供应量供应量A51312B24114C3674销量销量91011销地销地加工厂加工厂费用费用1011342123行位势行位势A513B241C367列位势列位势销地销地加工厂加工厂费用费用10113420523-4-1-1675123行位势行位势A513B241C367列位势列位势销地销地加工厂加工厂费用费用1011342+-+-123行位势行位势A513B241C367列位势列位势销地销地加工厂加工厂费用费用10954+-+-2123行位势行位势A513B241C367列位势列位势销地销地加工厂加工厂费用费用109542013-24-11565123行位势行位势ABC列位势列位势销地销地加工厂加工厂运量运量109542l最优运输方案如下最优运输方案如下供求不均衡运输供求不均衡运输l在运输的实际工作中，由于经济活动和市在运输的实际工作中，由于经济活动和市场环境的多变性，经常会存在供求不平衡场环境的多变性，经常会存在供求不平衡的现象，此时应对上述的方法进行一定的的现象，此时应对上述的方法进行一定的修正。修正。l修正的基本思路是：修正的基本思路是：化不均衡为均衡，如化不均衡为均衡，如果出现供求不平衡，则设一个虚销点或虚果出现供求不平衡，则设一个虚销点或虚发点，得出最优方案后再去掉虚设的点发点，得出最优方案后再去掉虚设的点。l【例【例12】1234供应量供应量A1518191350B2014151755C2512172270销量销量30602040销地销地加工厂加工厂费用费用l【例【例12】12345供应量供应量A15181913050B20141517055C25121722070销量销量3060204025销地销地加工厂加工厂费用费用l解决供求不均衡问题时，可使用解决供求不均衡问题时，可使用西北角法西北角法来求得初始可来求得初始可行方案。行方案。3020401554025l【例【例12】12345行位势行位势A151819130B201415170C251217220列位势列位势销地销地加工厂加工厂费用费用3020401554025002217-2162130-9-29-312-42l【例【例12】12345行位势行位势A151819130B201415170C251217220列位势列位势销地销地加工厂加工厂费用费用3020401554025002217-216213+-+-+-l【例【例12】12345行位势行位势A151819130B201415170C251217220列位势列位势销地销地加工厂加工厂费用费用30555202525002217-216213+-+-+-15l【例【例12】12345行位势行位势A151819130B201415170C251217220列位势列位势销地销地加工厂加工厂费用费用30201020602015l【练习练习】1234供应量供应量A1518191350B2014151730C2512172270销量销量30604540销地销地加工厂加工厂费用费用 在以上讨论中，假定物品由产地直接运送到销售目在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运到某个中间转运站先将物品由产地运到某个中间转运站(可能是另外的产、可能是另外的产、销地或中间转运仓库销地或中间转运仓库)，然后再转运到销售地。有时，经，然后再转运到销售地。有时，经转运比直接运到目的地更为经济。总之，很多情况下，转运比直接运到目的地更为经济。总之，很多情况下，在决定运输方案时有必要把转运也考虑进去。显然考在决定运输方案时有必要把转运也考虑进去。显然考虑转运将使运输问题变得更为复杂。虑转运将使运输问题变得更为复杂。有转运的运输问题有转运的运输问题 假定假定m个产地个产地A1,A2,Am和和n个销地个销地B1,B2,Bn都可都可以作为中间转运站使用，从而发送物品的地点相接收物品以作为中间转运站使用，从而发送物品的地点相接收物品的地点都有的地点都有m+n个。这样一来，我们就得到了一个扩大了个。这样一来，我们就得到了一个扩大了的运输问题。的运输问题。运输表 接收地接收地供供应地地 供供应地地 销售地售地发送量送量1mm+1m+n供供应地地1x11x1mx1,m+1x1,m+nQ+a1mxm.,1xmmxm,m+1xm,m+nQ+am销售地售地m+1xm+1,1xm+1,mxm+1,m+1xm+1,m+nQm+nxm+n,1xm+1,n+mxm+n,m+1xm+n,m+nQ接收量接收量QQQ+bm+1Q+bm+n在上述模型中:(a)产地发送到各个地方的物品数量之和，等于该产地的产量加上经它转运的物品数量；(b)销地接收到各个地方的物品数量之和，等于该销地的需求量加上经它转运的物品数量；例：已知例：已知A1，A2，A3三个饮料厂生产同一规格的饮料，三个饮料厂生产同一规格的饮料，用相同价格供应用相同价格供应B1，B2，B3三个销售网点销售。有两个三个销售网点销售。有两个转运站转运站T1，T2，并且产品运输可以在各产地，各销售地并且产品运输可以在各产地，各销售地及各转运站之间转运。已知各产地、销地、中转站相互及各转运站之间转运。已知各产地、销地、中转站相互之间每吨货物的单位运价和产量，见下页表。之间每吨货物的单位运价和产量，见下页表。各产地、销地、中转站之间的关系产地地转运站运站销售地售地产量量A1A2A3 T1T2B1B2B3产地地A1862410830A2851395910A3654228720转运运站站T12148463T2328232销售售地地B1492425B2105863 4B38973254销售量售量153510（1）对扩大的运输问题建立运价表。对于没有运输路）对扩大的运输问题建立运价表。对于没有运输路线的取无穷大的正数线的取无穷大的正数M；对自己运输的运价对自己运输的运价=0。（2）所有转运站的转运量等于销量，即）所有转运站的转运量等于销量，即Q=30+20+10=15+35+10=60,取取T1，T2的产量与运量均的产量与运量均为为60t。（3）在原来的产量与销量的数值在加上调运量，三个在原来的产量与销量的数值在加上调运量，三个产地的产量为产地的产量为90t，70t，80t,销量均为销量均为60t；三个销量为三个销量为75t,95t,70t,产量均为产量均为60t.如下页表所示。如下页表所示。各产地、销地、中转站之间的关系产地地转运站运站销售地售地产量量A1A2A3 T1T2B1B2B3产地地A10862M410890A28051395970A36504228780转运运站站T12140846360T2M328023260销售售地地B1492420M560B2105863M 0460B38973254060销售量售量6060606060759570用表上作业法求解的最优方案 运量运量销售地售地产量量A1A2A3 T1T2B1B2B3产地地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060销售量售量6060606060759570实际最优方案及最优运输路线如图，最小费用为300。A1A2A3B1B3B2T1T2阶段性练习1.试求下表给出的产销不平衡运输问题的最优试求下表给出的产销不平衡运输问题的最优解解B1B2B3B4供应供应量量A137645A224322A343856销量销量3322B1B2B3B4B5供应量供应量A137640 5A2243202A3438506销量销量33223 行差额行差额列差额列差额3 32 23 31 11 13 32 20 03 3B1B2B3B4B5供应量供应量A137640 5A2243202A3438506销量销量33223 行差额行差额列差额列差额1 10 01 11 11 13 32 20 03 32 20 0B1B2B3B4B5供应量供应量A137640 5A2243202A3438506销量销量33223 行差额行差额列差额列差额1 11 11 14 41 13 32 20 03 3B1B2B3B4B5供应量供应量A137640 5A2243202A3438506销量销量33223 行差额行差额列差额列差额1 11 11 11 13 32 20 03 32 21 12 2B1B2B3B4B5供应量供应量A137640 5A2243202A3438506销量销量33223 行位势行位势列位势列位势0 03 33 32 20 03 32 21 12 26 60 0-3-31 12 24 45 50 0当检验是否为最优解时，如果有检验数等当检验是否为最优解时，如果有检验数等于零，则无穷解，即：有多个最优解。于零，则无穷解，即：有多个最优解。B1B2B3B4供应量供应量A137645A224322A343856销量销量33222 23 32 21 12 2阶段性练习2.有三个产地有三个产地A1，A2，A3，生产同一种物品，使用生产同一种物品，使用者为者为B1，B2和和B3，各产地到各使用者的单位运价各产地到各使用者的单位运价见下表。这三个使用者的需求量分别为见下表。这三个使用者的需求量分别为10、4、6个个单位。由于销售需要和客观条件的限制，产地单位。由于销售需要和客观条件的限制，产地A1至至少要发出少要发出6个单位的产品，它最多只能生产个单位的产品，它最多只能生产11个单个单位的产品；位的产品；A2必须发出必须发出7个单位的产品；个单位的产品；A3至少要至少要发出发出4个单位的产品，试根据上述条件用标上作业个单位的产品，试根据上述条件用标上作业法求该运输问题的最优运输方案。法求该运输问题的最优运输方案。B1B2B3供应量供应量A13546X=4销量销量1046B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行差额行差额列差额列差额1 13 34 41 13 31 10 00 0M M3 3B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行差额行差额列差额列差额1 13 34 41 13 31 12 21 1M M3 32 2B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行差额行差额列差额列差额1 11 14 41 13 31 12 21 1M M3 32 27 7B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行差额行差额列差额列差额1 11 14 41 13 30 02 20 03 32 27 74 40 0B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行差额行差额列差额列差额1 11 14 41 13 30 00 03 32 27 74 40 03 33 33 3B1B2B3B4供应量供应量A1354M6A135405A2267M7A3435M4A343503销量销量10465行位势行位势列位势列位势3 32 27 74 40 03 33 33 30 04 44 4-4-44 45 5-2-2-1-13 30 0B1B2B3供应量供应量A13546A13545A22677A34354A34353销量销量10467 74 40 03 33 33 3B1B2B3供应量供应量A13549A22677A34354销量销量10467 74 43 36 6