TransportationandNetworkModels(英文版知識(shí)講義)

TransportationandNetworkModels(英文版知識(shí)講義)第五講TransportationandNetworkModelsIntroductionSeveralspecificmodels(whichcanbeusedastemplatesforreal-lifeproblems)willbeintroduced.TRANSPORTATIONMODEL

ASSIGNMENTMODEL

NETWORKMODELS

IntroductionTRANSPORTATIONMODEL

ASSIGNMENTMODEL

Determinehowtosendproductsfromvarioussourcestovariousdestinationsinordertosatisfyrequirementsatthelowestpossiblecost.Allocatingfixed-sizedresourcestodeterminetheoptimalassignmentofsalespeopletodistricts,jobstomachines,taskstocomputers…NETWORKMODELS

Involvethemovementorassignmentofphysicalentities(e.g.,money).TransportationModelAnexle,theAutoPowerCompanymakesavarietyofbatteryandmotorizeduninterruptibleelectricpowersupplies(UPS’s).AutoPowerhas4finalassemblyplantsinEuropeandthedieselmotorsusedbytheUPS’sareproducedintheUS,shippedto3harborsandthensenttotheassemblyplants.Productionplansforthethirdquarter(July–Sept.)havebeenset.Therequirements(demandatthedestination)andtheavailablenumberofmotorsatharbors(supplyatorigins)areshownonthenextslide:DemandSupplyAssemblyPlant

No.ofMotorsRequiredLeipzig 400(2)Nancy 900(3)Liege 200(4)Tilburg 500 2000

Harbor

No.ofMotorsAvailable(A)Amsterdam 500(B)Antwerp 700(C)LeHavre 800 2000BalancedGraphicalpresentationofLeHavre(C)800Antwerp(B)700Amsterdam(A)500SupplyLiege(3)200Tilburg(4)500Leipzig(1)400Nancy(2)900andDemand:TransportationModelAutoPowermustdecidehowmanymotorstosendfromeachharbor(supply)toeachplant(demand).Thecost($,onapermotorbasis)ofshippingisgivenbelow.

TODESTINATION

LeipzigNancyLiegeTilburgFROMORIGIN

(1)(2)(3)(4)

(A)Amsterdam 1201304159.50(B)Antwerp6140100110(C)LeHavre102.509012242Thegoalistominimizetotaltransportationcost.Sincethecostsintheprevioustableareonaperunitbasis,wecancalculatetotalcostbasedonthefollowingmatrix(wherexijrepresentsthenumberofunitsthatwillbetransportedfromOriginitoDestinationj):TransportationModel

TODESTINATIONFROMORIGIN

1234

A 120xA1130xA241xA359.50xA4

B 61xB140xB2100xB3110xB4C102.50xC190xC2122xC342xC4TotalTransportationCost=

120xA1+130xA2+41xA3+…+122xC3+42xC4TransportationModelTwogeneraltypesofconstraints.1.Thenumberofitemsshippedfromaharbor

cannotexceedthenumberofitemsavailable.ForAmsterdam:xA1+xA2+xA3+xA4

<500ForAntwerp:xB1+xB2+xB3+xB4

<700ForLeHavre:xC1+xC2+xC3+xC4

<800Note:Wecouldhaveusedan“=“insteadof“<“sincesupplyanddemandarebalancedforthismodel.TransportationModel2.Demandateachplantmustbesatisfied.ForLeipzig:xA1+xB1+xC1

>400ForNancy:xA2+xB2+xC2

>900ForLiege:xA3+xB3+xC3>200Note:Wecouldhaveusedan“=“insteadof“>“sincesupplyanddemandarebalancedforthismodel.ForTilburg:xA4+xB4+xC4>500TransportationModelTwogeneraltypesofconstraints.VariationsontheTransportationModelSupposewenowwanttomaximizethevalueoftheobjectivefunctioninsteadofminimizingit.Inthiscase,wewouldusethesamemodel,butnowtheobjectivefunctioncoefficientsdefinethecontributionmargins(i.e.,unitreturns)insteadofunitcosts.SolvingMaxTransportationModelsWhensupplyanddemandarenotequal,thentheproblemisunbalanced.Therearetwosituations:Whensupplyisgreaterthandemand:WhenSupplyandDemandDifferInthiscase,whenalldemandissatisfied,theremainingsupplythatwasnotallocatedateachoriginwouldappearasslackinthesupplyconstraintforthatorigin.Usinginequalitiesintheconstraints(asinthepreviousexle)wouldnotcauseanyproblems.VariationsontheTransportationModelInthiscase,theLPmodelhasnofeasiblesolution.However,therearetwoapproachestosolvingthisproblem:1.Rewritethesupplyconstraintstobe

equalitiesandrewritethedemand

