第三章运输问题精选PPT.ppt

《第三章运输问题精选PPT.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

10、 A2 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

12、2101010108 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

15、B1 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

19、3B 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

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

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

27、=9-4+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 A

29、1 19 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、

35、v vj 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页基变量基变量基变量基变量 检验数检验数检验数检验数 如果设如果设如果

37、设如果设u 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 4

41、3 32 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

44、 3B B4 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=c