2.4运输问题(修改)

1、1第2.4节 运输问题p一、一、 运输问题的数学模型运输问题的数学模型p二、二、 表上作业法表上作业法p三、产销不平衡的运输问题及其求解方法三、产销不平衡的运输问题及其求解方法2 例例1 1 某公司经销甲产品。它下设三个加工厂。某公司经销甲产品。它下设三个加工厂。每日的产量每日的产量分别是：分别是：A A1 1为为7 7吨，吨，A A2 2为为4 4吨，吨，A A3 3为为9 9吨。吨。该公司把这些产品分别运该公司把这些产品分别运往四个销售点。往四个销售点。各销售点每日销量为：各销售点每日销量为：B B1 1为为3 3吨，吨，B B2 2为为6 6吨，吨，B B3 3为为5 5吨，吨，B B4

2、 4为为6 6吨。吨。已知从各工厂到各销售点的单位产品的运价。问该已知从各工厂到各销售点的单位产品的运价。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。费为最少。 单位运价表单位运价表 产销平衡表产销平衡表 销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 7 4 9 销量 3 6 5 6 3一、运输问题的数学模型已知有已知有m个生产地点个生产地点 Ai , i=1,2,，m。可供应某种物资，其可供应某种物资，其供应量供应量(产量产量)分别为：分别为：ai，i=1，2，m有有n个销地个销地 Bj，j=

3、1,2,n，其需要量分别为其需要量分别为 ：bj，j=1,2,n从从 Ai 到到 Bj 运输单位物资的运价运输单位物资的运价(单价单价)为：为：cij这些数据可汇总于产销平衡表和单位运价表中，见下表。有这些数据可汇总于产销平衡表和单位运价表中，见下表。有时可把这两表合二为一。时可把这两表合二为一。 销地销地产地产地1 2 n产量产量12m a a1 1a a2 2a am m销量销量b b1 1 b b2 2 b bn n4 若用若用 xij 表示从表示从 Ai 到到 Bj 的运量，那么在产销平衡的条件的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为：下，要求得总运费最小

