最优化理论与算法完整版课件

TPSHUAI,1,最优化理论与算法,TPSHUAI,2,提纲,1.线性规划对偶定理2.非线性规划K-K-T定理3.组合最优化算法设计技巧,使用教材：最优化理论与算法陈宝林参考书：数学规划黄红选，韩继业清华大学出版社,TPSHUAI,3,其他参考书目,NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley牛顿,1670,欧拉,1755,Minf(x1x2xn)f(x)=0,TPSHUAI,9,欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法,拉格朗日，1797,Minf(x1x2xn)s.t.gk(x1x2xn)=0,k=1,2,m,TPSHUAI,10,1930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划6-70年代：Cook等复杂性理论，组合优化迅速发展,电子计算机-最优化,TPSHUAI,11,最优化应用举例,具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）,TPSHUAI,12,1.食谱问题,我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。,TPSHUAI,13,1.食谱问题（续）,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。,Min3x+2.5ys.t.2x+4y403x+2y50 x,y0.,极小化目标函数可行区域（单纯形）可行解,TPSHUAI,14,2运输问题,设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题。,TPSHUAI,15,令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：,2运输问题（续）,TPSHUAI,16,以价格qi购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：501000-0.3(50-30)1000-0.1501000=39000,3税下投资问题,TPSHUAI,17,我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。,3税下投资问题（续）,TPSHUAI,18,4选址问题（1）,实例:一组潜在位置（地址）,一组顾客集合及相应的利润和费用数据；解:设施开放(使用)的数目，他们的位置，以及顾客被哪个设施服务的具体安排方案；目标：总的利润最大化。,数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提供.,TPSHUAI,19,4选址问题（2）,TPSHUAI,20,4选址问题（3）,TPSHUAI,21,5负载平衡(1),实例:网络G(V,E)及一组m个数的集合s,d0，表示连接源点s与汇点d之间的流量解:s,d0的一组路由,即G(V,E)中m条s与d间的路,表示连接s与d的负载流量的路径。目标:极小化网络负载,TPSHUAI,22,5负载平衡(2),TPSHUAI,23,6.结构设计问题,两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,TPSHUAI,24,6.结构设计问题,TPSHUAI,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,6.结构设计问题,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：,6.结构设计问题,TPSHUAI,28,基本概念,在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,TPSHUAI,29,基本概念,最优化问题可写成如下形式:,TPSHUAI,30,基本概念,Df1.1设f(x)为目标函数，S为可行域，x0S,若对每一个xS,成立f(x)f(x0),则称x0为极小化问题minf(x),xS的最优解（整体最优解）,则称x0为极小化问题minf(x),xS的局部最优解,Df1.2设f(x)为目标函数，S为可行域，,TPSHUAI,31,Thankyouverymuchforyourattendance!,优化软件//neos/solvers/index.html,TPSHUAI,32,最优化理论与算法,帅天平北京邮电大学数学系Email:tpshuai,Tel:62281308,Rm:主楼8141预备知识,TPSHUAI,33,1，预备知识,1.线性空间2.范数3.集合与序列4.矩阵的分解与校正,TPSHUAI,34,1.线性空间,Df1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群(,3.线性规划-单纯形方法4,于是我们有如下定理：,3.1.线性规划-单纯形方法5,由上知,要减少费用,只有当C0时才可能，即,3.1线性规划-单纯形方法6,令y=x+d,0,我们能降低费用吗？,3.1线性规划-单纯形方法7,3.1线性规划-单纯形方法8,3.1线性规划-单纯形方法9,正确性如何？显然按上述取法，是可以保证y0的。y还是基本可行解吗？,3.1线性规划-单纯形方法10,3.1线性规划-单纯形方法11,单纯形法,3.1线性规划-单纯形方法12,Th3.4(单纯形法的收敛性）对于相容的非退化(每个基可行解都是非退的)LP问题，那么经过有限次迭代后，单纯形法或者得到最优的BFS(最优可行基B）或有一个方向d:且最优的费用为-.,3.1线性规划-单纯形方法13,例1,3.1线性规划-单纯形方法14,3.1线性规划-单纯形方法15,3.1线性规划-单纯形方法16,3.1线性规划-单纯形方法17,3.1线性规划-单纯形方法18,3.1线性规划-单纯形方法19,新的基为B=(A1,A3,A4,A7),3.1线性规划-单纯形方法20,3.1线性规划-单纯形方法21,新的基为B=(A3,A4,A5,A7),3.1线性规划-单纯形方法22,利用分块矩阵,表格形式的单纯形方法,3.1线性规划-单纯形方法23,3.1线性规划-单纯形方法24,3.1线性规划-单纯形方法25,进基变量,离基变量,旋转元,右端向量,返回,单纯形表,例2：求解线性规划问题,化成标准化形式,3.1线性规划-单纯形方法26,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1/2,0,1,-1/2,7/0.5,1,1/2,1,0,1/2,18/0.5,x2,7,18,1,1/2,1/2,x5,x6离基，,x2进基，,x5离基，,x1进基，,3.1线性规划-单纯形方法27,0,-4,-2,-2,-1,-86,0,1,0,2,-1,1,0,1,-1,1,14,11,0,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）minz=-86，maxz=86,1,3.1线性规划-单纯形方法28,例3：求解线性规划问题,3.1线性规划-单纯形方法29,3.1线性规划-单纯形方法30,x3进基，x6离基,3.1单纯形方法31,初始单纯型表,最优单纯型表,3.2两阶段法con1x1+0.25*x4-8*x5-x6+9*x7=0;con2x2+0.5*x4-12*x5-0.5*x6+3*x7=1;con3x3+x6=1;end,3.3退化情形18,1，修正单纯形方法2，逆的乘积形式,3.4修正单纯形方法,1，修正单纯形方法,3.4修正单纯形方法-1,回忆单纯形方法，不妨设初始单纯形表中系数矩阵含有单位阵，即系数矩阵为,3.4修正单纯形方法-2,3.4修正单纯形方法-3,这样，有了初始表(即问题的系数矩阵，费用向量和右端向量子集组成)，当前表*和基B，则修正单纯形方法就可进行下去了,3.4修正单纯形方法4,修正单纯形方法,4)把主列置于逆矩阵表的右边，组成下列表,3.4修正单纯形方法5,例3.4.1，用修正单纯形法解下列LP,3.4修正单纯形方法-6,约束方程的系数矩阵,3.4修正单纯形方法-7,第1次迭代：,3.4修正单纯形方法-8,第二次迭代,3.4修正单纯形方法-9,计算主列,3.4修正单纯形方法-10,3.4修正单纯形方法-11,计算主列,3.4修正单纯形方法-12,第4次迭代,3.4修正单纯形方法-13,2逆的乘积形式初看起来，用修改的(m+1)(m+1)矩阵代替(m+1)(n+1)的表，似乎明显的节省了计算量。然而这一方法需要计算原问题表中的yj和wpj，若对每一个非基序列都要进行这样的计算，则需要m(n-m)次乘法。这个数量并不明显小于原单纯形算法中计算量。然而这个算法重要性在于其精巧和在其他一些问题上的很好应用。下面我们将给出一种改进形式的方法，其基的逆矩阵以乘积形式存储，从而节省了存储空间。,3.4修正单纯形方法-14,3.4修正单纯形方法-15,由(3.4.8)式得到,由于,3.4修正单纯形方法-16,3.4修正单纯形方法-17,下面讨论如何利用初等阵来计算单纯形方法中所需数据。,3.4修正单纯形方法-18,(1)用初等阵E右乘一个行向量,(2)用E左乘一个列向量,3.4修正单纯形方法-19,(3)计算有关递推公式,3.4修正单纯形方法-20,例3.4.2，用改进修正单纯形法解LP,3.4修正单纯形方法-21,约束方程的系数矩阵,3.4修正单纯形方法-22,3.4修正单纯形方法-23,第二次迭代,3.4修正单纯形方法-24,计算主列,3.4修正单纯形方法-25,3.4修正单纯形方法-26,第3次迭代,最优化理论与算法,帅天平北京邮电大学数学系Email:tpshuai,Tel:62281308,Rm:主楼8145，对偶理论与灵敏度分析,第四章对偶理论与灵敏度分析,对偶理论对偶单纯形法原始-对偶算法灵敏度分析,4.对偶问题,重新考虑食谱问题。以出售奶和蛋给需要维生素的人的食品杂货商的利益出发，他知道奶和蛋按其维生素Vc和Vb的含量而有一定的价值。他的问题是确定出售维生素Vc的价格x和维生素Vb的价格y：他不能将价格订得高于奶和蛋的市场流行价，否则将失去他的顾客；他希望商店的总收入为最大。,4.对偶问题（续一）,Max40 x+50ys.t.2x+3y34x+2y2.5x,y0.,极大化目标函数可行区域（单纯形）可行解,Min3x+2.5ys.t.2x+4y403x+2y50 x,y0.,极小化目标函数可行区域（单纯形）可行解,4.对偶问题（续二）,对比一下从消费者和供应商各自的利益导出的两个问题，我们不难发现两个问题可以通过下述简单的变换，而相互转化：,当你把食谱问题的对偶问题解出以后（练习），你会发现一个（重要的）事实：这两个问题的最优值是相等的！,思考题：在数学上，是不是还有一些对偶的问题和概念？,4.对偶理论1,4.1LP的对偶理论,PrimalMincxs.t.Axb,(4.1.1)x0,DualMaxwbs.t.wAc,(4.1.2)w0,4.1.1对偶问题的表达,1,对称形式的对偶,2,非对称形式的对偶,4.对偶理论2,3,一般形式的对偶,Primal,化为等价的标准形式,4.对偶理论3,写成矩阵形式,按非对称对偶的定义,得上述LP的对偶问题,4.对偶理论4,于是原LP的对偶,(Dual),4.对偶理论5,以上分析可知有如下关系,4.对偶理论6,引理1对偶问题的对偶是原始问题(Thedualofthedualistheprimal.),4.对偶理论7,即得原问题,4.对偶理论9,例4.1.2设原问题,4.对偶理论10,例4.1.2设原问题,4.对偶理论11,例4.1.3设原问题,4.对偶理论12,于是可得对偶问题,4.对偶理论13,5.1.2对偶定理注意到,原问题和对偶问题是由同一数据集(A,b,c)所定义，且对偶问题的对偶即是原问题，因此可以选原始-对偶对中任一为原问题，而另一则自动为对偶。下面讨论两者间的关系。,4.对偶理论14,推论2对偶规划(4.1.1)和(4.1.2)有最优解的充要条件是它们同时有可行解。推论3若原问题(4.1.1)的目标函数值在可行域上无下界,则其对偶问题无可行解;反之,若对偶(4.1.2)的目标函数值在可行域上无上界,则原问题无可行解.,5.对偶理论,4.对偶理论15,定理4.1.2设(4.1.1)和(4.1.2)中有一个问题存在最优解，则另一个问题也存在最优解，且这两个问题的最优目标函数值相等。,证明：设(4.1.1)存在最优解。引进松弛变量，将（4.1.1）写成等价形式：,4.对偶理论16,由于(4.1.12)存在最优解，因此能用单纯形方法求得一个最优基本可行解。不妨设此最优解为,相应的最优基为B.此时所有判别数满足：,4.对偶理论17,即,把所有松弛变量在基下对应的判别数所满足的条件(4.1.13)用矩阵表示,得,4.对偶理论18,4.对偶理论19,4.1.3互补松弛性质,4.对偶理论20,4.对偶理论21,例4.1.3求解如下LP,4.对偶理论22,4.对偶理论23,4.对偶理论对偶单纯形法1,4.2对偶单纯形法4.2.1对偶单纯形法基本思想,4.对偶理论对偶单纯形法2,注:对偶可行的基本解不一定是原问题的可行解.若还是原问题的可行解,则此解即为最优解.,回忆(修正)单纯形法的基本思路是保持原问题的可行性和互补松弛条件下,在它的最优解上寻求对偶问题的可行性.,类似的,对偶单纯形法的基本思路是:在保持对偶可行性和互补松弛条件下,在它的最优解上寻求原问题的可行性.,4.对偶理论对偶单纯形法3,4.对偶理论对偶单纯形法4,下面分析如何选取离基变量和进基变量.设在某次迭代中得到如下表:,4.对偶理论对偶单纯形法5,4.对偶理论对偶单纯形法6,4.对偶理论对偶单纯形法7,下面说明上述转换能改进对偶可行的基本解.,2)主元消去后仍然保持对偶可行性,即所有判别数都小于或等于0(对极小化问题),4.对偶理论对偶单纯形法8,4.对偶理论对偶单纯形法9,即对偶问题的目标函数值在迭代过程中单调增(非减).,对偶问题的可行解w越来越接近最优解.原问题的对偶可行的基本解将向着满足可行性方向转化而接近原问题最优解.,4.对偶理论对偶单纯形法10,4.对偶理论对偶单纯形法11,例1,4.对偶理论对偶单纯形法12,4.对偶理论对偶单纯形法13,4.对偶理论对偶单纯形法14,4.对偶理论对偶单纯形法15,4.对偶理论对偶单纯形法16,4.2初始对偶可行的基本解,对偶单纯形法中要求先给出一个初始的对偶可行的基本解.这个解未必直接能求出,因此需要引进一个方法与单纯形法中类似,我们也是通过解一个辅助问题-扩充问题来求解.扩充问题的构造,扩充问题的构造:先给出(4.2.1)的一个基本解(这很容易).不妨设A的前m列线性无关,由这m列构成基矩阵B.于是(4.2.1)可改写成,4.对偶理论对偶单纯形法17,4.对偶理论对偶单纯形法18,在(4.2.10)中以系数矩阵的前m列和第n+1列组成的m+1阶单位矩阵为基,则得一个基本解,4.对偶理论对偶单纯形法19,上述做法是正确的,因为主元消去运算前后判别数之间有如下关系:,综上立明,4.对偶理论对偶单纯形法20,注意到(4.2.10)的对偶问题有可行解,故用对偶单纯形方法求解(4.2.10)时,仅有如下两种情况发生:,(1)扩充问题无可行解,则原问题亦无可行解.(反证),4.对偶理论对偶单纯形法21,例2.2,4.对偶理论对偶单纯形法22,于是得扩充问题,构作单纯形表,4.对偶理论对偶单纯形法23,4.对偶理论对偶单纯形法24,4.对偶理论对偶单纯形法25,例2.3,4.对偶理论对偶单纯形法26,把约束矩阵置于单纯形表中,4.对偶理论对偶单纯形法27,4.对偶理论对偶单纯形法28,4.对偶理论对偶单纯形法29,4.3原始对偶算法1,基本思想这一方法实际上是由某些网络问题的一个特殊算法发展起来的.,构造对偶问题,考虑原问题,互补松弛条件是:如果x和分别是P和D的可行解,则它们是最优解的充要条件是对一切的i和j有,由于P是标准形式,故对任意可行解x,(1)总是成立的,4.3原始对偶算法2,下面我们集中讨论关系式(2)假定是对偶问题D的可行解,若能设法找出P的一个可行解x,使得满足关系式(2),即,则这个x(及)是最优的,4.3原始对偶算法3,对给定求这样一个x的思想,导致了原始对偶算法.给定,要找这样一个x,可以通过解由所确定的辅助问题(称为限制的原始问题RP)而得到.当这样的x没有搜索到,那么就得到RP的对偶信息(RP的对偶记为DRP),此信息告诉我们如何修改,于是得到新的.重复此过程,在有限步内就收敛到最优解,4.3原始对偶算法4,算法开始时是D的可行解且始终保持对偶可行性.在c0时可直接取=0为初始对偶可行解.当c不是非负的时候,应用Beale等人的方法很容易的找出可行解:,4.3原始对偶算法5,原始对偶算法,显然增加约束后不会改变原问题P的解,此时新的原始问题的对偶为,4.3原始对偶算法6,中将有一些取严格不等式,而另一些取等式.设取等式的约束指标集为J:,4.3原始对偶算法7,因此不妨设D有一可行解,则不等式约束,这即相当于求一个x,使得满足,4.3原始对偶算法8,称J为允许列集合.为找出这样的x,构造新的LP,称为限制的原始问题(RP):,利用单纯形法求解此RP:若最优值为0则已找到(6)的解,因此也是P的最优解.若最优值大于0,如何处理?,4.3原始对偶算法9,为解决此问题,需要考察限制的原始问题RP的对偶DRP,4.3原始对偶算法10,现在我们处于这样的情形:试图只应用允许列来找出一个可行解x,但由于RP的最优值0,所以努力失败了,这就可能考察利用原来的和新得到的来校正,4.3原始对偶算法11,因为RP和DRP是一对相互对偶的规划,所以它们的最优值相等.因此有,但是我们得到了RP的最优解及其对偶的最优解,所以我们应该选取0,从而改进D的费用,4.3原始对偶算法12,为维持可行性,只需考察下述不等式,4.3原始对偶算法13,此时,可行性准则变为,于是有,4.3原始对偶算法14,当解限制的原始问题并达到了改进D的解的时候,我们重新定义集合J,然后重复上述过程直到或者opt=0并因此得到P的最优解,或者由定理1知P无可行解.,Procedureprimal-dual,4.3原始对偶算法15,begininfeasible:=no,opt:=noletbefeasibleinD(comment:possibleby(3);whileinfeasible:=noandopt:=nodobeginsetsolveRPbythesimplexalgorithmifopt=0thenopt:=yeselseiftheninfeasible:=yeselseendend,4.3原始对偶算法16,我们运用表格形式进行迭代。初始表结构如下：,此表中原来变量xj中仍属于限定问题中.即jJ,则用在上方标注.解RP的进离基运算在标的列和y的列进行,限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可,4.3原始对偶算法17,4.3原始对偶算法18,“限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可”的理由,下面求解上述LP。首先找出对偶问题的一个可行解。例4.3.1的对偶是：,4.3原始对偶算法19,于是得一阶段问题,显然w=(0,0)是一个可行解，此时有,4.3原始对偶算法20,变量上方的标识符表示该变量属于RP,4.3原始对偶算法21,按照前述给定的格式，得初表如下,4.3原始对偶算法22,4.3原始对偶算法23,J=2,用单纯形法解RP：x2进基,y1离基.经主元消去得下表(注：解RP时第4行不变）,RP的判别数均非正,达到最优，Z0=20修改对偶问题的可行解,4.3原始对偶算法24,此时J=1，2，再解RP：x1进基，y2离基.经主元消去得下表,4.3原始对偶算法25,RP问题达到最优，最优值Z0=0，因此得原问题的最优解x*=(x1,x2,x3)=(2,1,0)目标函数的最优值fmin=5,对偶问题的最优解w=(0,1).,335,4.4灵敏度分析,1，引入2，改变系数向量3，改变右端向量4，改变约束矩阵5，增加新的约束,336,前面讲的线性规划问题中，都假定问题中是已知常数。但实际上这些数往往是一些估计和预测的数字,市场条件变化，价值变量cj就会变化,aij是随工艺技术条件的改变而改变,而值bi则是根据资源投入后能产生多大经济效益来决定的一种决策选择.,在大多数实际问题中。不仅要求求出问题的最优解，而且还希望知道当问题中的某些参数改变时最优解怎样变动。参数的变化可分为离散的和连续的两种。灵敏度分析是指对系统或事物因周围条件离散变化显示出来的敏感程度的分析，即对最优解的影响进行分析研究。而参数规划则是研究参数连续的变化时对最优解的影响,1引入,337,这就是灵敏度分析所要研究解决的问题。,因此就会提出以下问题：,当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化?,这些参数在一个多大范围内变化时，问题的最优解变不变?,影响最优解的参数有如下几类：改变费用系数cj改变右端费用bi改变约束方程的系数矩阵A加入新的约束,参数变化后的结果最优解不变：最优基及其取值不变基变量不变但取值改变基变量改变，取值亦改变,338,重新解新线性规划问题？,重新计算发生变化的个别系数,判断问题现状,采取如下措置,339,考虑标准LP问题为,RHS,0,假定得到最优单纯形表如下,(4.4.1),2改变系数向量c,340,当价值向量c改变时,在单纯形表里受影响的只是检验数,和目标函数值，其它没有改变，,因而只需计算新的检验数,和目标函数值,如果检验数非正，则原最优解依然是最优解；,否则是基本可行解，,以此为初始基可行解按单纯形法进行迭代,就可以求出新问题的解。,341,1、情形I:是非基变量,改变非基变量的价值向量：,若，,由单纯形法计算公式知，只有检验数起变化,则原最优解依然是最优解；,否则,由此进行单纯形迭代。,即价值向量只有一个分量,新的检验数,342,2、情形II:是基变量,基变量对应的约束为第L个,即,改变基变量的价值向量,问题最后一张单纯形表中，,新检验数(因基变量检验数要求0),新目标函数值,把单纯形表上的第L行元素乘以加到检验数行上，,总之,343,例1,最优解:(x1,x2,x3,x4,x5,x6)=(5,3,1,0,0,0),344,检验数仍非负,问题原最优解仍是此时最优解;,更多信息:,对非基变量的价值系数在某范围变化最优解都不发生改变,最优解都不发生改变,最优解都不发生改变,同理,最优解都不发生改变,非基变量,345,若检验数向量非负数，而右端向量没变，故仍最优解，,否则用单纯形算法即可。,基变量,把最优单纯形表的第3行乘以1-(-1)加到检验数行上,再令,得到对应新问题的单纯形表,346,1.基本思想,如果，则已发现新问题的最优解，,否则利用对偶单纯形算法求解新问题。,3改变右端向量b,347,其中为的第r列。,当只改变一个分量时：,如果，则已发现新问题的最优解.,因新问题的单纯形表检验数向量不变，,仍有,否则，单纯形表对应新问题的一个基本(不可行)解和,故可用对偶单纯形法继续求解。,对偶问题的一个可行解，,348,b3由3变成5时，,续上例,仍是最优基本可行解。,349,b3由3变成11时，,单纯形表对应新问题的一个基本(不可行)解和,故可用对偶单纯形法继续求解。,对偶问题的一个可行解，,此时单纯形表,350,4改变约束矩阵A,有如下两种情形,351,此时情况较复杂，若只有少数列发生变化可用如下方法,352,353,5加入新的约束,设原有约束为Ax=b，在此基础上，我们增加一个新的约束,(2)若原问题的最优解不满足新的约束，则需要把新的约束条件增加到原来的最优表中再解新问题。,设原来的最优基为B。最优解为,354,355,356,357,358,359,360,361,362,总结:,当原问题只有个别数据改变,特别是变化幅度不大时,用灵敏度分析比对新问题重新求解简单,在现实中市场因素(价值系数),生产资料(右端向量),生产技术(矩阵元素)随时在变化,而参数的变化必然引起模型的变化,最优化理论与算法,帅天平北京邮电大学数学系Email:tpshuai,Tel:62281308,Rm:主楼8147，最优性条件,第七章最优性条件,无约束问题的极值条件约束极值问题的最优性条件对偶及鞍点,7.1无约束问题的极值条件,考虑非线性规划问题,1，无约束极值问题,称为无约束极值问题（UNLP）,7.最优性条件-无约束1,7.最优性条件-无约束2,Th7.1.1(非极小点的充分条件)设f(x)在点x*处可微,若存在方向d(0)Rn,使得f(x*)d0,使得对任意(0,),有f(x*+d)f(x*).此时,我们称d为f(x)在x*的一个下降方向.,证明.由f(x)在x*可微,则f(x*+d)=f(x*)+f(x*)d+|d|(x*;d),其中(x*;d)0(当0).,2，必要条件,7.最优性条件-无约束3,移项且两边同除以(0),得（f(x*+d)f(x*)）/f(x*)d+|d|(x*;d)由于f(x*)d0使得对任意(0,),f(x*)d+|d|(x*;d)0.定理立明.,定理7.1.2-3(极小点的必要条件)设x*处是问题(UNLP)的局部极小点.当f(x)在x*可微时,则梯度f(x*)=0.当f(x)在x*二次可微时.则f(x*)=0且Hessian矩阵H(x*)是半正定的,7.最优性条件-无约束4,证明(1).若f(x*)0,作d=f(x*).则有f(x*)d0使得f(x*+d)0使得f(x*+d)f(x*)（(0,)）,则d称为f(x)在x*的下降方向(decedentdirection),设f(x)在x*可微.若存在向量d满足f(x*)d0,则由Th7.1.1,d是f(x)在x*.的下降方向。记所有这样的向量集合为,7.最优性条件-有约束3,由可行方向定义和下降方向知，从点x*,沿可行方向dD(x*)作一个很小的移动还是可行点.进一步，由Th7.1.1,若f(x*)d0，则d是f在x*的下降方向。下面定理将说明若x*是局部最优且f(x*)d0.iI在x*处不起作用约束G0(x*)=d|gi(x*)d0,iI.,380,7.最优性条件-不等式约束2,证明概要.设dG0(x*).因S为开集，则存在10使得对(0,1)，x*+dS。另外存在20使得对(0,2)，iI.gi(x*+d)0,最后存在30使得对任意(0,3)andiI有gi(x*+d)gi(x*),从而dD,D是x*处的可行方向锥.于是G(x*)D.由Th7.2.1,立明。,Th7.2.2.(必要条件)考虑极小化问题minf(x)subjecttogi(x)0，i=1,m，xS,其中S是Rn中的非空开集。设x*为可行点，I=i|gi(x*)=0.进一步假设，f(x)和gi(x)（iI）在x*可微，gi（iI）在x*连续.若x*是局部最优解，则F0(x*)G0(x*)=,其中F0(x*)=d|f(x*)d0，iI.,7.最优性条件-不等式约束3,7.最优性条件-不等式约束4,x*=(2,1)g1(x*)=(-4,-2),g2(x*)=(-1,-1),f(x*)(-2,-2),7.最优性条件-不等式约束5,384,7.最优性条件-不等式约束6,证明.由Th7.2.2,不存在向量d同时满足f(x*)d0和gi(x*)d0.,7.最优性条件-不等式约束12,7.最优性条件-不等式约束13,Karush-Kuhn-Tucker条件可写成向量形式f(x*)-ug(x*)=0,ug(x*)=0,u0.,这表明f(x*)属于起作用约束的这些约束的梯度所形成的锥中。,7.最优性条件-不等式约束14,7.最优性条件-不等式约束15,7.最优性条件-不等式约束16,7.最优性条件-不等式约束17,396,7.最优性条件-不等式约束18,Th7.2.5.(Karush-Kuhn-Tucker充分条件)考虑极小化问题minf(x)subjecttogi(x)0，i=1,m，xS,其中S是En.中非空开集.设x*为可行点,I=i|gi(x*)=0.设f(x)和诸gi是凸的，进一步假设f(x)和gi(x)(iI)在x*可微,gi(iI)在x*连续.若K-K-T条件在x*成立，则x*是全局最优解.,证明略,7.最优性条件-等与不等式约束1,4.一般约束问题的一阶最优性条件,记,7.最优性条件-等与不等式约束2,7.最优性条件-等与不等式约束3,7.最优性条件-等与不等式约束4,证明略,7.最优性条件-等与不等式约束5,7.最优性条件-等与不等式约束6,7.最优性条件-等与不等式约束7,7.最优性条件-等与不等式约束8,7.最优性条件-等与不等式约束9,7.最优性条件-等与不等式约束10,现定义两集合,7.最优性条件-等与不等式约束11,7.最优性条件-等与不等式约束12,例:,7.最优性条件-等与不等式约束13,例,7.最优性条件-等与不等式约束14,7.最优性条件-等与不等式约束15,KKT最优性必要条件（Th2.4）加以推广。这是通过增加约束规格来实现的.,前面FJ条件中w0不一定为正,在下面定理中。我们将前面提到的,7.最优性条件-等与不等式约束16,若采用矩阵和向量记号,则KKT可如下简洁表示,7.最优性条件-等与不等式约束17,则KKT条件可表为,7.最优性条件-等与不等式约束18,7.最优性条件-等与不等式约束19,7.最优性条件-等与不等式约束20,5.二阶条件,7.最优性条件-等与不等式约束21,为此,我们考虑函数的二阶导数,首先给出如下定义,7.最优性条件-等与不等式约束22,例,7.最优性条件-等与不等式约束23,7.最优性条件-等与不等式约束24,现在我们考虑问题(7.2.1).,7.最优性条件-等与不等式约束25,7.最优性条件-等与不等式约束26,7.最优性条件-等与不等式约束27,7.最优性条件-等与不等式约束28,7.最优性条件-等与不等式约束29,7.最优性条件-等与不等式约束30,7.最优性条件-等与不等式约束31,7.最优性条件-等与不等式约束32,为给出局部最优解的二阶充分条件，我们定义集合,7.最优性条件-等与不等式约束33,7.最优性条件-等与不等式约束34,7.最优性条件-等与不等式约束35,下面分两种情况讨论,7.最优性条件-等与不等式约束36,7.最优性条件-等与不等式约束37,7.最优性条件-等与不等式约束38,7.最优性条件-等与不等式约束39,例7.2.7考虑下列非线性规划问题,检验以下各点是否为局部最优解,7.最优性条件-等与不等式约束40,记目标函数和约束函数分别为f(x),g(x),h(x),他们在点x处的梯度分别是,Lagrange函数是,Lagrange函数关于x的Hessian矩阵是,7.最优性条件-等与不等式约束41,7.最优性条件-等与不等式约束42,7.最优性条件-等与不等式约束43,后两点请自行验证之,7.最优性条件-等与不等式约束44,例7.2.8考虑下列非线性规划问题,记目标函数和约束函数分别为f(x),h(x),他们在点x处的梯度分别是,7.最优性条件-等与不等式约束45,例,7.最优性条件-等与不等式约束46,7.最优性条件-等与不等式约束47,Ch7.3对偶理论1,7.3.1对偶形式,Ch7.3对偶理论2,其对偶形式(对偶问题)定义如下,Ch7.3对偶理论3,于是(LP)问题(*)的对偶形如,Ch7.3对偶理论4,Ch7.3对偶理论5,7.3.2对偶定理,对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即,1.弱对偶定理,Ch7.3对偶理论6,Ch7.3对偶理论7,2.凸规划与Slater约束规格,Ch7.3对偶理论8,Ch7.3对偶理论9,3.强对偶定理,Ch7.3对偶理论10,证明:先证第一部分:(1)无解=(2)有解.令集合,Ch7.3对偶理论11,Ch7.3对偶理论12,Ch7.3对偶理论13,Ch7.3对偶理论14,例考虑如下约束优化问题,显然该问题无最优解,但目标函数的下确界fmin=0.该问题的Lagrange对偶函数,Ch7.3对偶理论15,7.3.3鞍点定理,Ch7.3对偶理论16,1鞍点与最优解,Ch7.3对偶理论17,Ch7.3对偶理论18,对于(2),在假设条件成立时,根据强对偶定理5.11,对于问题(PNLP)的最优解,存在,使得,Ch7.3对偶理论19,2.鞍点与KKT点,最优化理论与算法,帅天平北京邮电大学数学系Email:tpshuai,Tel:62281308,Rm:主楼8148，算法,第八章算法,算法概念算法收敛问题,ch8算法-概念,8.1.1算法映射,下降，即对某个函数，在每次迭代中后继点处的函数值要有所减小。,迭代下降算法,考虑极小化问题f(x)s.t.xS这里f是目标函数，S是可行域。对于求解这一问题的解答程序或算法可以看作是一个迭代过程，这过程按照规定的一组指令和终止准则一起产生一个点序列。,ch8算法概念,Df8.1.1算法A是定义在空间X上的点到集映射,即对每一个点xX,给定一个子集A(x)X.,Ch8算法-概念,ch8算法概念,如图所示,应用算法A时,经A作用得到一个闭区间,从此区间中任取一点作为后继点,重复这个过程,得一由算法产生得点列,在一定条件下,它收敛于问题的解.如3,2,3/2,5/4,3,3/2,9/8,33/32,etc.,ch8算法概念,8.1.2解集合,为了求解上述问题，要求使用的算法具有这样的性质：由算法产生的点列收敛于整体最优解然而，在许多情形下，要满足这一点很难做到。事实上由于非凸性，问题的规模和其它一些困难，达到整体最优几乎不可能，因此当达到属于预定集的某一点达到，则可以停止迭代，这个预定集就称之为解集合常用的解集