运输问题jssk运筹学.ppt

《运输问题jssk运筹学.ppt》由会员分享，可在线阅读，更多相关《运输问题jssk运筹学.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 学学 教教 程程制作单位制作单位:南京航空航天大学金城学院南京航空航天大学金城学院主讲人主讲人:朱雪春朱雪春E-mail: 在经济建设中，经常会遇到大宗物资调拨中的运在经济建设中，经常会遇到大宗物资调拨中的运输问题，如煤炭、钢铁、木材、粮食等物资，在全国输问题，如煤炭、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网，应如何制定调有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最运方案，将这些物资运到各消费地点，而使总运费最小。小。一般的运输问题就是要解决把某种产品从若干个一般的运输问题就是要解决把某种产品从若干个产地调运到若

2、干个销地，在每个产地的供应量与每个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。提下，如何确定一个使得总的运输费用最小的方案。运输问题运输问题例例例例1.1.1.1.某公司从两个产地某公司从两个产地A A1 1,A,A2 2将物品运往三个销地将物品运往三个销地B B1 1，B B2 2，B B3 3,各产地的产量、各销地的销量和各产各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问地运往各销地的每件物品的运费如下表所示：问应如何调运，

3、使得总运输费最小？应如何调运，使得总运输费最小？运输问题运输问题运输问题运输问题 解：解：我们知道我们知道A A1 1、A A2 2两个产地的总产量为：两个产地的总产量为：200+300=500200+300=500（件）；（件）；B B1 1，B B2 2，B B3 3三个销地三个销地的总销量为：的总销量为：150+150+200=500150+150+200=500（件）（件）,总产量总产量等于总销量这是一个产销平衡的运输问题。把等于总销量这是一个产销平衡的运输问题。把 A A1 1，A A2 2 的产量全部分配给的产量全部分配给B B1 1，B B2 2，B B3 3，正好满，正好满足这

4、三个销地的需要。足这三个销地的需要。运输问题运输问题 设设xij表示从产地表示从产地Ai调运到调运到Bj的运输量（的运输量（i=1,2;j=1,2,3），现将安排的运输量列表如下：），现将安排的运输量列表如下：运输问题运输问题 从上表可写出此问题的数学模型。从上表可写出此问题的数学模型。满足产地产量的约束条件为：满足产地产量的约束条件为：x11+x12+x13=200，x21+x22+x23=300.满足销地销量的约束条件为：满足销地销量的约束条件为：x11+x21=150，x12+x22=150，x13+x23=200.运输问题运输问题所以此运输问题的线性规划的模型如下：所以此运输问题的线性

5、规划的模型如下：目标函数：目标函数：min Z=6x11+4x12+6x13+6x21+5x22+5x23约束条件：约束条件：x11+x12+x13=200，x21+x22+x23=300，x11+x21=150，x12+x22=150，x13+x23=200.xij0.(i=1,2;j=1,2,3)运输问题运输问题 运输问题运输问题 假设有假设有m个生产地点（以后称为产地），可以供应某种物资，个生产地点（以后称为产地），可以供应某种物资，用用Ai表示，表示，i=1,2,m；有；有n个销售地（以后称为销地），用个销售地（以后称为销地），用Bj表示，表示，j=1,2,n；产地的产量和销地的销售量

6、分别为；产地的产量和销地的销售量分别为ai，i=1,2,m和和bj，j=1,2,n，从，从Ai到到Bj运输单位物资的运价运输单位物资的运价为为cij。运输问题运输问题如何调运，运输费用最小？如何调运，运输费用最小？表表3.1 运输问题运输问题如果运输问题的总产量等于其总销量，即如果运输问题的总产量等于其总销量，即则称该运输问题为产销则称该运输问题为产销平衡运输问题平衡运输问题；反之，；反之，称为产销不平衡运输问题。称为产销不平衡运输问题。产销平衡情况下的运输问题的数学模型：产销平衡情况下的运输问题的数学模型：假设假设xij表示从表示从Ai到到Bj的运量，则所求的数学模型为的运量，则所求的数学模