constraintstobe<.Unfulfilleddemandwillappearasslackoneachofthedemandconstraintswhenoneoptimizesthemodel.Whendemandisgreaterthansupply:VariationsontheTransportationModel2.Revisethemodeltoappendaplaceholder

origin,calledadummyorigin,withsupply

equaltothedifferencebetweentotal

demandandtotalsupply.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.Forexle,youmightwanttoassignSalespeopletosalesterritoriesComputerstonetworksConsultantstoclientsServicerepresentativestoservicecallsCommercialartiststoadvertisingcopyTheimportantconstraintisthateachpersonormachinebeassignedtooneandonlyonetask.WewillusetheAutoPowerexletoillustrateAssignmentproblems.AutoPowerEurope’sAuditingProblemAutoPower’sEuropeanheadquartersisinBrussels.Thisyear,eachofthefourcorporatevice-presidentswillvisitandauditoneoftheassemblyplantsinJune.Theplantsarelocatedin:Leipzig,GermanyLiege,BelgiumNancy,FranceTilburg,theNetherlandsAssignmentModelTheissuestoconsiderinassigningthedifferentvice-presidentstotheplantsare:1.Matchingthevice-presidents’areasof

expertisewiththeimportanceofspecific

problemareasinaplant.2.Thetimethemanagementauditwillrequire

andtheotherdemandsoneachvice-

presidentduringthetwo-weekinterval.3.Matchingthelanguageabilityofavice-

presidentwiththeplant’sdominantlanguage.Keepingtheseissuesinmind,firstestimatethe(opportunity)costtoAutoPowerofsendingeachvice-presidenttoeachplant.AssignmentModelThefollowingtableliststheassignmentcostsin$000sforeveryvice-president/plantcombination.

PLANT

LeipzigNancyLiegeTilburgV.P.(1)(2)(3)(4)

Finance(F) 24102111Marketing(M)14221015Operations(O)15172019Personnel(P)11191413AssignmentModel

PLANT

LeipzigNancyLiegeTilburgV.P.(1)(2)(3)(4)

Finance(F) 24102111Marketing(M)14221015Operations(O)15172019Personnel(P)11191413Considerthefollowingassignment:Totalcost=24+22+20+13=79Thequestionis,isthistheleastcostassignment?AssignmentModelCompleteenumerationisthecalculationofthetotalcostofeachfeasibleassignmentpatterninordertopicktheassignmentwiththelowesttotalcost.SolvingbyCompleteEnumerationThisisnotaproblemwhenthereareonlyafewrowsandcolumns(e.g.,vice-presidentsandplants).However,completeenumerationcanquicklybecomeburdensomeasthemodelgrowslarge.AssignmentModel1.Fcanbeassignedtoanyofthe4plants.2.OnceFisassigned,Mcanbeassignedtoany

oftheremaining3plants.3.NowOcanbeassignedtoanyofthe

remaining2plants.4.Pmustbeassignedtotheonlyremaining

plant.Thereare4x3x2x1=24possiblesolutions.Ingeneral,iftherearenrowsandncolumns,thentherewouldben(n-1)(n-2)(n-3)…(2)(1)=n!

(nfactorial)solutions.Asnincreases,n!increasesrapidly.Therefore,thismaynotbethebestmethod.AssignmentModelForthismodel,let

xij=numberofV.P’softypeiassignedtoplantjwherei=F,M,O,P

j=1,2,3,4TheLPFormulationandSolutionNoticethatthismodelisbalancedsincethetotalnumberofV.P.’sisequaltothetotalnumberofplants.Remember,onlyoneV.P.(supply)isneededateachplant(demand).AssignmentModelAsaresult,theoptimalassignmentis:

PLANT

LeipzigNancyLiegeTilburgV.P.(1)(2)(3)(4)

Finance(F) 24102111Marketing(M)14221015Operations(O)15172019Personnel(P)11191413TotalCost($000’s)=10+10+15+13=48AssignmentModelTheAssignmentmodelissimilartotheTransportationmodelwiththeexceptionthatsupplycannotbedistributedtomorethanonedestination.RelationtotheTransportationModelIntheAssignmentmodel,allsuppliesanddemandsareone,andhenceintegers.Asaresult,eachdecisionvariablecellwilleithercontaina0(noassignment)ora1(assignmentmade).Ingeneral,theassignmentmodelcanbeformulatedasatransportationmodelinwhichthesupplyateachoriginandthedemandateachdestination=1.AssignmentModelCase1:SupplyExceedsDemandUnequalSupplyandDemand:Intheexle,supposethecompanyPresidentdecidesnottoaudittheplantinTilburg.Nowthereare4V.P.’stoassignto3plants.Hereisthecost(in$000s)matrixforthisscenario:

