数据、模型与决策(运筹学)课后习题和案例答案007

PAGE

32

7-

PAGE

32

Chapter7

NetworkOptimizationProblems

ReviewQuestions

7.1-1 Asupplynodeisanodewherethenetamountofflowgeneratedisafixedpositivenumber.Ademandnodeisanodewherethenetamountofflowgeneratedisafixednegativenumber.Atransshipmentnodeisanodewherethenetamountofflowgeneratedisfixedatzero.

7.1-2 Themaximumamountofflowallowedthroughanarcisreferredtoasthecapacityofthatarc.

7.1-3 Theobjectiveistominimizethetotalcostofsendingtheavailablesupplythroughthenetworktosatisfythegivendemand.

7.1-4 Thefeasiblesolutionspropertyisnecessary.Itstatesthataminimumcostflowproblemwillhaveafeasiblesolutionifandonlyifthesumofthesuppliesfromitssupplynodesequalsthesumofthedemandsatitsdemandnodes.

7.1-5 Aslongasallitssuppliesanddemandshaveintegervalues,anyminimumcostflowproblemwithfeasiblesolutionsisguaranteedtohaveanoptimalsolutionwithintegervaluesforallitsflowquantities.

7.1-6 Networksimplexmethod.

7.1-7 Applicationsofminimumcostflowproblemsincludeoperationofadistributionnetwork,solidwastemanagement,operationofasupplynetwork,coordinatingproductmixesatplants,andcashflowmanagement.

7.1-8 Transportationproblems,assignmentproblems,transshipmentproblems,maximumflowproblems,andshortestpathproblemsarespecialtypesofminimumcostflowproblems.

7.2-1 Oneofthecompany’smostimportantdistributioncenters(LosAngeles)urgentlyneedsanincreasedflowofshipmentsfromthecompany.

7.2-2 Autoreplacementpartsareflowingthroughthenetworkfromthecompany’smainfactoryinEuropetoitsdistributioncenterinLA.

7.2-3 TheobjectiveistomaximizetheflowofreplacementpartsfromthefactorytotheLAdistributioncenter.

7.3-1 Ratherthanminimizingthecostoftheflow,theobjectiveistofindaflowplanthatmaximizestheamountflowingthroughthenetworkfromthesourcetothesink.

7.3-2 Thesourceisthenodeatwhichallflowthroughthenetworkoriginates.Thesinkisthenodeatwhichallflowthroughthenetworkterminates.Atthesource,allarcspointawayfromthenode.Atthesink,allarcspointintothenode.

7.3-3 Theamountismeasuredbyeithertheamountleavingthesourceortheamountenteringthesink.

7.3-4 1.Whereassupplynodeshavefixedsuppliesanddemandnodeshavefixeddemands,thesourceandsinkdonot.

2.Whereasthenumberofsupplynodesandthenumberofdemandnodesinaminimumcostflowproblemmaybemorethanone,therecanbeonlyonesourceandonlyonesinkinastandardmaximumflowproblem.

7.3-5 Applicationsofmaximumflowproblemsincludemaximizingtheflowthroughadistributionnetwork,maximizingtheflowthroughasupplynetwork,maximizingtheflowofoilthroughasystemofpipelines,maximizingtheflowofwaterthroughasystemofaqueducts,andmaximizingtheflowofvehiclesthroughatransportationnetwork.

7.4-1 Theoriginisthefirestationandthedestinationisthefarmcommunity.

7.4-2 Flowcangoineitherdirectionbetweenthenodesconnectedbylinksasopposedtoonlyonedirectionwithanarc.

7.4-3 Theoriginnowistheonesupplynode,withasupplyofone.Thedestinationnowistheonedemandnode,withademandofone.

7.4-4 Thelengthofalinkcanmeasuredistance,cost,ortime.

7.4-5 Sarahwantstominimizehertotalcostofpurchasing,operating,andmaintainingthecarsoverherfouryearsofcollege.

7.4-6 When“realtravel”throughanetworkcanendatmorethatonenode,adummydestinationneedstobeaddedsothatthenetworkwillhavejustasingledestination.

7.4-7 Quick’smanagementmustconsidertrade-offsbetweentimeandcostinmakingitsfinaldecision.

7.5-1 Thenodesaregiven,butthelinksneedtobedesigned.

7.5-2 Astate-of-the-artfiber-opticnetworkisbeingdesigned.

