第3章运输问题11-04-11

1、第三章第三章 运输问题运输问题北京物资学院信息学院北京物资学院信息学院北京物资学院运筹学教学课件北京物资学院运筹学教学课件本章主要内容本章主要内容第一节第一节 运输问题的数学模型及其特征运输问题的数学模型及其特征第二节第二节 运输问题的求解运输问题的求解表上作业法表上作业法第三节第三节 产销不平衡的运输问题及应用产销不平衡的运输问题及应用第一节第一节 运输问题的数学模型及其特征运输问题的数学模型及其特征 运输问题的定义运输问题的定义 运输问题的数学模型运输问题的数学模型 运输问题的特征运输问题的特征1. 1. 运输问题的定义运输问题的定义例例1 1： 某集团新购进一批钢材，分别存储在三个仓库，

2、现在某集团新购进一批钢材，分别存储在三个仓库，现在要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所需的费用见下表，问如何调运才能使总运费降到最低？需的费用见下表，问如何调运才能使总运费降到最低？工厂工厂B1工厂工厂B2工厂工厂B3工厂工厂B4库存量库存量仓库仓库A1291079仓库仓库A213425仓库仓库A384257需求量需求量3846运输问题：运输问题：有有m个供应点向个供应点向n个需求点供应某种物资，这个需求点供应某种物资，

3、这m个供应点个供应点A1、A2、.Am的供应量分别为的供应量分别为a1、a2、.am；n个需求点个需求点B1、B2、.Bn的需求量分别为的需求量分别为b1、b2、.bn；已已知从任一供应点知从任一供应点Ai向任一需求点向任一需求点Bj运输一个单位物资的费用运输一个单位物资的费用为为cij。问采取什么样的物资调运方案才能使总运费最省？问采取什么样的物资调运方案才能使总运费最省？B1B2Bn供应量供应量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam需求量需求量b1b2bn2. 2. 运输问题的数学模型运输问题的数学模型1111min(1,2,.). .(1,2,.

4、)0,1,2,.,1,2,.mnijijijnijijmijjiijzc xxaims txbjnxim jn 11mnijijab （其其中中）运输问题的约束方程组系数矩阵及特征运输问题的约束方程组系数矩阵及特征11121212221211.111.1.11.111111.1111nnmmmnxxxxxxxxxA 矩阵矩阵A是一个是一个m+n行行mn列的矩阵，它的秩不超过列的矩阵，它的秩不超过m+n-1。运输问题一般有运输问题一般有m+n-1个基变量。个基变量。系数矩阵非常稀疏。系数矩阵非常稀疏。 xij的系数列向量为：的系数列向量为：m行n行(0.1.0.1.0)TijimjPee 3.

5、运输问题的特征运输问题的特征特征特征1：运输问题一定有可行解；运输问题一定有可行解；特征特征2：运输问题一定有最优解；运输问题一定有最优解；特征特征3：运输问题每一组基对应运输问题每一组基对应 m+n-1个基变量；个基变量；特征特征4：运输问题的运输问题的 m+n-1个基变量构成的变量组不含个基变量构成的变量组不含闭回路闭回路；特征特征5：任意一个非基变量和任意一个非基变量和 m+n-1个基变量组成的变个基变量组成的变量组中必定存在一条并且只存在唯一一条闭回路；量组中必定存在一条并且只存在唯一一条闭回路； 特征特征6：如果运输问题中的供应量和需求量都是整数，如果运输问题中的供应量和需求量都是整

6、数，则任一基解中各变量的取值也都是整数。则任一基解中各变量的取值也都是整数。 闭回路闭回路定义：凡是能够排列成下列序列的一组变量的集合就定义：凡是能够排列成下列序列的一组变量的集合就称为运输问题的一个闭回路。称为运输问题的一个闭回路。1 12 12 23 21,s ssi ji ji ji ji ji jxxxxxx并称集合中每一个变量为此闭回路的一个并称集合中每一个变量为此闭回路的一个顶点顶点；称连；称连接相邻两个变量（顶点）以及连接最后一个顶点和第接相邻两个变量（顶点）以及连接最后一个顶点和第一个顶点的线段为此闭回路的一个顶点的线段为此闭回路的边边。或或1 11 22 22 31,s ss

