MBA课程_管理运筹学课件_第四章_线性规划.ppt

步骤如下： 1、在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。 2、从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素。比较该元素所在的行和列的产量，取它们最小者填入产销平衡表相应的位置。同时在单位运价表中划去一行或一列。 3、对上述未划去的元素再分别计算出各行、各列的差额。重复第一、二步的工作，直到给出初始解为止。 管理运筹学 第四章 线性规划 运输问题 管理运筹学 第四章 线性规划 运输问题 销地 产地 B1 B2 B3 B4 行差额 A1 3 11 3 10 0 A2 1 9 2 8 1 A3 7 4 10 5 1 列差额 2 5 1 3 销地 产地 B1 B2 B3 B4 产量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 注意事项： 每次填完数，都只划去一行或一列，只有最后一个例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0。 管理运筹学 第四章 线性规划 运输问题 5、最优运输方案的判定 (1)闭回路法 (2)位势法 管理运筹学 第四章 线性规划 运输问题 (1)闭回路法 在给出调运方案的计算表上，从每一空格出发，找一条闭回路。它是以空格为起点，用水平线或垂直线向前划，每碰到一数字格就转90度后继续前进。直到回到起始空格处为止。 管理运筹学 第四章 线性规划 运输问题 闭回路计算检验数的经济解释为： 在已给出初始解的中，如最小元素法，可以从任一空格出发，如从 (A1 , B1) 出发，若 让 A1 的产品调 1 吨给B1 ，为了保持产销平衡，就要依次 作调整：在 (A1 , B3) 处减少 1 吨， (A2 , B3) 处增加 1 吨，(A2 , B1) 处减少 1 吨，即构成了以(A1 , B1) 空格为起点，其它为有数字的格的闭回路。如下表中直线所示，在这闭回路中，各顶点所在格的右上角的数字是单位运价。 管理运筹学 第四章 线性规划 运输问题 可见这一调整方案使运费增加了：(+1)?3 + (-1) ?3 + (+1)?2 + (-1) ?1 = 1 (元) 这表明若这样调整运输方式将增加运费。将“1”这个数填入(A1 , B1) 格，这就是检验数。按以上所述，就可以找出所有空格的检验数，如下表。 管理运筹学 第四章 线性规划 运输问题 空 格 闭 回 路 检验数 (A1 , B1) (1,1)? (1,3)? (2,3)? (2,1)?(1,1) 1 (A1 , B2) (1,2)? (1,4)? (3,4)? (3,2)?(1,2) 2 (A2 , B2) (2,2)? (2,3)? (1,3)? (1,4)? (3,4)? (3,2)? (2,2) 1 (A2 , B4) (2,4)? (2,3)? (1,3)? (1,4)?(2,4) -1 (A3 , B1) (3,1)? (3,4)? (1,4)? (1,3)? (2,3)? (2,1)? (3,1) 10 (A3 , B3) (3,3)? (3,4)? (1,4)? (1,3)? (3,3) 12 (2)位势法 用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点很多时，这种计算很费时。下面介绍一种较为简便的方法——位势法。 所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由选中变量xij的检验数 所决定的，则非选中变量xij的检验数就可以用公式 求出。 管理运筹学 第四章 线性规划 运输问题 管理运筹学 第四章 线性规划 运输问题 销地 产地 B1 B2 B3 B4 行位势 u