4、的调运方案的数学模型为：0)23(, 2 , 1) 13(, 2 , 1. .min1111ijmijijnjiijminjijijxnjbxmiaxtsxcz5一、运输问题的数学模型 这就是运输问题的数学模型。它包含这就是运输问题的数学模型。它包含mn个变量，个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。个约束方程，其系数矩阵的结构比较松散，且特殊。行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112116一，运输问题的数学模型 该系数矩阵中对应于变量该系数矩阵中对应于变量 xij 的系数向量的系数向量Pij

5、，其分量中除，其分量中除第第i个和第个和第m+j个为个为1以外，其余的都为零。即以外，其余的都为零。即 Pij= (0, ,1,0,0,1,0,0)T = ei+ em+j 对产销平衡的运输问题，由于有以下关系式存在：对产销平衡的运输问题，由于有以下关系式存在：njminjmiimiijnjijjaxxb111111运输问题是否一定有解？运输问题是否一定有解？( (见后面见后面) )运输问题的基变量共有运输问题的基变量共有 m m + + n n -1 -1 个，个，A A的秩为的秩为 m m + + n n -1 -1？ 最后一行可由前最后一行可由前m+n-1m+n-1行线性表示。其中任何一

6、行都是一样。行线性表示。其中任何一行都是一样。7二，表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：可归纳为： (1)(1) 找出初始基可行解。即在找出初始基可行解。即在(m(mn)n)产销平衡表上用产销平衡表上用西北角法或最小元素法，西北角法或最小元素法，VogelVogel法给出法给出 m+n-1 m+n-1 个数字，称个数字，称为数字格。它们就是初始基变量的取值。为数字格。它们就是初始基变量的取值。 (2)(2) 求各非基变

7、量的检验数，即在表上计算空格的检求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。否则转到下一步。 (3)(3) 确定换入变量和换出变量，找出新的基可行解。确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。在表上用闭回路法调整。 (4)(4) 重复重复(2)(2)，(3)(3)直到得到最优解为止。直到得到最优解为止。 82.1 确定初始基可行解 与一般线性规划问题不同，产销平衡的运输问题总与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有：是存在可行解。因有

8、： minjjidba11 必存在必存在xij0，i=1，m，j=1，n，如：如： Xij = aibj / d就是可行解。又因就是可行解。又因0 xijmin(aj，bj)，故，故运输问题必存在最优解。运输问题必存在最优解。 92.1 确定初始基可行解 确定初始基可行解的方法很多，有确定初始基可行解的方法很多，有西北角法西北角法，最小元素，最小元素法和伏格尔法和伏格尔(Vogel)(Vogel)法法。一般希望的方法是既简便，又尽可能。一般希望的方法是既简便，又尽可能接近最优解。下面介绍最小元素法：接近最优解。下面介绍最小元素法： 101.1.最小元素法最小元素法最小元素法的基本思路是以运价最

9、低者优先为原则安排初始的最小元素法的基本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系。调运方案，即从单位运价表中最小运价处开始确定供销关系。若产量大于销量，则用加工厂的产量满足对应销地的全部日销若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。日产量中减去调运量。反之，若产量小于销售量。则把加工厂

10、的日产量全部分配给对反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。行，并从对应销地的日销量中减去调运量。依次类推，逐步推出初始方案。依次类推，逐步推出初始方案。由于最小元素法已经考虑到了运价最低者优先为原则，因此所由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过若干次调整即可求求的初始基本可行解通常比较接近最优解。经过若干次调整即可求得最有解。得最有解。 11例例1 1 某公司经销甲产品

11、。下设三个加工厂某公司经销甲产品。下设三个加工厂1 1，2 2，3 3，每，每天把产品分别运往四个销地天把产品分别运往四个销地1 1，2 2，3 3，4 4。各加工厂的。各加工厂的日产量，各销地的日销量以及从各加工厂运送单位产品至各日产量，各销地的日销量以及从各加工厂运送单位产品至各销售地的运价如下表：销售地的运价如下表： 销地销地产地产地 B B1 1 B B2 2 B B3 3 B B4 4 日产量（吨）日产量（吨） A A1 1 3 311113 310107 7A A2 2 1 19 92 28 84 4A A3 3 7 74 410105 59 9日销量（吨）日销量（吨）3 36 6

12、5 56 6单位：千元单位：千元/ /吨吨 问该公司应如何确定调运方案，在满足各销地需求量的问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？前提下可使得总运费最小？ 126 65 56 63 3销量（吨）销量（吨） 9 95 510104 47 7A A3 3 4 48 82 29 91 13 3A A2 2 7 7 10103 311113 3A A1 1 产量（吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 为了用最小元素法确定初始基本可行解，可先画出综合运输表。为了用最小元素法确定初始基本可行解，可先画出综合运输表

13、。然后按以下步骤确定初始调运方案。然后按以下步骤确定初始调运方案。 从全部单位运价中找出最低单位运价（若有两个以上最低单从全部单位运价中找出最低单位运价（若有两个以上最低单位运价，则可在其中任选其一）。然后比较最低运价所对应的加工位运价，则可在其中任选其一）。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。厂的日产量和销地的日销量，并且确定第一笔供销关系。-3136 65 56 63 3销量（吨）销量（吨） 9 95 510104 47 7A A3 3 4 48 82 21 19 91 13 3A A2 2 7 7 10103 311113 3A A1 1 产量（

14、吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 -3 在未被划去的单位运价中再找寻最低运价，比较最低运价对应在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确定供销关系。基本原则与定供销关系。基本原则与中描述过程相同。中描述过程相同。 -1146 65 56 63 3销量（吨）销量（吨） 9 95 53 310104 46 67 7A A3 3 4 48 82 21 19 91 13 3A A2 2 7 7 10103 33

15、34 411113 3A A1 1 产量（吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 -3-1 重复步骤重复步骤可逐个确定从加工厂到销地的供销关系。基本原则可逐个确定从加工厂到销地的供销关系。基本原则是在空格内内每填入一个调运量必须划去一行或一列。填入最后一是在空格内内每填入一个调运量必须划去一行或一列。填入最后一个调运量后则同时划去一行和一列个调运量后则同时划去一行和一列这样在运输表中共计填入了这样在运输表中共计填入了m mn n1 1个数字。这些数字对应了一个初始基本可行解。个数字。这些数字对应了一个初始基本可行解。 -6-4 -315

16、6 65 56 63 3销量（吨）销量（吨） 9 95 53 310104 46 67 7A A3 3 4 48 82 21 19 91 13 3A A2 2 7 7 10103 33 34 411113 3A A1 1 产量（吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 -3-1 -6 -4 -3131421233234x =4,x =3,x =3,x =1,x =6,x3所填入的所填入的m mn n1 13 34 41 16 6个数字为对应个数字为对应初始基本可行解的初始基本可行解的 6 6个初始基变量的值。即个初始基变量的值。即对应的总

17、运费为对应的总运费为Z433103112643586（千元）（千元）16必须补充说明的是：利用最小元素法确定初始调运方案过必须补充说明的是：利用最小元素法确定初始调运方案过程中，可能出现最低单位运价对应的产地的产量和销地的销量程中，可能出现最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必须同时恰好相等的情形。此时在运输表中填入一个数字后，必须同时划去产地所在行和销地所在列，这和每填入一个数字只划一条划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的基本原则相违背（最后一个数字除外）。这时我们称运直线的基本原则相违背（最后一个数字除外）。这时我们

18、称运输问题出现了退化。输问题出现了退化。为了使运输表中有为了使运输表中有m mn n1 1个数字格。需要添加一个个数字格。需要添加一个“0”0”调运量，它的位置可在同时划去的那行或那列的任一空格处。调运量，它的位置可在同时划去的那行或那列的任一空格处。这个这个“0”0”调运量是不可缺少的。因为运输问题的基本解中基调运量是不可缺少的。因为运输问题的基本解中基变量的个数必须是变量的个数必须是m mn n1 1个。不能多，也不能少。出现了数个。不能多，也不能少。出现了数字为字为0 0的数字格只是说明在初始基本可行解中有一个基变量为的数字格只是说明在初始基本可行解中有一个基变量为零。即该初始基本可行解

19、是退化解。零。即该初始基本可行解是退化解。172.1 确定初始基可行解 用最小元素法给出初始解时，有可能在产销平衡表用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现列，这时就出现退化退化。关于退化时的处理详见教材。关于退化时的处理详见教材。182.1 确定初始基可行解 2. 2. 伏格尔法（略）伏格尔法（略） 192.22.2最优解的判别最优解的判别回顾利用单纯形法求解线性规划的步骤：回顾利用单纯形法求解线性规划的步骤：在求出基本可行解以后，就必须检验该基本可行解是否为在求出基本可行解以后

20、，就必须检验该基本可行解是否为最优解，为此给出一个检验标准。在求极大化的线性规划时，最优解，为此给出一个检验标准。在求极大化的线性规划时，若初始基本可行解所有非基变量检验数若初始基本可行解所有非基变量检验数 （j j为非基变量下标）为非基变量下标）则初始可行解为最优解，停止计算。否则将进行基变换，则初始可行解为最优解，停止计算。否则将进行基变换，对初始基本可行解进行改进。对初始基本可行解进行改进。运输问题初始基本可行解的最优性检验也必须设定一个标运输问题初始基本可行解的最优性检验也必须设定一个标准。由于运输问题目标函数是求极小化问题，因此检验标准是准。由于运输问题目标函数是求极小化问题，因此检

21、验标准是计算所有非基变量（空格）的检验数计算所有非基变量（空格）的检验数 (i,j(i,j为非基变量下标为非基变量下标) )如果所有非基变量检验数如果所有非基变量检验数 则初始基本可行解为最优解。则初始基本可行解为最优解。下面介绍两种计算检验数的方法。下面介绍两种计算检验数的方法。-1jjBj =c -C B P0-1i ji jBi j =c -C B P-1ijijBij =c -C B P0201.1.闭回路法。闭回路法。 利用闭回路的概念计算非基变量的检验数，以判别基本可行解利用闭回路的概念计算非基变量的检验数，以判别基本可行解是否为最优解。是否为最优解。l 定义：若运输表中的一组变量

22、经过适当排列以后，可写成如下形定义：若运输表中的一组变量经过适当排列以后，可写成如下形式：式： 其中其中 互不相同，互不相同， 互不相同。互不相同。那么这些变量集合就构成了一个闭回路。其中的每一个变量称为那么这些变量集合就构成了一个闭回路。其中的每一个变量称为这个闭回路的顶点。这个闭回路的顶点。由闭回路定义可知，若用水平和垂直的线段将这个变量集合中由闭回路定义可知，若用水平和垂直的线段将这个变量集合中处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且该闭回路的每一条边（水平或垂直）上只包含两个顶点。且都处于该闭回路的每一条边（水

23、平或垂直）上只包含两个顶点。且都处于每条边的两个端点上。如每条边的两个端点上。如1 11 22 22 3s ss 1i ji ji ji ji ji jx,x,x,x,x,x12si ,i ,i12sj ,j ,j232414153533x ,x ,x ,x ,x ,x11123231x ,x ,x ,x21表中变量集合表中变量集合, ,变量集合变量集合 , ,变量集合等均构成闭回路变量集合等均构成闭回路 B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 B B6 6 B B7 7 B B8 8 B B9 9 产量产量 A A1 1 a a1 1A A2 2 a a2 2A

24、 A3 3 a a3 3A A4 4 a a4 4销量销量 b b1 1 b b2 2b b3 3b b4 4b b5 5b b6 6b b7 7b b8 8b b9 911123231x ,x ,x ,x232414153533x ,x ,x ,x ,x ,x常见的几种闭回路见表：常见的几种闭回路见表：161747492926x ,x ,x ,x ,x ,x22l性质性质定理定理1 1 运输问题模型中，系数矩阵运输问题模型中，系数矩阵A A的一组系数列向量的一组系数列向量线性无关的充分必要条件是线性无关的充分必要条件是这组向量所对应的变量这组向量所对应的变量 不包含闭回路。不包含闭回路。本定

25、理证明从略。本定理证明从略。变量组变量组 不包含闭回路的含义是该变量组中不包含闭回路的含义是该变量组中任何一个变量子集合均不构成闭回路。任何一个变量子集合均不构成闭回路。由定理可得如下推论：由定理可得如下推论：推论推论1.1.若一组变量包含闭回路，那么这组变量所对应得系数列若一组变量包含闭回路，那么这组变量所对应得系数列向量线性相关。向量线性相关。推论推论2.m2.mn n1 1个变量构成基本可行解的基变量的充分必要条个变量构成基本可行解的基变量的充分必要条件是它们不包含闭回路。件是它们不包含闭回路。1 12 2s si ji ji jP ,P ,P1 12 2s si ji ji jx,x,

26、x1 12 2s si ji ji jx,x,x23定理定理2 2 若变量组若变量组 (s=m+n-1)(s=m+n-1)是运输问题是运输问题基本可行解的基变量，是一个非基变量，则变量组基本可行解的基变量，是一个非基变量，则变量组中存在包含的唯一闭回路。中存在包含的唯一闭回路。由定理由定理2 2可知，从任何一个非基变量对应的空格出发，用可知，从任何一个非基变量对应的空格出发，用水平或垂直线向前划，遇到某个基变量对应的数字格，试转水平或垂直线向前划，遇到某个基变量对应的数字格，试转9090o o后继续前进，最后总能找到一条闭回路，回到起始空格。后继续前进，最后总能找到一条闭回路，回到起始空格。i

27、jx1 12 2s si ji ji jx,x,x1 12 2s siji ji ji jx ,x,x,xijx24l闭回路法。闭回路法。设是一个非基变量，根据定理设是一个非基变量，根据定理2 2，在运输表中可以找到以，在运输表中可以找到以为第一个顶点，其他顶点均为基变量的唯一闭回路。为第一个顶点，其他顶点均为基变量的唯一闭回路。然后沿一个方向将闭回路中奇数顶点对应的值取为正，然后沿一个方向将闭回路中奇数顶点对应的值取为正，偶数顶点对应的值为负。求它们的代数和，即为非基变量对偶数顶点对应的值为负。求它们的代数和，即为非基变量对应的检验数。应的检验数。填入相应的空格。做上记号以便与数字格的基变量

28、值（调运填入相应的空格。做上记号以便与数字格的基变量值（调运量）相区别。量）相区别。ijxijxijcijc252.2 最优解的判别 闭回路法计算检验数的经济解释为：闭回路法计算检验数的经济解释为：在已给在已给出初始解的表中，可从任一空格出发，如出初始解的表中，可从任一空格出发，如(A(A1 1，B B1 1) )。若让若让A A1 1的产品调运的产品调运1 1吨给吨给B B1 1。为了保持产销平衡，。为了保持产销平衡，就要依次作调整：就要依次作调整： 在在(A(A1 1，B B3 3) )处减少处减少1 1吨，吨，(A(A2 2，B B3 3) )处增加处增加1 1吨，吨，(A(A2 2，B

29、 B1 1) )处减少处减少1 1吨，即构成了以吨，即构成了以(A(A1 1，B B1 1) )空格为起空格为起点，其他为数字格的闭回路。点，其他为数字格的闭回路。如表中的虚线所示。如表中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单在这表中闭回路各顶点所在格的右上角数字是单位运价。位运价。262.2 最优解的判别销 地 加工厂 B1 B2 B3 B4 产量 A1 3 (+1) 11 3 4(-1) 10 3 7 A2 1 3(-1) 9 2 1(+1) 8 4 A3 7 4 6 10 5 3 9 销量 3 6 5 6 可见这调整的方案使运费增加可见这调整的方案使运费增加 (+1)(+

30、1)3+(3+(1)1)3+(+1)3+(+1)2+(2+( 1) 1)=1(=1(元元) ) 这表明若这样调整运量将增加运费。将这表明若这样调整运量将增加运费。将“1”1”这个数填这个数填入入(A(A1 1，B B1 1) )格，这就是检验数。格，这就是检验数。276 65 56 63 3销量（吨）销量（吨） 9 95 53 310104 46 67 7A A3 3 4 48 82 21 19 91 13 3A A2 2 7 7 10103 33 34 411113 3A A1 1 产量（吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 例例2

31、 2 在例在例1 1中用最小元素法求出初始基本可行解为下表所示。试用中用最小元素法求出初始基本可行解为下表所示。试用闭回路法求各非基变量（空格）的检验数闭回路法求各非基变量（空格）的检验数解：非基变量为起点的闭回路为，如表所示。解：非基变量为起点的闭回路为，如表所示。因此所对应的检验数因此所对应的检验数11132321x ,x ,x ,x1111132321 =c -c +c -c =3-3+2-1=111x286 65 56 63 3销量（吨）销量（吨） 9 95 53 3101012124 46 67 71010A A3 3 4 48 8- -2 21 19 91 13 3A A2 2 7

32、 7 10103 33 34 411113 3A A1 1 产量（吨）产量（吨） B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 而非基变量而非基变量 对应的检验数：对应的检验数： 其他非基变量的检验数用同样方法求解，结果下表。其他非基变量的检验数用同样方法求解，结果下表。本例中本例中 ，则必存在对现行调运方案的改进办，则必存在对现行调运方案的改进办法。可使得总费用进一步降低。法。可使得总费用进一步降低。12x1212143432 =c -c +cc =11-10+5-4=224 =-10292.2 最优解的判别 当检验数还存在负数时，说明原方案不是最优当检验

33、数还存在负数时，说明原方案不是最优解，要继续改进，改进方法见解，要继续改进，改进方法见2.32.3小节。小节。空 格 闭 回 路 检 验 数 (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12) (22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 302.2 最优解的判别 2

34、. 位势法（略）位势法（略） 312.3 改进的方法闭回路调整法 当在表中空格处出现当在表中空格处出现负检验数时负检验数时，表明未得最优解。若，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。以入变量。以(2(2，4)4)为调入格。以此格为出发点，作一闭回路，为调入格。以此格为出发点，作一闭回路，如下表所示。如下表所示。322.3 改进的方法闭回路调整法 (2(2，4)4)格的调入量格的调入量是选择闭回路上具有

35、是选择闭回路上具有(-1)(-1)的数字格中的的数字格中的最小者。即最小者。即=min(1,3)=1(=min(1,3)=1(其原理与单纯形法中按其原理与单纯形法中按规划来规划来确定换出变量相同确定换出变量相同) )。然后按闭回路上的。然后按闭回路上的正、负号，加入和正、负号，加入和减去此值，得到调整方案减去此值，得到调整方案，如下表所示。，如下表所示。332.3 改进的方法闭回路调整法 对上表给出的解，再用闭回路法或位势法求各空格的对上表给出的解，再用闭回路法或位势法求各空格的检检验数验数，见下表。表中的所有检验数都非负，故此表中的，见下表。表中的所有检验数都非负，故此表中的解为最优解。这时

36、得到的总运费最小是解为最优解。这时得到的总运费最小是85元。元。B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 30 09 92 22 21 11212342.4 表上作业法计算中的问题 1. 1. 无穷多最优解无穷多最优解 2. 2. 退化退化35三 产销不平衡的运输问题及其求解方法 前面所讲表上作业法，都是以产销平衡为前提条件的；但是前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。题化成产销平衡的问题。 当产大于销时当产大于销时

37、 minjjiba1136三、产销不平衡的运输问题及其求解方法minjijijxcz11min 运输问题的数学模型可写成运输问题的数学模型可写成0), 2 , 1(,), 2 , 1(,11ijmijijnjiijxnjbxmiax= =37三、产销不平衡的运输问题及其求解方法njnjiijniijmiaxxx1111,), 2 , 1(,mijijnjbx1), 2 , 1( 1.由于总的产量大于销量，就要考虑多余的物资在哪一个产由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设地就地储存的问题。设xi, n+1是产地是产地Ai的储存量，于是有：的储存量，于是有：mimi

38、njnjinibbax11111,38三，产销不平衡的运输问题及其求解方法 令ijijcc , 0ijc 当 i=1,，m，j=1,，n时 当 i=1,，m，j=n+1时将其分别代入，得到将其分别代入，得到39三、 产销不平衡的运输问题及其求解方法 minjijijminjminiminjijijijijxccxcxcz1111111,11min0111ijmijijnjiijxbxax40三、 产销不平衡的运输问题及其求解方法由于该模型中有由于该模型中有11111njjnjnjmiibbba 所以这是一个产销平衡的运输问题。所以这是一个产销平衡的运输问题。 当产大于销时，只要增加一个当产大于销时，只要增加一个假想的销地假想的销地j j= =n n+1(+1(实际上实际上是储存是储存) )，该销地总