7、i ji ji ji ji ji jxxxxxxB1B2B3B4B5A1A2A3A4X45X41X31X33X13X15B1B2B3B4B5A1A2A3A4X34X32X14X12B1B2B3B4B5A1A2A3A4X35X41X31X43X13X15B1B2B3B4B5A1A2A3A4X11X12X22X24X44X42X21（1 1）每个顶点都是转折点；）每个顶点都是转折点；（2 2）闭回路是一条闭合的折线，每一条边都是水）闭回路是一条闭合的折线，每一条边都是水平或垂直的；平或垂直的；（3 3）闭回路上同一行（列）的顶点有偶数个。）闭回路上同一行（列）的顶点有偶数个。闭回路上的点对应的系数

8、列向量线性相关。闭回路上的点对应的系数列向量线性相关。PijPikPlkPlsPusPujijimjPee 0ijiklklsusujPPPPPP 由于由于容易证明容易证明第二节第二节 运输问题的求解运输问题的求解-表上作业法表上作业法第四步：确定进基变量和出基变量，调整非最优的调运第四步：确定进基变量和出基变量，调整非最优的调运方案，获得更好的调运方案；方案，获得更好的调运方案；转第二步。转第二步。表上作业法的基本步骤：表上作业法的基本步骤：第一步：编制初始调运方案，即寻找第一个基可行解；第一步：编制初始调运方案，即寻找第一个基可行解；第二步：计算各非基变量的检验数；第二步：计算各非基变量的

9、检验数；第三步：判断当前的调运方案是否是最优方案，如果已经第三步：判断当前的调运方案是否是最优方案，如果已经是最优，则算法结束，问题已经解决；否则，转第四步；是最优，则算法结束，问题已经解决；否则，转第四步；第一步：编制初始调运方案第一步：编制初始调运方案要求得运输问题的初始基可行解，必须保证找到要求得运输问题的初始基可行解，必须保证找到 m+n1 个基变量个基变量.运输问题的任意运输问题的任意m+n-1个变量构成一组基变量的充要条个变量构成一组基变量的充要条件是变量组中不含闭回路件是变量组中不含闭回路.关键关键:找出找出m+n-1个不含闭回路的变量。个不含闭回路的变量。西北角法（左上角法）西

10、北角法（左上角法）最小元素法最小元素法Vogel 法法问题：如何使得一个选定的变量不包含在闭回路中问题：如何使得一个选定的变量不包含在闭回路中？B1B2B3B4库存量库存量A1291079A213425A384257需求量需求量3846623163对应的总运费为对应的总运费为 C 1= 23 + 93 + 96 + 36 + 32 + 42 + 43 + 23 + 21 + 51 + 56 = 1106 = 110西北角法西北角法( (左上角法左上角法) )-3-3-6-6-2-2 -3-3-1-1 -6-6最小元素最小元素法法B1B2B3B4库存量库存量A1291079A213425A384

11、257需求量需求量3846523443对应的总运费为对应的总运费为 C 2= 95 + 75 + 74 + 14 + 13 + 23 + 22 + 42 + 43 + 23 + 24 = 1004 = 100-3-3-4-4-2-2-3-3-4-4-5-5Vogel 法法B1B2B3B4库存量库存量A1291079A213425A384257需求量需求量3846154533对应的总运费为对应的总运费为 C 2= 23 + 93 + 95 + 75 + 71 + 21 + 25 + 45 + 43 + 23 + 24 =884 =88-3-3-1-1-5-5-3-3-5-5-4-4B1B2B3B

12、4供应量供应量A178143A226535A314278需求量需求量2176105262退化情况的处理退化情况的处理-2-2-1-1-5-5-2-2-6-6用西北角法求下列运输问题的第一个基可行解用西北角法求下列运输问题的第一个基可行解B1B2B3供应量供应量A11842A25251A35737需求量需求量217172-2-2-1-1-7-7注意：每次只能划去一行或一列，不能同时划去行和列。注意：每次只能划去一行或一列，不能同时划去行和列。当只剩下一行（列）时，只能划去列（行）。当只剩下一行（列）时，只能划去列（行）。想一想：为什么？想一想：为什么？00用最小元素法求下列运输问题的第一个基可行

13、解用最小元素法求下列运输问题的第一个基可行解第二步：计算各非基变量的检验数第二步：计算各非基变量的检验数1. 1. 闭回路法闭回路法；2. 2. 位势法。位势法。检验数的定义：检验数的定义：非基变量的取值每增加非基变量的取值每增加1 1时，总运费的时，总运费的 增加量。增加量。运输问题的最优性条件：运输问题的最优性条件：检验数非负检验数非负1. 1. 闭回路法闭回路法基变量不含闭回路，但任何一个非基变量都可以与基变基变量不含闭回路，但任何一个非基变量都可以与基变量构成唯一一条闭回路量构成唯一一条闭回路B1B2B3B4库存量库存量A1291079A213425A384257需求量需求量38466

