运输问题表上作业法

《运输问题表上作业法》由会员分享，可在线阅读，更多相关《运输问题表上作业法（85页珍藏版）》请在装配图网上搜索。

1、4.2 4.2 表上作业法表上作业法表上作业法表上作业法表上作业法与单纯形法的关系表上作业法与单纯形法的关系表上作业法的基本步骤表上作业法的基本步骤确定初始基可行解确定初始基可行解最小元素法的基本步骤最小元素法的基本步骤伏格尔法伏格尔法n运输问题的求解采用表上作业法，即用列运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。计算方法，实质上是单纯形法。n表上作业法是一种特定形式的单纯形法，表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所它与单纯形法有着完全相同的解题步骤，所不同的只

2、是完成各步采用的具体形式。不同的只是完成各步采用的具体形式。1.1.表上作业法表上作业法2.2.表上作业法与单纯形法的关系表上作业法与单纯形法的关系|表上作业法中的最小元素法和伏格尔法实质表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；上是在求单纯形表中的初始基可行解；|表上作业法中的表上作业法中的“位势法位势法”实质上是在求单实质上是在求单纯形表中的检验数；纯形表中的检验数；|调运方案表中数字格的数实质上就是单纯形调运方案表中数字格的数实质上就是单纯形法中基变量的值；法中基变量的值；|调运方案表上的调运方案表上的“闭回路法闭回路法”实质上是在做实质上是在做单纯形表上的

3、换基迭代。单纯形表上的换基迭代。|（1 1）找出初始基可行解：）找出初始基可行解： m+n-1m+n-1个数字格（基变个数字格（基变量）；量）；|（2 2）求各非基变量（空格）的检验数。）求各非基变量（空格）的检验数。 ,那么那么选取选取xijij为入基变量；为入基变量； |（3 3）确定入基变量，若）确定入基变量，若 min|0ijijlk3.3.表上作业法的基本步骤表上作业法的基本步骤| （4 4）确定出基变量，找出入基变量的闭合回路；）确定出基变量，找出入基变量的闭合回路；| （5 5）在表上用闭合回路法调整运输方案；）在表上用闭合回路法调整运输方案；| （6 6）重复）重复2 2、3

4、3、4 4、5 5步骤，直到得到最优解。步骤，直到得到最优解。4 4、确定初始基可行解、确定初始基可行解 |与一般的线性规划不同，与一般的线性规划不同，产销平衡的运输问产销平衡的运输问题一定具有可行解（同时也一定存在最优题一定具有可行解（同时也一定存在最优解）。解）。|最小元素法最小元素法（the least cost rule）和伏格尔法和伏格尔法（Vogels approximation method）。）。 z最小元素法的基本思想是最小元素法的基本思想是就近供应就近供应，即从单位，即从单位运价表中最小的运价开始确定产销关系，依此运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本

5、方案为止类推，一直到给出基本方案为止.最小元素法最小元素法|找出最小运价，确定供求关系，最大量的供找出最小运价，确定供求关系，最大量的供应应 ；|划掉已满足要求的行或划掉已满足要求的行或 ( (和和) ) 列，如果需要列，如果需要同时划去行和列，必须要在该行或列的任意同时划去行和列，必须要在该行或列的任意位置填个位置填个“0”0”；|在剩余的运价表中重复在剩余的运价表中重复1 1、2 2两步，直到得到两步，直到得到初始基可行解。初始基可行解。5 5、最小元素法的基本步骤、最小元素法的基本步骤|最小元素法最小元素法最小元素法的基本思想是就近供应，即最小元素法的基本思想是就近供应，即从单位运价表中

6、最小的运价开始确定产从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方销关系，依此类推，一直到给出基本方案为止。案为止。 表表4-1甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）3656最小元素法的应用（以引例最小元素法的应用（以引例4-14-1为例）为例） 甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）3656甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）3656表表4-2表表4-33 甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059

7、销量（销量（bj）3656表表4-3甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）3656甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）3656表表4-4表表4-531甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）3656表表4-5 第三步：在表第三步：在表4-54-5中再找出最小运价中再找出最小运价“3”3”，这样一步步地进行下去，直到单位运价表上这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。的所有元素均被划去为止。 表表4-7甲甲乙乙丙丙丁丁产量（产量（ai）A

8、 A7B B4C C9销量（销量（b bj j）3 3656表表4-6甲甲乙乙丙丙丁丁产量（产量（ai）A311107B1984C7109销量（销量（bj）3656321344653 33|最后在产销平衡表上得到一个调运方案，见最后在产销平衡表上得到一个调运方案，见表表4-64-6。这一方案的总运费为。这一方案的总运费为8686个单位。个单位。|最小元素法各步在运价表中划掉的行或列是需求得最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到入一个数相应地划掉一行或一列，这

