Chapter运输问题简化实用

会计学1Chapter运输问题简化实用TheP&TCompanyDistributionProblem(Section6.1)(P&T公司的配送问题)CharacteristicsofTransportationProblems(Section6.2)(运输问题的特征)VariantsofTransportationProblems:BetterProducts(Section6.3)(运输问题的变形：求佳产品公司问题)TableofContents(主要内容)第1页/共81页VariantsofTransportationProblems:Nifty(Section6.3)(运输问题的变形：耐芙迪公司问题)ApplicationsofTransportationProblems:MetroWater(Section6.4)(运输问题的应用：米德罗水管站问题)ApplicationsofTransportationProblems:NorthernAirplane(Section6.4)(运输问题的应用：北方飞机制造公司问题)TableofContents(主要内容)第2页/共81页ApplicationsofTransportationProblems:Middletown(Section6.4)(运输问题的应用：米德尔学区问题)ApplicationsofTransportationProblems:Energetic(Section6.4)(运输问题的应用：源丰公司问题)ACaseStudy:TexagoCorp.SiteSelectionProblem(Section6.5)(运输问题的应用：特赛格公司的选址问题)TableofContents(主要内容)第3页/共81页P&TCompanyDistributionProblem罐头厂1-贝林翰罐头厂2-尤基尼罐头厂3-艾尔贝仓库1-萨克拉门托仓库2-盐湖城仓库3-赖皮特城仓库4-奥尔巴古第4页/共81页P&TCompanyDistributionProblem贝林翰先满足萨克拉门托，剩余的运送到盐湖城艾尔贝先满足奥尔巴古，剩余的运送到赖皮特尤基尼满足剩余需求第5页/共81页ShippingData第6页/共81页ShippingCostperTruckload第7页/共81页P&TCompanyDistributionProblem当前的配送结果是什么？总配送成本是多少？第8页/共81页CurrentShippingPlanTotalshippingcost=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)=$165,595第9页/共81页P&TCompanyDistributionProblem试建立该网络配送问题的数学模型？第10页/共81页运输问题运输问题关心的是以最低的总配送成本把出发地的任何产品运送到每一个目的地第11页/共81页TerminologyforaTransportationProblem第12页/共81页CharacteristicsofTransportationProblemsTheRequirementsAssumption(需求假设)Eachsourcehasafixedsupplyofunits,wherethisentiresupplymustbedistributedtothedestinations.(每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地)Eachdestinationhasafixeddemandforunits,wherethisentiredemandmustbereceivedfromthesources.(每一个目的地都有一个固定的需求量，所有的需求量都必须由出发地满足)第13页/共81页CharacteristicsofTransportationProblemsTheFeasibleSolutionsProperty(可行解特性)Atransportationproblemwillhavefeasiblesolutionsifandonlyifthesumofitssuppliesequalsthesumofitsdemands.(当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解)第14页/共81页CharacteristicsofTransportationProblemsTheCostAssumption(成本假设)Thecostofdistributingunitsfromanyparticularsourcetoanyparticulardestinationisdirectlyproportionaltothenumberofunitsdistributed.(从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系)Thiscostisjusttheunitcostofdistributiontimesthenumberofunitsdistributed.(这个成本就等于配送的单位成本乘以所配送的数量)第15页/共81页TheTransportationModelAnyproblem(whetherinvolvingtransportationornot)fitsthemodelforatransportationproblemif(任何满足下述两个条件的问题都可以建模成运输问题)ItcanbedescribedcompletelyintermsofatablelikeTable6.5thatidentifiesallthesources,destinations,supplies,demands,andunitcosts,and(完全描述成如表6.5所示的参数表形式，明确出发地、目的地、供应量、需求量和单位成本)第16页/共81页TheTransportationModelsatisfiesboththerequirementsassumptionandthecostassumption.(同时满足需求假设和成本假设)Theobjectiveistominimizethetotalcostofdistributingtheunits.(目标就是要使配送总成本最小)第17页/共81页TheP&TCo.TransportationProblem运输问题模型参数表(供应量、需求量和单位成本)第18页/共81页SpreadsheetFormulation第19页/共81页NetworkRepresentation第20页/共81页运输问题的网络表述忽略出发地和目的地在地理上的布局左边一列为出发地(S)，旁边的数字代表供应量右边一列为目的地(D)，旁边的数字代表需求量箭头表示可能的运输途径，其上面的数字代表单位运输成本第21页/共81页TheTransportationProblemisanLPLetxij=thenumberoftruckloadstoshipfromcanneryitowarehousej(假设xij是从第i个罐头加工厂运送到第j个仓库的车数)

