《运筹学课件第三章运输问题.doc》由会员分享，可在线阅读，更多相关《运筹学课件第三章运输问题.doc（14页珍藏版）》请在三一文库上搜索。
1、第三章运输问题一、学习目的与要求1、掌握表上作业法及其在产销平衡运输问题求解中的应用2、掌握产销不平衡运输问题求解方法二、课时 6学时第一节 运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况：设某种物品有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，问怎样调运这些物品才能使总运费最小？为直观清楚起见，列出运输表：销地产地B1B2Bn产量A1c11c12c1na1x11x12x1nA2c21c22c2na2
2、x21x22x2nc11c12c1nx11x12x1nAmcm1cm2cmnamxm1Xm2xmn销量b1b2bn表中xij为由产地Ai到销地Bj的物品数量，cij表示产地Ai到销地Bj的单位运价。如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。产销平衡运输问题的数学模型如下：这就是运输问题的数学模型，它包含mn个变量，(n十m)个约束方程其系数矩阵的结构比较松散，且特殊。二、运输问题数学模型的特点1、运输问题有有限最优解，即必有最优基本可行解2、运输问题约束条件的系数矩阵A的秩为(m+n-1)该系数矩陈中对应于变量xij的系数向量pij，
3、其分量中除第i个和第m十j个为1以外，其余的都为零即 Aij(0110)=ei+em+j 对产销平衡的运输问题具有以下特点：(1)约束条件系数矩阵的元素等于0或1(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。此外，对于产销平衡问题，还有以下特点(3)所有结构约束条件都是等式约束(4)各产地产量之和等于各销地销量之和第二节 用表上作业法求解运输问题解题步骤第1步：确定初始基本可行解。第2步：最优性判别，若最优准则ij0，则当前解最优，计算停止，否则转第3步。第3步：取一个检验数最小的非基变量做进基变量。第4步：调整当前基本
4、可行解，转第2步一、确定初始基本可行解（初始调运方案）以实例介绍：例 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售，各工厂的生产量、各销点的销售量（假定产位均为t）以及各工厂到各销售点的单位运价（元/t）于下表中，要求研究产品如何调运才能使总运费最小？ 销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214A最小元素法销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量8141214总运费（目标函数）：这个解满足约束条件，其非零变量的个数为6（等于m+n-1=3+4
5、-1=6）。B 西北角法销地产地B1B2B3B4产量A14124111688A2210391064A38511622814销量8141214总运费（目标函数）：这个解满足约束条件，其非零变量的个数为6（等于m+n-1=3+4-1=6）。C 沃格尔（Vogel）法销地产地B1B2B3B4 产量行罚数12345A14124111600071124A221039101116682A3851162212148销量814121448列罚数125132213321241252总运费（目标函数）：二、解的最优性检验1、闭回路法销地产地B1B2B3B4产量A141241116106A2210391082A38
6、511622148销量8141214检验数表销地产地B1B2B3B4产量A112A21-1A31012销量由于，故知解不是最优解。2、对偶变量法（也称位势法）对产销平衡问题，若用分别表示前m个约束条件与后n个约束条件的对偶变量，即有对偶变量这时对偶问题的对偶规划写成由上一章知道，线性规划问题变量xj的检验数可表示为由此可写出运输问题某变量xij的检验数如下：现设我们已得到解到了运输问题的一个基可行解，其基变量是由于基变量的检验数等于零，故对这组基变量可写出方程组这个方程组有m+n-1个方程。解以上方程组，可得解（上方程组解不唯一），此方程组解称为位势。由上章知当每个达到最优解。 例 用位势法对
7、上例最小元素法有的解作最优性检验。销地产地B1B2B3B4产量uiA141241116u1106A22103910u282A38511622u3148销量814121448vjv1v2v3v4解：先建立方程组令得方程组的解：计算检验数销地产地B1B2B3B4产量uiA1412411161A221039100A38511622-4销量814121448vj29310由于240，故知解不是最优解。三、解的改进（用闭回路法调整当前基可行解）解的改进步骤：（1）以xij为换入变量，找出运输表中的闭回路；（2）对顶点进行编号；（3）确定换出变量：在闭回路上的所有偶数顶点中找出运输量量小的顶点，以该格中的
8、变量为换出变量；（4）以换出变量值为奇数顶点处的运输量增加值，得新的运输方案；（5）检验新的方案是否为最优，如否则重复以上步骤。例：对上例进行改进求解。销地产地B1B2B3B4产量uiA1412411162106A221039100820A38511622-3148销量814121448vj2829目标函数值为244令得方程组的解：销地产地B1B2B3B4产量uiA14124111620200A2210391000210A38511622-390120销量814121448vj2829因此此方案为最优方案。四、表上作业法计算中的几个问题1、某个基本可行解有几个非基变量的检验数为负若运输问题的某
9、个基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。2、无穷多个最优解当迭代到运输问题的最优解时，如果有某非基变量的检验数0，则说明该运输问题有无穷多最优解。（如上例，为得到另一个最优解，只需让ij0的非基变量进基）3、退化问题当运输问题某部分产地的产量和与另一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的，为了使表上作业法的迭代工作进行下去，退化解应在同时划去的一行或一列中的某个空格中填入数字0，表示这
10、个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。b.在用闭回路法调整当前基本可行解时，调整量的取值应为minxij/( i,j )为闭回路上所有偶数号格点。这时可能出现有两个（或以上）偶数号格点的xij都相等且都为极小值，只能取其中一个为离基格，其余的仍作为基格，而在作运输量调整时，运输量与相等的那些偶数号格点的xij都将调整为0，因此得到的也是一个退化了的基可行解。第三节运输问题的进一步讨论一、产销不平衡的运输问题1、如果总产量大于总销量，即此时运输问题的数学模型为为借助产销平衡时表上作业法求解，可增加一个假想销地Bn+1，由于实际上它不存在，因而由产地Ai（i
11、=1,2,m）调运到这个假想销地的物品数量xi,n+1（相当于松驰变量），实际上是就地存贮在Ai的物品数量。就地存贮的物品数量不经运输，故可令其运价ci,n+1=0（i=1,2,m）。 若令假想销地的销量为bn+1，且 则模型变为运输表销地产地B1B2BnBn+1产量A1c11c12c1n0a1x11x12x1nA2c21c22c2n0a2x21x22x2nc11c12c1n0x11x12x1nAmcm1cm2cmn0amxm1Xm2xmn销量b1b2bnbn+12、总销量大于总产量可假想增加一个产地Am+1，它的产量等于由于这个产地并不存在，求出由它发往各销地的物品数量xm+1,j（j=1,
12、2,n），实际上各销地所需物品的欠缺额，显然有cm+1,j=0（j=1,2,n）。因此数学模型为例 某市有三个造纸厂A1,A2,A3,其纸产量分别为8，5，9个单位，有4个集中用户B1,B2,B3,B4,其需用量为4，3，5，6个单位，由各厂到各用户的单位运价如表所示，试确定总运费最小的调运方案。 销地产地B1B2B3B4产量A1312348A2112595A367159销量4356解略:最优方案如下销地产地B1B2B3B4产量A131234844A21125953A36715952销量4356Min z= 49二、有转运的运输问题假定某一产品有m个产地A1,A2,Am和n个销地B1,B2,B
13、n，都可作为中间站使用，从而发送物品的地点和接收物品的地点都有m+n个。这样一来，我们就得到一个扩大了的运输问题。令ai：表示第 i 个产地的产量（净供应量）；bj：表示第 j 个销地的销量（净需要量）；xij：表示第 i 个发送地运到第 j 个接收地的物品数量；cij：表示第 i 个发送地运到第 j 个接收地的单位运价；ci：表示第 i 个地点转运单位物品的费用。若将产地与销地统一编号，并把产地排在前，销地排在后，则有假定为产销平衡问题，即有运输表：销地产地产地销地发送量产地销地接收量运价表：销地产地产地销地发送量产地销地接收量例：如下图示出了一个运输系统，它包括两个产地、两个销地及一个中转
14、站，各产地产量和各销地销量用相应节点处箭线旁的数字表示，节点连线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。解：销地产地产地转运销地发送量12345产地1-4532M6050(50)10(10)25-12M49050(50)(20)2020(20)转运332-3555050(30)(20)销地42M5-365050(50)5M456-55050(50)销量5050508070用最小元素法得初始运输方案，最经过2次迭代得最优解,总运费300。第四节 应用问题举例由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多所以在解决实际问题时，人们常常尽可能把
15、某些线性规划的问题化为运输问题的数学模型下面介绍几个典型的例子例1 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机已知该厂各季度的生产能力及生产每台柴油机的成本如表所示又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元要求在完成合同的情况下，做出使该厂全年生产(包括储存、维护)费用最小的决策解: 由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数根据合同要求，必须满足：又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：第i季度生产的用于j季度交货的
16、每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用cij的具体数值见表设用ai表示该厂第i季度的生产能力，bj表示第j季度的合同供应量，则问题可写成：因为当ji时，xij=0所以当ji时,取cij=M,M为一个充分大的正数。此外，由于是产量大于销量的不平衡问题，加上一个假想的需求D，就可以把问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，如下)经用表上作业法求解，可得多个最优方案，表332中列出最优方案之一即第1季度生产25台，10台当季交货，15台季度交货；季度生产5台用于季度交货；季度生产30台，其中20台于当季交货，10台于季度交货季度生产10台，于当
17、季交货按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元例2 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务已知(1)各条航线的起点、终点城市及每天航班数(2)假定各条航线使用相同型号的船只，又已知各城市间的航程天数(3)又知每条船只每次装卸货的时间各需1天。问该航运公司至少应配备多少条船，才能满足所有航线的运输需求?每天航班数表各城市之间的航程天数解： 该公司所需配备船只分两部分：(1)载货航程需要的周转船只数。例如航线l，在港口E装货1天，ED航程l 7天，在D卸货1天，总计19天每天3航班，故该航线周转船只需57条各条航线周转所需船只数见表以上累
18、计共需周转船只数91条(2)各港口间调度所需船只数有些港口每天到达船数多于需要船数例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B各港口每天余缺船只数的计算见表为使配备船只数最少，应做到周转的空船数为最少因此建立以下运输问题，其产销平衡表见表单位运价表应为相应各港口之间的船只航程天数，见表用表上作业法求出空船的最优调度方案见表另一最优解为xCA=1,xCE=1,xDB=1,xDE=1,xFE=1按这两个方案掉运船只，解得Z=40，说明各港口之间调度所需船只至少为40艘。综合以上两方面的要求，在不考虑维修、储备等情况下，该公司至少配备131条船，才能满足4条航线正常运输的需要。 （注：可编辑下载，若有不当之处，请指正，谢谢!）