第三章运输问题优秀课件.ppt

《第三章运输问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章运输问题优秀课件.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章运输问题第三章运输问题第1页，本讲稿共41页第三章第三章 运输问题运输问题3.1 3.1 3.1 3.1 运输问题的数学模型运输问题的数学模型运输问题的数学模型运输问题的数学模型已知有已知有已知有已知有mm个生产地点个生产地点个生产地点个生产地点A Ai i，i=1i=1，2 2，mm，可供应某种物资，其供，可供应某种物资，其供，可供应某种物资，其供，可供应某种物资，其供应量（产量）分别为应量（产量）分别为应量（产量）分别为应量（产量）分别为a ai i，i=1i=1，2 2，mm，有，有，有，有n n个销地个销地个销地个销地B Bj j，j=1j=1，2 2，n n，其需要量分别为，其

2、需要量分别为，其需要量分别为，其需要量分别为b bj j，j=1j=1，2 2，n n，从，从，从，从A Ai i到到到到B Bj j运输单位物资运输单位物资运输单位物资运输单位物资的运价（单价）为的运价（单价）为的运价（单价）为的运价（单价）为c cij ij，这些数据可汇总于产销平衡表和单位运价，这些数据可汇总于产销平衡表和单位运价，这些数据可汇总于产销平衡表和单位运价，这些数据可汇总于产销平衡表和单位运价表中，见下表。表中，见下表。表中，见下表。表中，见下表。（）第2页，本讲稿共41页若用若用若用若用x xij ij表示从表示从表示从表示从A Ai i到到到到B Bj j的运量，那么在产

3、销平衡条件下，要求得总运的运量，那么在产销平衡条件下，要求得总运的运量，那么在产销平衡条件下，要求得总运的运量，那么在产销平衡条件下，要求得总运费最小的调运方案，可求解以下数学模型：费最小的调运方案，可求解以下数学模型：费最小的调运方案，可求解以下数学模型：费最小的调运方案，可求解以下数学模型：第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量 1 2 n1 2 n产地产地产地产地1 12 2mm c c1111 c c1212 c c1n1n c c2121 c c2222 c c2n2n c cm1m1 c cm2m2 c cmnmna a1 1a a2 2a

4、amm销量销量销量销量 b b1 1 b b2 2 b bn n第3页，本讲稿共41页第三章第三章 运输问题运输问题这就是运输问题的数学模型。它包括这就是运输问题的数学模型。它包括mn个变量个变量，（，（m+n）个约个约束方程，其系数矩阵结构比较松散，且特殊：束方程，其系数矩阵结构比较松散，且特殊：第4页，本讲稿共41页第三章第三章 运输问题运输问题第5页，本讲稿共41页系数矩阵中对应于变量系数矩阵中对应于变量系数矩阵中对应于变量系数矩阵中对应于变量x xij ij的系数向量的系数向量的系数向量的系数向量P Pij ij，其分量除第，其分量除第，其分量除第，其分量除第i i个和第个和第个和第个

5、和第m+jm+j个为个为个为个为1 1外，其余的均为零。即外，其余的均为零。即外，其余的均为零。即外，其余的均为零。即P Pij ij=（01100110）T T=e=ei i+e+em+jm+j对于产销平衡的运输问题由于存在：对于产销平衡的运输问题由于存在：对于产销平衡的运输问题由于存在：对于产销平衡的运输问题由于存在：可以证明：可以证明：可以证明：可以证明：只有只有只有只有m+n-1m+n-1个独立约束方程个独立约束方程个独立约束方程个独立约束方程。即系数矩阵的秩。即系数矩阵的秩。即系数矩阵的秩。即系数矩阵的秩=m+n-1=m+n-1。由于以上特征，所以求解运输问题时，可用比较简便的计算方

6、法，习由于以上特征，所以求解运输问题时，可用比较简便的计算方法，习由于以上特征，所以求解运输问题时，可用比较简便的计算方法，习由于以上特征，所以求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。惯上称为表上作业法。惯上称为表上作业法。惯上称为表上作业法。3.23.2 表上作业法表上作业法表上作业法表上作业法表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯形法。但具体计算术语有所不同，可

