运筹学 18.ppt

Chapter18DeterministicDynamicProgramming toaccompanyOperationsResearch ApplicationsandAlgorithms4theditionbyWayneL Winston Copyright c 2004Brooks Cole adivisionofThomsonLearning Inc Description Dynamicprogrammingisatechniquethatcanbeusedtosolvemanyoptimizationproblems Inmostapplications dynamicprogrammingobtainssolutionsbyworkingbackwardfromtheendoftheproblemtowardthebeginning thusbreakingupalarge unwieldyproblemintoaseriesofsmaller moretractableproblems 18 1TwoPuzzlesExample Weshowhowworkingbackwardcanmakeaseeminglydifficultproblemalmosttrivialtosolve Supposethereare20matchesonatable Ibeginbypickingup1 2 or3matches Thenmyopponentmustpickup1 2 or3matches Wecontinueinthisfashionuntilthelastmatchispickedup Theplayerwhopicksupthelastmatchistheloser HowcanI thefirstplayer besureofwinningthegame IfIcanensurethatitwillbeopponent sturnwhen1matchremains Iwillcertainlywin Workingbackwardonestep ifIcanensurethatitwillbemyopponent sturnwhen5matchesremain Iwillwin IfIcanforcemyopponenttoplaywhen5 9 13 17 21 25 or29matchesremain Iamsureofvictory ThusIcannotloseifIpickup1matchonmyfirstturn 18 2ANetworkProblem Manyapplicationsofdynamicprogrammingreducetofindingtheshortest orlongest paththatjoinstwopointsinagivennetwork Forlargernetworksdynamicprogrammingismuchmoreefficientfordeterminingashortestpaththantheexplicitenumerationofallpaths CharacteristicsofDynamicProgrammingApplications Characteristic1Theproblemcanbedividedintostageswithadecisionrequiredateachstage Characteristic2Eachstagehasanumberofstatesassociatedwithit Byastate wemeantheinformationthatisneededatanystagetomakeanoptimaldecision Characteristic3Thedecisionchosenatanystagedescribeshowthestateatthecurrentstageistransformedintothestateatthenextstage Characteristic4Giventhecurrentstate theoptimaldecisionforeachoftheremainingstagesmustnotdependonpreviouslyreachedstatesorpreviouslychosendecisions Thisideaisknownastheprincipleofoptimality Characteristic5IfthestatesfortheproblemhavebeenclassifiedintoonofTstages theremustbearecursionthatrelatedthecostorrewardearnedduringstagest t 1 Ttothecostorrewardearnedfromstagest 1 t 2 T 18 3AnInventoryProblem Dynamicprogrammingcanbeusedtosolveaninventoryproblemwiththefollowingcharacteristics Timeisbrokenupintoperiods thepresentperiodbeingperiod1 thenextperiod2 andthefinalperiodT Atthebeginningofperiod1 thedemandduringeachperiodisknown Atthebeginningofeachperiod thefirmmustdeterminehowmanyunitsshouldbeproduced Productioncapacityduringeachperiodislimited Eachperiod sdemandmustbemetontimefrominventoryorcurrentproduction Duringanyperiodinwhichproductiontakesplace afixedcostofproductionaswellasavariableper unitcostisincurred Thefirmhaslimitedstoragecapacity Thisisreflectedbyalimitonend of periodinventory Aper unitholdingcostisincurredoneachperiod sendinginventory Thefirmsgoalistominimizethetotalcostofmeetingontimethedemandsforperiods1 2 T Inthismodel thefirm sinventorypositionisreviewedattheendofeachperiod andthentheproductiondecisionismade Suchamodeliscalledaperiodicreviewmodel Thismodelisincontrasttothecontinuousreviewmodelinwhichthefirmknowsitsinventorypositionatalltimesandmayplaceanorderorbeginproductionatanytime 18 4Resource AllocationProblems Resource allocationproblems inwhichlimitedresourcesmustbeallocatedamongseveralactivities areoftensolvedbydynamicprogramming Touselinearprogrammingtodoresourceallocation threeassumptionsmustbemade Assumption1 Theamountofaresourceassignedtoanactivitymaybeanynonnegativenumber Assumption2 Thebenefitobtainedfromeachactivityisproportionaltotheamountoftheresourceassignedtotheactivity Assumption3 Thebenefitobtainedfrommorethanoneactivityisthesumofthebenefitsobtainedfromtheindividualactivities Evenifassumptions1and2donothold dynamicprogrammingcanbeusedtosolveresource allocationproblemsefficientlywhenassumption3isvalidandwhentheamountoftheresourceallocatedtoeachactivityisamemberofafiniteset GeneralizedResourceAllocationProblem Theproblemofdeterminingtheallocationofresourcesthatmaximizestotalbenefitsubjecttothelimitedresourceavailabilitymaybewrittenaswherextmustbeamemberof 0 1 2 Tosolvethisbydynamicprogramming defineft d tobethemaximumbenefitthatcanbeobtainedfromactivitiest t 1 Tifdunitesoftheresourcemaybeallocatedtoactivitiest t 1 T WemaygeneralizetherecursionstothissituationbywritingfT 1 d 0foralldwherextmustbeanon negativeintegersatisfyinggt xt d ATurnpikeTheorem Turnpikeresultsaboundinthedynamicprogrammingliterature Whyaretheresultsreferredtoasaturnpiketheorem Thinkabouttakinganautomobiletripinwhichourgoalistominimizethetimeneededtocompletethetrip Foralongtripitmaybeadvantageoustogoslightlyoutofourwaysothatmostofthetripwillbespentonaturnpike onwhichwecantravelatthegreatestspeed 18 5EquipmentReplacementProblems Manycompaniesandcustomersfacetheproblemofdetermininghowlongamachineshouldbeutilizedbeforeitshouldbetradedinforanewone Problemsofthistypearecalledequipment replacementproblemsandcanbesolvedbydynamicprogramming AnequipmentreplacementmodelwasactuallyusedbyPhillipsPetroleumtoreducecostsassociatedwithmaintainingthecompany sstockoftrucks 18 6FormulatingDynamicProgrammingRecursions Inmanydynamicprogrammingproblems agivenstagesimplyconsistsofallthepossiblestatesthatthesystemcanoccupyatthatstage Ifthisisthecase thenthedynamicprogrammingrecursioncanoftenbewritteninthefollowingform Ft i min costduringstaget ft 1 newstageatstaget 1 wheretheminimumintheaboveequationisoveralldecisionsthatareallowable orfeasible whenthestateatstatetisi Correctformulationofarecursionoftheformrequiresthatweidentifythreeimportantaspectsoftheproblem Aspect1 Thesetofdecisionsthatisallowable orfeasible forthegivenstateandstage Aspect2 Wemustspecifyhowthecostduringthecurrenttimeperiods staget dependsonthevalueoft thecurrentstate andthedecisionchosenatstaget Aspect3 Wemustspecifyhowthestateatstaget 1dependsonthevalueoft thestatesatstaget andthedecisionchosenatstaget Notallrecursionsareoftheformshownbefore AFisheryExample Theownerofalakemustdecidehowmanybasstocatchandselleachyear Ifshesellsxbassduringyeart thenarevenuer x isearned Thecostofcatchingxbassduringayearisafunctionc x b ofthenumberofbasscaughtduringtheyearandofb thenumberofbassinthelakeatthebeginningoftheyear Ofcourse bassdoreproduce AFisheryExample Tomodelthis weassumethatthenumberofbassinthelakeatthebeginningofayearis20 morethanthenumberofbassleftinthelakeattheendofthepreviousyear Assumethatthereare10 000bassinthelakeatthebeginningofthefirstyear Developadynamicprogrammingrecursionthatcanbeusedtomaximizetheowner snetprofitoveraT yearhorizon AFisheryExample Inproblemswheredecisionsmustbemadeatseveralpointsintime thereisoftenatrade offofcurrentbenefitsagainstfuturebenefits AtthebeginningofyearT theownerofthelakeneednotworryabouttheeffectthatthecaptureofbasswillhaveonthefuturepopulationofthelake Sothebeginningoftheyearproblemisrelativelyeasytosolve Forthisreason welettimebethestage Ateachstage theownerofthelakemustdecidehowmanybasstocatch AFisheryExample Wedefinexttobethenumberofbasscaughtduringyeart Todetermineanoptimalvalueofxt theownerofthelakeneedonlyknowthenumberofbass callitbt inthelakeatthebeginningofyeart Therefore thestateatthebeginningofyeartisbt Wedefineft bt tobethemaximumnetprofitthatcanbeearnedfrombasscaughtduringyearst t 1 Tgiventhatbtbassareinthelakeatthebeginningofyeart AFisheryExample Wemaynowdisposeofaspects1 3oftherecursion Aspect1 Whataretheallowabledecisions Duringanyyearwecan tcatchmorebassthanthereareinthelake Thus ineachstateandforallt0 xt btmusthold Aspect2 Whatisthenetprofitearnedduringyeart Ifxtbassarecaughtduringayearthatbeginswithbtbassinthelake thenthenetprofitisr xt c xt bt Aspect3 Whatwillbethestateduringyeart 1 Theyeart 1statewillbe1 2 bt xt AFisheryExample AfteryearT therearenofutureprofitstoconsider soft bt max r xt c xt bt ft 1 1 2 bt xt where0 xt bt Weusethisequationtoworkbackwardsuntilf1 10 000 hasbeencomputed Thentodeterminetheoptimalfishingpolicy webeginbychoosingx1tobeanyvalueattainingthemaximumintheequationforf1 10 000 Thenyear2willbeginwith1 2 10 000 x1 bassinthelake AFisheryExample Thismeansthatx2shouldbechosentobeanyvalueattainingthemaximumintheequationforf2 1 2 10 000 x1 Continueinthisfashionuntiloptimalvaluesofx3 x4 xThavebeendetermined IncorporatingtheTimeValueofMoneyintoDynamicProgrammingFormulations Aweaknessofthecurrentformulationisthatprofitsreceivedduringthelateryearsareweightedthesameasprofitsreceivedduringtheearlieryears Supposethatforsome 1 1receivedatthebeginningofyeart 1isequivalentto dollarsreceivedatthebeginningofyeart Wecanincorporatethisideaintothedynamicprogrammingrecursionbyreplacingthepreviousequationwithwhere0 xt bt Thenweredefineft bt tobethemaximumnetprofitthatcanbeearnedduringyearst t 1 T Thisapproachcanbeusedtoaccountforthetimevalueofmoneyinanydynamicprogrammingformulation ComputationalDifficultiesinUsingDynamicProgramming Thereisaproblemthatlimitsthepracticalapplicationofdynamicprogramming Inmanyproblems thestatespacebecomessolargethatexcessivecomputationaltimeisrequiredtosolvetheproblembydynamicprogramming 18 7TheWagner WhitinAlgorithmandtheSilver MealHeuristic TheInventoryExampleinthischapterisaspecialcaseofthedynamiclot sizemodel DescriptionofDynamicLot SizeModelDemanddtduringperiodst t 1 2 T isknownatthebeginningofperiod1 Demandforperiodtmustbemetontimefrominventoryorfromperiodtproduction Thecostc x ofproducingxunitsduringanyperiodisgivenbyc 0 0 andforx 0 c x K cx whereKisafixedcostforsettingupproductionduringaperiod andcisavariableper unitcostofproduction Attheendofperiodt theinventorylevelitisobserved andaholdingcosthitisincurred Weleti0denotestheinventorylevelbeforeperiod1productionoccurs Thegoalistodetermineaproductionlevelxiforeachperiodtthatminimizesthetotalcostofmeeting ontime thedemandsforperiods1 2 T Thereisalimitctplacedonperiodt sendinginventory Thereisalimitrtplacedonperiodt sproduction WagnerandWhitinhavedevelopedamethodthatgreatlysimplifiesthecomputationofoptimalproductionschedulesfordynamiclot sizemodels Lemmas1and2arenecessaryforthedevelopmentoftheWagner Whitinalgorithm Lemma1 Supposeitisoptimaltoproduceapositivequantityduringaperiodt Thenforsomej 0 1 T t theamountproducedduringperiodtmustbesuchthatafterperiodt sproduction aquantitydt dt 1 dt jwillbeinstock Inotherwords ifproductionoccursduringp