《运筹学运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学运输问题.ppt（60页珍藏版）》请在三一办公上搜索。
1、1,第三章 运输问题,运输问题约束条件的系数矩阵具有特殊的结构，有更为简单的求解方法，从而节约大量的计算时间和费用。,2,产地-m个,Ai表示，i=1,2,m；产量 ai,i=1,2,m,表3.1,要求使总运费最小的调运方案。,Cij:-从Ai到Bj运输单位物资的运价,销售地-n个，Bj 表示，j=1,2,n；销售量 bj，j=1,2,n，,3.1、运输问题的数学模型,3,产销平衡运输问题,数学模型 解:假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为:,总产量等于其总销量，即,4,LP问题-mn个变量，m+n个约束条件.单纯形法求解，在每个约束上加入一个人工变量若 m=4，n=5
2、，变量个数就有29个之多，非常复杂。,5,1、基本概念与重要结论系数矩阵特点：（1）元素等于0或1；（2）每列只有两个元素为1，其余都是0；（3）每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。,3.2 表上作业法,6,运输问题的解-代表着一个运输方案变量xij的值-由Ai调运数量为xij的物品给Bj。基变量-m+n-1个，只有m+n-1个约束条件是线性独立的。进一步我们想知道，怎样的 m+n-1个变量会构成一组基变量？,7,8,基本概念 闭回路,顶点-出现在闭回路中的变量闭回路的边-相邻两个变量用一条直线相连,x11、x12、x32、x34、x24、x21 构成一个
3、闭回路。,9,10,定理3.1：m+n-1个变量 构成基变量的充分必要条件是它不包含有任何闭回路。,11,求解运输问题的一种简化方法，实质是单纯形法。（1）找初始基可行解-即在(mn)产销平衡表上给出m+n-1个数字格-不能构成闭回路，且行和等于产量，列和等于销售量；（2）求非基变量检验数-在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求得最优解为止。,2、表上作业法,12,基本思想-就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，
4、直到给出初始方案为止。,（1）确定初始基可行解 方法一：最小元素法,例3.2 某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。,13,表3.5,3,1,14,方案的总运费为 86 元,15,两种特殊情况：、多个元素同时最小，任选一个作基变量、对于最小元素，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n 1
5、）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。,16,单位产品运价如表3.8所示。利用最小元素法，求初始调运方案,例3.3,初始调运方案。如表3.9,17,伏格尔法一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最小运费调运。,方法二 伏格尔法,最小元素法缺点为节省一处的费用，有时造成在其它地方要花多几倍的运费。,18,表3.10,19,6,3,3,1,5,2,2,2,20,目标函数是要求
6、最小化，所以当所有的非基变量检验数全都大于等于 0 时为最优解。求空格检验数,、方法一：闭回路法、方法二：位势法,（2）、最优解的判别,21,、方法一：闭回路法,例,检验数的经济解释：保持产销平衡,检验数=调整方案使运费的改变量(+1)3+(-1)3+(+1)2+(-1)1=1(元),22,所有空格检验数-表3.13,表3.7不是最优解，还需要进一步改进,-1,23,m+n 个未知量 u1,um,v1,vn，由上述基本可行解可构造如下一个方程组：,是一组基可行解，,现在引进,、方法二：位势法,其中cij为单位运价。方程组（3.2）共有m+n 个未知数和m+n-1个方程。(3.2)的解存在且恰有
7、一个自由变量。称u1,um为行位势，v1,vn为列位势。,24,定理3.2 设已给了一组基本可行解，则对每一个非基变量xij 来说，它所对应的检验数为：ij=cij(ui+vj),25,仍以例3.2所给出的初始基可行解表3.7为例：,先令u1=0，然后按ui+vj=cij(i,j)基变量指标集，相继确定ui、vj。,0,10,-5,9,3,-1,2,26,计算所有的空格检验数 ij=cij(ui+vj),(i,j),还有负检验数-未得到最优解，进一步进行改进。,1,2,1,-1,10,12,11=c11(u1+v1)=3(0+2)=1,27,若有两个或两个以上的检验数为负时，一般选择其中最小的
8、负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3.16可知(A2,B4)为调入格（即以它对应的变量 x24 为换入变量）。以此格为出发点，作一闭回路，如表3.17所示。,、基可行解改进的方法闭回路调整法,28,闭回路上（-1）数字格中的最小者。即=min1,3=1 然后按闭回路上的正、负号，加入和减去此值，得到调整方案,(A2,B4)格的调入量,29,再用闭回路法或位势法求表3.18各空格的检验数,检验数都大于等于 0，表3.18为最优解。总运费最小值是 85 元。,30,产销平衡的运输问题必定存在最优解。,那么有唯一最优解还是无穷多个最优解？依据仍然是看非基变量（即空
9、格处）的检验数是否有为0的。若有，则存在无穷多个最优解；否则，只有唯一最优解。,表3.19-例3.2有无穷多个最优解。,31,最优表3.18中以(A1,B1)为调入格,作闭回路(q=min2,3=2，经调整后得到另一个最优解,32,调入量0 2 中的任一实数，这时的解仍为最优解,表3.21不是基可行解线性规划问题可以在顶点取到最优解，也可在非顶点即是边界点上取到最优解,33,转化为产销平衡,3.3、产销不平衡的运输问题及其求解方法,当产大于销时，,34,多余的物资在那一个产地贮存的问题。设 xin+1 是产地 Ai 的贮存量，故有：,产量大于销量,35,将其分别代入，得到：,这是一个产销平衡的
10、运输问题。,36,销大于产,37,设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的运价表如表3.22所示。试求出总的运费最省的化肥调拨方案。,例3.4,38,表3.22 单位运价：万元/万吨,39,表3.24 最优调运方案,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法的计算简单得多，所以在解决实际问题时，人们常常尽可能把某些线性规划问题化为运输问题的数学模型。,40,某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的
11、成本如表3.25所示。又如果生产出来的柴油机当季不交货，每台每季度需存储费、维护费等共0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护等）费用最小的决策。,表3.25,例3.5,41,解：设 xij 表示为第i季度生产的用于第j季度交货的柴油机数。,生产能力限制 x11+x12+x13+x14 25 x22+x23+x24 35 x33+x34 30 x44 10,合同要求 x11=10 x12+x22=15 x13+x23+x33=25 x14+x24+x34+x44=20,42,ai：第 i 季度生产能力bj：第 j 季度的合同供应量则问题可写成：,xij的单台实际
12、成本 cij=该季度单位成本+储存、维护等费用。cij 的具体数值见表3.26。,43,产大于销注意：当 i j 时，xij=0，应令对应的 cij=M，加一个假想的需求季度 V，变成产销平衡,表3.27 产销平衡表与单位运价表,44,表上作业法求解，可得多个最优方案表3.28中列出最优方案之一该厂总生产（储存、维护）费用-773万元。,表3.28 最优调运方案,45,3.4 转运问题,转运问题-运输问题的一个扩充，产销地之间再增加中转点。在转运问题中我们还允许把物品一个产地运往另一个产地或中转点或销地，也允许把物品从一个中转点运往另一个中转点或产地或销地，也允许把物品从一个销地运往另一个中转
13、点或产地。在每一个产地的供应量都有一个限量，而每一个销地的需求量也都有一个限制，任意两点间的单位物品的运价已知，如何使总的运输费最小?,46,例3.5,某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去销售，有关分厂的产量、各销售公司的销量及运价如表329所示，求总的运费最小的调运方案？,这是一个普通的产销平衡运输问题，但是如果假定：,47,（1）每个分厂的物资不一定直接发送到销地，可以从其中几个产地集中一起运；（2）运往各销地的物资可以先运给其中几个销地，再转运给其它销地；（3）除产地、销地外，还有几个中转站，在产地之间、销地之间或产地与销地之间转运。各产地、销地、中转站及相互之间每
14、吨物资的运价如表330所示，问在考虑产销之间直接运输和非直接运输的各种可能方案的情况下，如何将三个分厂的物资运往销售公司，使总的运费最少？,48,表330,（1）由于问题中的所有产地、销地、中转站都可以看成产地，也可以看成销地，因此整个问题可以看成是一个由11个产地和11个销地组成的运输问题；（2）对于扩大的运输问题建立运价表，表中的不可能运输方案的运价用M代替；（3）所有中转站的产量等于销量，也即流入量等于流出量。由于运费最少时不可能出现物资的来回倒运现象，因此每个中转站的运量不会超过20吨，所以可以规定中转站的产量和销量均为20吨，这样就可以得到扩大的产销平衡运输问题及其运价表，如表331
15、。,50,表331,51,利用表上作业法求得最优解如表332,52,3.5 案例分析3.5.1 报刊征订、推广费用的节省问题,（1）问题的提出中华图书进出口总公司的主营业务之一就是中文书刊对国外出口业务，由中文书刊出口部及深圳分公司和上海分公司负责。就中文报刊而言，每年1012月为下一年度报刊订阅的征订期，在此期间，为巩固老订户，发展新订户，要向国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。（2）有关数据由于中文书刊的出口的订户大部分集中在日本、韩国以及香港地区，因此公司要根据订户的分布数量的不同，寄发征订材料的数量也就不同；由于三个部门都同属于中华图书进出口总公司，为了避
16、免内部恶性竞争，三个部门所寄宣传材料的数量由总公司统一安排。一般情况下，这些材料无论由三家中那一家寄出，征收用户的效果大致相同；同时无论读者向那个部门订阅，为总公司创造的利润大致相同。但由于各部门与三个用户的距离不同，邮寄方式及人工费用不同，导致从各部门寄往各地的费用也不同。,53,表333 三个部门寄出的征订材料数量,表334 寄往三个地区的征订材料数量,表335 各部门寄往各地的费用,54,要求作出一个公司整体的中文书刊材料的邮递方案，使得公司总的邮运费最小。,解：记A1，A2 和A3 分别表示“中文书刊出口部”、“深圳分公司”和“上海分公司”。B1、B2 和B3 分别表示“日本”、“香港
17、”和“韩国”，转化为一个产销平衡运输问题，表336,55,表337,表中数字表示Ai 邮寄到Bi 的邮件数量。,56,3.5.2 宏达电子的货物转运问题,宏达电子仪器公司，其生产线分别在大连、广州，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。在任意分厂的生产线生产的产品可能被运往公司设在长沙或天津的地区仓库中的任意一个。从这些仓库，公司向南京、西安、济南和上海的零售商发货。这些城市间的每台仪器的运费我们标在两个城市间上的弧上，单位为万元；工厂和零售商的供给与需求在图的左侧和右侧标明如图3.1所示。问应该如何调运仪器，使总的运费最低,57,图3.1 宏达电子仪器公司转运网
18、络图,58,解：该转运问题可以转化为一个运输问题。（1）由于问题中的所有产地、中转站都可以看成产地，而中转站与销地都可以看成销地，因此整个问题可以看成是一个由4个产地和6个销地组成的运输问题；（2）对于扩大的运输问题建立运价表，表中的不可能运输方案的运价用M代替；（3）所有中转站的产量等于销量，也即流入量等于流出量。由于运费最少时不可能出现物资的来回倒运现象，因此每个中转站的运量不会超过1000台，所以可以规定中转站的产量和销量均为1000台，扩大的产销平衡运输问题及其运价表，如表338所示,59,表338,60,利用表上作业法求得最优解如表339所示,总运费为5200万元。,550,200,350,400,300,150,50,
