第八章 运输问题课件.ppt

一、运输问题模型及其求解思路,1、问题的提出：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？,一、运输问题模型及其求解思路,运价表,销量和产量和产销平衡,一、运输问题模型及其求解思路,为建立模型，设 xij 为从产地Ai运往销地Bj的运输量，得到下表：,运量表,一、运输问题模型及其求解思路,据题意，可建立线性规划模型：Min f = 6x11+4x12+6x13+6x21+5x22+5x23s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0(i=1,2；j=1,2,3）,一、运输问题模型及其求解思路,2、产销平衡运输问题模型的特点从模型的建立可知：列数为2（产地数）3（销地数）6；行数为2（产地数）+3（销地数）5；再观察模型的系数矩阵：,一、运输问题模型及其求解思路,前2行之和后3行之和,一、运输问题模型及其求解思路,对于产销平衡的运输问题，若产地为m个，销地为n个，则变量个数为mn个，线性无关的约束条件个数为m+n-1，故基本解中的基变量个数为m+n-1。,一、运输问题模型及其求解思路,3、运输问题求解思路表上作业法由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。,一、运输问题模型及其求解思路,我们关心的量均在运价表和运量表中，故将两表和为作业表：,一、运输问题模型及其求解思路,表上作业法的总体思路和单纯形法类似：,每个步骤都充分利用运输表的特点,一、运输问题模型及其求解思路,例：某食品公司下属的A1、A2、A3 ，3个厂生产方便食品，要运输到B1、B2、B3、B4 ，4个销售点，数据如下表，求最优运输方案。,二、确定初始基本可行解,1、西北（左上）角法每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,3,4,2,2,3,6,二、确定初始基本可行解,这样得到的初始基本可行解为：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6，其余均为0。对应的总运费为：33+411+29+22+310+65135,二、确定初始基本可行解,2、最小元素法每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,3,4,3,1,6,3,二、确定初始基本可行解,用最小元素法求出的初始基本可行解为： x21 =3, x22 =1, x13 =4, x32 =6, x34=3, x14 =3,其余均为0。对应的总运费为：31+12+43+64+35+31086,二、确定初始基本可行解,为保证基变量的个数有m+n-1个，注意：1、每次填完数，只能划去一行或一列，只有最后一个格子例外。2、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上0。（退化的基本可行解）,二、确定初始基本可行解,3,5,3,0,6,3,二、确定初始基本可行解,3,4,0,1,6,3,三、最优性检验,检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。下面介绍两种计算检验数的方法：,三、最优性检验,1、闭回路法闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转90o (当然也可以不改变方向）继续前进。这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。,三、最优性检验,每一个非基变量都有唯一的闭回路,三、最优性检验,观察x24的闭回路：若让第一个顶点非基变量x24的取值变为1，为了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点+1，偶数顶点-1。上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ，这就说明原方案还不是最优方案，需要进行调整。,三、最优性检验,若让x111，则总运费变化：33+211 。,三、最优性检验,如果规定作为起始顶点的非基变量xij为第 1 个顶点，其闭回路上的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有该非基变量的检验数：ij = (闭回路上的奇数顶点运价之和) - (闭回路上的偶数顶点运价之和)最优标准：所有检验数0,三、最优性检验,检验数计算如下表：,（1）,（2）,（1）,（-1）,（10）,（12）,三、最优性检验,2、位势法闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。位势法：设产地Ai对应的位势量为ui ，销地Bj对应的位势量为vj， 检验数ij =cij ui-vj。,三、最优性检验,三、最优性检验,根据基变量xij 的检验数ij =0 ，对应基变量的运价cij可以分解为ui 和vj，即cij =ui+vj 。因为位势量ui ,vj的总数为m + n 个，而限定方程只有m+n-1个（基变量个数），所以位势量（ ui ,vj ）有无穷多组解，其中总有一个自由变量。故可以任意取一个位势量赋以定值，从而确定其它位势量的值，一般取u1 0。,三、最优性检验,10,3,9,2,vj,20,6,5,6,3,销量bj,-5,9,5 3,10,4 6,7,A3,-1,4,8,2 1,9,1 3,A2,0,7,10 3,3 4,11,3,A1,ui,产量ai,B4,B3,B2,B1,（1）,（2）,（1）,（-1）,（10）,（12）,检验数计算总结,1、闭回路法计算式：ij = (闭回路上的奇数顶点运价之和) - (闭回路上的偶数顶点运价之和)2、位势法计算式：ij = cij - ui vj,四、方案调整,最小检验数原则，确定进基变量,最小偶点原则，确定出基变量和调整量,+1,-1,+1,-1,四、方案调整,得到新的基变量：x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新计算检验数。,（0）,（2）,（2）,（1）,（9）,（12）,四、方案调整,经过一次基变换，所有ij 0，已得到最优解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它为0。最优值：f* =35+102+13+81+46+53 = 85,四、方案调整,闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者 rk，那么 xrk 作为进基变量；（使总运费尽快减少）2、出基变量的确定：在进基变量xrk 的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）,四、方案调整,即求=Minxij闭回路上的偶数顶点的xij= xpq。那么确定xpq为出基变量，为调整量；3、换基调整：对闭回路的奇数顶点运量调整为：xij+，对各偶数顶点运量调整为：xij-，特别 xpq-=0，xpq变为非基变量。重复以上步骤，直到所有检验数均非负，即得到最优解。,练习题已知如下运价表，用表上作业法求解：,初始解对应目标值为33+41+42+44+8361,3,4,2,1,0,3,0,3,4,1,3,3,4,(3),(2),(3),(0),(-1),(-2),4,0,3,0,2,4,0,3,4,1,3,3,2,(3),(2),(3),(2),(1),(2),已达到最优，最优目标值为44+42+44+5355,五、运输问题的几种特殊情况,1、多个最优方案的情况：若最优表中有非基变量的检验数为0，则为多个最优方案的情况。这种情况下，可将检验数为0的非基变量作为进基变量，即可得到另一个最优方案。,五、运输问题的几种特殊情况,如上例中的最优方案就不唯一：,（0）,（2）,（2）,（1）,（9）,（12）,检验数为0者进基,最小偶点为出基变量和调整量,+2,-2,-2,+2,五、运输问题的几种特殊情况,得到另一个最优方案：x11 = 2, x13 = 5, x21 = 1, x24 = 3, x32 = 6, x34 = 3, 其余 xij = 0；最优值仍然为 f* = 85,五、运输问题的几种特殊情况,2、无解情况：当某个产地Ai不能向某个销地Bj供应产品时，设相应的运费为M（类似于大M法），然后求最优解。在最优解中，若相应xij的取值为0 ，则此最优解为原问题的最优解；若xij的取值不为0，则原问题无解。,五、运输问题的几种特殊情况,3、退化情况一个或多个基变量等于0。思考：运输问题是否存在无界解情况？,六、运输问题的应用,1、产销不平衡的运输问题例：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？,销量产量,六、运输问题的应用,六、运输问题的应用,100,x24,x14,库存量,200,150,150,销量,300,x23,x22,x21,A2,300,x13,x12,x11,A1,产量,B3,B2,B1,多余的产量100作为库存， A1和A2各库存多少待定。,六、运输问题的应用,100,0,0,库存量,200,150,150,销量,300,5,5,6,A2,300,6,4,6,A1,产量,B3,B2,B1,在运价表中也增加库存的相应列：库存量运价为0。,六、运输问题的应用,转化为产销平衡的运输问题后同样求解：,100,150,50,200,100,六、运输问题的应用,结论：对于产量大于销量的运输问题，在运输作业表上增加一列，其销量等于总产量和总销量之差，运价均为0。可以将增加的一列理解为假想销地，其销量即库存量。思考：对于销量大于产量的问题怎么办？,销量产量,六、运输问题的应用,六、运输问题的应用,办法：增加一行表示缺货量。,100,0,0,0,缺货量,200,150,250,销量,300,5,5,6,A2,200,6,4,6,A1,产量,B3,B2,B1,六、运输问题的应用,实际应用中，可能出现的其他情况：（1）某些运输线路上的运输能力有限制；如范例中，A1产地产量为7，B4销地销量为6，从A1到B4线路上最大运输能力为4。处理办法：直接在约束条件中增加该约束，即保证X14的取值不超过产量、销量和线路最大运输能力。,六、运输问题的应用,（2）销量大于产量，但某些销地的销量必须完全满足，不能有缺货；处理办法：对缺货量到该销地的运价定为一个充分大的值M。（类似于大M法）,六、运输问题的应用,如表中B2销量不能短缺：,100,0,M,0,缺货量,200,150,250,销量,300,5,5,6,A2,200,6,4,6,A1,产量,B3,B2,B1,六、运输问题的应用,（3）销量大于产量时，若某地的销量可以有一定量缺货，但供应量必须不小于某个值p；处理办法：将该销地分解为两个销地Bj1和Bj2， Bj1对应必须满足的销量p， Bj2对应缺货的销量bj-p。其中，缺货量到Bj1的运价为“大M”。,六、运输问题的应用,如表中B2销量不能低于100：,100,0,0,缺货量,200,150,250,销量,300,5,5,6,A2,200,6,4,6,A1,产量,B3,B2,B1,B21,B22,100,50,4,4,5,5,M,0,六、运输问题的应用,例1：石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需大于求，经院研究决定一区供应量可减少0300t，二区必须满足需求量，三区供应量不少于1700t，试求总费用为最低的调运方案。,六、运输问题的应用,解：根据题意，作出产销平衡的运价表，取M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。,六、运输问题的应用,例2：设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。,六、运输问题的应用,解：根据题意，作出产销平衡的运价表,六、运输问题的应用,2、生产与储存问题例1：某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。,六、运输问题的应用,六、运输问题的应用,解： 设 xij为第 i 季度生产的第 j季度交货的柴油机数目，那么应满足：,交货： 生产：x11 = 10 x11 + x12 + x13 + x14 25x12 + x22 = 15 x22 + x23 + x24 35x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10,六、运输问题的应用,把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：,例2：光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：,六、运输问题的应用,已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在78月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排16月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？,六、运输问题的应用,解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地。1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；2）上年末库存103台，只有仓储费和运输费，把它列为的0行；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）1-6表示1-6月份正常生产情况， 1-6表示1-6月份加班生产情况。,六、运输问题的应用,产销平衡的运价表：,六、运输问题的应用,3、转运问题原运输问题上增加若干转运站。运输方式有：产地 转运站、转运站 销地、产地 产地、产地 销地、销地 转运站、销地 产地等。,例：某公司有A1、 A2、 A3三个分厂生产某种物质，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表：,六、运输问题的应用,假设：1、每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。运价如下表，试求总费用为最少的调运方案。,六、运输问题的应用,解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地；2、不可能方案的运费取作M，自身对自身的运费为0；3、产量及销量可定为：中转站 产量和销量均为20，产地 产量为原产量+20，销量为20销地 产量为20，销量为原销量+20。其中，20为各点可能变化的最大流量；4、对于最优方案，其中 xii为自身对自身的运量，实际上不进行运作。,六、运输问题的应用,可得到扩大的产销平衡运输问题表：,