7、型为 运输问题运输问题该模型中，目标函数表示运该模型中，目标函数表示运输总费用，要求其极小化；输总费用，要求其极小化；第一个约束条件的意义是由第一个约束条件的意义是由各产地运往某一销地的物品各产地运往某一销地的物品数量之和等于该销地的销量；数量之和等于该销地的销量；第二个约束条件表示由某一第二个约束条件表示由某一产地运往各销地的物品数量产地运往各销地的物品数量之和等于该产地的产量；之和等于该产地的产量；第三个约束条件表示决策变第三个约束条件表示决策变量的非负条件。量的非负条件。运输问题运输问题约束条件展开：约束条件展开：min Z=(c11x11+c12x12+c1nx1n)+(c21x21+

8、c22x22+c2nx2n)+(cm1xm1+cm2xm2+cmnxmn)x11+x1n =a1 x21+x2n =a2 xm1+xmn =amx11+x21+xm1 =b1 x12+x22+xm2 =b2 x1n+x2n+xmn =bn约束方程式约束方程式共共mn个变个变量，量，m+n个个约束条件。约束条件。技术系数技术系数矩阵矩阵 系数矩阵的秩为系数矩阵的秩为m+n-1,基变量的个数是基变量的个数是m+n-1（即基（即基变量的个数产地个数销售地个数变量的个数产地个数销售地个数-1）运输问题运输问题求解平衡运输问题的表上作业法：求解平衡运输问题的表上作业法：（1）确定一个初始的可行调运方案：

9、）确定一个初始的可行调运方案：西北角法，最小元素法，伏格尔法西北角法，最小元素法，伏格尔法；（2）判断当前可行方案是否为最优：）判断当前可行方案是否为最优：闭回路法闭回路法和和位势法位势法；（3）方案调整直至找到最优方案。）方案调整直至找到最优方案。运输问题运输问题例例3.2 某公司有某公司有3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价表如工厂到各销售点的单位产品运价表如3.5所示。问该公司应所示。问该公司应如何调运产品，在满足各销售点

10、的需要量的前提下，使总的如何调运产品，在满足各销售点的需要量的前提下，使总的运费最小。运费最小。运输问题运输问题1）确定初始调运方案）确定初始调运方案西北角法西北角法 西北角法使最简单而且能快速给出一个初始方西北角法使最简单而且能快速给出一个初始方案的方法，它从运输量的表格中的西北角即左上案的方法，它从运输量的表格中的西北角即左上角开始确定运输量，并且取得尽可能大的运输量，角开始确定运输量，并且取得尽可能大的运输量，从而获得一个初始调运方案。从而获得一个初始调运方案。运输问题运输问题例例3.2 某公司有某公司有3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4个销售点销售

11、，各工厂的生产量、各销售点的销售量以及各个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价表如工厂到各销售点的单位产品运价表如3.5所示。问该公司应所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的如何调运产品，在满足各销售点的需要量的前提下，使总的运费最小。运费最小。运输问题运输问题 运输问题运输问题 检查全表，产销已平衡，得到初始调运方案：检查全表，产销已平衡，得到初始调运方案：x11=3,x12=4,x22=2,x23=2,x33=3,x34=6,其余其余xij=0，总运，总运费为费为135。方案中，调运量的个数正好是基变量应有的个数方案中

12、，调运量的个数正好是基变量应有的个数3+4-1=6。运输问题运输问题 对于任何一个产销平衡问题，应用西北角法总可对于任何一个产销平衡问题，应用西北角法总可以给出一个初始调运方案，因此，以给出一个初始调运方案，因此，平衡运输问题平衡运输问题必必有基本可行解，又因目标函数有下界（不能为负），有基本可行解，又因目标函数有下界（不能为负），因此，也因此，也必有最优解必有最优解。并且，对于平衡运输问题，。并且，对于平衡运输问题，当产量和销量均为整数时，其可行解和最优解也必当产量和销量均为整数时，其可行解和最优解也必为整数解。为整数解。运输问题运输问题 西北角法的优点是简便易行，缺点是在制定调西北角法的优

13、点是简便易行，缺点是在制定调运方案时，没有考虑运输费用，即没有采用运方案时，没有考虑运输费用，即没有采用“就就近供应近供应”的原则，这样所得的初始方案往往离最的原则，这样所得的初始方案往往离最优调运方案相差甚远。优调运方案相差甚远。运输问题运输问题最小元素法最小元素法：基本思想是就近供应，即从单位运价表中最小的：基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，以此类推，直到给出初始方案为止。运价开始确定产销关系，以此类推，直到给出初始方案为止。1）确定初始调运方案）确定初始调运方案最小元素法最小元素法 运输问题运输问题 检查全表，产销已平衡，得到初始调运方案：检查全表，产销已平