(i=1,2,3;j=1,2,3,4)MinimizeCost=$464x11+$513x12+$654x13+$867x14+$352x21+$416x22

+$690x23+$791x24+$995x31+$682x32+$388x33+$685x34第22页/共81页TheTransportationProblemisanLPsubjectto(约束)

Cannery1: x11+x12+x13+x14=75

Cannery2: x21+x22+x23+x24=125

Cannery3: x31+x32+x33+x34=100

Warehouse1: x11+x21+x31=80

Warehouse2: x12+x22+x32=65

Warehouse3: x13+x23+x33=70

Warehouse4: x14+x24+x34=85

andxij≥0(i=1,2,3;j=1,2,3,4)第23页/共81页IntegerSolutionsPropertyAslongasallitssuppliesanddemandshaveintegervalues,anytransportationproblemwithfeasiblesolutionsisguaranteedtohaveanoptimalsolutionwithintegervaluesforallitsdecisionvariables.Therefore,itisnotnecessarytoaddconstraintstothemodelthatrestrictthesevariablestoonlyhaveintegervalues.第24页/共81页整数解性质只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件第25页/共81页求解(最优化)算法单纯形法网络单纯形法运输单纯形法算法的适应范围越小，求解效率越高第26页/共81页DistributionSystematProctorandGambleProctorandGambleneededtoconsolidateandre-designtheirNorthAmericandistributionsystemintheearly1990’s.(宝洁公司需要巩固并再设计其九十年代早期在北美建立起来的配送系统)50productcategories

(50个产品种类)60plants

(60家工厂)15distributioncenters

(15个配送中心)1000customerzones

(1000个客户区)获奖作品第27页/共81页DistributionSystematProctorandGambleSolvedmanytransportationproblems(oneforeachproductcategory).(解决大量运输问题，每个产品种类都存在一个运输问题)Goal:findbestdistributionplan,whichplantstokeepopen,etc.(目标：寻找最优的配送方案，哪些工厂保持开放)Closedmanyplantsanddistributioncenters,andoptimizedtheirproductsourcinganddistributionlocation.(关闭许多工厂和配送中心，优化产品来源和配送点)Implementedin1996.Saved$200millionperyear.(1996年实施，北美工厂数减少20%，每年给公司节约2亿美金)第28页/共81页ModelingVariantsofTransportationProblemThesumofthesuppliesexceedsthesumofthedemands.(供应总量超过需求总量)Thesumofthesuppliesislessthanthesumofthedemands.(供应总量小于需求总量)Adestinationhasbothaminimumdemandandamaximumdemand.(一个目的地同时存在最小需求和最大需求)Certainsource-destinationcombinationscannotbeusedfordistributingunits.(在配送中不能使用特定的出发地-目的地组合)Theobjectiveistomaximizethetotalprofit.(目标是最大化总利润)第29页/共81页BetterProducts(AssigningPlantstoProducts)TheBetterProductsCompanyhasdecidedtoinitiatetheproductoffournewproducts,usingthreeplantsthatcurrentlyhaveexcesscapacity.(求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造)第30页/共81页BetterProducts(AssigningPlantstoProducts)生产能力产品1234工厂1412728247524029-237533730272145需求的产量20303040表示不存在数据的单元格第31页/共81页TransportationProblemFormulation第32页/共81页BetterProducts(AssigningPlantstoProducts)Whichplantsshouldproducewhichproducts?哪个工厂应该生产哪种产品？第33页/共81页SpreadsheetFormulation第34页/共81页TheNiftyCompanyspecializesintheproductionofasingleproduct,whichitproducesinthreeplants.(耐芙迪公司在3个工厂中专门生产一种产品)Fourcustomerswouldliketomakemajorpurchases.Therewillbeenoughtomeettheirminimumpurchaserequirements,butnotalloftheirrequestedpurchases.(订单主要来自四个客户，公司能够满足他们的最低购买要求，但是无法满足他们的所有购买要求)NiftyCo.(ChoosingCustomers)第35页/共81页Duelargelytovariationsinshippingcost,thenetprofitperunitsoldvariesdependingonwhichplantsupplieswhichcustomer.(主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个客户)NiftyCo.(ChoosingCustomers)第36页/共81页DatafortheNiftyCompany第37页/共81页NiftyCo.(ChoosingCustomers)耐芙迪公司应该销售给每个客户多少产品？应该从每个工厂运送多少产品至每个客户？HowmanyunitsshouldNiftyselltoeachcustomerandhowmanyunitsshouldtheyshipfromeachplanttoeachcustomer?第38页/共81页SpreadsheetFormulation第39页/共81页MetroWater(DistributingNaturalResources)MetroWaterDistrictisanagencythatadministerswaterdistributioninalargegeographicregion.Theregionisarid,sowatermustbebroughtinfromoutsidetheregion.(米德罗水管站是一个主管着广阔地域的水资源分配机构，由于这个地域十分干燥，所以这个机构需要从外地引水)第40页/共81页MetroWater(DistributingNaturalResources)Sourcesofimportedwater:Colombo,Sacron,andCalorierivers.(水源主要有：科伦坡河、塞克隆河和卡路里河)Maincustomers:CitiesofBerdoo,LosDevils,SanGo,andHollyglass.(主要的客户有：布都城、劳斯戴维斯城、圣哥城和豪利格拉斯城)第41页/共81页MetroWater(DistributingNaturalResources)第42页/共81页MetroWater(DistributingNaturalResources)应该从每条河里获取多少水资源？应该从每条河里向各个城市输送多少水资源？HowmuchwatershouldMetrotakefromeachriver,andhowmuchshouldtheysendfromeachrivertoeachcity?第43页/共81页SpreadsheetFormulation第44页/共81页NorthernAirplane(ProductionScheduling)NorthernAirplaneCompanyproducescommercialairplanes.Thelaststageinproductionistoproducethejetenginesandinstallthem.

