运输成本管理.ppt

甲 乙 丙 丁 产量（ai） A 5 7 B 3 4 C 3 9 销量（bj） 3 6 5 6 6 甲 乙 丙 丁 两最小元素之差 A 3 11 3 10 B 9 2 8 C 7 4 10 5 两最小元素之差 2 1 甲 乙 丙 丁 产量（ai） A 5 7 B 3 1 4 C 3 9 销量（bj） 3 6 5 6 6 甲 乙 丙 丁 产量（ai） A 5 2 7 B 3 1 4 C 3 9 销量（bj） 3 6 5 6 6 基可行解的最优性检验 初始方案是否是最优方案，需要一定的方法来判定，对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。 第三节 降低运输成本的方法及措施 闭合回路 ： 是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个空格存在唯一的闭回路。 6 5 6 3 销量（bj） 9 3 6 C 4 1 3 B 7 3 4 A 产量（ai） 丁 丙 乙 甲 （+3） （-3） （+2） （-1） 甲 乙 丙 丁 产量（ai） A 4 3 7 B 3 1 4 C 6 3 9 销量（bj） 3 6 5 6 6 5 6 3 销量（bj） 9 3（+5） 6（-4） C 4 1 3 B 7 3（-10） 4 （+11） ?11 = 1 A 产量（ai） 丁 丙 乙 甲 6 5 6 3 销量（bj） 9 3（+5） 6（-4） C 4 1（-2） （+9） 3 B 7 3（-10） 4（+3） ?12 = 2 ?11 = 1 A 产量（ai） 丁 丙 乙 甲 6 5 6 3 销量（bj） 9 3 6 C 4 （+8） 1（-2） ?22 = 1 3 B 7 3（-10） 4（+3） ?12 = 2 ?11 = 1 A 产量（ai） 丁 丙 乙 甲 6 5 6 3 销量（bj） 9 3（-5） （+10） 6 C 4 ?24 = -1 1 ?22 = 1 3 B 7 3（+10） 4（-3） ?12 = 2 ?11 = 1 A 产量（ai） 丁 丙 乙 甲 6 5 6 3 销量（bj） 9 3（-5） ?33 = 12 6 （+7） C 4 ?24 = -1 1（+2） ?22 = 1 3（-1） B 7 3（+10） 4（-3） ?12 = 2 ?11 = 1 A 产量（ai） 丁 丙 乙 甲 甲 乙 丙 丁 产量（ai） A ?11 = 1 ?12 = 2 4 3 7 B 3 ?22 = 1 1 ?24 = -1 4 C ?31 = 10 6 ?33 = 12 3 9 销量（bj） 3 6 5 6 第三节 降低运输成本的方法及措施 如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方案。在表中， ?24 = -1,说明方案需要进一步改进。 位势法 这一表达式完全可以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表所示），由于基变量的运价等于其所对应的行位势与列位势之和，即： Cij - ( ui + vj ) = 0 在例1 的由最小元素法得到的初始解中x23 , x34 , x21 , x32 , x13 , x14 是基变量。xa为人工变量, 这时对应的检验数是: 基变量 检验数 Xa ca - u1 = 0 ∵ ca = 0 ∴u1 = 0 x23 c23 - ( u2 + v3 ) = 0 即 2 - ( u2 + v3 ) = 0 X34 c34 - ( u3 + v4 ) = 0 5 - ( u3 + v4 ) = 0 x21 c21 - ( u2 + v1 ) = 0 1 - ( u2 + v1 ) = 0 x32 c32 - ( u3 + v2 ) = 0 4 - ( u3 + v2 ) = 0 x13 c13 - ( u