第十章--非线性规划.ppt

1,10.非线性规划NonlinearProgramming,SessionTopics,非线性规划的挑战非线性规划的实例复杂的非线性规划问题,2,10.1非线性规划的挑战,非线性规划与线性规划的区别是目标函数或约束条件为非线性函数。非线性规划模型的建立与线性规划模型的建立几乎没有区别，但是非线性规划的求解远比线性规划的求解困难得多。现在也没有成熟的算法可用来求解任何一个线性规划问题。但是一些典型的中小型问题还是可以用EXCEL求解。,下面例题显示了一个非线性函数的建立及简单非线性规划问题的求解。,目标是构造利润与产量之间的函数,3,趋势线对话框AddTrendlineDialogueBox,非线性规划,4,增加趋势线选项AddTrendlineOptions,非线性规划,5,趋势线（二次方程）TheTrendline(QuadraticEquation),非线性规划,6,解非线性规划模型SolvingNonlinearProgrammingModels,考虑下列的代数形式的模型：MaximizeProfit=0.5x56x4+24.5x339x2+20 xsubjecttox5x0,非线性规划,7,初值取x=0时的解答,初值取x=3时的解答,初值取x=4.7时的解答,非线性规划,8,利润曲线TheProfitGraph,非线性规划解的搜索,非线性规划,9,投资组合的选择PortfolioSelection,管理大量证券投资组合的职业经理习惯于用基于非线性规划的计算机模型帮助他们工作。投资者同时关心着期望回报和风险如何追求收益和风险的平衡？非线性规划经常被用于确定证券投资组合，该组合在一定的假设下，获得收益和风险之间的最优平衡目标:风险极小化约束：期望回报可接受的回报的最小水平考虑3支股票的一个投资组合问题：在期望回报至少要达到18%的前提下，怎样的投资组合使风险最小？,10.2非线性规划的实例,案例1：,10,股票数据DataforStocks,非线性规划,11,代数模型AlgebraicFormulation,MinimizeRisk=(0.25S1)2+(0.45S2)2+(0.05S3)2+2(0.04)S1S2+2(0.005)S1S3+2(0.01)S2S3subjectto(21%)S1+(30%)S2+(8%)S318%S1+S2+S3=100%andS10,S20,S30.,设Si为投资于股票i的投资比率，i=1，2，3,非线性规划,12,投资组合的选择PortfolioSelection,非线性规划,13,使用SolverTable作期望回报和风险的平衡,非线性规划,14,案例2：航班降落调度,在大型机场中，飞机的降落要受到很多安全约束条件的限制。本例中将研究如何对单条跑道上的飞机进行调度。已经有人研究了更一般的问题，但这些问题相当复杂（动态案例，例如航班晚点，同时有多条跑道，等等），因此我们只讨论一个简单的情形。有十个航班需要降落。每个航班都有一个最早到达时间（飞机以最高速度到达降落区域的时间）和最晚到达时间（可能受其他因素如燃油量等的影响）。在这个时间窗口内，航空公司需要选择一个目标时间，并将它作为航班到达时间公布出去。如果比此目标时间迟到或早到，则可能会引起机场秩序混乱并带来额外的费用支出。为将这些费用计入考虑并方便进行对比，每个航班都定义了早到每分钟的惩罚和晚到每分钟的惩罚。下表1列出了每个航班的时间窗口（以从当天零时起分钟数计）和惩罚值。,15,表1：航班时间窗口等信息,由于尾流影响以及飞机停留在跑道上的时间影响，在两次降落之间需要间隔一段安全时间。在表2中第p和q降落之间需要等待的最短时间(分钟),即便这两个航班实际上不是连续降落的.应采取何种降落调度方案才能够在使总惩罚最小,同时航班又都在指定的时间窗口中降落,并且满足两个航班降落之间的时间间隔?,16,两个航班降落之间的时间间隔（分钟）,17,分析：设第i架飞机实际降落时间为xi,目标是惩罚值最小,ci惩罚值(由于早到惩罚和晚到惩罚一样)，mi目标到达时间,约束:实际到达时间界于最早到达与最晚到达之间,两架飞机降落时间的间隔大于等于要求时间间隔,18,最优方案,19,案例3：建筑工地上的人员规划,在建筑工地上负责架设高层建筑的钢结构的建筑工人称为钢结构安装工。下表列出了一个工地上在六个月内对钢结构安装工的需求人数。在每个月第一天可以从其他工地向此工地转移工人，每转移一个工人需要支出100元。在每月最后一天，工人可以离开去其他工地，此时每有一个工人离开需要支出160元。工人过多或过少都会带来额外支出，每缺员或冗员一人需要支出200元（如果人员不足出现缺员，则其他工人需要加班，因此有额外支出）。,表：每月钢结构安装工需求量,每天加班时间不能超过正常时间的25%,每个月至多只能新来三名工人.而根据与工会达成的协议,每个月离开此工地去其他工地的工人数不能超过总人数1/3,我们假定在二月底此工地上已经有了三名钢结构安装工,且在二月底没有人离开,并且要求在八月底此工地上仍然应有三名钢结构安装工,那么每个月到来和离开的工人数为多少才能使总成本最低?,20,分析:决策变量:设每月到来人数为xi,每月离开人数为yi,目标为总成本最少:,Si-1为上月末留下的人员,di为第i月需求人员,约束:每月至多能新来三名工人,每个月离开的工人数不能超过总人数的1/3,每天加班时间不能超过正常时间的25%,若冗员，此约束不起作用，若缺员，此约束才起作用,21,最优人员规划方案,22,一个具有非线性目标函数的模型，只要模型具有某些特征(如：线性约束、边际收益递减等)，使用可分离规划技术，Solver都可以很容易求出最优解。然而，如果一个问题具有边际收益递增或者具有非线性的约束，或者间断的利润曲线，求出最优解就会变得十分复杂：这样的问题可能存在很多局部最优解；suchproblemsmayhavemanylocaloptimaSolver可能只给出局部最优解，而不是全局最优解；解决这种问题的一种方法就是多次求解，每次求解时都尝试使用不同的初值：当决策变量只有一两个时，使用SolverTable能完成这种步骤。,非线性规划,10.4复杂的非线性规划问题,23,使用SolverTable尝试不同初值UsingSolverTabletoTryDifferentStartingPoints,非线性规划,24,EvolutionarySolver使用了与标准的Solver完全不同的搜索一个模型最优解的方法，EvolutionarySolver的原理是根据遗传学(genetics)、进化论(evolution)和适者生存原理(thesurvivalofthefittest)建立的，因此这种方法有时就称为遗传算法(GeneticAlgorithm),标准的Solver从一个初始点开始朝着优化的方向前进，EvolutionarySolver从随机产生的大量候选解(群体,population)开始并在求解过程中跟踪整个群体。,非线性规划,10.5EvolutionarySolver软件和遗传算法,EvolutionarySolver软件和遗传算法EvolutionarySolverandGeneticAlgorithms,25,标准Solver求解对下列问题有困难：高度非线性目标函数不光滑(有尖点)目标函数不连续具有很多局部最优(很多峰谷)Excel函数如IF,MAX,ABS,ROUND,etc.,EvolutionarySolver,26,安装“PremiumSolver”后，在Solver上会增加一个“Premium”按钮.,PremiumSolver,27,PremiumSolver,点击“Premium”按钮，出现三个不同选项StandardGRGNonlinearis等价于Solver中不选“AssumeLinearModel”.StandardSimplexLP等价于Solver中选择“AssumeLinearModel”.StandardEvolutionary等价于使用PremiumSolver中的遗传算法,28,选择高于市场收益的投资组合SelectingaPortfoliotoBeattheMarket,投资组合经理的一个普遍共同目标是获得高于市场的收益。如果我们假设过去的业绩在一定程度上是未来的指示器，那么挑选在过去收益通常高于市场的投资组合也可能就是在未来收益高于市场的投资组合。考虑在纽约证券交易所交易的5家大型股票：美国在线AmericaOnline(AOL)波音Boeing(BA)福特Ford(F)宝洁Procter&Gamble(PG)麦当劳McDonalds(MCD)问题:这些股票的如何构成一个投资组合在未来最有可能获得高于市场的收益？,7.非线性规划,实际举例5,29,30,31,非线性规划,32,EvolutionarySolver的优点和缺点AdvantagesandDisadvantagesofEvolutionarySolver,EvolutionarySolver求解非线性规划问题相对于标准的Solver有两个优点：不受目标函数的复杂性影响；不受局部最优解的影响。EvolutionarySolver的缺点.比标准Solver要花更长时间找到最终解；EvolutionarySolver对于有很多约束条件的模型效果不佳；EvolutionarySolver是一个随机的过程，重新运行相同的模型通常会产生不同的结果；最终解不一定是最优的。,非线性规划,33,案例10.2了解组合投资Tayor估计BB股票将会在明年从现在的每股50美元上涨到72美元；LOP股票会今年每股127美元的基础上上涨42%；ILI股票会从现在的每股4美元涨到8美元；HEAL会从现在的每股50美元增加到每股75美元；QUI会在现在的每股150美元的基础上上涨46%；AUA会从现在的每股20美元涨到26美元；五种股票的方差数据如下表：,34,协方差数据如下表:,35,a)一开始,莉迪亚希望忽视所有投资的风险。在这种情况下，她最优的投资组合决策是什么，也就是她在六种不同股票上分别投资多少？应该投资组合的风险是多少？,IfLydiawantstoignoretheriskofherinvestmentsheshouldinvestallhermoneyintothestockthatpromisesthehighestexpectedreturn.Accordingtothepredictionsoftheinvestmentadvisorstheexpectedreturnsequal20%forBigbell,42%forLotsofplace,100%forInternetlife,50%forHealthtomorrow,46%forQuicky,and30%forAutomobileAlliance.Therefore,sheshouldinvest100%ofhermoneyintoInternetlife.Therisk(variance)ofthisportfolioequals0.333.,36,b)莉迪亚认为不能在一种股票上投入超过总额的40%的资金，在不考虑风险并加入这一限制条件下，她的最优组合投资是什么，该投资组合的总风险又是多少？,Lydiashouldput40%ofhermoneyintothestockwiththehighestexpectedreturns,40%intothestockwiththesecondhighestexpectedreturns,and20%intothestockwiththethirdhighestexpectedreturns.Wecanalsofindthisintuitivesolutionbysolvingasimplelinearprogrammingproblem,inwhichwemaximizeMaxExpectedReturn=SUMPRODUCT(Portfolio,StockExpectedReturn)subjecttoTotal=OneHundredPercentPortfolioMaxInSingleStock,37,c)现在莉迪亚要将投资风险考虑在内。为了在下面几个问题中使用，建立一个二次规划模型，使她的风险最小，同时保证她的收益不低于她选择的最低可接受水平。,38,d)莉迪亚希望获得至少35%的预期收益，同时她又要保持最小的投资风险，在这种情况下，最优的投资组合是什么？ThereturnofLydiasportfolioisnolongerapartoftheobjectivebutnowbecomespartofanewconstraint:PortfolioExpectedReturn(C21)35%(MinimumExpectedReturn).Theobjectiveisnowtominimizetherisk.,39,e)如果莉迪亚要获得至少25%的预期收益，最小的投资风险是多少？至少40%的预期收益呢，情况又如何？,Sincethereturnconstraintinnotbindinginpartd,decreasingtheright-hand-sidewillnotchangetheoptimalsolution.Theminimumriskforaminimumexpectedreturnof25%isthesameasforaminimumexpectedreturnof35%(0.00136).,40,f)在莉迪亚的投资决策中，是否存在任何问题或不足？Lydiasapproachisveryrisky.Sheputsalotofconfidenceintheadviceofthetwoinvestmentexperts.Ofcourse,Lydiacannotexpecttofindanoptimalinvestmentstrategywithhermodeliftheestimatessheusesfortheinputparametersarewrong.,41,10.3案例跨国投资,查尔斯决定将30000德国马克投资在一种七年期的B债券上，债券的利率为,查尔斯是在四年前的上周（即讲座中的被称作“第一年”的1月初），购进这一债券的。他认为这个债券是一个很好的投资机会，因为利率很高，且会在后面的几年有所增加，而且在第一年之后，可以随时出售债券。,七年的利率,42,他计算了一下如果在七年当中任何一年出售最初价值为100马克的债券的话，可以获得的收益如下：,100德国马克的总回报,在前面四年中，查尔斯没有出售任何债券。但是去年德国联邦政府对利息收入加收了资本利益税。德国政府规定每年个人从利息中获得的6100德国马克是不用缴税的，超过6100德国马克部分的税率为30%。例如当查尔斯的利息收入为10100德国马克，他就必须支付4000德国马克（10100-6100）的30%，即120德国马克的税款。他的税后收入将为8900德国马克。,43,因为去年的利息税，查尔斯决心重新评估这项投资。他知道，资历本利益会影响B债券的潜在收益，但也可能存在能使收益最大的方案。如果在不同年份将部分债券售出的话，他可以减少需交的资本利息税。查尔斯认为这一计划是可行的，因为政府只要求投资者在出售时才支付利息收入的税款。例如，若查尔斯在第六年底售出1/3的债券，那么他要交的税额为（6351-6100）的30%。查尔斯问了自己好几个问题，是否应该将所有债券保持到第七年年底？这样的话，他可以得到总收入为300000.7823，但是那一年就必须付出高额的利息税。考虑到税款的支出，他想是否可以在今年（第五年）或者明年年底出售部分的债券。若查尔斯售出债券的话，他现在的投资选择是有限的。他可以购买利息为4%的存款单（CD），因此他将考察这一投资的回报。他碰到一位当地银行的投资顾问，顾问建议他继续持有B股票到七年年底再售出。她说虽然最后一年在原来的9%的利率上还要支付30%的利息税，总的净利率仍为6.30%,比存款单的收益要高得多.,44,a)建立可用于下面几题的可分离规划模型,b)查尔斯的最优投资策略是什么?,45,c)银行投资顾问给查尔斯提供的建议中有一个最基本的错误是什么?WhenCharlessellsallB-Bondsintheseventhyear,thenhemustpay30%oftaxesontheamountofinterestincomeexceedingDM6100.Thisamountisearnedinterestnotonlyfromthelastyear,butitincludesinterestfromallthepreviousyears.SoCharlesdoesnotpay30%taxonthe9percentinterestheearnedinthelastyear,butheeffectivelypaystaxonthetotalinterestofalltheyears.Thistaxpaymentdecreaseshisafter-taxinterestsomuchthatitpaysforhimtosellsomeofhisbondsinthesixthyearinordertotakeadvantageoftheyearlytax-freeincomeofDM6100.ComparethetotalamountofinterestCharlesearnsifhesellstax-freeafter