运筹学运输问题课件

《运筹学运输问题课件》由会员分享，可在线阅读，更多相关《运筹学运输问题课件（60页珍藏版）》请在装配图网上搜索。

1、运筹学运输问题1第三章第三章 运输问题运输问题运输问题约束条件的系数矩阵具有特殊的结构，有更为简单的求解方法，从而节约大量的计算时间和费用。运筹学运输问题2 产地产地-m个个,Ai表示，表示，i=1,2,m；产量产量 ai ,i=1,2,m 销地销地产地产地B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量销量b1b2bn表表3.1要求使总运费最小的调运方案。要求使总运费最小的调运方案。Cij:-从从Ai到到Bj运输单位物资的运价运输单位物资的运价 销售地销售地-n个，个，Bj 表示，表示，j=1,2,n；销售量销售量 bj，j=1,2,n，

2、3.1、运输问题的数学模型、运输问题的数学模型运筹学运输问题3产销平衡运输问题产销平衡运输问题数学模型数学模型 解解:假设假设 xij 表示从表示从Ai到到 Bj 的运量的运量,则所求的则所求的数学模型为数学模型为:njjmiiba11总产量等于其总销量，即总产量等于其总销量，即njmixmiaxnjbxxcZijinjijjmiijminjijij,2,1;,2,10,2,1,2,1min1111运筹学运输问题4LP问题-mn个变量，m+n个约束条件.单纯形法求解，在每个约束上加入一个人工变量若 m=4，n=5，变量个数就有29个之多，非常复杂。njmixmiaxnjbxxcZijinjij

3、jmiijminjijij,2,1;,2,10,2,1,2,1min1111运筹学运输问题5 1、基本概念与重要结论基本概念与重要结论系数矩阵特点：系数矩阵特点：（1）元素等于）元素等于0或或1；（2）每列只有两个元素为）每列只有两个元素为1，其余都是，其余都是0；（3）每一个变量，在前）每一个变量，在前m个约束方程中只出现一个约束方程中只出现一次，在后次，在后n个约束方程中也只出现一次。个约束方程中也只出现一次。3.2 表上作业法表上作业法101010010101110000001100000011,1221111Axxxxxxmnmnnmijji 1nijij 1xbj1,2,nxai1,