7、归纳为：形法。但具体计算术语有所不同，可归纳为：形法。但具体计算术语有所不同，可归纳为：形法。但具体计算术语有所不同，可归纳为：（1 1）找出初始基本可行解，即在（）找出初始基本可行解，即在（）找出初始基本可行解，即在（）找出初始基本可行解，即在（mnmn）产销平衡表上给出）产销平衡表上给出）产销平衡表上给出）产销平衡表上给出m+n-1m+n-1个个个个独立的数字格。独立的数字格。独立的数字格。独立的数字格。第三章第三章 运输问题运输问题第6页，本讲稿共41页（2 2）求各非基变量的检验数，即在表上计算空格的检验）求各非基变量的检验数，即在表上计算空格的检验）求各非基变量的检验数，即在表上计算

8、空格的检验）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否数，判别是否达到最优解。如已是最优解，则停止计算，否数，判别是否达到最优解。如已是最优解，则停止计算，否数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。则转到下一步。则转到下一步。则转到下一步。（3 3）确定调入变量和调出变量，找出新的基本可行解。在）确定调入变量和调出变量，找出新的基本可行解。在）确定调入变量和调出变量，找出新的基本可行解。在）确定调入变量和调出变量，找出新的基本可行解。在表上用闭合回路法调整。表上用闭合回路法调整。表上用闭合回路法调整。表上用闭合回路

9、法调整。（4 4）重复（）重复（）重复（）重复（2 2）（）（）（）（3 3），直到得到最优解。），直到得到最优解。），直到得到最优解。），直到得到最优解。以上算法都可以在表上完成。下面通过例子说明表上作业法的以上算法都可以在表上完成。下面通过例子说明表上作业法的以上算法都可以在表上完成。下面通过例子说明表上作业法的以上算法都可以在表上完成。下面通过例子说明表上作业法的计算步骤。计算步骤。计算步骤。计算步骤。例例例例3.13.1 某公司经销一种产品，公司有三个加工厂某公司经销一种产品，公司有三个加工厂某公司经销一种产品，公司有三个加工厂某公司经销一种产品，公司有三个加工厂A A1 1、A A2

10、 2、A A3 3，其产，其产，其产，其产量分别为量分别为量分别为量分别为7t7t、4t4t、9t9t。公司有四个经销点。公司有四个经销点。公司有四个经销点。公司有四个经销点B B1 1、B B2 2、B B3 3、B B4 4，其销，其销，其销，其销量分别为量分别为量分别为量分别为3t3t、6t6t、5t5t、6t6t。已知各加工厂到各销售点的单位产品。已知各加工厂到各销售点的单位产品。已知各加工厂到各销售点的单位产品。已知各加工厂到各销售点的单位产品运费如下表所示，问公司应如何调运产品，在满足各销售点运费如下表所示，问公司应如何调运产品，在满足各销售点运费如下表所示，问公司应如何调运产品，

11、在满足各销售点运费如下表所示，问公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费最小。的需求量的前提下，使总运费最小。的需求量的前提下，使总运费最小。的需求量的前提下，使总运费最小。第三章第三章 运输问题运输问题第7页，本讲稿共41页解解解解 先画出该问题的单位运价表和产销平衡表，如下：先画出该问题的单位运价表和产销平衡表，如下：先画出该问题的单位运价表和产销平衡表，如下：先画出该问题的单位运价表和产销平衡表，如下：第三章第三章 运输问题运输问题B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 711119 94 43 32 210

12、1010108 85 5销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4产产产产地地地地A A1 1A A2 2A A3 37 74 49 9销量销量销量销量3 36 65 56 63.2.1 确定初始基本可行解确定初始基本可行解与一般线性规划问题不同。与一般线性规划问题不同。与一般线性规划问题不同。与一般线性规划问题不同。产销平衡的运输问题总是存在可行产销平衡的运输问题总是存在可行产销平衡的运输问题总是存在可行产销平衡的运输问题总是存在可行解。解。解。解。第8页，本讲稿共41页设设设设第三章第三章 运输问题运输问题令令这就是一个可行解，又因变量有界，即这就是一