7.5-3 Atreeisanetworkthatdoesnothaveanypathsthatbeginandendatthesamenodewithoutbacktracking.Aspanningtreeisatreethatprovidesapathbetweeneverypairofnodes.Aminimumspanningtreeisthespanningtreethatminimizestotalcost.

7.5-4 Thenumberoflinksinaspanningtreealwaysisonelessthanthenumberofnodes.Furthermore,eachnodeisdirectlyconnectedbyasinglelinktoatleastoneothernode.

7.5-5 Todesignanetworksothatthereisapathbetweeneverypairofnodesattheminimumpossiblecost.

7.5-6 No,itisnotaspecialtypeofaminimumcostflowproblem.

7.5-7 Agreedyalgorithmwillsolveaminimumspanningtreeproblem.

7.5-8 Applicationsofminimumspanningtreeproblemsincludedesignoftelecommunicationnetworks,designofalightlyusedtransportationnetwork,designofanetworkofhigh-voltagepowerlines,designofanetworkofwiringonelectricalequipment,anddesignofanetworkofpipelines.

Problems

7.1 a)

b)

c)

7.2 a)

b)

c)

7.3 a)

b)

c)

7.4 a)

b)

c) Thetotalshippingcostis$2,187,000.

7.5 a)

b)

c)

d)

e)

f) $1,618,000+$583,000=$2,201,000whichishigherthanthetotalinProblem7.5($2,187,000).

7.6

ThereareonlytwoarcsintoLA,withacombinedcapacityof150(80+70).Becauseofthisbottleneck,itisnotpossibletoshipanymorethan150fromSTtoLA.Since150actuallyarebeingshippedinthissolution,itmustbeoptimal.

7.7

7.8 a)

b)

7.9 a)

b)

c)

d)

7.10

Shortestpath:FireStation–C–E–F–FarmingCommunity

7.11 a)

b)

c) Shortestroute:Origin–A–B–D–Destination

d) Yes

e) Yes

7.12 a)

b)

7.13 a) Timesplaytheroleofdistances.

b)

7.14

1. CD:Cost=1 4. EG:Cost=5

EF:Cost=1 *choosearbitrarily DA:Cost=4

2. EG:Cost=5 EB:Cost=7

EB:Cost=7 FG:Cost=7

EC:Cost=4 CA:Cost=5

FG:Cost=7 CB:Cost=2 *lowest

FC:Cost=3 *lowest 5. EG:Cost=5

FD:Cost=4 DA:Cost=4

3. EG:Cost=5 BA:Cost=2 *lowest

EB:Cost=7 FG:Cost=7

FG:Cost=7 CA:Cost=5

FD:Cost=4 6. EG:Cost=5 *lowest

CD:Cost=1 *lowest FG:Cost=7

CA:Cost=5

CB:Cost=2 Total=$14million

7.15

1. BC:Cost=1 *lowest 4. BE:Cost=7

2. BA:Cost=4 CF:Cost=4 *lowest

BE:Cost=7 CE:Cost=5

CA:Cost=6 DF:Cost=5

CD:Cost=2 *lowest 5. BE:Cost=7

CF:Cost=4 CE:Cost=5

CE:Cost=5 FE:Cost=1 *lowest

3. BA:Cost=4 *lowest FG:Cost=8

BE:Cost=7 6. EG:Cost=6 *lowest

CA:Cost=6 FG:Cost=8

CF:Cost=4

CE:Cost=5

DA:Cost=5 Total=$18,000

DF:Cost=5

7.16

1. FG:Cost=1 *lowest 6. DA:Cost=6

2. FC:Cost=6 DB:Cost=5

FD:Cost=5 DC:Cost=4

FI:Cost=2 *lowest EB:Cost=3 *lowest

FJ:Cost=5 FC:Cost=6

GD:Cost=2 FJ:Cost=5

GE:Cost=2 HK:Cost=7

GH:Cost=2 IK:Cost=8

GI:Cost=5 IJ:Cost=3

3. FC:Cost=6 7. BA:Cost=4

FD:Cost=5 DA:Cost=6

FJ:Cost=5 DC:Cost=4

GD:Cost=2 *lowest FC:Cost=6

GE:Cost=2 FJ:Cost=5

GH:Cost=2 HK:Cost=7

IH:Cost=2 IK:Cost=8

IK:Cost=8 IJ:Cost=3 *lowest

IJ:Cost=3 8. BA:Cost=4 *lowest

4. DA:Cost=6 DA:Cost=6

DB:Cost=5 DC:Cost=4

DE:Cost=2 *lowest FC:Cost=6

DC:Cost=4 HK:Cost=7

