运筹学与供应链管理第五讲Transportation and Network Models

第五讲TransportationandNetworkModels,Introduction,Severalspecificmodels(whichcanbeusedastemplatesforreal-lifeproblems)willbeintroduced.,TRANSPORTATIONMODEL,ASSIGNMENTMODEL,NETWORKMODELS,Introduction,TRANSPORTATIONMODEL,ASSIGNMENTMODEL,Determinehowtosendproductsfromvarioussourcestovariousdestinationsinordertosatisfyrequirementsatthelowestpossiblecost.,Allocatingfixed-sizedresourcestodeterminetheoptimalassignmentofsalespeopletodistricts,jobstomachines,taskstocomputers,NETWORKMODELS,Involvethemovementorassignmentofphysicalentities(e.g.,money).,TransportationModel,Anexample,theAutoPowerCompanymakesavarietyofbatteryandmotorizeduninterruptibleelectricpowersupplies(UPSs).,AutoPowerhas4finalassemblyplantsinEuropeandthedieselmotorsusedbytheUPSsareproducedintheUS,shippedto3harborsandthensenttotheassemblyplants.,Productionplansforthethirdquarter(JulySept.)havebeenset.Therequirements(demandatthedestination)andtheavailablenumberofmotorsatharbors(supplyatorigins)areshownonthenextslide:,Demand,Supply,AssemblyPlantNo.ofMotorsRequiredLeipzig400(2)Nancy900(3)Liege200(4)Tilburg5002000,HarborNo.ofMotorsAvailable(A)Amsterdam500(B)Antwerp700(C)LeHavre8002000,Graphicalpresentationof,TransportationModel,AutoPowermustdecidehowmanymotorstosendfromeachharbor(supply)toeachplant(demand).,Thecost($,onapermotorbasis)ofshippingisgivenbelow.,Thegoalistominimizetotaltransportationcost.,Sincethecostsintheprevioustableareonaperunitbasis,wecancalculatetotalcostbasedonthefollowingmatrix(wherexijrepresentsthenumberofunitsthatwillbetransportedfromOriginitoDestinationj):,TransportationModel,TransportationModel,Twogeneraltypesofconstraints.,1.Thenumberofitemsshippedfromaharborcannotexceedthenumberofitemsavailable.,ForAmsterdam:xA1+xA2+xA3+xA4500,ForAntwerp:xB1+xB2+xB3+xB4700,ForLeHavre:xC1+xC2+xC3+xC4900,ForLiege:xA3+xB3+xC3200,Note:Wecouldhaveusedan“=“insteadof“sincesupplyanddemandarebalancedforthismodel.,ForTilburg:xA4+xB4+xC4500,TransportationModel,Twogeneraltypesofconstraints.,VariationsontheTransportationModel,Supposewenowwanttomaximizethevalueoftheobjectivefunctioninsteadofminimizingit.,Inthiscase,wewouldusethesamemodel,butnowtheobjectivefunctioncoefficientsdefinethecontributionmargins(i.e.,unitreturns)insteadofunitcosts.,SolvingMaxTransportationModels,Whensupplyanddemandarenotequal,thentheproblemisunbalanced.Therearetwosituations:,Whensupplyisgreaterthandemand:,WhenSupplyandDemandDiffer,Inthiscase,whenalldemandissatisfied,theremainingsupplythatwasnotallocatedateachoriginwouldappearasslackinthesupplyconstraintforthatorigin.,Usinginequalitiesintheconstraints(asinthepreviousexample)wouldnotcauseanyproblems.,VariationsontheTransportationModel,Inthiscase,theLPmodelhasnofeasiblesolution.However,therearetwoapproachestosolvingthisproblem:,1.Rewritethesupplyconstraintstobeequalitiesandrewritethedemandconstraintstobe.,Unfulfilleddemandwillappearasslackoneachofthedemandconstraintswhenoneoptimizesthemodel.,Whendemandisgreaterthansupply:,VariationsontheTransportationModel,2.Revisethemodeltoappendaplaceholderorigin,calledadummyorigin,withsupplyequaltothedifferencebetweentotaldemandandtotalsupply.,Thepurposeofthedummyoriginistomaketheproblembalanced(totalsupply=totaldemand)sothatonecansolveit.,Thecostofsupplyinganydestinationfromthisoriginiszero.,Oncesolved,anysupplyallocatedfromthisorigintoadestinationisinterpretedasunfilleddemand.,VariationsontheTransportationModel,Certainroutesinatransportationmodelmaybeunacceptableduetoregionalrestrictions,deliverytime,etc.,Inthiscase,youcanassignanarbitrarilylargeunitcostnumber(identifiedasM)tothatroute.,Thiswillforceonetoeliminatetheuseofthatroutesincethecostofusingitwouldbemuchlargerthanthatofanyotherfeasiblealternative.,EliminatingUnacceptableRoutes,ChooseMsuchthatitwillbelargerthananyotherunitcostnumberinthemodel.,VariationsontheTransportationModel,Generally,LPmodelsdonotproduceintegersolutions.,TheexceptiontothisistheTransportationmodel.Ingeneral:,IntegerValuedSolutions,Ifallofthesuppliesanddemandsinatransportationmodelhaveintegervalues,theoptimalvaluesofthedecisionvariableswillalsohaveintegervalues.,VariationsontheTransportationModel,AssignmentModel,Ingeneral,theAssignmentmodelistheproblemofdeterminingtheoptimalassignmentofn“indivisible”agentsorobjectstontasks.,Forexample,youmightwanttoassign,Salespeopletosalesterritories,Computerstonetworks,Consultantstoclients,Servicerepresentativestoservicecalls,Commercialartiststoadvertisingcopy,Theimportantconstraintisthateachpersonormachinebeassignedtooneandonlyonetask.,WewillusetheAutoPowerexampletoillustrateAssignmentproblems.,AutoPowerEuropesAuditingProblem,AutoPowersEuropeanheadquartersisinBrussels.Thisyear,eachofthefourcorporatevice-presidentswillvisitandauditoneoftheassemblyplantsinJune.Theplantsarelocatedin:,Leipzig,Germany,Liege,Belgium,Nancy,France,Tilburg,theNetherlands,AssignmentModel,Theissuestoconsiderinassigningthedifferentvice-presidentstotheplantsare:,1.Matchingthevice-presidentsareasofexpertisewiththeimportanceofspecificproblemareasinaplant.,2.Thetimethemanagementauditwillrequireandtheotherdemandsoneachvice-presidentduringthetwo-weekinterval.,3.Matchingthelanguageabilityofavice-presidentwiththeplantsdominantlanguage.,Keepingtheseissuesinmind,firstestimatethe(opportunity)costtoAutoPowerofsendingeachvice-presidenttoeachplant.,AssignmentModel,Thefollowingtableliststheassignmentcostsin$000sforeveryvice-president/plantcombination.,AssignmentModel,Considerthefollowingassignment:,AssignmentModel,Completeenumerationisthecalculationofthetotalcostofeachfeasibleassignmentpatterninordertopicktheassignmentwiththelowesttotalcost.,SolvingbyCompleteEnumeration,Thisisnotaproblemwhenthereareonlyafewrowsandcolumns(e.g.,vice-presidentsandplants).However,completeenumerationcanquicklybecomeburdensomeasthemodelgrowslarge.,AssignmentModel,1.Fcanbeassignedtoanyofthe4plants.,2.OnceFisassigned,Mcanbeassignedtoanyoftheremaining3plants.,3.NowOcanbeassignedtoanyoftheremaining2plants.,4.Pmustbeassignedtotheonlyremainingplant.,Thereare4x3x2x1=24possiblesolutions.,Ingeneral,iftherearenrowsandncolumns,thentherewouldben(n-1)(n-2)(n-3)(2)(1)=n!(nfactorial)solutions.Asnincreases,n!increasesrapidly.Therefore,thismaynotbethebestmethod.,AssignmentModel,Forthismodel,letxij=numberofV.Psoftypeiassignedtoplantjwherei=F,M,O,Pj=1,2,3,4,TheLPFormulationandSolution,NoticethatthismodelisbalancedsincethetotalnumberofV.P.sisequaltothetotalnumberofplants.,Remember,onlyoneV.P.(supply)isneededateachplant(demand).,AssignmentModel,Asaresult,theoptimalassignmentis:,TotalCost($000s)=10+10+15+13=48,AssignmentModel,TheAssignmentmodelissimilartotheTransportationmodelwiththeexceptionthatsupplycannotbedistributedtomorethanonedestination.,RelationtotheTransportationModel,IntheAssignmentmodel,allsuppliesanddemandsareone,andhenceintegers.,Asaresult,eachdecisionvariablecellwilleithercontaina0(noassignment)ora1(assignmentmade).,Ingeneral,theassignmentmodelcanbeformulatedasatransportationmodelinwhichthesupplyateachoriginandthedemandateachdestination=1.,AssignmentModel,Case1:SupplyExceedsDemand,UnequalSupplyandDemand:,Intheexample,supposethecompanyPresidentdecidesnottoaudittheplantinTilburg.Nowthereare4V.P.stoassignto3plants.,Hereisthecost(in$000s)matrixforthisscenario:,AssignmentModel,Toformulatethismodel,simplydroptheconstraintthatrequiredaV.P.atplant4andsolveit.,AssignmentModel,UnequalSupplyandDemand:,Case2:DemandExceedsSupply,UnequalSupplyandDemand:,Inthisexample,assumethattheV.P.ofPersonnelisunabletoparticipateintheEuropeanaudit.Nowthecostmatrixisasfollows:,AssignmentModel,1.Modifytheinequalitiesintheconstraints(similartotheTransportationexample)2.AddadummyV.P.asaplaceholdertothecostmatrix(shownbelow).,AssignmentModel,Inthesolution,thedummyV.P.wouldbeassignedtoaplant.Inreality,thisplantwouldnotbeaudited.,AssignmentModel,UnequalSupplyandDemand:,InthisAssignmentmodel,theresponsefromeachassignmentisaprofitratherthanacost.,MaximizationModels,Forexample,AutoPowermustnowassignfournewsalespeopletothreeterritoriesinordertomaximizeprofit.,Theeffectofassigninganysalespersontoaterritoryismeasuredbytheanticipatedmarginalincreaseinprofitcontributionduetotheassignment.,AssignmentModel,Hereistheprofitmatrixforthismodel.,AssignmentModel,TheAssignmentModel,Certainassignmentsinthemodelmaybeunacceptableforvariousreasons.,SituationswithUnacceptableAssignments,Inthiscase,youcanassignanarbitrarilylargeunitcost(orsmallunitprofit)numbertothatassignment.,ThiswillforceSolvertoeliminatetheuseofthatassignmentsince,forexample,thecostofmakingthatassignmentwouldbemuchlargerthanthatofanyotherfeasiblealternative.,AssignmentModel,NetworkModels,Transportationandassignmentmodelsaremembersofamoregeneralclassofmodelscallednetworkmodels.,Networkmodelsinvolvefrom-tosourcesanddestinations.,Appliedtomanagementlogisticsanddistribution,networkmodelsareimportantbecause:,Theycanbeappliedtoawidevarietyofrealworldmodels.,Flowsmayrepresentphysicalquantities,Internetdatapackets,cash,airplanes,cars,ships,products,ZigwellInc.isAutoPowerslargestUSdistributorofUPSgeneratorsinfiveMidwesternstates.,NetworkModels,ACapacitatedTransshipmentModel,NetworkModels,Thisisanetworkdiagramornetworkflowdiagram.,Eacharrowiscalledanarcorbranch.Eachsiteistermedanode.,NetworkModels,cijthecosts(perunit)oftraversingtheroutes,uijthecapacitiesalongtheroutes,Costsareprimarilyduetofuel,tolls,andthecostofthedriverfortheaveragetimeittakestotraversethearc.,Becauseofpre-establishedagreementswiththeteamsters,Zigwellmustchangedriversateachsiteitencountersonaroute.,Becauseoflimitationsonthecurrentavailabilityofdrivers,thereisanupperbound,uij,onthenumberofgeneratorsthatmaytraverseanarc.,NetworkModels,NetworkModels,LPFormulationoftheModel,NetworkModels,ACapacitatedTransshipmentModel,Thegoalistofindashipmentplanthatsatisfiesthedemandsatminimumcost,subjecttothecapacityconstraints.,Thecapacitatedtransshipmentmodelisbasicallyidenticaltothetransportationmodelexceptthat:,1.Anyplantorwarehousecanshiptoanyotherplantorwarehouse,2.Therecanbeupperand/orlowerbounds(capacities)oneachshipment(branch),NetworkModels,Thedecisionvariablesare:,xij=totalnumberofBigGenssentonarc(i,j)=flowfromnodeitonodej,Themodelbecomes:,Minc12x12+c23x23+c24x24+c25x25+c34x34+c43x43+c53x53+c54x54,s.t.,+x12=10,-x12+x23+x24+x25=0,-x23x43x53+x34=-3,-x24+x43x34x54=-7,-x25+x53+x54=0,0xijuijallarcs(i,j)inthenetwork,PropertiesoftheModel,1.xijisassociatedwitheachofthe8arcsinthenetwork.Therefore,thereare8correspondingvariables:x12,x23,x24,x25,x34,x43,x53,andx54Theobjectiveistominimizetotalcost.,2.Thereisonematerialflowbalanceequationassociatedwitheachnodeinthenetwork.Forexample:,Intermediatenodesthatareneithersupplypointsnordemandpointsareoftentermedtransshipmentnodes.,3.Thepositiveright-handsidescorrespondtonodesthatarenetsuppliers(origins).,Thesumofallright-hand-sidetermsiszero(i.e.,totalsupplyinthenetworkequalstotaldemand).,Thezeroright-handsidescorrespondtonodesthathaveneithersupplynordemand.,Thenegativeright-handsidescorrespondtonodesthatarenetdestinations.,Ingeneral,flowbalanceforagivennode,j,is:,Totalflowoutofnodejtotalflowintonodej=supplyatnodej,Negativesupplyisarequirement.Nodeswithnegativesupplyarecalleddestinations,sinks,ordemandpoints.,Nodeswithpositivesupplyarecalledorigins,sources,orsupplypoints.,Nodeswithzerosupplyarecalledtransshipmentpoints.,4.AsmallmodelcanbeoptimizedwithSolver.,IntegerOptimalSolutions,NetworkModels,ACapacitatedTransshipmentModel,Theintegerpropertyofthenetworkmodelcanbestatedthus:,IfalltheRHStermsandarccapacities,uij,areintegersinthecapacitatedtransshipmentmodel,therewillalwaysbeaninteger-valuedoptimalsolutiontothismodel.,NetworkModels,ThestructureofthismodelmakesitpossibletoapplyspecialsolutionmethodsandsoftwarethatoptimizethemodelmuchmorequicklythanthemoregeneralsimplexmethodusedbySolver.,EfficientSolutionProcedures,NetworkModels,ACapacitatedTransshipmentModel,Thismakesitpossibletooptimizeverylargescalenetworkmodelsquicklyandcheaply.,NetworkModels,Theshortest-routemodelreferstoanetworkforwhicheacharc(i,j)hasanassociatednumber,cij,whichisinterpretedasthedistance(orcost,ortime)fromnodeitonodej.,NetworkModels,AShortest-RouteModel,Arouteorpathbetweentwonodesisanysequenceofarcsconnectingthetwonodes.,Theobjectiveistofindtheshortest(orleast-costorleast-time)routesfromaspecificnodetoeachoftheothernodesinthenetwork.,NetworkModels,Inthisexample,AaronDrunnermakesfrequentwinedeliveriesto7differentsites:,Notethatthearcsareundirected(flowispermittedineitherdirection).,Thegoalistominimizeoverallcostsbymakingsurethatanyfuturedeliverytoanygivensiteismadealongtheshortestroutetothatsite.,ThegoalistominimizeoverallcostsbyfindingtheshortestroutefromnodeHtoanyoftheother7nodes.Notethatinthismodel,thetaskistofindanoptimalroute,notoptimalxijs.,NetworkModels,Inthisexample,MichaelCarrisresponsibleforobtainingahighspeedprintingpressforhisnewspapercompany.,NetworkModels,AnEquipmentReplacementModel,Inagivenyearhemustchoosebetweenpurchasing:,NewPrintingPress,OldPrintingPress,highannualacquisitioncost,lowinitialmaintenancecost,noannualacquisitioncost,highinitialmaintenancecost,NetworkModels,Assumea4-yeartimehorizon.Let:,cijdenotethecostofbuyingnewequipmentatthebeginningofyeari,i=1,2,3,4andmaintainingittothebeginningofyearj,j=2,3,4,5,Threealternativefeasiblepoliciesare:,1.Buyingnewequipmentatthebeginningofeachyear.,Total(acquisition+maintenance)cost=c12+c23+c34+c45,2.Buynewequipmentonlyatthebeginningofyear1andmaintainitthroughallsuccessiveyears.,Total(buying+maintenance)cost=c15,3.Buynewequipmentatthebeg