PLANT NUMBEROFV.P.sV.P. 1 2 3 AVAILABLE

F 24 10 21 1

M 14 22 10 1

O 15 17 20 1

P 11 19 14 1No.ofV.P.s 4Required 1 1 1 3

AssignmentModelToformulatethismodel,simplydroptheconstraintthatrequiredaV.P.atplant4andsolveit.AssignmentModelUnequalSupplyandDemand:Case2:DemandExceedsSupplyUnequalSupplyandDemand:Inthisexle,assumethattheV.P.ofPersonnelisunabletoparticipateintheEuropeanaudit.Nowthecostmatrixisasfollows:

PLANT NUMBEROFV.P.sV.P. 1 2 3 4 AVAILABLE

F 24 10 21 11 1

M 14 22 10 15 1

O 15 17 20 19 1No.ofV.P.s 3Required 1 1 1 1 4

AssignmentModel 1.Modifytheinequalitiesintheconstraints

(similartotheTransportationexle) 2.AddadummyV.P.asaplaceholdertothe

costmatrix(shownbelow).

PLANT NUMBEROFV.P.sV.P. 1 2 3 4 AVAILABLE

F 24 10 21 11 1

M 14 22 10 15 1

O 15 17 20 19 1Dummy 0 0 0 0 1No.ofV.P.s 4Required 1 1 1 1 4

ZerocosttoassignthedummyDummysupply;nowsupply=demandAssignmentModelInthesolution,thedummyV.P.wouldbeassignedtoaplant.Inreality,thisplantwouldnotbeaudited.AssignmentModelUnequalSupplyandDemand:InthisAssignmentmodel,theresponsefromeachassignmentisaprofitratherthanacost.MaximizationModelsForexle,AutoPowermustnowassignfournewsalespeopletothreeterritoriesinordertomaximizeprofit.Theeffectofassigninganysalespersontoaterritoryismeasuredbytheanticipatedmarginalincreaseinprofitcontributionduetotheassignment.AssignmentModelHereistheprofitmatrixforthismodel.

NUMBEROF TERRITORY SALESPEOPLE SALESPERSON 1 2 3AVAILABLE

A 40 30 20 1

B 18 28 22 1

C 12 16 20 1

D 25 24 27 1No.of 4

Salespeople 1 1 1 3

Required

ThisvaluerepresentstheprofitcontributionifAisassignedtoTerritory3.AssignmentModelTheAssignmentModelCertainassignmentsinthemodelmaybeunacceptableforvariousreasons.SituationswithUnacceptableAssignmentsInthiscase,youcanassignanarbitrarilylargeunitcost(orsmallunitprofit)numbertothatassignment.ThiswillforceSolvertoeliminatetheuseofthatassignmentsince,forexle,thecostofmakingthatassignmentwouldbemuchlargerthanthatofanyotherfeasiblealternative.AssignmentModelNetworkModelsTransportationandassignmentmodelsaremembersofamoregeneralclassofmodelscallednetworkmodels.Networkmodelsinvolvefrom-tosourcesanddestinations.Appliedtomanagementlogisticsanddistribution,networkmodelsareimportantbecause:Theycanbeappliedtoawidevarietyofrealworldmodels.Flowsmayrepresentphysicalquantities,Internetdatapackets,cash,airplanes,cars,ships,products,…ZigwellInc.isAutoPower’slargestUSdistributorofUPSgeneratorsinfiveMidwesternstates.NetworkModelsACapacitatedTransshipmentModelZigwellhas10BigGen’satsite1Thesegeneratorsmustbedeliveredtoconstructionsitesintwocitiesdenotedand343BigGen’sarerequiredatsiteand7arerequiredatsite34NetworkModels1+102543-3-7Thisisanetworkdiagramornetworkflowdiagram.Eacharrowiscalledanarcorbranch.

Eachsiteistermedanode.SupplyDemandNetworkModelscij thecosts(perunit)oftraversingthe

routesuij thecapacitiesalongtheroutesCostsareprimarilyduetofuel,tolls,andthecostofthedriverfortheaveragetimeittakestotraversethearc.Becauseofpre-establishedagreementswiththeteamsters,Zigwellmustchangedriversateachsiteitencountersonaroute.Becauseoflimitationsonthecurrentavailabilityofdrivers,thereisanupperbound,uij,onthenumberofgeneratorsthatmaytraverseanarc.NetworkModels1+102543-3-7c12c23c24c25c34c43c53u12u23u24u25u34u43u53NetworkModelsLPFormulationoftheModelNetworkModelsACapacitatedTransshipmentModelThegoalistofindashipmentplanthatsatisfiesthedemandsatminimumcost,subjecttothecapacityconstraints.Thecapacitatedtransshipmentmodelisbasicallyidenticaltothetransportationmodelexceptthat:1.Anyplantorwarehousecanshiptoanyother