FC:Cost=6 IK:Cost=8

FJ:Cost=5 JK:Cost=4

GE:Cost=2 9. AC:Cost=3 *lowest

GH:Cost=2 DC:Cost=4

IH:Cost=2 FC:Cost=6

IK:Cost=8 HK:Cost=7

IJ:Cost=3 IK:Cost=8

5. DA:Cost=6 JK:Cost=4

DB:Cost=5 10. HK:Cost=7

DC:Cost=4 IK:Cost=8

EB:Cost=3 JK:Cost=4 *lowest

EH:Cost=4

FC:Cost=6

FJ:Cost=5

GH:Cost=2 *lowest Total=$26million

IH:Cost=2

IK:Cost=8

IJ:Cost=3

7.17 a) Thecompanywantsapathbetweeneachpairofnodes(groves)thatminimizescost(lengthofroad).

b) 78:Distance=0.5

76:Distance=0.6

65:Distance=0.9

51:Distance=0.7

54:Distance=0.7

83:Distance=1.0

32:Distance=0.9

Total=5.3miles

7.18 a) Thebankwantsapathbetweeneachpairofnodes(offices)thatminimizescost(distance).

b) B1B5:Distance=50

B5B3:Distance=80

B1B2:Distance=100

B2M:Distance=70

B2B4:Distance=120

Total=420miles

Cases

7.1 a) ThenetworkshowingthedifferentroutestroopsandsuppliesmayfollowtoreachtheRussianFederationappearsbelow.

b) ThePresidentisonlyconcernedabouthowtomostquicklymovetroopsandsuppliesfromtheUnitedStatestothethreestrategicRussiancities.Obviously,thebestwaytoachievethisgoalistofindthefastestconnectionbetweentheUSandthethreecities.WethereforeneedtofindtheshortestpathbetweentheUScitiesandeachofthethreeRussiancities.

ThePresidentonlycaresaboutthetimeittakestogetthetroopsandsuppliestoRussia.Itdoesnotmatterhowgreatadistancethetroopsandsuppliescover.Thereforewedefinethearclengthbetweentwonodesinthenetworktobethetimeittakestotravelbetweentherespectivecities.Forexample,thedistancebetweenBostonandLondonequals6,200km.ThemodeoftransportationbetweenthecitiesisaStarliftertravelingataspeedof400milesperhour*1.609kmpermile=643.6kmperhour.ThetimeistakestobringtroopsandsuppliesfromBostontoLondonequals6,200km/643.6kmperhour=9.6333hours.Usingthisapproachwecancomputethetimeoftravelalongallarcsinthenetwork.

Bysimpleinspectionandcommonsenseitisapparentthatthefastesttransportationinvolvesusingonlyairplanes.Wethereforecanrestrictourselvestoonlythosearcsinthenetworkwherethemodeoftransportationisairtravel.Wecanomitthethreeportcitiesandallarcsenteringandleavingthesenodes.

ThefollowingsixspreadsheetsfindtheshortestpathbetweeneachUScity(BostonandJacksonville)andeachRussiancity(St.Petersburg,Moscow,andRostov).

BostontoSt.Petersburg:

BostontoMoscow:

BostontoRostov:

JacksonvilletoSt.Petersburg:

JacksonvilletoMoscow:

JacksonvilletoRostov:

Thespreadsheetscontainthefollowingformulas:

ComparingallsixsolutionsweseethattheshortestpathfromtheUStoSaintPetersburgisBostonLondonSaintPetersburgwithatotaltraveltimeof12.71hours.TheshortestpathfromtheUStoMoscowisBostonLondonMoscowwithatotaltraveltimeof13.21hours.TheshortestpathfromtheUStoRostovisBostonBerlinRostovwithatotaltraveltimeof13.95hours.Thefollowingnetworkdiagramhighlightstheseshortestpaths.

