运筹学 运输问题 (2)优秀课件.ppt

运筹学 运输问题第1页，本讲稿共44页 运输问题 运运输问题（Transportation Problem，简记为TP）是一是一类常常见而且极其特殊的而且极其特殊的线性性规划划问题.它最早是从它最早是从物物资调运工作中提出来的，是物流运工作中提出来的，是物流优化管理的重要的化管理的重要的内容之一内容之一 。从理从理论上上讲，运，运输问题也可用也可用单纯形法来求解，形法来求解，但是由于运但是由于运输问题数学模型具有特殊的数学模型具有特殊的结构，存在一构，存在一种比种比单纯形法更形法更简便的便的计算方法算方法 表上作业法表上作业法，用表上作用表上作业法来求解运法来求解运输问题比用比用单纯形法可形法可节约计算算时间与与计算算费用用.但表上作但表上作业法的法的实质仍是仍是单纯形法形法 第2页，本讲稿共44页1 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物某种物资共有共有 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，问怎怎样调运才能运才能使使总运运费最小？最小？一、运输问题的数学模型一、运输问题的数学模型 加速物加速物资流流转 降低流通降低流通费用用 第3页，本讲稿共44页 运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运运输表表1 1、产销平衡平衡问题即即 设 xij 表示表示产地地 Ai 运往运往销地地 Bj(i=1,2,m;j=1,2,n)的运量的运量.销地销地产地产地 B1 B2 Bn产量产量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bnNote:cij 在左下角在左下角 xij 在右上角在右上角 第4页，本讲稿共44页1 运输问题及其数学模型2 2、产销不平衡不平衡问题当当当当第5页，本讲稿共44页 运输问题二、运输问题数学模型的特点二、运输问题数学模型的特点讨论产销平衡平衡问题定理定理 1 平衡运平衡运输问题必有可行解，也必有最优解问题必有可行解，也必有最优解.证明明定理定理 2 平衡运平衡运输问题的的约束方程系数矩束方程系数矩阵 A 和增广矩和增广矩阵 的秩相等，且等于的秩相等，且等于 m+n-1.即即 定理定理2 说明：明：基可行解包含基可行解包含m+n-1个基个基变量量.定理定理 3 平衡运输问题的约束方程系数矩阵平衡运输问题的约束方程系数矩阵 A 的所有的所有各各阶子式只取子式只取 0，1 或或-1 三个三个值.定理定理 4 如果平衡运输问题中的所有产量如果平衡运输问题中的所有产量 ai 和销量和销量 bj都是整数，那么，它的任一基可行解都是整数解都是整数，那么，它的任一基可行解都是整数解.证明明note第6页，本讲稿共44页定理定理 1 1 的证明的证明Proof:则取取显然有然有 ，又又所以所以 ，是，是问题的一个可行解的一个可行解.又因又因为 ，对于任一可行于任一可行解有目解有目标函数函数值 ，对于求极小化于求极小化问题，目，目标函数函数值有下界，有下界，则必有最必有最优解解.第7页，本讲稿共44页1 运输问题及其数学模型Note:平衡运输问题有平衡运输问题有 个变量，个变量，个约束个约束条件，规模很大。条件，规模很大。Go back第8页，本讲稿共44页定理定理 4 的证明的证明Proof:设 x 是是 Ax=b 的任一基可行解，的任一基可行解，B 为对应的基矩的基矩阵，则 其中其中 Bt 是用是用 b 中中对应的的 m+n-1元素替元素替换 B 的第的第t 列列元素得到的矩元素得到的矩阵.显然然，由定理，由定理 3 知，知，det Bt 是个整数，是个整数，det B=，因此，因此，都是整数都是整数.其基其基变量量为第9页，本讲稿共44页 运输问题定义定义 1 1（其中（其中 互不相同，互不相同，互不相同）互不相同）形式的形式的变量集合，称量集合，称为一个一个闭回路，其中回路，其中诸变量称量称为这个个闭回路的回路的顶点点.B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如：变量集合量集合变量集合量集合2、每一行（或列）若有每一行（或列）若有闭回路的回路的顶点，点，则有两个有两个顶点；点；3、每两个每两个顶点格子的点格子的连线都是水平的或垂直的；都是水平的或垂直的；4、闭回路中回路中顶点的个数必点的个数必为偶数偶数.闭回路的几何特征：回路的几何特征：1、每一个每一个顶点格子都是点格子都是 90转角点；角点；凡是能排列成凡是能排列成凡是能排列成凡是能排列成第10页，本讲稿共44页1 运输问题及其数学模型闭回路的代数性回路的代数性质：性性质 1 构成构成闭回路的回路的变量量组对应的列向量的列向量组必必线性相关性相关.证明明性性质 2 分组分组构成构成闭回路，回路，则该变量量组对应的列向量的列向量组是是线性相关的性相关的.推推论 1 若若变量量组对应的列向量的列向量组线性无关，性无关，则该变量量组一定不包含一定不包含闭回路回路.若若变量量组 中有一个部中有一个部Go on第11页，本讲稿共44页性质性质 1 的证明的证明Proof:由直接由直接计算可知算可知故故该向量向量组线性相关性相关.第12页，本讲稿共44页 运输问题在在变量量组 中，若有某中，若有某一个一个变量量 xij 是它所在的行（第是它所在的行（第 i 行）或列（第行）或列（第 j 列）列）中出中出现于于（*）中的唯一中的唯一变量，量，则称称该变量量 xij 是是该变量量组的一个孤立点的一个孤立点.定定义 2闭回路的特征回路的特征性性质 3 没有孤立点没有孤立点 若一若一变量量组中不包含任何中不包含任何闭回路，回路，则该变量量组必有孤立点必有孤立点.反反证孤立点不会是孤立点不会是闭回路上的点回路上的点定理定理 5 变量量组 对应的列向量的列向量组线性无关的充性无关的充要要条件是条件是该变量量组中不包含任何中不包含任何闭回路回路.证明明第13页，本讲稿共44页定理定理 5 的的证明明Proof:用反用反证法法设变量量组（*）对应的列向量的列向量组线性无关，但性无关，但该变量量组包含一个以其中某些包含一个以其中某些变量量为顶点的点的闭回路，回路，则由性由性质 2 知，知，这些些变量量对应的列向量必的列向量必线性相关，与假性相关，与假设矛盾矛盾.定理定理 5 变量量组 对应的列向量的列向量组线性无关的充性无关的充要要条件是条件是该变量量组中不包含任何中不包含任何闭回路回路.设有一有一组数数 使得使得 由于由于变量量组（*）中不包含任何中不包含任何闭回路，由性回路，由性质 3 可知其中必有孤立点，可知其中必有孤立点，不妨设不妨设 为孤立点，为孤立点，又不妨设又不妨设 是（是（*）在第）在第i1 1行上唯一的变量，这时由行上唯一的变量，这时由p pijij的特征，（的特征，（1 1）的左端第）的左端第i1个分量和个分量和为k1，而右端，而右端为0，在第在第 j1列上的唯一列上的唯一变量如何？量如何？但但 仍不包含仍不包含闭回路，其中回路，其中还有孤立点有孤立点,与前面与前面类似分析可似分析可证 k2=0.同理得同理得 k3=k4=kr=0这就就证明了向量明了向量组（*）线性无关性无关.第14页，本讲稿共44页1 运输问题及其数学模型推论推论 2 2 平衡运平衡运输问题中的一中的一组 m+n-1 个个变量量能构成基能构成基变量的充要条件是它不包含任何量的充要条件是它不包含任何闭回路回路.该推推论给出了运出了运输问题的基可行解中基的基可行解中基变量的一量的一个基本特征：基个基本特征：基变量量组不含不含闭回路回路.这就是基可行解就是基可行解在表上的一个表在表上的一个表现，利用它来判断，利用它来判断 m+n 1 个个变量量是否构成基是否构成基变量量组，就看它是否包含，就看它是否包含闭回路回路.这种方法种方法简便易行，它比直接判断便易行，它比直接判断这些些变量量对应的列向量是否的列向量是否线性无关要性无关要简便得多便得多.利用基利用基变量的量的这个特征，将可以个特征，将可以导出求平衡运出求平衡运输问题的初始基可行解的一些的初始基可行解的一些简便方法便方法.第15页，本讲稿共44页2 运输问题的表上作业法2 2 运输问题的表上作业法运输问题的表上作业法 表上作表上作业法（又称运法（又称运输单纯形法）是根据形法）是根据单纯形形法的原理和运法的原理和运输问题的特点，的特点，设计的一种在表上运算的一种在表上运算的求解运的求解运输问题的的简便而有效的方法便而有效的方法.主要步主要步骤：1、求一个初始求一个初始调运方案（初始基可行解）；运方案（初始基可行解）；2、判判别当前方案是否当前方案是否为最最优，若是，若是则迭代停止，否迭代停止，否则 转下一步；下一步；3、改改进当前方案，得到新的方案（新的基可行解），当前方案，得到新的方案（新的基可行解），再返回再返回 2。第16页，本讲稿共44页 运输问题一、初始方案的确定一、初始方案的确定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex.1 50 已知某商品有三个已知某商品有三个产地地A1、A2、A3和四个和四个销地地B1、B2、B3、B4 ，产量、量、销量及量及单位运价如表位运价如表.问应如何如何调运，在运，在满足各足各销地需要的情况下，使地需要的情况下，使总的运的运费支出支出为最少？最少？解：解：5101020235规则:从运从运输表的西表的西北角开始北角开始,优先安排先安排编号小的号小的产地和地和销地地的运的运输任任务.填了几个数字？填了几个数字？Note:在填入一个数在填入一个数时，如果行和列同，如果行和列同时饱和，和，规定只划去一行或一列定只划去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15500第17页，本讲稿共44页2 运输问题的表上作业法2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15规则:优先安排先安排单位运价最小的位运价最小的产地与地与销地之地之间的运的运输 任任务.40102551010Note:在某行（或列）填入最后一个数在某行（或列）填入最后一个数时，如果行和，如果行和列同列同时饱和，和，规定只划去定只划去该行（或列）行（或列）BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字？填了几个数字？第18页，本讲稿共44页 运输问题定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡运运输问题的基可行解，的基可行解，m+n-1 个个填入数字的格子填入数字的格子对应的的是基是基变量量.Proof:首先，得到的初始解首先，得到的初始解 为可行解是显然的为可行解是显然的.其次，由于行列数共有其次，由于行列数共有 m+n，而按填数字的方法，而按填数字的方法,除填最后一个数除填最后一个数时，划去一行一列外，每填一个数划去，划去一行一列外，每填一个数划去一行或一列一行或一列.因此因此,共填共填 m+n-1 个数个数.最后，最后，证明所填明所填 m+n-1 个数个数对应的的变量量组不含不含闭回路回路.用反用反证法法若含有若含有闭回路回路 不妨不妨设此此闭回路如右回路如右（其他情形同理可（其他情形同理可证）不妨不妨设填填 后划去行，故后划去行，故 必必须较 先填，先填，且填后划去的是列，从而且填后划去的是列，从而 必必须较 先填，且填后划先填，且填后划去的是行，而去的是行，而这又又说明明 必必须较 先填，且填后划先填，且填后划去的是列，去的是列，这又得到又得到 必必须较 先填，且填后划去的先填，且填后划去的是行，是行，这样就得到了矛盾，所以，填数的就得到了矛盾，所以，填数的 m+nm+n-1-1 个格个格子子对应的的变量量组不含不含闭回路，从而，回路，从而，证得了本定理得了本定理.第19页，本讲稿共44页2 运输问题的表上作业法关关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路；不产生闭回路；2、填一个数字填一个数字只只划去一行或一列划去一行或一列 填满填满m+n-1-1个数个数.BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 按最小元素法按最小元素法3423、Vogel 法法 (元素差元素差额法法)规则：计算各行各列的最小元素与次小元素的差算各行各列的最小元素与次小元素的差额，优先安排差先安排差额最大的所最大的所在行或列的在行或列的单位运价最位运价最小的小的产地与地与销地之地之间的的运运输任任务第20页，本讲稿共44页 运输问题二、最二、最优性性检验 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 设 是平衡运是平衡运输问题的的一一组基基变量，量，是非基是非基变量，量，则在在变量量组 中存在唯一的中存在唯一的闭回路回路.1、闭回路法回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3检验数表数表-5-10 6 6 6第21页，本讲稿共44页2 运输问题的表上作业法2、位位势法（法（对偶偶变量法）量法）求求检验数的数的方法方法约束方程的系数矩束方程的系数矩阵的秩的秩为m+n-1x0必必为基基变量量,x0=0约束方程的系数矩束方程的系数矩阵的秩的秩为m+n对任意的任意的 a0，与原与原问题等价等价由于由于xj 的的检验数数 设：为基基变量，由于基量，由于基变量量的的检验数等于零数等于零有解，不唯一有解，不唯一ui 称称为行位行位势，vj 称称为行位行位势第22页，本讲稿共44页 运输问题 BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3检验数表数表-5-10 6 6 6-2-120273见 Ex.1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解10053-12-5 若若 ，则此时的运输方案为最优的，则此时的运输方案为最优的第23页，本讲稿共44页2 运输问题的表上作业法三、基可行解的改三、基可行解的改进 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3检验数表数表-5-10 6 6 6选择进基基变量量则取非基取非基变量量 xst 为进基基变量量确定出基确定出基变量量调整量整量则基基变量量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在整方法：在该闭回路上，奇点运量加回路上，奇点运量加 ，偶点减去，偶点减去 能能转运多少？运多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因为因为 ，所以此运输方案为最优，所以此运输方案为最优方案方案Note:若在若在闭回路上有几个偶点回路上有几个偶点处的运量等于的运量等于 ，则可任取其中一个作可任取其中一个作为出基出基变量（运量擦去），其余几量（运量擦去），其余几个点的个点的值调整后整后变为0.(0.(但但应填入，填入，说明明这些些变量量还在基内，在基内，这时就出就出现了退化了退化)问：从从A2到到B4的的单位运价位运价c24在什么范在什么范围变化化时，所得，所得最最优调运方案不运方案不变.c12在什么范在什么范围变化呢？化呢？第24页，本讲稿共44页四、四、踏石法踏石法1)、找入变量、找入变量l从从 中找最小者，对应中找最小者，对应 xij 就是入就是入变量变量2)、以、以 非基变量非基变量xij 为起点，寻找由原基变量构成的为起点，寻找由原基变量构成的闭合回路闭合回路l该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量因此，闭合回路中必有偶数个变量(包括包括 xij)，且回路中每行每，且回路中每行每列只有两个变量列只有两个变量3)、求入基变量、求入基变量 xij 的最大值及新基变量的解的最大值及新基变量的解l从从 xij出发，沿任一个方向对回路拐角上的基变量依此标出发，沿任一个方向对回路拐角上的基变量依此标“”和和“+”，表示表示“”和和“+”xij，从而迭代后仍满足分配的平衡，从而迭代后仍满足分配的平衡l标有标有“”的变量中最小者就是的变量中最小者就是出基变量出基变量，对应，对应xij*的值就是所的值就是所求入基变求入基变量量 xij 的最大值。的最大值。l标有标有“”的变量减去的变量减去 xij*，标有标有“+”的变量加上的变量加上 xij*4)、用位势法求新基变量的检验数、用位势法求新基变量的检验数l若所有若所有 ，则达到最，则达到最优，算法停止；优，算法停止；否则返回否则返回 1）。）。第25页，本讲稿共44页 补充补充 例题例题 踏石法，以最低费用法所得初始解开始（注意：对基变量踏石法，以最低费用法所得初始解开始（注意：对基变量xij有：有：cij=ui+vj，任取一个任取一个ui或或vj=0，计算出，计算出ui、vj)所有所有 cij (ui+vj)=0，达到最优。，达到最优。答：最优解如上分配表，答：最优解如上分配表，OBJ=98OBJ=121OBJ=101第26页，本讲稿共44页五、五、运输问题迭代中的一些具体问题运输问题迭代中的一些具体问题 1)闭合回路的画法闭合回路的画法l从从入基入基变量变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法它基变量，则返回上一拐角，换一个方向走，采用深探法l闭合回路不一定是矩形闭合回路不一定是矩形 2)产销不平衡产销不平衡l供过于求，即供过于求，即 ai bj，增加一个虚收点增加一个虚收点Dn+1，bn+1=ai-bj,令令 wi,n+1=0,i=1,2,ml供小于求，即供小于求，即 ai bj，增加一个虚发点增加一个虚发点Wm+1，am+1=bj-ai,令令 wm+1,j=0,j=1,2,n 3)关于退化问题关于退化问题(1)、初始解退化初始解退化。即初始基变量的个数少于。即初始基变量的个数少于m+n 1。必须补足基变量。必须补足基变量的个数，否则不能正常解出的个数，否则不能正常解出m+n个个ui和和 vjl所补基变量的值为所补基变量的值为 0，补充的原则：，补充的原则：(1)尽量先选运费小的实变量；尽量先选运费小的实变量；(2)补充后不补充后不能有某个基变量独占一行一列能有某个基变量独占一行一列第27页，本讲稿共44页六、六、关于退化问题关于退化问题(2)、迭代过程中出现退化迭代过程中出现退化l闭合回路中标有闭合回路中标有“”的基变量同时有多个达到最小的基变量同时有多个达到最小l变换后，有多个原基变量变为变换后，有多个原基变量变为 0，选运费最大者为出，选运费最大者为出基基变量，其余保留变量，其余保留在新的基础解中在新的基础解中l退化较严重时，可能会出现多次迭代只有值为退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。的基变量在转移。此时，一要耐心，二要正确选择出变量此时，一要耐心，二要正确选择出变量踏石法迭代中需注意的问题：踏石法迭代中需注意的问题：(1)、错误地将分配表中基变量的解代入到运费表中、错误地将分配表中基变量的解代入到运费表中(2)、不能正确画闭合回路、不能正确画闭合回路(3)、初始解退化，未能补足基变量的个数初始解退化，未能补足基变量的个数。因此在位势法中多次。因此在位势法中多次令某个令某个ui或或 vj为为 0；(4)、在位势法中只能令一个在位势法中只能令一个 ui 或或 vj 为为 0；若不能求出全部；若不能求出全部 ui和和 vj，说明基变量未选够数或未选对，说明基变量未选够数或未选对第28页，本讲稿共44页 运输问题七、七、补充：运输问题的图上作业法补充：运输问题的图上作业法 图上作上作业法是在交通法是在交通图上上进行物行物资调运方案运方案编制和制和调整的一种科学方法。在整的一种科学方法。在铁路特路特别是公路运是公路运输中使用很中使用很多且有很好的效果。多且有很好的效果。在交通在交通图中，用中，用表示表示产地（地（发点），并将点），并将产量量记在在圆圈内；用圈内；用表示表示销地地（收点），并将（收点），并将销量量记在方在方框内。框内。206040402463目目标：吨公里数：吨公里数(费用用)最小的最小的调运方案运方案 .物物资调运的流向用与交通运的流向用与交通线平行的箭平行的箭线表示，表示，规定定画在前画在前进方向的右方向的右边，调运量加括号运量加括号记在箭在箭线的右的右边。(20)(20)(40)第29页，本讲稿共44页补充：运输问题的图上作业法20303020243对流：物流：物资在同一在同一线路上往返运路上往返运输.(20)(20)(30)(30)(10)这是是对流流20303020243(20)(20)(30)(30)106030(10)(20)1、无圈无圈的交通的交通图2020502010 对于无圈于无圈图，每条，每条边都是割都是割边，去掉它网，去掉它网络将不将不连通，所以，每通，所以，每条条边上的运量是不得不上的运量是不得不只要每条只要每条边上不上不产生生对流，即流，即为最最优方案方案第30页，本讲稿共44页 运输问题206040402463(20)(20)(40)2、有一个圈的交通有一个圈的交通图圈圈长：圈上每一条：圈上每一条边的的长度之和（度之和（记为 l）l=15 先用先用“丢边破圈破圈”方法，得到无圈方法，得到无圈图，再，再产生一生一个个没有没有对流的方案。流的方案。内圈内圈长 l内内：流向在圈内的：流向在圈内的边的的长度之和度之和l内内=8外圈外圈长 l外外：流向在圈外的：流向在圈外的边的的长度之和度之和l外外=4是最是最优解解码？称称为迂回迂回调整方案：整方案：对内圈各流量中最小内圈各流量中最小调运量，运量，进行反向行反向调运运(40)(20)(20)结论：内外圈内外圈长都小于圈都小于圈长的一半的无的一半的无对流的流的调运方案运方案 为最最优方案方案第31页，本讲稿共44页补充：运输问题的图上作业法3、有多个、有多个圈圈的交通的交通图106030202050203020有几个圈？如有一个圈的情形，如有一个圈的情形，对每一个圈先用每一个圈先用“丢边破圈破圈”方方法，得到无圈法，得到无圈图，再，再产生一个没有生一个没有对流的方案。再流的方案。再进行行检查、调整。整。只需检查13个圈吗？会循环吗？一般不一般不够！因！因为对一个圈一个圈进行行调整后，会整后，会对已已检查的圈有影响的圈有影响.不会！因不会！因为每次目每次目标函数下降函数下降值大于一个固定大于一个固定值（如（如 1）第32页，本讲稿共44页 运输问题4、产销不平衡运不平衡运输问题当当Note:通常建立运通常建立运输模模型指的是平衡运型指的是平衡运输模型模型可以虚可以虚设一个一个产地地 Am+1,其其产量量为 并假并假设产地地 Am+1 运往各运往各销地的地的单位运价位运价为 cm+1,j=0(j=1,2,n).则原原问题可可转化化为平衡运平衡运输问题：产大于大于销，可通，可通过虚虚设销地，地，类似似建立平衡运建立平衡运输模型模型第33页，本讲稿共44页2 运输问题的表上作业法Ex.2已知运已知运输问题由表由表给出，出，试建立运建立运输模型模型.Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解:Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本本题产量量为25，销量量为29，是，是销大于大于产问题 虚虚设一个一个产地地 A3，由于并没有生，由于并没有生产，所以运价，所以运价为零，得运零，得运输模型模型.如果各如果各销地不地不满足足时，单位缺位缺货费为 4，3，7，则运运输模型模型为437第34页，本讲稿共44页 运输问题 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex.3 已知运已知运输问题由表由表给出，如果出，如果产地地 Ai 的的产量量必必须运走运走，试建立运建立运输模型模型.BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解解:这是一个是一个产大于大于销的运的运输问题.234虚虚设一一销地地 B4,销量量 b4=15.BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10 最高最高需求量需求量 20 10不限不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三个三个销地的最低需求地的最低需求为 30，最高需求不限最高需求不限.根据根据现有有产量，量，B3 至多能得到至多能得到 25.建立运建立运输模型模型 .2说明什么？明什么？第35页，本讲稿共44页 运输问题3 运输问题应用举例运输问题应用举例Ex.4 (生生产调度度问题)某制冰厂每年某制冰厂每年1 4 季度必季度必须供供应并并块 15、20、25、10（千吨）（千吨）.已知已知该厂各季度冰厂各季度冰 块的生的生产能力及冰能力及冰块的的单位成本如表位成本如表.如果生如果生产出来出来的冰的冰块不在当季度使用，每千吨冰不在当季度使用，每千吨冰块存存储一个季度一个季度费用用为4（千元）（千元）.又又设该制冰厂每年第制冰厂每年第3季度末季度末对贮冰冰库进行清行清库维修修.问应如何安排冰如何安排冰块的生的生产，可使，可使该厂全年生厂全年生产、存存储费用最少？用最少？季季 度度 生产能力（千吨）生产能力（千吨）单位成本（千元）单位成本（千元）1 25 5 2 18 7 3 16 8 4 15 5第36页，本讲稿共44页3 运输问题应用举例季季 度度 生产能力（千吨）生产能力（千吨）单位成本（千元）单位成本（千元）1 25 5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：解：5B54913M0MMMMM0005118179137第37页，本讲稿共44页 运输问题Ex.5 (运量有界的运运量有界的运输问题)6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 表表1 给出一个运出一个运输问题.现在在规定定产地地 Ai 至至销地地 Bj 的运量不能超的运量不能超过 dij,由表由表 2 2 给定定.试建立运建立运输问题 .解解：虚虚设 Dij(i=1,2;j=1,2,3)6 6个点，个点，Dij 既作既作产地，地，又作又作销地，其地，其产量、量、销量都量都为 dij .产地地 Ai 的物的物资只可只可运送运送给 Dij,而而 Dij 的物的物资只可运送只可运送给 Bj,或送或送给自身自身.第38页，本讲稿共44页3 运输问题应用举例 BjAi D11 D12 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 8 104330000305040000206074334254257563321303124244214第39页，本讲稿共44页 运输问题Ex.6 (空空车调度度问题)某航运公司承担六个港口城市某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航的四条固定航线的物的物资运运输任任务.已知各条航已知各条航线的起点、的起点、终点城市及每天航班数点城市及每天航班数见表表1，假定各条航，假定各条航线使用相同型号的船只，又各城市使用相同型号的船只，又各城市间的航程天数的航程天数见表表2.又知每条船只每次装卸又知每条船只每次装卸货的的时间各各需一天，需一天，则该航运公司至少航运公司至少应配配备多少条船，才能多少条船，才能满足足所有航所有航线的运的运货需求？需求？航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表表2 2第40页，本讲稿共44页3 运输问题应用举例解解：该公司所需配公司所需配备船只分两部分船只分两部分.1 1、载货航程需要的周航程需要的周转船只数船只数航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表表2 2 如航如航线1，在港口，在港口E 装装货1 天，天，E 至至 D 航程航程17天，天，在在D 卸卸货1天，天，总计19天天.每天每天3 航班，故航班，故该航航线周周转船只需船只需5757条条.航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数需周转船只数需周转船只数11171193572131521031719194113115115累累计共需周共需周转船只数船只数91条条.第41页，本讲稿共44页 运输问题2 2、各港口、各港口间调度所需船只数度所需船只数港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101 港口每天到达与需要的船只不同，如表港口每天到达与需要的船只不同，如表.为使配使配备船只数最少，船只数最少，应做到周做到周转的空船数的空船数为最少最少.建立运建立运输模型，模型，C、D、F 为空船的空船的产地地，A、B、E 为销地，地，单位运价位运价为相相应各港口之各港口之间的船只航程天数的船只航程天数.港港 口口 A B E每天多余船只每天多余船只 C2 35 2 D141317 2 F783 1每天缺少船只每天缺少船只 1 1 311111 用表上作用表上作业法法求出空船的最求出空船的最优调度方案度方案.最少需周最少需周转的的空船数空船数为40条条.所以，在不考所以，在不考虑维修、修、储备等情况下，等情况下，该公司至公司至少少应配配备131条船条船.第42页，本讲稿共44页3 运输问题应用举例Ex.7 (运运输问题悖悖论)paradox 在运在运输问题中，有一种在若干个中，有一种在若干个产销地运价不地运价不变的的情况下，当情况下，当调运量增加了，运量增加了，总运运费反而会下降的奇怪反而会下降的奇怪现象象 .Bj Ai B1 B2 B3 B4 B5 ai A11415 61314 7 A2169221316 18 A3851145 6 A412418910 15 bj 4 11 12 8 11746851510 如下面的运如下面的运输问题，总调运量运量46单位，最位，最优总费用用444单位位.现在在总产量和量和总销量各增加量各增加10单位，位，单位位运价不运价不变，总费用将用将如何？如何？12112112 46 8011150运量运量为56,最最优总费用用为409单位位.怎么会怎么会产生呢？生呢？产生生负费用路用路多品种物多品种物资运运输问题、转运运问题、车(船船)调度度问题等等第43页，本讲稿共44页 运输问题 运输问题运输问题 完完第44页，本讲稿共44页