运筹学-第四章-运输问题和指派问题.pptVIP

第四章运输问题和指派问题

运输问题提到运输问题，想到什么？服装专卖店的转运问题等快递业的运输问题实际生活中有哪些方面涉及运输问题

产销平衡和单位运价表销地单位运费产地运输问题的提出某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。运输的单位本钱供需平衡

运输问题的求解方法计算过程：1．寻找初始可行解；2．检查是否已到达最优。假设已是最优或无可行解，那么结束；3．进一步改善目前的解；寻找初始可行解的方法〔1〕西北角方法；〔2〕最小元素法。

求平衡运输问题初始解方法—西北角方法西北角方法24233311321974101085求初始解3113219741010856首先满足西北角上空格的需求

初始解求平衡运输问题初始解方法—西北角方法西北角方法其余为0。总运费=3*3+4*11+2*9+2*2+3*10+6*5=135〔元〕311321974101085

求平衡运输问题初始解方法—最小元素法求初始解最小元素法311321974101085311321974101085134633首先满足运费最小的空格

初始解求平衡运输问题初始解方法—最小元素法最小元素法其余为0。总运费=4*3+3*10+3*1+1*2+6*4+3*5=86〔元〕311321974101085

两种方法结果比较最小元素法西北角方法311321974101085311321974101085

西北角法得到初始方案：总运费=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〔元〕

最优解的检验——闭回路法要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量〔对应于运输表格中的空格〕的检验数，假设有某空格的检验数为负，那么说明将变为基变量将使运费减少，故当前这个解不是最优解；假设所有空格的检验数全非负，那么不管怎样变换解均不能使运输费用减少，即为最优解。

311321974101085闭回路法——以最小元素法得到的解为初始可行解1-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=10说明：该空格可以保持不变，即该运输路线不用安排运输

1-112432存在检验数0的空格，该解不是最优解311321974101085检验数0表示：例如〔A2,B4〕如果增加A2到B4的1单位产品，将会降低1单位的运费，所以，该解不是最优解。

解的改进〔1〕以为换入变量，找出它在运输表中的闭回路；〔2〕以空格为第一个奇数顶点，沿闭回路的顺〔或逆〕时针方向前进，对闭回路上的顶点一次编号；〔3〕在闭回路上的所有偶数顶点中，找出运输量最小的顶点〔格子〕，以该格中的变量为换出变量；〔4〕以为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案；〔5〕然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。

3+1+1-1-1124510311219741031085此时，总费用为：5*3+2*10+3*1+1*8+6*4+3*5=8586接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复……直至得到最优解总费用为85

运输问题的建模和Excel规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。单位运输本钱供给=需求

一般运输问题的根本原那么最小化所有运输费用之和供给=需求产品是离散计量的要求运输量是整数个单位产品线性约束先讨论产销平衡的运输问题总供给量=总需求量

运输问题的一般模式目标函数供给约束需求约束非负约束n表示物资的n个销地m表示物资的m个产地

问题分析决策变量目标函数约束条件：产量约