9、样最终将得到一个具有一个具有m+n-1m+n-1个数字格（基变量）的初始基可行解。个数字格（基变量）的初始基可行解。 6.6.应注意的问题应注意的问题 表表4-7甲甲乙乙丙丙丁丁产量（产量（ai）A3113104B19284C7410512销量（销量（bj）3656表表4-8甲甲乙乙丙丙丁丁产量（产量（ai）A4B4C12销量（销量（bj）365631 47. 7. 举例举例 将例将例4-14-1的各工厂的产量做适当调整（调的各工厂的产量做适当调整（调整结果见表整结果见表4-74-7），就会出现上述特殊情况。），就会出现上述特殊情况。 0 06 66 68.8.伏格法尔法伏格法尔法伏格尔法的基

10、本步骤：伏格尔法的基本步骤：8.8.伏格尔法伏格尔法1.1.计算每行、列两个最小运价的差；计算每行、列两个最小运价的差；2.2.找出最大差所在的行或列；找出最大差所在的行或列；3.3.找出该行或列的最小运价，确定供求关系，最大量找出该行或列的最小运价，确定供求关系，最大量的供应的供应 ；4.4.划掉已满足要求的行或划掉已满足要求的行或 ( (和和) ) 列，如果需要同时划列，如果需要同时划去行和列，必须要在该行或列的任意位置填个去行和列，必须要在该行或列的任意位置填个“0”0”；5.5.在剩余的运价表中重复在剩余的运价表中重复1414步，直到得到初始基可步，直到得到初始基可行解。行解。表表4-

11、1甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）3656表表4-12甲甲乙乙丙丙丁丁两最小元素之差两最小元素之差A311310B1928C7105两最小元素之差两最小元素之差13011254表表4-13甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）3656表表4-14甲甲乙乙丙丙丁丁两最小元素之差两最小元素之差A311310B1928C7410两最小元素之差两最小元素之差562130125表表4-15甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）365663表表4-16甲甲乙乙丙丙丁丁两最小元素之差两最小元素之

12、差A311310B928C74105两最小元素之差两最小元素之差212011表表4-17甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）3656633表表4- 18 甲甲乙乙丙丙丁丁两最小元素之差两最小元素之差A31110B1928C74105两最小元素之差两最小元素之差12673表表4-19甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）3656表表4-20甲甲乙乙丙丙丁丁两最小元素之差两最小元素之差A311310B192C74105两最小元素之差两最小元素之差63352812|总运费为总运费为85|由以上可见，伏格尔法同最小元素法除在确由以上可见，伏格尔法同

13、最小元素法除在确定供求关系的原则上不同外，其余步骤是完定供求关系的原则上不同外，其余步骤是完全相同的。伏格尔法给出的初始解比最小元全相同的。伏格尔法给出的初始解比最小元素法给出的初始解一般来讲会更接近于最优素法给出的初始解一般来讲会更接近于最优解。解。 表表4-23甲甲乙乙丙丙丁丁产量（产量（ai）A7B4C9销量（销量（bj）36566335124.2.2 4.2.2 基可行解的最优性检验基可行解的最优性检验n对初始基可行解的最优性检验有对初始基可行解的最优性检验有闭合回路法闭合回路法和和位势法位势法两种基本方法。两种基本方法。闭合回路法具体、闭合回路法具体、直接，并为方案调整指明了方向；而

14、位势法直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。具有批处理的功能，提高了计算效率。|所谓所谓闭合回路闭合回路是是在已给出的调运方案的运输在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转填入数字的格才能向左或右转9090度（当然也度（当然也可以不改变方向）继续前进，这样继续下去，可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个

15、空格存在唯一的闭折线叫做闭合回路。一个空格存在唯一的闭回路。回路。|所谓闭合回路法，就是对于代表非基变量的所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整空格（其调运量为零），把它的调运量调整为为1 1，由于产销平衡的要求，由于产销平衡的要求, ,我们必须对这个我们必须对这个空格的闭回路的顶点的调运量加上或减少空格的闭回路的顶点的调运量加上或减少1 1。最后我们计算出由这些变化给整个运输方案最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数变量的空格的检验数也即非基

16、变量的检验数都大于等于零，则已求得最优解，否则继续都大于等于零，则已求得最优解，否则继续迭代找出最优解。迭代找出最优解。1.1.闭合回路闭合回路n下面就以表下面就以表4-64-6中给出的初始基可行解（最中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论闭合小元素法所给出的初始方案）为例，讨论闭合回路法。回路法。表表4-24甲甲乙乙丙丙丁丁产量（产量（ai）A 437B 3 14C639销量（销量（bj）3656（+3）（-3）（+2）（-1）|从表从表4-64-6给定的初始方案的任一空格出发寻找闭合回路，如对给定的初始方案的任一空格出发寻找闭合回路，如对于空格（于空格（A A，甲）在

17、初始方案的基础上将，甲）在初始方案的基础上将A A生产的产品调运一个生产的产品调运一个单位给甲，为了保持新的平衡，就要依次在（单位给甲，为了保持新的平衡，就要依次在（A A，丙）处减少，丙）处减少一个单位、（一个单位、（B B，丙）处增加一个单位、（，丙）处增加一个单位、（B B，甲）处减少一个，甲）处减少一个单位；即要寻找一条除空格（单位；即要寻找一条除空格（A A，甲）之外其余顶点均为有数，甲）之外其余顶点均为有数字格（基变量）组成的闭合回路。表字格（基变量）组成的闭合回路。表4-244-24中用虚线画出了这条中用虚线画出了这条闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运闭合回路

