资源描述
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 Problem1.Optimization model for transportation problemThe transportation problem which demand equals supply and its optimization modelnThe transportation problem which demand equals supplynoptimization modelAetna School of Management,S.J.T.U.All Rights Reserved,Ren Jian Biao,2019Session4TransportationandAssignmentProblems运运输输与指派与指派问题问题renjbonline.shrenjb.home.物流中的一个普遍物流中的一个普遍问题问题是如何以尽可能小的成本把是如何以尽可能小的成本把货货物从一系列起始地（物从一系列起始地（sources）（如工厂、）（如工厂、仓库仓库）运运输输到一系列到一系列终终点地（点地（destinations）（如）（如仓库仓库、顾顾客）客）The Transportation Problem 运运输问题输问题你怎么去分析你怎么去分析这类问题这类问题呢？呢？想想看！想想看！产产地地销销地地产量产量bi需求量需求量ai 决策变量决策变量供应量供应量Xij单位运价单位运价Cij第三章：运输问题（第三章：运输问题（1）-产销平衡运输问题产销平衡运输问题Aetna School of Management,S.J.T.U.All Rights Reserved,Ren Jian Biao,2019Session4TransportationandAssignmentProblems运运输输与指派与指派问题问题renjbonline.shrenjb.home.P&T公司是一家由家族公司是一家由家族经营经营的小公司。它收的小公司。它收购购生生 菜并在食品罐菜并在食品罐头头厂中把它厂中把它们们加工成加工成为为罐罐头头，然后，然后 再把再把这这些罐些罐头头食品分食品分销销到各地到各地卖卖出去。豌豆罐出去。豌豆罐头头 在三个食品罐在三个食品罐头头厂（靠近厂（靠近华华盛盛顿顿的的贝贝林翰；俄勒林翰；俄勒 冈冈州的尤基尼；明尼州的尤基尼；明尼苏苏达州的艾达州的艾尔尔贝贝李）加工，李）加工，然后用卡然后用卡车车把它把它们们运送到美国西部的四个分运送到美国西部的四个分销仓销仓 库库(加利福尼加利福尼亚亚州的州的萨萨克拉克拉门门托；犹他州托；犹他州盐盐湖城湖城；南达科他州；南达科他州赖赖皮特城；新墨西哥州澳皮特城；新墨西哥州澳尔尔巴古巴古)。Transportation Problem Example 运运输问题举输问题举例例实际举实际举例例n这段时间公司成本正迅速增长而利润没有得这段时间公司成本正迅速增长而利润没有得到同样增长。到同样增长。n道格拉斯对配送经理说：豌豆罐头的运输成道格拉斯对配送经理说：豌豆罐头的运输成本，几年前是本，几年前是100，000美元，而上季度已涨美元，而上季度已涨到到178，000美元。美元。n配送经理：司机要价太高，我们正打算重新配送经理：司机要价太高，我们正打算重新雇佣司机，成本会下降到雇佣司机，成本会下降到165，000美元。美元。n道格拉斯：可否从另外角度看问题。你是不道格拉斯：可否从另外角度看问题。你是不是从我们三个罐头厂把豌豆罐头运到我们的是从我们三个罐头厂把豌豆罐头运到我们的四个仓库中？可以请管理科学小组生成运输四个仓库中？可以请管理科学小组生成运输计划。计划。书书P189公司目前的做法公司目前的做法：1。罐头厂贝林翰离仓库最远，所以把它的。罐头厂贝林翰离仓库最远，所以把它的产品送到离它最近的一个仓库，也就是萨产品送到离它最近的一个仓库，也就是萨克拉门托仓库，若有剩余送到盐湖城仓库。克拉门托仓库，若有剩余送到盐湖城仓库。2。因为澳尔巴古仓库离罐头厂最远，所以。因为澳尔巴古仓库离罐头厂最远，所以将离它最近的罐头厂（艾尔贝将离它最近的罐头厂（艾尔贝李罐头厂）李罐头厂）的产品运到澳尔巴古仓库，如果还有剩余的产品运到澳尔巴古仓库，如果还有剩余的化，若有剩余，运到赖皮特城仓库。的化，若有剩余，运到赖皮特城仓库。3。用尤基尼罐头厂满足其它仓库的剩余需求。用尤基尼罐头厂满足其它仓库的剩余需求。书书P191罐头厂1：贝林翰罐头厂2：尤基尼罐 头 厂 3：艾尔贝.李仓库3：赖皮特城仓库2：盐湖城仓库1：萨克拉门托仓库4：澳尔巴古书书P189表一：P&T公司的运输数据表罐头厂产量仓库仓库分配量分配量贝林翰75萨克拉门托萨克拉门托80尤基尼125盐湖城盐湖城65艾 尔 贝 李100赖皮特城赖皮特城70澳尔巴古澳尔巴古85合计300合计合计300书书P191表二：P&T公司的运输计划 至从 仓库 萨克拉门托盐湖城 赖皮特城澳尔巴古罐头厂 贝林翰750尤基尼56555艾 尔 贝 李1585表三：表三：P&TP&T公司的单位卡车运输成本公司的单位卡车运输成本至从仓库萨克拉门托盐湖城 赖皮特城澳尔巴古罐头厂贝林翰464513654867尤基尼352416690791艾 尔 贝 李995682388685因而：公司目前做法的运输成本：公司目前做法的运输成本：总的运输成本总的运输成本=75*464+5*352+65*416+55*69015*388+85*685=165，595（美元）（美元）管理科学小组要做的是要做的是检查当前运输管理科学小组要做的是要做的是检查当前运输计划是否最优，研究用运输问题解的方案是否计划是否最优，研究用运输问题解的方案是否会更节约成本。建立该问题的运输问题模型：会更节约成本。建立该问题的运输问题模型：最小化最小化成本成本=464x11+513x12+654x13+867x14+352x21+416x22+690 x23+791x24+995x31+682x32+388x33+685x34约束条件约束条件x11+x12+x13+x14=75x21+x22+x23+x24=125x31+x32+x33+x34=100 x11+x21+x31=80 x12+x22+x32=65x13+x23+x33=70 x14+x24+x34=85表四：表四：P&T公司的运输问题的最优解公司的运输问题的最优解至至从从仓库仓库萨萨克克拉拉门托门托盐湖城盐湖城 赖赖皮皮特特城城澳澳尔尔巴巴古古罐罐头头厂厂贝林翰贝林翰020055尤基尼尤基尼804500艾艾 尔尔 贝贝 李李007030计算机计划总运输成本手工计划总的运输成本手工计划总的运输成本=75*464+5*352+65*416+55*69015*388+85*685=165，595（美元）（美元）计算机计划总运输成本计算机计划总运输成本=20*513+55*867+80*352+45*416+70*388+30*685=152，535美元美元比当前计划相比减少了比当前计划相比减少了13060美元。美元。萨克拉门萨克拉门盐湖城盐湖城赖皮特城赖皮特城澳尔巴古澳尔巴古罐罐头头厂厂贝林翰贝林翰75464，0，7551320，6540，86755，尤基尼尤基尼12535280，541645，656900，557910，艾艾 尔尔 贝贝 李李1009950，6820，38870，1568530，851。人工规则的确很好的照顾了贝林翰和澳尔巴古的。人工规则的确很好的照顾了贝林翰和澳尔巴古的利益，但它却使尤基尼和艾尔贝利益，但它却使尤基尼和艾尔贝李的利益大大受损。李的利益大大受损。而后两个厂的产量都多于前者。而后两个厂的产量都多于前者。2。虽然人工规则所在行和列都选了最小值，但没有。虽然人工规则所在行和列都选了最小值，但没有选全局最小值，造成了局部最优，全局受损。选全局最小值，造成了局部最优，全局受损。仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰46451365486775尤基尼352416690791125艾尔贝李99568238868510080657085仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰46451365486775尤基尼35280416690791125艾尔贝李99568238868510080657085仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰46451365486775尤基尼3528041669079112545艾尔贝李9956823887068510080657085仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰46451365486775尤基尼352804164569079112545艾尔贝李995682388706851003080657085仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰4645132065486775尤基尼352804164569079112545艾尔贝李99568238870685100308065207085仓库萨克拉门托盐 湖城赖 皮特城澳 尔巴古罐头厂贝林翰46451320654867557555尤基尼352804164569079112545艾尔贝李9956823887068530100308065207085一老板有一老板有3工厂生产甲产工厂生产甲产品销往品销往4个地区，个地区，求运费最少？求运费最少？销地销地B1销地销地B2销地销地B3销地销地B4产量产量产地产地A13元元/吨吨113107吨吨产地产地A218284产地产地A3741059销量销量3吨吨656练习题练习题思路：首先考虑思路：首先考虑运费最少的对应的产地和销地运费最少的对应的产地和销地书书P167例例1：求佳公司决定使用三个有生产余力的工厂进行：求佳公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。表的最后一行给出了要求的产品生产率数量来衡量。表的最后一行给出了要求的产品生产率（每天的产品数量），以满足计划的销售量。每种产（每天的产品数量），以满足计划的销售量。每种产品在不同工厂中的单位成本有差异。品在不同工厂中的单位成本有差异。重庆百货大楼股份有限公司物流优化配送系统重庆百货大楼股份有限公司物流优化配送系统指派问题指派问题(assignment problem)重庆移动公司基站维护外包问题的分析及对策重庆移动公司基站维护外包问题的分析及对策重庆移动公司基站维护外包问题的分析及对策重庆移动公司基站维护外包问题的分析及对策基站外包问题解析基站外包问题解析p实际维护工作中，结合重庆市行政划分和重庆移实际维护工作中，结合重庆市行政划分和重庆移动公司网络结构特点，分成了北碚片区动公司网络结构特点，分成了北碚片区(A1)(A1)、永川、永川片区片区(A2)(A2)、万州片区、万州片区(A3)(A3)、黔江片区、黔江片区(A4)(A4)、城区片、城区片区区(A5)(A5)、涪陵片区、涪陵片区(A6)(A6)六个片区进行代维工作开展。六个片区进行代维工作开展。重庆移动公司基站代维现状及问题城区城区北碚北碚永川永川涪陵涪陵万州万州黔江黔江城区城区涪陵涪陵北碚北碚永川永川万州万州黔江黔江公司公司1公司公司2公司公司3公司公司4Optimizationmodelforassigmentproblem01整数规划应用指派问题 (P128)英英日日德德俄俄甲甲乙乙丙丙丁丁2151341041415914161378119第五章：第五章：0-1整数规划整数规划英英日日德德俄俄甲甲乙乙丙丙丁丁2151341041415914161378119注意到：注意到：1从人来看，如果从人来看，如果B不作日语，损失特别大不作日语，损失特别大62从事来看，如果英语不分配给甲，损失特别大从事来看，如果英语不分配给甲，损失特别大501整数规划应用指派问题 (P128)原理：从人的角度思考原理：从人的角度思考.考虑人最适合的工作考虑人最适合的工作 从工作的角度思考从工作的角度思考.考虑工作最适合的人考虑工作最适合的人英英日日德德俄俄甲甲乙乙丙丙丁丁2151341041415914161378119各行都减去这一行的各行都减去这一行的最小值，得到的最小值，得到的0表表示这个示这个0所在的行对所在的行对应的人最适合的工作应的人最适合的工作是这个是这个0所在的列对所在的列对应的事应的事这一列有三个这一列有三个0，表示这一列的，表示这一列的事有三个人适合事有三个人适合作作行最小值行最小值英英日日德德俄俄甲甲乙乙丙丙丁丁01311260101105740142第五章：第五章：0-1整数规划整数规划指派问题第一步第一步:各行元素各行元素该行行最小该行行最小各列元素各列元素该列列最小该列列最小 本题有本题有n个独立的个独立的0元素则已得最优解元素则已得最优解 各列都减去这一列的各列都减去这一列的最小值，得到的最小值，得到的0表表示这个示这个0所在的列行所在的列行对应的事最适合的人对应的事最适合的人是这个是这个0所在的行对所在的行对应的人应的人甲甲 俄俄乙乙 日日丙丙 英英丁丁 德德英英日日德德俄俄甲甲乙乙丙丙丁丁01311260101105740142英英日日德德俄俄甲甲乙乙丙丙丁丁01370606905320100列最小值列最小值有三个人适合英文有三个人适合英文为什么确定丙英为什么确定丙英第五章：第五章：0-1整数规划整数规划 各列都减去这一列的最小值各列都减去这一列的最小值 每行至少一个每行至少一个0各行都减去这一行的最小值各行都减去这一行的最小值每列至少一个每列至少一个0第五章：第五章：0-1整数规划整数规划某列某列0的个数特别少，是什么意思？的个数特别少，是什么意思？某行某行0的个数特别少，是什么意思？的个数特别少，是什么意思？某列某列0的个数特别多，是什么意思？的个数特别多，是什么意思？某行某行0的个数特别多，是什么意思？的个数特别多，是什么意思？第五章：第五章：0-1整数规划整数规划谢谢！
展开阅读全文