plantorwarehouse2.Therecanbeupperand/orlowerbounds

(capacities)oneachshipment(branch)NetworkModelsThedecisionvariablesare:xij=totalnumberofBigGen’ssentonarc(i,j)=flowfromnodeitonodejThemodelbecomes:Minc12x12+c23x23+c24x24+c25x25+c34x34+

c43x43+c53x53+c54x54s.t.+x12=10-x12+x23+x24+x25=0-x23–x43–x53+x34=-3-x24+x43–x34–x54=-7-x25+x53+x54=00<

xij<uijallarcs(i,j)inthenetworkPropertiesoftheModel1.xijisassociatedwitheachofthe8arcsinthe

network.Therefore,thereare8corresponding

variables:x12,x23,x24,x25,x34,x43,x53,andx54Theobjectiveistominimizetotalcost.2.Thereisonematerialflowbalanceequation

associatedwitheachnodeinthenetwork.For

exle:Totalflowoutofnodeis10units1Totalflowoutofnodeminusthetotalflowintonodeiszero(i.e.,totalflowoutmustequaltotalflowintonode).222Totalflowoutofnodemustbe3unitslessthanthetotalflowintonode.33Intermediatenodesthatareneithersupplypointsnordemandpointsareoftentermedtransshipmentnodes.3.Thepositiveright-handsidescorrespondto

nodesthatarenetsuppliers(origins).Thesumofallright-hand-sidetermsiszero(i.e.,totalsupplyinthenetworkequalstotaldemand).Thezeroright-handsidescorrespondtonodesthathaveneithersupplynordemand.Thenegativeright-handsidescorrespondtonodesthatarenetdestinations.Ingeneral,flowbalanceforagivennode,j,is:Totalflowoutofnodej–totalflowintonodej=supplyatnodejNegativesupplyisarequirement.Nodeswithnegativesupplyarecalleddestinations,

sinks,

or

demandpoints.Nodeswithpositivesupplyarecalledorigins,sources,orsupplypoints.Nodeswithzerosupplyarecalledtransshipmentpoints.4.AsmallmodelcanbeoptimizedwithSolver.IntegerOptimalSolutionsNetworkModelsACapacitatedTransshipmentModelTheintegerpropertyofthenetworkmodelcanbestatedthus:IfalltheRHStermsandarccapacities,uij,areintegersinthecapacitatedtransshipmentmodel,therewillalwaysbeaninteger-valuedoptimalsolutiontothismodel.NetworkModelsThestructureofthismodelmakesitpossibletoapplyspecialsolutionmethodsandsoftwarethatoptimizethemodelmuchmorequicklythanthemoregeneralsimplexmethodusedbySolver.EfficientSolutionProceduresNetworkModelsACapacitatedTransshipmentModelThismakesitpossibletooptimizeverylargescalenetworkmodelsquicklyandcheaply.NetworkModelsTheshortest-routemodelreferstoanetworkforwhicheacharc(i,j)hasanassociatednumber,cij,whichisinterpretedasthedistance(orcost,ortime)fromnodeitonodej.NetworkModelsAShortest-RouteModelArouteorpathbetweentwonodesisanysequenceofarcsconnectingthetwonodes.Theobjectiveistofindtheshortest(orleast-costorleast-time)routesfromaspecificnodetoeachoftheothernodesinthenetwork.NetworkModelsInthisexle,AaronDrunnermakesfrequentwinedeliveriesto7differentsites:874H12347651611213323Notethatthearcsareundirected(flowispermittedineitherdirection).Distancebetweennodes.HomeBaseThegoalistominimizeoverallcostsbymakingsurethatanyfuturedeliverytoanygivensiteismadealongtheshortestroutetothatsite.ThegoalistominimizeoverallcostsbyfindingtheshortestroutefromnodeHtoanyoftheother7nodes.Notethatinthismodel,thetaskistofindanoptimalroute,notoptimalxij’s.NetworkModelsInthisexle,MichaelCarrisresponsibleforobtainingahighspeedprintingpressforhisnewspapercompany.NetworkModelsAnEquipmentReplacementModelInagivenyearhemustchoosebetweenpurchasing:NewPrintingPressOldPrintingPresshighannual

acquisitioncostlowinitial

maintenancecostnoannual

acquisitioncosthighinitial

maintenancecostNetworkModelsAssumea4-yeartimehorizon.Let:cijdenotethecostofbuyingnewequipment

atthebeginningofyeari,i=1,2,3,4

andmaintainingittothebeginningofyear

j,j=2,3,4,5Threealternativefeasiblepoliciesare:1.Buyingnewequipmentatthebeginningof

eachyear.Total(acquisition+mainten