4、2,m 运筹学运输问题6运输问题的解-代表着一个运输方案变量xij的值-由Ai调运数量为xij的物品给Bj。基变量-m+n-1个，只有m+n-1个约束条件是线性独立的。进一步我们想知道，怎样的 m+n-1个变量会构成一组基变量？运筹学运输问题701111)1(11111111111列展开按第mD101010010101110000001100000011,1221111Axxxxxxmnmnn运筹学运输问题8基本概念 闭回路),1,1,1slnjjjls且互不相同凡是能排成凡是能排成,(,1132222111sjijijijijijiiixxxxxxsss互不相同，且,1mik,1sk形成的变

5、量的集合形成的变量的集合顶点顶点-出现在闭回路中的变量闭回路的边闭回路的边-相邻两个变量用一条直线相连例例3.1 设 m=3，n=4，表3.2x34x32A3x24x21A2x12x11A1B4B3B2B1 销地产地x11、x12、x32、x34、x24、x21 构成一个闭回路。构成一个闭回路。运筹学运输问题9x34x32A3A2x14x12A1B4B3B2B1 销地产地运筹学运输问题10定理3.1：m+n-1个变量 构成基变量的充分必要条件是它不包含有任何闭回路。)1(,2211nmsxxxssjijiji运筹学运输问题11求解运输问题的一种简化方法，实质是单纯形法。（1）找初始基可行解-即

6、在(mn)产销平衡表上给出m+n-1个数字格-不能构成闭回路，且行和等于产量，列和等于销售量；（2）求非基变量检验数-在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求得最优解为止。2、表上作业法表上作业法运筹学运输问题12基本思想-就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。（1）确定初始基可行解确定初始基可行解 方法一：最小元素法例3.2 某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂

7、的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。运筹学运输问题13表3.5 销地产地B1B2B3B4产量A13113107A219284A3741059销量365631运筹学运输问题14方案的总运费为方案的总运费为 86 元元 运价表运价表B1B2B3B4产量产量A13113107A219284A3741059销量销量3656表表3.7B1B2B3B4产量产量A1437A2314A3639销量销量3656运筹学运输问题15两种特殊情况：、多个元素同时最小，任选一个作基变量1、对于最小元素，发现

8、该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n 1）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。运筹学运输问题16单位产品运价如表3.8所示。利用最小元素法，求初始调运方案 销地产地B1B2B3B4产量A1531049A216964A32010577销量3584例3.3表表3.9B1B2B3B4产量产量A15049A2314A377销量销量3584初始调运方案。如表3.9运筹学

9、运输问题17伏格尔法伏格尔法一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最小运费调运。方法二 伏格尔法最小元素法缺点为节省一处的费用，有时造成在其它地方要花多几倍的运费。运筹学运输问题18 销地产地B1B2B3B4行差额产量A131131007A2192814A37410519列差额2513销量3656表3.10运筹学运输问题19 销地产地B1B2B3B4行差额产量A131131007A2192814A37410519列差额2513销量36566337615222运筹学运输问题20

10、目标函数是要求最小化，所以当所有的非基变量检验数全都大于等于 0 时为最优解。求空格检验数、方法一：闭回路法、方法二：位势法（2）、）、最优解的判别最优解的判别运筹学运输问题21表表3.12/3.7B1B2B3B4产量产量A1437A2314A3639销量销量3656、方法一：闭回路法例3132检验数的经济解释：保持产销平衡 检验数=调整方案使运费的改变量(+1)3+(-1)3+(+1)2+(-1)1=1(元)运筹学运输问题22所有空格检验数-表3.13空空 格格闭闭 回回 路路检验数检验数(A1,B1)(1,1)(1,3)(2,3)(2,1)(1,1)1(A1,B2)(1,2)(1,4)(3

11、,4)(3,2)(1,2)2(A2,B2)(2,2)(2,3)(1,3)(1,4)(3,4)(3,2)(2,2)1(A2,B4)(2,4)(2,3)(3,3)(1,4)(2,4)-1(A3,B1)(3,1)(3,4)(1,4)(1,3)(2,3)(2,1)(3,1)10(A3,B3)(3,3)(3,4)(1,4)(1,3)(3,3)12表3.7不是最优解，还需要进一步改进表表3.7/3.5B1B2B3B4产量产量A1437A2314A3639销量销量3656313271011910845-1运筹学运输问题231 1,(1)s si ji jxxsmn设m+n 个未知量 u1,um,v1,vn，

12、由上述基本可行解可构造如下一个方程组：是一组基可行解，现在引进ssssjijijijijijicvucvucvu22221111、方法二：位势法其中cij为单位运价。方程组（3.2）共有m+n 个未知数和m+n-1个方程。(3.2)的解存在且恰有一个自由变量。称u1,um为行位势，v1,vn为列位势。运筹学运输问题24定理3.2 设已给了一组基本可行解，则对每一个非基变量xij 来说，它所对应的检验数为：ij=cij (ui+vj)运筹学运输问题25表表3.7/3.14B1B2B3B4行位势uiA1A2 A3列位势 vj1321045仍以例3.2所给出的初始基可行解表3.7为例：先令u1=0，

13、然后按ui+vj=cij(i,j)基变量指标集，相继确定ui、vj。010-593-12运筹学运输问题26计算所有的空格检验数 ij=cij (ui+vj),(i,j)表表3.16B1B2B3B4行位势uiA1000A200-1A300-5列位势 vj29310313271011910845还有负检验数-未得到最优解，进一步进行改进。121-1101211=c11 (u1+v1)=3 (0+2)=1运筹学运输问题27若有两个或两个以上的检验数为负时，一般选择其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3.16可知(A2,B4)为调入格（即以它对应的变量 x2

14、4 为换入变量）。以此格为出发点，作一闭回路，如表3.17所示。、基可行解改进的方法闭回路调整法运筹学运输问题28表表3.17B1B2B3B4产量产量A1437A2314A3639销量销量3656闭回路上（-1）数字格中的最小者。即 =min1,3=1 然后按闭回路上的正、负号，加入和减去此值，得到调整方案(+1)(-1)(-1)(+1)表表3.18B1B2B3B4产量产量A1527A23 14A3639销量销量3656(A2,B4)格的调入量 运筹学运输问题29表表3.18B1B2B3B4产量产量A1527A23 14A3639销量销量3656 再用闭回路法或位势法求表表3.18各空格的检验

15、数检验数都大于等于 0，表3.18为最优解。总运费最小值是 85 元。检验数表表3.19B1B2B3B4A102A221A3912运筹学运输问题30产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多个最优解？依据仍然是看非基变量（即空格处）的检验数是否有为0的。若有，则存在无穷多个最优解；否则，只有唯一最优解。表3.19-例3.2有无穷多个最优解。运筹学运输问题31表表3.18B1B2B3B4产量产量A1527A23 14A3639销量销量3656最优表3.18中以(A1,B1)为调入格,作闭回路(q=min2,3=2，经调整后得到另一个最优解表表3.20B1B2B3B4产量产量A1

16、 257A21 34A3639销量销量3656运筹学运输问题32表表3.18B1B2B3B4产量产量A1527A23 14A3639销量销量3656表表3.21B1B2B3B4产量产量A1 52-7A23-1+4A3639销量销量3656调入量0 j 时，xij=0，应令对应的 cij=M，加一个假想的需求季度 V，变成产销平衡 销售生产IIIIIIIVV产 量I10.810.9511.1011.25025IIM11.1011.2511.40035IIIMM11.0011.15030IVMMM11.30010销 量1015252030表3.27 产销平衡表与单位运价表 交货生产IIIIIIIV

17、销量I10.810.9511.1011.2525II11.1011.2511.4035III11.0011.1530IV11.3010产量10152520运筹学运输问题44表上作业法求解，可得多个最优方案表3.28中列出最优方案之一该厂总生产（储存、维护）费用-773万元。销售生产IIIIIIIVV产 量I1015025II53035III201030IV1010销 量1015252030表3.28 最优调运方案运筹学运输问题453.4 转运问题转运问题 转运问题-运输问题的一个扩充，产销地之间再增加中转点。在转运问题中我们还允许把物品一个产地运往另一个产地或中转点或销地，也允许把物品从一个中

18、转点运往另一个中转点或产地或销地，也允许把物品从一个销地运往另一个中转点或产地。在每一个产地的供应量都有一个限量，而每一个销地的需求量也都有一个限制，任意两点间的单位物品的运价已知，如何使总的运输费最小?运筹学运输问题46例例3.53.5 某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去销售，有关分厂的产量、各销售公司的销量及运价如表329所示，求总的运费最小的调运方案？B1B2B3B4产 量A13113107A219284A3741059销 量3656这是一个普通的产销平衡运输问题，但是如果假定：运筹学运输问题47（1）每个分厂的物资不一定直接发送到销地，可以从其中几个产地集中一起

19、运；（2）运往各销地的物资可以先运给其中几个销地，再转运给其它销地；（3）除产地、销地外，还有几个中转站，在产地之间、销地之间或产地与销地之间转运。各产地、销地、中转站及相互之间每吨物资的运价如表330所示，问在考虑产销之间直接运输和非直接运输的各种可能方案的情况下，如何将三个分厂的物资运往销售公司，使总的运费最少？运筹学运输问题48产地中转站销地A1A2A3T1T2T3T4B1B2B3B4产地A1132143311310A213521928A3312374105中转站T12311322846T2151124527T3423121824T4323212126销地B13172411142B211

20、94858121B332104222423B410856746213表330运筹学运输问题49（1）由于问题中的所有产地、销地、中转站都可以看成产地，也可以看成销地，因此整个问题可以看成是一个由11个产地和11个销地组成的运输问题；（2）对于扩大的运输问题建立运价表，表中的不可能运输方案的运价用M代替；（3）所有中转站的产量等于销量，也即流入量等于流出量。由于运费最少时不可能出现物资的来回倒运现象，因此每个中转站的运量不会超过20吨，所以可以规定中转站的产量和销量均为20吨，这样就可以得到扩大的产销平衡运输问题及其运价表，如表331。运筹学运输问题50表331A1A2A3T1T2T3T4B1B

21、2B3B4产量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1012452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量2020202020202023262526240运筹学运输问题51利用表上作业法求得最优解如表332A1A2A3T1T2T3T4B1B2B3B4产量A120727A2136524A3203629T117320T22020T32020T42

22、020B114620B22020B32020B42020销量2020202020202023262526240运筹学运输问题523.5 案例分析案例分析3.5.1 报刊征订、推广费用的节省问题报刊征订、推广费用的节省问题（1）问题的提出中华图书进出口总公司的主营业务之一就是中文书刊对国外出口业务，由中文书刊出口部及深圳分公司和上海分公司负责。就中文报刊而言，每年1012月为下一年度报刊订阅的征订期，在此期间，为巩固老订户，发展新订户，要向国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。（2）有关数据由于中文书刊的出口的订户大部分集中在日本、韩国以及香港地区，因此公司要根据订户

23、的分布数量的不同，寄发征订材料的数量也就不同；由于三个部门都同属于中华图书进出口总公司，为了避免内部恶性竞争，三个部门所寄宣传材料的数量由总公司统一安排。一般情况下，这些材料无论由三家中那一家寄出，征收用户的效果大致相同；同时无论读者向那个部门订阅，为总公司创造的利润大致相同。但由于各部门与三个用户的距离不同，邮寄方式及人工费用不同，导致从各部门寄往各地的费用也不同。运筹学运输问题53表333 三个部门寄出的征订材料数量部门份数/册中文书刊出口部15000深圳分公司7500上海分公司7500总计30000表334 寄往三个地区的征订材料数量国家和地区份数/册日本15000中国香港特别行政区10

24、000韩国5000总计30000表335 各部门寄往各地的费用日本中国香港特别行政区韩国中文书刊出口部10.2079深圳分公司12.50414上海分公司687.50运筹学运输问题54要求作出一个公司整体的中文书刊材料的邮递方案，使得公司总的邮运费最小。B1B2B3A110.207915000A212.504147500A3687.5750015000100005000解：记A1，A2 和A3 分别表示“中文书刊出口部”、“深圳分公司”和“上海分公司”。B1、B2 和B3 分别表示“日本”、“香港”和“韩国”，转化为一个产销平衡运输问题，表336运筹学运输问题55表337B1B2B3A17500

25、25005000A2075000A3750000表中数字表示Ai 邮寄到Bi 的邮件数量。运筹学运输问题563.5.2 宏达电子的货物转运问题宏达电子的货物转运问题 宏达电子仪器公司，其生产线分别在大连、广州，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。在任意分厂的生产线生产的产品可能被运往公司设在长沙或天津的地区仓库中的任意一个。从这些仓库，公司向南京、西安、济南和上海的零售商发货。这些城市间的每台仪器的运费我们标在两个城市间上的弧上，单位为万元；工厂和零售商的供给与需求在图的左侧和右侧标明如图3.1所示。问应该如何调运仪器，使总的运费最低 运筹学运输问题57零售商零

26、售商需求量需求量 200 150 350 300 40060025644636233广州广州大连大连1天津天津长沙长沙南京南京西安西安济南济南 上海上海供应量供应量工厂工厂仓库仓库图3.1 宏达电子仪器公司转运网络图 运筹学运输问题58解：该转运问题可以转化为一个运输问题。（1）由于问题中的所有产地、中转站都可以看成产地，而中转站与销地都可以看成销地，因此整个问题可以看成是一个由4个产地和6个销地组成的运输问题；（2）对于扩大的运输问题建立运价表，表中的不可能运输方案的运价用M代替；（3）所有中转站的产量等于销量，也即流入量等于流出量。由于运费最少时不可能出现物资的来回倒运现象，因此每个中转站

27、的运量不会超过1000台，所以可以规定中转站的产量和销量均为1000台，扩大的产销平衡运输问题及其运价表，如表338所示运筹学运输问题59长沙天津南京西安济南上海产量广州23MMMM600大连31MMMM400长沙0M26361000天津M044651000销量10001000200150350300零售商零售商 200 150 350 300 40060025644636233广州广州大连大连1天津天津长沙长沙南京南京西安西安济南济南 上海上海工厂工厂仓库仓库表338运筹学运输问题60利用表上作业法求得最优解如表339所示长沙天津南京西安济南上海产量广州55050600大连400400长沙4502003501000天津5501503001000销量10001000200150350300总运费为5200万元。200 150 350 300 40060025644636233广州广州大连大连1天津天津长沙长沙南京南京西安西安济南济南 上海上海55020035040030015050