最优化理论与算法完整版.ppt

TP SHUAI,1,最优化理论与算法,TP SHUAI,2,提纲,1.线性规划 对偶定理2.非线性规划 K-K-T 定理3.组合最优化 算法设计技巧,使用教材：最优化理论与算法 陈宝林参考书：数学规划 黄红选，韩继业 清华大学出版社,TP SHUAI,3,其他参考书目,Nonlinear Programming-Theory and AlgorithmsMokhtar S.Bazaraa,C.M.ShettyJohn Wiley&Sons,Inc.1979(2nd Edit,1993，3nd Edit，2006),Linear and Nonlinear Programming David G.LuenbergerAddison-Wesley Publishing Company,2nd Edition,1984/2003.,TP SHUAI,4,Linear Programming and Network Flows M.S.Bazaraa,J.J.Jarvis,John Wiley&Sons,Inc.,1977.,运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999,组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/1998,其他参考书目,TP SHUAI,5,1,绪论-学科概述,最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.,运筹学的“三个代表”模型理论算法,最优化首先是一种理念,其次才是一种方法.,TP SHUAI,6,绪论-运筹学（Operations Research-OR）,TP SHUAI,7,优化树,TP SHUAI,8,最优化的发展历程,费马:1638;牛顿,1670,欧拉,1755,Min f(x1 x2 xn)f(x)=0,TP SHUAI,9,欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法,拉格朗日，1797,Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m,TP SHUAI,10,1930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展,电子计算机-最优化,TP SHUAI,11,最优化应用举例,具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版（TEX,Latex,etc.）,TP SHUAI,12,1.食谱问题,我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。,TP SHUAI,13,1.食谱问题（续）,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,极小化目标函数可行区域（单纯形）可行解,TP SHUAI,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问怎样调运这些物品才能使总运费最小？,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题。,TP SHUAI,15,令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：,2 运输问题（续）,TP SHUAI,16,以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=39000,3 税下投资问题,TP SHUAI,17,我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。,3 税下投资问题（续）,TP SHUAI,18,4 选址问题（1）,实例:一组潜在位置（地址）,一组顾客集合及相应的 利润和费用数据；解:设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。,数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.,TP SHUAI,19,4 选址问题（2）,TP SHUAI,20,4选址问题（3）,TP SHUAI,21,5负载平衡(1),实例:网络G(V,E)及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解:s,d0的一组路由,即G(V,E)中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。目标:极小化网络负载,TP SHUAI,22,5 负载平衡(2),TP SHUAI,23,6.结构设计问题,两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,TP SHUAI,24,6.结构设计问题,TP SHUAI,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,6.结构设计问题,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：,6.结构设计问题,TP SHUAI,28,基本概念,在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,TP SHUAI,29,基本概念,最优化问题可写成如下形式:,TP SHUAI,30,基本概念,Df 1.1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x),x S的最优解（整体最优解）,则称x0为极小化问题min f(x),x S的局部最优解,Df 1.2 设f(x)为目标函数，S为可行域，,TP SHUAI,31,Thank you very much for your attendance!,优化软件,TP SHUAI,32,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼814 1 预备知识,TP SHUAI,33,1，预备知识,1.线性空间2.范数3.集合与序列4.矩阵的分解与校正,TP SHUAI,34,1.线性空间,Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群(&交换群),TP SHUAI,35,1.线性空间,Df 1.4:给定一非空集合V和一个域F,并定义两种运算加法+:VVV以及数乘:FVV.若构成一交换群,且两种运算满足下面性质:,则称V在域F上关于加法和数乘 运算构成一线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.,TP SHUAI,36,1.线性空间,例子,TP SHUAI,37,1.线性空间,TP SHUAI,38,1.线性空间,Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是V中包含S的最小子空间.,TP SHUAI,39,1.线性空间,TP SHUAI,40,1.线性空间,TP SHUAI,41,2.范数,TP SHUAI,42,2.范数,TP SHUAI,43,2.范数,TP SHUAI,44,3.集合与序列,TP SHUAI,45,3，集合与序列,TP SHUAI,46,3.集合与序列,TP SHUAI,47,3.集合与序列,TP SHUAI,48,4.矩阵的分解与校正,Th1.5 若n阶矩阵A可逆，则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LU,TP SHUAI,49,4.矩阵的分解与校正,Th1.6 设A为对称正定矩阵，则（1）矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵，D为对角矩阵（2）存在可逆的下三角矩阵L，使得A=LLT.当L的对角元素为正时，分解是唯一的。(Cholesky分解),TP SHUAI,50,4.矩阵的分解与校正,TP SHUAI,51,4.矩阵的分解与校正,TP SHUAI,52,5.函数的可微性与展开,TP SHUAI,53,5.函数的可微性与展开,当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为,TP SHUAI,54,5.函数的可微性与展开,TP SHUAI,55,5.函数的可微性与展开,TP SHUAI,56,5.函数的可微性与展开,TP SHUAI,57,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8142，凸分析与凸函数,TP SHUAI,58,2.凸集与凸函数,2.1 凸集与锥,TP SHUAI,59,2.凸集与凸函数,TP SHUAI,60,2.凸集与凸函数,TP SHUAI,61,2.凸集与凸函数,TP SHUAI,62,运用定义不难验证如下命题：,2.凸集与凸函数,TP SHUAI,63,2.凸集与凸函数,多面体(polyhedral set)是有限闭半空间的交.(可表为 Axb).,TP SHUAI,64,2.凸集与凸函数,TP SHUAI,65,多面集 x|Ax0也是凸锥，称为多面锥。,2.凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合,K(S)=x|0,xS,是包含S的最小凸锥.,锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间.,约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则,coneS=K(S)0,TP SHUAI,66,2.凸集与凸函数,Df 2.5 非空凸集中的点 x 称为极点,若 x=x1+(1-)x2,(0,1),x1,x2 S,则 x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.,由上可知,任何有界凸集中任一点都可表成极点的凸组合.,TP SHUAI,67,2.凸集与凸函数,Def 2.6.设非空凸集SRn,Rn中向量d0 称为S的一个回收方向(方向),若对每一 xS,R(x.d)=x+d|0 S.S的所有方向构成的尖锥称为S的回收锥,记为0+S,方向d1和d2 称为S的两个不同的方向,若对任意0,都有 d1d2；方向d称为S的极方向extreme direction,若 d=d1+(1-)d2,(0,1),d1,d2 是S的两个方向,则有 d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合,TP SHUAI,68,2.凸集与凸函数,TP SHUAI,69,2.凸集与凸函数,表示定理,Th2.4 若多面体P=xRn|Axb,r(A)=n则:,则,(3)指标集J是空集当且仅当P是有界集合,即多胞形.,TP SHUAI,70,2.凸集与凸函数,表示定理直观描述:设 X 为非空多面体.则存在有限个极点 x1,xk,k0.进一步,存在有限个极方向 d1,dl,l0 当且仅当 X 无界.进而,xX 的充要条件是 x 可以表为 x1,xk 的凸组合和d1,dl的非负线性组合(凸锥组合).,推论2.1 若多面体S=x|Ax=b,x0非空,则S必有极点.,TP SHUAI,71,2.2 凸集分离定理,2.凸集与凸函数,TP SHUAI,72,2.凸集与凸函数,TP SHUAI,73,证明：令,2.凸集与凸函数,TP SHUAI,74,所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。,2.凸集与凸函数,下证明唯一性,TP SHUAI,75,2.凸集与凸函数,TP SHUAI,76,2.凸集与凸函数,TP SHUAI,77,2.凸集与凸函数,证明提纲,TP SHUAI,78,由此可得,2.凸集与凸函数,TP SHUAI,79,2.凸集与凸函数,Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理,TP SHUAI,80,证明,2.凸集与凸函数,TP SHUAI,81,推论2.2：设S为Rn 中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)0,2.凸集与凸函数,TP SHUAI,82,2.凸集与凸函数,TP SHUAI,83,2.凸集与凸函数,TP SHUAI,84,作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。,2.凸集与凸函数,2.3 择一定理,TP SHUAI,85,2.凸集与凸函数,TP SHUAI,86,2.凸集与凸函数,TP SHUAI,87,2.凸集与凸函数,TP SHUAI,88,2.凸集与凸函数,TP SHUAI,89,2.凸集与凸函数,TP SHUAI,90,2.凸集与凸函数,TP SHUAI,91,2.凸集与凸函数,TP SHUAI,92,2.凸集与凸函数,TP SHUAI,93,2.凸集与凸函数,2.4 凸函数,Df2.10 设SRn是非空凸集,函数f:SR,若对任意x1,x2S,和每一(0,1)都有 f(x1+(1-)x2)f(x1)+(1-)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.,2.4.1 基本性质,TP SHUAI,94,2.凸集与凸函数,TP SHUAI,95,Th2.13 设 f 是一凸函数，则对任意的xRn 和d(0)Rn，f在x处沿方向d的方向导数存在。,2.凸集与凸函数,TP SHUAI,96,2.凸集与凸函数,TP SHUAI,97,2.凸集与凸函数,TP SHUAI,98,命题2.3 设f是定义在凸集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数,2.凸集与凸函数,(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)=x|xS,f(x),R 和上镜图epi(f)=(x,y)|xS,yR,yf(x)都是凸集,TP SHUAI,99,2.凸集与凸函数,设S 为Rn中的非空凸集,则 f(x)是凸的当且仅当上镜图 epif=(x,y)|xS,yR,yf(x)是凸集,对上镜图事实上我们有如下定理,TP SHUAI,100,2.凸集与凸函数,TP SHUAI,101,定理2.14 设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。,2.凸集与凸函数,TP SHUAI,102,2.凸集与凸函数,TP SHUAI,103,2.凸集与凸函数,TP SHUAI,104,2.凸集与凸函数,2.5.2 凸函数的判别,Th2.16.设S 是Rn 中的非空开凸集,f(x):SR 是可微的函数 则 f(x)是凸函数当且仅当对任意的 x*S,我们有f(x)f(x*)+f(x*)(x-x*),任意 xS.类似的,f(x)严格凸当且仅当对每一 x*S,f(x)f(x*)+f(x*)(x-x*),任意 xS.,2.4.2 凸函数的判别,TP SHUAI,105,2.凸集与凸函数,TP SHUAI,106,2.凸集与凸函数,Th 2.16*.设S 是 Rn 上的非空开凸集,f(x)为 S 到 R上的可微函数.则 f(x)是凸函数当且仅当任意的 x1,x2 S,有(f(x2)-f(x1)(x2-x1)0.类似的,f 严格凸当且仅当对任意相异的 x1,x2 S,(f(x2)-f(x1)(x2-x1)0.,TP SHUAI,107,2.凸集与凸函数,TP SHUAI,108,2.凸集与凸函数,Th 2.17 设S 是 Rn a上的非空开凸集,f(x)为 S 到 R上的二次可微函数.则(1)f(x)是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2)f(x)是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.,TP SHUAI,109,凸规划,2.凸集与凸函数,TP SHUAI,110,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8143，线性规划的基本性质,TP SHUAI,111,第二章 线性规划的基本性质,标准形式与图解法基本性质,TP SHUAI,112,我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。,2.线性规划-例子-食谱问题,TP SHUAI,113,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,极小化目标函数可行区域（单纯形）可行解,2.线性规划-例子-食谱问题,TP SHUAI,114,1标准形式,矩阵表示,其中A是mn矩阵，c是n维行向量，b是m维列向量。,注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。,2.线性规划-形式,TP SHUAI,115,任意非标准形式均可化为标准形式，如,引入松弛变量xn+1，xn+2,xn+m.,2.线性规划-形式,TP SHUAI,116,则有,2.线性规划-形式,TP SHUAI,117,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,例如，考虑食谱问题,2.图解法 当自变量个数少于3时,可以用较简便的方法求解.,2.线性规划-图解法,TP SHUAI,118,可行区域的极点：(0,25)(15,2.5)最优解(20,0),Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,2.线性规划-图解法,TP SHUAI,119,3 基本性质3.1 线性规划的可行域,定理 2.2 线性规划的可行域是凸集.,3.2 最优极点,观察上例，最优解在极点(15,2.5)达到，我们有如下事实:线性规划若存在最优解,则最优解一定可在某极点上达到.,2.线性规划-性质1,TP SHUAI,120,考察线性规划的标准形式(2.2),根据表示定理，任意可行点x可表示为,2.线性规划-性质2,TP SHUAI,121,把x的表达式代入(2.2),得等价的线性规划:,2.线性规划-性质3,TP SHUAI,122,于是,问题简化成,在(2.6)中令,显然,当,时目标函数取极小值.,2.线性规划-性质4,TP SHUAI,123,因此极点x(p)是问题(2.2)的最优解.,即(2.5)和(2.8)是(2.4)的最优解,此时,2.线性规划-性质5,TP SHUAI,124,2,若(2.2)存在有限最优解,则目标数的最优值可在某极点达到.,定理2.3 设线性规划(2.2)的可行域非空,则,2.线性规划-性质6,TP SHUAI,125,4最优基本可行解,前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。,不失一般性,设rank(A)=m,A=B,N,B是m阶可逆的.,2.线性规划-性质7,TP SHUAI,126,于是,Ax=b可写为,于是,2.线性规划-性质8,TP SHUAI,127,称为方程组Ax=b的一个基本解.,定义2.6,为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵,称为一组可行基.,2.线性规划-性质9,TP SHUAI,128,且至少有一个分量为0,称基本可行解是退化的.,2.线性规划-性质10,TP SHUAI,129,2.线性规划-性质11,TP SHUAI,130,2.线性规划-性质12,TP SHUAI,131,2.线性规划-性质13,TP SHUAI,132,容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过,2.线性规划-性质14,TP SHUAI,133,定理2.4 令K=x|Ax=b,x0,A是mn矩阵,r(A)=m则K的极点集与Ax=b,x0的基本可行解集合等价.,证明:(提纲)1)设x是K的极点,则x是Ax=b,x0的基本可行解.2)设x是Ax=b,x0的基本可行解,则x是K的极点.,2.线性规划-性质15,TP SHUAI,134,1),先证极点x的正分量所对应的A的列线性无关.,2.线性规划-性质16,TP SHUAI,135,2.线性规划-性质17,TP SHUAI,136,2.线性规划-性质18,TP SHUAI,137,2)设x是Ax=b,x0的基本可行解,记,2.线性规划-性质19,TP SHUAI,138,即,2.线性规划-性质20,TP SHUAI,139,总结,线性规划存在最优解,目标函数的最优值 一定能在某极点上达到.可行域K=x|Ax=b,x0的极点就是其基本可行解.从而,求线性规划的最优解,只需要求出最优基本可行解即可.,2.线性规划-性质21,TP SHUAI,140,5 基本可行解的存在问题,定理2.5 若Ax=b,x0有可行解,则一定存在基本可行解,其中A是秩为m的mn矩阵.,2.线性规划-性质22,TP SHUAI,141,否则,我们通过如下步骤构造出一基本可行解,2.线性规划-性质23,TP SHUAI,142,2.线性规划-性质24,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8144，线性规划的单纯形方法,第三章 单纯形方法,1，单纯形方法原理2，两阶段法和大Mf法3，退化情形4，修正单纯形方法,单纯形法的基本思路 是有选择地取（而不是枚举所有的）基本可行解，即是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，要求新顶点的目标函数值不比原目标函数值差，如此迭代，直至找到最优解，或判定问题无界。,单纯形法的基本过程,3.1线性规划-单纯形方法1,3.1线性规划-单纯形方法2,给定标准形式的LP,利用分块矩阵,3.1线性规划-单纯形方法3,于是目标函数,于是有,基本可行解x与基B关联;,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）min z=-86，max z=86,1,3.1线性规划-单纯形方法28,例3：求解线性规划问题,3.1线性规划-单纯形方法29,3.1线性规划-单纯形方法30,x3进基，x6离基,3.1单纯形方法31,初始单纯型表,最优单纯型表,3.2 两阶段法&大M法1,单纯形法三要素：初始基本可行解，解的迭代，最优性检验后两个已解决,现考虑如何获得一个初始基可行解.,（一）两阶段法,设标准LP为,3.2 两阶段法&大M法2,若系数矩阵中有一个单位矩阵，则容易得到初始基可行解.所以我们希望幸运的碰到这种矩阵.没有的话，硬性加一个？,3.2 两阶段法&大M法3,问题是如何由(3.2.3)的初始可行解获得原来LP的一个初始可行解？为此，考虑如下辅助LP(第一阶段),如果原问题有可行解，则辅助问题的最优值为0，反之亦然。,3.2两阶段法&大M法4,3.2 两阶段法&大M法5,利用单纯形法求得一个最优可行解.这个解将会给我们带来什么？,3.2 两阶段法&大M法6,于是我们获得一个初始基可行解,从而可以以此基可行解出发利用单纯形法求出最优解.,第一阶段：不考虑原LP问题是否有基可行解，添加人工变量，构造仅含人工变量的目标函数，得辅助规划(3.2.4),单纯型法求解上述模型，若有目标函数=0，说明原问题存在初始基本可行解，转入第二阶段。否则，原问题无可行解，计算停止。,第二阶段：将第一阶段计算得到的最终表，除去人工变量，从该初始基本可行解开始，用单纯形法求原问题的最优解或判定原问题无界。,3.2 两阶段法&大M法7,写成标准化形式,例1 求解,3.2 两阶段法&大M法8,第1 阶段,首先引入人工变量，构造辅助规划问题,其对应的单纯形表为,3.2 两阶段法&大M法9,RHS,3.2 两阶段法&大M法10,RHS,RHS,RHS,第一阶段结束，得到辅助问题的一个最优解,同时得到原问题的一个初始基本可行解,3.2 两阶段法&大M法11,去掉人工变量对应的行、列，得到原问题的初始典式，,直接开始第二阶段运算,第 2 阶 段,RHS,RHS,z,原问题的最优解,其最优值为,3.2 两阶段法&大M法12,例2求解,3.2 两阶段法&大M法13,解：引进人工变量进行第一阶段,3.2 两阶段法&大M法14,单纯形法求解：,3.2 两阶段法&大M法15,0 1 1-1 0 1 0 4,0 0 2-3 0 0 1 4,0-1 1-2 1 0 0 0,0 0 4-6 0 0 0 8,3.2 两阶段法&大M法16,0 2 0 1-2 0 1 4,0 2 0 1-1 1 0 4,0 4 0 2-4 0 0 8,3,3.2 两阶段法&大M法17,0 1 0-0 2,0 0 0 0-1-1 1 0,0 0 1-3/2 0 2,0 0 0 0-2-2 0 8,2,3.2 两阶段法&大M法18,第二阶段：,3.2 两阶段法&大M法19,第二阶段初始单纯形表：,3.2 两阶段法&大M法20,前面所说的两阶段法分成两步走。能不能把这两步合并？如何合并？,（二）大M法,设原问题为,引入m个人工变量,3.2 两阶段法&大M法21,现在关键是如何选取目标函数，因要包含原问题,所以必须包含原目标。联系到两阶段法，我们要强迫人工变量取值为0，于是加上一个惩罚因子，因为是极小化，所以希望这个惩罚因子越大越好！,在目标函数中增加,3.2 两阶段法&大M法22,可行吗？,直观上，因M为足够大的正数，新问题最优解对应的人工变量取值应满足，（除非原问题不可行）,从而新LP问题的最优解对应于原问题的（基本）可行解，,容易知道此时两个问题的目标函数值满足,3.2 两阶段法&大M法23,因此只需求解辅助问题就可求得原问题的最优解。,且两个规划目标值相等，故原问题的最优解,综合,3.2 两阶段法&大M法24,例3 求解如下LP,解：,得到最优解：(25/3，10/3，0，11)T 最优目标值：max=112/3,3.2 两阶段法&大M法25,3.2.3 单个人工变量技巧1,前述方法引入多个人工变量，能否只引入一个变量而达到目标？,考虑LP,3.2.3 单个人工变量技巧2,3.2.3 单个人工变量技巧3,例子：,3.2.3 单个人工变量技巧4,利用表格形式求解一个(3.2.17)的BFS：,3.2.3 单个人工变量技巧5,于是得到(3.2.17)的一个BFS，下面再用两阶段(或大M)法求解之.,3.2.3 单个人工变量技巧6,3.2.3 单个人工变量技巧7,于是得到进行第二阶段时的初始表。,由上知道这是最优单纯形表。,3.3 退化情形1,单纯形法收敛定理要求BFS非退化，这个限制可以去掉吗？试看下例。,例(3.3.1)：用单纯形法求解下面的LP,注意到该LP有一个明显的BFS x=(0，0，1，0，0，0，0),3.3 退化情形2,其单纯形法迭代过程如下：,3.3 退化情形3,3.3 退化情形4,3.3 退化情形5,3.3 退化情形6,前例表明算法会无限循环下去，能否找到一种办法避免出现这种情况？,(a)摄动法,3.3 退化情形7,下面讨论这种办法的可行性。,对右端向量b 作如下摄动。令,于是得（3.3.1）的摄动问题：,3.3 退化情形8,下面我们将证明当适当对取值时，LP(3.3.3)非退化，且可以通过求解LP(3.3.3)来确定原LP(3.3.1)的最优解或得出其他结论。,3.3 退化情形9,前面分析表明摄动问题当0充分小时非退化，因此可以避免循环，并且通过求解摄动问题一定能够给出线性规划(3.3.1)的解答。下一个问题是如何求解摄动问题？此时需要处理两个问题：（1）初始可行解；（2）迭代过程中如何处理b().,(a)初始可行解的确定 思想：是由原LP(3.3.1)的BFS来找LP(3.3.3)的BFS.,3.3 退化情形10,对应的摄动问题约束为,幸运的是我们可以通过将变量下标进行适当调整，使得上述情况不出现。改变标号，使得(3.3.8)为如下等价约束:,3.3 退化情形11,一般地，若已知LP(3.3.1)的一个BFS，则进行列调换，把基列排在非基列的左边，并相应地改变变量的下标，使其从1开始按递增顺序排列，这样x1,x2,.,xm是基变量，然后 再建立摄动问题(3.3.3).这时，若(3.3.1)的现行BFS是,3.3 退化情形12,于是可以用单纯形法求解下去。但右端向量含有参数，这对计算有影响吗？实际上我们可以不必让取具体数字。注意到：,3.3 退化情形13,概言之，以如下步骤确定离基之变量：,(b)置j=1.,(a)令,(c)令,(d)置j:=j+1,转(c).,3.3 退化情形14,例：用摄动法解例(3.3.1),初始单纯形表如下,3.3 退化情形15,即在单纯形表中选最左边的正检验数对应的非基变量入基。,即在比值达到最小的行中，选最上面的那行所对应的基变量 出基。,3.3 退化情形17,Bland规则(退化问题的处理)：,该问题的最优解,model:obj min=-0.75*x4+20*x5-0.5*x6+6*x7;con1 x1+0.25*x4-8*x5-x6+9*x7=0;con2 x2+0.5*x4-12*x5-0.5*x6+3*x7=1;con3 x3+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,例，用修正单纯形法解下列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,例，用改进修正单纯形法解LP,3.4 修正单纯形方法-21,约束方程的系数矩阵,3.4 修正单纯形方法-22,3.4 修正单纯形方法-23,第二次迭代,3.4 修正单纯形方法-24,计算主列,3.4 修正单纯形方法-25,3.4 修正单纯形方法-26,第3次迭代,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8145，对偶理论与灵敏度分析,第四章 对偶理论与灵敏度分析,对偶理论对偶单纯形法原始-