14、23163141412222333347934256cccccc 含义：含义：x14 每增加一个单位，总运费增加每增加一个单位，总运费增加-6个单位个单位+1+1+1-1-1-1623163所有非基变量的检验数见上表所有非基变量的检验数见上表B1B2B3B4库存量库存量A12910790-6A2134255-5A384257143需求需求量量38462. 2. 位势法位势法位势位势：运输问题的对偶变量称为位势。：运输问题的对偶变量称为位势。因为因为m个供应点个供应点n个需求点的运输问题有个需求点的运输问题有m+n个约束，个约束，因此运输问题就有因此运输问题就有m+n个位势。个位势。 行位势行位

15、势:关于供应点关于供应点Ai的约束对应的对偶变量，记为的约束对应的对偶变量，记为 ui, i=1,2,m。列位势列位势:关于需求点关于需求点Bj的约束对应的对偶变量，记为的约束对应的对偶变量，记为vj, j = 1,2,n。 定理定理：运输问题变量运输问题变量xij的检验数的检验数ijijijcuv 11101(,.,.)10ijijBijijmnijijcC B Pcuuvvcuv 证明：证明：位势及检验数的求法位势及检验数的求法由于基变量的检验数为由于基变量的检验数为0，所以可以利用，所以可以利用m+n-1 个基变个基变量求出位势量求出位势B1B2B3B4库存量库存量A1291079A21

16、3425 A384257需求量需求量3846623163029-610-8130-65-5143第四步：调整调运方案第四步：调整调运方案1. 1. 确定入基变量：选取最小负检验数对应的非基变量确定入基变量：选取最小负检验数对应的非基变量入基入基2. 2. 确定出基变量和调整量确定出基变量和调整量将进基变量对应的闭回路中的顶点分为将进基变量对应的闭回路中的顶点分为奇顶点奇顶点和和偶顶点偶顶点，令令= min 闭回路上所有偶顶点对应的运量闭回路上所有偶顶点对应的运量xij 则则即为调即为调整量，选取一个运量等于整量，选取一个运量等于的偶顶点为出基变量。的偶顶点为出基变量。3.调整：闭回路上奇顶点上

17、的运量增加调整：闭回路上奇顶点上的运量增加，偶顶点上的运偶顶点上的运量减少量减少。闭回路以外顶点的运量不变。闭回路以外顶点的运量不变。上例中：若选上例中：若选x14进基，进基，则则 =min6,3,6=3, 出基变量为出基变量为x23,调整后得：调整后得：B1B2B3B4库存库存量量A12910790-6A2134255-5A384257143需求量需求量3846623163总运费：总运费： C = 23 + 93 + 73 + 35 + 24 + 53 = 92 110 x32进基，则进基，则 =min3,3=3, 出基变量选出基变量选x34,调整调整后得：后得：B1B2B3B4库存量库存量

18、A1291079A213425A384257需求需求量量38463543330-6-2294756618-3检验数全部非负，已经是最优调运方案；检验数全部非负，已经是最优调运方案；总费用总费用C*= 23 + 90 + 76 + 35 + 43 + 24 = 83 B1B2B3B4库存量库存量A1291079A213425A384257需求量需求量38460543360-6-529773531113表上作业法计算中应注意的问题表上作业法计算中应注意的问题1.1.解的情况解的情况 唯一：唯一：非基变量检验数全部大于非基变量检验数全部大于0 0； 无穷多解：无穷多解：至少存在一个非基变量检验数等于

19、至少存在一个非基变量检验数等于0 0。2.退化情况：退化情况：在确定初始基可行解的时候，当填在确定初始基可行解的时候，当填(i,j)格子时，格子时，若若ai=bj, 则则xij=ai=bj, 但此时只能划去一行或一列，但此时只能划去一行或一列，在后面的填充过程中相应格子要填在后面的填充过程中相应格子要填0。3.调整时，若闭回路上出现两个或两个以上偶顶点调整时，若闭回路上出现两个或两个以上偶顶点取值同时达到最小，只能选一个变量出基。取值同时达到最小，只能选一个变量出基。课堂练习课堂练习用表上作业法求解下列运输问题用表上作业法求解下列运输问题. .B1B2B3B4供应量供应量A13113107A2

