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

CHAPTER6TRANSPORTATIONANDASSIGNMENTPROBLEMSReVieWQUeStiOnS6.1- 1TheCEOisconcernedaboutescalatingcosts,inparticulartheshippingcostsforpeas.6.1-2KimBakerisbeingaskedtolookatthecurrentshippingplanandseeiftheycandevelopanewonethatwouldreducethetotalshippingcosttoanabsoluteminimum.6.2- 1Transportationproblemsingeneralareconcernedwithdistributinganycommodityfromanygroupofsupplycenters,calledsources,toanygroupofreceivingcenters,calleddestinations,insuchawayastominimizethetotaldistributioncost.6.2- 2Thedataneededforatransportationproblemarethesupplies,demands,andunitcosts.6.2- 3FormulatingaproblemasatransportationproblemonlyrequiresfillingoutatableintheformatofTable6.5.6.2- 4Atransportationproblemwillhavefeasiblesolutionsifandonlyifthesumofitssuppliesequalsthesumofitsdemands.6.2- 5Aslongasallitssuppliesanddemandshaveintegervalues,anytransportationproblemwithfeasiblesolutionsisguaranteedtohaveanoptimalsolutionwithintegervaluesforallitsdecisionvariables.6.2- 6Thetransportationsimplexmethodandnetworksimplexmethodcansolvethemfaster.6.3- 1A<signinsteadofan=signisusedintherespectivecellsandthecorrespondingconstraintsintheSolverdialogbox.6.3- 2Insteadofademandrow,thereisbothaminimumrowandamaximumrow.ThenconstraintsareenteredsothatShipped>MinimumandShipped<Maximum.6.4- 1Theareasofapplicationinthissectionaredistributingnaturalresources,productionscheduling,designingschoolattendancezones,meetingenergyneeds,andchoosinganewsitelocation.6.4- 2Minimizethetotalcostofmeetingthewaterneedsofthefourcitiestheyserve.6.4- 3Thesourcesaretheproductionofjetenginesonregulartimeandovertimeineachofthefourmonths.Thedestinationsaretheirinstallationineachofthefourmonths.6.5- 4Distancesplaytheroleofunitcosts.6.4- 5Minimizethetotalcostofmeetingalltheenergyneeds.6.5- 1Thethreekeyfactorsare(1)thecostoftransportingtheoilfromitssourcestoalltherefineries,includingthenewone;(2)thecostoftransportingfinishedproductfromalltherefineries,includingthenewone,tothedistributioncenters;and(3)operatingcostsforthenewrefineries.6.5- 2Thenewrefinerywillhaveagreatimpactontheoperationoftheentiredistributionsystem,includingdecisionsonhowmuchtoshiptoandfromeachrefinery(newandold).6.6- 3Threetransportationproblemsweresolvedtocomparetotalshippingcostsforcrudeoilwitheachpotentialchoiceofanewrefinerysite,andthreeweresolvedtocomparetotalshippingcostsforfinishedproductwitheachpotentialchoiceofanewrefinerysite.Thisresultedinsixtotalproblems.6.7- 4Managementmustconsidernon-financialfactorsaswell,suchasclosenesstocorporateheadquartersandwhetherthereareanycosttrendsortrendsinthemarketplacethatmightalterthepictureinthefuture.6.8- 1Givenasetoftaskstobeperformedandasetofassigneesthatareavailabletoperformthesetasks,theproblemistodeterminewhichassigneeshouldbeassignedtoeachtask.6.9- 2(1)Thenumberofassigneesandthenumberoftasksarethesame;(2)eachassigneeistobeassignedtoexactlyonetask;(3)eachtaskistobeperformedbyexactlyoneassignee;(4) thereisacostassociatedwitheachcombinationofanassigneeperformingatask;and(5) theobjectiveistodeterminehowalltheassignmentshouldbemadetominimizethetotalcost.6.6- 3(1)Identifytheassigneesandtasks,and(2)constructacosttablethatgivesthecostassociatedwitheachcombinationofanassigneeperformingatask.6.6- 4Whenanassignmentproblemisdescribedasatransportationproblem,thesourcesareassignments,thedestinationsaretasks,andthesuppliesanddemandsareallequalto1.6.7- 5TheHungarianmethodsolvesassignmentproblemswell.6.8- 1Whenformulatingthespreadsheetmodel,aconstraintisincludedintheSolverdialogboxthatsetstheassignee/taskcombinationequalto0.6.7- 2Ifanassigneewillperformmorethanonetask,thesupplyischangefrom1tothegreateramountthatcanbeperformed.6.7- 3Ifataskwillbeperformedbymorethanoneassignee,thedemandischangedfrom1tothegreateramount.PrObIemS6.1 a)UnitCost($)Destination(RetailOutlet)1234Supply150060040020010Source220090010030020(Plant)330040020010020420010030020010Demand20101020b)IIIlllIII±6.4a)UnitCost($)Destination(DistributionCenter)1234SupplySource150075030045012(Plant)265080040060017340070050055011Demand10101010-L-6.56.76.8WttMI)MiWt硼懒AllowableRangeDestinationSacramentoSaltLakeCityRapidCityAlbuquerqueSourceBellingham449to492to528570to8516to888EugeneYOto367401to437473to770toAlbertLea267to331to-to472601to1,036Theserangestellmanagementhowmucheachindividualcostcanchangewithoutchangingtheoptimalsolution.IsiCeIIs神（U掘Mta搬怵a) Theoptimalsolutionwouldchangebecausethedecreaseof$30millionisoutsidetheallowabledecreaseof$20million.b) Theoptimalsolutionwouldremainthesamesincetheallowableincreaseis.c) PercentageofallowabledecreaseforCalorietoSanGo=(230-215)/20=75%.PercentageofallowableincreaseforSacrontoLosDevils=(145-130)/=0%.Sum=75%<100%,sobythe100%-ruletheoptimalsolutionwillnotchange.d) PercentageofallowabledecreaseforsupplyatSacron=(0.5/2.5)=20%.PercentageofallowabledecreasefordemandatHollyglass=(0.5/1.5)=33.3%.Sum=53.3%<100%,sobythe100%ruleforsimultaneouschanges,theshadowpriceswillremainvalid.6.11-L-2636466.166.17a)TheFeasibleSolutionsPropertyguaranteesthat,sincethesumofthesuppliesandthesumofthedemandsareequal,theproblemwillhavefeasiblesolutions.b) TheIntegerSolutionPropertyguaranteesthat,sincesuppliesanddemandsareintegers,theresultingoptimalsolutionswillbeintegers.SuppliesandDemandsare1,sotheonlypossiblevaluesofvariablesinanoptimalsolutionare0or1.c) Thiscanbeinterpretedasanassignmentproblemsinceallthesuppliesanddemandsareequalto1.Eachsourceshipsoneunit(theassignee)toonedestination(thetask).e)-1-6.18a)-L-b)-L-6.20a)Thisproblemfitsasanassignmentproblemwithshipsasassigneesandportsasassignments.6.216.22a)Theproblemfitsintotheformatforanassignmentproblemwithswimmersbeingassignedtostrokes.Thetimesoftheswimmersreplacethecostsofatraditionalproblem.6.23CaSeS6.1 C)Ptior)1(ShiPPingbyRail):RaneWNJmCCOllSShipmentQuartl0F1ShippingCostB3:F5TotalAvaiIabIe110:112TotaICost115TotalReceivedB13:F1TotaIShippedG1O:G1TetanllR15:FlWn-25lWhencomparingthethreeoptions,itisbesttousethecombinationplan,whileshippingentirelybyrailleadstothehighestcosts.Ifcostsofshippingbywaterareexpectedtoriseconsiderablymorethanforshippingbyrail,staywithrailanduseOption1.Ifthereverseistrue,thenuseOption2.Ifthecostcomparisonswillremainroughlythesame,useOption3.Option3isclearlythemostfeasiblebutmaynotbechosenifitistoologisticallycumbersome.Moreknowledgeofthesituationisnecessarytodeterminethis.6.2 a)$20millionissavedincomparisonwiththeresultsinFigure6.13byshipping20millionfewerbarrelstoCharlestonand20millionmoretoSt.Louis.b) $40millionissavedincomparisonwiththeresultsinFigure6.17.Thecostofshippingbothcrudeoilandfinishedproductunderthisplanis$940million+$1,390million=$2,330millionor$2.33billionasavingsof$60millioncomparedtotheoriginalresultsinTable6.20.c) $35millionissavedincomparisonwiththeresultsinpart(b).$75millionissavedincomparisonwiththeresultsinFigure6.17.d) Thissolutioncosts$40millionmorethanthesolutioninpart(a).Thissolutioncosts$20millionmorethanthesolutionisFigure6.13.Thetotalcostofshippingbothcrudeoilandfinishedproductunderthisplanis$1,355million+$980million=$2,335millionor$2,335billion.Thisis$5millionmorethanthecostofthecombinedtotalobtainedinpart(b),but$55millionlessthanthetotalinTable6.20.e) Thetwotransportationproblems(shippingtorefineriesandshippingtodistributionscenters)arecombinedintoasinglemodel.Theamountshippedtotherefineriesisconstrainedtobenomorethancapacity:TotalReceived(D16:G16)<Capacity(D18:G18).Thetotalshippedoutoftherefineriesisconstrainedtoequalthetotalamountshippedin:ShippedOut(H31:H34)=Shippedln(J31J34).Thegoalistominimizethetotalcombinedcost(inJ45)whichisthesumofthetwointermediatecosts(inJ20andJ39).Thetotalcombinedcostis$2,320millionor$2.32billion,whichis$10millionlessthaninpart(b),$15millionlessthaninpart(d),and$70millionlessthaninTable6.20.f) IftheLosAngelesrefineryischoseninstead,thenthecombinedshippingcostis$2,450million.IftheGalvestonrefineryischoseninstead,thenthecombinedshippingcostis$2,470million.SiteTotalCostofShippingCrudeOilTotalCostofShippingFinishedProductOperatingCostforNewRefineryTotalVariableCostLosAngeles$880million$1.57billion$620million$3.07billionGalveston870million1.60billion570million3.12billionSt.Louis950million1.37billion530million2.92billiong) Answerswillvary.6.3a)Assignonescientisttoeachofthefiveprojectstomaximizethetotalnumberofbidpoints.TomaximizethescientistspreferencesyouwanttoassignDr.TsaitoleadprojectUp,Dr.KvaaltoleadprojectStable,Dr.ZunertoleadprojectChoice,Dr.MickeytoleadprojectHope,andDr.RollinstoleadprojectRelease.b) Dr.Rollinsisnotavailable,sohis“Supply“incell114isreducedtozero.Sincenowmustallowaprojecttonotbedone,theconstraintsinrows15to17becomeTotalAssigned(B15:F15)<Demand(B17:F17)ratherthan=.ProjectUpwouldnotbedone.c) SinceDr.ZoonerorDr.Mickeycanleadtwoprojects,their“Supply“incolumnIischangedto2andthecorrespondingconstraintchangedto(inordertoallowthemtodoeitheroneortwoprojects).Dr.KvaalleadsprojectStable,Dr.ZunerleadsprojectChoice,Dr.TsaileadsprojectRelease,andDr.MickeyleadstheprojectsHopeandUp.d) UnderthenewbidsofDr.Zunertheassignmentdoesnotchange:e) CertainlyDr.ZunercouldbedisappointedthatsheisnotassignedtoprojectStable,especiallywhensheexpressedahigherpreferenceforthatprojectthanthescientistassigned.Theoptimalsolutionmaximizesthepreferencesoverall,butindividualscientistsmaybedisappointed.Weshouldthereforemakesuretocommunicatethereasoningbehindtheassignmentstothescientists.f) Wheneverascientistcannotleadaparticularprojectweconstrainthecorrespondingchangingcell(E10,F10,C13,E13,andB14)toequal0.Dr.KvaalleadsprojectStable,Dr.ZunerleadsprojectChoice,Dr.TsaileadsprojectRelease,Dr.MickeyleadsprojectUp,andDr.RollinsleadsprojectHope.g) Whenwewanttoassigntwoassigneestothesametaskweneedtoduplicatethattask.ProjectUpisledbyDr.Mickey,StablebyDr.Kvaal,ChoicebyDr.Zuner,HopebyDr.ArriagaandDr.Santos,andReleasebyDr.TsaiandDr.Rollins.h) No.Maximizingoverallpreferencesdoesnotmaximizeindividualpreferences.Scientistswhodonotgettheirfirstchoicemaybecomeresentfulandthereforelackthemotivationtoleadtheirassignedproject.Forexample,intheoptimalsolutionofpart(g),Dr.SantosclearlyelectedprojectReleaseashisfirstchoice,buthewasassignedtoleadprojectHope.Inaddition,maximizingpreferencesignoresotherconsiderationsthatshouldbefactoredintotheassignmentdecision.Forexample,thescientistwiththehighestpreferenceforaprojectmaynotbethescientistmostqualifiedtoleadtheproject.