Chapter06-运输问题和指派问题.ppt
《Chapter06-运输问题和指派问题.ppt》由会员分享,可在线阅读,更多相关《Chapter06-运输问题和指派问题.ppt(106页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Chapter 6.Transportation and Assignment Problems第六章第六章.运输问运输问题和指派问题题和指派问题Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 2The P&T Company Distribution Problem(Section 6.1)(P&T(P&T公司的配送问题公司的配送问题)Characteristics of Transportation Problems(Section 6.2)(运输问题的特征运输问题的特征)Variants of Transportation Problems:Better P
2、roducts(Section 6.3)(运输问题的运输问题的变形:求佳产品公司问题变形:求佳产品公司问题)Table of Contents(主要内容主要内容)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 3Variants of Transportation Problems:Nifty(Section 6.3)(运输问题的变形:耐芙运输问题的变形:耐芙迪公司问题迪公司问题)Applications of Transportation Problems:Metro Water(Section 6.4)(运输问题的应运输问题的应用:米德罗水管站问题用:米德罗水
3、管站问题)Applications of Transportation Problems:Northern Airplane(Section 6.4)(运输问题运输问题的应用:北方飞机制造公司问题的应用:北方飞机制造公司问题)Table of Contents(主要内容主要内容)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 4Applications of Transportation Problems:Middletown(Section 6.4)(运输问题的应用:运输问题的应用:米德尔学区问题米德尔学区问题)Applications of Transport
4、ation Problems:Energetic(Section 6.4)(运输问题的应用:运输问题的应用:源丰公司问题源丰公司问题)A Case Study:Texago Corp.Site Selection Problem(Section 6.5)(运输问题的应用:运输问题的应用:特赛格公司的选址问题特赛格公司的选址问题)Table of Contents(主要内容主要内容)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 5Characteristics of Assignment Problems:Sellmore(Section 6.6)(指派问题的特征
5、:塞尔指派问题的特征:塞尔默公司问题默公司问题)Variants of Assignment Problems:Job Shop(Section 6.7)(指派问题的变形:娇普肖普公司指派问题的变形:娇普肖普公司问题问题)Variants of Assignment Problems:Better Products(Section 6.7)(指派问题的变形:求佳指派问题的变形:求佳产品公司问题产品公司问题)Variants of Assignment Problems:Revised Middletown(Section 6.7)(指派问题的变形:米指派问题的变形:米德尔学区的新问题德尔学区的
6、新问题)Table of Contents(主要内容主要内容)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 6P&T Company Distribution Problem罐头厂罐头厂1-1-贝林翰贝林翰罐头厂罐头厂2-2-尤基尼尤基尼罐头厂罐头厂3-3-艾尔贝艾尔贝仓库仓库1-1-萨克拉门托萨克拉门托仓库仓库2-2-盐湖城盐湖城仓库仓库3-3-赖皮特城赖皮特城仓库仓库4-4-奥尔巴古奥尔巴古Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 7P&T Company Distribution Problem贝林翰先满足萨克拉门托,贝
7、林翰先满足萨克拉门托,剩余的运送到盐湖城剩余的运送到盐湖城艾尔贝先满足奥尔巴古,艾尔贝先满足奥尔巴古,剩余的运送到赖皮特剩余的运送到赖皮特尤基尼满足剩余需求尤基尼满足剩余需求Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 8Shipping DataCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 9Shipping Cost per TruckloadCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 10P&T Company Distribution Problem当前的配送结果是什么?总配送成本是多少?
8、Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 11Current Shipping PlanTotal shipping cost=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)=$165,595Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 12P&T Company Distribution Problem试建立该网络配送问题的数学模型?Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 13运输问题运输问题运输问题关心的是以最低的总配送成本把出
9、发地的任何产品运送到每一个目的地Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 14Terminology for a Transportation ProblemCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 15Characteristics of Transportation ProblemsThe Requirements Assumption(需求假设需求假设)lEach source has a fixed supply of units,where this entire supply must be distribut
10、ed to the destinations.(每一个出发每一个出发地都有一个固定的供应量,所有的供应量都必地都有一个固定的供应量,所有的供应量都必须配送到目的地须配送到目的地)lEach destination has a fixed demand for units,where this entire demand must be received from the sources.(每一个目的地都每一个目的地都有一个固定的需求量,所有的需求量都必须由有一个固定的需求量,所有的需求量都必须由出发地满足出发地满足)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学
11、16Characteristics of Transportation ProblemsThe Feasible Solutions Property(可行解特性可行解特性)lA transportation problem will have feasible solutions if and only if the sum of its supplies equals the sum of its demands.(当且仅当供应量的总当且仅当供应量的总和等于需求量的总和时,运输问题才有和等于需求量的总和时,运输问题才有可行解可行解)Copyright 2007 深圳大学管理学院深圳大学管理
12、学院 运筹学运筹学 17Characteristics of Transportation ProblemsThe Cost Assumption(成本假设成本假设)lThe cost of distributing units from any particular source to any particular destination is directly proportional to the number of units distributed.(从任何从任何一个出发地到任何一个目的地的货物配送一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系成本和所配送的数量
13、成线性比例关系)lThis cost is just the unit cost of distribution times the number of units distributed.(这个成本就等于配送的单位这个成本就等于配送的单位成本乘以所配送的数量成本乘以所配送的数量)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 18The Transportation ModelAny problem(whether involving transportation or not)fits the model for a transportation proble
14、m if(任何满任何满足下述两个条件的问题都可以建模成运输足下述两个条件的问题都可以建模成运输问题问题)lIt can be described completely in terms of a table like Table 6.5 that identifies all the sources,destinations,supplies,demands,and unit costs,and(完全描述成完全描述成如表如表6.56.5所示的参数表形式,明确出发地、目所示的参数表形式,明确出发地、目的地、供应量、需求量和单位成本的地、供应量、需求量和单位成本)Copyright 2007 深圳
15、大学管理学院深圳大学管理学院 运筹学运筹学 19The Transportation Modellsatisfies both the requirements assumption and the cost assumption.(同时满足需求假设和同时满足需求假设和成本假设成本假设)The objective is to minimize the total cost of distributing the units.(目标就是要使配送总目标就是要使配送总成本最小成本最小)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 20The P&T Co.Transp
16、ortation Problem运输问题模型参数表运输问题模型参数表(供应供应量、需求量和单位成本量、需求量和单位成本)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 21Spreadsheet FormulationCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 22Network RepresentationCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 23运输问题的网络表述运输问题的网络表述忽略出发地和目的地在地理上的忽略出发地和目的地在地理上的布局布局左边一列为出发地左边一列为出发地(S)S),
17、旁边的数旁边的数字代表供应量字代表供应量右边一列为目的地右边一列为目的地(D)D),旁边的旁边的数字代表需求量数字代表需求量箭头表示可能的运输途径,其上箭头表示可能的运输途径,其上面的数字代表单位运输成本面的数字代表单位运输成本Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 24The Transportation Problem is an LPLet xij=the number of truckloads to ship from cannery i to warehouse j(假假设设xij是从第是从第i个罐头加工厂运送到第个罐头加工厂运送到第j个个仓库
18、的车数仓库的车数)(i=1,2,3;j=1,2,3,4)Minimize Cost=$464x11+$513x12+$654x13+$867x14+$352x21+$416x22+$690 x23+$791x24+$995x31+$682x32+$388x33+$685x34Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 25The Transportation Problem is an LPsubject to(约束约束)Cannery 1:x11+x12+x13+x14=75Cannery 2:x21+x22+x23+x24=125Cannery 3:x31
19、+x32+x33+x34=100Warehouse 1:x11+x21+x31=80Warehouse 2:x12+x22+x32=65Warehouse 3:x13+x23+x33=70Warehouse 4:x14+x24+x34=85and xij 0(i=1,2,3;j=1,2,3,4)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 26Integer Solutions PropertyAs long as all its supplies and demands have integer values,any transportation proble
20、m with feasible solutions is guaranteed to have an optimal solution with integer values for all its decision variables.Therefore,it is not necessary to add constraints to the model that restrict these variables to only have integer values.Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 27整数解性质整数解性质只要它的供应量和需求
21、量都是只要它的供应量和需求量都是整数,任何有可行解的运输问整数,任何有可行解的运输问题必然有所有变量都是整数的题必然有所有变量都是整数的最优解。因此,没有必要加上最优解。因此,没有必要加上所有变量都是整数的约束条件所有变量都是整数的约束条件Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 28求解求解(最优化最优化)算法算法单纯形法单纯形法网络单纯形法网络单纯形法运输单纯形法运输单纯形法算法的适应范围越小,算法的适应范围越小,求解效率越高求解效率越高Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 29Distribution Syste
22、m at Proctor and GambleProctor and Gamble needed to consolidate and re-design their North American distribution system in the early 1990s.(Proctor&Gamble(Proctor&Gamble公司需要公司需要巩固并再设计其九十年代早期在北美建立巩固并再设计其九十年代早期在北美建立起来的配送系统起来的配送系统)l50 product categories(50(50个产品种类个产品种类)l60 plants(60(60家工厂家工厂)l15 distrib
23、ution centers(15(15个配送中心个配送中心)l1000 customer zones(1000(1000个客户区个客户区)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 30Distribution System at Proctor and GambleSolved many transportation problems(one for each product category).(解决大量运输问题,解决大量运输问题,每个产品种类都存在一个运输问题每个产品种类都存在一个运输问题)Goal:find best distribution plan
24、,which plants to keep open,etc.(目标:寻找最优的配送方案,目标:寻找最优的配送方案,哪些工厂保持开放哪些工厂保持开放)Closed many plants and distribution centers,and optimized their product sourcing and distribution location.(关闭许多工厂和配送中心,关闭许多工厂和配送中心,优化产品来源和配送点优化产品来源和配送点)Implemented in 1996.Saved$200 million per year.(1996年实施,北美工厂数减少年实施,北美工厂数
25、减少20%,每年,每年给公司节约给公司节约2亿美金亿美金)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 31Modeling Variants of Transportation ProblemThe sum of the supplies exceeds the sum of the demands.(供应总量超过需求总量供应总量超过需求总量)The sum of the supplies is less than the sum of the demands.(供应总量小于需求总量供应总量小于需求总量)A destination has both a min
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapter06 运输 问题 指派
限制150内