运筹学-第四章-运输问题和指派问题.培训讲学.ppt

《运筹学-第四章-运输问题和指派问题.培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学-第四章-运输问题和指派问题.产销平衡和单位运价表销地单位运费产地B1B2B3B4产量A13113107A219284A3741059销量365620运输问题的提出某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。运输的单位成本供需平衡运输问题的求解方法计算过程：1．寻找初始可行解；2．检查是否已达到最优。若已是最优或无可行解，则结束；3．进一步改善目前的解；寻找

2、初始可行解的方法（1）西北角方法；（2）最小元素法。求平衡运输问题初始解方法—西北角方法B1B2B3B4产量A17A24A39需求量365620西北角方法B1B2B3B4产量A17A24A39需求量36562024233311321974101085求初始解3113219741010856首先满足西北角上空格的需求初始解求平衡运输问题初始解方法—西北角方法西北角方法其余为0。总运费=3*3+4*11+2*9+2*2+3*10+6*5=135（元）B1B2B3B4产量A1347A2224A3369需求量3656203

3、11321974101085求平衡运输问题初始解方法—最小元素法求初始解B1B2B3B4产量A17A24A39需求量365620最小元素法311321974101085B1B2B3B4产量A17A24A39需求量365620311321974101085134633首先满足运费最小的空格初始解求平衡运输问题初始解方法—最小元素法最小元素法其余为0。总运费=4*3+3*10+3*1+1*2+6*4+3*5=86（元）B1B2B3B4产量A1437A2314A3639需求量365620311321974101085两种

4、方法结果比较最小元素法西北角方法B1B2B3B4产量A1347A2224A3369需求量365620311321974101085B1B2B3B4产量A1437A2314A3639需求量365620311321974101085西北角法得到初始方案：总运费=3*3+4*11+2*9+2*2+3*10+6*5=135（元）最小元素法得到初始方案：总运费=4*3+3*10+3*1+1*2+6*4+3*5=86（元）最优解的检验——闭回路法要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对

5、应于运输表格中的空格）的检验数，若有某空格的检验数为负，则说明将变为基变量将使运费减少，故当前这个解不是最优解；若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用减少，即为最优解。311321974101085闭回路法——以最小元素法得到的解为初始可行解B1B2B3B4产量A1437A2314A3639销量3656201-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=1>0说明：该空格可以保持不变，即该运输路线不用安排运输1-112432存在检验数<0的空格，该解不是最优解B1B2B3B4产

6、量A1437A2314A3639销量365620311321974101085检验数<0表示：例如（A2,B4）如果增加A2到B4的1单位产品，将会降低1单位的运费，所以，该解不是最优解。解的改进（1）以为换入变量，找出它在运输表中的闭回路；（2）以空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点一次编号；（3）在闭回路上的所有偶数顶点中，找出运输量最小的顶点（格子），以该格中的变量为换出变量；（4）以为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这

7、一数值，从而得出一新的运输方案；（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。3B1B2B3B4产量A17A234A3639销量365620+1+1-1-1124510311219741031085此时，总费用为：5*3+2*10+3*1+1*8+6*4+3*5=85<86接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复……直至得到最优解总费用为85B1B2B3B4产量A1527A2314A3639销量365620运输问题的建模和Excel

8、规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。B1B2B3B4产量A13113107A219284A3741059销量365620单位运输成本供给=需求一般运输问题的基本原则最小化所有运输费用之和供给=