运筹学 11.ppt

Chapter11NonlinearProgramming toaccompanyOperationsResearch ApplicationsandAlgorithms4theditionbyWayneL Winston Copyright c 2004Brooks Cole adivisionofThomsonLearning Inc 11 1ReviewofDifferentialCalculus Theequationmeansthatasxgetsclosertoa butnotequaltoa thevalueoff x getsarbitrarilyclosetoc Afunctionf x iscontinuousatapointifIff x isnotcontinuousatx a wesaythatf x isdiscontinuous orhasadiscontinuity ata Thederivativeofafunctionf x atx a writtenf a isdefinedtobeN thorderTaylorseriesexpansionThepartialderivativeoff x1 x2 xn withrespecttothevariablexiiswritten 11 2IntroductoryConcepts Ageneralnonlinearprogrammingproblem NLP canbeexpressedasfollows Findthevaluesofdecisionvariablesx1 x2 xnthat max ormin z f x1 x2 xn s t g1 x1 x2 xn or b1s t g2 x1 x2 xn or b2 gm x1 x2 xn or bm Asinlinearprogrammingf x1 x2 xn istheNLP sobjectivefunction andg1 x1 x2 xn or b1 gm x1 x2 xn or bmaretheNLP sconstraints AnNLPwithnoconstraintsisanunconstrainedNLP ThefeasibleregionforNLPaboveisthesetofpoints x1 x2 xn thatsatisfythemconstraintsintheNLP Apointinthefeasibleregionisafeasiblepoint andapointthatisnotinthefeasibleregionisaninfeasiblepoint IftheNLPisamaximizationproblemthenanypointinthefeasibleregionforwhichf f x holdstrueforallpointsxinthefeasibleregionisanoptimalsolutiontotheNLP NLPscanbesolvedwithLINGO EvenifthefeasibleregionforanNLPisaconvexset heoptimalsolutionneednotbeaextremepointoftheNLP sfeasibleregion ForanyNLP maximization afeasiblepointx x1 x2 xn isalocalmaximumifforsufficientlysmall anyfeasiblepointx x 1 x 2 x n having x1 x 1 i 1 2 n satisfiesf x f x Example11 TireProduction Firerockproducesrubberusedfortiresbycombiningthreeingredients rubber oil andcarbonblack Thecostsforeacharegiven Therubberusedinautomobiletiresmusthaveahardnessofbetween25and35anelasticityofat16atensilestrengthofatleast12Tomanufactureasetoffourautomobiletires 100poundsofproductisneeded Therubbertomakeasetoftiresmustcontainbetween25and60poundsofrubberandatleast50poundsofcarbonblack Ex 11 continued Define R poundsofrubberinmixtureusedtoproducefourtiresO poundsofoilinmixtureusedtoproducefourtiresC poundsofcarbonblackusedtoproducefourtiresStatisticalanalysishasshownthatthehardness elasticity andtensilestrnegthofa100 poundmixtureofrubber oil andcarbonblackisTensilestrength 12 5 10 O 001 O 2Elasticity 17 35R 04 O 002 O 2Hardness 34 10R 06 O 3 C 001 R O 005 O 2 001C2FormulatetheNLPwhosesolutionwilltellFirerockhowtominimizethecostofproducingtherubberproductneededtomanufactureasetofautomobiletires Example11 Solution AfterdefiningTS TensileStrengthE ElasticityH HardnessofmixturetheLINGOprogramgivesthecorrectformulation ItiseasytousetheExcelSolvertosolveNLPs Theprocessissimilartoalinearmodel ForNLPshavingmultiplelocaloptimalsolutions theSolvermayfailtofindtheoptimalsolutionbecauseitmaypickalocalextremumthatisnotaglobalextremum 11 3ConvexandConcaveFunctions Afunctionf x1 x2 xn isaconvexfunctiononaconvexsetSifforanyx sandxn sf cx 1 c xn cf x 1 c f xn holdsfor0 c 1 Afunctionf x1 x2 xn isaconcavefunctiononaconvexsetSifforanyx sandxn sf cx 1 c xn cf x 1 c f xn holdsfor0 c 1 Theorems ConsiderageneralNLP SupposethefeasibleregionSforNLPisaconvexset Iff x isconcaveonS thenanylocalmaximum minimum fortheNLPisanoptimalsolutiontotheNLP Supposefn x existsforallxinaconvexsetS Thenf x isaconvex concave functionofSifandonlyiffn x 0 fn x 0 forallxinS Supposef x1 x2 xn hascontinuoussecond orderpartialderivativesforeachpointx x1 x2 xn S Thenf x1 x2 xn isaconvexfunctiononSifandonlyifforeachx S allprincipalminorsofHarenon negative Supposef x1 x2 xn hascontinuoussecond orderpartialderivativesforeachpointx x1 x2 xn S Thenf x1 x2 xn isaconcavefunctiononSifandonlyifforeachx Sandk 1 2 n allnonzeroprincipalminorshavethesamesignas 1 k TheHessianoff x1 x2 xn isthenxnmatrixwhoseijthentryisAnithprincipalminorofannxnmatrixisthedeterminantofanyiximatrixobtainedbydeletingn irowsandthecorrespondingn icolumnsofthematrix Thekthleadingprincipalminorofannxnmatrixisthedeterminantofthekxkmatrixobtainedbydeletingthelastn kroseandcolumnsofthematrix 11 4SolvingNLPswithOneVariable SolvingtheNLPTofindtheoptimalsolutionfortheNLPfindallthelocalmaxima orminima ApointthatisalocalmaximumoralocalminimumfortheNLPiscalledalocalextremum Theoptimalsolutionisthelocalmaximum orminimum havingthelargest orsmallest valueoff x TherearethreetypesofpointsforwhichtheNLPcanhavealocalmaximumorminimum thesepointsareoftencalledextremumcandidates Pointswherea x b f x 0 calledastationarypointoff x Pointswheref x doesnotexistEndpointsaandboftheinterval a b Example21 ProfitMaximizationbyMonopolist Itcostsamonopolist 5 unittoproduceaproduct Ifheproducesxunitsoftheproduct theneachcanbesoldfor10 xdollars Tomaximizeprofit howmuchshouldthemonopolistproduce Example21 Solution ThemonopolistwantstosolvetheNLPTheextremumcandidatescanbeclassifiedasCase1checktellsusx 2 5isalocalmaximumyieldingaprofitP 2 5 6 25 P x existsforallpointsin 0 10 sotherearenoCase2candidates A 0hasP 0 5 0soa 0isalocalminimum b 10hasP 10 15 0 sob 10isalocalminimum Demandisoftenmodeledasalinearfunctionofprice ProfitisaconcavefunctionofpriceandSolvershouldfinetheprofitmaximizingprice SolvingonevariableNLPswithLINGOIfyouaremaximizingaconcaveobjectivefunctionf x thenyoucanbecertainthatLINGOwillfindtheoptimalsolutiontotheNLPIfyouareminimizingaconvexobjectivefunction thenyouknowthatLINGOwillfindtheoptimalsolutiontotheNLP TryingtominimizeanonconvexfunctionormaximizeanonconcavefunctionofaonevariableNLPthenLINGOmayfindalocalextremumthatdoesnotsolvetheNLP 11 5GoldenSectionSearch TheGoldenSectionMethodcanbeusedifthefunctionisaunimodalfunction Afunctionf x isunimodelon a b ifforsomepointon a b f x isstrictlyincreasingon a andstrictlydecreasingon b TheoptimalsolutionoftheNLPissomepointontheinterval a b Byevaluatingf x attwopointsx1andx2on a b wemayreducethesizeoftheintervalinwhichthesolutiontotheNLPmustlie Afterevaluatingf x1 andf x2 oneofthesecasesmustoccur Itcanbeshownineachcasethattheoptimalsolutionwilllieinasubsetof a b Case1 f x1 f x2 andTheintervalinwhichx barmustlie either a x2 or x1 b iscalledtheintervalofuncertainty Manysearchalgorithmsusetheseideastoreducetheintervalofuncertainty Mostofthesealgorithmsproceedasfollows Beginwiththeregionofuncertaintyforxbeing a b Evaluatef x attwojudiciouslychosenpointsx1andx2 Determinewhichofcases1 3holds andfindareducedintervalofuncertainty Evaluatef x attwonewpoints thealgorithmspecifieshowthetwonewpointsarechosen Returntostep2unlessthelengthoftheintervalofuncertaintyissufficientlysmall Spreadsheetscanbeusedtoconductgoldensectionsearch 11 6UnconstrainedMaximizationandMinimizationwithSeveralVariables ConsiderthisunconstrainedNLPThesetheoremsprovidethebasicsofunconstrainedNLP sthatmayhavetwoormoredecisionvariables IfisalocalextremumfortheNLPthen 0 Apointhaving 0fori 1 2 niscalledastationarypointoff IfHk 0 k 1 2 n thenastationarypointisalocalminimumforunconstrainedNLP If fork 1 2 n Hkisnonzeroandhasthesamesignas 1 k thenastationarypointisalocalmaximumfortheunconstrainedNLP IfHn 0andtheconditionsoftheprevioustwotheoremsdonothold thenastationarypointisnotalocalextremum LINGOwillfindtheoptimalsolutionifusedtosolvemaximizingconcavefunctionorminimizingaconvexfunctionproblems 11 7 TheMethodofSteepestAscent Themethodofsteepestascentcanbeusedtoapproximateafunction sstationarypoint Givenavectorx x1 x2 xn Rn thelengthofx written x isForanyvectorx theunitvectorx x iscalledthenormalizedversionofx Considerafunctionf x1 x2 xn allofwhosepartialderivativesexistateverypoint Agradientvectorforf x1 x2 xn written f x isgivenby Supposeweareatapointvandwemovefromvasmalldistance inadirectiond Thenforagiven themaximalincreaseinthevalueoff x1 x2 xn willoccurifwechooseIfwemoveasmalldistanceawayfromvandwewantf x1 x2 xn toincreaseasquicklyaspossible thenweshouldmoveinthedirectionof f v 11 8LagrangeMultipliers LagrangemultiplierscanbeusedtosolveNLPsinwhichalltheconstraintsareequalityconstraints ConsiderNLPsofthefollowingtype TosolvetheNLP associateamultiplier iwiththeithconstraintintheNLPandformtheLagrangian forwhichthepointsforwhichTheLagrangemultipliers icanbeusedinsensitivityanalysis 11 9TheKuhn TuckerConditions TheKuhn TuckerconditionsareusedtosolveNLPsofthefollowingtype TheKuhn TuckerconditionsarenecessaryforapointtosolvetheNLP SupposetheNLPisamaximizationproblem IfisanoptimalsolutiontoNLP thenmustsatisfythemconstraintsintheNLP andtheremustexistmultipliers 1 2 msatisfying SupposetheNLPisaminimizationproblem IfisanoptimalsolutiontoNLP thenmustsatisfythemconstraintsintheNLP andtheremustexistmultipliers 1 2 msatisfying Unlessaconstraintqualificationorregularityconditionissatisfiedatanoptimalpoint theKuhn Tuckerconditionsmayfailtoholdat LINGOcanbeusedtosolveNLPswithinequality andpossiblyequality constraints IfLINGOdisplaysthemessageDUALCONDITIONS SATISFIEDthenyouknowithasfoundthepointsatisfyingtheKuhn Tuckerconditions 11 10 QuadraticProgramming Aquadraticprogrammingproblem QPP isanNLPinwhicheachtermintheobjectivefunctionisofdegree2 1 or0andallconstraintsarelinear LINGO ExcelandWolfe smethod amodifiedversionofthetwo phasesimplex maybeusedtosolveQPPproblems Inpractice themethodofcomplementarypivotingismostoftenusedtosolveQPPs 11 11 SeparableProgramming ManyNLPsareofthefollowingform Theyarecalledseperableprogrammingproblemsthatareoftensolvedbyapproximatingeachfj x andgij xj byapiecewiselinearfunction Toapproximatetheoptimalsolutiontoaseparateprogrammingproblem solvethefollowingapproximationproblemFortheapproximationproblemtoyieldagoodapproximationtothefunctionsfiandgj k wemustaddthefollowingadjacencyassumption Forj 1 2 n atmosttwo j k scanbepositive 11 12TheMethodofFeasibleDirections Thismethodtakesthesteepestascentmethodofsection12 7intoacasewheretheNLPnowhaslinearconstraints Tosolvebeginwithafeasiblesolutionx0 Letd0beasolutionto Chooseournewpointx1tobex1 x0 t0 d0 x0 wheret0solvesLetd1beasolutiontoChooseournewpointx2tobex2 x1 t1 d1 x1 wheret1solves Continuegeneratingpointsx3 xkinthisfashionuntilxk xk 1orsuccessivepointsaresuf