数据、模型与决策（第12版）课件 第7章网络模型

NetworkFlowModelsChapter7Copyright©2016PearsonEducation,Inc.ChapterTopicsNetworkComponentsTheShortestRouteProblemTheMinimalSpanningTreeProblemTheMaximalFlowProblemCopyright©2016PearsonEducation,Inc.NetworkComponents(1of3)Anetworkisanarrangementofpaths(branches)connectedatvariouspoints(nodes)throughwhichoneormoreitemsmovefromonepointtoanother.Thenetworkisdrawnasadiagramprovidingapictureofthesystem,thusenablingvisualrepresentationandenhancedunderstanding.Alargenumberofreal-lifesystemscanbemodeledasnetworkswhicharerelativelyeasytoconceiveandconstruct.Copyright©2016PearsonEducation,Inc.Networkdiagramsconsistofnodesandbranches.Nodes

(circles),representjunctionpoints,orlocations.Branches(lines),connectnodesandrepresentflow.NetworkComponents(2of3)Copyright©2016PearsonEducation,Inc.Figure7.1NetworkofrailroadroutesFournodes,fourbranchesinfigure.“Atlanta”,node1,termedtheorigin;anyofothers,destination.Branchesidentifiedbybeginningandendingnodenumbers.Valueassignedtoeachbranch(distance,time,cost,etc.).NetworkComponents(3of3)Copyright©2016PearsonEducation,Inc.Problem:Determinetheshortestroutesfromtheorigintoalldestinations.Figure7.2ShippingroutesfromLosAngelesTheShortestRouteProblemDefinitionandExampleProblemData(1of2)Copyright©2016PearsonEducation,Inc.Figure7.3NetworkrepresentationofshortestrouteproblemTheShortestRouteProblemDefinitionandExampleProblemData(2of2)Copyright©2016PearsonEducation,Inc.Figure7.4Networkwithnode1inthepermanentsetTheShortestRouteProblemSolutionApproach(1of8)Determinetheinitialshortestroutefromtheorigin(node1)totheclosestnode(3).Thepermanentsetindicatesthenodesforwhichtheshortestroutetohasbeenfound.Copyright©2016PearsonEducation,Inc.Figure7.5Networkwithnodes1and3inthepermanentsetTheShortestRouteProblemSolutionApproach(2of8)Determineallnodesdirectlyconnectedtothepermanentset.Copyright©2016PearsonEducation,Inc.Figure7.6Networkwithnodes1,2,and3inthepermanentsetRedefinethepermanentset.TheShortestRouteProblemSolutionApproach(3of8)Copyright©2016PearsonEducation,Inc.Figure7.7Networkwithnodes1,2,3,and4inthepermanentsetTheShortestRouteProblemSolutionApproach(4of8)Copyright©2016PearsonEducation,Inc.TheShortestRouteProblemSolutionApproach(5of8)Figure7.8NetworkwithNodes1,2,3,4,&6inthepermanentsetCopyright©2016PearsonEducation,Inc.TheShortestRouteProblemSolutionApproach(6of8)Figure7.9Networkwithnodes1,2,3,4,5&6inthepermanentsetCopyright©2016PearsonEducation,Inc.TheShortestRouteProblemSolutionApproach(7of8)Figure7.10NetworkwithoptimalroutesfromLAtoalldestinationsCopyright©2016PearsonEducation,Inc.TheShortestRouteProblemSolutionApproach(8of8)Table7.1ShortesttraveltimefromorigintoeachdestinationCopyright©2016PearsonEducation,Inc.TheShortestRouteProblemSolutionMethodSummarySelectthenodewiththeshortestdirectroutefromtheorigin.Establishapermanentsetwiththeoriginnodeandthenodethatwasselectedinstep1.Determineallnodesdirectlyconnectedtothepermanentsetnodes.Selectthenodewiththeshortestroutefromthegroupofnodesdirectlyconnectedtothepermanentsetnodes.Repeatsteps3&4untilallnodeshavejoinedthepermanentset.Copyright©2016PearsonEducation,Inc.TheShortestRouteProblemComputerSolutionwithQMforWindows(1of2)Exhibit7.1Copyright©2016PearsonEducation,Inc.TheShortestRouteProblemComputerSolutionwithQMforWindows(2of2)Exhibit7.2DestinationnodeDistancetonode5,DesMoinesCopyright©2016PearsonEducation,Inc.Formulationasa0-1integerlinearprogrammingproblem.xij=0ifbranchi-jisnotselectedaspartoftheshortestrouteand1ifitisselected.MinimizeZ=16x12+9x13+35x14+12x24+25x25+15x34+ 22x36+14x45+17x46+19x47+8x57+14x67subjectto: x12+x13+x14=1 x12-x24-x25=0 x13-x34-x36=0x14+x24+x34-x45-x46-x47=0 x25+x45-x57=0 x36+x46-x67=0 x47+x57+x67=1 xij=0or1