14、衡，得到初始调运方案：x13=4,x14=3,x21=3,x23=1,x32=6,x34=3,其余其余xij=0，总运费，总运费为为86。对比西北角法和最小元素法，由于考虑了运价的影对比西北角法和最小元素法，由于考虑了运价的影响，所以由最小元素法获得的调运方案要优于西北角响，所以由最小元素法获得的调运方案要优于西北角法。法。运输问题运输问题 1）确定初始调运方案）确定初始调运方案伏格尔法伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔造成在其他处要多花几倍的运费。伏格尔法考虑到，法考虑到，一产地的产品假如不能

15、按最小运费就近供应，就考虑一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处最小运费调运时，运费增加越多。因而对差额最大处就应当采用最小运费调运。就应当采用最小运费调运。基此，伏格尔法的步骤：基此，伏格尔法的步骤：运输问题运输问题第一步：在单位运价表中增加一行和一列，列的格位置相应填入第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该

16、列的次小运费与最小运费之差，称为列差额。置相应填入该列的次小运费与最小运费之差，称为列差额。运输问题运输问题第二步：从行或列差额中选出最大者，选择它所在行或列中的最小第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。如表中，元素。如表中，B2列是最大差额所在列，列是最大差额所在列，B2列中最小元素为列中最小元素为4，可，可确定确定A3的产品先供应的产品先供应B2的需要，同时将的需要，同时将B2列数字划去，如图：列数字划去，如图：运输问题运输问题第三步：对表中未划去的元素再分别计算出各行、各列的最小元素第三步：对表中未划去的元素再分别计算出各行、各列的最小元素和次最小运费的差额，并

17、填入该表的最右列和最下行。重复第一、和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。如图：二步。直到给出初始解为止。如图：运输问题运输问题 由以上可见，伏格尔法同最小元素法除在供求关由以上可见，伏格尔法同最小元素法除在供求关系的原则上不同外，其余步骤相同。伏格尔法给出系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解就是最优解。解。本例用伏格尔法给出的初始解就是最优解。运输问题运输问题2）最优解的判别）最优解的判别闭回路法闭回路法 在用西北角法和最

18、小元素法确定初始方案，产销平在用西北角法和最小元素法确定初始方案，产销平衡表中，我们称右上角没有填数字的格子为衡表中，我们称右上角没有填数字的格子为空格空格，而，而把右上角填有数字的个子称为把右上角填有数字的个子称为基格基格。闭回路闭回路，就是从某一，就是从某一空格出发空格出发，沿水平或垂直方，沿水平或垂直方向前进，如向前进，如遇基格可作垂直或水平方向转向（转向处遇基格可作垂直或水平方向转向（转向处称顶点）前进，也可穿越继续前进称顶点）前进，也可穿越继续前进。如。如遇空格不能转遇空格不能转向，必须穿越继续前进向，必须穿越继续前进，但，但最后仍回到原来的空格最后仍回到原来的空格，目的是围成一个矩

19、形的，或各边顺次垂直的曲折多变目的是围成一个矩形的，或各边顺次垂直的曲折多变形的闭合回路。形的闭合回路。运输问题运输问题2）最优解的判别）最优解的判别闭回路法闭回路法 闭回路的顶点除去起始和终了是同一个空格外，闭回路的顶点除去起始和终了是同一个空格外，其他所有顶点均为基格。凡是可行的调运方案，其他所有顶点均为基格。凡是可行的调运方案，每一个空格，也就是每一个非基变量，都可以画每一个空格，也就是每一个非基变量，都可以画一个闭回路，而且是唯一的。一个闭回路，而且是唯一的。思考：最小元素法中，思考：最小元素法中，(A1,B1)，(A2,B2)的的闭回路？闭回路？运输问题运输问题 运输问题运输问题 计

