运筹学运输问题ppt课件讲义

1、第六章 运输问题 前面几章中，我们讨论了线性规划的一般形式及求解方法，对偶线性规划问题与灵敏度分析等问题。但在实际工作中，常常遇到很多线性规划问题，由于它们约束条件变量的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的方法求解，从而可以大量节约计算的时间和费用。本章讨论的运输问题就是这一类特殊的线性规划问题。结构安排第一节 运输问题的数学模型第二节 表上作业法第三节 产销不平衡的运输问题及应用 举例第一节 运输问题的数学模型 在社会经济生活中，经常会碰到大宗物资的调运问题。如煤、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网络，制定调运方案，将这些物资运到各消费地点，这样

2、调运的目的，不仅是要把这些物资供给各地消费，而且我们也希望调运的费用最省，这类问题就是所谓的运输问题。一、运输问题案例 例 ：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示，问应如何调运，使得总运输费最小？销地运费单价产地B1B2B3产量（件）A1646200A2655300销 量150150200 解：因为此问题中产量和销量都是500，所以这是一个产销平衡问题。 设xij表示从产地Ai调运到销地Bj的运输量 （i=1，2；j=1，2，3），例如，x12表示由A1调运到B2的物品数量，现将安排的运输量列表如下：

3、销地运费单价产地B1B2B3产量（件）A1x11x12x13200A2x21x22x23300销 量150150200500此运输问题的线性规划模型如下：二、运输问题的一般情形 假设某物资有m个产地 A1，A2，.，Am ， n个销地 B1，B2，.，Bn，已知这m个产地的产量为 a1，a2，.，am；n个销地的销量分别为 b1，b2，.，bn，从第i个产地到第j个销地的单位物资运价为cij,这些数据可用产销平衡表和单位运价表表示如下。产销平衡表销地产地B1B2.Bn 产量A1A2.Ama1a2.am销 量b1b2.bn单位运价表销地产地B1B2.BnA1A2.Amc11c21.cm1c12c

4、22.cm2.c1nc2n.cmn 若总产量等于总销量（产销平衡），试确定总运费最省的调运方案。建模：设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n。销地产地B1B2.Bn 产量A1A2.AmX11X21.Xm1X12X22 .Xm2.X1nX2n.Xmna1a2.am销 量b1b2.bn则运输问题的数学模型如下：显然，模型是具有mn个变量， m+n个约束的线性规划，可以用一般的单纯形法求解，但是当m与n较大时，模型的规模比较大，计算比较困难。为了进一步研究针对运输问题的特殊解法，下面考察它的约束系数矩阵。约束方程组的系数矩阵具有特殊的结构写出上式的系数矩阵A，形式如下：m

5、行n行矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行，ei+em+j。 将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。 容易证明，秩A=m+n-1。事实上，由于A的前m行之和等于后n行之和，因此，秩Am+n-1;又，取A的前m+n-1行，变量 对应的列所构成的A的子式为 由此易知，这个m+n-1阶子式的值为1或-1，所以，A的秩恰为m+n-1。可见运输问题的基可行解中，基变量的个数应为m+

6、n-1个。 根据运输问题数学模型结构上具有的上述特征，在前面所讲的单纯形方法的基础上，逐渐创造出一种专门用来求解运输问题线性规划模型的运输单纯形方法，一般称其为表上作业法。第二节 表上作业法 表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。 确定初始方案( 初 始 基本可行解) 改进调整（换基迭代）否 判定是否 最 优？是结 束最优方案下面通过例子介绍它的计算步骤。运输问题求解思路图一、初始方案的给定1、最小元素法2、Vogel法1、最小元素法 基本

7、思路是：就近供应，即从运价表中最小运价开始确定调运量，然后次小，一直到给出初始调运方案为止。 （1）找出运价表中最小元素 ，确定 ，若 ，则令 ，划掉运价表的第L行；反之，若 ，则令 ，划掉运价表的第k列。 （2）在运价表剩余元素中重复（1），直至运价表元素全部被划掉。 例：某糖果公司下设三个工厂，每日产量分别为：A1 7吨、A2 4吨、A3 9吨。该公司将这些产品运往四个门市部，各门市部每日销量为：B1 3吨、B2 6吨、B3 5吨、B4 6吨。各工厂到各门市部的单位运价如下表，试确定最优的运输方案。返回中间转运问题产销平衡表 销地产地 B1 B2 B3 B4产 量A1A2A3 749销 量

8、 3 6 5 6销地产地 B1 B2 B3 B4A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5单位运价表 314633注意： 有时选定最小元素后，发现该行的产地剩余产量恰好等于销地剩余销量。此时在产销平衡表上就必须划去一行和一列。此时为了保持数字个数仍然为m+n-1个。则必须在产销平衡表上划去的该行和该列的任意空格处填上数字“0”，如下表所示：Table1 产销平衡表 销地产地 B1 B2 B3 B4产 量A1A2A3749销 量 3 6 5 6销地产地 B1 B2 B3 B4A1A2A3 3 11 4 5 7 7 3 8 1 2 10 6Table2 单位运价表 362、

