第五章-运输问题与指派问题(MBA讲义)课件

大家好大家好1Chapter 5 5 运输问题与指派问题运输问题与指派问题Transportation and Assignment Problem 1运运 输输 模模 型型The Transportation model 2运输问题网络模型运输问题网络模型Transportation Network 3 应用实例应用实例4 指派问题指派问题 Assignment Problem 2物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）运输问题运输问题 The Transportation Problem想想看！想想看！如何分析这类问题31 运输问题模型实例运输问题模型实例 The P&T Company 分配网络P189P&TP&T公司是一家由家族经营的小公司。它收购生菜并在食品公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝李）加工，然后用卡车把它们运送到美国西部的四个分销李）加工，然后用卡车把它们运送到美国西部的四个分销仓库仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古科他州赖皮特城；新墨西哥州澳尔巴古)4P&T Company Distribution Problem贝林翰罐头工厂尤基尼工厂艾尔贝.李工厂萨克拉门萨克拉门托仓库托仓库奥尔巴古奥尔巴古盐湖城盐湖城P&TP&T公司问题中的仓库和加工厂位置图公司问题中的仓库和加工厂位置图赖皮特赖皮特澳尔巴古澳尔巴古5相关数据Shipping DataCanneryOutput产量产量Warehouse分配量分配量AllocationBellingham75 truckloadsSacramento80 truckloadsEugene125 truckloadsSalt Lake City65 truckloadsAlbert Lea100 truckloadsRapid City70 truckloadsTotal300 truckloadsAlbuquerque85 truckloadsTotal300 truckloads运输成本 per Truckload Warehouse仓库仓库From To萨克拉门托萨克拉门托盐湖城盐湖城赖皮特赖皮特澳尔巴古澳尔巴古罐头厂罐头厂贝林翰$464$513$654$867尤基尼352416690791艾尔贝.李995682388685总产量=总的需求量=300车，产销平衡6线性规划模型线性规划模型设设Let Let xij=从罐头厂从罐头厂i 运往仓库运往仓库j卡车数卡车数 the number of truckloads to ship from cannery i to warehouse j(i=1,2,3分别表示贝林翰罐头厂，尤基尼罐头厂，艾分别表示贝林翰罐头厂，尤基尼罐头厂，艾尔贝尔贝.李罐头厂；李罐头厂；j=1,2,3,4分别表示萨克拉门托仓库，盐湖城仓库，赖皮特分别表示萨克拉门托仓库，盐湖城仓库，赖皮特仓库和澳尔巴古仓库仓库和澳尔巴古仓库)则线性规划模型为则线性规划模型为 Minimize Cost=464x11+513x12+654x13+867x14+352x21+416x22+690 x23+791x24+995x31+682x32+388x33+685x34subject toCannery 1:x11+x12+x13+x14=75Cannery 2:x21+x22+x23+x24=125Cannery 3:x31+x32+x33+x34=100Warehouse 1:x11+x21+x31=80Warehouse 2:x12+x22+x32=65Warehouse 3:x13+x23+x33=70Warehouse 4:x14+x24+x34=85 xij 0(i=1,2,3;j=1,2,3,4)7Transportation Problem Example运输问题举例运输问题举例实际举例实际举例作为一个运输问题的作为一个运输问题的P&T公司电子表格描述公司电子表格描述 8运输问题一般模型运输问题一般模型general The Transportation problem modelTerminology术语 for a Transportation ProblemP&T Company ProblemTruckloads of canned peasCanneriesWarehousesOutput from a canneryAllocation to a warehouseShipping cost per truckload from a cannery to a warehouseGeneral ModelUnits of a commodity商品单位Sources运出地Destinations目的地Supply from a source运出量Demand at a destination需求量Cost per unit distributed from a source to a destination单位成本9 一般模型表示：设A1、A2、Am 表示m个产地；B1、B2、Bn 表示n个销地；ai 表示产地Ai的产量；bj 表示销地Bj 的销量；cij 表示把物资从产地Ai运往销地Bj的单位运价,设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：m n Min f=cij xij i=1 j=1 s.t.xij =ai i=1,2,m xij =bj j=1,2,n xij 0 (i=1,2,m;j=1,2,n)10运输问题的特征运输问题的特征Characteristics of Transportation Problems运输问题的假定数学模型为：1、需求假设：需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足2、可行解假定可行解假定：当且仅当供应量的总和总和等于需求量的总和时，运输问题才有可行解，且有最优解 3、成本假设：成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4、整数解性质：整数解性质：当供应量和需求量都是整数，必存在决策变量均为整数的最优解11例例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：解：产销平衡问题：总产量=总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：运运 输输 模模 型型 销地产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200 销地产地B1B2B3产量 aiA1646200A2655300销量 bj15015020012 数学模型为数学模型为 Min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2；j=1、2、3）133 Transportation Network 运输问题的运输问题的网络表示网络表示 销地产地B1B2B3B3供应量aiA1675325A2842710A259101615需求量 bj13219714Transportation Network 运输问题的网络表示运输问题的网络表示每一个节点建立一个约束方程，目标函数为每一条箭线上的决策变量xi j 乘以单位运价ci j之和2321341a2=10a3=15b1=13b2=21b3=9b4=7a1=25供供应应量量sources运价运价需需求求量量Destinations 需求地需求地6753842759106x11x12x13x14A1A2A3B1B2B3B4suppliesdemands15供应地约束需求地约束LP Model of Transportation Problem运输问题线性规划模型运输问题线性规划模型16 供应总量超出了需求总量供应总量超出了需求总量 ai bj 供应总量小于需求总量供应总量小于需求总量 ai bj 增加一个虚拟的生产地，其产量等于增加一个虚拟的生产地，其产量等于bj ai，此产地到，此产地到需求地的单位运价为零。需求地的单位运价为零。一个目的地同时存在着最小需求和最大需求一个目的地同时存在着最小需求和最大需求 在配送中不能使用特定的出发地在配送中不能使用特定的出发地目的地组合目的地组合 目标是与配送量有关的总利润最大不是成本最小目标是与配送量有关的总利润最大不是成本最小 各种运输问题变体各种运输问题变体 Variants of Transportation Problems17求佳公司分配工厂生产产品P199求佳公司用3个有多余生产能力的工厂生产4种新产品，3个工厂的多余生产能力和4种产品的需求量以及每种产品在不同工厂的单位产品生产成本如下单位成本单位成本 Product:1234生产能力生产能力工厂工厂1$41$27$28$247524029237533730272145需求量20303040Question:哪个工厂应生产何种产品及数量哪个工厂应生产何种产品及数量18电电子子表表格格模模型型数学模型 Minimize Cost=41x11+27x12+28x13+24x14+40 x21+29x22+23x24+37x31+30 x32+27x33+21x34S.T.工厂1：x11+x12 x13+x14 75 工厂2:x21+x22+x23+x24 75 工厂3:x31+x32+x33+x34 45 产品1需求:x11+x21+x31=20 产品2需求:x12+x22+x32=30 产品3需求:x13+x23+x33=30 产品4需求:x14+x24+x34=30 xij 0(i=1,2,3;j=1,2,3,4)19耐芙迪公司选择顾客Nifty Company P201单位利润单位利润 顾客顾客:1234产量产量工厂工厂1$55$42$46$53800023718324850003295951357000最小采购量7000300020000要求采购量7000900060008000顾客顾客1 1为最好顾客，需求必须满足，顾客为最好顾客，需求必须满足，顾客2 2、3 3也是重要顾客，也是重要顾客，最低需满足其订单的最低需满足其订单的1/31/3，顾客，顾客4 4的订单可以不考虑，问，的订单可以不考虑，问，在满足上述要求的前提下，需向每一位顾客供应多少产品在满足上述要求的前提下，需向每一位顾客供应多少产品数量，可使总利润最大数量，可使总利润最大?20电子表格模型电子表格模型P200 7000 x11+x21+x31 7000 3000 x12+x22+x32 9000 3000 x13+x23+x33 6000 x14+x24+x34 8000SUM（C11：F11）21一个获奖的应用宝洁公司重新设计制造和配送体系一个获奖的应用宝洁公司重新设计制造和配送体系Distribution System at Proctor and Gamble P197nProctor and Gamble needed to consolidate合并 and re-design their North American distribution system in the early 1990s.q50 product categories 50多个产品类别多个产品类别q60 plants 60个工厂q15 distribution centers 15个配送中心个配送中心q1000 customer zones 超过超过1000个的顾客群体个的顾客群体 nSolved many transportation problems(one for each product category).nGoal:find best distribution plan,which plants to keep open,etc.nClosed many plants and distribution centers,and optimized their product sourcing and distribution location.工厂减少20%nImplemented in 1996.Saved$200 million per year.For more details,see 1997 Jan-Feb Interfaces article,“Blending OR/MS,Judgement,and GIS:Restructuring P&Gs Supply Chain”,downloadable at 22Metro Water米德罗水资源(Distributing Natural Resources)Metro Water District is an agency that administers water distribution in a large geographic region.The region is arid干旱,so water must be brought in from outside the region.qSources of imported water:克伦坡河Colombo,塞克隆Sacron,and 卡路里Calorie rivers.水源来自三条河qMain customers:Cities of Berdoo,Los Devils,San Go,and Hollyglass.供应四个城市Cost per Acre FootBerdooLos DevilsSan GoHollyglassAvailableColombo River$160$130$220$1705Sacron River1401301901506Calorie River1902002305Needed2541.5(million 立方英尺)Question:从每条河流中引进多少水，在满足需求的前提下，使总成本最少从每条河流中引进多少水，在满足需求的前提下，使总成本最少布都洛斯戴维斯圣哥豪利格拉斯P20323Spreadsheet Formulation布都洛斯戴维斯圣哥豪利格拉斯克伦坡克伦坡塞克隆塞克隆卡路里卡路里24北方飞机公司Northern Airplane(Production Scheduling)北方飞机公司生产商业飞机，其中最重要的步骤是生产飞机发动机Northern Airplane Company produces commercial airplanes.The last stage in production is to produce the jet engines and install them.q公司必须满足第2列发动机安装量 in column 2.qProduction and storage costs vary from month to month.Maximum ProductionUnit Cost of Production($million)Unit Costof Storage($thousand)MonthScheduledInstallationsRegularTimeOvertimeRegularTimeOvertime11020101.081.101521530151.111.121532525101.101.11154205101.131.15Question:制定一个生产计划，每月生产发动机的数量，使制造和存储制定一个生产计划，每月生产发动机的数量，使制造和存储成本最小成本最小How many engines should be produced in each of the four months so that the total of the production and storage costs will be minimized?P20525Spreadsheet Formulation26最优生产计划最优生产计划Optimal Production at Northern AirplaneMonth1(RT)2(RT)3(RT)3(OT)4(RT)Production201025105Installation101525020Stored10551001 1月份生产月份生产2020个发动机个发动机,其中当月装配其中当月装配1010个个,5,5个在个在2 2月份装配月份装配,另另5 5个在个在4 4月份装配月份装配,2,2月份正常生产月份正常生产1010个，用于当月装配，个，用于当月装配，3 3月份月份正常生产正常生产2525个，当月装配，个，当月装配，3 3月加班生产月加班生产1010个用于个用于4 4月分装配，月分装配，4 4月正常生产月正常生产5 5个用于当月装配。个用于当月装配。27米德尔城学生区域划分Middletown School DistrictnMiddletown米德尔城 School District is 开办opening a third high school and thus needs to redraw需要重新规划 the boundaries for the area of the city that will be assigned to the respective schools.nThe city has been divided into 9 tracts区域 with approximately equal populations.nEach school has a minimum and maximum number of students that should be assigned.nThe school district management has decided that the appropriate objective is to minimize the average distance that students must travel to school.Question:How many students from each tract should be assigned to each school?P20728Data for the Middletown School DistrictDistance(Miles)to SchoolTract123Number of High School Students12.21.92.550021.41.31.740030.51.81.145041.20.32.040050.90.71.050061.11.60.645072.70.71.545081.81.20.840091.51.70.7500Minimum enrollment1,2001,1001,000Maximum enrollment1,8001,7001,50029Spreadsheet Formulation3033运输问题的应用运输问题的应用 编制生产计划编制生产计划二、生产与储存问题二、生产与储存问题例例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。31解：解：设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：交货：x11 =10 生产：x11+x12+x13+x14 25 x12+x22 =15 x22+x23+x24 35 x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44 =20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：目标函数：Min f=10.8 x11+10.95 x12+11.1 x13+11.25 x14+11.1 x22+11.25 x23+11.4 x24 +11.0 x33+11.15 x34 +11.3 x44 32二、生产与储存问题二、生产与储存问题例例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？33解：解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和各月生产与交货分别视为产地和销地销地 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；2）上年末库存103台，只有仓储费和运输费，把它列为第0行；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）1-6表示1-6月份正常生产情况，1-6表示1-6月份加班生产情况。产销平衡与运价表：34 用软件解得的结果是：1-6月最低生产费用为8307.5万元，每月的销售安排如下表所示3533运输问题的应用运输问题的应用三、三、转运问题转运问题：在原运输问题上增加若干转运站。运输方式有：产地 转运站、转运站 销地、产地 产地、产地 销地、销地 转运站、销地 产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中 产地：1-广州、2-大连、转运站3-上海、4-天津、销地：5-南京、6-济南、7-南昌、8-青岛36解：解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：目标函数：Min f=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i ：输出量-输入量=产量 对转运站（中转点）：输入量-输出量=0 对销地（收点）j ：输入量-输出量=销量例8（续）目标函数：Min f=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48 约束条件：s.t.x13+x14 600 (广州分厂供应量限制）x23+x24+x28 400 (大连分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）x35+x45=200（南京的销量）x36+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）xij 0 ,i,j=1,2,3,4,5,6,7,837用软件求得结果：用软件求得结果：x13=550 x14=50 ；x23=0 x24=100 x28=300；x35=200 x36=0 x37=350 x38=0 ；x45=0 x46=150 x47=0 x48=0 。最小运输费用为：最小运输费用为：4600百元百元例例9、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：试求总费用为最少的调运方案。假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。38用Excel求解上述运输问题39运价如下表：解：解：把此转运问题转化为一般运输问题：1、把所有产地Ai、销地Bj、转运站Tk 都同时看作产地和销地；2、运输表中不可能方案的运费取作M，自身对自身的运费为0；3、Ai：产量为 20+原产量，销量为 20；Ti：产量、销量均为 20；Bi：产量为 20，销量为 20+原销量，其中20为各点可能变化的最大流量；4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。4033运输问题的应用运输问题的应用 扩大的运输问题产销平衡与运价表：41