《运筹学》课件 第4章 运输问题

第四章运输问题一驿过一驿，驿骑如星流。

平明发咸阳，暮及陇山头。——岑参《初过陇山途中呈宇文判官》第4章内容提要4.1运输问题及其数学模型4.2表上作业法4.3产销不平衡的运输问题4.4运输模型的应用4.5线形规划的基本理论物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）TheTransportationProblem运输问题你怎么去分析这类问题呢？想想看！TheTransportationProblem运输问题运输问题是线性规划问题的特例。产地：货物发出的地点。销地：货物接收的地点。产量：各产地的可供货量。销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。4.1运输模型

某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。一、运输问题举例

销地产地B1B2B3B4产量A163255A275842A332973销量2314(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数

minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件。产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束

xij≥0(i=1,2,3；j=1,2,3,4)

运输问题的LP模型

二、表式运输模型

销地产地A1A2…Am产量a1a2…amB1B2…Bn销地b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn产销平衡三、运输问题的三种类型

产大于销产小于销

决策变量m

n约束方程m+n系数矩阵的结构如下：四、运输模型的特点x11x12…x1nx21x22…x2n…………xm1xm2…xmnm行n列在实际问题建模时，还会出现如下一些变化：①有时目标函数求最大，如求利润最大或营业额最大等；②当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；③产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在产量约束条件中加上m个松弛

变量；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在需求约束条件中减去n个松弛变量。运输问题求解的有关概念基变量的特点

（1）基变量共有m+n-1个

（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路4.2表上作业法表上作业法适合于产销平衡的运输问题求解步骤：找出初始方案（初始基可行解）：在m

n维产销平衡表上给出m+n-1个数字。

最优性检验：计算各非基变量的检验数，当

ij0最优。方案调整与改进：确定进基变量和离基变量，找出新的基可行解。最小元素法“就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量min{ai,bj}。最大差额法不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列查)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。一、确定初始方案从单位运价表中逐次挑选最小元素，安排运量min{ai,bj}。然后，划去该元素所在行或列：当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。最小元素法销地产地B1B2B3B4产量A163255A275842A332973销量2314130222初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38例1求以下运输问题

销地产地B1B2B3B4产量A13113107A219284A3741059销量

3656最小元素法3B1B2B3B4A1113101A29287A3410531销量3656947产量最小单位运价A2供应B1最小单位运价31012最小单位运价43最小单位运价64最小单位运价35伏格尔法3B1B2B3B4A1113101A29287A3410531列差额2513110行差额A3供应B22101853最大差额64该列最小单位运价35947产量销量3656分别计算各行各列的最小运费和次小运费的差额再计算未划去各行各列的最小运费和次小运费的差额2最大差额该列最小单位运价2最大差额该列最小单位运价76最大差额该行最小单位运价初始解

哪一个更优呢？最小元素法：

3*1+6*4+4*3+1*2+3*10+3*5=86

伏格尔法：

3*1+6*4+5*3+2*10+1*8+3*5=85

最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。伏格尔法则考虑一产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有了一个差额差额越大，说明不能按最小运费调运时，运费增加越多。因此对差额最大处，就应当采用最小运费调运判别方法是计算非基变量的检验数：

ij=cij–

CBPij’=cij–

CBB-1Pij运输问题的目标函数要求为最小，即当

ij0视为最优。位势法计算检验数

ij=cij–

CBPij’=cij–

CBB-1Pij

ij=cij–(ui+vj)ui代表产地Ai的位势量，vj代表销地Bj的位势量。基变量的检验数为0，即

ij=cij–ui

–