18、。闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的价，单位运价前的“+”+”、“-”-”号表示运量的调整方向。号表示运量的调整方向。|对应这样的方案调整，运费会有什么变化呢？可以对应这样的方案调整，运费会有什么变化呢？可以看出（看出（A A，甲）处增加一个单位，运费增加，甲）处增加一个单位，运费增加3 3个单位；个单位；在（在（A A，丙）处减少一个单位，运费减少，丙）处减少一个单位，运费减少3 3个单位；在个单位；在（B B，丙）处增加一个单位，运费增加，丙）处增加一个单位，运费增加2 2个单位；在个单位；在（B B，甲）处减少一个单位，运费减少，甲）处减少一个单位，运费减少1

19、1个单位。增减个单位。增减相抵后，总的运费增加了相抵后，总的运费增加了1 1个单位。由检验数的经济个单位。由检验数的经济含义可以知道，（含义可以知道，（A A，甲）处单位运量调整所引起的，甲）处单位运量调整所引起的运费增量就是（运费增量就是（A A，甲）的检验数，即，甲）的检验数，即1111=1=1。 表表4-24甲甲乙乙丙丙丁丁产量（产量（ai）A 437B 3 14C639销量（销量（bj）3656（+3）（-3）（+2）（-1）|仿照此步骤可以计算初始方案中所有空仿照此步骤可以计算初始方案中所有空格的检验数，表格的检验数，表4-254-25表表4-304-30展示了各展示了各检验数的计算

20、过程，表检验数的计算过程，表4-304-30给出了最终给出了最终结果。可以证明，对初始方案中的每一结果。可以证明，对初始方案中的每一个空格来说个空格来说“闭合回路存在且唯一闭合回路存在且唯一”。表表4-25甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1（+11）43（-10）7B314C6（-4）3（+5）9销量（销量（bj）3656表表4-26甲乙丙丁产量（ai）A 11 = 1 12 = 24（+3）3（-10）7B3（+9）1（-2）4C6（-4）3（+5）9销量（bj）3656表表4-27甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 24（+3）3（-10）7B3

21、22 = 11（-2）（+8）4C639销量（销量（bj）3656表表4-28甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 24（-3）3（+10）7B3 22 = 11 24 = -14C6（+10）3（-5）9销量（销量（bj）3656表表4-29甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 24（-3）3（+10）7B3（-1） 22 = 11（+2） 24 = -14C（+7）6 33 = 123（-5）9销量（销量（bj）3656表表4-30甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C