c) ThePresidentmustsatisfyeachRussiancity’smilitaryrequirementsatminimumcost.Therefore,thisproblemcanbesolvedasaminimum-costnetworkflowproblem.ThetwonodesrepresentingUScitiesaresupplynodeswithasupplyof500each(wemeasureallweightsin1000tons).ThethreenodesrepresentingSaintPetersburg,Moscow,andRostovaredemandnodeswithdemandsof–320,-440,and–240,respectively.AllnodesrepresentingEuropeanairfieldsandportsaretransshipmentnodes.Wemeasuretheflowalongthearcsin1000tons.Forsomearcs,capacityconstraintsaregiven.AllarcsfromtheEuropeanportsintoSaintPetersburghavezerocapacity.AlltruckroutesfromtheEuropeanportsintoRostovhaveatransportationlimitof2,500*16=40,000tons.Sincewemeasurethearcflowsin1000tons,thecorrespondingarccapacitiesequal40.Ananalogouscomputationyieldsarccapacitiesof30forboththearcsconnectingthenodesLondonandBerlintoRostov.Forallothernodeswedeterminenaturalarccapacitiesbasedonthesuppliesanddemandsatthenodes.Wedefinetheunitcostsalongthearcsinthenetworkin$1000per1000tons(or,equivalently,$/ton).Forexample,thecostoftransporting1tonofmaterialfromBostontoHamburgequals$30,000/240=$125,sothecostsoftransporting1000tonsfromBostontoHamburgequals$125,000.

Theobjectiveistosatisfyalldemandsinthenetworkatminimumcost.Thefollowingspreadsheetshowstheentirelinearprogrammingmodel.

Thetotalcostoftheoperationequals$412.867million.TheentiresupplyforSaintPetersburgissuppliedfromJacksonvilleviaLondon.TheentiresupplyforMoscowissuppliedfromBostonviaHamburg.Ofthe240(=240,000tons)demandedbyRostov,60areshippedfromBostonviaIstanbul,150areshippedfromJacksonvilleviaIstanbul,and30areshippedfromJacksonvilleviaLondon.ThepathsusedtoshipsuppliestoSaintPetersburg,Moscow,andRostovarehighlightedonthefollowingnetworkdiagram.

d) NowthePresidentwantstomaximizetheamountofcargotransportedfromtheUStotheRussiancities.Inotherwords,thePresidentwantstomaximizetheflowfromthetwoUScitiestothethreeRussiancities.AllthenodesrepresentingtheEuropeanportsandairfieldsareonceagaintransshipmentnodes.Theflowalonganarcisagainmeasuredinthousandsoftons.Thenewrestrictionscanbetransformedintoarccapacitiesusingthesameapproachthatwasusedinpart(c).TheobjectiveisnowtomaximizethecombinedflowintothethreeRussiancities.

Thelinearprogrammingspreadsheetmodeldescribingthemaximumflowproblemappearsasfollows.

Thespreadsheetshowsalltheamountsthatareshippedbetweenthevariouscities.ThetotalsupplyforSaintPetersburg,Moscow,andRostovequals225,000tons,104,800tons,and192,400tons,respectively.ThefollowingnetworkdiagramhighlightsthepathsusedtoshipsuppliesbetweentheUSandtheRussianFederation.

e) Thecreationofthenewcommunicationsnetworkisaminimumspanningtreeproblem.Asusual,agreedyalgorithmsolvesthistypeofproblem.

Arcsareaddedtothenetworkinthefollowingorder(oneofseveraloptimalsolutions):

Rostov-Orenburg

120

Ufa-Orenburg

75

Saratov-Orenburg

95

Saratov-Samara

100

Samara-Kazan

95

Ufa–Yekaterinburg

125

Perm–Yekaterinburg

85

Theminimumcostofreestablishingthecommunicationlinesis$695,000.

7.2 a) Therearethreesupplynodes–theYennode,theRupiahnode,andtheRinggitnode.Thereisonedemandnode–theUS$node.Below,wedrawthenetworkoriginatingfromonlytheYensupplynodetoillustratetheoveralldesignofthenetwork.Inthisnetwork,weexcludeboththeRupiahandRinggitnodesforsimplicity.

b) Sincealltransactionlimitsaregivenintheequivalentof$1000wedefinetheflowvariablesastheamountinthousandsofdollarsthatJakeconvertsfromonecurrencyintoanotherone.HistotalholdingsinYen,Rupiah,andRinggitareequivalentto$9.6million,$1.68million,and$5.6million,respectively(ascalculatedincellsI16:K18inthespreadsheet).So,thesuppliesatthesupplynodesYen,Rupiah,andRinggitare-$9.6million,-$1.68million,and-$5.6million,respectively.ThedemandattheonlydemandnodeUS$equals$16.88million(thesumoftheoutflowsfromthesourcenodes).ThetransactionlimitsarecapacityconstraintsforallarcsleavingfromthenodesYen,Rupiah,andRinggit.Theunitcostforeveryarcisgivenbythetransactioncostforthecurrencyconversion.

Jakeshouldconverttheequivalentof$2millionfromYentoeachUS$,Can$,Euro,andPound.Heshouldconvert$1.6millionfromYentoPeso.Moreover,