运筹学 三章(运输问题).ppt

第三章 运输问题3.1 运输问题及其数学模型运输问题及其数学模型3.2 表上作业法表上作业法3.3 运输问题的进一步讨论运输问题的进一步讨论12/27/202212/27/20221 1浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系本章学习要求n掌握表上作业法及其在产销平衡运输问题求解中的应用n掌握产销不平衡运输问题的求解方法12/27/202212/27/20222 2浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3.1 运输问题及其数学模型运输问题及其数学模型1.1.运输问题的一般提法运输问题的一般提法运输问题的一般提法运输问题的一般提法：假设有假设有m个生产地点，可以供应某种个生产地点，可以供应某种物资（以后称为产地），用物资（以后称为产地），用Ai来表示，来表示，i=1,m,有有n个销地，用个销地，用Bj来表示，来表示，j=1,n，产地的产量和销地的销量分别为，产地的产量和销地的销量分别为ai,bj，从，从产地产地Ai到销地到销地Bj运输一个单位物资的运价为运输一个单位物资的运价为Cij，这些数据可汇，这些数据可汇总于下表，在假设产销平衡的条件下，即总于下表，在假设产销平衡的条件下，即ai=bj，问该如何，问该如何调运物品使总运费最小？调运物品使总运费最小？B1B2Bn产量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam销量b1b2bn12/27/202212/27/20223 3浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系建模：设建模：设xij表示从表示从Ai到到Bj的运量，则所求的的运量，则所求的数学模型为：数学模型为：min=cijxij s.t.xij=ai i=1,mxij=bj j=1,nj=1ni=1mi=1mj=1nxij0 i=1,m,j=1,n12/27/202212/27/20224 4浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2.例如例如：三个产地四个销地，用网络表示：三个产地四个销地，用网络表示2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14产地产地运价运价销地销地6753482759106产量产量销量销量总产量总产量60吨吨总销量总销量60吨吨产销平衡的运输问题产销平衡的运输问题12/27/202212/27/20225 5浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系运输问题线性规划模型运输问题线性规划模型产产地地约约束束销销地地约约束束12/27/202212/27/20226 6浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系运输问题的表格表示运输问题的表格表示12/27/202212/27/20227 7浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系注意：注意：注意：注意：1.1.运输问题有可行解的充要条件为：运输问题有可行解的充要条件为：运输问题有可行解的充要条件为：运输问题有可行解的充要条件为：2.2.平衡运输问题有最优解平衡运输问题有最优解平衡运输问题有最优解平衡运输问题有最优解3.3.平衡运输问题的约束方程组的系数矩阵的系数矩阵平衡运输问题的约束方程组的系数矩阵的系数矩阵平衡运输问题的约束方程组的系数矩阵的系数矩阵平衡运输问题的约束方程组的系数矩阵的系数矩阵A A的秩为的秩为的秩为的秩为m+n-1m+n-14.4.运输问题的求解过程与单纯形法类似，只是更简单，运输问题的求解过程与单纯形法类似，只是更简单，运输问题的求解过程与单纯形法类似，只是更简单，运输问题的求解过程与单纯形法类似，只是更简单，通常称表上作业法，而且是求解极小化问题。通常称表上作业法，而且是求解极小化问题。通常称表上作业法，而且是求解极小化问题。通常称表上作业法，而且是求解极小化问题。5.5.运输问题的系数矩阵具有什么特点？运输问题的系数矩阵具有什么特点？运输问题的系数矩阵具有什么特点？运输问题的系数矩阵具有什么特点？6.6.运输问题的运输问题的运输问题的运输问题的LDLD是怎样的？是怎样的？是怎样的？是怎样的？12/27/202212/27/20228 8浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3.2 表上作业法n初始基可行解的确定初始基可行解的确定n最优性检验最优性检验n基变换基变换12/27/202212/27/20229 9浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系运输问题基的表示运输问题基的表示 mm个产地、个产地、个产地、个产地、n n个销地的运输问题，除了满足可行的条件个销地的运输问题，除了满足可行的条件个销地的运输问题，除了满足可行的条件个销地的运输问题，除了满足可行的条件外，任何一个基要满足以下条件：外，任何一个基要满足以下条件：外，任何一个基要满足以下条件：外，任何一个基要满足以下条件：n n基变量的个数为基变量的个数为基变量的个数为基变量的个数为m+n-1m+n-1；n n基变量不能形成闭回路；基变量不能形成闭回路；基变量不能形成闭回路；基变量不能形成闭回路；12/27/202212/27/20221010浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系123412312341231234123123412312341231234123基在运输表中的表示基在运输表中的表示12/27/202212/27/20221111浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系123412312341231234123123412312341231234123运输表中同行同列组成回路的变量运输表中同行同列组成回路的变量12/27/202212/27/20221212浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系一一.初始基可行解的确定初始基可行解的确定n西北角法西北角法n最小元素法最小元素法n沃格尔法沃格尔法12/27/202212/27/20221313浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1.西北角法西北角法813131466方法：优先满足运输表中左上角空格的供销要求方法：优先满足运输表中左上角空格的供销要求填一个数字只能划去一行或一列填一个数字只能划去一行或一列12/27/202212/27/20221414浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2.最小元素法最小元素法12015130113021930120200方法：按单位运价的大小，决定供应的先后，优先方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）满足单位运价最小者的供销要求（就近供应）12/27/202212/27/20221515浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3.沃格尔法沃格尔法3212323311*3113行罚数行罚数列列罚罚数数414*13*1219方法：计算出每一行及每一列中单位运价最小和次小的两个元素之方法：计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。足其供销关系。12/27/202212/27/20221616浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系二二.最优性检验求最优性检验求非基变量的检验数非基变量的检验数n闭回路法闭回路法n位势法位势法12/27/202212/27/20221717浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1.闭回路法闭回路法n方法方法求非基变量检验数求非基变量检验数求非基变量检验数求非基变量检验数 ij ij,以以以以该变该变量所在格量所在格量所在格量所在格为顶为顶点，其他点，其他点，其他点，其他顶顶点点点点为为基基基基变变量找一个量找一个量找一个量找一个闭闭回路，从回路，从回路，从回路，从该该非基非基非基非基变变量量量量顶顶点点点点为为“”，“”，“”，“”依次加减其运价，即依次加减其运价，即依次加减其运价，即依次加减其运价，即为检验为检验数。数。数。数。n意义：意义：以以以以该该非基非基非基非基变变量充当基量充当基量充当基量充当基变变量量量量时单时单位运量运位运量运位运量运位运量运费费的的的的损损失。当所失。当所失。当所失。当所有的有的有的有的 ij ij00，则则已得运已得运已得运已得运输问题输问题的最的最的最的最优优解。即解。即解。即解。即单单位物品由位物品由位物品由位物品由i-i-j j引起引起引起引起总总运运运运费费的的的的变变化。化。化。化。12/27/202212/27/20221818浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(1)12=c12-c22+c21-c11=7-4+8-6=5512/27/202212/27/20221919浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(2)513=c13-c23+c21-c11=5-2+8-6=5512/27/202212/27/20222020浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(3)5514=(c14-c34+c33-c23+c21-c11)=3-6+10-2+8-6=7712/27/202212/27/20222121浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(4)55712=c24-c34+c33-c23=7-6+10-2=9912/27/202212/27/20222222浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(5)557932=c32-c24+c23-c33=9-4+2-10=-3-312/27/202212/27/20222323浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.闭回路法闭回路法(6)5579-331=c31-c21+c23-c32=5-8+2-10=-11-1112/27/202212/27/20222424浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2.位势法位势法该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为：该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为：U Ui i,V,Vj j无约束无约束无约束无约束由由LP中中ij 的定义：的定义：ij=Cij-CBB-1Pij Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij=cij-(ui+vj)对基变量而言：对基变量而言：c cij ij=(u ui i+v+vj j)由由由由m+n-1m+n-1个基变量对应个基变量对应个基变量对应个基变量对应m+n-1m+n-1个线性方程个线性方程个线性方程个线性方程而而而而LDLD的变量有的变量有的变量有的变量有m+nm+n个，对偶问题有无穷多解，则可个，对偶问题有无穷多解，则可个，对偶问题有无穷多解，则可个，对偶问题有无穷多解，则可设其中一个最优解为设其中一个最优解为设其中一个最优解为设其中一个最优解为0 0，而推导出其他分量。从而求，而推导出其他分量。从而求，而推导出其他分量。从而求，而推导出其他分量。从而求出非基变量的检验数。出非基变量的检验数。出非基变量的检验数。出非基变量的检验数。12/27/202212/27/20222525浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314662.位势法位势法(1)uivj0622010-412/27/202212/27/20222626浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314662.位势法位势法(2)uivj0622010-45579-13-312/27/202212/27/20222727浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系三三.基变换闭回路法基变换闭回路法与单纯形法一样，如果所有非基变量检验数与单纯形法一样，如果所有非基变量检验数与单纯形法一样，如果所有非基变量检验数与单纯形法一样，如果所有非基变量检验数 ij ij 0 0，则该基解，则该基解，则该基解，则该基解为最优解，否则不是最优解，需要进行基变换，换入变量的确为最优解，否则不是最优解，需要进行基变换，换入变量的确为最优解，否则不是最优解，需要进行基变换，换入变量的确为最优解，否则不是最优解，需要进行基变换，换入变量的确定方法一样，设换入变量定方法一样，设换入变量定方法一样，设换入变量定方法一样，设换入变量x xlklk的检验数为的检验数为的检验数为的检验数为 lklk ，换换换换出出出出变变变变量量量量为为为为x xsfsf 以以以以x xlklk和基变量为顶点找一个闭回路，分别标号和基变量为顶点找一个闭回路，分别标号和基变量为顶点找一个闭回路，分别标号和基变量为顶点找一个闭回路，分别标号”+”,”-”,”+”,”_”+”,”-”,”+”,”_”；在标号为；在标号为；在标号为；在标号为”-”-”的最小的的最小的的最小的的最小的运量为调整量，在闭回路上进行调整，运量为调整量，在闭回路上进行调整，运量为调整量，在闭回路上进行调整，运量为调整量，在闭回路上进行调整，“”的加的加的加的加“-”的减，当存在的减，当存在的减，当存在的减，当存在x xsfsf为为为为0 0时，为换出变量，得一新的基可时，为换出变量，得一新的基可时，为换出变量，得一新的基可时，为换出变量，得一新的基可行解，再求检验数。行解，再求检验数。行解，再求检验数。行解，再求检验数。12/27/202212/27/20222828浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.基变换基变换-确定换入换出变量确定换入换出变量5579-3-11-11-612/27/202212/27/20222929浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8131314661.基变换得新的基解基变换得新的基解-621212/27/202212/27/20223030浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1313141.基变换得新的基解基变换得新的基解621212/27/202212/27/20223131浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系确定初始基础可行解确定初始基础可行解确定初始基础可行解确定初始基础可行解西北角法西北角法西北角法西北角法沃格尔法沃格尔法沃格尔法沃格尔法求非基变量的检验数求非基变量的检验数求非基变量的检验数求非基变量的检验数闭回路法闭回路法闭回路法闭回路法对偶变量法对偶变量法对偶变量法对偶变量法确定进基变量确定进基变量确定进基变量确定进基变量确定离基变量确定离基变量确定离基变量确定离基变量得到新的基础可行解得到新的基础可行解得到新的基础可行解得到新的基础可行解表上作业法总结表上作业法总结表上作业法总结表上作业法总结沿闭回路调整运量沿闭回路调整运量沿闭回路调整运量沿闭回路调整运量最小元素法最小元素法最小元素法最小元素法12/27/202212/27/20223232浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系单纯形法与表上作业法比较单纯形法与表上作业法比较单纯形法（单纯形法（Min）表上作业法表上作业法确定初确定初始基变始基变量量XB+松驰变量松驰变量+（人工变量）（人工变量）XB系数矩阵为系数矩阵为I，m个个其余其余XN最小元素法、沃格尔法等最小元素法、沃格尔法等XB数字格，数字格，m+n-1个个XN 空格空格检验数检验数基变量基变量 j=0非基变量非基变量 j=cj-cBB-1pj基变量基变量 ij=0非基变量非基变量 ij=cij-Ui-Vj调整调整进基：进基：min j j 0出基：出基：minbi/aik，aik0进基：进基：min ij ij总销量时，总销量时，总销量时，总销量时，可增加一个假想销地可增加一个假想销地可增加一个假想销地可增加一个假想销地B Bn+1n+1,销量销量销量销量 a ai i b bj j，C Ci,n+1i,n+1=0=0，n n当当当当总产总产量量量量bj（产量（产量销量）所以要虚构一销销量）所以要虚构一销地地B5，其销量，其销量b5=30，而，而ci5=0，这样，就转化成了一个产销平衡问题。，这样，就转化成了一个产销平衡问题。B1B2B3B4B5产量产量A130508040030 A270408060050A3100305020060销量销量151040453014014014014012/27/202212/27/20223939浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系例如：例如：B1B2B3B4产量产量A13113109 A219284A3741057销量销量136156204012/27/202212/27/20224040浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系二、一些变形和推广二、一些变形和推广1 1、最大化问题、最大化问题、最大化问题、最大化问题1）找出单位物资效益表（）找出单位物资效益表（cij）中的最大元素）中的最大元素M，即，即M=maxcij2)令令cij=M-cij，并视为运价。，并视为运价。3）由）由cij构成单位运价表，按通常的表上作业法求解，求得构成单位运价表，按通常的表上作业法求解，求得最优解后把所得结果转换为原问题的答案。最优解后把所得结果转换为原问题的答案。2 2、销量不确定、销量不确定、销量不确定、销量不确定（有最高需求和最低需求）（有最高需求和最低需求）设销地设销地Bk的最低需求为的最低需求为bk，最高需求为，最高需求为bk”，这时可把看，这时可把看作作Bk和和Bk”两个销地，两个销地，Bk需求量需求量bk，Bk”的需求量的需求量bk”-bk12/27/202212/27/20224141浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系例：设某种材料有例：设某种材料有例：设某种材料有例：设某种材料有A A1 1、A A2 2、A A3 3三个生产厂家，其产品供应三个生产厂家，其产品供应三个生产厂家，其产品供应三个生产厂家，其产品供应B B1 1、B B2 2、B B3 3、B B4 4四个城市，假定等量的材料在这些城市的使用效果相同，已知各四个城市，假定等量的材料在这些城市的使用效果相同，已知各四个城市，假定等量的材料在这些城市的使用效果相同，已知各四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？运价如表所示，求使运费最少的调运方案？运价如表所示，求使运费最少的调运方案？运价如表所示，求使运费最少的调运方案？B1B2B3B4产量产量A11613221750 A21413191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限不限12/27/202212/27/20224242浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系B1B2B3B4产量产量A11613221750 A21413191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限不限B B1 1 B B1 B B2B B3B B4 B B4销量销量3020703010105050A1A1A2A3A4产量产量产量产量5060605050505016161419M16161419013131320M22221923017171515MMM17171515MM0 012/27/202212/27/20224343浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系4 4、缺货损失问题、缺货损失问题、缺货损失问题、缺货损失问题如下表，设销地如下表，设销地1 1不允许缺货；销地不允许缺货；销地2 2缺货，单位损失费缺货，单位损失费3 3元；销地元；销地3 3缺货，缺货，单位损失费单位损失费2 2元，问如何处理？元，问如何处理？B1B2B3产量产量A151710 A264680A332515销量销量655525B1B2B3产量产量A151710 A264680A332515销量销量655525A440M323 3、指定销售问题、指定销售问题、指定销售问题、指定销售问题如规定销地如规定销地1的需求量必须由产地的需求量必须由产地4供应，如何处理？供应，如何处理？1）直接令）直接令x41=b12)令令c41=-M，或者，或者c11=c21=c31=M这样销地这样销地1的需求量肯定是由产地的需求量肯定是由产地1供应了。供应了。12/27/202212/27/20224444浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系三、生产与存储问题三、生产与存储问题例：某厂按合同须于当年每个季度末分别提供例：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交每台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费货，每台每积压一个季度工厂需支付保管及维护费0.15万元，万元，试问在按合同完成任务的情况下，工厂应如何安排生产计划试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？才能使全年消耗的生产与存贮费用的总和最少？季度季度工厂生产能力（台工厂生产能力（台/季）季）成本（万元成本（万元/台）台）交货量（台）交货量（台）12510.81023511.101533011.002541011.302012/27/202212/27/20224545浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系发货点：生产起重机的四个季度发货点：生产起重机的四个季度发货量：生产能力发货量：生产能力收货点：按合同交付起重机的四个季度收货点：按合同交付起重机的四个季度收货量：按合同提供起重机的数量收货量：按合同提供起重机的数量cij=第第i季度每台起重机的生产成本季度每台起重机的生产成本+（j-i）个季度每台起重机）个季度每台起重机的存贮费（的存贮费（ji）12345发量（台）发量（台）125235330410收量（台）收量（台）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.30000012/27/202212/27/20224646浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系四、有转运的运输问题四、有转运的运输问题1 1、运输表的构成、运输表的构成、运输表的构成、运输表的构成1）产地：原产地、中间转运站、转运物资的销地）产地：原产地、中间转运站、转运物资的销地2）销地：原销地、中间转运站、转运物资的产地）销地：原销地、中间转运站、转运物资的产地3）设各转运站转运物资的数量均为）设各转运站转运物资的数量均为 ai这样专职转运站的产量和销量均为这样专职转运站的产量和销量均为 ai而原产地而原产地Ai的产量均为（的产量均为（ai+ai）原销地原销地Bj的销量均为（的销量均为（bj+ai）4)将各条线路实际的运输单位列成单位运价表，其中不可能将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用的运输其单位运价用M表示。表示。12/27/202212/27/20224747浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2 2、举例：、举例：、举例：、举例：A、B两个化肥厂每年各生产磷肥两个化肥厂每年各生产磷肥900万吨、万吨、600万吨，这些万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口知三个港口C、D、E每年能承担的船运量分别为每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，且已知单万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？才能使运费最少？ABCDEA029107B2071010C97034D1010302E71042012/27/202212/27/20224848浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系ABCDEA029107B2071010C97034D1010302E710420P发量发量收量收量24002100150015001500150015002200190018001000000012/27/202212/27/20224949浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系习题：习题：习题：习题：3.103.103.123.1212/27/202212/27/20225050浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系