(北方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后一步是生产喷气发动机并把它们安装到已经完成的飞机框架上去)第45页/共81页NorthernAirplane(ProductionScheduling)Thecompanymustmeetthedeliverydeadlineindicatedincolumn2.(公司必须满足交货期的限制)Productionandstoragecostsvaryfrommonthtomonth.(生产和存储成本每个月都有可能发生变化)第46页/共81页NorthernAirplane(ProductionScheduling)第47页/共81页NorthernAirplane(ProductionScheduling)每个月各生产多少航空发动机可以使生产和存储总成本最低？Howmanyenginesshouldbeproducedineachofthefourmonthssothatthetotaloftheproductionandstoragecostswillbeminimized?第48页/共81页SpreadsheetFormulation第49页/共81页OptimalProductionatNorthernAirplane第50页/共81页MiddletownSchoolDistrictMiddletownSchoolDistrictisopeningathirdhighschoolandthusneedstoredrawtheboundariesfortheareaofthecitythatwillbeassignedtotherespectiveschools.(米德尔城学区开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域)Thecityhasbeendividedinto9tractswithapproximatelyequalpopulations.(这个城市被分成了拥有大致相同数量人口的9个区域)第51页/共81页MiddletownSchoolDistrictEachschoolhasaminimumandmaximumnumberofstudentsthatshouldbeassigned.(每一所中学都有一个最小和最大的学生数目的要求)Theschooldistrictmanagementhasdecidedthattheappropriateobjectiveistominimizetheaveragedistancethatstudentsmusttraveltoschool.(学区管理者认为划分学区界限的适当目标是使学生到学校的平均路程最短)第52页/共81页DatafortheMiddletownSchoolDistrict第53页/共81页Howmanystudentsfromeachtractshouldbeassignedtoeachschool?各个区域应该有多少学生被分配到各个学校？MiddletownSchoolDistrict第54页/共81页SpreadsheetFormulation第55页/共81页Energetic(MeetingEnergyNeeds)TheEnergeticCompanyneedstomakeplansfortheenergysystemsforanewbuilding.(源丰公司需要为新的建筑物建立起能源系统)第56页/共81页Energetic(MeetingEnergyNeeds)Theenergyneedsfallintothreecategories:(能源需求主要来源于三个方面)electricity(20units)(电，20个单位)heatingwater(10units)(热水，10个单位)heatingspace(30units)(建筑物内取暖，30个单位)第57页/共81页Energetic(MeetingEnergyNeeds)Thethreepossiblesourcesofenergyare(满足这些需求的三个可能的能源来源是)Electricity(电)naturalgas(天然气)solarheatingunit(limitedto30unitsbecauseofroofsize)(安装在屋顶上的太阳能加热装置，由于屋顶大小的限制，太阳能的能源量只有30个单位)第58页/共81页CostDataforEnergetic第59页/共81页Energetic(MeetingEnergyNeeds)HowshouldEnergeticmeettheenergyneedsforthenewbuilding?源丰公司应该如何来满足新建筑的能源需求？第60页/共81页SpreadsheetFormulation第61页/共81页使用符号的总结当需求大于供应时，供应前用“=”，需求前用“