20、算各空格的检验数，它等于其闭回路上奇数点运价与偶数计算各空格的检验数，它等于其闭回路上奇数点运价与偶数点运价之负值的和。点运价之负值的和。ij=(第一第一顶顶点的运价点的运价)-(第二顶点的运价第二顶点的运价)+(第三顶点的运价第三顶点的运价)-(第四顶点的运价第四顶点的运价)=(奇数奇数顶顶点运价之和点运价之和)-(偶数偶数顶顶点运价之和点运价之和)运输问题运输问题 运输问题运输问题以以x11检验数为例检验数为例 运输问题运输问题将检验数填入产销平衡表中，并用括号括起来。将检验数填入产销平衡表中，并用括号括起来。运输问题运输问题 检验数的经济涵义是：在保证产销平衡的前提下，空检验数的经济涵义

21、是：在保证产销平衡的前提下，空格的调运量增加一个单位，相应在空格闭回路的偶数顶格的调运量增加一个单位，相应在空格闭回路的偶数顶点均减少一个单位，奇数顶点均增加一个单位后，所引点均减少一个单位，奇数顶点均增加一个单位后，所引起的总运费的改变量。起的总运费的改变量。正的空格检验数意味着总运费将正的空格检验数意味着总运费将增加，负的空格检验数意味着总费用将减少增加，负的空格检验数意味着总费用将减少。最优解判别准则：最优解判别准则：若所有若所有检验数都非负，则得到最优解检验数都非负，则得到最优解，即相应的运输，即相应的运输方案最优；若有方案最优；若有检验数小于零，则方案还需要调整检验数小于零，则方案还

22、需要调整。运输问题运输问题2）最优解的判别）最优解的判别位势法位势法 用闭回路法求检验数时，需要给每一个空格找一条用闭回路法求检验数时，需要给每一个空格找一条闭回路。当产销点很多时，空格的数量很大，计算检闭回路。当产销点很多时，空格的数量很大，计算检验数将十分费时。下面介绍一种较为简便的方法验数将十分费时。下面介绍一种较为简便的方法位位势法势法。计算过程如下：。计算过程如下：运输问题运输问题2）最优解的判别）最优解的判别位势法位势法（1）仅考虑基变量对应的运价）仅考虑基变量对应的运价（2）在表的下面和右边各增加一行和一列，分别称为位）在表的下面和右边各增加一行和一列，分别称为位势行和位势列。在

23、新增加的行、列中分别填上一些数字势行和位势列。在新增加的行、列中分别填上一些数字，表表中的各个数恰好等于它所对应的位势行和位势列的两中的各个数恰好等于它所对应的位势行和位势列的两个所填数字之和；表中用个所填数字之和；表中用ui(i=1,2,m)和和vj(j=1,2,n)分分别代表位势列和位势行上的各个数字，并分别称为别代表位势列和位势行上的各个数字，并分别称为ui和和vj为第为第i行和第行和第j列的位势。因它们之间相互关联，只要任选列的位势。因它们之间相互关联，只要任选其中一个值，其余均能算出。其中一个值，其余均能算出。运输问题运输问题令令u10运输问题运输问题（3）计算各空格处的位势）计算各

24、空格处的位势hij=ui+vj（4）计算各空格处的检验数）计算各空格处的检验数ij=cij-hij运输问题运输问题3）调运方案的改进调运方案的改进调入变量的确定：调入变量的确定：取绝对值最大的那个负空格检验数所对应取绝对值最大的那个负空格检验数所对应的非基变量作为调入变量的非基变量作为调入变量；调出变量的确定：以调入变量为第一顶点，沿着闭回路某一调出变量的确定：以调入变量为第一顶点，沿着闭回路某一前进方向，比较各偶数顶点的调运量，找出其最小值，这最前进方向，比较各偶数顶点的调运量，找出其最小值，这最小值所对应的变量为调出变量，而这个小值所对应的变量为调出变量，而这个最小值就是调整量最小值就是调

25、整量。调整调运方案：在调入变量所对应的闭回路中，所有调整调运方案：在调入变量所对应的闭回路中，所有奇数顶奇数顶点的运量都加上调整量，所有偶数顶点的运量都减去调整量点的运量都加上调整量，所有偶数顶点的运量都减去调整量。而该闭回路顶点以外的地方，所有运量而该闭回路顶点以外的地方，所有运量都不变都不变。运输问题运输问题3）调运方案的改进调运方案的改进调整后调整后的方案的方案运输问题运输问题3）调运方案的改进调运方案的改进再计算各空格处的检验数再计算各空格处的检验数空格处的检验数都为非负，已得到最优解。此时，总运空格处的检验数都为非负，已得到最优解。此时，总运费最小为费最小为35+102+31+18+

