运筹学与供应链管理-第5讲

第五讲TransportationandNetworkModelsIntroductionSeveralspecificmodels(whichcanbeusedastemplatesforreal-lifeproblems)willbeintroduced.TRANSPORTATIONMODELASSIGNMENTMODELNETWORKMODELSIntroductionTRANSPORTATIONMODELASSIGNMENTMODELDeterminehowtosendproductsfromvarioussourcestovariousdestinationsinordertosatisfyrequirementsatthelowestpossiblecost.Allocatingfixed-sizedresourcestodeterminetheoptimalassignmentofsalespeopletodistricts,jobstomachines,taskstocomputers…NETWORKMODELSInvolvethemovementorassignmentofphysicalentities(e.g.,money).TransportationModelAnexample,theAutoPowerCompanymakesavarietyofbatteryandmotorizeduninterruptibleelectricpowersupplies(UPS’s).AutoPowerhas4finalassemblyplantsinEuropeandthedieselmotorsusedbytheUPS’sareproducedintheUS,shippedto3harborsandthensenttotheassemblyplants.Productionplansforthethirdquarter(July–Sept.)havebeenset.Therequirements(demandatthedestination)andtheavailablenumberofmotorsatharbors(supplyatorigins)areshownonthenextslide:DemandSupplyAssemblyPlantNo.ofMotorsRequired(1)Leipzig400(2)Nancy900(3)Liege200(4)Tilburg5002000HarborNo.ofMotorsAvailable(A)Amsterdam500(B)Antwerp700(C)LeHavre8002000BalancedGraphicalpresentationofLeHavre(C)800Antwerp(B)700Amsterdam(A)500SupplyLiege(3)200Tilburg(4)500Leipzig(1)400Nancy(2)900andDemand:TransportationModelAutoPowermustdecidehowmanymotorstosendfromeachharbor(supply)toeachplant(demand).Thecost($,onapermotorbasis)ofshippingisgivenbelow.TODESTINATIONLeipzigNancyLiegeTilburgFROMORIGIN(1)(2)(3)(4)(A)Amsterdam1201304159.50(B)Antwerp6140100110(C)LeHavre102.509012242Thegoalistominimizetotaltransportationcost.Sincethecostsintheprevioustableareonaperunitbasis,wecancalculatetotalcostbasedonthefollowingmatrix(wherexijrepresentsthenumberofunitsthatwillbetransportedfromOriginitoDestinationj):TransportationModelTODESTINATIONFROMORIGIN1234A120xA1130xA241xA359.50xA4B61xB140xB2100xB3110xB4C102.50xC190xC2122xC342xC4TotalTransportationCost=120xA1+130xA2+41xA3+…+122xC3+42xC4TransportationModelTwogeneraltypesofconstraints.1.Thenumberofitemsshippedfromaharborcannotexceedthenumberofitemsavailable.ForAmsterdam:xA1+xA2+xA3+xA4500ForAntwerp:xB1+xB2+xB3+xB4700ForLeHavre:xC1+xC2+xC3+xC4800Note:Wecouldhaveusedan“=“insteadof““sincesupplyanddemandarebalancedforthismodel.TransportationModel2.Demandateachplantmustbesatisfied.ForLeipzig:xA1+xB1+xC1400ForNancy:xA2+xB2+xC2900ForLiege:xA3+xB3+xC3200Note:Wecouldhaveusedan“=“insteadof““sincesupplyanddemandarebalancedforthismodel.ForTilburg:xA4+xB4+xC4500TransportationModelTwogeneraltypesofconstraints.VariationsontheTransportationModelSupposewenowwanttomaximizethevalueoftheobjectivefunctioninsteadofminimizingit.Inthiscase,wewouldusethesamemodel,butnowtheobjectivefunctioncoefficientsdefinethecontributionmargins(i.e.,unitreturns)insteadofunitcosts.SolvingMaxTransportationModelsWhensupplyanddemandarenotequal,thentheproblemisunbalanced.Therearetwosituations:Whensupplyisgreaterthandemand:WhenSupplyandDemandDifferInthiscase,whenalldemandissatisfied,theremainingsupplythatwasnotallocatedateachoriginwouldappearasslackinthesupplyconstraintforthatorigin.Usinginequalitiesintheconstraints(asinthepreviousexample)wouldnotcauseanyproblems.VariationsontheTransportationModelInthiscase,theLPmodelhasnofeasiblesolution.However,therearetwoapproachestosolvingthisproblem:1.Rewritethesupplyconstraintstobeequalitiesandrewritethedemandconstraintstobe.Unfulfilleddemandwillappearasslackoneachofthedemandconstraintswhenoneoptimizesthemodel.Whendemandisgreaterthansupply:VariationsontheTransportationModel2.Revisethemodeltoappendaplaceholderorigin,calledadummyorigin,withsupplyequaltothedifferencebetweentotaldemandandtotalsupply.Thepurposeofthedummyoriginistomaketheproblembalanced(totalsupply=totaldemand)sothatonecansolveit.Thecostofsupplyinganydestinationfromthisoriginiszero.Oncesolved,anysupplyallocatedfromthisorigintoadestinationisinterpretedasunfilleddemand.VariationsontheTransportationModelCertainroutesinatransportationmodelmaybeunacceptableduetoregionalrestrictions,deliverytime,etc.Inthiscase,youcanassignanarbitrarilylargeunitcostnumber(identifiedasM)tothatroute.Thiswillforceonetoeliminatetheuseofthatroutesincethecostofusingitwouldbemuchlargerthanthatofanyotherfeasiblealternative.EliminatingUnacceptableRoutesChooseMsuchthatitwillbelargerthananyotherunitcostnumberinthemodel.VariationsontheTransportationModelGenerally,LPmodelsdonotproduceintegersolutions.TheexceptiontothisistheTransportationmodel.Ingeneral:IntegerValuedSolutionsIfallofthesuppliesanddemandsinatransportationmodelhaveintegervalues,theoptimalvaluesofthedecisionvariableswillalsohaveintegervalues.VariationsontheTransportationModelAssignmentModelIngeneral,theAssignmentmodelistheproblemofdeterminingtheoptimalassignmentofn“indivisible”agentsorobjectstontasks.Forexample,youmightwanttoassignSalespeopletosalesterritoriesComputerstonetworksConsultantstoclientsServicerepresentativestoservicecallsCommercialartiststoadvertisingcopyTheimportantconstraintisthateachpersonormachinebeassignedtooneandonlyon