Chapter06-运输问题和指派问题

Chapter6.TransportationandAssignmentProblems第六章.运输问题和指派问题Copyright2007©深圳大学管理学院运筹学2TheP&TCompanyDistributionProblem(Section6.1)(P&T公司的配送问题)CharacteristicsofTransportationProblems(Section6.2)(运输问题的特征)VariantsofTransportationProblems:BetterProducts(Section6.3)(运输问题的变形：求佳产品公司问题)TableofContents(主要内容)Copyright2007©深圳大学管理学院运筹学3VariantsofTransportationProblems:Nifty(Section6.3)(运输问题的变形：耐芙迪公司问题)ApplicationsofTransportationProblems:MetroWater(Section6.4)(运输问题的应用：米德罗水管站问题)ApplicationsofTransportationProblems:NorthernAirplane(Section6.4)(运输问题的应用：北方飞机制造公司问题)TableofContents(主要内容)Copyright2007©深圳大学管理学院运筹学4ApplicationsofTransportationProblems:Middletown(Section6.4)(运输问题的应用：米德尔学区问题)ApplicationsofTransportationProblems:Energetic(Section6.4)(运输问题的应用：源丰公司问题)ACaseStudy:TexagoCorp.SiteSelectionProblem(Section6.5)(运输问题的应用：特赛格公司的选址问题)TableofContents(主要内容)Copyright2007©深圳大学管理学院运筹学5CharacteristicsofAssignmentProblems:Sellmore(Section6.6)(指派问题的特征：塞尔默公司问题)VariantsofAssignmentProblems:JobShop(Section6.7)(指派问题的变形：娇普肖普公司问题)VariantsofAssignmentProblems:BetterProducts(Section6.7)(指派问题的变形：求佳产品公司问题)VariantsofAssignmentProblems:RevisedMiddletown(Section6.7)(指派问题的变形：米德尔学区的新问题)TableofContents(主要内容)Copyright2007©深圳大学管理学院运筹学6P&TCompanyDistributionProblemCANNERY1BellinghamCANNERY2EugeneWAREHOUSE1SacramentoWAREHOUSE2SaltLakeCityWAREHOUSE3RapidCityWAREHOUSE4AlbuquerqueCANNERY3AlbertLea罐头厂1-贝林翰罐头厂2-尤基尼罐头厂3-艾尔贝仓库1-萨克拉门托仓库2-盐湖城仓库3-赖皮特城仓库4-奥尔巴古Copyright2007©深圳大学管理学院运筹学7P&TCompanyDistributionProblem贝林翰先满足萨克拉门托，剩余的运送到盐湖城艾尔贝先满足奥尔巴古，剩余的运送到赖皮特尤基尼满足剩余需求Copyright2007©深圳大学管理学院运筹学8ShippingDataCopyright2007©深圳大学管理学院运筹学9ShippingCostperTruckloadCopyright2007©深圳大学管理学院运筹学10P&TCompanyDistributionProblem当前的配送结果是什么？总配送成本是多少？Copyright2007©深圳大学管理学院运筹学11CurrentShippingPlanTotalshippingcost=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)=$165,595Copyright2007©深圳大学管理学院运筹学12P&TCompanyDistributionProblem试建立该网络配送问题的数学模型？Copyright2007©深圳大学管理学院运筹学13运输问题运输问题关心的是以最低的总配送成本把出发地的任何产品运送到每一个目的地Copyright2007©深圳大学管理学院运筹学14TerminologyforaTransportationProblemCopyright2007©深圳大学管理学院运筹学15CharacteristicsofTransportationProblemsTheRequirementsAssumption(需求假设)Eachsourcehasafixedsupplyofunits,wherethisentiresupplymustbedistributedtothedestinations.(每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地)Eachdestinationhasafixeddemandforunits,wherethisentiredemandmustbereceivedfromthesources.(每一个目的地都有一个固定的需求量，所有的需求量都必须由出发地满足)Copyright2007©深圳大学管理学院运筹学16CharacteristicsofTransportationProblemsTheFeasibleSolutionsProperty(可行解特性)Atransportationproblemwillhavefeasiblesolutionsifandonlyifthesumofitssuppliesequalsthesumofitsdemands.(当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解)Copyright2007©深圳大学管理学院运筹学17CharacteristicsofTransportationProblemsTheCostAssumption(成本假设)Thecostofdistributingunitsfromanyparticularsourcetoanyparticulardestinationisdirectlyproportionaltothenumberofunitsdistributed.(从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系)Thiscostisjusttheunitcostofdistributiontimesthenumberofunitsdistributed.(这个成本就等于配送的单位成本乘以所配送的数量)Copyright2007©深圳大学管理学院运筹学18TheTransportationModelAnyproblem(whetherinvolvingtransportationornot)fitsthemodelforatransportationproblemif(任何满足下述两个条件的问题都可以建模成运输问题)ItcanbedescribedcompletelyintermsofatablelikeTable6.5thatidentifiesallthesources,destinations,supplies,demands,andunitcosts,and(完全描述成如表6.5所示的参数表形式，明确出发地、目的地、供应量、需求量和单位成本)Copyright2007©深圳大学管理学院运筹学19TheTransportationModelsatisfiesboththerequirementsassumptionandthecostassumption.(同时满足需求假设和成本假设)Theobjectiveistominimizethetotalcostofdistributingtheunits.(目标就是要使配送总成本最小)Copyright2007©深圳大学管理学院运筹学20TheP&TCo.TransportationProblem运输问题模型参数表(供应量、需求量和单位成本)Copyright2007©深圳大学管理学院运筹学21SpreadsheetFormulationCopyright2007©深圳大学管理学院运筹学22NetworkRepresentationCopyright2007©深圳大学管理学院运筹学23运输问题的网络表述忽略出发地和目的地在地理上的布局左边一列为出发地(S)，旁边的数字代表供应量右边一列为目的地(D)，旁边的数字代表需求量箭头表示可能的运输途径，其上面的数字代表单位运输成本Copyright2007©深圳大学管理学院运筹学24TheTransportationProblemisanLPLetxij=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+$685x34Copyright2007©深圳大学管理学院运筹学25TheTransportationProblemisanLPsubjectto(约束)Cannery1:x11+x12+x13+x14=75Cannery2:x21+x22+x23+x24=125Cannery3:x31+x32+x33+x34=100Warehouse1:x11+x21+x31=80Warehouse2:x12+x22+x32=65Warehouse3:x13+x23+x33=70Warehouse4:x14+x24+x34=85andxij≥0(i=1,2,3;j=1,2,3,4)Copyright2007©深圳大学管理学院运筹学26IntegerSolutionsPropertyAslongasallitssuppliesanddemandshaveintegervalues,anytransportationproblemwithfeasiblesolutionsisguaranteedtohaveanoptimalsolutionwithintegervaluesforallitsdecisionvariables.Therefore,itisnotnecessarytoaddconstraintstothemodelthatrestrictthesevariablestoonlyhaveintegervalues.Copyright2007©深圳大学管理学院运筹学27整数解性质只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件Copyright2007©深圳大学管理学院运筹学28求解(最优化)算法单纯形法网络单纯形法运输单纯形法算法的适应范围越小，求解效率越高Copyright2007©深圳大学管理学院运筹学29DistributionSystematProctorandGambleProctorandGambleneededtoconsolidateandre-designtheirNorthAmericandistributionsystemintheearly1990’s.(Proctor&Gamble公司