26、64+35=85元元运输问题运输问题总运费最小为总运费最小为35+102+31+18+64+35=85元元最终方案是：最终方案是：表上作业法计算中的问题表上作业法计算中的问题1、两个运价同时最小、两个运价同时最小 当遇到两个运价同时是最小，比如都是当遇到两个运价同时是最小，比如都是1，则任意，则任意选择一个分配运量。选择一个分配运量。运输问题运输问题表上作业法计算中的问题表上作业法计算中的问题2、无穷多最优解：、无穷多最优解：产销平衡问题必有最优解，如何判断是唯一最产销平衡问题必有最优解，如何判断是唯一最优解还是无穷多最优解。原则：某个非基变量（空优解还是无穷多最优解。原则：某个非基变量（空格

27、）的检验数为格）的检验数为0时，该问题有无穷多最优解。如时，该问题有无穷多最优解。如例中空格（例中空格（1，1）的检验数是）的检验数是0，表明例，表明例1有无穷多有无穷多最优解。可在表中，以（最优解。可在表中，以（1，1）为调入格，作闭回）为调入格，作闭回路路(1,1)+-(1,4)-(2,4)+-(2,1)-(1,1)+。确定。确定=min(2,3)=2。经调经调整后得到另一最整后得到另一最优优解。解。运输问题运输问题总运费最小为总运费最小为32+35+11+83+46+53=85元元最终方案是：最终方案是：运输问题运输问题3、退化、退化1）在用西北角法和最小元素法给出初始解时，有）在用西北

28、角法和最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现退化。价表上同时划去一行和一列，这时就出现退化。出现退化时，在相应的格中一定要填入一个出现退化时，在相应的格中一定要填入一个0，以，以表示此格为数字格。表示此格为数字格。举例：举例：运输问题运输问题西北角法退化西北角法退化 需要划去需要划去A1行或行或B2列，然后在（列，然后在（2,2）或）或（1,3）格中添加）格中添加1个个0。运输问题运输问题最小元素法退化最小元素法退化需要需要划去划去B2列和列和A3行，然后行，然后在空格在空格(1,2),

29、(2,2),(3,3),(3,4)(1,2),(2,2),(3,3),(3,4)中任选一个添加一个中任选一个添加一个0 0。运输问题运输问题3、退化、退化2）在用闭回路法调整时，在闭回路上出现两个）在用闭回路法调整时，在闭回路上出现两个和两个以上的具有（和两个以上的具有（-1）标记的相等的最小值，）标记的相等的最小值，这时只能选择其中一个作为调入量。而经调整后，这时只能选择其中一个作为调入量。而经调整后，得到退化解，这时另一个数字格必须填入一个得到退化解，这时另一个数字格必须填入一个0，表明它时基变量。当出现退化解后，并作改进，表明它时基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有

30、标记（调整时，可能在某闭回路上有标记（-1）的取值）的取值为为0的数字格，这是应取调整量的数字格，这是应取调整量=0举例：举例：运输问题运输问题3、退化、退化运输问题运输问题3、退化、退化运输问题运输问题练习：设某物资需要由产地练习：设某物资需要由产地A1,A2,A3调往销地调往销地B1,B2,B3,B4，各，各产地的产量和各销地的产量以及各产地到各销地的单位运价如产地的产量和各销地的产量以及各产地到各销地的单位运价如表所示，请分别用最小元素法和伏格尔法确定最优方案。表所示，请分别用最小元素法和伏格尔法确定最优方案。运输问题运输问题运输问题运输问题该方案为最优调运方案，它对应的目标函数值即最小

31、该方案为最优调运方案，它对应的目标函数值即最小总运费为总运费为Z=143660361543=57第3节 产销不平衡的运输问题及其求解方法v前前面面所所讲讲表表上上作作业业法法，都都是是以以产产销销平平衡衡为为前前提提条条件件的的；但但是是实实际际问问题题中中产产销销往往往往是是不不平平衡衡的的。就就需需要要把把产产销销不不平衡的问题化成产销平衡的问题。平衡的问题化成产销平衡的问题。v当产大于销时当产大于销时 第3节 产销不平衡的运输问题及其求解方法v运输问题的数学模型可写成运输问题的数学模型可写成第3节 产销不平衡的运输问题及其求解方法v由于由于总总的的产产量大于量大于销销量，就要考量，就要考