13、个可行解，又因变量有界，即由线性方程组理论，运输问题最多有由线性方程组理论，运输问题最多有Cnnm+n-1个基解，在这有限个基解，在这有限个基本解中必存在最优解。个基本解中必存在最优解。确定初始基本可行解的方法有很多，一般希望的方法既简便又尽可确定初始基本可行解的方法有很多，一般希望的方法既简便又尽可能接近最优解，最常用的方法有两种：最小元素法和伏格尔（能接近最优解，最常用的方法有两种：最小元素法和伏格尔（Vogel）法。）法。第9页，本讲稿共41页1.1.最小元素法最小元素法最小元素法最小元素法基本思想：就近供应，即从单位单价表中最小的运价开始确定供基本思想：就近供应，即从单位单价表中最小的

14、运价开始确定供基本思想：就近供应，即从单位单价表中最小的运价开始确定供基本思想：就近供应，即从单位单价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基本可行解为止。销关系，然后次小。一直到给出初始基本可行解为止。销关系，然后次小。一直到给出初始基本可行解为止。销关系，然后次小。一直到给出初始基本可行解为止。第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 14 43 37 7A A2 23 3 1 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 6项目项目项目项目B B1

15、 1B B2 2B B3 3B B4 4A A1 13 311113 31010A A2 21 19 92 28 8A A3 37 74 410105 5该方案的总费用为该方案的总费用为86元。元。第10页，本讲稿共41页2.2.伏格尔法伏格尔法伏格尔法伏格尔法最小元素法的缺点：为了节省一处的费用，有时造成其他处要多最小元素法的缺点：为了节省一处的费用，有时造成其他处要多最小元素法的缺点：为了节省一处的费用，有时造成其他处要多最小元素法的缺点：为了节省一处的费用，有时造成其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小

16、运花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不能按最小运费调运时运费增加越多。因而对差额最大处，就应当不能按最小运费调运时运费增加越多。因而对差额最大处，就应当不能按最小运费调运时运费增加越多。因而对差额最大处，就应当不能按最小运费调运时运费增加越多。因而对差额最大处，就应当采用最小运费调运。

17、基于此，伏格尔法的步骤是：采用最小运费调运。基于此，伏格尔法的步骤是：采用最小运费调运。基于此，伏格尔法的步骤是：采用最小运费调运。基于此，伏格尔法的步骤是：第一步：第一步：第一步：第一步：分别计算出各行和各列的最小运费和次小运费之间分别计算出各行和各列的最小运费和次小运费之间分别计算出各行和各列的最小运费和次小运费之间分别计算出各行和各列的最小运费和次小运费之间的差额，并填入最右列和最下行。的差额，并填入最右列和最下行。的差额，并填入最右列和最下行。的差额，并填入最右列和最下行。第二步：第二步：第二步：第二步：从行和列差额中选择最大者，选择它所在的行或列的最小从行和列差额中选择最大者，选择它

18、所在的行或列的最小从行和列差额中选择最大者，选择它所在的行或列的最小从行和列差额中选择最大者，选择它所在的行或列的最小元素。元素。元素。元素。第三步：第三步：第三步：第三步：对未划的行和列再分别计算各行、各列的最小运费对未划的行和列再分别计算各行、各列的最小运费对未划的行和列再分别计算各行、各列的最小运费对未划的行和列再分别计算各行、各列的最小运费和次小运费的差额，重复一、二步。和次小运费的差额，重复一、二步。和次小运费的差额，重复一、二步。和次小运费的差额，重复一、二步。第三章第三章 运输问题运输问题第11页，本讲稿共41页第三章第三章 运输问题运输问题B B1 1B B2 2B B3 3B

19、 B4 4行差额行差额行差额行差额A A1 13 311113 310100 0A A2 21 19 92 28 81 1A A3 37 74 410105 51 1列差额列差额列差额列差额2 25 51 13 3项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 15 52 27 7A A2 23 3 1 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 622 27 76 6第12页，本讲稿共41页由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不同由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不

20、同由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不同由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不同外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初始解更接近最优解。始解更接近最优解。始解更接近最优解。始解更接近最优解。本例用伏格尔法给出的初始解即为最优解，最优值是本例用伏格尔法给出的初始解即为最优解，最优值是本例用伏格尔法给出的初始解即为最优解，最优值是本例用伏格尔法给出的初始解即为最