9、Vogel法基本思路是：从全局考虑。其方法是从运价表上分别找出每行与每列最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。 当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中的行或列，再重复上述步骤。直到找出最佳调运方案。Table3 产销平衡表 销地产地 B1 B2 B3 B4产 量A1A2A3749销 量 3 6 5 6Table4 单位运价表 销地产地B1 B2 B3 B4 两最小元素之差 A1A2A33 11 3 101 9 2 87 4 10 50 0 0 7 01 1 1 6 0 1 2两最小元素之差2 5 1 32 1 32 1 2 1 2

10、2365213二、最优性检验与方案的调整最小元素法和Vogel法给出的是一个基可行解，要确定该基可行解是否是最优解，还必须进行最优性检验。并进一步对方案进行调整。进行最优性检验的方法主要有闭回路法和位势法。1、闭回路法闭回路是指调运方案中由一个空格和若干个数字格的水平或垂直连线包围成的封闭回路。所谓的闭回路，就是从一个空格出发，沿水平方向或垂直方向前进，遇到合适的数字格后转90度，继续前进，如果能够回到出发点，则称这个封闭折线为闭回路。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。Table5 产销平衡表 3 6 5 6销 量749A1A2A3产

11、量 B1 B2 B3 B4销地产地365213练习： 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？（a） （b） （c） （d） （e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的； 表中的每一行和每一列由折线相连的闭回路的顶点只有两个；=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和） 闭回路法计算非基变量xij检验数的公式：Table6 运输方案闭回路表 销地产地 B1 B2 B3 B4产 量A1A2A3 4 3 3 1 6 3749销 量 3 6 5 6 -1 +1 -1 +1 3 11 3 10 1 9 2 8 7 4 10 5

12、A1A2A3 B1 B2 B3 B4销地产地Table2 单位运价表 1 2 1 -1 10 12A1A2A3 B1 B2 B3 B4销地产地Table7 检验数表 方案的调整 若最优性检验时某非基（空格Ai，Bj）xij的检验数为负，说明这个非基变量变为基变量时运费会更小，因而这个解不是最优解，还可以进一步调整改进。改进的具体步骤：（1）以xij为换入变量，找出它在运输表中的闭回路。（2）以空格（ Ai，Bj ）为第一个奇数，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。（3）在闭回路上的所有偶数顶点中，找出运输量最小的顶点，以该变量为换出变量。（4）以该变量为调整量，将该闭回

13、路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出以新的运输方案。 然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上的步骤继续进行调整，一直到得出最优解为止。Table8 运输方案调整表 销地产地 B1 B2 B3 B4产 量A1A2A3 4 3 3 1 6 3749销 量 3 6 5 6 -1 +1 -1 +1Table9 运输方案调整表 销地产地 B1 B2 B3 B4产 量A1A2A3 5 2 3 1 6 3749销 量 3 6 5 6Table10 新检验数表 销地产地 B1 B2 B3 B4A1A2A3 0 2 2 1 9 12 注意

14、:有时在闭回路调整中，在需要减少运量的地方有两个以上相等的最小数。这样调整时在原先空格处填上这个最小数，而有两个最小数的地方成了空格。此时只需把其中之一变为空格，其余均补添“0”，使方案中由数字格仍为m+n-1。（将为“0”的格当数字格看待）2、位势法闭回路法需要求每一个空格的检验数，这对于大型的运输问题来说显得非常复杂。位势法求检验数时，第一步需要将运输方案表（初始可行解）中的运输量（数字格）换上单位运价表中对应格的运价：销地产地 B1 B2 B3 B4产 量A1A2A3 4 3 3 1 6 3749销 量 3 6 5 6销地产地 B1 B2 B3 B4A1A2A3 3 10 1 2 4 5

15、Table11 运输方案表Table12 调运价格表 第二步在上表的右面和下面增加一行和一列，并新添上一些数字，使得表中的各个数恰好等于他所在行和列的这些新添写的数字之和。通常用ui(i=1,2,.,m)和vj(j=1,2,.,n)来代表这些新添数字。 ui和vj分别称为第i行和第j列的位势。 由于这些数字是相互关联的，填写时先决定其中的任意一个，再推导出其余位势的数值，如令v1=1，则有如下的位势表：再用闭回路法计算各空格的检验数，如（A3，B1）格的检验数：C31是空格（A3，B1）对应的运价表中的运价，u3+v1恰好是该空格所在行和列的位势，类似的，任意空格的检验数为：销地产地 B1 B

16、2 B3 B4uiA1A2A3 3 10 1 2 4 510-4vj 1 8 2 9+1Table13 位势表得到各空格处的检验数，经过对比可以发现，这与闭回路法计算结果相一致。销地产地 B1 B2 B3 B4A1A2A3 1 2 1 -1 10 12Table14 检验数表位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj） =（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和） 闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）表上作业法计算步骤框图分析实际问题列出产销平衡表和单

