供應(yīng)鏈運(yùn)籌學(xué)管理含義英文

第五講TransportationandNetworkModelsIntroductionSeveralspecificmodels(whichcanbeusedastemplatesforreal-lifeproblems)willbeintroduced.TRANSPORTATIONMODEL

ASSIGNMENTMODEL

NETWORKMODELS

IntroductionTRANSPORTATIONMODEL

ASSIGNMENTMODEL

Determinehowtosendproductsfromvarioussourcestovariousdestinationsinordertosatisfyrequirementsatthelowestpossiblecost.Allocatingfixed-sizedresourcestodeterminetheoptimalassignmentofsalespeopletodistricts,jobstomachines,taskstocomputers…NETWORKMODELS

Involvethemovementorassignmentofphysicalentities(e.g.,money).

TransportationModelAnexample,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)Antwerp

6140100110(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(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,youmightwanttoassignSalespeopletosalesterritoriesComputerstonetworksConsultantstoclientsServicerepresentativestoservicecallsCommercialartiststoadvertisingcopyTheimportantconstraintisthateachpersonormachinebeassignedtooneandonlyonetask.WewillusetheAutoPowerexampletoillustrateAssignmentproblems.AutoPowerEurope’sAuditingProblemAutoPower’sEuropeanheadquartersisinBrussels.Thisyear,eachofthefourcorporatevice-presidentswillvisitandauditoneoftheassemblyplantsinJune.Theplantsarelocatedin:Leipzig,GermanyLiege,BelgiumNancy,FranceTilburg,theNetherlandsAssignmentModelTheissuestoconsiderinassigningthedifferentvice-presidentstotheplantsare:1.Matchingthevice-presidents’areasofexpertisewiththeimportanceofspecificproblemareasinaplant.2.Thetimethemanagementauditwillrequireandtheotherdemandsoneachvice-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,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.AssignmentModelForthismodel,letxij=numberofV.P’’softypeiassignedtoplantjwherei=F,M,O,Pj=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:Intheexample,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:Inthisexample,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

AssignmentModel1.Modifytheinequalitiesintheconstraints(similartotheTransportationexample)2.AddadummyV.P.asaplaceholdertothecostmatrix(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.MaximizationModelsForexample,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,forexample,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.SupplyDemandNetworkModelscijthecosts(perunit)oftraversingtheroutesuijthecapacitiesalongtheroutesCostsareprimarilyduetofuel,tolls,andthecostofthedriverfortheaveragetimeittakestotraversethearc.Becauseofpre-establishedagreementswiththeteamsters,Zigwellmustchangedriversateachsiteitencountersonaroute.Becauseoflimitationsonthecurrentavailabilityofdrivers,thereisanupperbound,uij,onthenumberofgeneratorsthatmaytraverseanarc.NetworkModels1+102543-3-7c12c23c24c25c34c43c53u12u23u24u25u34u43u53NetworkModelsLPFormulationoftheModelNetworkModelsACapacitatedTransshipmentModelThegoalistofindashipmentplanthatsatisfiesthedemandsatminimumcost,subjecttothecapacityconstraints.Thecapacitatedtransshipmentmodelisbasicallyidenticaltothetransportationmodelexceptthat:1.Anyplantorwarehousecanshiptoanyotherplantorwarehouse2.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.xijisassociatedwitheachofthe8arcsinthenetwork.Therefore,thereare8correspondingvariables:x12,x23,x24,x25,x34,x43,x53,andx54Theobjectiveistominimizetotalcost.2.Thereisonematerialflowbalanceequationassociatedwitheachnodeinthenetwork.Forexample:Totalflowoutofnodeis10units1Totalflowoutofnodeminusthetotalflowintonodeiszero(i.e.,totalflowoutmustequaltotalflowintonode).222Totalflowoutofnodemustbe3unitslessthanthetotalflowintonode.33Intermediatenodesthatareneithersupplypointsnordemandpointsareoftentermedtransshipmentnodes.3.Thepositiveright-handsidescorrespondtonodesthatarenetsuppliers(origins).Thesumofallright-hand-sidetermsiszero(i.e.,totalsupplyinthenetworkequalstotaldemand).Thezeroright-handsidescorrespondtonodesthathaveneithersupplynordemand.Thenegativeright-handsidescorrespondtonodesthatarenetdestinations.Ingeneral,flowbalanceforagivennode,j,is:Totalflowoutofnodej–totalflowintonodej=supplyatnodejNegativesupplyisarequirement.Nodeswithnegativesupplyarecalleddestinations,sinks,ordemandpoints.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.NetworkModelsInthisexample,AaronDrunnermakesfrequentwinedeliveriesto7differentsites:874H12347651611213323Notethatthearcsareundirected(flowispermittedineitherdirection).Distancebetweennodes.HomeBaseThegoalistominimizeoverallcostsbymakingsurethatanyfuturedeliverytoanygivensiteismadealongtheshortestroutetothatsite.ThegoalistominimizeoverallcostsbyfindingtheshortestroutefromnodeHtoanyoftheother7nodes.Notethatinthismodel,thetaskistofindanoptimalroute,notoptimalxij’s.NetworkModelsInthisexample,MichaelCarrisresponsibleforobtainingahighspeedprintingpressforhisnewspapercompany.NetworkModelsAnEquipmentReplacementModelInagivenyearhemustchoosebetweenpurchasing:NewPrintingPressOldPrintingPresshighannualacquisitioncostlowinitialmaintenancecostnoannualacquisitioncosthighinitialmaintenancecostNetworkModelsAssumea4-yeartimehorizon.Let:cijdenotethecostofbuyingnewequipmentatthebeginningofyeari,i=1,2,3,4andmaintainingittothebegi