21、优解，最优值是8585元。元。元。元。3.2.2 3.2.2 最优解的判别最优解的判别最优解的判别最优解的判别判别的方法是计算空格（非基变量）的检验数判别的方法是计算空格（非基变量）的检验数判别的方法是计算空格（非基变量）的检验数判别的方法是计算空格（非基变量）的检验数c cij ij-C-CB BB B-1-1P Pij ij都大于都大于都大于都大于等于零（等于零（等于零（等于零（为什么？为什么？为什么？为什么？）。下面介绍两种求空格检验数的方法。）。下面介绍两种求空格检验数的方法。）。下面介绍两种求空格检验数的方法。）。下面介绍两种求空格检验数的方法。1.1.闭回路法闭回路法闭回路法闭回路

22、法从每个空格出发找一条闭回路，它是以某空格为起点，用水从每个空格出发找一条闭回路，它是以某空格为起点，用水从每个空格出发找一条闭回路，它是以某空格为起点，用水从每个空格出发找一条闭回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一个数字时可以转平或垂直线向前划，每碰到一个数字时可以转平或垂直线向前划，每碰到一个数字时可以转平或垂直线向前划，每碰到一个数字时可以转9090后继续前进，直后继续前进，直后继续前进，直后继续前进，直到回到起始空格为止。到回到起始空格为止。到回到起始空格为止。到回到起始空格为止。第三章第三章 运输问题运输问题第13页，本讲稿共41页可以证明：可以证明：可以证明：可

23、以证明：如果不区分闭回路的方向，每一个非基变量空格如果不区分闭回路的方向，每一个非基变量空格如果不区分闭回路的方向，每一个非基变量空格如果不区分闭回路的方向，每一个非基变量空格都存在唯一一个闭回路。都存在唯一一个闭回路。都存在唯一一个闭回路。都存在唯一一个闭回路。闭回路法是用来检查一个非基变量从零增加到大于零时能不能闭回路法是用来检查一个非基变量从零增加到大于零时能不能闭回路法是用来检查一个非基变量从零增加到大于零时能不能闭回路法是用来检查一个非基变量从零增加到大于零时能不能改变目标函数值的一种方法。改变目标函数值的一种方法。改变目标函数值的一种方法。改变目标函数值的一种方法。以上例采用最小元

24、素法得出的调运表为例。以上例采用最小元素法得出的调运表为例。以上例采用最小元素法得出的调运表为例。以上例采用最小元素法得出的调运表为例。第三章第三章 运输问题运输问题第14页，本讲稿共41页第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 14 43 37 7A A2 23 31 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 6项目项目项目项目B B1 1B B2 2B B3 3B B4 4A A1 13 311113 31010A A2 21 19 92 28 8A A3 37

25、 74 410105 5第15页，本讲稿共41页例如在上表中，如果例如在上表中，如果例如在上表中，如果例如在上表中，如果x x2222增加一个单位，那么要保持解的可行性，就要增加一个单位，那么要保持解的可行性，就要增加一个单位，那么要保持解的可行性，就要增加一个单位，那么要保持解的可行性，就要把把把把x x2222回路中每个转角点的数字加以调整：减少一个回路中每个转角点的数字加以调整：减少一个回路中每个转角点的数字加以调整：减少一个回路中每个转角点的数字加以调整：减少一个x x3232，增加一个，增加一个，增加一个，增加一个x x3434，减少一个减少一个减少一个减少一个x x1414，增加一

26、个，增加一个，增加一个，增加一个x x1313，减少一个，减少一个，减少一个，减少一个x x2323。这样的改变可以继续保持供求的平衡假如这样的改变可以继续保持供求的平衡假如这样的改变可以继续保持供求的平衡假如这样的改变可以继续保持供求的平衡假如C C2222 表示增加一个单位表示增加一个单位表示增加一个单位表示增加一个单位x x2222后后后后运费的增加数，那么由运费表可知：运费的增加数，那么由运费表可知：运费的增加数，那么由运费表可知：运费的增加数，那么由运费表可知：c c2222=c=c2222-c-c3232-+c-+c3434-c-c1414+c+c1313-c-c2323=9-4+