32、虑虑多余的物多余的物资资在哪一个在哪一个产产地就地地就地储储存的存的问题问题。这时，只要增加一个假想的销地这时，只要增加一个假想的销地jm+1（实际上是储存），该销地的总需要量为：（实际上是储存），该销地的总需要量为：设设xi,n+1是是产产地地Ai的的储储存量，于是有：存量，于是有：可转化为产销平衡的运输问题可转化为产销平衡的运输问题因为因为第3节 产销不平衡的运输问题及其求解方法可转化为产销平衡的运输问题可转化为产销平衡的运输问题因为因为 在单位运价表中，从各产地到假想销地的单位运在单位运价表中，从各产地到假想销地的单位运价为价为ci,n+1=0，就可转化成产销平衡的运输问题。，就可转化成

33、产销平衡的运输问题。第3节 产销不平衡的运输问题及其求解方法当当产产大于大于销时销时，只要增加一个假想的，只要增加一个假想的销销地地j=n+1(实际实际上上是是储储存存)，该销该销地地总总需要量需要量为为 而在单位运价表中从各产地到假想销地的单位运价为，而在单位运价表中从各产地到假想销地的单位运价为，就转化成一个产销平衡的运输问题。就转化成一个产销平衡的运输问题。第3节 产销不平衡的运输问题及其求解方法 在最优解中，虚设产地在最优解中，虚设产地Am+1到销地到销地Bj的运量实际上就的运量实际上就是最后分配方案中销地是最后分配方案中销地Bj的缺货量。的缺货量。在产销不平衡问题中，如果某产地不允许

34、将物资就地在产销不平衡问题中，如果某产地不允许将物资就地贮存或者不允许缺货，则要令相应运价贮存或者不允许缺货，则要令相应运价Ci,n+1或或Cm+1,j=M（M是充分大的正数）。是充分大的正数）。第3节 产销不平衡的运输问题及其求解方法例例2 设有三个化肥厂设有三个化肥厂(A，B，C)供应四个地区供应四个地区(，)的农用化肥。假定等量的化肥在这些地区使用的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表肥厂到各地区运送单位化肥的运价如表3-25所示。试求所示。试求出总的运费最

35、节省的化肥调拨方案。出总的运费最节省的化肥调拨方案。第3节 产销不平衡的运输问题及其求解方法v解解：这这是是一一个个产产销销不不平平衡衡的的运运输输问问题题，总总产产量量为为160160万万吨吨，四四个个地地区区的的最最低低需需求求为为110110万万吨吨，最最高高需需求求为为无无限限。根根据据现现有有产产量量，第第个个地地区区每每年年最最多多能能分分配配到到6060万万吨吨，这这样样最最高高需需求求为为210210万万吨吨，大大于于产产量量。为为了了求求得得平平衡衡，在在产产销销平平衡衡表表中中增增加加一一个个假假想想的的化化肥肥厂厂D D，其其年年产产量量为为5050万万吨吨。由由于于各各

36、地地区区的的需需要要量量包包含含两两部部分分，如如地地区区，其其中中3030万万吨吨是是最最低低需需求求，故故不不能能由由假假想想化化肥肥厂厂D D供供给给，令令相相应应运运价价为为M(M(任任意意大大正正数数)，而而另另一一部部分分2020万万吨吨满满足足或或不不满满足足均均可可以以，因因此此可可以以由由假假想想化化肥肥厂厂D D供供给给，按按前前面面讲讲的的，令令相相应应运运价价为为0 0。对对凡凡是是需需求求分分两两种种情情况况的的地地区区，实实际际上上可可按按照照两两个个地地区区看看待待。这这样样可可以以写写出出这这个个问问题题的的产产销销平平衡衡表表(表表3-26)3-26)和和单单位位运运价价表表(表表3-27)3-27)。第3节 产销不平衡的运输问题及其求解方法v产销平衡表(表3-26),单位运价表(表3-27)第3节 产销不平衡的运输问题及其求解方法v根据表上作业法计算，可以求得这个问题的最优方案如表3-28所示)