vj=0，并令u1=0，计算各行各列的位势量。二、最优性检验闭回路法在初始解上，对每个空格找一条闭回路以某个空格为起点，用水平或垂直线向前划，每碰到一个数字格转90度，继续前进，直接回到起始空格为止。从每一空格出发一定存在和可以找到唯一的闭回路。可能有时要跳过某个数字格闭回路法3B1B2B3B4A111A2987A31031销量3656947产量31012436435(+1)(-1)(+1)(-1)(1)33B1B2B3B4A111A2987A31031销量3656947产量31012436435(-1)(+1)(-1)(+1)(1)3(2)113103B1B2B3B4A111A2987A31031销量3656947产量6435(+1)(1)3(2)11(12)104312(-1)83B1B2B3B4A111A2987A31031销量3656947产量31012436435(-1)(-1)(-1)(+1)(+1)(+1)(10)7(1)3(2)11(-1)8(12)103B1B2B3B4A111A2987A31031销量3656947产量31012436435(-1)(+1)(+1)(-1)(+1)(-1)(1)9(1)3(2)11(-1)8(12)10(10)7(1)3闭回路法:空格检验数有负数，未达最优3B1B2B3B4A111A287A31031销量3656947产量31012436435(1)9(2)11(-1)8(12)10(12)73B1B2B3B4A111A2987A31031销量3656947产量31012436435基变量的检验数

ij=cij–ui

–

vj=0，即cij=ui+vj，且令u1=0，计算位势量ui和vj位势法销地产地B1B2B3B4产量A162321525A2758422A33023973销量2314uivj0625-1-35计算非基变量的检验数

ij=cij–ui

–

vj位势法（续）销地产地B1B2B3B4产量uiA1623215250A2758422-1A33023973-3销量2314vj6525-2217105非基变量x12的检验数

12=c12–u1–v2=-2，即让非基变量x12从0增到1，可使总运费减少2个单位。确定进基变量检查非基变量xij的检验数

ij

，按min{

ij|

ij<0}=

lk确定xlk进基。确定离基变量非基变量xlk进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持产销平衡。保持产销平衡的方法是闭回路法。闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90º，继续前进，直到返回始点。奇偶点：

始点是偶点，依次奇偶相间标注；偶点标“+”

，表示运量增加量；奇点标“-”

，表示运量减少量。调整量：最小可减少的运量，即奇点运量的最小值。奇点运量的最小值所在格的基变量离基。三、改进的方法（闭回路调整法）(1)3闭回路调整法:空格检验数有负数，未达最优,调整3B1B2B3B4A111A287A31031销量3656947产量31012436435(1)9(2)11(-1)8(12)10(12)73B1B2B3B4A111A287A31031销量3656947产量310124364359(-1)818

210

532调整量θ＝min{3,1}=1位势法ABCDEF需求量300200200300300100供应量

至从71003空格检验数计算公式:δij=cij-(ui+vj)10032004073009(-1)5(0)4(2)8(-1)5位势v643300位势u例子闭回路300200200300300100700548751003DA和FC格的检验数均为负数，这里选择DA空格检验数:DA:DA

DCECEBFBFADA5-3+3-4+7-9=-1新解为1003200407483009(-1)5–++––+ABC供应量