27、5-10+3-2=19-4+5-10+3-2=1说明如果把说明如果把说明如果把说明如果把x x2222增加一个单位，那么总运费要增加增加一个单位，那么总运费要增加增加一个单位，那么总运费要增加增加一个单位，那么总运费要增加1 1元。元。元。元。我们计算我们计算我们计算我们计算x x2424的检验数：的检验数：的检验数：的检验数：c c2424=?=?第三章第三章 运输问题运输问题第16页，本讲稿共41页已知运输问题的产销平衡和单位运价表，试用伏格尔法求出一已知运输问题的产销平衡和单位运价表，试用伏格尔法求出一已知运输问题的产销平衡和单位运价表，试用伏格尔法求出一已知运输问题的产销平衡和单位运价

28、表，试用伏格尔法求出一个调运方案，并判断该方案是否是最优的。个调运方案，并判断该方案是否是最优的。个调运方案，并判断该方案是否是最优的。个调运方案，并判断该方案是否是最优的。作业作业项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 18 84 41 12 27 7A A2 26 69 94 47 72525A A3 35 53 34 43 32626销量销量销量销量1010101020201515第17页，本讲稿共41页作业作业项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 19

29、98 8121213131818A A2 210101010121214142424A A3 38 89 9111112126 6A A4 410101010111112121212销量销量销量销量6 6141435355 5第18页，本讲稿共41页2.2.位势法位势法位势法位势法用闭回路法求检验数时，需要给每一空格找一条闭回路。当用闭回路法求检验数时，需要给每一空格找一条闭回路。当用闭回路法求检验数时，需要给每一空格找一条闭回路。当用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点多时，这种计算很繁琐。下面介绍一种更为简便的方产销点多时，这种计算很繁琐。下面介绍一种更为简便的方产销点

30、多时，这种计算很繁琐。下面介绍一种更为简便的方产销点多时，这种计算很繁琐。下面介绍一种更为简便的方法法法法位势法（乘数法）。位势法（乘数法）。位势法（乘数法）。位势法（乘数法）。位势法的原理是线性规划的对偶理论。下面通过一个简单的例子位势法的原理是线性规划的对偶理论。下面通过一个简单的例子位势法的原理是线性规划的对偶理论。下面通过一个简单的例子位势法的原理是线性规划的对偶理论。下面通过一个简单的例子来说明。来说明。来说明。来说明。设有一个两个产地、三个销地的运输问题，其线性规划模型如下：设有一个两个产地、三个销地的运输问题，其线性规划模型如下：设有一个两个产地、三个销地的运输问题，其线性规划模

31、型如下：设有一个两个产地、三个销地的运输问题，其线性规划模型如下：第三章第三章 运输问题运输问题第19页，本讲稿共41页共有共有共有共有6 6个决策变量，在基本解中，应有四个基变量（个决策变量，在基本解中，应有四个基变量（个决策变量，在基本解中，应有四个基变量（个决策变量，在基本解中，应有四个基变量（为什么？为什么？为什么？为什么？），），），），2 2个个个个非基变量。设非基变量。设非基变量。设非基变量。设u u1 1，u u2 2为对应于产地的对偶变量，为对应于产地的对偶变量，为对应于产地的对偶变量，为对应于产地的对偶变量，v v1 1，v v2 2，v v3 3为对应于销为对应于销为对应

32、于销为对应于销地的对偶变量，则其对偶问题是：地的对偶变量，则其对偶问题是：地的对偶变量，则其对偶问题是：地的对偶变量，则其对偶问题是：第三章第三章 运输问题运输问题第20页，本讲稿共41页如果原始问题得到一个调运方案（基本可行解），则对偶问题如果原始问题得到一个调运方案（基本可行解），则对偶问题如果原始问题得到一个调运方案（基本可行解），则对偶问题如果原始问题得到一个调运方案（基本可行解），则对偶问题的约束条件是相应各变量的最优条件。对应于基变量的约束条件的约束条件是相应各变量的最优条件。对应于基变量的约束条件的约束条件是相应各变量的最优条件。对应于基变量的约束条件的约束条件是相应各变量的最优