22、31 = 106 33 = 1239销量（销量（bj）3656|如果检验数表中所有数字均大于等于零，如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方致运费的增加，即给定的方案是最优方案。在表案。在表4-304-30中，中， 2424 = -1, = -1,说明方案说明方案需要进一步改进。需要进一步改进。 2.2.位势法位势法)(jiijijvucn这一表达式完全可以通过先前所述的闭合这一表达式完全可以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表回路法得到。在某一的闭合回路上（如下表所示），由于

23、基变量的运价等于其所对应的所示），由于基变量的运价等于其所对应的行位势与列位势之和，即：行位势与列位势之和，即： kiikvuckllkvucjlljvuclkxlukv非基变量非基变量基变量基变量ijxiuljxjv（-cik）基变量）基变量ikx（+clk）基变量）基变量 （+cij） （-clj）于是于是所以所以)()()(jlklkiijljlkikijijvuvuvuccccc)(jiijijvucn对于一个具有对于一个具有m m个产地、个产地、n n个销地的运输问题，应具个销地的运输问题，应具有有m m个行位势、个行位势、n n个列位势，即具有个列位势，即具有“m+nm+n”个位势

24、。个位势。运输问题基变量的个数只有运输问题基变量的个数只有“m+n-1”m+n-1”个，所以利个，所以利用基变量所对应的用基变量所对应的“m+n-1”m+n-1”个方程，求出个方程，求出“m+nm+n”个位势，进而计算各非基变量的检验数是不现实的。个位势，进而计算各非基变量的检验数是不现实的。n通常可以通过在这些方程中对任意一个因子假定一通常可以通过在这些方程中对任意一个因子假定一个任意的值（如个任意的值（如u1=0等等），再求解其余的等等），再求解其余的“m+n-1”个未知因子，这样就可求得所有空格（非基变量）个未知因子，这样就可求得所有空格（非基变量）的检验数。仍以表的检验数。仍以表4-6

25、中给出的初始基可行解（最小中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论位势法求解元素法所给出的初始方案）为例，讨论位势法求解非基变量检验数的过程。非基变量检验数的过程。|第一步：把方案表中基变量格填入其相应的第一步：把方案表中基变量格填入其相应的运价并令运价并令u u1 1=0 =0 ；让每一个基变量；让每一个基变量xijij都有都有c cijij= = u ui i + + v vj j ，可求得所有的位势，如表，可求得所有的位势，如表4-324-32所所示。示。iujv表表4-32甲甲乙乙丙丙丁丁A310B12C45|第二步：利用第二步：利用 )(jiijijvuc计算各非

26、基变量计算各非基变量xij 的检验数，结果见表的检验数，结果见表4-30。 103-1-59204.2.34.2.3方案的优化方案的优化n在负检验数中找出最小的检验数，该检验数在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入基变量所所对应的变量即为入基变量。在入基变量所处的闭合回路上，赋予入基变量最大的增量，处的闭合回路上，赋予入基变量最大的增量，即可完成方案的优化。在入基变量有最大增即可完成方案的优化。在入基变量有最大增量的同时，一定存在原来的某一基变量减少量的同时，一定存在原来的某一基变量减少为为“0”0”，该变量即为出基变量。切记出基，该变量即为出基变量。切记出基变量

27、的变量的“0”0”运量要用运量要用“空格空格”来表示，而来表示，而不能留有不能留有“0”0”。 在表在表4-304-30中，中， 24min|01ijij ，故选择，故选择x24为入基变量。在入基变量为入基变量。在入基变量x24所处的闭合回路上所处的闭合回路上（如表（如表4-33所示），赋予最大的增量所示），赋予最大的增量“1”，相应地，相应地有有x23最大的增量最大的增量“1”，相应地有，相应地有x23出基出基, x13=5,x14=2.利用闭合回路法或位势法计算各空格（非基变量）的利用闭合回路法或位势法计算各空格（非基变量）的检验数，可得表检验数，可得表4-34（同伏格尔法的初始解表（同伏

28、格尔法的初始解表4-23）。）。 表表4-30甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C 31 = 106 33 = 1239销量（销量（bj）3656表表4-33甲甲乙乙丙丙丁丁产量（产量（ai）A 11 = 1 12 = 2437B3 22 = 11 24 = -14C 31 = 106 33 = 1239销量（销量（bj）3656表表4-34甲甲乙乙丙丙丁丁产量（产量（ai）A527B314C639销量（销量（bj）3656 由于表由于表4-33中的检验数均大于等于零，所以表中的检验数均大于等于零，所以表4-33（同伏格

29、尔法（同伏格尔法所给出的初始解表所给出的初始解表4-23）给出的方案是最优方案，这个最优方案的）给出的方案是最优方案，这个最优方案的运费是运费是85个单位。个单位。 23 = 1 31 = 9 22 = 2 11 = 1 12 = 2 33 = 124.34.3运输问题的拓展运输问题的拓展 n总产量大于总销量的运输问题即为产大于总产量大于总销量的运输问题即为产大于销的运输问题。销的运输问题。n在实际问题中，产大于销意味着某些产品在实际问题中，产大于销意味着某些产品被积压在仓库中。可以这样设想，被积压在仓库中。可以这样设想，如果把如果把仓库也看成是一个假想的销地，并令其销仓库也看成是一个假想的销

30、地，并令其销量刚好等于总产量与总销量的差量刚好等于总产量与总销量的差；那么，；那么，产大于销的运输问题就转换成产销平衡的产大于销的运输问题就转换成产销平衡的运输问题运输问题 n假想一个销地，相当于在原产销关系表上假想一个销地，相当于在原产销关系表上增加一列。增加一列。 4.3.1产大于销的运输问题产大于销的运输问题 n假想列所对应的运价假想列所对应的运价|由于假想的销地代表的是仓库，而我们由于假想的销地代表的是仓库，而我们优化的运费是产地与销地间的运输费用，优化的运费是产地与销地间的运输费用，并不包括厂内的运输费用；所以假想列并不包括厂内的运输费用；所以假想列所对应的运价都应取为所对应的运价都

31、应取为“0”0”。n至此，我们已经将产大于销的运输问题至此，我们已经将产大于销的运输问题转换成产销平衡的运输问题，进一步的转换成产销平衡的运输问题，进一步的求解可利用上节介绍的表上作业法来完求解可利用上节介绍的表上作业法来完成。成。 n 例例4-2 4-2 将表将表4-354-35所示的产大于销所示的产大于销的运输问题转换成产销平衡的运输问的运输问题转换成产销平衡的运输问题题表表4-35甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C7410512销量（销量（bj）3656|解解 此运输问题的总产量为此运输问题的总产量为2323、总销量为、总销量为2020，所以，所以假设一个销

32、地戊并令其销量刚好等于总产量与总销假设一个销地戊并令其销量刚好等于总产量与总销量的差量的差“3”3”。取假想的戊列所对应的运价都为。取假想的戊列所对应的运价都为“0”0”，可得表，可得表4-364-36所示的产销平衡运输问题。所示的产销平衡运输问题。表表4-36甲甲乙乙丙丙丁丁戊戊产量（产量（ai）A31131007B192804C74105012销量（销量（bj）365634.3.2销大于产的运输问题销大于产的运输问题 n总销量大于总产量的运输问题即为销大于产的运总销量大于总产量的运输问题即为销大于产的运输问题。输问题。n可以这样设想，可以这样设想，假想一个产地，并令其产量刚好假想一个产地，

33、并令其产量刚好等于总销量与总产量的差；等于总销量与总产量的差；那么，销大于产的运那么，销大于产的运输问题同样可以转换成产销平衡的运输问题输问题同样可以转换成产销平衡的运输问题 n假想的产地并不存在，于是各销地从假想产地所假想的产地并不存在，于是各销地从假想产地所得到的运量，实际上所表示的是其未满足的需求。得到的运量，实际上所表示的是其未满足的需求。n由于假想的产地与各销地之间并不存在实际的运由于假想的产地与各销地之间并不存在实际的运输，所以假想的产地行所有的运价都应该是输，所以假想的产地行所有的运价都应该是“0”0”。n至此，我们又将销大于产的运输问题转换成了产至此，我们又将销大于产的运输问题

34、转换成了产销平衡的运输问题。销平衡的运输问题。 例例4-3 4-3 将表将表4-374-37所示的销大于产所示的销大于产的运输问题转换成产销平衡的运输的运输问题转换成产销平衡的运输问题问题表表4-37甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059销量（销量（bj）11656|解解 此运输问题的总产量为此运输问题的总产量为2020、总销量为、总销量为2828，所以，所以假设一个产地假设一个产地D D并令其产量刚好等于总销量与总产量并令其产量刚好等于总销量与总产量的差的差“8”8”。令假想的。令假想的D D行所对应的运价都为行所对应的运价都为“0”0”，可得表可得表4

35、-374-37所示的产销平衡运输问题所示的产销平衡运输问题。表表4-38甲甲乙乙丙丙丁丁产量（产量（ai）A3113107B19284C741059D00008销量（销量（bj）116564.3.3运输问题的应用举例运输问题的应用举例n 例例4-4 4-4 设有三个化肥厂供应四个地区的设有三个化肥厂供应四个地区的化肥需求，假定等量化肥在这些地区的使化肥需求，假定等量化肥在这些地区的使用效果相同。各化肥厂年产量、各地区年用效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化需要量及从各化肥厂到各地区运送单位化肥的单位运价如表肥的单位运价如表4-394-39所示，试求出总的所示，

36、试求出总的运费最节省的化肥调拨方案。运费最节省的化肥调拨方案。表表4-39地区地区1地区地区2地区地区3地区地区4年产量年产量化肥厂化肥厂A1613221750化肥厂化肥厂B1413191560化肥厂化肥厂C192023M50年需要量年需要量/万万t最低需求最低需求3070010最高需求最高需求507030不限不限|根据现有产量，除满足地区根据现有产量，除满足地区1 1、地区、地区2 2和地区和地区3 3的的最低需求外，地区最低需求外，地区4 4每年最多能分配到每年最多能分配到6060万吨，万吨，这样其不限的最高需求可等价认为是这样其不限的最高需求可等价认为是6060万吨。万吨。 160307

37、0060|解解 这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量为为160160万吨，四个地区的最低需求为万吨，四个地区的最低需求为110110万吨，最万吨，最高需求为无限高需求为无限。|按最高需求分析，总需求为按最高需求分析，总需求为210210万吨，大于总万吨，大于总产量产量160160万吨，将此问题定义为销大于产的运万吨，将此问题定义为销大于产的运输问题。输问题。|为了求得平衡，在产销平衡表中增加一个假想为了求得平衡，在产销平衡表中增加一个假想的化肥厂的化肥厂D D，令其年产量为，令其年产量为5050万吨。万吨。 |各地区的需要量包含最低和最高两部分：如地各地区的

38、需要量包含最低和最高两部分：如地区区1 1，其中，其中3030万吨是最低需求，故这部分需求万吨是最低需求，故这部分需求不能由假想的化肥厂不能由假想的化肥厂D D来供给，因此相应的运来供给，因此相应的运价定义为任意大正数价定义为任意大正数M M ；而另一部分；而另一部分2020万吨满万吨满足与否都是可以的，因此可以由假想化肥厂足与否都是可以的，因此可以由假想化肥厂D D来供给，按前面讲的，令相应运价为来供给，按前面讲的，令相应运价为“0”0”。 210 16050|凡是需求分两种情况的地区，实际上可按凡是需求分两种情况的地区，实际上可按照两个地区来看待，这样可以将表照两个地区来看待，这样可以将表

39、4-394-39所示所示的运输问题转换为表的运输问题转换为表4-404-40所示的运输问题。所示的运输问题。 表表4-40 （单位：万吨）（单位：万吨）地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量化肥厂化肥厂A16161322171750化肥厂化肥厂B14141319151560化肥厂化肥厂C19192023MM50化肥厂化肥厂DM0M0M050年需要量年需要量302070301050用表上作业法计算，可以求得这个问题的最优方案用表上作业法计算，可以求得这个问题的最优方案如表如表4-41所示。所示。地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最

40、小元素差两最小元素差A161613221717B141413191515C19192023MMDM0MM0两最小元素差两最小元素差地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量3020703010501903021402153100地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A161613221717B141413191515C19192023MMDM0M0M两最小元素差两最小元素差214021531000地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50

41、B60C50D50年需要量年需要量3020703010503020地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A1616221717B141413191515C19192023MMDM0M0M两最小元素差两最小元素差2202231000地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量30207030105030201350地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A1616221717B1414131915C19192023MMDM0M0M两最

42、小元素差两最小元素差557MM31000地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量302070301050302013501510地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A1616221717B14141319C19192023MMDM0M0M两最小元素差两最小元素差557MM31000地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量3020703010503020135015101530地区地区1 地区地区1地

43、区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A1616221717B1419C19192023MMDM0M0M两最小元素差两最小元素差557MM30000地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量3020703010503020135015101530132014地区地区1 地区地区1地区地区2地区地区3地区地区4地区地区4两最小元素差两最小元素差A1616221717B141419C19192023MMDM0M0M两最小元素差两最小元素差557MM31000地区地区1 地区地区1地区地区2地区地区3地区

44、地区4地区地区4年产量年产量A50B60C50D50年需要量年需要量3020703010503020135015101530132003020 例例4-6 4-6 在在A1、A2、A3、A4、A5和和A6六个经济区六个经济区之间有砖、砂子、炉灰、块石、卵石、木材和之间有砖、砂子、炉灰、块石、卵石、木材和钢材七种物资需要运输。具体的运输需求如表钢材七种物资需要运输。具体的运输需求如表4-434-43所示，各地点间的路程（公里）见表所示，各地点间的路程（公里）见表4-444-44，试确定一个最优的汽车调度方案。试确定一个最优的汽车调度方案。表表4-43货物货物起点起点 终点终点车次车次起点起点终点

45、终点车次车次起点起点 终点终点车次车次砖砖A1A311A1A52A1A66砂子砂子A2A114A2A33A2A63炉灰炉灰A3A19A4A14块石块石A3A47A3A65卵石卵石A4A28A4A53木材木材A5A22钢材钢材A6A44表表4-44 到到从从A2A3A4A5A6A121191315A22101410A3459A4416A56|汽车的最优调度实质上就是空车行驶的汽车的最优调度实质上就是空车行驶的公里数最少。先构造如表公里数最少。先构造如表4-454-45所示的各地所示的各地区汽车出入平衡表，表中区汽车出入平衡表，表中“十十”号表示该号表示该点产生空车，点产生空车，“”号表示该点需要

46、调进号表示该点需要调进空车。空车。表表4-44A1A2A3A4A5A6出车数出车数1920211524来车数来车数27101411514平衡数平衡数+8-10-7-4+3+10|平衡结果平衡结果A A1 1、A A5 5、A A6 6除装运自己的货物外，可除装运自己的货物外，可多出空车多出空车2121车次；车次；A A2 2、A A3 3、A A4 4缺缺2121车次。按最车次。按最小空驶调度，可构造表小空驶调度，可构造表4-464-46所示的运输问题所示的运输问题数据表，进而可得表数据表，进而可得表4-474-47所示的最优调度方所示的最优调度方案。案。 表表4-45A2A3A4aiA121

47、198A514543A61091610bj1074表表4-46A2A3A4aiA188A533A627110bj1074作作 业业课本课本P P6262：6 6、7 7题题课本课本P P6363：8 8题题2021-11-20第第6262页习题页习题6.6.已知某厂每月可生产甲产品已知某厂每月可生产甲产品270270吨，先运至吨，先运至A A1 1、A A2 2、A A3 3三个仓库，然后在分别供应三个仓库，然后在分别供应B B1 1、B B2 2、B B3 3、B B4 4、B B5 5五个用户。已知仓库容量分别为五个用户。已知仓库容量分别为5050、100100、150150吨，各用户的需

48、要量分别为吨，各用户的需要量分别为2525、105105、6060、3030、7070吨。已知从该厂经各仓库然后供应吨。已知从该厂经各仓库然后供应各用户的运费如下表所示，试确定一个使总运各用户的运费如下表所示，试确定一个使总运费最少的调运方案。费最少的调运方案。|仓库总容量：仓库总容量：50+100+150=30050+100+150=300（t t）|各地区需求：各地区需求：25+105+60+30+70=29025+105+60+30+70=290（t t）|由于该厂每月最多生产甲产品由于该厂每月最多生产甲产品270t270t，则仓库有，则仓库有30t30t不满，各地区有不满，各地区有20

49、t20t不能满足需求不能满足需求|可假设存在仓库可假设存在仓库A A4 4，它的存储量为，它的存储量为20t20t，用户，用户B B6 6 的的需求量为需求量为30t30t。这样就转化为产销平衡问题。由于。这样就转化为产销平衡问题。由于A A4 4 与与B B6 6都是假设的，不需要运输，故运价都为都是假设的，不需要运输，故运价都为0 0，但是由但是由A A4 4运到运到B B6 6的运输无法发生，因两者皆为假设的运输无法发生，因两者皆为假设的，运价为无穷大，设为的，运价为无穷大，设为M M。此题属于产销不平衡问题此题属于产销不平衡问题 2021-11-20第第6262页习题页习题用伏格尔法求

50、解初始基可行解得：用伏格尔法求解初始基可行解得：B1B2B3B4B5B6产量产量A15050A2254530100A310605030150A42020销量销量2510560307030iujv数字格内填入相应价格，用位势法检验是否为最优解，得：数字格内填入相应价格，用位势法检验是否为最优解，得：B1B2B3B4B5B6uiA1150A220403025A3354025020A40-5vj-5152055-20用位势法检验是否为最优解，得：用位势法检验是否为最优解，得：B1B2B3B4B5B6uiA111=151513= 014= 1515=3516=200A2204023=-303025=0

51、26=-525A331=15354034=3025020A441= 1042=-1043=-1544=0046=M+25-5vj-5152055-20因检验数存在负数，故需用闭合回路法调整因检验数存在负数，故需用闭合回路法调整 B1B2B3B4B5B6产量产量A111=155013= 014= 1515=3516=2050A2254523=-303025=026=-5100A331=15106034=305030150A441= 1042=-1043=-1544=02046=M+2520销量销量2510560307030用闭合回路法调整得：用闭合回路法调整得：B1B2B3B4B5B6产量产量A

52、15050A225 6015100A3507030150A4515 20销量销量2510560307030用位势法检验得：用位势法检验得：B1B2B3B4B5B6uiA1（5）15(20)(5)(35)(20)0A220（10）1530(10)(5)15A3(5)35（20）(20)25020A4(10)0(15)0 (10)(M+35)-15vj5150155-20因检验数全为正，所以已得最优方案。因检验数全为正，所以已得最优方案。即即A A3 3差差30t30t没有得到满足，没有得到满足， B B2 2缺缺5t5t，B B4 4缺缺15t15t。7 7、已知某运输问题的单位运价及最优调运方

53、、已知某运输问题的单位运价及最优调运方案如表所示（括号中的数据代表运输数量），案如表所示（括号中的数据代表运输数量），由于产地由于产地A A2 2至销地至销地B B2 2的道路关闭，故最优调运的道路关闭，故最优调运方案将发生变化，试在原最优调运方案的基础方案将发生变化，试在原最优调运方案的基础上，寻找新的最优调运方案。上，寻找新的最优调运方案。表表4-504-50B1B2B3B4B5aiA110205（4） 9（5）109A2210（4）103064A31（3） 20（1）710（1）4（3）8bj35463解：由于解：由于A A2 2 到到B B2 2道路关闭，则其运价为道路关闭，则其运价为

54、M M，应，应令其出基，以实现最优调度。先将令其出基，以实现最优调度。先将M M反映进产反映进产销平衡表，然后用位势法作检验，有：销平衡表，然后用位势法作检验，有：iujvB1B2B3B4B5A1（10）（1）59(7)0A2（21-M）M (24-M) （40-M） (22-M)M-19 A3120（1）1041019593要令要令A2 B2出基，即令其运输量为出基，即令其运输量为0，找出负检验数最小的来，找出负检验数最小的来进行调整，得：进行调整，得：B1B2B3B4B5产量产量A1459A2314A35128销量销量35463iujv用位势法作检验，有：用位势法作检验，有：B1B2B3B

55、4B5A1（11）（1）59(7)0A22（M-22） (2)（18）63 A3（1）20（1）1041-119593检验数已全为非负，故已得最优调度方案。检验数已全为非负，故已得最优调度方案。8 8、已知某运输问题的单位运价及最优调运方已知某运输问题的单位运价及最优调运方案如表案如表4 4所示，试回答下述问题：所示，试回答下述问题：(1)(1)A A1 1到到B B2 2、A A3 3到到B B5 5、和、和A A4 4到到B B1 1的单位运价，的单位运价，分别在什么范围内变化时上表中给出的最分别在什么范围内变化时上表中给出的最优方案不变；优方案不变；(2)(2)若若A A1 1到到B B

56、2 2的单位运价由的单位运价由1 1变为变为3 3，最优方案，最优方案将发生怎样的变化；将发生怎样的变化；(3)(3)若若A A3 3到到B B5 5的单位运价由的单位运价由4 4变为变为2 2，最优方案，最优方案将发生怎样的变化；将发生怎样的变化；2021-11-20表表4-51B1B2B3B4B5B6aiA12（20）1（30）333550A242（20）2（20）44440A33（10）542（39）41（11） 60A44221（1）2（30）231bj305020403011解：（解：（1 1）设）设A A1 1 到到B B2 2的单位运价为的单位运价为c c1212，因，因A A1

57、 1 到到B B2 2是是基变量，它的运价变化会引起非基变量检验系数的基变量，它的运价变化会引起非基变量检验系数的变化，此时，只需对其再进行位势法分析即可。变化，此时，只需对其再进行位势法分析即可。|要令最优方案不变，则非基变量的检验数非负；要令最优方案不变，则非基变量的检验数非负；故有故有c12 00；3- 3- c12 0 0；4- 4- c12 00；2- 2- c12 0 0；2+ 2+ c1200；1+ 1+ c12 0 0解上述不等式得解上述不等式得0 0 c12 22。即。即A A1 到到B B2的单位的单位运价在运价在00，22内变化时，最有方案不变。内变化时，最有方案不变。i

58、ujvB1B2B3B4B5B6A12c12(3- c12)(2)(1)(5)0A2（ c12 ）22（20）(1+ c12)(2+ c12)2- c12A33（4- c12 ） （3- c12 ）2（1）11A4(c12)(2- c12)(1)1 2(2)02 c12c12120(1)| A A3 3 到到B B5 5的单位运价属于非基变量，它的变的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其化不会引起其它检验数变化，故只需保证其检验数非负即可。检验数非负即可。 先用位势法算出原方案的检验数：先用位势法算出原方案的检验数：B1B2B3B4B5B6uiA121(2)(2)(

59、1)(5)0A2（1）22（3）(1)(3)1A33（3） （2）2（1）11A4(2)(1)(1)1 2(2)0vj2 11120 设设A A3 3 到到B B5 5的单位运价为的单位运价为c c3535，则其检验数满足，则其检验数满足c c3535 - -（1+21+2） 0 0，即，即c c3535 3 3。也就是说。也就是说A A3 3 到到B B5 5的的单位运价大于等于单位运价大于等于3 3时，最有方案不变。时，最有方案不变。|A A4 4 到到B B1 1的单位运价属于非基变量，它的变化的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其检不会引起其它检验数变化，

60、故只需保证其检验数非负即可。验数非负即可。 设设A A4 4到到B B1 1的单位运价为的单位运价为c c4141，则其检验数，则其检验数满足满足c c4141 - -（0+20+2） 0 0，即，即c c3535 2。也就是说。也就是说A4到到B1的单位运价大于等于的单位运价大于等于2 2时，即时，即A4 到到B1的单的单位运价变化范围是位运价变化范围是2，+)最有方案不变。最有方案不变。先用位势法算出原方案的检验数：先用位势法算出原方案的检验数：B1B2B3B4B5B6uiA121(2)(2)(1)(5)0A2（1）22（3）(1)(3)1A33（3） （2）2（1）11A4(2)(1)(

61、1)1 2(2)0vj2 11120iujv把变化直接反映到表中可得下表：把变化直接反映到表中可得下表：B1B2B3B4B5B6A123(0)(2)(1)(5)0A2（3）22（20）(4)(5)-1A33（1） （0）2（1）11A4(3)(-1)(1)1 2(2)0233120(2)若若A1到到B2的单位运价由的单位运价由1变为变为3，最优方案将发生，最优方案将发生怎样的变化；怎样的变化；因存在检验数为负数，最优方案发生改变，用闭合回路法调整得：因存在检验数为负数，最优方案发生改变，用闭合回路法调整得：B1B2B3B4B5B6aiA1212950A2202040A39401160A4130

