表上作业法--运输问题课件.ppt

《表上作业法--运输问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输问题的表上作业法例1某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表3中，问如何调运才能使总运费最小？销地产地产量4124111621039108511622销量814121448表3该运输问题的数学模型为：可以证明：约束矩阵的秩为r(A)=6.从而基变量的个数为6.可以证明：约束矩阵的秩r(A)=m+n-1.基变量的个数为m+n-1.对于m个产地、n个销地产销平衡的运输问题，销地产地产量4124

2、111621039108511622销量814121448解一销地产地产量4124111621039108511622销量814121448解二表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。计算过程（假设产销平衡）：1.找出初始基本可行解。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调

3、运量的值即为基变量的值。2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。4.重复2、3直到得到最优解。下面介绍三种常用的方法。1.最小元素法思想：优先满足运价（或运距）最小的运输业务。一。给出运输问题的初始可行解（初始调运方案）销地产地产量4124111610398511622销量14121448表3①销地产地产量412411162109108511

4、622销量8141448表3①②销地产地产量412112109108511622销量814121448表3①②③销地产地产量4121182109108116销量8121448表3①②③④销地产地产量412118210910811销量81248表3①③④⑤②销地产地产量4128210910811销量81248表3①③④⑤⑥⑥②此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒉西北角法西北角

5、法是优先满足运输表中西北角（左上角）上空格的运输需求。销地产地产量41241121039108511622销量14121448表3销地产地产量41241121039108511622销量14121448表3①销地产地产量41241121039108511622销量121448表3①销地产地产量41241121039108511622销量14121448表3①②销地产地产量412411210398511622销量14121448表3①②销地产地产量412411210398511622销量14121448表3

6、①②③销地产地产量412411210398511622销量141448表3①②③销地产地产量412411210398511622销量14121448表3①②③④销地产地产量4124112103985116销量14121448表3①③②④销地产地产量4124112103985116销量14121448表3①③②④⑤销地产地产量4124112103985116销量141248表3①③②④⑤销地产地产量4124112103985116销量14121448表3①③②④⑤⑥⑥此时得到一个初始调运方案（初始可行解）：

7、其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。⒊沃格尔（Vogel)法从上面两例看，最小元素法比较合理。但从下表看10151555沃格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行

8、（或该列）次小的方格中。销地产地产量4124111621039108511622销量81412648表3销地产地产量行罚数1234124111602103910181161销量8121448列罚数1251323销地产地产量行罚数123412411160021039101185112212销量8141248列罚数1251322133销地产地产量行罚数12341241116000103911185112212销量141248列罚数