33、条件。对应于基变量的约束条件等式成立，对应于非基变量的约束条件，将不等号两边相减，即等式成立，对应于非基变量的约束条件，将不等号两边相减，即等式成立，对应于非基变量的约束条件，将不等号两边相减，即等式成立，对应于非基变量的约束条件，将不等号两边相减，即得到它的检验数。得到它的检验数。得到它的检验数。得到它的检验数。第三章第三章 运输问题运输问题第21页，本讲稿共41页例如，在这个调运方案中，例如，在这个调运方案中，例如，在这个调运方案中，例如，在这个调运方案中，x x1111，x x1212，x x1313，x x2121是基变量，则对是基变量，则对是基变量，则对是基变量，则对偶约束条件中，前

34、偶约束条件中，前偶约束条件中，前偶约束条件中，前4 4个约束条件等式成立，即：个约束条件等式成立，即：个约束条件等式成立，即：个约束条件等式成立，即：这是一个有这是一个有这是一个有这是一个有5 5个变量、个变量、个变量、个变量、4 4个方程的方程组，令任一变量等于零（不个方程的方程组，令任一变量等于零（不个方程的方程组，令任一变量等于零（不个方程的方程组，令任一变量等于零（不妨令妨令妨令妨令u u1 1=0=0），则可解出其他），则可解出其他），则可解出其他），则可解出其他u ui i、v vj j变量的值。将求出的变量的值。将求出的变量的值。将求出的变量的值。将求出的u ui i、v vj

35、j代入到代入到代入到代入到非基变量对应的约束条件，两边相减，即得到它们的检验数：非基变量对应的约束条件，两边相减，即得到它们的检验数：非基变量对应的约束条件，两边相减，即得到它们的检验数：非基变量对应的约束条件，两边相减，即得到它们的检验数：第三章第三章 运输问题运输问题第22页，本讲稿共41页由于运输模型的特殊性，上述计算过程相对比较简单。由于运输模型的特殊性，上述计算过程相对比较简单。由于运输模型的特殊性，上述计算过程相对比较简单。由于运输模型的特殊性，上述计算过程相对比较简单。在例在例在例在例3.13.1由最小元素法的得到的初始解中由最小元素法的得到的初始解中由最小元素法的得到的初始解中

36、由最小元素法的得到的初始解中x x2323，x x3434，x x2121，x x3232，x x1313，x x1414是基变量，这时对应的检验数是：是基变量，这时对应的检验数是：是基变量，这时对应的检验数是：是基变量，这时对应的检验数是：第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 14 43 37 7A A2 23 31 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 6第23页，本讲稿共41页基变量基变量基变量基变量 检验数检验数检验数检验数 如果设如果设如果设如果设u

