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

第四章运输问题和指派问题运输问题提到运输问题，想到什么？服装专卖店的转运问题等快递业的运输问题实际生活中有哪些方面涉及运输问题产销平衡和单位运价表销地单位运费产地B1B2B3B4产量A13113107A219284A3741059销量365620运输问题的提出某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。运输的单位成本供需平衡运输问题的求解方法计算过程：1．寻找初始可行解；2．检查是否已达到最优。若已是最优或无可行解，则结束；3．进一步改善目前的解；寻找初始可行解的方法（1）西北角方法；（2）最小元素法。求平衡运输问题初始解方法—西北角方法B1B2B3B4产量A17A24A39需求量365620西北角方法B1B2B3B4产量A17A24A39需求量36562024233311321974101085求初始解3113219741010856首先满足西北角上空格的需求初始解求平衡运输问题初始解方法—西北角方法西北角方法1112222333343,4,2,2,3,6xxxxxx其余为0。总运费=3*3+4*11+2*9+2*2+3*10+6*5=135（元）B1B2B3B4产量A1347A2224A3369需求量365620311321974101085求平衡运输问题初始解方法—最小元素法求初始解B1B2B3B4产量A17A24A39需求量365620最小元素法311321974101085B1B2B3B4产量A17A24A39需求量365620311321974101085134633首先满足运费最小的空格初始解求平衡运输问题初始解方法—最小元素法最小元素法1314212332344,3,3,1,6,3xxxxxx其余为0。总运费=4*3+3*10+3*1+1*2+6*4+3*5=86（元）B1B2B3B4产量A1437A2314A3639需求量365620311321974101085两种方法结果比较最小元素法西北角方法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（元）1112222333343,4,2,2,3,6xxxxxx1314212332344,3,3,1,6,3xxxxxx最优解的检验——闭回路法要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表格中的空格）的检验数，若有某空格的检验数为负，则说明将变为基变量将使运费减少，故当前这个解不是最优解；若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用减少，即为最优解。(,)ijABijx311321974101085闭回路法——以最小元素法得到的解为初始可行解B1B2B3B4产量A1437A2314A3639销量3656201-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=10说明：该空格可以保持不变，即该运输路线不用安排运输1-112432存在检验数0的空格，该解不是最优解B1B2B3B4产量A1437A2314A3639销量365620311321974101085检验数0表示：例如（A2,B4）如果增加A2到B4的1单位产品，将会降低1单位的运费，所以，该解不是最优解。解的改进（1）以为换入变量，找出它在运输表中的闭回路；（2）以空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点一次编号；（3）在闭回路上的所有偶数顶点中，找出运输量最小的顶点（格子），以该格中的变量为换出变量；（4）以为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案；（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。ijx(,)ijAB()minijLex()minijLex3B1B2B3B4产量A17A234A3639销量365620+1+1-1-1124510311219741031085此时，总费用为：5*3+2*10+3*1+1*8+6*4+3*5=8586接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复……直至得到最优解总费用为85B1B2B3B4产量A1527A2314A3639销量365620运输问题的建模和Excel规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。B1B2B3B4产量A13113107A219284A3741059销量365620单位运输成本供给=需求一般运输问题的基本原则最小化所有运输费用之和供给=需求产品是离散计量的要求运输量是整数个单位产品线性约束先讨论产销平衡的运输问题总供应量=总需求量运输问题的一般模式0..min11ijjmiijinjijijijxdxsxtsxc目标函数供给约束需求约束非负约束n表示物资的n个销地m表示物资的m个产地问题分析决策变量目标函数约束条件：产量约束、销量约束、非负B1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349需求量365620决策变量非负约束需求约束供给约束根据一般模式求解上述运输问题得到：11121334111213142122232431323334112131122232132333142434min311357493..6560(1,2,3;1,2,3,4)ijzxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxij注意：由于供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解，所以无需设置有关整数解的约束条件实际中，产销往往是不平衡的。可有两种情况：总产量小于总销量（供不应求）总产量大于总销量（供大于求）产销不平衡的运输问题总产量小于总销量（供不应求）1111min(1,2...,)()..(1,2...,)()0(1,2...,;1,2...,)mnijijijnijijmijjiijzcxxaimstxbjnximjn产量约束销量约束总产量大于总销量（供大于求）1111min(1,2...,)()..(1,2...,)()0(1,2...,;1,2...,)mnijijijnijijmijjiijzcxxaimstxbjnximjn产量约束销量约束例4.2自来水输送问题某市有甲乙丙丁四个居民区，自来水有A、B、C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30、70、10、10千吨，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库每天向各居民区供水所需付出的引水管理费用不同（见表格，其中水库C与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各居民区用户按照统一标准900元/千吨收费。此外，四个居民区都向公司申请了额外用水量，分别为每天50、70、20、40千吨。甲乙丙丁A160130220170B140130190150C190200230问：（1）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少问题分析决策变量目标函数约束条件甲乙丙丁最大供水量AxA1xA2xA3xA4100BxB1xB2xB3xB4120CxC1xC2xC3----100基本用水量30701010额外用水量50702040最大用水量801403050使用Excel求解送水问题1供不应求的问题使用Excel求解送水问题2最大供水量增倍供大于求的问题4.3运输问题的变形总供应量大于总需求总供应量小于总需求一个目的地同时存在着最小需求量和最大需求量，于是所有在这两个数值之间的数量都是可以接受的在运输中不能使用特定的出发地——目的地组合目标是使与运输量有关的总利润最大而不是使总成本最小例4.3某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040问题分析供大于求的问题决策变量目标函数约束条件单位成本生产能力产品1产品2产品3产品4工厂1x11x12x13x1475工厂2x21x22x23=0x2475工厂3x31x32x33x3445需求量20303040使用Excel求解例4.4需求量存在最小需求量和最大需求量的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客很有可能有大量订购。顾客1是公司最好的顾客，所以他的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表格）。问应向每个顾客供应多少产品，才能使公司的总利润最大？单位利润（元）产量顾客1顾客2顾客3顾客4工厂1554246538000工厂2371832485000工厂3295951357000最少供应量7000300020000要求订购量7000900060008000例4.4问题分析该问题要求满足不同顾客的需求（订购量），解决办法是：实际供应量≥最少供应量实际供应量≤要求订购量但条件是：最少供应量（7000+3000+2000+0=12000）≤总产量（8000+5000+7000=20000）≤要求订购总量（7000+9000+6000+8000=30000）问题分析决策变量目标函数约束条件单位利润（元）产量顾客1顾客2顾客3顾客4工厂1x11x12x13x148000工厂2x21x22x23x245000工厂3x31x32x33x347000最少供应量7000300020000要求订购量7