《第04章运输问题-运筹学课件.ppt》由会员分享，可在线阅读，更多相关《第04章运输问题-运筹学课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第第4 4章章 运输问题运输问题2运输问题与有关概念运输问题与有关概念运输问题的求解运输问题的求解表上作业法表上作业法运输问题应用运输问题应用建模建模本章内容重点本章内容重点34.1 4.1 运输问题模型及有关概念运输问题模型及有关概念 4.1.1 4.1.1 问题的提出问题的提出 一一般般的的运运输输问问题题就就是是要要解解决决把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量与与每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下，如如何何确确定定一一个个使使得得总的运输
2、费用最小的方案。总的运输费用最小的方案。44.1运输问题模型及有关概念运输问题模型及有关概念例例4.1:某公司从两个产地某公司从两个产地A1、A2将物将物品运往三个销地品运往三个销地B1、B2、B3，各产地的，各产地的产量、各销地的销量和各产地运往各销产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？如何调运可使总运输费用最小？6Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150
3、x13+x23=200 xij0(i=1,2；j=1,2,3）4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念7111000000111100100010010001001系数矩阵系数矩阵4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念8 模型系数矩阵特征模型系数矩阵特征1.共有共有m+n 行，分别表示各产地和行，分别表示各产地和销地；销地；m n 列，分别表示各决策变列，分别表示各决策变量；量；2.每列只有两个每列只有两个1，其余为，其余为0，分别，分别表示只有一个产地和一个销地被使表示只有一个产地和一个销地被使用。用。4.1 4.1 运输问题模型及有关概念运输问题模
4、型及有关概念10表表4-3运输问题数据表运输问题数据表4.1运输问题模型及有关概念运输问题模型及有关概念销地销地产地产地B1 B2 Bn产量产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量销量d1 d2 dn设设xij为为从从产产地地Ai运运往往销销地地Bj的的运运输输量量，根根据据这这个个运运输输问问题题的的要求，可以建立运输变量表（表要求，可以建立运输变量表（表4-4）。）。11表表4-4运输问题变量表运输问题变量表4.1运输问题模型及有关概念运输问题模型及有关概念销地销地产地产地B1 B2 Bn产量产量A1 A2 Amx11 x
5、12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量销量d1 d2 dn13 运运输输问问题题是是一一种种特特殊殊的的线线性性规规划划问问题题，在在求求解解时时依依然然可可以以采采用用单单纯纯形形法法的的思思路路，如图如图4-14-1所示所示。由由于于运运输输规规划划系系数数矩矩阵阵的的特特殊殊性性，如如果果直直接接使使用用线线性性规规划划单单纯纯形形法法求求解解计计算算，则则无无法法利利用用这这些些有有利利条条件件。人人们们在在分分析析运运输输规规划划系系数数矩矩阵阵特特征征的的基基础础上上建建立立了了针针对对运运输问题的输问题的表上作业法表上作业法。下下面面主主要
6、要讨讨论论基基本本可可行行解解、检检验验数数以以及及基的转换基的转换等问题。等问题。产销平衡运输模型求解产销平衡运输模型求解15 运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5 运输问题求解作业数据表(下页）16产销平衡运输模型数据表产销平衡运输模型数据表销地销地产地产地B1B2Bn产量产量A1c11x11c12x12c1nx1na1A2c21x21c22x22c2nx2na2 Amcm1xm1cm2xm2cmn xmnam销量销量b1b2bn18定义定义4.1在表在表4-5的决策变量格中，凡是能
7、的决策变量格中，凡是能够排列成下列形式的够排列成下列形式的xab,xac,xdc,xde,xst,xsb(4-7)或或xab,xcb,xcd,xed,xst,xat(4-8)其其中中，a,d,s各各不不相相同同；b,c,t各各不不相相同同，我我们们称称之之为为变变量量集集合合的的一一个个闭闭回回路路，并并将将式式（4-7）、式式（4-8）中中的的变变量量称称为为这这个个闭闭回回路路的顶点。的顶点。为为了了说说明明这这个个特特征征，我我们们不不加加证证明明的的给给出出一一些些概概念念和和结结论论。下下面的讨论建立在表面的讨论建立在表4-54-5中决策变量格的基础上。中决策变量格的基础上。4.1
8、4.1 运输问题模型及有关概念运输问题模型及有关概念19例如，例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。等都是闭回路。若若把把闭闭回回路路的的各各变变量量格格看看作作节节点点，在在表表中可以画出如下形式的闭回路：中可以画出如下形式的闭回路：4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念闭回路示意图闭回路示意图20 根根据据定定义义可可以以看看出出闭闭回回路路的的一一些些明显特点：明显特点：(1)(1)闭闭回回路路均均为为一一封封闭闭折折线线，它它的的每每一一条条边边，或或为为水
9、水平平的的，或或为为垂垂直直的；的；(2)(2)闭闭回回路路的的每每一一条条边边（水水平平的的或或垂垂直直的的）均均有有且且仅仅有有两两个个闭闭回回路路的的顶点（变量格）。顶点（变量格）。4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念定定理理4.1变变量量组组xab,xcd,xef,xst 所所对对应应的的系系数数列列向向量量pab,pcd,pef,pst 线线性性无无关关的的充充分分必必要要条条件件是是这这个个变变量量组中组中不包含闭回路不包含闭回路。推推论论产产销销平平衡衡运运输输问问题题的的m+n-1个个变变量量构构成成基基变变量量的的充充分分必必要要条条件件是是它它不含闭
10、回路。不含闭回路。这这个个推推论论给给出出了了运运输输问问题题基基本本解解的的重重要要性性质质，也也为为寻寻求求基基本本可可行行解解提提供了依据。供了依据。4.1 4.1 运输问题模型及有关概念运输问题模型及有关概念244.24.2运输问题求解运输问题求解表上作业法表上作业法 一、初始基本可行解的确定一、初始基本可行解的确定根根据据上上面面的的讨讨论论，要要求求得得运运输输问问题题的的初初始始基基本本可可行行解解，必必须须保保证证找找到到m+n1个个不不构构成成闭闭回回路路的的基基变变量。量。一般的方法步骤如下：一般的方法步骤如下：254.24.2运输问题求解运输问题求解表上作业法表上作业法(
11、1)在在运运输输问问题题求求解解作作业业数数据据表表中中任任选选一一个个单单元元格格xij(Ai行行Bj列列交交叉叉位位置置上上的格的格),令令 xij=minai,bj即即从从Ai向向Bj运运最最大大量量(使使行行或或列列在在允允许许的的范范围围内内尽尽量量饱饱和和，即即使使一一个个约约束束方方程程得得以以满满足足),填填入入xij的的相相应应位置；位置；26运输问题求解运输问题求解表上作业法表上作业法(2)从从ai和和bj中中分分别别减减去去xij的的值值，修修正正为为新新的的ai和和bj 即即调调整整Ai的的拥拥有有量量及及Bj的需求量；的需求量；(3)若若ai=0，则则划划去去对对应应
12、的的行行（已已经经把把拥拥有有的的量量全全部部运运走走），若若bj=0则则划划去去对对应应的的列列（已已经经把把需需要要的的量量全全部部运运来来），且且每每次次只只划划去去一一行行或或一一列列（即即每每次次要要去掉且只去掉一个约束）；去掉且只去掉一个约束）；28上述计算过程可用流程图描述如下（图上述计算过程可用流程图描述如下（图4-2）取未划去的单元格取未划去的单元格xij,令令xij=minai,bjai=ai-xijbj=bj-xijai=0?划去第划去第i行行划去第划去第j列列是是否否bj=0否否所所有有行行列列是是否否均均被被划划去去是是找到初始基找到初始基本可行解本可行解图图4-2求
13、运输问题的初始基本可行解过程求运输问题的初始基本可行解过程注：为了方便，这里总记剩注：为了方便，这里总记剩余的产量和销量为余的产量和销量为ai,bj294.24.2运输问题求解运输问题求解表上作业法表上作业法 按照上述方法所产生的一组变量的按照上述方法所产生的一组变量的取值将满足下面条件：取值将满足下面条件：(1)所所得得的的变变量量均均为为非非负负，且且变变量量总数恰好为总数恰好为m+n1个；个；(2)所有的约束条件均得到满足；所有的约束条件均得到满足；(3)所得的变量不构成闭回路。所得的变量不构成闭回路。314.24.2运输问题求解运输问题求解表上作业法表上作业法 1 1、初始基本可行解的
14、确定、初始基本可行解的确定 （1 1）西北角法）西北角法：从西北角（左上：从西北角（左上角）格开始，在格内的右下角标上允角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得其他格划去。如此进行下去，直至得到一个基本可行解。到一个基本可行解。32 （2）最小元素法最小元素法：从运价最小：从运价最小的格开始，在格内的右下角标上允的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小许取得的最大数
15、。然后按运价从小到大顺序填数。若某行（列）的产到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直的其他格划去。如此进行下去，直至得到一个基本可行解。至得到一个基本可行解。4.24.2运输问题求解运输问题求解表上作业法表上作业法33 注注:应用西北角法和最小元素应用西北角法和最小元素法，每次填完数，都只划去一行或法，每次填完数，都只划去一行或一列，只有一列，只有最后一个元例外最后一个元例外（同时（同时划去一行和一列）。当填上一个数划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划后行、列同时饱和时，也应任意划去一
16、行（列），在保留的列（行）去一行（列），在保留的列（行）中没被划去的格内标一个中没被划去的格内标一个0 0。4.24.2运输问题求解运输问题求解表上作业法表上作业法4.2运输问题求解运输问题求解表上作业法表上作业法354.2运输问题求解运输问题求解表上作业法表上作业法364.24.2运输问题求解运输问题求解表上作业法表上作业法37 最最优优性性检检验验就就是是检检查查所所得得到到的的方方案案是是不不是是最最优优方方案案。检检查查的的方方法法与与单单纯纯形形方方法法中中的的原原理理相相同同，即即计计算算检检验验数数。由由于于目目标标要要求求极极小小，因因此此，当当所所有有的的检检验验数数都都大大
17、于于或或等等于于零零时时该该调调运运方方案案就就是是最最优优方方案案；否否则则就就不不是是最最优优，需需要要进进行行调调整整。下下面面介介绍绍两两种种求求检检验验数数的的方方法法:闭闭回路法回路法和和位势法位势法二、基本可行解的最优性检验二、基本可行解的最优性检验 4.24.2运输问题求解运输问题求解表上作业法表上作业法 2.2.位势法位势法 位位势势：设设对对应应基基变变量量xij的的m+n-1个个ij，存在，存在ui,vj满足满足ui+vj=cij，i=1,2,m;j=1,2,n.称称这这些些ui,vj为为该该基基本本可可行行解解对对应应的的位势。位势。4.24.2运输问题求解运输问题求解
18、表上作业法表上作业法48由于有由于有m+n个变量（个变量（ui,vj），），m+n-1个方程（基变量个数），个方程（基变量个数），故有一个自由变量，位势不唯一。故有一个自由变量，位势不唯一。利用位势求检验数：利用位势求检验数：ij=cij-ui-vji=1,m;j=1,n4.2运输问题求解运输问题求解表上作业法表上作业法49前例，位势法求检验数：前例，位势法求检验数：step1从任意基变量对应的从任意基变量对应的cij开始开始,任任取取 ui或或vj，然后利用，然后利用cij=ui+vj 公式公式依次找出依次找出m+n个个ui、vj,我们我们从从c14=10开始开始step2计算非基变量的检验
19、数计算非基变量的检验数 ij=cij-ui-vj；填入圆圈内；填入圆圈内4.2运输问题求解运输问题求解表上作业法表上作业法504.2运输问题求解运输问题求解表上作业法表上作业法51 当当非非基基变变量量的的检检验验数数出出现现负负值值时时，则则表表明明当当前前的的基基本本可可行行解解不不是是最最优优解解。在在这这种种情情况况下下，应应该该对对基基本本可可行行解解进进行行调调整整，即即找找到到一一个个新新的的基基本本可可行行解解使使目目标标函函数数值值下下降降，这这一一过过程程通通常常称称为为换换基基(或或主主元元变变换换)过程过程。4.24.2运输问题求解运输问题求解表上作业法表上作业法三、求
20、新的基本可行解三、求新的基本可行解52（1）选负检验数中最小者选负检验数中最小者 rk，那么，那么xrk为为主元，作为进基变量（上页图中主元，作为进基变量（上页图中x24）;（2）以以xrk为起点找一条闭回路，除为起点找一条闭回路，除xrk外外其余顶点必须为基变量格（上页图中的回其余顶点必须为基变量格（上页图中的回路）路）;4.2运输问题求解运输问题求解表上作业法表上作业法在运输问题的表上作业法中，换基的过程是如下进行：在运输问题的表上作业法中，换基的过程是如下进行：53（3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号，xrk为为1，沿一个方向（顺时针或逆时针），沿一个方向（顺时针或逆
21、时针）依次给各顶点标号；依次给各顶点标号；（4）求求 =Minxij xij对应闭回路上的对应闭回路上的偶数标号格偶数标号格=xpq 那么确定那么确定xpq为出基为出基变量，变量，为调整量；为调整量；4.24.2运输问题求解运输问题求解表上作业法表上作业法54（5）对闭回路的各奇标号顶点调整对闭回路的各奇标号顶点调整为：为：xij+，对各偶标号顶点，对各偶标号顶点调整调整为：为：xij-，特别，特别 xpq-=0，xpq变变为非基变量。为非基变量。重复重复(2)、(3)步，直到所有检验步，直到所有检验数均非负，得到最优解。数均非负，得到最优解。4.24.2运输问题求解运输问题求解表上作业法表上
22、作业法554.2运输问题求解运输问题求解表上作业法表上作业法 ij0，得到，得到最优解最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余xij=0;最优值最优值：f*=35+102+13+81+46+53=8556例题求解过程总结：例题求解过程总结：初始基本可行解初始基本可行解位势法求检验数：位势法求检验数：58选择负检验数，找出闭回路，确定选择负检验数，找出闭回路，确定调整运输量调整运输量59计算新的基本可行解，重新计算，检验计算新的基本可行解，重新计算，检验数均为非负，即得到最优解：数均为非负，即得到最优解：；最优值为；最优值为858560产销不平衡问题
23、的处理产销不平衡问题的处理 实践中的运输问题常常非产销平衡，为下列实践中的运输问题常常非产销平衡，为下列的一般运输问题模型的一般运输问题模型611.产量大于销量的情况产量大于销量的情况考虑考虑 si dj 情况，得到的数学模型为情况，得到的数学模型为62我们只须在模型中的产量限制约束我们只须在模型中的产量限制约束(前前m个不等式约束个不等式约束)中引入中引入m个松弛变量个松弛变量xin+1i=1,2,m 即可，变为：即可，变为：xij+xin+1=sii=1,2,m然后，需设一个销地然后，需设一个销地Bn+1,它的销量它的销量为：为：dn+1=si-dj 由于实际不运送由于实际不运送,它们的运
24、费为它们的运费为cin+1=0i=1,2,m。于是，这个运输问题就转化成了一于是，这个运输问题就转化成了一个产销平衡的问题个产销平衡的问题63例例4.3某公司从两个产地某公司从两个产地A1、A2将物品运往三个将物品运往三个销地销地B1、B2、B3，各产地的产量、各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运费如下表所示，问：应如何调运可使总运输费用最小？输费用最小？64 解：增加一个虚设的销地运输费用解：增加一个虚设的销地运输费用为为0 0652.销量大于产量的情况销量大于产量的情况考虑考虑 si dj
25、情况，得到的数学模型为情况，得到的数学模型为66我们只须在模型中的销量限制约束我们只须在模型中的销量限制约束(后后n个不等式约束个不等式约束)中引入中引入n个松弛变量个松弛变量xm+1jj=1,2,n 即可，变为：即可，变为：xij+xm+1j=djj=1,2,n然后，需设一个销地然后，需设一个销地BAm+1,它的它的c产量产量为：为：dm+1=dj-si 由于实际不运送由于实际不运送,它们的运费为它们的运费为cm+1j=0j=1,2,n。于是，这个运输问题就转化成了一于是，这个运输问题就转化成了一个产销平衡的问题个产销平衡的问题67某公司从两个产地某公司从两个产地A1、A2将物品运往三将物品
26、运往三个销地个销地B1、B2、B3，各产地的产量、各，各产地的产量、各销地的销量和各产地运往各销地每件物销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运品的运费如下表所示，问：应如何调运可使总运输费用最小？可使总运输费用最小？例例4.468解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 04.3运输问题的应用运输问题的应用例例4.5:某研究院有三个区。每年分别需要用某研究院有三个区。每年分别需要用煤煤3000、1000、2000吨，由河北临城、山西盂吨，由河北临城、山西盂县两处煤矿供应，价格、质量相同。供应能力县两处煤矿供应，价格、质量相同。供应能力分别
27、为分别为1500、4000吨，运价如下表。由于需求吨，运价如下表。由于需求大于供给，经研究提出，大于供给，经研究提出，1区供应量可减少区供应量可减少0300吨，吨，2区必须满足需求量，区必须满足需求量，3区供应量不少区供应量不少于于1700吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。70 解解:根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：取取M代表一个很大的正数，其作用是强迫相代表一个很大的正数，其作用是强迫相应的应的x31、x33、x34取值为取值为0。71例例4.6:设有设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4四个地区的农用化肥。假设
28、效果四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用相同，有关数据如下表。试求总费用为为最低最低的化肥调拨方案。的化肥调拨方案。72首先，作出产销平衡运价表首先，作出产销平衡运价表:最低要求必须满最低要求必须满足，因此把相应的虚设产地运费取为足，因此把相应的虚设产地运费取为M；最；最高要求与最低要求的差允许按需要安排，因高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为此把相应的虚设产地运费取为0。对应。对应4”的的销量销量50是考虑问题本身适当取的数据，根据是考虑问题本身适当取的数据，根据产销平衡要求确定产销平衡要求确定D的产量为的产量为50。解：解：生产与储存问题
29、生产与储存问题例例4.7:某厂按合同规定须于当年每个季度末分某厂按合同规定须于当年每个季度末分别提供别提供10、15、25、20台同一规格的柴油机。台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费交货，每台每积压一个季度需储存、维护等费用用0.15万元。试求在完成合同的情况下，使该万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案厂全年生产总费用为最小的决策方案交货：交货：生产：生产：x11 =10 x11+
30、x12+x13+x14 25x12+x22 =15 x22+x23+x24 35x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44=20 x4410解：解：设设xij 为第为第i季度生产的第季度生产的第j 季度交季度交货的柴油机数目，那么应满足货的柴油机数目，那么应满足把第把第i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第i个生产个生产厂的产量；把第厂的产量；把第j季度交货的柴油机数目看作季度交货的柴油机数目看作第第j个销售点的销量；成本加储存、维护等费个销售点的销量；成本加储存、维护等费用看作运费。用看作运费。可构造下列产销平衡问题：可构造下列产销平衡问题：目标函数：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25 x14+11.1 x22+11.25 x23+11.4 x24 +11.0 x33+11.15 x34 +11.3 x44