数据、模型与决策（第12版）课件 第10章非线性规划

NonlinearProgrammingChapter10Copyright©2016PearsonEducation,Inc.NonlinearProfitAnalysisConstrainedOptimizationSolutionofNonlinearProgrammingProblemswithExcelANonlinearProgrammingModelwithMultipleConstraintsNonlinearModelExamplesChapterTopicsCopyright©2016PearsonEducation,Inc.Problemsthatfitthegenerallinearprogrammingformatbutcontainnonlinearfunctionsaretermednonlinearprogramming(NLP)problems.Solutionmethodsaremorecomplexthanlinearprogrammingmethods.Determininganoptimalsolutionisoftendifficult,ifnotimpossible.Solutiontechniquesgenerallyinvolvesearchingasolutionsurfaceforhighorlowpointsrequiringtheuseofadvancedmathematics.OverviewCopyright©2016PearsonEducation,Inc. Profitfunction,Z,withvolumeindependentofprice: Z=vp-cf-vcvwherev=salesvolume p=price cf=unitfixedcost cv=unitvariablecostAddvolume/pricerelationship:v=1,500-24.6pNonlinearProfitAnalysisOptimalValueofaSingleNonlinearFunctionFigure10.1LinearrelationshipofvolumetopriceCopyright©2016PearsonEducation,Inc.Withfixedcost(cf=$10,000)andvariablecost(cv=$8):Profit,Z=1,696.8p-24.6p2-22,000 OptimalValueofaSingleNonlinearFunctionFigure10.2ThenonlinearprofitfunctionCopyright©2016PearsonEducation,Inc.Theslopeofacurveatanypointisequaltothederivativeofthecurve’sfunction.Theslopeofacurveatitshighestpointequalszero.Figure10.3MaximumprofitfortheprofitfunctionOptimalValueofaSingleNonlinearFunctionMaximumPointonaCurveCopyright©2016PearsonEducation,Inc.Figure10.4Maximumprofit,optimalpriceandoptimalvolumeOptimalValueofaSingleNonlinearFunctionSolutionUsingCalculusZ=1,696.8p-24.6p2-2,000dZ/dp=1,696.8-49.2p =0p=1696.8/49.2=$34.49v=1,500-24.6pv=651.6pairsofjeansZ=$7,259.45Copyright©2016PearsonEducation,Inc.Anonlinearproblemcontainingoneormoreconstraintsbecomesaconstrainedoptimizationmodeloranonlinearprogramming(NLP)model.Anonlinearprogrammingmodelhasthesamegeneralformasthelinearprogrammingmodelexceptthattheobjectivefunctionand/ortheconstraint(s)arenonlinear.SolutionproceduresaremuchmorecomplexandnoguaranteedprocedureexistsforallNLPmodels.ConstrainedOptimizationinNonlinearProblemsDefinitionCopyright©2016PearsonEducation,Inc.Effectofaddingconstraintstononlinearproblem:Figure10.5NonlinearprofitcurvefortheprofitanalysismodelConstrainedOptimizationinNonlinearProblemsGraphicalInterpretation(1of3)Copyright©2016PearsonEducation,Inc.Figure10.6AconstrainedoptimizationmodelConstrainedOptimizationinNonlinearProblemsGraphicalInterpretation(2of3)Copyright©2016PearsonEducation,Inc.Figure10.7AconstrainedoptimizationmodelwithasolutionpointnotontheconstraintboundaryConstrainedOptimizationinNonlinearProblemsGraphicalInterpretation(3of3)Copyright©2016PearsonEducation,Inc.Unlikelinearprogramming,thesolutionisoftennotontheboundaryofthefeasiblesolutionspace.Cannotsimplylookatpointsonthesolutionspaceboundarybutmustconsiderotherpointsonthesurfaceoftheobjectivefunction.Thisgreatlycomplicatessolutionapproaches.Solutiontechniquescanbeverycomplex.ConstrainedOptimizationinNonlinearProblemsCharacteristicsCopyright©2016PearsonEducation,Inc.Exhibit10.1WesternClothingProblemSolutionUsingExcel(1of3)Formulaforprofit=1500-24.6*C5Copyright©2016PearsonEducation,Inc.Exhibit10.2WesternClothingProblemSolutionUsingExcel(2of3)Clickon“GRGNonlinear”Copyright©2016PearsonEducation,Inc.Exhibit10.3WesternClothingProblemSolutionUsingExcel(3of3)Copyright©2016PearsonEducation,Inc.MaximizeZ=$(4-0.1x1)x1+(5-0.2x2)x2

subjectto: x1+2x2=40Where: x1=numberofbowlsproduced x2=numberofmugsproduced 4–0.1X1=profit($)perbowl 5–0.2X2=profit($)permug BeaverCreekPotteryCompanyProblemSolutionUsingExcel(1of6)Exhibit10.4BeaverCreekPotteryCompanyProblemSolutionUsingExcel(2of6)=C5+2*C6=SUMPRODUCT(C5:C6,D5:D6)Copyright©2016PearsonEducation,Inc.Exhibit10.5BeaverCreekPotteryCompanyProblemSolutionUsingExcel(3of6)Copyright©2016PearsonEducation,Inc.Exhibit10.6BeaverCreekPotteryCompanyProblemSolutionUsingExcel(4of6)Copyright©2016PearsonEducation,Inc.Exhibit10.7BeaverCreekPotteryCompanyProblemSolutionUsingExcel(5of6)Select“Sensitivity”Copyright©2016PearsonEducation,Inc.Exhibit10.8BeaverCreekPotteryCompanyProblemSolutionUsingExcel(6of6)LagrangemultiplierforlaborCopyright©2016PearsonEducation,Inc.MaximizeZ=(p1-12)x1+(p2-9)x2subjectto: 2x1+2.7x2