20、19284A3741059需求量需求量3656B1B2B3B4供应量供应量A13113107A219284A3741059需求量需求量3656431363B1B2B3B4供应量供应量A13113107A219284A3741059需求量需求量36564313630310-12-59121-11012调整量为调整量为 min3,1=1，出基变量为出基变量为x23.B1B2B3B4供应量供应量 A13113107 A219284 A3741059需求量需求量3656531362最优解最优解: :1314212432345,2,3,1,6,3,03 51021 38 14 65385ijxxxxxx

21、xf 其其余余总总费费用用0310-23-590221912由于由于x11的检验数为的检验数为0，所以最优解不唯一。，所以最优解不唯一。B1B2B3B4供应量供应量 A13113107 A219284 A3741059需求量需求量36565133620310-23-592219120最优解最优解: :1113212432342,5,1,3,6,3,03 23 51 18 34 65 385ijxxxxxxxf 其其余余总总费费用用第三节第三节 产销不平衡的运输问题及应用产销不平衡的运输问题及应用表上作业法是以产销平衡为前提的：表上作业法是以产销平衡为前提的：11mnijijab 实际中，往往遇

22、到产销不平衡的运输问题实际中，往往遇到产销不平衡的运输问题1.1.产大于销（供过于求）产大于销（供过于求） 11mnijijab 2.2.销大于产（供不应求）销大于产（供不应求）11mnijijab 产销不平衡运输问题向产销平衡运输问题的转化产销不平衡运输问题向产销平衡运输问题的转化产大于销的运输问题：产大于销的运输问题：11mnijijab 1111min(1,2,.). .(1,2,. )0,1,2,.,1,2,.mnijijijnijijmijjiijzc xxaims txbjnxim jn 数学模型数学模型设设xi n+1 是产地是产地Ai 的储存量，化成标准形的储存量，化成标准形1

23、11111min(1,2,.). .(1,2,. ,1)0,1,2,.,1,2,.1mnijijijnijijmijjiijzc xxaims txbjn nxim jn 其中其中,11110,1,.i nmnnijijcimbab 引入一个虚拟的销地（需求量等于引入一个虚拟的销地（需求量等于 ），并），并令各个产地到虚拟销地的单位运费为令各个产地到虚拟销地的单位运费为0 0。11mnijijab 产小于销的运输问题：产小于销的运输问题：11mnijijab 引入一个虚拟的产地（产量等于引入一个虚拟的产地（产量等于 ），），并令该虚拟产地到各销地的单位运费为并令该虚拟产地到各销地的单位运费为0

24、 0。11nmjijiba 总供应量为总供应量为1919千吨，而总需求量为千吨，而总需求量为1515千吨千吨例例2： A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分四个城市。已知三个产地今年的蔬菜产量预计分别为别为7千吨、千吨、5千吨和千吨和7千吨；四个城市今年的蔬菜需求量分别千吨；四个城市今年的蔬菜需求量分别为为2千吨、千吨、3千吨、千吨、4千吨和千吨和6千吨；从每个蔬菜产地平均运输千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用千吨蔬菜到各个城市的单位费用(万元万元)见下表，你能否替

25、他见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？们编制一个总运费最省的蔬菜调运方案？ 单位运费单位运费B1B2B3B4供应量供应量A1211347A2103595A378127需求量需求量2346 需求地需求地生产地生产地B1B2B3B4B5供应量供应量A12113407A21035905A3781207需求量需求量2346400-220430825723343222387最优解中最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量。表示两个产地没有运出去的蔬菜量。假如例假如例2 2中各产地的蔬菜总产量不是中各产地的蔬菜总产量不是1919千吨，而是千吨，而是1212千吨，就

26、成了一个供不应求的运输问题。千吨，就成了一个供不应求的运输问题。 单位运费单位运费B1B2B3B4供应量供应量A1211343A2103594A378125需求量需求量2346 单位运费单位运费B1B2B3B4供应量供应量A1211344A2103593A378125A400003需求量需求量2346 引入一个虚拟产地引入一个虚拟产地例例3 3 设有三个化肥厂供应四个地区的农用化肥。假定等量的设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各个化肥厂到各地区单位化肥的运价如下表

27、区年需要量及从各个化肥厂到各地区单位化肥的运价如下表所示，试决定使总运费最省的化肥调拨方案。所示，试决定使总运费最省的化肥调拨方案。 需求地区需求地区化肥厂化肥厂IIIIIIIV产量产量（万吨）（万吨）A1613221750B1413191560C192023-50最低需求最低需求（万吨）（万吨）3070 010最高需求最高需求（万吨）（万吨）507030不限不限这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量160160万吨，四个万吨，四个地区的最低需求量为地区的最低需求量为110110万吨，最高需求为无限。根据现万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到有产量，第四个地区每年最多能分配