运筹学 运输问题

2023/2/71第三章

运输问题第一节 运输问题及其数学模型第二节 用表上作业法求解运输问题第三节 运输问题的进一步讨论第四节应用问题举例讲四节：2023/2/72§3-1运输问题及其数学模型一、运输问题的数学模型设某物品有m个产地A1,A2,…,Am；各产地的产量分别是a1,a2,…,am；有n个销地B1,B2,…,Bn。各销地的销量分别是b1,b2,…,bn

；假如从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij；问怎样调运这些物品才能使总运费最小？这个问题是一个多产地多销地的单品种物品运输问题。把这个问题整理成为一个表,称之为运价表。（见下页）返回第三章目录2023/2/73表3-1运价表

销地产地B1B2┅Bm产量A1x11c11x12c12┅…x1nc1na1A2x21c21x22c22┅…x2nc2na2┇┇…┇…┅……┇Amxm1cm1xm2cm2┅…xmncmnam销量b1b2┅bn变量xij(i=1,2,..,m;j=1,2,…,n)为由产地Ai

运往销地Bj

的物品数量。称为产销平衡运输问题称为产销不平衡运输问题2023/2/74产销平衡运输问题的数学模型这是一个线性规划问题，可以用单纯形法求解。但是，由于它所含变量多，求解极不方便。即使求解一个m＝3，n＝4的简单运输问题，变量数目也将达到19个之多。因此，必须寻找更简便的求解方法。产量约束销量约束非负约束总运输费用极小化由某一产地运往各个销地的物品数量之和等于该产地的产量由各个产地运往某一销地的物品数量之和等一该销地的销量非负条件2023/2/75二、运输问题的数学模型的特点1.运输问题有有限最优解对运输问题的数学模型，若令变量另外，在运输问题的数学模型中,目标函数是取最小值,它的值不会趋于无穷大,在实际问题中也不可能出现这种情况,因此,运输问题有有限最优解。对运输问题数学模型的约束条件进行整理,得其系数矩阵的结构形式为：其中：是运输问题的一个可行解2023/2/762.运输问题约束条件的系数矩阵m

行n

行第i

个第(m+j)个系数列向量的结构：即除第i个和第(m+j)个分量为1外，其它分量全等于0。2023/2/77运输问题的特点:(1)

约束条件系数矩阵的元素等于0或1；(2)

约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次。如果是产销平衡运输问题,还有以下特点：（3）所有结构约束条件都是等式约束；（4）各产地产量之和等于各销地销量之和。例1某种物品先存放在两个仓库A1和A2中，再运往三个使用地B1，B2，B3，其间的运距（或单位运价）如表3-2小方格中的数据所示，试建立使总运输量（或总运费）最小的运输问题数学模型。2023/2/78表3-2