37、 u1 1=0=0，则可以求得：，则可以求得：，则可以求得：，则可以求得：u u1 1=0=0，u u2 2=-1=-1，u u3 3=-5=-5，v v1 1=2=2，v v2 2=9=9，v v3 3=3=3，v v4 4=10=10，因此非基变量因此非基变量因此非基变量因此非基变量的检验数：的检验数：的检验数：的检验数：ij ij=c=cij ij-(u-(ui i+v+vj j)这样就可以从已知的这样就可以从已知的这样就可以从已知的这样就可以从已知的u ui i，v vj j中求得。这些计算可以在表格中进行，中求得。这些计算可以在表格中进行，中求得。这些计算可以在表格中进行，中求得。这

38、些计算可以在表格中进行，以例以例以例以例3.13.1说明。说明。说明。说明。第三章第三章 运输问题运输问题第24页，本讲稿共41页第一步，按最小元素法给出初始解，制成表格。第一步，按最小元素法给出初始解，制成表格。第一步，按最小元素法给出初始解，制成表格。第一步，按最小元素法给出初始解，制成表格。第二步，在上表中增加一行、一列，在列中填入第二步，在上表中增加一行、一列，在列中填入第二步，在上表中增加一行、一列，在列中填入第二步，在上表中增加一行、一列，在列中填入u ui i，在行中填入，在行中填入，在行中填入，在行中填入v vj j。令。令。令。令u u1 1=0=0，然后依据，然后依据，然后

39、依据，然后依据u ui i+v+vj j=c=cij ij，相继确定，相继确定，相继确定，相继确定u ui i，v vj j，依次求出所有的，依次求出所有的，依次求出所有的，依次求出所有的u ui i、v vi i的值。的值。的值。的值。例如由例如由例如由例如由u u1 1+v+v3 3=3=3可得出可得出可得出可得出v v3 3=3=3；由；由；由；由u u1 1+v+v4 4=10=10得出得出得出得出v v4 4=10=10；由；由；由；由u u3 3+v+v4 4=5=5得出得出得出得出u u3 3=-5=-5以此类推。以此类推。以此类推。以此类推。第三章第三章 运输问题运输问题项目项

40、目项目项目销地销地销地销地B B1 1B B2 2B B3 3B B4 4A A1 14 43 3A A2 23 31 1A A3 36 63 3第25页，本讲稿共41页 第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地u ui iB B1 1B B2 2B B3 3B B4 4A A1 11 12 24 43 30 0A A2 23 31 11 1-1-1-1-1A A3 310106 612123 3-5-5v vj j2 29 93 31010B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 711119 94 43 32

41、2101010108 85 5第26页，本讲稿共41页第三步，按第三步，按第三步，按第三步，按 ij ij=c=cij ij-(u-(ui i+v+vj j)计算所有空格的检验数。如：计算所有空格的检验数。如：计算所有空格的检验数。如：计算所有空格的检验数。如：1111=c=c1111-(u-(u1 1+v+v1 1)=3-(0+2)=1)=3-(0+2)=1 1212=c=c1212-(u-(u1 1+v+v2 2)=11-(0+9)=2)=11-(0+9)=2这些计算可直接在表上进行。这些计算可直接在表上进行。这些计算可直接在表上进行。这些计算可直接在表上进行。这和前面的计算结果是一样的。

42、在上表中还有负的检验数，这和前面的计算结果是一样的。在上表中还有负的检验数，这和前面的计算结果是一样的。在上表中还有负的检验数，这和前面的计算结果是一样的。在上表中还有负的检验数，说明未得最优解，还可以改进。说明未得最优解，还可以改进。说明未得最优解，还可以改进。说明未得最优解，还可以改进。第三章第三章 运输问题运输问题第27页，本讲稿共41页3.2.3 3.2.3 改进的计算方法改进的计算方法改进的计算方法改进的计算方法在所有为负值的检验数中选最小的负检验数，以它对应的非基变在所有为负值的检验数中选最小的负检验数，以它对应的非基变在所有为负值的检验数中选最小的负检验数，以它对应的非基变在所有

43、为负值的检验数中选最小的负检验数，以它对应的非基变量为调入变量，如在例量为调入变量，如在例量为调入变量，如在例量为调入变量，如在例3.13.1中中中中 2424=-1=-1，选非基变量，选非基变量，选非基变量，选非基变量x x2424为调入变量，并为调入变量，并为调入变量，并为调入变量，并以以以以x x2424所在的表格为出发点作出一个闭回路，如下表：所在的表格为出发点作出一个闭回路，如下表：所在的表格为出发点作出一个闭回路，如下表：所在的表格为出发点作出一个闭回路，如下表：第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B

44、4 4A A1 14 43 37 7A A2 23 31 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 6第28页，本讲稿共41页由于由于由于由于 2424=-1=-1，表明增加一个单位的，表明增加一个单位的，表明增加一个单位的，表明增加一个单位的x x2424的运输量，就可以使总运输量的运输量，就可以使总运输量的运输量，就可以使总运输量的运输量，就可以使总运输量减少减少减少减少1 1。我们应尽量多地增加。我们应尽量多地增加。我们应尽量多地增加。我们应尽量多地增加x x2424的运输量，但为了保证运输方案的运输量，但为了保证运输方案的运输量，但为了保证运输方案的运

45、输量，但为了保证运输方案的可行性（即所有调运量必须大于等于零），所以以出发点的可行性（即所有调运量必须大于等于零），所以以出发点的可行性（即所有调运量必须大于等于零），所以以出发点的可行性（即所有调运量必须大于等于零），所以以出发点x x2424所在空格为所在空格为所在空格为所在空格为1 1 1 1的闭回路顶点的序号序号中，找到所有偶数的顶点的调运的闭回路顶点的序号序号中，找到所有偶数的顶点的调运的闭回路顶点的序号序号中，找到所有偶数的顶点的调运的闭回路顶点的序号序号中，找到所有偶数的顶点的调运量：量：量：量：x x1414=3=3，x x2323=1=1，取其最小的值为，取其最小的值为，取其

46、最小的值为，取其最小的值为x x2424的值，即的值，即的值，即的值，即x x2424=min(3,1)=1=min(3,1)=1。为为为为例使产销平衡，把所有闭回路上为偶数顶点的运输量都减少这个值，例使产销平衡，把所有闭回路上为偶数顶点的运输量都减少这个值，例使产销平衡，把所有闭回路上为偶数顶点的运输量都减少这个值，例使产销平衡，把所有闭回路上为偶数顶点的运输量都减少这个值，而其他顶点运输量增加这个值，即得到调整后的运输方案，如下表：而其他顶点运输量增加这个值，即得到调整后的运输方案，如下表：而其他顶点运输量增加这个值，即得到调整后的运输方案，如下表：而其他顶点运输量增加这个值，即得到调整后

47、的运输方案，如下表：第三章第三章 运输问题运输问题第29页，本讲稿共41页对此表格出的运输方案，我们用位势法进行检验：对此表格出的运输方案，我们用位势法进行检验：对此表格出的运输方案，我们用位势法进行检验：对此表格出的运输方案，我们用位势法进行检验：第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地产量产量产量产量B B1 1B B2 2B B3 3B B4 4A A1 15 52 27 7A A2 23 31 14 4A A3 36 63 39 9销量销量销量销量3 36 65 56 6第30页，本讲稿共41页可知所有检验数都大于等于零，此解是最优解，这时最小总可知所有检验数都大

48、于等于零，此解是最优解，这时最小总可知所有检验数都大于等于零，此解是最优解，这时最小总可知所有检验数都大于等于零，此解是最优解，这时最小总费用为费用为费用为费用为8585元。元。元。元。第三章第三章 运输问题运输问题项目项目项目项目销地销地销地销地u ui iB B1 1B B2 2B B3 3B B4 4A A1 10 02 25 52 20 0A A2 23 32 21 11 1-1-1A A3 39 96 612123 3-5-5v vj j2 29 93 31010第31页，本讲稿共41页3.33.3产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法产销不平衡的运输问题及

49、其求解方法产销不平衡的运输问题及其求解方法前面讲的表上作业法，都是以产销平衡为前提的。但实际问前面讲的表上作业法，都是以产销平衡为前提的。但实际问前面讲的表上作业法，都是以产销平衡为前提的。但实际问前面讲的表上作业法，都是以产销平衡为前提的。但实际问题中往往是产销不平衡的，就需要把产销不平衡问题转化成产题中往往是产销不平衡的，就需要把产销不平衡问题转化成产题中往往是产销不平衡的，就需要把产销不平衡问题转化成产题中往往是产销不平衡的，就需要把产销不平衡问题转化成产销平衡问题。销平衡问题。销平衡问题。销平衡问题。当产大于销时，运输问题的数学模型可写成：当产大于销时，运输问题的数学模型可写成：当产大

50、于销时，运输问题的数学模型可写成：当产大于销时，运输问题的数学模型可写成：第三章第三章 运输问题运输问题第32页，本讲稿共41页由于总的产量大于销量，就要考虑多余的物资在哪一地贮存由于总的产量大于销量，就要考虑多余的物资在哪一地贮存由于总的产量大于销量，就要考虑多余的物资在哪一地贮存由于总的产量大于销量，就要考虑多余的物资在哪一地贮存问题。设问题。设问题。设问题。设x xi,n+1i,n+1是产地是产地是产地是产地A Ai i的贮存量，于是有：的贮存量，于是有：的贮存量，于是有：的贮存量，于是有：第三章第三章 运输问题运输问题第33页，本讲稿共41页令令令令c c ij ij=c=cij ij