《运输问题 表上作业法》由会员分享，可在线阅读，更多相关《运输问题 表上作业法（85页珍藏版）》请在金锄头文库上搜索。
1、4.2 表上作业法表上作业法表上作业法与单纯形法的关系表上作业法的基本步骤确定初始基可行解最小元素法的基本步骤伏格尔法三、三、 运输问题的求解运输问题的求解n运输问题的求解采用表上作业法，即用列 表的方法求解线性规划问题中的运输模型的 计算方法，实质上是单纯形法。n表上作业法是一种特定形式的单纯形法， 它与单纯形法有着完全相同的解题步骤，所 不同的只是完成各步采用的具体形式。1.表上作 业法2.表上作业法与单纯形法的关系|表上作业法中的最小元素法和伏格尔法实质 上是在求单纯形表中的初始基可行解；|表上作业法中的“位势法”实质上是在求单 纯形表中的检验数；|调运方案表中数字格的数实质上就是单纯形
2、 法中基变量的值；|调运方案表上的“闭回路法”实质上是在做 单纯形表上的换基迭代。|（1）找出初始基可行解： m+n-1个数字格（基变量 ）；|（2）求各非基变量（空格）的检验数。,那么选取xij为入基变量； |（3）确定入基变量，若 3.表上作业法的基本步骤| （4）确定出基变量，找出入基变量的闭合回路；| （5）在表上用闭合回路法调整运输方案；| （6）重复2、3、4、5步骤，直到得到最优解。4、确定初始基可行解 |与一般的线性规划不同，产销平衡的运输问 题一定具有可行解（同时也一定存在最优解） 。|最小元素法（the least cost rule）和伏格尔法 （Vogels appro
3、ximation method）。 z最小元素法的基本思想是就近供应，即从单位 运价表中最小的运价开始确定产销关系，依此 类推，一直到给出基本方案为止.最小元素法|找出最小运价，确定供求关系，最大量的供应 ； |划掉已满足要求的行或 (和) 列，如果需要同 时划去行和列，必须要在该行或列的任意位置 填个“0”； |在剩余的运价表中重复1、2两步，直到得到初 始基可行解。5、最小元素法的基本步骤|最小元素法最小元素法的基本思想是就近供应，即 从单位运价表中最小的运价开始确定产销 关系，依此类推，一直到给出基本方案为 止。表4-1甲乙丙丁产产量（ai ） A3113107 B19284 C7410
4、59销销量（bj ）3656最小元素法的应用（以引例4-1为例）第一步：从表第一步：从表4-14-1中找出最小运价中找出最小运价“1”1”， 最小运最小运 价所确定的供应关系为（价所确定的供应关系为（B B，甲），在（，甲），在（B B，甲）的，甲）的 交叉格处填上交叉格处填上“3”3”，形成表，形成表4-24-2；将运价表的甲列；将运价表的甲列 运价划去得表运价划去得表4-3.4-3.甲乙丙丁产产量（ai ） A7 B4 C9销销量（bj ）3656甲乙丙丁产产量（ai ） A3113107 B19284 C741059销销量（bj ）3656表4-2表4-33第二步：在表第二步：在表4-3
5、4-3的未被划掉的元素中再找出最小的未被划掉的元素中再找出最小 运价运价“2”2”，最小运价所确定的供应关系为（，最小运价所确定的供应关系为（B B，丙，丙 ），即将），即将B B余下的余下的1 1个单位产品供应给丙，表个单位产品供应给丙，表4-24-2转换转换 成表成表4-44-4。划去。划去B B行的运价，划去行的运价，划去B B行表明行表明B B所生产的所生产的 产品已全部运出，表产品已全部运出，表4-34-3转换成表转换成表4-54-5。甲乙丙丁产产量（ai ） A3113107 B19284 C741059销销量（bj ）3656表4-3甲乙丙丁产产量（ai ） A7 B4 C9销销
6、量（bj ）3656甲乙丙丁产产量（ai ） A3113107 B19284 C741059销销量（bj ）3656表4-4表4-531甲乙丙丁产产量（ai ） A3113107 B19284 C741059销销量（bj ）3656表4-5第三步：在表4-5中再找出最小运价“3”， 这样一步步地进行下去，直到单位运价表上的 所有元素均被划去为止。 表4-7 甲乙丙丁产产量（ai ） A7 B4 C9 销销量（bj ）3656表4-6 甲乙丙丁产产量（ai ） A311107 B1984 C7109销销量（bj ）36563213446533|最后在产销平衡表上得到一个调运方案，见 表4-6。这
7、一方案的总运费为86个单位。|最小元素法各步在运价表中划掉的行或列是需求得 到满足的列或产品被调空的行。一般情况下，每填入 一个数相应地划掉一行或一列，这样最终将得到一个 具有m+n-1个数字格（基变量）的初始基可行解。 在供需关系格（在供需关系格（i i，j j ）处填入一数字，刚好）处填入一数字，刚好 使第使第 i i个产地的产品调空，同时也使第个产地的产品调空，同时也使第j j个销地的需个销地的需 求得到满足。填入一数字同时划去了一行和一列，求得到满足。填入一数字同时划去了一行和一列， 那么最终必然无法得到一个具有那么最终必然无法得到一个具有m+n-1m+n-1个数字格（基个数字格（基
8、变量）的初始基可行解。变量）的初始基可行解。6.应注意的问题为了使在产销平衡表上有为了使在产销平衡表上有m+n-1m+n-1个数字格，这时个数字格，这时 需要在第行或第列此前未被划掉的任意一个空格上需要在第行或第列此前未被划掉的任意一个空格上 填一个填一个“0”0”。填。填“0”0”格虽然所反映的运输量同空格虽然所反映的运输量同空 格没有什么不同；但它所对应的变量却是基变量，格没有什么不同；但它所对应的变量却是基变量， 而空格所对应的变量是非基变量。而空格所对应的变量是非基变量。表4-7 甲乙丙丁产产量（ai ） A3113104B19284 C7410512 销销量（bj ）3656 表4-
9、8 甲乙丙丁产产量（ai ） A4 B4 C12 销销量（bj ）36563147. 举例 将例4-1的各工厂的产量做适当调整（调 整结果见表4-7），就会出现上述特殊情况。 066每次从当前运价表上，计算各行各列每次从当前运价表上，计算各行各列 中两个最小运价之差值（行差值中两个最小运价之差值（行差值h hi i，列差列差 值值k kj j），），优先取最大差值的行或列中最小优先取最大差值的行或列中最小 的格来确定运输关系，直到求出初始方案的格来确定运输关系，直到求出初始方案 。8.伏格法尔法伏格尔法的基本步骤：8.伏格尔法1.计算每行、列两个最小运价的差； 2.找出最大差所在的行或列； 3
10、.找出该行或列的最小运价，确定供求关系，最大量 的供应 ； 4.划掉已满足要求的行或 (和) 列，如果需要同时划 去行和列，必须要在该行或列的任意位置填个 “0”； 5.在剩余的运价表中重复14步，直到得到初始基可 行解。表4-1甲乙丙丁产产量（ai ） A3113107 B19284 C741059销销量（bj ）3656表4-12甲乙丙丁两最小元素之差 A311310 B1928 C7105两最小元素之差 130 1 1 254表4-13 甲乙丙丁产产量（ai） A7 B4 C9 销销量（bj ）3656表4-14甲乙丙丁两最小元素之差 A311310 B1928 C7410两最小元素之差
11、562130 1 25表4-15 甲乙丙丁产产量（ai ） A7 B4 C9 销销量（bj ）365663表4-16 甲乙丙丁两最小元素之差 A311310 B928 C74105 两最小元素之差2120 11表4-17 甲乙丙丁产产量（ai ） A7 B4 C9 销销量（bj ）3656633表4- 18甲乙丙丁两最小元素之差 A31110 B1928 C74105 两最小元素之差12673表4-19甲乙丙丁产产量（ai ） A7 B4 C9 销销量（bj ）3656表4-20甲乙丙丁两最小元素之差 A311310 B192C74105 两最小元素之差63352812|总运费为85|由以上可
12、见，伏格尔法同最小元素法除在确 定供求关系的原则上不同外，其余步骤是完全 相同的。伏格尔法给出的初始解比最小元素法 给出的初始解一般来讲会更接近于最优解。 表4-23 甲乙丙丁产产量（ai ） A7 B4 C9 销销量（bj ）36566335 124.2.2 基可行解的最优性 检验n对初始基可行解的最优性检验有闭合回路法 和位势法两种基本方法。闭合回路法具体、直 接，并为方案调整指明了方向；而位势法具有 批处理的功能，提高了计算效率。 |所谓闭合回路是在已给出的调运方案的运输 表上从一个代表非基变量的空格出发，沿水平 或垂直方向前进，只有遇到代表基变量的填入 数字的格才能向左或右转90度（当
13、然也可以不 改变方向）继续前进，这样继续下去，直至回 到出发的那个空格，由此形成的封闭折线叫做 闭合回路。一个空格存在唯一的闭回路。|所谓闭合回路法，就是对于代表非基变量的 空格（其调运量为零），把它的调运量调整为 1，由于产销平衡的要求,我们必须对这个空格 的闭回路的顶点的调运量加上或减少1。最后 我们计算出由这些变化给整个运输方案的总运 输费带来的变化。如果所有代表非基变量的空 格的检验数也即非基变量的检验数都大于等于 零，则已求得最优解，否则继续迭代找出最优 解。1.闭合回路n下面就以表4-6中给出的初始基可行解 （最小元素法所给出的初始方案）为例， 讨论闭合回路法。 表4-24甲乙丙丁
14、产产量（ai） A 437 B 3 14 C639 销销量（bj ）3656（+3）（-3）（+2）（-1）|从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对 于空格（A，甲）在初始方案的基础上将A生产的产品调运一个单 位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一个单 位、（B，丙）处增加一个单位、（B，甲）处减少一个单位；即 要寻找一条除空格（A，甲）之外其余顶点均为有数字格（基变量 ）组成的闭合回路。表4-24中用虚线画出了这条闭合回路。闭合 回路顶点所在格括号内的数字是相应的单位运价，单位运价前的 “+”、“-”号表示运量的调整方向。|对应这样的方案调整，运费会有什么变
15、化呢？可以 看出（A，甲）处增加一个单位，运费增加3个单位； 在（A，丙）处减少一个单位，运费减少3个单位；在 （B，丙）处增加一个单位，运费增加2个单位；在（ B，甲）处减少一个单位，运费减少1个单位。增减相 抵后，总的运费增加了1个单位。由检验数的经济含 义可以知道，（A，甲）处单位运量调整所引起的运 费增量就是（A，甲）的检验数，即11=1。 表4-24 甲乙丙丁产产量（ai） A 437 B 3 14 C639 销销量（bj ）3656（+3）（-3）（+2）（-1）|仿照此步骤可以计算初始方案中所有空 格的检验数，表4-25表4-30展示了各检 验数的计算过程，表4-30给出了最终结
16、果 。可以证明，对初始方案中的每一个空格 来说“闭合回路存在且唯一”。表4-25 甲乙丙丁产产量（ai） A11 = 1（+11）43（-10）7 B314 C6（-4）3（+5）9 销销量（bj ）3656表4-26甲乙丙丁产量（ai）A11 = 112 = 24（+3）3（-10）7 B3（+9）1（-2）4 C6（-4）3（+5）9 销量（bj ）3656表4-27 甲乙丙丁产产量（ai） A11 = 112 = 24（+3）3（-10）7 B322 = 11（-2）（+8）4C639 销销量（bj ）3656表4-28 甲乙丙丁产产量（ai ） A11 = 112 = 24（-3）3（+10）7 B322 = 1124 = -14 C6（+10）3（-5）9 销销量（bj ）3656表4-29 甲乙丙丁产产量（ai ） A11 = 112 = 24（-3）3（+10）7 B3（-1）22 = 11（+2）24 = -14 C（+7）633 = 123（-5）9 销销量（bj ）3656表4-