TheShortestRouteProblemComputerSolutionwithExcel(1of4)Copyright©2016PearsonEducation,Inc.Exhibit7.3TheShortestRouteProblemComputerSolutionwithExcel(2of4)TotalhoursFirstconstraint;=A6+A7+A8Constraintfornode2;=A6-A9-A10DecisionvariablesCopyright©2016PearsonEducation,Inc.Exhibit7.4TheShortestRouteProblemComputerSolutionwithExcel(3of4)Onetruckleavesnode1,andonetruckendsatnode7FlowconstraintsCopyright©2016PearsonEducation,Inc.Exhibit7.5TheShortestRouteProblemComputerSolutionwithExcel(4of4)Onetruckflowsoutofnode1;onetruckflowsintonode7Copyright©2016PearsonEducation,Inc.Figure7.11NetworkofpossiblecableTVpathsTheMinimalSpanningTreeProblemDefinitionandExampleProblemData Problem:Connectallnodesinanetworksothatthetotalofthebranchlengthsareminimized.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(1of6)Figure7.12Spanningtreewithnodes1and3 Startwithanynodeinthenetworkandselecttheclosestnodetojointhespanningtree.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(2of6)Figure7.13Spanningtreewithnodes1,3,and4Selecttheclosestnodenotpresentlyinthespanningarea.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(3of6)Figure7.14Spanningtreewithnodes1,2,3,and4Continuetoselecttheclosestnodenotpresentlyinthespanningarea.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(4of6)Figure7.15Spanningtreewithnodes1,2,3,4,and5Continuetoselecttheclosestnodenotpresentlyinthespanningarea.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(5of6)Figure7.16Spanningtreewithnodes1,2,3,4,5,and7Continuetoselecttheclosestnodenotpresentlyinthespanningarea.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionApproach(6of6)Figure7.17MinimalspanningtreeforcableTVnetworkOptimalSolutionCopyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemSolutionMethodSummarySelectanystartingnode(conventionally,node1).Selectthenodeclosesttothestartingnodetojointhespanningtree.Selecttheclosestnodenotcurrentlyinthespanningtree.Repeatstep3untilallnodeshavejoinedthespanningtree.Copyright©2016PearsonEducation,Inc.TheMinimalSpanningTreeProblemComputerSolutionwithQMforWindowsExhibit7.6Copyright©2016PearsonEducation,Inc.Figure7.18NetworkofrailwaysystemTheMaximalFlowProblemDefinitionandExampleProblemData Problem:Maximizetheamountofflowofitemsfromanorigintoadestination.Copyright©2016PearsonEducation,Inc.Figure7.19Maximalflowforpath1-2-5-6TheMaximalFlowProblemSolutionApproach(1of5)Step1:Arbitrarilychooseanypaththroughthenetworkfromorigintodestinationandshipasmuchaspossible.Copyright©2016PearsonEducation,Inc.Figure7.20Maximalflowforpath1-4-6TheMaximalFlowProblemSolutionApproach(2of5)Step2:Re-computebranchflowinbothdirectionsStep3:Selectotherfeasiblepathsarbitrarilyanddeterminemaximumflowalongthepathsuntilflowisnolongerpossible.Copyright©2016PearsonEducation,Inc.Figure7.21Maximalflowforpath1-3-6TheMaximalFlowProblemSolutionApproach(3of5)Continue0Copyright©2016PearsonEducation,Inc.Figure7.22Maximalflowforpath1-3-4-6TheMaximalFlowProblemSolutionApproach(4of5)ContinueCopyright©2016PearsonEducation,Inc.Figure7.23MaximalflowforrailwaynetworkTheMaximalFlowProblemSolutionApproach(5of5)OptimalSolutionCopyright©2016PearsonEducation,Inc.TheMaximalFlowProblemSolutionMethodSummaryArbitrarilyselectanypathinthenetworkfromtheorigintothedestination.Adjustthecapacitiesateachnodebysubtractingthemaximalflowforthepathselectedinstep1.Addthemaximalflowalongthepathtotheflowintheoppositedirectionateachnode.Repeatsteps1,2,and3untiltherearenomorepathswithavailableflowcapacity.Copyright©2016PearsonEducation,Inc.TheMaximalFlowProblemComputerSolutionwithQMforWindowsExhibit7.7Copyright©2016PearsonEducation,Inc.xij=flowalongbranchi-jandintegerMaximizeZ=x61subjectto: x61-x12-x13-x14=0 x12-x24-x25=0 x13-x34-x36=0 x14+x24+x34-x46=0 x25-x56=0 x36+x46+x56-x61=0 x12

6 x24

3 x34

2 x13

7 x25

8 x36

6 x14

4 x46

5 x56

4 x61

17 xij

0 andintegerTheMaximalFlowProblemComputerSolutionwithExcel(1of4)Copyright©2016PearsonEducation,Inc.TheMaximalFlowProblemComputerSolutionwithExcel(2of4)Exhibit7.8Objective-maximizeflowfromnode6Constraintatnode1;=C15-C6-C7-C8Constraintatnode6;=C12+C13+C14-C15DecisionvariablesCopyright©2016PearsonEducation,Inc.TheMaximalFlowProblemComputerSolutionwithExcel(3of4)Exhibit7.9Copyright©2016PearsonEducation,Inc.TheMaximalFlowProblemComputerSolutionwithExcel(4of4)Exhibit7.10Copyright©2016PearsonEducation,Inc.TheMaximalFlowProblemExampleProblemStatementandDataDeterminetheshortestroutefromAtlanta(node1)toeachoftheotherfivenodes(branchesshowtraveltimebetweennodes).Assumingthebranchesshowdistance(insteadoftraveltime)betweenthenodes,developaminimalspanningtree.Copyright©2016PearsonEducation,Inc.Step1(partA):DeterminetheShortestRouteSolution1. PermanentSet Branch