62、31bj305020403011表表4-51B1B2B3B4B5B6aiA12（20）3（30）50A22（20）2（20）40A33（10）2（39）1（11）60A41（1）2（30）31bj305020403011iujv重新计算检验数，得：重新计算检验数，得：B1B2B3B4B5B6A123(0)(2)(0)(5)0A2（3）22（4）(2)(5)-1A33（1） （0）2（0）11A4(3)2(0)（1） 2(3)-1233130非基变量检验数均为非负，故为最优方案。非基变量检验数均为非负，故为最优方案。iujv（3）把）把A3 到到B5的单位运价改为的单位运价改为2，然后求检验数得

63、：，然后求检验数得：B1B2B3B4B5B6A121(2)(2)(1)(5)0A2（1）22（3）(1)(3)1A33（3） （2）2（-1）11A4(2)(1)(1)1 2(2)02 11120B1B2B3B4B5B6aiA12（20）1（30）333550A242（20）2（20）44440A33（10）542（39）41（11）60A44221（1）2（30）231bj305020403011表表4-51由于存在负检验数，故最优方案发生变化，此时用闭合回路法调由于存在负检验数，故最优方案发生变化，此时用闭合回路法调整得：整得：B1B2B3B4B5B6aiA1203050A2202040A

64、3109301160A43131bj305020403011iujv重新计算检验数，得：重新计算检验数，得：B1B2B3B4B5B6A121(2)(2)(1)(5)0A2（1）22（2）(1)(3)1A33（3） （2）2（1）11A4(2)(1)(1)1 2(2)0211120检验数全为非负，故已得最优方案。检验数全为非负，故已得最优方案。B1B2B3B4B5B6产量产量A111=155013= 014= 1515=3516=2050A2254523=-303025=026=-5100A331=15106034=305030150A441= 1042=-1043=-1544=02046=M+2520销量销量2510560307030B1B2B3B4B5B6产量产量A111=155013= 014= 1515=3516=2050A225453025=026=-5100A331=1534=3030150A441= 1044=046=M+2520销量销量25105603070306515502043=-155155542=-1055070