销地产地B1B2B3产量A134210A23534销量356x11x12x13x21x22x23解题思路：（1）假设变量（2）分析约束（3）明确目标（4）建立模型（5）求解变量（6）分析方案（7）得出决论66-6=010-6=434-3=13-3=011-1=05-1=444-4=04-4=000显然x11=3,x12=1,x13=6,x22=4,x21=0,x23=0是该运输问题的一个可行解。目标函数值z=452023/2/79§3-2用表上作业法求解运输问题它是求解运输问题的一种简便而有效的方法,其求解过程在运输表上进行,它是一种迭代法,其步骤为：1.先按某种规划找出一个初始解(初始调运方案）；2.对现行解作最优性判别；3.若不是最优解,就在表上对它进行调整改进,得出一个新解；4.再判别,再改进,直到得到运输问题的最优解为止；※在迭代过程中,得出的所有解都要求是运输问题的基可行解。例2某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售地出售，各工厂的生产量，各销售地的销售量（假定单位均为吨）以及各工厂到各销售地的单位运价（元/吨）示于表3-4中，要求研究产品如何调运才能使总运费最小？返回第三章目录2023/2/710一、确定运输问题的初始基可行解（初始调运方案）1.最小元素法：

销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448810-8=222-2=0212-2=101016-10=610-10=031414-14=022-14=8488-8=014-8=6566-6=06-6=08-8=0661该运输问题一个初始可行解为：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8.总运费＝4×10＋11×6＋2×8＋3×2＋5×14＋6×8＝2462023/2/711用西北角法确定运输问题的初始可行解

销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214482.西北角法88-8=0116-8=888-8=014－8=6266－6=010-6=4344-4=012-4=8488-8=022-8=1451466初始可行解为：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14.总运输费用z＝8×4＋8×12＋6×10＋4×3＋8×11＋14×6＝3722023/2/712用沃格尔法确定运输问题的初始可行解

销地产地B1B2B3B4产量行罚数12345A141241116A22103910A38511622销量814121448列罚数123450112513140122138012128761212002243.沃格尔法该运输问题的可行解为：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8,其他变量等于0。总运输费z＝2440806020404002023/2/713确定初始可行解的三种方法比较最小元素法：z＝246西北角法：z＝372沃格尔法：z＝244沃格尔法解出的目标函数值最小，最小元素法次之，西北角法最大；一般说来，沃格尔法得出的解质量最好，在运输问题中，常用来作最优解的近似解。二、解的最优性检验2023/2/7141.最小元素法解题思想：为了减少运费,应优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。解题步骤：(4)在余下的供销点的供销关系中,继续安排调运,直到安排完成所有供销任务,得到一个完整的方案为止。确定初始基可行解（初始调运方案）2023/2/7152.西北角法解题思想:优先满足运输表中西北角(即左上角)上空格的供销量需求.解题步骤:(1).最先填xij=min(ai,bj),即(Ai,Bj

)；(2).若

xij=ai

，则Ai

行不在考虑,且Bj

列剩下bj-ai

来填左上角其它空格.(3).若

xij=bj

，则Bj

列不再考虑,且Ai

行剩下ai

-bj

来填左上角其它空格.(4).如此继续完成调运,最后得出一个初始方案。用西北角法确定运输问题的初始可行解2023/2/7163.沃格尔法解题思想：对于每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若罚数的值很大，不按最小运价组织运输就会造成很大的损失；故应尽量按最小单位运价按排运输。解题步骤：（1）先计算运输表中每一行和每一列的罚数值，并称为行罚数和列罚数。（2）将行罚数填入位于运输表右侧行罚数栏的左边第一列的相应格子中；列罚数填入位于运输表下边列罚数栏的第一行的相应格子中。（3）找出该列和该行的列罚数和行罚数中的最大值；根据最大罚数值的位置在运输表中运价最小的格中填入一个尽可能大的运输量，并划去对应的一行或一列。（4）继续找其它列和行的列罚数和行罚数；找出其它运输量；已划去的不再找。直到最后按排完，即得到一个初始运输方案。用沃尔沃法确定运输问题的初始可行解2023/2/717二、解的最优性检验得到了初始可行解后，应对其进行判别是否是最优解,常用方法有：闭回路法和对偶变量法。1.闭回路法解题思想：对运输表中的解的各非基变量即某空格(Ai,Bj)进行检验;若存在检验数为负，说明将xij变为基变量后，将使运费减少；故当前解不是最优解；若所有检验数为正，则无论怎样变换解均不能使运输费降低，即当前解是最优解。解题步骤：以某空格(Ai,Bj)为顶点，由填有数字的其它格为其它顶点，通过水平线段和竖直线段组成封闭多边形。可以是简单的多边形，也可以是复杂的多边形。然后顺时针或逆时针转，以(Ai,Bj)为第一顶点格，奇格为正，偶格为负，将单位运价之代数和作为该空格的检验数sij

：若所有sij≥0，则是最优解：若存在sij＜0，则不是最优解。2023/2/718用闭回路法对解的最优性进行检验

销地产地B1B2B3B4产量A141210461116A2821023910A38145118622销量8141214481012-1112s11=c11-c21+c23-c14=4-2+3-4=1s31=c31-c34+c14-c13+c23-c21=8-6+11-4+3-2=10s12=c12-c32+c34-c14=12-5+6-11=2s22=c22-c32+c34-c14+c13-c23=10-5+6-11+4-3=1s33=c33-c34+c14-c13=11-6+11-4=12s24=c24-c14+c13-c23=9-11+4-3=-1由于s24＝-1＜0所以，上表中的解不是最优解。2023/2/7192.对偶变量法（位势法）:解题思想：用u1,u2,…,um分别表示与前m个约束相对应的对偶变量，用v1,v2,…,vn分别表示与后n个约束相对应的对偶变量，即对偶变量向量：Y=(u1,u2,…,um,v1,v2,…,vn)将运输问题的数学模型写成对偶规划：2023/2/720经过整理得出运输问题变量xij的检验数为：如果所有的sij≥0，则所求得的可行解是最优解，如果存在sij＜0，则所求得的可行解不是最优解，需要改进。2023/2/721解题步骤：(一）在运输表右边增加一位势列ui；在下边增加一位势行vj；(二）计算位势(三）计算检验数：

sij=cij-(ui+vj)由于基变量的检验数sij＝0，故对这组基变量可以写出方程组：这个方程组有（m+n-1)方程，（m+n）个变量，所以它的解不是唯一解。这个方程组的解称为位势。2023/2/722例3用位势法对前例运输问题作最优性检验。

销地产地B1B2B3B4产量uiA141210461116u1A2821023910u2A38145118622u3销量814121448vjv1v2v3v4（1）在运价表上增加一位势列ui

和位势行vj

，（上表）（2）建立位势方程组，计算位势。10-429310（3）计算检验数。sij＝cij－（ui+vj)1102112-1由于s24=-1＜0，所以上表得出的可行解不是最优解。需要改进2023/2/723建立位势方程组，计算位势u2＝0，v1＝2v3＝3，u1＝1v4＝10

，u3＝－4v2＝9任意指定某一位势等于一个较小的整数或零，如

u2＝0将计算结果填入运输表的位势列和位势行。2023/2/724三.解的改进1.改进原因对运输问题来说,若某空格的检验数sij为负，说明将这个非基变量变为基变量时运费会减小，因而这个解不是最优解,还需要改进；2.改进方法在运输表中，找出sij＜0的空格对应的闭回路Lij，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量,以得到另一个更好的基可行解。2023/2/7253.改进步骤：(1)以xij为换入变量，找出它在运输表中的闭回路；(2)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺时针或逆时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的所有偶数顶点中，找出运输量最小(minxij)的顶点(格子)，以该格中的变量为换出变量；(4)以minxij为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减少这一数值，从而得出一新的运输方案。该方案的总运费比原运输方案的总运费减少，改变量等于sij(minxij)。（5）对得到的新解进行最优性判别。重复上述步骤，直到得到最优解为止。2023/2/726例4对例2用最小元素法得出的解进行改进（2）计算检验数，对解的最优性进行判断。

销地产地B1B2B3B4产量A141210461116A2821023910A38145118622销量814121448（+2）（-2）（+2）（-2）124

21122109（1）因为s24＜0，所以，以此格——（A2，B4）为顶点寻找一个闭回路，进行解的改进。∵sij≥0,∴最优解为：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8 z＝12×4＋4×11＋8×2＋2×9＋14×5＋8×6＝2442023/2/727四、需要说明的几个问题1.若运输问题的某一基可行解中，有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取sij＜0中最小者对应的变量为换入变量。2.当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重最优解。3.当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时，需同时划去运输表的一行和一列，即出现退化。退化是时有发生的，为使迭代进行下去，退化时在同时划去的一行或一列中的某个格中填入0，表示该格变量取值为0的基变量，使迭代过程中基可行解的分量恰好为(m+n–1)个。2023/2/728§3-3运输问题的进一步讨论一、产销不平衡的运输问题解题思想：把产销不平衡的运输问题转化为产销平衡问题。返回第三章目录2023/2/729可假想一个销地Bn+1，其销量为bn+1，其实质没有运输，只是就地储藏。设调运假想销地的物品数量为xi,n+1；故其单位运价ci,n+1＝0;且此式对应的运输表见下页。2023/2/730产量大于销量的运输表

销地产地B1B2…BnBn+1（储存）产量A1x11c11x12c12……x1nc1nx1,n+10a1A2x21c21x22c22……x2nc2nx2,n+10a2┆┆…┆…┆…┆…┆…┆Amxm1cm1xm2cm2……xmncmnxm,n+10am销量b1b2…bn2023/2/731(2)如果总销量大于总产量，则增加一个假想产地，它的产量等于总销量与总产量之差。

销地产地B1B2…Bn产量A1x11c11x12c12……x1nc1na1A2x21c21x22c22……x2nc2na2┆┆…┆…┆…┆…┆Amxm1cm1xm2cm2……xmncmnamAm+1(假想产地）00……0销量b1b2…bnxm+1,1xm+1,2xm+1,n2023/2/732二、有转运的运输问题由于空间位置的需要，需考虑转运问题，才能使总运费最小。A1A2B2B1B3产地销地A2A1B2B1B3产地销地（a)无转运（a)包含转运比较以上两图。显然，包含转运的运输问题复杂得多。2023/2/733假定m个产地A1,A2,…,Am和n个销地B1,B2,…,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。ai

：第i个产地的产量（净供应量）；bj

：第j个销地的销量（净需要量）；xij

：第i个发送地运到第j个接收地的物品数量；cij

：由第i个发送地运到第j个接收地的单位运价；ti

：第i个地点转运物品的数量；ci

：第i个地点转运单位物品的费用；则有：am+1=am+2=,…,am+n=0，b1=b2=,…,=bm=0n个销地的净产量等于零。m个产地地的净销量等于零。2023/2/734有转运的运输问题模型：由第i个产地发送到各个地方的物品数量之和，等于该产地的产量加上经它转运的物品数量。由第i个发送地发送到各个地方的物品数量之和，等于经它转运的物品数量。由各地运到第j地的物品数量之和，等于转运量。由各地运到第j地的物品数量之和，等于净需要量加上转运量。令xii=Q-ti或xjj=Q-tj

，则ti=Q-xii,tj=Q-xjj经整理得：2023/2/735注意：在上式中，对所有i＝j，cij＝－ci。由于目标函数中是常数,故不影响求最优解。其对应的表如下有转运问题的运输表有转运问题的运价表2023/2/736有转运问题的运输表

接收发送产地销地发送量1…mm+1…m+n产地1x11…x1mx1,m+1…x1,m+nQ+a1┆┆…┆┆…┆┆mxm1…xmmxm,m+1…xm,m+nQ+am销地m+1xm+1,1…xm+1,mxm+1,m+1…xm+1,m+nQ┆┆…┆┆…┆┆m+nxm+n,1…xm+n,mxm+n,m+1…xm+n,m+nQ接收量Q…QQ+bm+1…Q+bm+n表3-172023/2/737有转运问题的运价表

接收发送产地销地发送量1…mm+1…m+n产地1-c1…c1mc1,m+1…c1,m+nQ+a1┆┆…┆┆…┆┆mcm1…-cmcm,m+1…cm,m+nQ+am销地m+1cm+1,1…cm+1,m-cm+1…cm+1,m+nQ┆┆…┆┆…┆┆m+ncm+n,1…cm+n,mcm+n,m+1…-cm+nQ接收量Q…QQ+bm+1…Q+bm+n表3-182023/2/738例6

有一个运输系统包括二个产地（①、②）、二个销地（④、⑤）及一个中间转运站（③），各产地的产量和各销地销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。解：a1=10,a2=40,a3=a4=a5=0b1=b2=b3=0,b4=30,b5=20Q=10+40=30+20=50c1=4,c2=1,c3=3,c4=3,c5=512345105243402145536305320以M表示足够大的正数，可得该问题的运输表3-192023/2/739表3-19

接收发送产地转运销地发送量12345产地1-4532M6025-12M490转运332-35550销地42M5-36505M456-550接收量5050508070例6图2023/2/740表3-20

接收发送产地转运销地发送量12345产地150-453102M602550-1220M20490转运33250-350550销地42M550-36505M45650-550接收量50505080702023/2/741表3-21

接收发送产地转运销地发送量12345产地150-453102M602550-1220M20490转运33250-305550销地42M550-36505M45650-550接收量50505080702023/2/742表3-22

接收发送产地转运销地发送量12345产地150-453102M602550-1202M20490转运33230-3205550销地42M550-36505M45650-550接收量5050508070Excel求解2023/2/743§3-4运用问题举例例题一：某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市和终点城市及每天的航班数见表3-28；（2）各城市间的航行时间见表3-29；（3）所有航线都使用同一种船只，每次装船和卸船时间均为1天。问该公司至少应配备多少条船才能满足所有航线运输的需要？表3-28航线起点城市终点城市每天航班数1ED32BC23AF14DB1表3-29各城市间的航行时间返回第三章目录2023/2/744表3-29各城市间的航行时间（天）解：所需船只可分为两部分：（1）各航线航行、装船、卸船所占用的船只，对各航线逐一分析，所需船只数列入表3-30中，累计共需91条船。

至从ABCDEFA0121477B1031388C23015557851703F7852030返回表3-282023/2/745表3-30各航线航行、装船、卸船所占用的船只（2）各港口之间调度所需船只数。这由每天到达港口的船只数与它所需发出的船只数不相等而产生。各港口城市每天到达船只数、需求船只数及其差额如表3-31中。航线装船天数卸船天数航行天数小计航班数所需船只11117193572113521031179194111315115表3-31各港口城市每天到达、需求及差额船只数城市ABCDEF每天到达012301每天需要120130余缺数-1-122-31航线2023/