Chapter7-NetworkFlowModels1Chapter7NetworkFlowModelsIntroductiontoManagementScience8thEditionbyBernardW.TaylorIIIChapter7-NetworkFlowModels2ChapterTopicsTheMinimumCostNetworkFlowProblemTheShortestRouteProblemTheMinimalSpanningTreeProblemTheMaximalFlowProblemChapter7-NetworkFlowModels3OverviewAnetworkisanarrangementofpathsconnectedatvariouspointsthroughwhichoneormoreitemsmovefromonepointtoanother.Thenetworkisdrawnasadiagramprovidingapictureofthesystemthusenablingvisualinterpretationandenhancedunderstanding.Alargenumberofreal-lifesystemscanbemodeledasnetworkswhicharerelativelyeasytoconceiveandconstruct.Chapter7-NetworkFlowModels4Networkdiagramsconsistofnodesandbranches.Nodes(circles),representjunctionpoints,orlocations.Branches(lines,Arcs),connectnodesandrepresentflow.Paths,asetofbranchesconnectingtwonodesNetworkComponents(1of3)Chapter7-NetworkFlowModels5Figure7.1NetworkofRailroadRoutesFournodes,fourbranchesinfigure.“Atlanta”,node1,termedorigin,anyofothersdestination.Branchesidentifiedbybeginningandendingnodenumbers.Valueassignedtoeachbranch(distance,time,cost,etc.).NetworkComponents(2of3)Chapter7-NetworkFlowModels6NetworkConcepts(3/3)Flow:thequantityroutingthroughabranchCapacity:themaxflowonabranchperunittimeSourcenode(Originnode)Destinationnode(Sinknode)Supplynode:flowinflowoutTransshipmentnode:flowin=flowoutChapter7-NetworkFlowModels7Problem:Determinetheshortestroutesfromtheorigintoalldestinations.Figure7.2ShippingRoutesfromLosAngelesTheShortestRouteProblemDefinitionandExampleProblemData(1of2)Chapter7-NetworkFlowModels8Figure7.3NetworkofShippingRoutesTheShortestRouteProblemDefinitionandExampleProblemData(2of2)Chapter7-NetworkFlowModels9Figure7.4NetworkwithNode1inthePermanentSetTheShortestRouteProblemSolutionApproach(1of8)Determinetheinitialshortestroutefromtheorigin(node1)totheclosestnode(3).Chapter7-NetworkFlowModels10Figure7.5NetworkwithNodes1and3inthePermanentSetTheShortestRouteProblemSolutionApproach(2of8)Determineallnodesdirectlyconnectedtothepermanentset.Chapter7-NetworkFlowModels11Figure7.6NetworkwithNodes1,2,and3inthePermanentSetRedefinethepermanentset.TheShortestRouteProblemSolutionApproach(3of8)Chapter7-NetworkFlowModels12Figure7.7NetworkwithNodes1,2,3,and4inthePermanentSetTheShortestRouteProblemSolutionApproach(4of8)ContinueChapter7-NetworkFlowModels13TheShortestRouteProblemSolutionApproach(5of8)Figure7.8NetworkwithNodes1,2,3,4,and6inthePermanentSetContinueChapter7-NetworkFlowModels14TheShortestRouteProblemSolutionApproach(6of8)Figure7.9NetworkwithNodes1,2,3,4,5,and6inthePermanentSetContinueChapter7-NetworkFlowModels15TheShortestRouteProblemSolutionApproach(7of8)Figure7.10NetworkwithOptimalRoutesfromLosAngelestoAllDestinationsOptimalSolutionChapter7-NetworkFlowModels16Table7.1ShortestTravelTimefromOrigintoEachDestinationTheShortestRouteProblemSolutionApproach(8of8)SolutionSummaryChapter7-NetworkFlowModels17TheShortestRouteProblemSolutionMethodSummarySelectthenodewiththeshortestdirectroutefromtheorigin.Establishapermanentsetwiththeoriginnodeandthenodethatwasselectedinstep1.Determineallnodesdirectlyconnectedtothepermanentsetnodes.Selectthenodewiththeshortestroute(branch)fromthegroupofnodesdirectlyconnectedtothepermanentsetnodes.Repeatsteps3and4untilallnodeshavejoinedthepermanentset.Chapter7-NetworkFlowModels18TheShortestRouteProblem...
