运输问题 课件.ppt

,第三章 运输问题,产销不平衡的运输问题,内 容,运 输 问 题,表上作业法,1,2,3,运输问题的应用,4,运筹学 第三章 运输问题,Slide 3,一、运输模型（产销平衡）,例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？,设Xij表示从产地Ai调运到Bj的运输量(i1，2；j1，2，3)，现将安排的运输量列表如下：,运筹学 第三章 运输问题,Slide 4,产销平衡表,满足产地产量的约束条件为： X11+X12+X13=200 X21+X22+X23=300满足销地销量的约束条件为： X11+X21150 X12+X22150 X13+X23200,运筹学 第三章 运输问题,Slide 5,使运输费最小的目标函数为： minz6X11+4X12+6X13+6X21+5X22+5X23Xij=0一般运输问题的线性规划的模型： 有m个产地生产某种物资，有n个地区需要该类物资。Al，A2，Am表示某种物资的m个产地；Bl，B2，Bn表示某种物资的n个销地；令a1, a2, , am表示各产地产量， b1, b2, , bn表示各销地的销量，ai=bj 称为产销平衡。Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。,运筹学 第三章 运输问题,Slide 6,则产销平衡的运输问题的线性规划模型如下所示：,运输问题有mn个决策变量，m+n 个约束条件。由于产销平衡条件，只有m+n1个相互独立，因此，运输问题的基变量只有m+n1 个。,运筹学 第三章 运输问题,Slide 7,共有2个产地和3个销地，产销平衡。基变量的个数为2+3-1=4,Objective value: 2500,运筹学 第三章 运输问题,Slide 8,二、表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。(1)给出初始调运方案初始基可行解：即在(mn)产销平衡表上给出m+n-1个数字格。用最小元素法或伏格尔法。(2)检验方案是否最优，若是最优解，则停止计算；否则转下一步。求各非基变量的检验数，即在表上计算空格的检验数。在表上用闭环回路法或乘数法。(3)调整调运方案，得新的方案。确定入基和出基变量，找出新的基可行解。在表上用闭环回路法。(4)重复(2),(3)直到求出最优方案。【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。,运筹学 第三章 运输问题,Slide 9,证：记ai= bj=QXij=aibj/Q就是一个可行解，因为Xij0，且满足Xij=ai, Xij=bj又因为Cij0,Xij0,所以目标函数有下界零。因而运输问题一定有最优解。1、确定初始基可行解最常用的方法是最小元素法。既简便，又尽可能接近最优解。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。,运筹学 第三章 运输问题,Slide 10,P83例2.1：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A17吨，A24吨，A39吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B13吨，B26吨，B35吨，B46吨。已知从各工厂到各销售点的单位产品的运价如下表所示。 产销平衡表,1）找出最小运价为1，先将A2的产品供应给B1，因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。2）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。最后在(A1,B4)的交叉格处填上3，将A1行和B4列运价同时划去，得到一个初始调运方案。这方案的总运费为86元。,3,1,4,6,3,3,运筹学 第三章 运输问题,Slide 12,最小元素法中的退化情况,第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。出现退化时，要在同时被划去的行列中选一个空格填0， 此格作为有数字格。,3,4,5,6,0,2,伏格尔法(Vogel)差额法：最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。,3,1,5,6,3,2,运筹学 第三章 运输问题,Slide 15,1）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。3）对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为85元。伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出的初始解就是最优解。,运筹学 第三章 运输问题,Slide 16,2、调运方案的检验,判别的方法是计算空格（非基变量）的检验数，若所有的检验数都大于等于0，为最优解。1）闭环回路法：在给出的初始调运方案表上，从每一空格出发找一条闭环回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一数字格转90后（回路的转角点必须是一个基变量） ，继续前进，直到回到起始空格为止。从每一空格出发一定存在且只有唯一的闭环回路。从空格开始加减闭环各个顶点的运输单价，可得每个空格对应的检验数。,3,1,4,6,3,3,运筹学 第三章 运输问题,Slide 18,闭环回路计算检验数的经济解释为：从任一空格出发，如(A1,B1)，若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在(A2,B1)处减少1吨，在(A2,B3)处增加1吨，在(A1,B3)处减少1吨，即构成了以空格(A1,B1)为起点的闭环回路。调整后的方案使运费变成(+1)3(1)1 (+1)2(1)31（元）这就是(A1,B1)的检验数。当检验数还存在负数时，说明原方案还不是最优解。用闭环回路求检验数,当产销点很多时,这种计算很繁琐。2）乘数法（位势法）：乘数法的原理是对偶理论。,运输问题,对偶问题,ij与原问题有什么关系？ 由对偶性质，ij是原问题变量xij 的检验数。当xij是基变量时， ij=0，此时有 由此求出Ui 和Vj，再代回（*）式求非基变量的ij（空格检验数）,P93-94,基变量：X13 U1+V3=C13=3X14 U1+V4=C14=10X21 U2+V1=C21=1X23 U2+V3=C23=2X32 U3+V2=C32=4X34 U3+V4=C34=5设U10，则V3=3,U2=-1, V1=2,V4=10,U3=-5,V2=9非基变量：C11U1V1=3021C12U1V211092C22U2V2=9191C24U2V481101C31U3V1=7+5210C33U3V3=105312,3、调整改进的闭环回路方法迭代,若有两个或两个以上的负检验数时，一般选其中最小的负检验数。以(24)格为调入格，以此格为出发点，作一闭环回路。在闭回路上进行运量调整，使选定空格处的运量尽可能地增加（即取相邻两数字格中较小的）。,运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。经检验，所有检验数都非负，故达到最优，最优方案总运费最小是85元。,运筹学 第三章 运输问题,Slide 22,课堂作业：,1、用表上作业法求出最优解。（最小元素法）,2、用伏格尔法直接给出近似最优解。,运筹学 第三章 运输问题,Slide 23,1、这是一个产销平衡的问题。1）初始调运方案（最小元素法）,40,15,20,25,10,25,初始调运方案的总运费为420元。2）最优解的判别（闭环回路法）,40,15,20,25,10,25,（乘数法）：基变量：X11 U1+V1=C11=3X12 U1+V2=C12=2X21 U2+V1=C21=7X23 U2+V3=C23=2X24 U2+V4=C24=3X31 U3+V1=C31=2设U10，则V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基变量：C13U1V3=70+29C14U1V460+17C22U2V2=542-C32U3V25124C33U3V3=4+1+27C34U3V4=5+1+17,运筹学 第三章 运输问题,Slide 26,3)调整调运方案，得新的方案。,以(22)格为调入格，以此格为出发点，作一闭环回路。经检验，所有检验数都大于0，该调运方案是最优的方案。总运费为395元。,40,15,20,25,10,25,2、用伏格尔法直接给出近似最优解。,5,20,20,25,20,10,0,0,运筹学 第三章 运输问题,Slide 29,用伏格尔法直接找到了近似最优方案，总运价为305元。,运筹学 第三章 运输问题,Slide 30,第二种算法：,用伏格尔法直接找到了近似最优方案，总运价为345元。用伏格尔法求解，是否一定要转化为产销平衡表？,三、产销不平衡的运输问题,产销平衡表,P96例2.3：假设产地A1的产品必须全部调运出去,产地A2、A3的商品调运不出的单位存储费为2百元和1百元,产大于销,运输费用：22+54+33+41+12=39 (百元) 存储费用：22+21=6 (百元)总成本：39+6=45(百元),P98例2.4销大于产,销地B1、B2的需求必须全部满足，销地B3、B4每短缺1吨，发生损失费1百元、0。,总成本是52百元，其中2百元是销地B3发生缺货的损失费。,运筹学 第三章 运输问题,Slide 34,例3石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北临城，山西孟县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同。两处煤矿能供应北方研究院的煤的数量，山西盂县为4000吨，河北临城为l500吨，由煤矿至北方研究院的单位运价(百元吨)见下表。由于需求大于供给，经院研究平衡决定一区供应量可减少0200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费最低的调运方案。,运筹学 第三章 运输问题,Slide 35,河北临城，山西孟县两处煤矿可以供应煤5500吨。一区、二区、三区至少需要煤5500吨。至多需要煤6000吨。一区和三区必须供应的煤分别为2800吨和1700吨。可以不供应的煤分别为200吨和300吨。 产销平衡表,运筹学 第三章 运输问题,Slide 36,例4设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。,运筹学 第三章 运输问题,Slide 37,三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量，地区IV 最高需求是否可以不限？最高需求是多少？160 3070060吨四个地区对化肥的最高需求为50703060 210吨,运筹学 第三章 运输问题,Slide 38,四、运输问题的应用,（一）生产与储存的问题 P109习题2-16 某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能力及市场每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护费用0.2万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。,运筹学 第三章 运输问题,Slide 39,设Xij为第i季度生产的用于第j季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用。四个季度的生产能力为100台。而四个季度末共须提供柴油机70台。,运筹学 第三章 运输问题,Slide 40,例6光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表。又已知上年末库存103台绣花机。加班生产机器每台增加成本1万元。,运筹学 第三章 运输问题,Slide 41,又如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7、8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。问应如何安排16月份的生产使总的生产(包括运输、仓储、维护)费用最少?设Xij为第i个月生产的用于第j个月交货的机器数实际的成本为该月生产成本加上运输、储存和维护费用将正常生产和加班生产分成两种不同的生产月来进行安排。六个月的生产能力为743台。而六个月末共须提供机器707台。上年末库存的103台绣花机，作为第0个月的生产供给。,运筹学 第三章 运输问题,Slide 43,（二）调度问题,例7：某航运公司承担六个港口初始A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表71。假定各条航线使用相同型号的船只，又各城市间的航程天数见表72。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？ 表71,表72,(1)载货航程需要的周转船只数：,运筹学 第三章 运输问题,Slide 45,例如：航线1，在港口E装货1天，ED航程17天，在D卸货1天，总计19天。每天3航班。故该航线需周转船57条以上共需周转船只数91条。(2)各港口间调度所需船只数。有些港口每天到达船数多于需要船数。例如，港口D，每天到达3条，需求1条。,运筹学 第三章 运输问题,Slide 46,为使各港口间调度周转所需的空船数最少，其产销平衡表如下。单位运价应为相应各港口之间的船只航程天数。,可求出空船的最优调度方案如下：,运筹学 第三章 运输问题,Slide 47,由上表可计算得知最少周转的空船数为40条。所以，在不考虑维修、储备等情况下，该公司至少应配备131条船。（三）转运问题例8腾飞电子仪器公司在大连和广州有两个分厂，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，公司同意大连分厂也可以向青岛直接供货。这些城市间的每台仪器的运输费用我们标在两个城市间的弧上，单位为百元。问应该如何调运仪器，使得总的运输费最低。,运筹学 第三章 运输问题,Slide 48,思路:将转运问题化为无转运问题。中转地3、4既可作为产地，也可作为销地。,例9：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A17吨，A24吨，A39吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B13吨，B26吨，B35吨，B46吨。已知从各工厂到各销售点的单位产品的运价如下表所示。课本P100例2.5,运筹学 第三章 运输问题,Slide 50,如果假定1）每个工厂生产的产品不一定直接发运到销售点，可以其中几个产地集中一起运；2）运往各销售点的产品可以先运给其中几个销售点，再转运给其它销售点；3）除产地、销售点之外，中间还可以有几个转运站，在产地之间、销售点之间或产地与销售点之间转运。已知各产地、销售点、中间转运站及相互之间每吨产品的运价如下表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往各个销售点，使总的运费最少。,运筹学 第三章 运输问题,Slide 52,从A1到B2的单位运价为11元，如从A1经A3运往B2，运价为347元，从A1经T2运往B2，运价为156元。运费最少的路经是从A1经A2、B1运往B2，运价为1+1+13元1)所有的产地、中转地和销地都可以看作产地，也可以看作销地。因此整个问题被当作有11个产地和11个销地的扩大运输问题。2)中转站的产量等于销量。每个中转站的转运量不大于20吨。可以规定四个中转站的产量和销量均为20吨。实际的转运量小于20吨，可以加入一个松弛量Xii，对应的运价为0。(20 Xii)为实际的转运量。3)原来的产地和销地也有转运站的作用，故三个厂产量为27、24、29吨，销量均为20吨，四个销售点的销量为23、26、25、26吨，产量均为20吨。同时引进Xii作为松弛变量。,运筹学 第三章 运输问题,Slide 54,例10：某厂在A、B、C三处设仓库供应点的各零售商，详见下图。图中各边数字为沿该线路运送一单位物资所需的费用（元）。已知A、B、C三仓库内现库存物资数分别为200、170、160单位。点各零售商所需物资数列于下表。且对零售商供应短缺一单位时的罚款也列于表中。应如何确立各仓库对各零售点的分配量，使总的运输费和罚款之和最小。,A,B,C,运筹学 第三章 运输问题,Slide 56,总供给量530，总需求量550。,