17、位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（闭回路法或位势法）所有检验数0找出绝对值最大的负检验数用闭回路调整，得出新方案得到最优方案算出总的运价是否三、表上作业法与单纯形法的比较（课后请大家进一步思考）初始基可行解的确定；最优性检验；确定入基变量；确定出基变量；迭代运算。表上作业法计算步骤、过程与单纯形法相同，但在具体计算时却不必画出单纯形表，而只需在产销平衡表上进行。四、多个最优方案的情形识别运输问题是否有多个最优解的方法与单纯形法一样，只需要看最优方案中是否有非基变量的检验数为零。如某个非基变量的检验数为零，可知此运输问题有多个最优解。此时只需要把检验数为零的非基变量作

18、为入基变量，调整运输方案，就可得到另一个最优方案。销地产地 B1 B2 B3 B4产 量A1A2A3 5 2 3 1 6 3749销 量 3 6 5 6销地产地 B1 B2 B3 B4A1A2A3 2 2 1 9 120+2-2-2+2检验数表最优方案调整表3 产销不平衡的运输问题及应用举例当产大于销 时，运输问题的数学模型可以写成： 由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地库存的问题。设 是产地 的库存量，于是有 例2 设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产

19、销地之间的单位运价表如下所示，试决定总运费最少的调运方案。销地产地 B1 B2 B3 B4A1A2A3 2 11 3 4 10 3 5 9 7 8 1 2Table 单位运价表Table5 产销平衡表 销地产地 B1 B2 B3 B4 库存产 量A1A2A3757销 量 2 3 4 6 4销地产地 B1 B2 B3 B4 库存A1A2A3 2 11 3 4 0 10 3 5 9 0 7 8 1 2 0Table6 单位运价表 总产量19，总销量15，产大于销销地产地 B1 B2 B3 B4 库存产 量A1A2A3 2 3 2 3 2 4 3757销 量 2 3 4 6 4Table18 运输方

20、案表 例3 设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区的需要量及从各化肥厂到各地区的单位运价表如下所示，试决定总运费最少的调运方案。Table 单位运价和产销量表需求地区化肥厂 产量（万t）ABC 16 13 22 17 14 13 19 15 19 20 23 506050最低需求（万t）最高需求（万t） 30 70 0 10 50 70 30 不限Table 产销平衡表 销地产地 产 量ABCD50605050销 量 30 20 70 30 10 50Table 单位运价表 最高需求为210万t，大于产量，增加一假想产地销地产地

21、ABCD 16 16 13 22 17 17 14 14 13 19 15 15 19 19 20 23 M M M 0 M 0 M 0不能由某地提供由假想产地提供，满足不满足均可Table 运输方案表销地产地 产 量ABCD 50 20 10 30 30 20 0 30 2050605050销 量 30 20 70 30 10 50Min 16x11+13x12+22x13+17x14+14x21+13x22+19x23+15x24+19x31+20 x32+23x33+1000 x34StX11+x12+x13+x14=50X21+x22+x23+x24=60X31+x32+x33+x34

22、=50X11+x21+x31=30X11+x21+x31=50X12+x22+x32=70X13+x23+x33=10end 例4 （中间转运问题）在典例中，如果假定：每个工厂生产的糖果不一定直接发送到销售点，可以将其中几个产地的糖果集中一起运；运往各销地的糖果可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还有几个转运站，在产地之间、销地之间或产销地之间转运。已知各产地、销地、中间转运站及相互之间每吨糖果的运价如下表，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的糖果运往销售地，使总的运费最少？产地中间装运站销地A1 A2 A3T1 T2

23、 T3 T4B1 B2 B3 B4产地A1A2A3 1 3 1 3 2 1 4 3 3 5 2 1 2 3 3 11 3 10 1 9 2 8 7 4 10 5中间转运站T1T2T3T4 2 3 1 1 5 4 2 3 2 3 1 3 2 1 1 1 3 1 2 2 1 2 2 8 4 6 4 5 2 7 1 8 2 4 1 2 6销地B1B2B3B4 3 1 7 11 9 4 3 2 10 10 8 5 2 4 1 1 8 5 8 4 2 2 2 6 7 4 6 1 4 2 1 2 1 4 2 3 2 1 3由于问题中所有产地、中间转运站、销地都可以看作产地，又可以看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。对扩大的运输问题建立单位运价表，方法是将不可能的运输方案运价用任意大的正数M代替。所有中间转运站的产量等于销量，由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的运数不超过20。可以规定中间转运站的产销量均为20，由于实际转运量不超过各自的产量和销量，所以在每个约束条件中增加一个松弛变量xii，相当于自己运给自己,对应运价为0。扩大的运输问题中原来的产