数模3-TransportationProblem.ppt

1、Suppose there are three origins A1,A2,A3, and four destinations B1,B2,B3,B4, to transport a certain cmmodity，we know the amount of available supply and demand and the transporting cost, how shall we transport to minimize the total cost?,Chapter 3 Transportation Problem,1. Optimization model for tran

2、sportation problem The transportation problem which demand equals supply and its optimization model The transportation problem which demand equals supply optimization model,Aetna School of Management,S.J.T.U.,All Rights Reserved,Ren Jian Biao,2001,Session4 Transportation and Assignment Problems,运输与指

3、派问题, ,物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）,The Transportation Problem 运输问题,你怎么去分析这类问题呢？,产 地,销 地,产量bi,需求量ai,决策变量供应量Xij,单位运价Cij,第三章：运输问题（1）-产销平衡运输问题,Aetna School of Management,S.J.T.U.,All Rights Reserved,Ren Jian Biao,2001,Session4 Transportation and Assignm

4、ent Problems,运输与指派问题, ,P&T公司是一家由家族经营的小公司。它收购生 菜并在食品罐头厂中把它们加工成为罐头，然后 再把这些罐头食品分销到各地卖出去。豌豆罐头 在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒 冈州的尤基尼；明尼苏达州的艾尔贝李）加工， 然后用卡车把它们运送到美国西部的四个分销仓 库(加利福尼亚州的萨克拉门托；犹他州盐湖城 ；南达科他州赖皮特城；新墨西哥州澳尔巴古)。,Transportation Problem Example 运输问题举例,实际举例,这段时间公司成本正迅速增长而利润没有得到同样增长。 道格拉斯对配送经理说：豌豆罐头的运输成本，几年前是100，0

5、00美元，而上季度已涨到178，000美元。 配送经理：司机要价太高，我们正打算重新雇佣司机，成本会下降到165，000美元。 道格拉斯：可否从另外角度看问题。你是不是从我们三个罐头厂把豌豆罐头运到我们的四个仓库中？可以请管理科学小组生成运输计划。,书P189,公司目前的做法：,1。罐头厂贝林翰离仓库最远，所以把它的产品送到离它最近的一个仓库，也就是萨克拉门托仓库，若有剩余送到盐湖城仓库。2。因为澳尔巴古仓库离罐头厂最远，所以将离它最近的罐头厂（艾尔贝李罐头厂）的产品运到澳尔巴古仓库，如果还有剩余的化，若有剩余，运到赖皮特城仓库。3。用尤基尼罐头厂满足其它仓库的剩余需求。,书P191,罐头厂1

6、：贝林翰,罐头厂2：尤基尼,罐头厂3：艾尔贝.李,仓库3：赖皮特城,仓库2：盐湖城,仓库1：萨克拉门托,仓库4：澳尔巴古,书P189,表一：P&T公司的运输数据表,书P191,表二：P&T公司的运输计划,表三：P&T公司的单位卡车运输成本,因而：公司目前做法的运输成本：,总的运输成本= =75*464+5*352+65*416+55*69015*388+85*685=165，595（美元） 管理科学小组要做的是要做的是检查当前运输计划是否最优，研究用运输问题解的方案是否会更节约成本。建立该问题的运输问题模型：,最小化成本 =464x11+513x12+654x13+867x14+352x21+

7、416x22+690 x23 +791x24+995x31+682x32+388x33+685x34 约束条件 x11+x12+x13+x14 =75 x21+x22+x23+x24 =125 x31+x32+x33+x34 =100 x11 +x21 +x31 = 80 x12 +x22 +x32 = 65 x13 +x23 +x33 = 70 x14 +x24 +x34=85,表四：P&T公司的运输问题的最优解,计算机计划总运输成本,手工计划总的运输成本= =75*464+5*352+65*416+55*69015*388+85*685=165，595（美元） 计算机计划总运输成本 =20

8、*513+55*867+80*352+45*416+70*388+30*685 =152，535美元 比当前计划相比减少了13060美元。,1。人工规则的确很好的照顾了贝林翰和澳尔巴古的 利益，但它却使尤基尼和艾尔贝李的利益大大受损。 而后两个厂的产量都多于前者。 2。虽然人工规则所在行和列都选了最小值，但没有 选全局最小值，造成了局部最优，全局受损。,练习题,思路：首先考虑运费最少的对应的产地和销地,书P167,例1：求佳公司决定使用三个有生产余力的工厂进行 四种新产品的生产制造。每单位产品需要等量的工作， 所以工厂的有效生产能力以每天生产的任意种产品的 数量来衡量。表的最后一行给出了要求的

9、产品生产率 （每天的产品数量），以满足计划的销售量。每种产 品在不同工厂中的单位成本有差异。,重庆百货大楼股份有限公司物流优化配送系统,重庆百货大楼股份有限公司物流优化配送系统,指派问题(assignment problem),重庆移动公司基站维护外包问题的分析及对策,基站外包问题解析,城区,北碚,永川,涪陵,万州,黔江,Optimization model for assigment problem,01整数规划应用指派问题 (P128),第五章：0 -1整数规划,注意到： 1 从人来看，如果B不作日语，损失特别大6 2 从事来看，如果英语不分配给甲，损失特别大5,01整数规划应用指派问题 (P128) 原理：从人的角度思考.考虑人最适合的工作 从工作的角度思考.考虑工作最适合的人,各行都减去这一行的最小值，得到的0表示这个0所在的行对应的人最适合的工作是这个0所在的列对应的事,这一列有三个0，表示这一列的事有三个人适合作,行最小值,第五章：0 -1整数规划,指派问题第一步:各行元素该行行最小各列元素该列列最小 本题有n个独立的0元素则已得最优解,各列都减去这一列的最小值，得到的0表示这个0所在的列行对应的事最适合的人是这个0所在的行对应的人,甲 俄 乙 日 丙 英 丁 德,列最小值,有三个人适合英文 为什