至从DEF需求量调整300200200300300100700487510031003200407483009–++––+2009(-1EF需求量ABC供应量

至从调整后300200200300300100700485总成本:100*5+100*4+200*3+200*9+100*7=400048200910053200310041007ABC供应量

至从DEF需求量重算检验数30020020030030010070048548200910053200310041007闭回路和检验数:DB:DBFB

FA

DA

DB4-7+9-5=1DC:DCECEBFBFADA3-3+4-7+9-5=1EA:EAEBFBFAEA8-4+7-9=2FC:FCECEBFBFC5-3+4-7=-1(-1)5(1)4(1)3(2)8负数!!!还要调整DEF需求量ABC供应量

至从第二次调整300200200300300100700520091005200310041007(-1)5(1)4(1)3(2)8–+–+1005710032004ABC供应量

至从DEF需求量第2次调整——最优300200200300300100700200910051004(1)7(2)4(2)3(1)810051003总成本:100*5+100*4+100*3+200*9+100*5=3500所有空格检验数均非负，达到最优解!DEF需求量ABC供应量

至从用位势法计算调整后的检验数ABCDEF需求量300200200300300100供应量

至从7(2)3空格检验数计算公式:δij=cij-(ui+vj)10031004(1)720091005(2)4(1)81005Dualv521420Dualu4.3产销不平衡问题产销平衡的运输问题采取表上作业法求解。产销不平衡的运输问题需划成产销平衡问题再求解。产大于销：虚设一个销地Bk(多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差bk=

ai-bj。产小于销：虚设一个产地Al(不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差ak=

bj

-

ai

。增加一个销地一、产大于销销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销量18121650-46B4000450465050初始基可行解销地产地B1B2B3B4产量A1592015A2317018A3628017销量1812164121561214

初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140最优性检验销地产地B1B2B3B4产量uiA159215015A2361127018A36122810417销量1812164vj0260-63-2511623-2

非基变量x32的检验数

32=-2，即让非基变量x32进基。闭回路调整x32进基最小调整量为12，x31离基销地产地B1B2B3B4产量A159215015A2361127018A36122x32810417销量1812164-+-+非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量。

基可行解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34销地产地B1B2B3B4产量A159215015A2317018A362810417销量181216461212

180

12基变量的检验数

ij=cij–ui

–

vj=0，且令u1=0，计算位势量ui和vj最优性检验

所有非基变量xij的检验数

ij=cij–ui–vj≥0，即得最优解。销地产地B1B2B3B4产量uiA159215015A231817018A360212810417销量1812164vj0260-4-635136232增加一个产地二、产小于销销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523-22000122232323初始基可行解销地产地B1B2B3产量A141210A234312A30001销量8105100571

初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=46最优性检验销地产地B1B2B3产量uiA141102010A23743512A301001销量8105vj01212-22210检验数

ij≥0，得最优解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46由于非基变量x33的检验数

33=0，为多最优解。让x33进基,x31离基,得另一最优解:x12=10,x13=0,x21=8,x23=4,x33=14.4运输模型的应用短缺资源分配，“产小于销”，需注意产销配比问题。

上例x12=10,x13=0,x21=7,x23=5,x31=1，表示销地B1脱销1个单位；然而x12=10,x13=0,x21=8,x23=4,x33=1，则表示销地B3脱销1个单位；但销地B3的销量为5，本身就很少，不允许脱销，如何处理呢？自来水分配问题：水价90元/kt，管理费45元/kt，引水费如下表：一、短缺资源的分配问题供区水库甲乙丙丁供水量kt/dA1613221750B1413191560C192023--50最低需求kt/d3070010最高需求kt/d507030不限如何分配供水量，保障各区最低需求，获利最大？

利润=收入-成本，收入最大，成本最小，则利润最大。收入：每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。每天总收入是常数，与水量分配无关，可以不与考虑。成本：各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到最小，总成本则最低。如何分配水量，既满足最低需求，又使总的引水费最低？最大需求量：供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。分析产小于销的运输问题化为平衡问题，虚设水库D，供水量50。各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0。供区水库供水量A50B60C50甲1甲2乙丙丁1丁216161322171714141319151519192023MM销量302070301050DM0M0M050用表上作业法求得最优方案供区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050销量302070301050最优分配方案：水库A向乙区供水50，水库B分别向乙区、丁区供水20和40，水库C向甲区供水50，不给丙区供水。最小引水费：1350+1320+15(10+30)+19(30+20)=2460引水管理费：45(50+60+50)=7200总成本：2460+7200=9600总收入：90(50+60+50)=14400最大获利：14400-9600=4740二、生产与存储问题某厂按照合同规定须于当年每季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货，每台每积压一个季度，存储维护费用0.15万元。要求在完成合同的情况下，使得全年生产（存储）费用最小的决策。季度生产能力/台单位成本/万元Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3销售运费单价生产ⅠⅡⅢⅣ虚拟D供应量（台）Ⅰ10.810.8+0.1511.1011.25025ⅡM11.1011.2511.40035ⅢMM11.011.15030ⅣMMM11.30010需求量/台1015252030注意：单位运价如何确定故设：表示第季度生产，用于第季度交货的产品数量。可建立数学模型。产地与销地之间存在转运站。面粉转运问题：三个面粉加工厂，两个糕点生产厂，两个中转站。三、资源转运问题终点始点面粉厂中转站糕点厂生产能力A1A2A3T1T2B1B2面粉厂A1323-683A242521374A3-2321143中转站T1352625T2-327-2糕点厂B16--2-94B2--4-396如何调运，总运费最低？转运能力≤t=max{

ai，

bj}=10销地产地面粉厂中转站糕点厂产量A1A2A3T1T2B1B2面粉厂A1A2A3中转站T1T2糕点厂B1B2销量0323M6840252137M20321143520625M3270M26MM2M09MM4M39013141310101010面粉厂产量:ai+t糕点厂产量:t转运站产量:t面粉厂销量:t糕点厂销量:bj+t转运站销量:t10101010101416323-68342521374-2321143352625-327-26--2-94--4-396用表上作业法求得最优方案最优分配方案：面粉厂A3向糕点厂B2直接运输2吨，A1、A2、A3向中转站T1和T2运输3、4、1吨，中转站T1和T2分别向糕点厂B1

、B2运输4、4吨。最小运费：33+24+31+42+24+24=44销地产地面粉厂中转站糕点厂产量A1A2A3T1T2B1B2面粉厂A1A2A3中转站T1T2糕点厂B1B2销量103131041410121364106410101010101010101010141633441234446《越州赵公救灾记》节选思政探讨

熙宁八年夏，吴越大旱。九月，资政殿大学士知越州赵公，前民之未饥，为书问属县灾所被者几乡，民能自食者有几，当廪于官者几人，沟防构筑可僦民使治之者几所，库钱仓粟可发者几何，富人可募出粟者几家，僧道士食之羡粟书于籍者其几具存，使各书以对，而谨其备。州县史录民之孤老疾弱不能自食者二万一千九百余人以告。故事，岁廪穷人，当给粟三千石而止。公敛富人所输，及僧道士食之羡者，得粟四万八千余石，佐其费。使自十月朔，人受粟日一升，幼小半之。忧其众相蹂也，使受粟者男女异日，而人受二日之食。忧其流亡也，于城市郊野为给粟之所凡五十有七，使各以便受之而告以去其家者勿给。计官为不足用也，取吏之不在职而寓于境者，给其食而任以事。不能自食者，有是具也。能自食者，为之告富人无得闭粜。又为之官粟，得五万二千余石，平其价予民。为粜粟之所凡十有八，使籴者自便如受粟。又僦民完成四千一百丈，为工三万八千，计其佣与钱，又与粟再倍之。民取息钱者，告富人纵予之而待熟，官为责其偿。弃男女者，使人得收养之。P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝·李）加工，然后用卡车把它们运送到美国西部的四个分销仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古)。TransportationProblemExample运输问题举例实际举例TransportationProblemExample运输问题举例实际举例P&T公司问题中的仓库和加工厂位置图

TransportationProblemExample运输问题举例实际举例作为一个运输问题的P&T公司电子表格描述

每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品需求假设（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假设（TheCostAssumption）整数解性质（IntegerSolutionsProperty）CharacteristicsofTransportationProblems运输问题的特征需求假设（TheRequirementsAssumption）：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足TheRequirementsAssumption需求假设可行解特性（TheFeasibleSolutionsProperty）：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解TheFeasibleSolutionsProperty可行解特性成本假设（TheCostAssumption）：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量

TheCostAssumption成本假设整数解性质（IntegerSolutionsProperty）：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件IntegerSolutio