管理运筹学讲义第7讲运输问题.ppt

1中山大学南方学院工商管理系中山大学南方学院工商管理系王甜源王甜源第第7 7讲讲 运输问题运输问题2p运输问题及其数学模型运输问题及其数学模型p表上作业法表上作业法p产销不平衡的运输问题产销不平衡的运输问题目目 录录3 在线性规划问题中，有一类特殊类型的问题运输问题。这在线性规划问题中，有一类特殊类型的问题运输问题。这类问题主要研究把某种物资类问题主要研究把某种物资从若干个产地调运到若干个销地从若干个产地调运到若干个销地，每个，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个费用已知，要求确定一个总运费最少总运费最少的方案。的方案。在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。利于国民经济持续发展。4 但是由于在运输问题的数学模型中，约束方程的系数矩阵具有但是由于在运输问题的数学模型中，约束方程的系数矩阵具有特殊的结构。因此，存在一种比单纯形法更为简便的方法特殊的结构。因此，存在一种比单纯形法更为简便的方法表上表上作业法。作业法。表上作业法通过定制的运输表确定最优调运方案，但其本质仍表上作业法通过定制的运输表确定最优调运方案，但其本质仍然是单纯形法，其主要步骤是：首先需要确定一个初始调运方案然是单纯形法，其主要步骤是：首先需要确定一个初始调运方案（初始基本可行解），然后检验现行调运方案（现行基本可行解）（初始基本可行解），然后检验现行调运方案（现行基本可行解）是否最优，若非最优，则需对现行调运方案（是否最优，若非最优，则需对现行调运方案（现行基本可行解）进现行基本可行解）进行行改进等几个阶段。只是表上作业法对单纯形法作了适当的修改，改进等几个阶段。只是表上作业法对单纯形法作了适当的修改，从而提高了计算的效率。从而提高了计算的效率。5 运输问题的一般提法是：某种物质（粮食、棉花、煤炭等）有运输问题的一般提法是：某种物质（粮食、棉花、煤炭等）有m m个产地个产地 ，其产量是，其产量是 ；有；有n n个销地个销地 ,其销量（或需求量）是其销量（或需求量）是 。现在需要把这种物质从现在需要把这种物质从m m个产地运送到个产地运送到n n个销地。若从个销地。若从 运到运到 的的单位运价为单位运价为 。又限定产销平衡，即又限定产销平衡，即 ，问应如何制定调运方案可使总费用最小？问应如何制定调运方案可使总费用最小？p运输问题及其数学模型运输问题及其数学模型6上述已知条件可用下面的表格来表示。上述已知条件可用下面的表格来表示。销量销量 产量产量 销地销地产地产地 7如果如果用用 代表从第产地运往第销地的物质单位数量代表从第产地运往第销地的物质单位数量（i=1i=1，2 m2 m；j j1 1，2 n2 n），为总运费，那么求解上述使），为总运费，那么求解上述使总运费最小的运输问题。可以用下列数学模型描述：总运费最小的运输问题。可以用下列数学模型描述：从每一个产地运往各个销地的物从每一个产地运往各个销地的物质数量之和等于该产地的产量质数量之和等于该产地的产量从各个产地运往每一个销地的物质从各个产地运往每一个销地的物质数量之和等于该销地的销量数量之和等于该销地的销量使总运费达到最小使总运费达到最小运输量非负运输量非负8 运输问题的线性规划模型具有运输问题的线性规划模型具有特殊的结构，其约束方程组的系数特殊的结构，其约束方程组的系数矩阵矩阵A A具有如下形式：具有如下形式：m mn n个决策变量，个决策变量，m mn n个约束条件。个约束条件。经证明：产销平衡的运输问题的非零经证明：产销平衡的运输问题的非零变量变量 为为m+n-1m+n-1个。具体证明如下：个。具体证明如下：A=1 1 1 1 1 11 1 11 1 1m行行 n行行 1 1 11 1 19A=1 1 1 1 1 11 1 11 1 1m行行 n行行 1 1 11 1 1 该矩阵的元素全部为该矩阵的元素全部为0 0或或1 1。每一列只有。每一列只有2 2个元素为个元素为1 1，其余为，其余为0 0。若用若用 表示决策变量表示决策变量 的系数列向量，则在的系数列向量，则在 中第中第i i个和第个和第 m mj j 个元素为个元素为1 1，其余为，其余为0 0。我们也可以用两个单位向量之和来。我们也可以用两个单位向量之和来 表示。表示。即：即：其中其中 和和 分别为第分别为第i i个元素和第个元素和第m mj j个元素为个元素为1 1的单位向量。的单位向量。10 通通过过对对运运输输问问题题的的数数学学模模型型约约束束矩矩阵阵的的特特殊殊结结构构作作进进一一步步分分析析，还可以发现矩阵的秩为还可以发现矩阵的秩为m mn n1 1，即，即()m+n-1m+n-1。这是因为系数矩阵这是因为系数矩阵A A的前的前m m个行向量之和减去后个行向量之和减去后n n个行向量之个行向量之 和恰好为零向量。即矩阵的和恰好为零向量。即矩阵的m mn n个行向量线性相关。因此个行向量线性相关。因此 ()m)mn n。再将矩阵。再将矩阵A A的第的第2,3,2,3,m+nm+n行与行与 所对应的列的交叉处的元素构成一个所对应的列的交叉处的元素构成一个m mn n1 1阶子式。阶子式。1 1 1 1 1 11 1 1 1 1 11 1 11 1 1表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）用最小元素法或伏格尔法找出初始基可行解（2）用闭回路法求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同p 表上作业法表上作业法换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否13n确定初始基本可行解确定初始基本可行解求运输问题的初始基本可行解有多种方法。在此我们只介求运输问题的初始基本可行解有多种方法。在此我们只介绍最小元素法和伏格尔法两种方法。为了确定初始基本可行解，绍最小元素法和伏格尔法两种方法。为了确定初始基本可行解，首先必须画出运输问题的基本表格。即调运表和运价表。首先必须画出运输问题的基本表格。即调运表和运价表。销地销地 产地产地 产量产量 销量销量 销地销地 产地产地 调运表调运表 运价表运价表 14在实际计算中，为了方便通常将调运表和运价表合二在实际计算中，为了方便通常将调运表和运价表合二为一，综合为下列运输表。为一，综合为下列运输表。销地销地产地产地 产量产量 c c1111 c c1212 c c1n1n c c2121 c c2222 c c2n2n c cm1m1 c cm2m2 c cmnmn 销量销量 运输表运输表 151 1，最小元素法，最小元素法最小元素法的基本思路是最小元素法的基本思路是以运价最低者优先为原则安排初始的以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系调运方案，即从单位运价表中最小运价处开始确定供销关系。若产量大于销量，则用加工厂的产量满足对应销地的全部日销若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。日产量中减去调运量。反之，若产量小于销售量。则把加工厂的日产量全部分配给对反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。行，并从对应销地的日销量中减去调运量。依次类推，逐步推出初始方案。依次类推，逐步推出初始方案。由于最小元素法已经考虑到了运价最低者优先为原则，因此所由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过若干次调整即可求求的初始基本可行解通常比较接近最优解。经过若干次调整即可求得最优解。得最优解。运输问题最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格即一组可行解，这里叫初始基。运输问题最小元素法例14122854396111110销量产量销地产地822010100614868000060运输问题最小元素法例14122854396111110销量产量销地产地82101468最小元素法缺点：会出现顾此失彼 （运费差额问题）考虑运价差19例例2 2，某公司经销甲产品。下设三个加工厂，某公司经销甲产品。下设三个加工厂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 65 56 6单位：千元单位：千元/吨吨 问该公司应如何确定调运方案，在满足各销地需求量的问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？前提下可使得总运费最小？206 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 销售地销售地加工厂加工厂 为了用最小元素法确定初始基本可行解，可先画出综合运输表。为了用最小元素法确定初始基本可行解，可先画出综合运输表。然后按以下步骤确定初始调运方案。然后按以下步骤确定初始调运方案。从全部单位运价中找出最低单位运价（若有两个以上最低单从全部单位运价中找出最低单位运价（若有两个以上最低单位运价，则可在其中任选其一）。然后比较最低运价所对应的加工位运价，则可在其中任选其一）。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。厂的日产量和销地的日销量，并且确定第一笔供销关系。-3216 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 产量（吨）产量（吨）B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 -3 在未被划去的单位运价中再找寻最低运价，比较最低运价对应在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确定供销关系。基本原则与定供销关系。基本原则与中描述过程相同。中描述过程相同。-1226 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 重复步骤重复步骤可逐个确定从加工厂到销地的供销关系。基本原则可逐个确定从加工厂到销地的供销关系。基本原则是在空格内内每填入一个调运量必须划去一行或一列。填入最后一是在空格内内每填入一个调运量必须划去一行或一列。填入最后一个调运量后则同时划去一行和一列个调运量后则同时划去一行和一列这样在运输表中共计填入了这样在运输表中共计填入了m mn n1 1个数字。这些数字对应了一个初始基本可行解。个数字。这些数字对应了一个初始基本可行解。-6-4-3236 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-3所填入的所填入的m mn n1 13 34 41 16 6个数字为对应个数字为对应初始基本可行解的初始基本可行解的6 6个初始基变量的值。即个初始基变量的值。即对应的总运费为对应的总运费为Z433103112643586（千元）（千元）24必必须须补补充充说说明明的的是是：利利用用最最小小元元素素法法确确定定初初始始调调运运方方案案过过程程中中，可可能能出出现现最最低低单单位位运运价价对对应应的的产产地地的的产产量量和和销销地地的的销销量量恰恰好好相相等等的的情情形形。此此时时在在运运输输表表中中填填入入一一个个数数字字后后，必必须须同同时时划划去去产产地地所所在在行行和和销销地地所所在在列列，这这和和每每填填入入一一个个数数字字只只划划一一条条直直线线的的基基本本原原则则相相违违背背（最最后后一一个个数数字字除除外外）。这这时时我我们们称称运运输问题出现了退化。输问题出现了退化。为为了了使使运运输输表表中中有有m mn n1 1个个数数字字格格。需需要要添添加加一一个个“0 0”调调运运量量，它它的的位位置置可可在在同同时时划划去去的的那那行行或或那那列列的的任任一一空空格格处处。这这个个“0 0”调调运运量量是是不不可可缺缺少少的的。因因为为运运输输问问题题的的基基本本解解中中基基变变量量的的个个数数必必须须是是m mn n1 1个个。不不能能多多，也也不不能能少少。出出现现了了数数字字为为0 0的的数数字字格格只只是是说说明明在在初初始始基基本本可可行行解解中中有有一一个个基基变变量量为为零。即该初始基本可行解是退化解。零。即该初始基本可行解是退化解。252 2，伏格尔法（，伏格尔法（VogelVogel）最最小小元元素素法法给给定定初初始始调调整整方方案案是是以以局局部部观观点点考考虑虑运运价价最最低低者者优先的原则。这可能造成整体的不合理。优先的原则。这可能造成整体的不合理。因因为为可可能能存存在在这这样样的的情情形形：某某单单位位运运价价在在整整个个单单位位运运价价表表中中可可能能并并不不是是最最低低的的，但但是是它它在在所所在在行行（或或所所在在列列）中中是是最最低低运运价价，而且它与同行（或同列）中的次最低运价相差非常显著。而且它与同行（或同列）中的次最低运价相差非常显著。因因此此就就该该行行（或或该该列列）而而言言，如如果果我我们们不不慎慎采采用用了了次次最最低低运运价价，而而不不是是最最低低运运价价，那那么么总总运运费费就就会会惩惩罚罚性性地地增增加加。我我们们通通常常把把每每行行或或每每列列的的次次最最低低运运价价与与最最低低运运价价之之差差额额称称为为罚罚金金成成本本（Penalty costPenalty cost）。为为了了避避免免在在总总运运费费总总增增加加过过多多的的罚罚金金成成本本。伏伏格格尔尔法法确确定定初初始始基基本本可可行行解解的的基基本本思思路路是是：罚罚金金成成本本最最高高的的行行或或列列中中运运价价最最低低者优先考虑。者优先考虑。即：即：罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数04-4=0第一次第一次结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数013-2=1第一次第一次结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011第一次第一次结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011列罚数4-2=22153第一次第一次结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011列罚数21531480优先安排销地，否则运价会更高下次不考虑该列第一次第一次第二次第二次结合例结合例1说明这种方法。说明这种方法。行罚数012列罚数213优先安排销地，否则运价会更高84122854396111110销量产量销地销地产地产地148006下次不考虑该行结合例结合例1说明这种方法。说明这种方法。行罚数01列罚数21284122854396111110销量产量销地销地产地产地148006下次不考虑该列802第三次第三次运输问题结合例结合例1说明这种方法。说明这种方法。行罚数76列罚数1284122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次结合例结合例1说明这种方法。说明这种方法。行罚数00列罚数24284122854396111110销量产量销地销地产地产地1480068024120000第五次第五次例1用伏格尔法得到的初始基可行解4122854396111110销量产量销地销地产地产地48148122目标函数值目标函数值用最小元素法求出的目标函数z=246 一般说来，伏格尔法得出的一般说来，伏格尔法得出的初始解的质量最好，常用来作初始解的质量最好，常用来作为运输问题最优解的近似解。为运输问题最优解的近似解。373 31 15 52 2罚金成本罚金成本 1 11 10 0罚金成本罚金成本 6 65-15-16 63 3 销量销量9 95 510104 4 6 67 7A A3 3 4 48 82 29 91 1A A2 2 7 710103 311113 3A A1 1 日产量日产量B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地 加工厂加工厂-6例例2 2用伏格尔法：用伏格尔法：计算出每行计算出每行(列列)的罚金成本，并填入附加的最右列的罚金成本，并填入附加的最右列(最下行最下行)。从所。从所有的罚金成本中找出最高值。选择它所在行有的罚金成本中找出最高值。选择它所在行(列列)的最低运价。比较最的最低运价。比较最小运价对应的加工厂的日产量和销售地的日销量的大小，确定第一笔小运价对应的加工厂的日产量和销售地的日销量的大小，确定第一笔供销关系。供销关系。381 11 10 03 31 15 52 2罚金成本罚金成本 罚金成本罚金成本 6 65-15-16 63 3 销量销量9 95 510104 4 6 67 7A A3 3 4 48 82 29 91 1A A2 2 7 710103 311113 3A A1 1 日产量日产量B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地 加工厂加工厂-6对未划去的单位运价再分别计算各行对未划去的单位运价再分别计算各行(列列)的罚金成本。再从的罚金成本。再从所有的罚金成本中找出最高值。选择它所在行所有的罚金成本中找出最高值。选择它所在行(列列)的最低运价。的最低运价。确定第二笔供销关系。确定第二笔供销关系。-391 11 10 03 31 15 52 2罚金成本罚金成本 6 67 7罚金成本罚金成本 6 65 56 63 3 销量销量9 95 510104 4 6 67 7A A3 3 1 1 4 48 82 29 91 1A A2 2 2 25 57 710103 311113 3A A1 1 日产量日产量B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地 加工厂加工厂-6-重复步骤重复步骤，直至求得求得初始调运方案。与最小元素法相同，最后，直至求得求得初始调运方案。与最小元素法相同，最后表中应有表中应有m mn n1 1个数字格。对应初始基本可行解的个数字格。对应初始基本可行解的m mn n1 1个基变量。个基变量。-3-3-5-5-1-1总运费总运费8585（千元（千元)403 3，用用上上述述两两种种方方法法求求解解的的初初始始调调运运调调运运方方案案为为运运输输问问题题的的一一个基本可行解。个基本可行解。由由运运输输问问题题数数学学模模型型的的特特征征可可知知。运运输输问问题题约约束束条条件件中中独独立立的的方方程程数数只只有有m mn n1 1个个。因因此此运运输输问问题题基基本本可可行行解解中中基基变变量的个数也一定是量的个数也一定是m mn n1 1个。个。用用最最小小元元素素法法或或伏伏格格尔尔法法求求得得的的初初始始调调运运方方案案中中有有m mn-1n-1个个数数字字格格。它它们们对对应应运运输输问问题题可可行行解解中中m mn n1 1个个非非负负分分量量，其它空白格对应可行解中的零分量其它空白格对应可行解中的零分量41n最优解的判别最优解的判别回顾利用单纯形法求解线性规划的步骤：回顾利用单纯形法求解线性规划的步骤：在在求求出出基基本本可可行行解解以以后后，就就必必须须检检验验该该基基本本可可行行解解是是否否为为最最优优解解，为为此此给给出出一一个个检检验验标标准准。在在求求极极大大化化的的线线性性规规划划时时，若若初初始基本可行解所有非基变量检验数始基本可行解所有非基变量检验数 （j j为非基变量下标）为非基变量下标）则则初初始始可可行行解解为为最最优优解解，停停止止计计算算。否否则则将将进进行行基基变变换换，对对初始基本可行解进行改进。初始基本可行解进行改进。下面介绍两种计算检验数的方法。下面介绍两种计算检验数的方法。421 1，闭回路法：，闭回路法：利利用用闭闭回回路路的的概概念念计计算算非非基基变变量量的的检检验验数数，以以判判别别基基本本可可行行解解是是否为最优解。否为最优解。l 定定义义：若若运运输输表表中中的的一一组组变变量量经经过过适适当当排排列列以以后后，可可写写成成如如下下形形式：式：其中其中 互不相同，互不相同，互不相同。互不相同。那那么么这这些些变变量量集集合合就就构构成成了了一一个个闭闭回回路路。其其中中的的每每一一个个变变量量称称为为这个闭回路的顶点。这个闭回路的顶点。由由闭闭回回路路定定义义可可知知，闭闭合合路路线线是是指指以以非非基基变变量量所所在在的的空空格格为为起起点点，沿沿着着水水平平或或垂垂直直方方向向前前进进，只只有有当当碰碰到到数数字字格格时时，才才能能改改变变前前进进方方向向，如如此此曲曲折折的的走走，一一直直到到返返回回其其实实空空返返回回其其实实空空格格所所经经过过的的一条路线。一条路线。P50P5043表中变量集合表中变量集合,变量集合变量集合 ,变量集合等均构成闭回路变量集合等均构成闭回路 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 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 9常见的几种闭回路见表：常见的几种闭回路见表：闭回路法思路：计算空格（非基变量）的检验数如何求检验数？分析：444122854396111110销量产量销地产地82101468从例1初始表分析：要保证产销平衡，则 称为闭回路+1-1+1-1454122854396111110销量产量销地产地82101468-2-146检验数表4122854396111110销量产量销地产地82101468-2-1-11-10-1247486 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 3-A A1 1 产量（吨）产量（吨）B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 在例在例2 2中，用最小元素法求出初始基本可行解为下表所示。试用闭回中，用最小元素法求出初始基本可行解为下表所示。试用闭回路法求各非基变量（空格）的检验数路法求各非基变量（空格）的检验数解：非基变量为起点的闭回路为，如表所示。解：非基变量为起点的闭回路为，如表所示。因此所对应的检验数因此所对应的检验数496 65 56 63 3销量（吨）销量（吨）9 95 53 31010-12-124 46 67 7-10-10A A3 3 4 48 82 21 19 9-1 13 3A A2 2 7 7 10103 33 34 41111-3 3A A1 1 产量（吨）产量（吨）B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 而非基变量而非基变量 对应的检验数：对应的检验数：其它非基变量的检验数用同样方法求解，结果下表。其它非基变量的检验数用同样方法求解，结果下表。本例中本例中 ，则必存在对现行调运方案的改进办法。，则必存在对现行调运方案的改进办法。可使得总费用进一步降低。可使得总费用进一步降低。502 2位势法位势法 由单纯形可知，在求解运输问题的初始基本可行解，以后也可以使由单纯形可知，在求解运输问题的初始基本可行解，以后也可以使用以下公式计算非基变量检验数。用以下公式计算非基变量检验数。(i,ji,j为非基变量下标为非基变量下标)经过对模型的转换（过程略），我们得到经过对模型的转换（过程略），我们得到一个方程组如下所示：一个方程组如下所示：51我们把这个方程组的解叫做我们把这个方程组的解叫做位势位势。计算位势后，可确定所有非基变量检验数。计算位势后，可确定所有非基变量检验数。若所有检验数小于等于零。则已求得最优解，若所有检验数小于等于零。则已求得最优解，否则必须作进一步改进。否则必须作进一步改进。以例以例2 2为例，通过位势法计算非基变量的为例，通过位势法计算非基变量的检验数。已知基变量为检验数。已知基变量为 。可得方程组。可得方程组 ，求解可得求解可得由由 （i,ji,j为非基变量下标为非基变量下标)由此可得：由此可得：因为因为 ，所以原方案不是最优解。，所以原方案不是最优解。52v v4 4v v3 3v v2 2v v1 1 v vj ju u3 35 53 31010-12-124 46 67 7-10-10A A3 3 u u2 28 81 12 21 19 9-1-11 13 3A A2 2 u u1 110103 33 34 41111-2-23 3-1-1A A1 1 u ui iB B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 上述计算检验数的过程可以在运输表中完成。方法是用上述计算检验数的过程可以在运输表中完成。方法是用 代替代替表中的产量行，用表中的产量行，用 列替代表中的销量列。首先取定列替代表中的销量列。首先取定 ，然后根，然后根据数字格的单位运价据数字格的单位运价 逐个确定其它各个逐个确定其它各个 最后利用公式最后利用公式 求出非基变量检验数。求出非基变量检验数。10103 3-1-12 2-5-59 953n改进基本可行解的方法改进基本可行解的方法 对已求得的基本可行解，若存在正的检验数，则说明当前解不对已求得的基本可行解，若存在正的检验数，则说明当前解不是最优解，需要改进。与单纯形法对基本可行解的改进方法相似，是最优解，需要改进。与单纯形法对基本可行解的改进方法相似，l首先确定换入变量。首先确定换入变量。即选取最大的正检验数所对应的非基变量为换入变量。即选取最大的正检验数所对应的非基变量为换入变量。l然后确定换出变量。然后确定换出变量。再一次使用闭回路法。由定理再一次使用闭回路法。由定理2，若，若 为换入变量，则以为换入变量，则以 为为起点，标出其它顶点都为基变量（数字格）的唯一闭回路，在由起点，标出其它顶点都为基变量（数字格）的唯一闭回路，在由 出出发的闭回路上标注减号的顶点上挑出调运量的最小值即就是调整量发的闭回路上标注减号的顶点上挑出调运量的最小值即就是调整量，而相应的基变量就是换出变量。，而相应的基变量就是换出变量。54若有两个减号顶点同时有同一个最小值，则可任取其若有两个减号顶点同时有同一个最小值，则可任取其中之一作为换出变量。中之一作为换出变量。同时按以下方法进行调整：同时按以下方法进行调整：在上述闭回路上，减号顶点运输量的值均减去调整量在上述闭回路上，减号顶点运输量的值均减去调整量 ，偶数顶点运输量的值均加上调整量偶数顶点运输量的值均加上调整量 。其中换出变量运输量必调。其中换出变量运输量必调整为零，且由数字格变成空格。表示该变量已由基变量变成了非整为零，且由数字格变成空格。表示该变量已由基变量变成了非基变量。若有其它偶数顶点的运输量也调整为零，则必须把基变量。若有其它偶数顶点的运输量也调整为零，则必须把“0 0”仍然填入所在格。表示对应的基变量并非离基变量，只是仍然填入所在格。表示对应的基变量并非离基变量，只是出现了取值为零的基变量，如前所述，此时出现了退化的基本可出现了取值为零的基变量，如前所述，此时出现了退化的基本可行解。行解。上述闭回路顶点以外的运输量保持不变。上述闭回路顶点以外的运输量保持不变。调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地821014681（-2）（-2）（+2）（+2）55调整后的解为：4122854396111110销量产量销地产地82121448-2-20-9-1-125657在例在例2 2中，用位势法检验初始基本可行解，出现了为正值的非基变量检中，用位势法检验初始基本可行解，出现了为正值的非基变量检验数。试利用闭回路法对该解作进一步调整并求出最优解。验数。试利用闭回路法对该解作进一步调整并求出最优解。解解:为正的检验数，所以以为换入变量，对应的闭回路上为正的检验数，所以以为换入变量，对应的闭回路上.两个减号顶点，调整量，两个减号顶点，调整量，以为换入变量以为换入变量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 销售地销售地加工厂加工厂 586 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 销售地销售地加工厂加工厂 按上述调整方法加号点按上述调整方法加号点 均增加均增加1，即，即 ，而减号，而减号点点 均减少均减少1。即。即 （离基）。由此可得改进后的调（离基）。由此可得改进后的调运方案运方案.总运费总运费85(千千元元)+1+1-1-159v v4 4v v3 3v v2 2v v1 1 v vj ju u3 35 53 31010-12-124 46 67 7-9-9A A3 3 u u2 28 81 12 2-1-19 9-2-21 13 3A A2 2 u u1 110102 23 35 51111-2-23 30 0A A1 1 u ui iB B4 4 B B3 3 B B2 2 B B1 1 销售地销售地加工厂加工厂 10103 3-2-23 3-5-59 9再利用位势法对改进后的基本可行解进行检验，如下表再利用位势法对改进后的基本可行解进行检验，如下表因为所有非基变量检验数均小于等于零，所以已得到最优解。因为所有非基变量检验数均小于等于零，所以已得到最优解。即最优调运方案即最优调运方案 ，此时最小运费，此时最小运费Z85（千元）（千元）说明本题有无穷多最优解。说明本题有无穷多最优解。60p产销不平衡的运输问题产销不平衡的运输问题（）若总产量大于总销量，即令假象销地的销量为：决策变量表示由到的物品数量。销地产地销量产量注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。61原产大于销平衡问题的数学模型62修改后产大于销平衡问题的数学模型63（）若总产量小于总销量，即令假象产地的销量为：仿照上述类似处理。6465例例4 4，设有产量分别为，设有产量分别为3030，5050，6060的三个原料产地的三个原料产地1 1，2 2，3 3。要将原料运往需求量分别为要将原料运往需求量分别为1515，1010，4040，4545的四个销售地的四个销售地1 1，2 2，3 3，4 4。单位运价表如表。试求总运费最省的调运方案。单位运价表如表。试求总运费最省的调运方案。A1A2A33584748610352销地产地 解解：总产量总产量 总销量总销量为总产量大于总销量的不平衡的运输问题。因此增加一个虚拟的销地为总产量大于总销量的不平衡的运输问题。因此增加一个虚拟的销地B5，需求量，需求量b5=140-110=30，且单位运价，且单位运价c15c25c350。66由此可得产销平衡的运输表由此可得产销平衡的运输表3030B B5 54545404010101515销量销量 6060 A A3 3 5050 A A2 2 3030A A1 1 B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地 加工厂加工厂 产量产量 3 37 75 58 84 48 84 46 63 310105 52 20 00 00 0对上述产销平衡运输表，可用表示作业法求解对上述产销平衡运输表，可用表示作业法求解。6730 30 45 45 404010 10 15 15 销量销量 60600 02 245455 55 53 31010 1010A A3 3 50500 030306 68 820204 47 7A A2 2 30300 04 48 815155 53 31515 A A1 1 产量产量 B B5 5 B B4 4 B B3 3 B B2 2 B B1 1 销售地销售地 加工厂加工厂 得初始基本可行解得初始基本可行解 总运费总运费Z Z470470 首先利用最小元素法确定初始基本可行解首先利用最小元素法确定初始基本可行解-15-30-45-10-15-568利用位势法求解非基变量检验数，以判断初始基本可行解利用位势法求解非基变量检验数，以判断初始基本可行解 是否最优。是否最优。v v5 5v v4 4v v3 3v v2 2v v1 1u