6,0003.6x1+2.9x2

8,5007.2x1+8.5x2

15,000where: x1=1,500-24.6p1 x2=2,700-63.8p2 p1=priceofdesignerjeans p2=priceofstraightjeansWesternClothingCompanyProblemSolutionUsingExcel(1of4)Copyright©2016PearsonEducation,Inc.Exhibit10.9WesternClothingCompanyProblemSolutionUsingExcel(2of4)=D5-12=SUMPRODUCT(C5:C6,E5:E6)=2*C5+2.7*C6Copyright©2016PearsonEducation,Inc.Exhibit10.10WesternClothingCompanyProblemSolutionUsingExcel(3of4)Copyright©2016PearsonEducation,Inc.Exhibit10.11WesternClothingCompanyProblemSolutionUsingExcel(4of4)Copyright©2016PearsonEducation,Inc.Centrallylocateafacilitythatservesseveralcustomersorotherfacilitiesinordertominimizedistanceormilestraveled(d)betweenfacilityandcustomers.

Where: (x,y)=coordinatesofproposedfacility (xi,yi)=coordinatesofcustomerorlocationfacilityiMinimizetotalmilesd=

ditiWhere: di=distancetotowni ti=annualtripstotowni

FacilityLocationExampleProblemProblemDefinitionandData(1of2)Copyright©2016PearsonEducation,Inc.FacilityLocationExampleProblemProblemDefinitionandData(2of2)Copyright©2016PearsonEducation,Inc.Exhibit10.12FacilityLocationExampleProblemSolutionUsingExcel=SQRT((B6-C14)^2+(C6-C15)^2)Copyright©2016PearsonEducation,Inc.Figure10.8Rescuesquadfacilitylocation

FacilityLocationExampleProblemSolutionMapCopyright©2016PearsonEducation,Inc.InvestmentPortfolioSelectionExampleProblemDefinitionandModelFormulation(1of2)Objectiveoftheportfolioselectionmodelis:tominimizesomemeasureofportfoliorisk(varianceinthereturnoninvestment)whileachievingsomespecifiedminimumreturnonthetotalportfolioinvestment.Copyright©2016PearsonEducation,Inc.MinimizeS=x12s12+x22s22+…+xn2sn2+

xixjrijsisjwhere: S=varianceofannualreturnoftheportfolio xi,xj=theproportionofmoneyinvestedininvestmentsiorj si2=thevarianceforinvestmenti rij=thecorrelationbetweenreturnsoninvestmentsiandj si,sj=thestd.dev.ofreturnsforinvestmentsiandjsubjectto: r1x1+r2x2+…+rnxn

rm x1+x2+…xn=1.0where: ri=expectedannualreturnoninvestmenti rm=theminimumdesiredannualreturnfromtheportfolio

InvestmentPortfolioSelectionExampleProblemDefinitionandModelFormulation(2of2)i≠jCopyright©2016PearsonEducation,Inc.InvestmentPortfolioSelectionExampleProblemSolutionUsingExcel(1of5)Copyright©2016PearsonEducation,Inc.Fourstocks,desiredannualreturnofatleast0.11.MinimizeZ=S=x12(.009)+x22(.015)+x32(.040)+X42(.023) +x1x2(.4)(.009)1/2(0.015)1/2+x1x3(.3)(.009)1/2(.040)1/2+ x1x4(.6)(.009)1/2(.023)1/2+x2x3(.2)(.015)1/2(.040)1/2+ x2x4(.7)(.015)1/2(.023)1/2+x3x4(.4)(.040)1/2(.023)1/2+ x2x1(.4)(.015)1/2(.009)1/2+x3x1(.3)(.040)1/2+(.009)1/2+ x4x1(.6)(.023)1/2(.009)1/2+x3x2(.2)(.040)1/2(.015)1/2+ x4x2(.7)(.023)1/2(.015)1/2+x4x3(.4)(.023)1/2(.040)1/2subjectto: .08x1+.09x2+.16x3+.12x4

0.11x1+x2+x3+x4=1.00xi

0InvestmentPortfolioSelectionExampleProblemSolutionUsingExcel(2of5)Copyright©2016PearsonEducation,Inc.Exhibit10.13InvestmentPortfolioSelectionExampleProblemSolutionUsingExcel(3of5)Doublingcovarianceswillincludeallinvestmentpairs=SUMPRODUCT9B6:B9,E6:E9)=SUM(E6:E9)Copyright©2016PearsonEducation,Inc.Exhibit10.14InvestmentPortfolioSelectionExampleProblemSolutionUsingExcel(4of5)AllmoneyisinvestedconstraintInvestmentreturnconstraintCopyright©2016PearsonEducation,Inc.InvestmentPortfolioSelectionExampleProblemSo