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