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

《最优化理论与算法完整版课件陈宝林》由会员分享，可在线阅读，更多相关《最优化理论与算法完整版课件陈宝林（902页珍藏版）》请在金锄头文库上搜索。

1、TP SHUAI1最优化理论与算法TP SHUAI2提纲1. 线性规划 对偶定理对偶定理2. 非线性规划 K-K-T 定理定理3. 组合最优化 算法设计技巧算法设计技巧使用教材：最最优化理论与算法优化理论与算法 陈宝林陈宝林参考书 ：数学规划数学规划 黄红选，黄红选， 韩继业韩继业 清华大学出版社清华大学出版社TP SHUAI3其他参考书目其他参考书目Nonlinear Programming - Theory and AlgorithmsMokhtar S. Bazaraa, C. M. ShettyJohn Wiley & Sons, Inc. 1979 (2nd Edit, 1993，3

2、nd Edit，2006)Linear and Nonlinear Programming David G. LuenbergerAddison-Wesley Publishing Company, 2nd Edition, 1984/2003.Convex Analysis R. T. RockafellarPrinceton Landmarks in Mathematics and Physics, 1996.Optimization and Nonsmooth Analysis Frank H. Clarke SIAM, 1990.TP SHUAI4Linear Programming

3、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 SHUAI51,绪论绪论-学科概述学科概述最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方

4、案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型模型理论理论算法算法最优化首先是一种理念最优化首先是一种理念, ,其次才是一种方法其次才是一种方法. .TP SHUAI6绪论绪论-运筹学（运筹学（Operations Research - OR） 运筹学方法随机过程方法统计学方法最优化/数学规划方法l连续优化：线性规划、连续优化：线性规划、非线性规划、非光滑优非线性规划、非光滑优化、全局优化、变分法、化、全局优化、变分法、二次规划、分式规划等二次规划、分式规划等l 离散优化：组合优化、离散优

5、化：组合优化、网络优化、整数规划网络优化、整数规划等等l几何规划几何规划l动态规划动态规划l不确定规划：随机规不确定规划：随机规划、模糊规划等划、模糊规划等l多目标规划多目标规划l对策论等对策论等l统计决策理论统计决策理论l马氏过程马氏过程l 排队论排队论l更新理论更新理论l仿真方法仿真方法l可靠性理论等可靠性理论等l回归分析回归分析l群分析群分析l模式识别模式识别l实验设计实验设计l因子分析等因子分析等TP SHUAI7优化树TP SHUAI8最优化的发展历程最优化的发展历程费马: :1638;牛顿,1670欧拉,1755Min f(x1 x2 xn ) f(x)=0TP SHUAI9欧拉，

6、拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Min f(x1 x2 xn)s.t. gk (x1 x2 xn )=0, k=1,2,mTP SHUAI101930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法， 冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理； KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展 电子计算机-最优化TP SHU

7、AI11最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版（TEX,Latex,etc.）TP SHUAI121. 食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。TP

8、SHUAI131. 食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解TP SHUAI142 运输问题设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.

9、假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。TP SHUAI15令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2 运输问题（续）TP SHUAI16以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元

10、的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=390003 税下投资问题TP SHUAI17我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3 税下投资问题（续）TP SHUAI184 选址问题（1）实例实例:一组潜在位置（地址）, 一组顾客集合及相应的 利润和费用数据； 解解: 设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。目标：总的利润最大化。数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.TP SHUAI194 选址问

11、题（2）TP SHUAI204选址问题（3）TP SHUAI215负载平衡(1)实例实例: 网络网络G(V,E) 及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解解: s,d0的一组路由, 即G(V,E) 中m 条s 与 d间的路, 表示连接s与d 的负载流量的路径。目标目标:极小化网络负载极小化网络负载TP SHUAI225 负载平衡(2)TP SHUAI236.结构设计问题结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下

12、使桁架重量最轻的桁架高度h及圆杆平均直径d。TP SHUAI24 受力分析图圆杆截面图桁杆示意图6.结构设计问题结构设计问题TP SHUAI256.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为 ：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为： 圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 由此得稳定约束：6.结构设计问题结构设计问题 另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题结构设计问题TP SHUAI28基本概念基本概念在上述例子中,有的目标函数和约束函数都是线性的,

13、称之为线性规划问题线性规划问题,而有的模型中含有非线性函数,称之为非线性规划称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.TP SHUAI29基本概念最优化问题可写成如下形式:TP SHUAI30基本概念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的局部最优解局部最优解

14、 Df 1.2 设f(x)为目标函数，S为可行域，TP SHUAI31优化软件 http:/www-neos.mcs.anl.gov/ http:/neos.mcs.anl.gov/neos/solvers/index.htmlTP SHUAI32最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼814 1 预备知识TP SHUAI331， 预备知识1.线性空间2.范数3.集合与序列4.矩阵的分解与校正TP SHUAI341.线性空间Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:则称为一个群群.若还满足对任

15、意的a,bG,有a+b=b+a,则称为一个阿贝尔群阿贝尔群(&交换群交换群)TP SHUAI351.线性空间Df 1.4:给定一非空集合V和一个域F,并定义两种运算加法加法+:VVV以及数乘数乘 : FVV.若构成一交换群,且两种运算满足下面性质:则称V在域F上关于加法和数乘 运算构成一线性空间线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子线性子空间空间.TP SHUAI361.线性空间例子TP SHUAI371.线性空间TP SHUAI381.线性空间Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是

16、V中包含S的最小子空间.TP SHUAI391.线性空间TP SHUAI401.线性空间TP SHUAI412.范数TP SHUAI422.范数TP SHUAI432.范数TP SHUAI443.集合与序列TP SHUAI453，集合与序列TP SHUAI463.集合与序列TP SHUAI473.集合与序列TP SHUAI484.矩阵的分解与校正Th1.5 若n阶矩阵A可逆，则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LUTP SHUAI494.矩阵的分解与校正Th1.6 设A为对称正定矩阵，则（1）矩阵A可唯一的分解成A=LDLT, 其中L为单位下三角矩阵，D为对角矩阵（

17、2）存在可逆的下三角矩阵L，使得A=LLT. 当L的对角元素为正时，分解是唯一的。(Cholesky分解)TP SHUAI504.矩阵的分解与校正TP SHUAI514.矩阵的分解与校正TP SHUAI525.函数的可微性与展开TP SHUAI535.函数的可微性与展开当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为TP SHUAI545.函数的可微性与展开TP SHUAI555.函数的可微性与展开TP SHUAI565.函数的可微性与展开TP SHUAI57最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8142，凸分析与凸函数TP

18、 SHUAI582. 凸集与凸函数2.1 凸集与锥凸集与锥TP SHUAI592. 凸集与凸函数TP SHUAI602. 凸集与凸函数x0xx-x0px0xx-x0pTP SHUAI612. 凸集与凸函数TP SHUAI62运用定义不难验证如下命题：2. 凸集与凸函数TP SHUAI632. 凸集与凸函数多面体多面体(polyhedral set)是有限闭半空间的交. (可表为 Axb ).x4x3x2x1x5xyTP SHUAI642. 凸集与凸函数TP SHUAI65多面集 x|Ax0也是凸锥，称为多面锥多面锥。2. 凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封

19、闭,一般的,对于凸集S,集合K(S)=x|0,xS是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出突出的,若它不包含一维子空间.约定约定: 非空集合非空集合S生成的凸锥生成的凸锥,是指可以表示成是指可以表示成S中有限个中有限个元素的非负线性组合元素的非负线性组合(称为凸锥组合称为凸锥组合)的所有点所构成的的所有点所构成的集合集合,记为记为coneS. 若若S凸凸,则则coneS=K(S) 0TP SHUAI662. 凸集与凸函数Df 2.5 非空凸集中的点 x 称为极极点点,若 x=x1+(1-)x2 , (0,1) , x1 ,x2 S, 则 x=x1=x2.换言之,x不能表示成S中两

20、个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.TP SHUAI672. 凸集与凸函数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不能表成它的两个不同方

21、向的凸锥组合x0x0dddTP SHUAI682. 凸集与凸函数TP SHUAI692. 凸集与凸函数表示定理表示定理Th2.4 若多面体若多面体P=x Rn|Axb, r(A)=n则则:(1)P的极点集是非空的有限集合的极点集是非空的有限集合,记为记为x kk K则则j(2)记记P的极方向集为的极方向集为d j J(约定约定P不存在极方向时不存在极方向时J=)(3)指标集指标集J是空集当且仅当是空集当且仅当P是有界集合是有界集合,即多胞形即多胞形.TP SHUAI702. 凸集与凸函数表表示示定定理理直直观观描描述述 :设 X 为非空多面体 . 则存在有限个极点 x1, , xk , k0.

22、 进一步 ,存在有限个极方向 d1, , dl, l0 当且仅当 X 无界 . 进而 , x X 的 充 要 条 件 是 x 可 以 表 为 x1, , xk 的凸组合和d1, , dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论推论2.1 若多面体若多面体S=x|Ax=b,x0非空非空,则则S必有极点必有极点.TP SHUAI712. 2 凸集分离定理凸集分离定理2. 凸集与凸函数TP SHUAI722. 凸集与凸函数TP SHUAI73证明：令2. 凸集与凸函数TP SHUAI74所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2. 凸集与凸函数下证明唯一性TP S

23、HUAI752. 凸集与凸函数TP SHUAI762. 凸集与凸函数TP SHUAI772. 凸集与凸函数xpX(i) (x- )(y- )0 对任意 xX.(ii) 令 p=y- ， =p p. Txxxyx 证明提纲TP SHUAI78由此可得2. 凸集与凸函数TP SHUAI792. 凸集与凸函数Th2.7表明，S为闭凸集， yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理TP SHUAI80证明2. 凸集与凸函数TP SHUAI81推论2.2：设S为Rn 中的非空集合，yS,则存在非零向量p，使对xclS, pT (x-y)02.

24、 凸集与凸函数TP SHUAI822. 凸集与凸函数TP SHUAI832. 凸集与凸函数TP SHUAI84 作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。2. 凸集与凸函数2.3 择一定理择一定理TP SHUAI852. 凸集与凸函数TP SHUAI862. 凸集与凸函数TP SHUAI872. 凸集与凸函数TP SHUAI882. 凸集与凸函数TP SHUAI892. 凸集与凸函数TP SHUAI902. 凸集与凸函数TP SHUAI912. 凸集与凸函数TP SHUAI922. 凸集与凸函数TP SHUAI932. 凸集

25、与凸函数2.4 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 SHUAI942.2. 凸集与凸函数TP SHUAI95Th2.13 设 f 是一凸函数，则对任意的xRn 和d(0 )Rn，f在x处沿方向d的方向导数存在。2. 凸集

26、与凸函数TP SHUAI962. 凸集与凸函数TP SHUAI972.凸集与凸函数TP SHUAI98命题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 SHUAI992.2. 凸集与凸函数设设S 为为Rn中的非空凸集中的非空凸集,则则 f(x) 是凸的

27、当且仅当上镜图是凸的当且仅当上镜图 epif=(x, y) | xS, yR, yf(x)是凸集是凸集对上镜图事实上我们有如下定理TP SHUAI1002. 凸集与凸函数TP SHUAI101定理2.14 设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。2. 凸集与凸函数TP SHUAI1022. 凸集与凸函数TP SHUAI1032. 凸集与凸函数TP SHUAI1042. 凸集与凸函数2.5.2 凸函数的判别凸函数的判别Th2.16. 设S 是是Rn 中的非空开凸集, f(x):SR 是可微的函数 则 f(x) 是凸函数当且仅当对任意

28、的 x*S, 我们有f(x) f(x*)+f(x*) (x-x*), 任意 xS. 类似的, f(x) 严格凸当且仅当对每一 x*S,f(x) f(x*)+f(x*) (x-x*), 任意 xS.l2.4.2 凸函数的判别凸函数的判别TP SHUAI1052. 凸集与凸函数TP SHUAI1062. 凸集与凸函数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)-

29、f(x1)(x2-x1)0. TP SHUAI1072. 凸集与凸函数TP SHUAI1082. 凸集与凸函数Def 2.11 . 设 S 是Rn 上的非空开集, f(x) f(x):SR 的函数 则 f(x) 在点x*int(S)称为二次可微的,若存在向量f(x*), 和 nn (Hessian) 矩阵 H(x*) , 及函数 : Rn R 使得对所有的 xS,f(x) = f(x*)+f(x*) (x-x*)+0.5(x-x*) H(x*) (x-x*)+|x-x*| (x-x*)其中 lim (x-x*)=0.2x*x*xx*Th 2.17 设S 是 Rn a上的非空开凸集, f(x)

30、为 S 到 R上的二次可微上的二次可微函数函数. 则(1) f(x) 是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2) f(x) 是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.TP SHUAI109凸规划2. 凸集与凸函数TP SHUAI110最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8143， 线性规划的基本性质TP SHUAI111第二章 线性规划的基本性质标准形式与图解法基本性质TP SHUAI112我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日

31、需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。2.线性规划- - 例子-食谱问题TP SHUAI113令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解2.线性规划- - 例子-食谱问题TP SHUAI1141标准形式标准形式矩阵表示其中A是mn矩阵，c是n维行向量， b是m维列向量

32、。注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。2.线性规划-形式TP SHUAI115任意非标准形式均可化为标准形式，如引入松弛变量xn+1， xn+2 , xn+m.2.线性规划-形式TP SHUAI116则有2.线性规划-形式TP SHUAI117Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.例如，考虑食谱问题2. 图解法 当自变量个数少于3时,可以用较简便的方法求解.2.线性规划-图解法TP SHUAI11830104020501020304050yx03x +2.5y2x+4y 403x+2y 50(15,

33、2.5)可行区域的极点：可行区域的极点：(0, 25)(15, 2.5) 最优解最优解(20, 0)Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.2.线性规划-图解法TP SHUAI1193 基本性质3.1 线性规划的可行域定理定理 2.2 线性规划的可行域是凸集线性规划的可行域是凸集. 3.2 最优极点观察上例，最优解在极点(15,2.5)达到，我们有如下事实:线性规划若存在最优解线性规划若存在最优解,则最优解一则最优解一定可在某极点上达到定可在某极点上达到.2.线性规划-性质1TP SHUAI120考察线性规划的标准形式(2. 2)根据表示定

34、理，任意可行点x可表示为2.线性规划-性质2TP SHUAI121把x的表达式代入(2. 2),得等价的线性规划:2.线性规划-性质3TP SHUAI122于是,问题简化成在(2.6)中令显然,当时目标函数取极小值.2.线性规划-性质4TP SHUAI123因此极点x(p)是问题(2.2)的最优解.即(2.5)和(2.8)是(2.4)的最优解,此时2.线性规划-性质5TP SHUAI1242,若若(2. 2)存在有限最优解存在有限最优解,则目标数的最则目标数的最优值优值可在某极点达到可在某极点达到.定理定理2.3 设线性规划设线性规划(2.2)(2.2)的可行域非空的可行域非空, ,则则1,(

35、2.2)1,(2.2)存在最优解的充要条件是所有存在最优解的充要条件是所有(j)cd非负非负,其中其中 是可行域的极方向是可行域的极方向d(j)2.线性规划-性质6TP SHUAI1254最优基本可行解前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=B,N,B是m阶可逆的.2.线性规划-性质7TP SHUAI126于是,Ax=b可写为于是特别的令Nx =0,则2.线性规划-性质8TP SHUAI127称为方程组Ax=b的一个基基本解本解.定义定义2.6B称为基矩阵基矩阵, 的各分量称为基变量基变量. xB基变量的全体称为一组基

36、一组基.的各分量称为非基变量基变量. xN为约束条件Ax=b,x0的一个基基本可行解本可行解. B称为可行基矩阵可行基矩阵称为一组可行基一组可行基.2.线性规划-性质9TP SHUAI128B b0,称基本可行解是非退化非退化的,若-1 若B b0,-1 且至少有一个分量为0,称基本可行解是退化退化的.2.线性规划-性质10TP SHUAI1292.线性规划-性质11TP SHUAI1302.线性规划-性质12TP SHUAI1312.线性规划-性质13TP SHUAI132容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的, 不超过2.线性规划-性质14TP SHUAI

37、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.线性规划-性质15TP SHUAI1341),先证极点x的正分量所对应的A的列线性无关.2.线性规划-性质16TP SHUAI1352.线性规划-性质17TP SHUAI1362.线性规划-性质18TP SHUAI1372)设x是Ax=b,x0的基本可行解,记2.线性规划-性质19TP SHUAI138即2.线性规划-性质20TP SHU

38、AI139总结,线性规划存在最优解,目标函数的最优值 一定能在某极点上达到.可行域K=x| Ax=b,x0的极点就是其基本可行解. 从而,求线性规划的最优解,只需要求出最优基本可行解即可.2.线性规划-性质21TP SHUAI1405 基本可行解的存在问题定理定理2. 5 若Ax=b,x0有可行解,则一定存在基本可行解,其中A是秩为m的mn矩阵.2.线性规划-性质22TP SHUAI141否则,我们通过如下步骤构造出一基本可行解2.线性规划-性质23TP SHUAI1422.线性规划-性质24最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8144，

39、 线性规划的单纯形方法第三章第三章 单纯形方法单纯形方法1 1，单纯形方法原理，单纯形方法原理2 2，两阶段法和大，两阶段法和大MfMf法法3 3，退化情形，退化情形4 4，修正单纯形方法，修正单纯形方法单单纯纯形形法法的的基基本本思思路路 是有选择地取（而不是枚举所有的）基本可行解，即是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，要求新顶点的目标函数值不比原目标函数值差，如此迭代，直至找到最优解，或判定问题无界。 初始基本可行解初始基本可行解是否最优解或是否最优解或无界解无界解? ?结束结束沿边界找沿边界找新的基本新的基本可行解可行解NY单纯形法的基本过程 3.1线性规划-

40、单纯形方法单纯形方法1 1怎么判断达到最优解怎么判断达到最优解?如何给出初如何给出初始基可行解始基可行解?迭代如何进行迭代如何进行? 3.1线性规划-单纯形方法单纯形方法2给定标准形式的给定标准形式的LPLP利用分块矩阵3.1线性规划-单纯形方法单纯形方法3于是目标函数于是有l 基本可行解x与基B关联;3.线性规划-单纯形方法单纯形方法4于是我们有如下定理：3.1.线性规划-单纯形方法单纯形方法5由上知,要减少费用, 只有当 C0时才可能，即3.1线性规划-单纯形方法单纯形方法6令 y=x+d, 0, 我们能降低费用吗？3.1线性规划-单纯形方法单纯形方法73.1线性规划-单纯形方法单纯形方法

41、83.1线性规划-单纯形方法单纯形方法9正确性如何？ 显然按上述取法，是可以保证y0的。y还是基本可行解吗？3.1线性规划-单纯形方法单纯形方法103.1线性规划-单纯形方法单纯形方法11单纯形法3.1线性规划-单纯形方法单纯形方法12Th3.4(单纯形法的收敛性）对于相容的非退化(每个基可行解都是非退的)LP问题， 那么经过有限次迭代后，单纯形法或者得到最优的BFS(最优可行基B）或有一个方向d:且最优的费用为-.3.1线性规划-单纯形方法单纯形方法13例例13.1线性规划-单纯形方法单纯形方法143.1线性规划-单纯形方法单纯形方法15Tc =(0 7 0 2 -3 0 0)3.1线性规划

42、-单纯形方法单纯形方法163.1线性规划-单纯形方法单纯形方法173.1线性规划-单纯形方法单纯形方法183.1线性规划-单纯形方法单纯形方法19新的基为B=(A1, A3, A4, A7)3.1线性规划-单纯形方法单纯形方法203.1线性规划-单纯形方法单纯形方法21新的基为B=(A3, A4, A5, A7) 3.13.1线性规划线性规划-单纯形方法单纯形方法22利用分块矩阵表格形式的单纯形方法表格形式的单纯形方法 3.13.1线性规划线性规划-单纯形方法单纯形方法233.1线性规划-单纯形方法单纯形方法24 0 Im 1 0ff右端右端3.1线性规划-单纯形方法单纯形方法25进基变量进基

43、变量离基变量离基变量旋转元旋转元右端向量右端向量返回返回单纯形表单纯形表例例2： 求解线性规划问题求解线性规划问题化成标准化形式3.1线性规划-单纯形方法单纯形方法26写出单纯形表25/136/20-3-20-2-7201/201-1/27/0.511/2101/218/0.5x271811/21/2x5x6离基，x2进基，x5离基，x1进基，3.1线性规划-单纯形方法单纯形方法270-4-2-2-1-860102-1101-11141100得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）min z=-86， max z=861 3.1线性规划-单纯

44、形方法单纯形方法28例例3： 求解线性规划问题求解线性规划问题3.1线性规划-单纯形方法单纯形方法293.1线性规划-单纯形方法单纯形方法30x3进基，x6离基 3.1单纯形方法单纯形方法31初始单纯型表初始单纯型表最优单纯型表最优单纯型表3.2 两阶段法两阶段法&大大M法法1单纯形法三要素： 初始基本可行解，解的迭代，最优性检验后两个已解决,现考虑如何获得一个初始基可行解.（一）两（一）两阶段法段法设标准设标准LP为为3.2 两阶段法两阶段法&大大M法法2若系数矩阵中有一个单位矩阵，则容易得到初始基可行解.所以我们希望幸运的碰到这种矩阵.没有的话，硬性加一个？3.2 两阶段法两阶段法&大大M

45、法法3问题是如何由(3.2.3)的初始可行解获得原来LP的一个初始可行解？为此，考虑如下辅助LP(第一阶段)1.如果原问题有可行解，则辅助问题的最优值为0，反之亦然。就可以得到辅助问题的初始基可行解2由于，所以以为基变量，, 同时所以一定有最小值.3.2两阶段法两阶段法&大大M法法4关系关系?3.2 两阶段法两阶段法&大大M法法5利用单纯形法求得一个最优可行解.这个解将会给我们带来什么？3.2 两阶段法两阶段法&大大M法法6于是我们获得一个初始基可行解,从而可以以此基可行解出发利用单纯形法求出最优解.第一阶段：第一阶段：不考虑原LP问题是否有基可行解，添加人工变量，构造仅含人工变量的目标函数，

46、得辅助规划(3.2.4)单纯型法求解上述模型，若有目标函数=0，说明原问题存在初始基本可行解，转入第二阶段。否则，原问题无可行解，计算停止。 第二阶段第二阶段：将第一阶段计算得到的最终表，除去人工变量，从该初始基本可行解开始，用单纯形法求原问题的最优解或判定原问题无界。3.2 两阶段法两阶段法&大大M法法7写成标准化形式例例1 1 求解求解3.2 两阶段法两阶段法&大大M法法8第第1 阶阶段段首先引入人工变量，构造辅助规划问题首先引入人工变量，构造辅助规划问题如果以为基变量，则可以得到该问题的BFS, 其对应的单纯形表为3.2 两阶段法两阶段法&大大M法法9 -5 0 -21 0 0 0 0

47、0 0 0 0 0 0 -1 -1 0 1 -1 6 -1 0 1 0 21 1 2 0 -1 0 1 1RHS -5 0 -21 0 0 0 0 0 2 0 8 -1 -1 0 0 3 1 -1 6 -1 0 1 0 21 1 2 0 -1 0 1 1gzgz3.2 两阶段法两阶段法&大大M法法10 -3/2 -7/2 0 -7/2 0 7/2 0 -7 2/3 4/3 0 1/3 -1 -4/3 0 1/3 1/6 -1/6 1 -1/6 0 1/6 0 1/32/3 4/3 0 1/3 -1 -1/3 1 1/3RHSgz 1/4 0 0 -21/8 -21/8 21/8 21/8 63

48、/8 0 0 0 0 0 -1 -1 01/4 0 1 -1/8 -1/8 1/8 1/8 3/81/2 1 0 1/4 -3/4 -1/4 3/4 1/4RHSgz 1/4 0 0 -21/8 -21/8 21/8 21/8 63/8 0 0 0 0 0 -1 -1 01/4 0 1 -1/8 -1/8 1/8 1/8 3/81/2 1 0 1/4 -3/4 -1/4 3/4 1/4RHSgz第一阶段结束，得到辅助问题的一个最优解同时得到原问题的一个初始基本可行解3.2 两阶段法两阶段法&大大M法法11去掉人工变量对应的行、列，得到原问题的初始典式，直接开始第二阶段运算第第 2 阶阶 段段

49、1/4 0 0 -21/8 -21/8 21/8 21/8 63/8 0 0 0 0 0 -1 -1 01/4 0 1 -1/8 -1/8 1/8 1/8 3/81/2 1 0 1/4 -3/4 -1/4 3/4 1/4RHSgzRHS 0 -1/2 0 -11/4 -9/431/4 0 -1/2 1 -1/4 1/4 1/4 1 2 0 1/2 -3/2 1/2z原问题的最优解其最优值为3.2 两阶段法两阶段法&大大M法法12例例2求解求解3.2 两阶段法两阶段法&大大M法法13解：引进人工变量进行第一阶段3.2 两阶段法两阶段法&大大M法法14单纯形法求解：3.2 两阶段法两阶段法&大大M

50、法法150 1 1 -1 0 1 0 4 0 0 2 -3 0 0 1 4 0 -1 1 -2 1 0 0 00 0 4 -6 0 0 0 8 3.2 两阶段法两阶段法&大大M法法160 2 0 1 -2 0 1 4 0 2 0 1 -1 1 0 40 4 0 2 -4 0 0 8 33.2 两阶段法两阶段法&大大M法法170 1 0 - 0 2 0 0 0 0 -1 -1 1 00 0 1 -3/2 0 20 0 0 0 -2 -2 0 8 23.2 两阶段法两阶段法&大大M法法18第二阶段： 3.2 两阶段法两阶段法&大大M法法19第二阶段初始单纯形表：3.2 两阶段法两阶段法&大大M法法

51、20前面所说的两阶段法分成两步走。能不能把这两步合并？如何合并？（二）大（二）大M法法设原原问题为引入m个人工变量3.2 两阶段法两阶段法&大大M法法21现在关键是如何选取目标函数，因要包含原问题,所以必须包含原目标。联系到两阶段法，我们要强迫人工变量取值为0，于是加上一个惩罚因子，因为是极小化，所以希望这个惩罚因子越大越好！在目标函数中增加3.2 两阶段法两阶段法&大大M法法22可行吗？直观上，因M为足够大的正数，新问题最优解对应的人工变量取值应满足 ，（除非原问题不可行） 从而新LP问题的最优解对应于原问题的（基本）可行解，容易知道此时两个问题的目标函数值满足3.2 两阶段法两阶段法&大大

52、M法法23因此只需求解辅助问题就可求得原问题的最优解。另一方面，原问题的任意可行解x对应于辅助问题的可行解 ，也对应新问题的可行解且两个规划目标值相等，且两个规划目标值相等，故原问题的最优解综合综合3.2 两阶段法两阶段法&大大M法法24例3 求解如下LP解： 得到最优解：得到最优解：(25/3(25/3，10/310/3，0 0，11)11)T T 最优目标值：最优目标值：max=112/3max=112/33.2 两阶段法两阶段法&大大M法法253.2.3 单个人工变量技巧单个人工变量技巧1前述方法引入多个人工变量，能否只引入一个变量而达到目标？考虑LP3.2.3 单个人工变量技巧单个人工

53、变量技巧23.2.3 单个人工变量技巧单个人工变量技巧3例子：3.2.3 单个人工变量技巧单个人工变量技巧4利用表格形式求解一个(3.2.17)的BFS：3.2.3 单个人工变量技巧单个人工变量技巧5于是得到(3.2.17)的一个BFS，下面再用两阶段(或大M)法求解之.3.2.3 单个人工变量技巧单个人工变量技巧63.2.3 单个人工变量技巧单个人工变量技巧7于是得到进行第二阶段时的初始表。由上知道这是最优单纯形表。3.3 退化情形退化情形1单纯形法收敛定理要求BFS非退化，这个限制可以去掉吗？试看下例。例例(3.3.1(3.3.1)：用单纯形法求解下面的LP注意到该LP有一个明显的BFS

54、x=(0，0，1，0，0，0，0)3.3 退化情形退化情形2其单纯形法迭代过程如下：3.3 退化情形退化情形33.3 退化情形退化情形43.3 退化情形退化情形53.3 退化情形退化情形6前例表明算法会无限循环下去，能否找到一种办法避免出现这种情况？(a)摄动法3.3 退化情形退化情形7下面讨论这种办法的可行性。对右端向量b b 作如下摄动。令于是得（3.3.1）的摄动问题：3.3 退化情形退化情形8下面我们将证明当适当对取值时，LP(3.3.3)非退化，且可以通过求解LP(3.3.3)来确定原LP(3.3.1)的最优解或得出其他结论。3.3 退化情形退化情形9前面分析表明摄动问题当0充分小时

55、非退化，因此可以避免循环，并且通过求解摄动问题一定能够给出线性规划 (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开始按递增顺

56、序排列，这样x1,x2,.,xm是基变量，然后 再建立摄动问题(3.3.3). 这时，若(3.3.1)的现行BFS是3.3 退化情形退化情形12于是可以用单纯形法求解下去。但右端向量含有参数，这对计算有影响吗？实际上我们可以不必让取具体数字。注意到：3.3 退化情形退化情形13概言之，以如下步骤确定离基之变量：(b)(b) 置置j=1. (a)令令(c)令令(d)(d) 置置j:=j+1,转(c). 3.3 退化情形退化情形14例：用摄动法解例(3.3.1),初始单纯形表如下(0,4)(0,0)3.3 退化情形退化情形15即在单纯形表中选最左边的正检验数对应的非基变量入基。即在比值达到最小的行

57、中，选最上面的那行所对应的基变量 出基。3.3 退化情形退化情形17解LP问题时常遇到基本可行解退化的情形，但在迭代过程中极少出现循环情形。注意注意BlandBland规则规则( (退化问题的处理退化问题的处理) )：该问题的最优解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;end3.3 退化情形退化情形181，修正单纯形方法2，逆的乘积形式3.4 3.4 修正单纯形方法修正单纯形方法1，修正

58、单纯形方法3.4 3.4 修正单纯形方法修正单纯形方法-1-1回忆单纯形方法，不妨设初始单纯形表中系数矩阵含有单位阵，即系数矩阵为3.4 3.4 修正单纯形方法修正单纯形方法-2-23.4 3.4 修正单纯形方法修正单纯形方法-3-3这样，有了初始表 (即问题的系数矩阵，费用向量和右端向量子集组成)，当前表*和基B，则修正单纯形方法就可进行下去了3.4 3.4 修正单纯形方法修正单纯形方法4 4修正单纯形方法修正单纯形方法4) 把主列置于逆矩阵表的右边，组成下列表3.4 3.4 修正单纯形方法修正单纯形方法5 5例3.4.1，用修正单纯形法解下列LP3.4 3.4 修正单纯形方法修正单纯形方法

59、-6-6约束方程的系数矩阵3.4 3.4 修正单纯形方法修正单纯形方法-7-70000100501060013第1次迭代：3.4 3.4 修正单纯形方法修正单纯形方法-8-800001005010600133-11-1x4第二次迭代3.4 3.4 修正单纯形方法修正单纯形方法-9-9计算主列3.4 3.4 修正单纯形方法修正单纯形方法-10-103.4 3.4 修正单纯形方法修正单纯形方法-11-11计算主列3.4 3.4 修正单纯形方法修正单纯形方法-12-12第4次迭代3.4 3.4 修正单纯形方法修正单纯形方法-13-132 逆的乘积形式 初看起来，用修改的(m+1)(m+1)矩阵代替(

60、m+1)(n+1)的表，似乎明显的节省了计算量。然而这一方法需要计算原问题表中的yj和wpj，若对每一个非基序列都要进行这样的计算，则需要m(n-m)次乘法。这个数量并不明显小于原单纯形算法中计算量。然而这个算法重要性在于其精巧和在其他一些问题上的很好应用。下面我们将给出一种改进形式的方法，其基的逆矩阵以乘积形式存储，从而节省了存储空间。3.4 3.4 修正单纯形方法修正单纯形方法-14-143.4 3.4 修正单纯形方法修正单纯形方法-15-15由(3.4.8)式得到由于3.4 3.4 修正单纯形方法修正单纯形方法-16-163.4 3.4 修正单纯形方法修正单纯形方法-17-17下面讨论如

61、何利用初等阵来计算单纯形方法中所需数据。3.4 3.4 修正单纯形方法修正单纯形方法-18-18(1)用初等阵E右乘一个行向量(2) 用E左乘一个列向量3.4 3.4 修正单纯形方法修正单纯形方法-19-19(3)计算有关递推公式3.4 3.4 修正单纯形方法修正单纯形方法-20-20例3.4.2，用改进修正单纯形法解LP3.4 3.4 修正单纯形方法修正单纯形方法-21-21约束方程的系数矩阵3.4 3.4 修正单纯形方法修正单纯形方法-22-223.4 3.4 修正单纯形方法修正单纯形方法-23-23第二次迭代3.4 3.4 修正单纯形方法修正单纯形方法-24-24计算主列3.4 3.4

62、修正单纯形方法修正单纯形方法-25-253.4 3.4 修正单纯形方法修正单纯形方法-26-26第3次迭代最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8145， 对偶理论与灵敏度分析第四章 对偶理论与灵敏度分析对偶理论对偶单纯形法原始-对偶算法灵敏度分析4. 对偶问题 重新考虑食谱问题。以出售奶和蛋给需要维生素的人的食品杂货商的利益出发，他知道奶和蛋按其维生素Vc和Vb的含量而有一定的价值。他的问题是确定出售维生素Vc的价格x和维生素Vb的价格 y：他不能将价格订得高于奶和蛋的市场流行价，否则将失去他的顾客；他希望商店的总收入为最大。维生素奶中含

63、量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.54. 对偶问题（续一）Max 40x + 50y s.t. 2x + 3y 3 4x + 2y 2.5 x, y 0.极大化目标函数极大化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解4. 对偶问题（续二） 对比一下从消费者和供应商各自的利益导出的两个问题，我们不难发现两个问题可以通过下述简单的变换，而相互转化：极小化费用 Min 大于等

64、于约束 食品费用 极大化利润Max小于等于约束 价格约束 当你把食谱问题的对偶问题解出以后（练习练习），你会发现一个（重要的）事实：这两个问题的最优值是相等的！思考题思考题：在数学上，是不是还有一些对偶的问题和概念？4. 对偶理论14.1 LP的对偶理论Primal Min cx s.t. Axb, (4.1.1) x0Dual Max wb s.t. wAc, (4.1.2) w04.1.1 对偶问题的表达1,对称形式的对偶2,非对称形式的对偶Primal Min cx s.t. Ax=b, x0Dual Max wb s.t. wAc, w 无约束(4.1.3)(4.1.4)4. 对偶理论

65、23,一般形式的对偶Primal化为等价的标准形式化为等价的标准形式4. 对偶理论3写成矩阵形式按非对称 对偶的定义,得上述LP 的对偶问题4. 对偶理论4于是原 LP的对偶(Dual)4. 对偶理论5以上分析可知有如下关系4. 对偶理论6引理1 对偶问题的对偶是原始问题 (The dual of the dual is the primal.)4. 对偶理论7即得原问题4. 对偶理论9例4.1.2 设原问题4. 对偶理论10例4.1.2 设原问题4. 对偶理论11例4.1.3 设原问题4. 对偶理论12于是可得对偶问题4. 对偶理论135.1.2 对偶定理 注意到,原问题和对偶问题是由同一数

66、据集(A,b,c)所定义，且对偶问题的对偶即是原问题，因此可以选原始-对偶对中任一为原问题，而另一则自动为对偶。下面讨论两者间的关系。4. 对偶理论14推论2 对偶规划(4.1.1)和(4.1.2)有最优解的 充要条件是它们同时有可行解。推论3 若原问题(4.1.1)的目标函数值在可行域上无下界,则其对偶问题无可行解;反之,若对偶(4.1.2)的目标函数值在可行域上无上界,则原问题无可行解.5. 对偶理论4. 对偶理论15 不可行 无界 有限最优解不可行无界有限最优解P D定理定理4.1.2 设设(4.1.1)和和(4.1.2)中有一个问题存在最优中有一个问题存在最优解，则另一个问题也存在最优

67、解，且这两个问题解，则另一个问题也存在最优解，且这两个问题的最优目标函数值相等。的最优目标函数值相等。证明：设证明：设(4.1.1)存在最优解。引进松弛变量，将存在最优解。引进松弛变量，将（4.1.1）写成等价形式：）写成等价形式：4. 对偶理论16由于(4.1.12)存在最优解，因此能用单纯形方法求得一个最优基本可行解。 不妨设此最优解为相应的最优基为B.此时所有判别数满足：4. 对偶理论17即把所有松弛变量在基下对应的判别数所满足的条件(4.1.13)用矩阵表示,得 4. 对偶理论184. 对偶理论194.1.3互补松弛性质4. 对偶理论204. 对偶理论21例4.1.3 求解如下LP4.

68、 对偶理论224. 对偶理论234. 对偶理论对偶单纯形法对偶单纯形法 14.2 对偶单纯形法对偶单纯形法 4.2.1对偶单纯形法基本思想对偶单纯形法基本思想4. 对偶理论对偶单纯形法2注:对偶可行的基本解不一定是原问题的可行解.若还是原问题的可行解,则此解即为最优解. 回忆(修正)单纯形法的基本思路是保持原问题的可行性和互补松弛条件下,在它的最优解上寻求对偶问题的可行性.类似的,对偶单纯形法的基本思路是:在保持对偶可行性和互补松弛条件下,在它的最优解上寻求原问题的可行性. 4. 对偶理论对偶单纯形法对偶单纯形法 34. 对偶理论对偶单纯形法对偶单纯形法 4下面分析如何选取离基变量和进基变量.

69、设在某次迭代中得到如下表:4. 对偶理论对偶单纯形法对偶单纯形法 54. 对偶理论对偶单纯形法对偶单纯形法 64. 对偶理论对偶单纯形法对偶单纯形法 7下面说明上述转换能改进对偶可行的基本解.2)主元消去后仍然保持对偶可行性,即所有判别数都小于或等于0(对极小化问题)4. 对偶理论对偶单纯形法对偶单纯形法 84. 对偶理论对偶单纯形法对偶单纯形法 9即对偶问题的目标函数值在迭代过程中单调增(非减).对偶问题的可行解w越来越接近最优解.原问题的对偶可行的基本解将向着满足可行性方向转化而接近原问题最优解.4. 对偶理论对偶单纯形法对偶单纯形法 104. 对偶理论对偶单纯形法对偶单纯形法 11例例1

70、4. 对偶理论对偶单纯形法对偶单纯形法12 4. 对偶理论对偶单纯形法对偶单纯形法 134. 对偶理论对偶单纯形法对偶单纯形法 144. 对偶理论对偶单纯形法对偶单纯形法 154. 对偶理论对偶单纯形法对偶单纯形法164.2 初始对偶可行的基本解初始对偶可行的基本解对偶单纯形法中要求先给出一个初始的对偶可行的 基本解.这个解未必直接能求出,因此需要引进一个方法与单纯形法中类似,我们也是通过解一个辅助问题-扩充问题来求解.扩充问题的构造 扩充问题的构造:先给出(4.2.1)的一个基本解(这很容易).不妨设A的前m列线性无关,由这m列构成基矩阵B.于是(4.2.1)可改写成 4. 对偶理论对偶单纯

71、形法对偶单纯形法17 4. 对偶理论对偶单纯形法对偶单纯形法18 在(4.2.10)中以系数矩阵的前m列和第n+1列组成的m+1阶单位矩阵为基,则得一个基本解4. 对偶理论对偶单纯形法对偶单纯形法19上述做法是正确的上述做法是正确的,因为主元消去运算前后判别数之间有如因为主元消去运算前后判别数之间有如下关系下关系:综上立明4. 对偶理论对偶单纯形法对偶单纯形法20 注意到注意到(4.2.10)的对偶问题有可行解的对偶问题有可行解,故用对偶单纯形方法故用对偶单纯形方法求解求解(4.2.10)时时,仅有如下两种情况发生仅有如下两种情况发生:(1)扩充问题无可行解扩充问题无可行解,则原问题亦无可行解

72、则原问题亦无可行解.(反证反证)4. 对偶理论对偶单纯形法对偶单纯形法21 例例2.24. 对偶理论对偶单纯形法对偶单纯形法22 于是得扩充问题构作单纯形表4. 对偶理论对偶单纯形法对偶单纯形法23 4. 对偶理论对偶单纯形法对偶单纯形法24 4. 对偶理论对偶单纯形法对偶单纯形法25 例例2.3 4. 对偶理论对偶单纯形法对偶单纯形法 26把约束矩阵置于单纯形表中4. 对偶理论对偶单纯形法对偶单纯形法27 4. 对偶理论对偶单纯形法对偶单纯形法28 4. 对偶理论对偶单纯形法对偶单纯形法 294.3 原始对偶算法1基本思想 这一方法实际上是由某些网络问题的一个特殊算法发展起来的.构造对偶问题

73、考虑原问题互补松弛条件是:如果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),此信息告诉我们如何修改 ,于是得到新的 .重复此过程,在有限步内

74、就收敛到最优解4.3 原始对偶算法4原始P对偶D限制原始RP限制原始对偶DRP调整到算法开始时是D的可行解且始终保持对偶可行性.在c0时可直接取=0为初始对偶可行解. 当c不是非负的时候,应用Beale等人的方法很容易的找出可行解:4.3 原始对偶算法5原始对偶算法原始对偶算法显然增加约束后不会改变原问题P的解,此时新的原始问题的对偶为4.3 原始对偶算法6中将有一些取严格不等式,而另一些取等式.设取等式的约束指标集为J:4.3 原始对偶算法7因此不妨设D有一可行解,则不等式约束这即相当于求一个x,使得满足4.3 原始对偶算法8称J为允许列集合.为找出这样的x,构造新的LP,称为限制的原始问题

75、(RP):利用单纯形法求解此RP:若最优值为0则已找到(6)的解,因此也是P的最优解.若最优值大于0,如何处理?4.3 原始对偶算法9为解决此问题,需要考察限制的原始问题RP的对偶DRP4.3 原始对偶算法10现在我们处于这样的情形:试图只应用允许列来找出一个可行解x,但由于RP的最优值0,所以努力失败了这就可能考察利用原来的和新得到的 来校正4.3 原始对偶算法11因为RP和DRP是一对相互对偶的规划,所以它们的最优值相等.因此有但是我们得到了RP的最优解及其对偶的最优解,所以我们应该选取0,从而改进D的费用4.3 原始对偶算法12为维持可行性,只需考察下述不等式4.3 原始对偶算法13此时

76、,可行性准则变为于是有4.3 原始对偶算法14当解限制的原始问题并达到了改进D的解的时候,我们重新定义集合J,然后重复上述过程直到或者opt=0并因此得到P的最优解,或者由定理1知P无可行解.Procedure primal-dual4.3 原始对偶算法15begin infeasible:=no, opt:= no let be feasible in D(comment:possible by(3) ); while infeasible:=noand opt:= no do begin set solve RP by the simplex algorithm if opt=0 then

77、 opt:= yes else if then infeasible:=yes else endend4.3 原始对偶算法16我们运用表格形式进行迭代。初始表结构如下：此表中原来变量xj 中仍属于限定问题中.即 jJ,则用在上方标注.解RP的进离基运算在标的列和y的列进行限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可4.3 原始对偶算法17求解每一限定原始问题的过程中除第m+2行外，均作运算但只能是属于限定原始问题的变量才有资格作为进基 变量。4.3 原始对偶算法18“限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可

78、”的理由理由下面求解上述LP。首先找出对偶问题的一个可行解。例4.3.1的对偶是： 4.3 原始对偶算法19于是得一阶段问题显然w=(0,0)是一个可行解，此时有4.3 原始对偶算法20变量上方的标识符表示该变量属于RP4.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问题

79、达到最优，最优值Z0=0，因此得原问题的最优解 x*=(x1,x2,x3)=(2,1,0)目标函数的最优值fmin=5,对偶问题的最优解w=(0,1).3354.4 4.4 灵敏度分析灵敏度分析1，引入2，改变系数向量3，改变右端向量4，改变约束矩阵5，增加新的约束336前面讲的线性规划问题中，都假定问题中 是已知常数。但实际上这些数往往是一些估计和预测的数字市场条件变化，价值变量 cj就会变化aij是随工艺技术条件的改变而改变而值bi则是根据资源投入后能产生多大经济效益来决定的一种决策选择. 在大多数实际问题中。不仅要求求出问题的最优解，而且还希望知道当问题中的某些参数改变时最优解怎样变动。

80、参数的变化可分为离离散的散的和连续的连续的两种。 灵敏度分析灵敏度分析是指对系统或事物因周围条件离散变化显示出来的敏感程度的分析，即对最优解的影响进行分析研究。而参数规划则是研究参数连续的变化时对最优解的影响1 1 引入引入337这就是灵敏度分析所要研究解决的问题。因此就会提出以下问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化?这些参数在一个多大范围内变化时，问题的最优解变不变?影响最优解的参数有如下几类：改变费用系数cj改变右端费用bi改变约束方程的系数矩阵A加入新的约束参数变化后的结果最优解不变：最优 基及其取值不变基变量不变但取值 改变基变量改变，取值 亦改变338原

81、问题原问题 对偶问题对偶问题 结论或继续计算的步骤结论或继续计算的步骤 可行解可行解非可行解非可行解 可行解非可行解可行解非可行解 问题的最优解或最优基不变用单纯形法继续迭代求最优解对偶单纯形法继续迭代求最优解原始/对偶单纯形算法或引进人工变量，编制新的单纯形表重新计算 重新解新线性规划问题？重新计算发生变化的个别系数,判断问题现状,采取如下措置339考虑标准LP问题为RHS 0假定得到最优单纯形表如下(4.4.1)2 改变系数向量改变系数向量 c 340当价值向量c改变时, 在单纯形表里受影响的只是检验数和目标函数值，其它没有改变，因而只需计算新的检验数和目标函数值如果检验数非正，则原最优解

82、依然是最优解；否则是基本可行解，以此为初始基可行解按单纯形法进行迭代就可以求出新问题的解。3411、情形I: 是非基变量改变非基变量的价值向量 ：若 ，由单纯形法计算公式知，只有检验数 起变化, 则原最优解依然是最优解；否则,由此进行单纯形迭代。即价值向量只有一个分量新的检验数 3422、情形、情形II: 是基变量是基变量基变量对应的约束为第 L个, 即改变基变量 的价值向量 ,问题最后一张单纯形表中，新检验数(因基变量检验数要求0)新目标函数值把单纯形表上的第L行元素乘以 加到检验数行上，再令得到对应新问题的单纯形表。总总之之343例例1最优解:(x1,x2,x3,x4,x5,x6)=(5,

83、3,1,0,0,0) 344检验数仍非负, 问题原最优解仍是此时最优解;更多信息更多信息:对非基变量的价值系数在某范围变化最优解都不发生改变最优解都不发生改变最优解都不发生改变同同理理最优解都不发生改变非非基基变变量量345 x1 x2 x3 x4 x5 x6 RHS z 0 0 0 0 -1 0 -18 x2 0 1 0 1/4 0 -1/4 3 x1 1 0 0 -1/6 1/3 1/2 5 x3 0 0 1 5/12 -1/3 1/4 1 若检验数向量非负数，而右端向量没变，故仍最优解，否则用单纯形算法即可。基基变变量量把最优单纯形表的第3行乘以 1-(-1) 加到检验数行上再令得到对应

84、新问题的单纯形表3461. 基本思想基本思想RHS 0如果 ，则已发现新问题的最优解，否则利用对偶单纯形算法求解新问题。3 改变右端向量改变右端向量 b347其中 为 的第 r 列。当只改变一个分量时：如果 ，则已发现新问题的最优解.因新问题的单纯形表检验数向量不变， 仍有否则，单纯形表对应新问题的一个基本(不可行)解和故可用对偶单纯形法继续求解。对偶问题的一个可行解，348b3由3变成5时，续上例仍是最优基本可行解。349b3由3变成11时，单纯形表对应新问题的一个基本(不可行)解和故可用对偶单纯形法继续求解。对偶问题的一个可行解， z x1 x2 x3 x4 x5 x6 RHS z 0 0

85、 0 -5/6 -1/3 -1/2 -18 x2 0 1 0 1/4 0 -1/4 -1 x1 1 0 0 -1/6 1/3 1/2 9 x30015/12-1/31/43 此时单纯形表3504 4 改变约束矩阵改变约束矩阵A有如下两种情形351此时情况较复杂，若只有少数列发生变化可用如下方法3523535 5 加入新的约束加入新的约束 设原有约束为Ax=b，在此基础上，我们增加一个新的约束(2)若原问题的最优解不满足新的约束，则需要把新的约束条件增加到原来的最优表中再解新问题。设原来的最优基为B。最优解为354355356357358359360361362总结总结:当原问题只有个别数据改变

86、, 特别是变化幅度不大时, 用灵敏度分析比对新问题重新求解简单, 在现实中市场因素(价值系数) , 生产资料(右端向量), 生产技术(矩阵元素)随时在变化, 而参数的变化必然引起模型的变化最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8147， 最优性条件第七章 最优性条件无约束问题的极值条件约束极值问题的最优性条件对偶及鞍点7.17.1无约束问题的极值条件无约束问题的极值条件考虑非线性规划问题1，无约束极值问题称为无约束极值问题（UNLP）7. 最优性条件-无约束17. 最优性条件-无约束2Th7.1.1(非极小点的充分条件) 设f(x)在点x*

87、处可微,若存在方向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*)d 0 使得对 任意(0, ), f(x*)d+|d|(x*;d)0 .定理立明.定理定理7.1.2-3(极小点的

88、必要条件)设x*处是问题(UNLP)的局部极小点.(1)当 f(x) 在 x*可微时,则梯度 f(x*)=0.(2) 当f(x) 在 x*二次可微时. 则 f(x*)=0 且 Hessian 矩阵 H(x*) 是半正定的7. 最优性条件-无约束4(2). 给定任意向量 d. 由 f(x) 在 x*的二次可微性，有f(x*+d)=f(x*) +f(x*)d+ dH(x*)d/2+ |d| (x*;d) (I), 其中 (x*;d) 0( 0). 由（1）的证明有 f(x*)=0. 移项整理并两端除以 , 得 =dH(x*)d/2+|d| (x*;d) (II).因 x* 局部极小, 对充分小 有

89、f(x*+d)f(x*) 2222 f(x*+d)f(x*)22证明证明(1). 若f(x*)0, 作 d=f(x*). 则有 f(x*) d 0 使得 f(x*+d)f(x*)， (0, ), 此与 x* 为局部极小相矛盾，故 f(x*)=0.7. 最优性条件-无约束5dH(x*)d/2+|d| (x*;d)0 2由(II), 显见对充分小的 成立 , 对 0取极限, 则有 dH(x*)d 0, 从而,H(x*) 半正定定义定义1 若f(x)在点x*处可微,且f(x*)=0,则称x*为f(x)的一个驻点驻点或平稳点平稳点.d(0)Rn, 既不是极大点也不是极小点的驻点称为鞍点鞍点.Th7.1

90、.4 (二阶充分条件二阶充分条件). 假设 f(x) 在 x*点二次可微,若 f(x*)=0 且 Hessian 矩阵 H(x*) 是正定的,则 x* 是(UNLP)的一个(严格)局部极小点3，二阶充分条件，二阶充分条件7. 最优性条件-无约束6证明证明. 因 f 在 x* 二次可微,故对任意 x, 有 f(x)=f(x*)+f(x*)(x-x*)+(x-x*)H(x*)(x-x*)/2+|x- x*| (x*; x- x*), 这里 (x*; x- x*) 0,当 xx*. 假设命题不真， x* 不是局部极小, 则存在序列 xk 收敛到 x* 并使得 f(xk) 0 使得 f(x*+d)f(

91、x*)（ (0, )）,则 d 称为 f(x) 在 x*的下降方向(decedent direction)设 f(x) 在 x*可微. 若存在向量 d 满足 f(x*)d0, 则 由Th7.1.1, d 是 f(x) 在 x*.的下降方向。记所有这样的向量集合为7. 最优性条件-有约束3由可行方向定义和下降方向知，可行方向定义和下降方向知， 从点 x*, 沿可行方向 dD(x*) 作一个很小的移动还是可行点. 进一步，由 Th 7.1.1, 若 f(x*)d0 ，则d 是f在 x*的下降方向。下面定理将说明 若 x* 是局部最优且 f(x*)d0, 则 dD(x*).即不是可行方向。Theor

92、em 7.2.1. (必要条件必要条件) 考虑极小化问题考虑极小化问题： min f(x) ，subject to xS,其中其中 S 是是 Rn 中非空集合中非空集合，设设 f(x) 在在 x*可微。若可微。若 x* 是局部极是局部极小点，则小点，则 F0(x*)D=,其中其中 F0(x*)=d |f(x*)d0, f(x*+ d)0， x*+ d S ， (0, 2)此与局部极小矛盾。此与局部极小矛盾。3797. 最优性条件-不等式约束1为把最优性的几何条件用代数来表示，引入起作用约束的概为把最优性的几何条件用代数来表示，引入起作用约束的概念。问题的约束条件在点念。问题的约束条件在点x*

93、* S S处有两种情形处有两种情形3 不等式约束的一阶最优性条件不等式约束的一阶最优性条件1，I= i| gi(x*)=0在x*处起作用约束2， gi(x*)0. iI在x*处不起作用约束G0(x*)=d |gi(x*)d0 , iI .3807. 最优性条件-不等式约束2证明概要证明概要. 设设 d G0(x*).因因 S 为开集，则存在为开集，则存在 10 使得对使得对 (0, 1)， x* + d S。 另外存在另外存在 20使得使得对对 (0, 2) ，i I. gi(x*+ d)0,最后存在最后存在 30 使得使得对任意对任意 (0, 3) and i I有有gi(x*+ d)gi(

94、x*), 从而从而 d D, D 是是 x*处的可行方向锥处的可行方向锥. 于是于是G(x*) D. 由由Th 7.2.1, 立明。立明。Th7.2.2. (必要条件必要条件) 考虑极小化问题考虑极小化问题 min f(x) subject to gi(x)0， i=1, m ，x S, 其中其中 S 是是 Rn中的非空开集。中的非空开集。 设设 x* 为可行点，为可行点， I= i| gi(x*)=0. 进一步假设，进一步假设， f(x) 和和 gi(x) （ i I ）在）在 x* 可微，可微， gi （ i I） 在在 x*连续连续. 若若 x* 是局部最优解，则是局部最优解，则 F0(

95、x*) G0(x*)=, 其中其中F0(x*)=d | f(x*)d0， i I .7. 最优性条件-不等式约束3g1(x)=-x - y + 5,g2(x)=-x - y + 3,g3(x)=x,g4(x)=y； I=2f(x)2(x 3),2(y 2) 2 2Min (x-3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222f(x*)g2(x*)(9/5, 6/5)F(x*)G(x*). g2(x)g1(x)x*7. 最优性条件-不等式约束4Min (x-3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222x*=(2,

96、 1)g1(x*)=(-4, -2),g2(x*)=(-1, -1),f(x*)(-2, -2)f(x*)g1(x*)x* 是最优解g2(x*)(2,1)x*7. 最优性条件-不等式约束5Th7.2.3. (Fritz John Condition, 1948)考虑极小化问题考虑极小化问题 min f(x) subject to gi(x)0， i=1, m ，x S, 其中其中 S 是是 En.中非空开集中非空开集. 设设 x* 为可行点为可行点, I= i| gi(x*)=0. 进一进一步假设步假设 f(x) 和和 gi(x)( i I )在在 x* 可微可微, gi ( i I) 在在

97、x*连续连续. 若若 x* 是局部最优解是局部最优解.则则存在一组非负数存在一组非负数 u0 , ui ( iI )使得使得 u0f(x*) - uigi(x*)=0, u0, ui0 for iI and (u0, uI)0.iI进一步进一步, 若若 gi(x) ( iI) 在 x*也可微，则 u0f(x*) uigi(x*)=0, uigi(x*)=0, u0, ui (所有 i ) ，且 (u0, u)0.i=1i=m3847. 最优性条件-不等式约束6证明证明. 由由Th7.2.2, 不存在向量不存在向量 d 同时满足同时满足 f(x*)d0 和和 gi(x*)d0 ，( i I).

98、设设 A 是其行由是其行由 f(x*) 和和 gi(x*)(i I)组成的矩阵组成的矩阵. 则则 Ad0,可以对约束强加某种限制，这种限制条件叫做约束规格或约束品性( constraint qualifications).已有很多的约束规格，特别的, Karush 1939, MS Thesis, Dept of Math, Univ of Chicago , Kuhn 和 Tucker 1951 独立给出的最优性必要条件恰是 Fritz John 条件条件加上加上 u00.7. 最优性条件-不等式约束12Th7.2.4. (Karush-Kuhn-Tucker 必要条件必要条件)考虑极小化问

99、题考虑极小化问题 min f(x) subject to gi(x)0， i=1, m ，x S, 其中其中 S 是是 En.中非空开集中非空开集. 设设 x* 为可行点为可行点, I= i| gi(x*)=0. 进一进一步假设步假设 f(x) 和和 gi(x)( i I )在在 x* 可微可微, gi ( i I) 在在 x*连续连续. gi for iI 线性独立线性独立.若若 x* 是局部最优解是局部最优解.则则存在一组非负数存在一组非负数ui( iI )使得使得 f(x*) uigi(x*)=0, ui 0 ( iI ).iI若还有若还有 gi ( i I )在在 x*可微可微, 则则

100、 f(x*) uigi(x*)=0, uigi(x*)=0, ui0 ， i=1, m.i=1i=m7. 最优性条件-不等式约束13Karush-Kuhn-Tucker 条件可写成向量形式条件可写成向量形式f(x*)-ug(x*)=0, ug(x*)=0, u0.这表明 f(x*) 属于起作用约束的这些约束的梯度所形成的锥中。7. 最优性条件-不等式约束147. 最优性条件-不等式约束157. 最优性条件-不等式约束167. 最优性条件-不等式约束173967. 最优性条件-不等式约束18Th7.2.5. (Karush-Kuhn-Tucker 充分条件充分条件)考虑极小化问题考虑极小化问题

101、min f(x) subject to gi(x)0， i=1, m ，x S, 其中其中 S 是是 En.中非空开集中非空开集. 设设 x* 为可行点为可行点, I= i| gi(x*)=0. 设设f(x)和诸和诸 gi 是凸的，是凸的， 进一步假设进一步假设 f(x) 和和 gi(x)( i I )在在 x* 可可微微, gi ( i I) 在在 x*连续连续. 若若 K-K-T条件在条件在 x*成立，则成立，则x*是全局是全局最优解最优解.证明略证明略7. 最优性条件-等与不等式约束14.一般约束问题的一阶最优性条件记7. 最优性条件-等与不等式约束27. 最优性条件-等与不等式约束37

102、. 最优性条件-等与不等式约束4证明略7. 最优性条件-等与不等式约束57. 最优性条件-等与不等式约束67. 最优性条件-等与不等式约束77. 最优性条件-等与不等式约束87. 最优性条件-等与不等式约束97. 最优性条件-等与不等式约束10现定义两集合7. 最优性条件-等与不等式约束117. 最优性条件-等与不等式约束12例:7. 最优性条件-等与不等式约束13例7. 最优性条件-等与不等式约束147. 最优性条件-等与不等式约束15KKT最优性必要条件（Th2.4）加以推广。这是通过增加约束规格来实现的.前面FJ条件中w0不一定为正, 在下面定理中。我们将前面提到的7. 最优性条件-等与

103、不等式约束16进一步假设,gi ( iI )在 x*, 连续可微,则 f(x*)+ uigi(x*)+ vjhj(x*) =0, uigi(x*)=0, ui(i=1, m.)i=1i=mo若采用矩阵和向量记号,则KKT可如下简洁表示定义定义Lagrange函数为函数为(7.2.48)7. 最优性条件-等与不等式约束17则KKT条件可表为7. 最优性条件-等与不等式约束187. 最优性条件-等与不等式约束197. 最优性条件-等与不等式约束205.二阶条件7. 最优性条件-等与不等式约束21为此,我们考虑函数的二阶导数,首先给出如下定义7. 最优性条件-等与不等式约束22例7. 最优性条件-等

104、与不等式约束237. 最优性条件-等与不等式约束24现在我们考虑问题(7.2.1).7. 最优性条件-等与不等式约束257. 最优性条件-等与不等式约束267. 最优性条件-等与不等式约束277. 最优性条件-等与不等式约束287. 最优性条件-等与不等式约束297. 最优性条件-等与不等式约束307. 最优性条件-等与不等式约束317. 最优性条件-等与不等式约束32为给出局部最优解的二阶充分条件，我们定义集合7. 最优性条件-等与不等式约束337. 最优性条件-等与不等式约束347. 最优性条件-等与不等式约束35下面分两种情况讨论7. 最优性条件-等与不等式约束367. 最优性条件-等与

105、不等式约束377. 最优性条件-等与不等式约束387. 最优性条件-等与不等式约束39例7.2.7 考虑下列非线性规划问题检验以下各点是否为局部最优解7. 最优性条件-等与不等式约束40记目标函数和约束函数分别为f(x),g(x),h(x),他们在点x处的梯度分别是Lagrange函数是Lagrange函数关于x的Hessian矩阵是7. 最优性条件-等与不等式约束417. 最优性条件-等与不等式约束427. 最优性条件-等与不等式约束43后两点请自行验证之7. 最优性条件-等与不等式约束44例7.2.8 考虑下列非线性规划问题记目标函数和约束函数分别为f(x), h(x),他们在点x处的梯度

106、分别是7. 最优性条件-等与不等式约束45例7. 最优性条件-等与不等式约束467. 最优性条件-等与不等式约束47Ch7.3 对偶理论17.3.1 对偶形式Ch7.3 对偶理论2其对偶形式其对偶形式(对偶问题对偶问题)定义如下定义如下Ch7.3 对偶理论3于是(LP)问题(*)的对偶形如Ch7.3 对偶理论4Ch7.3 Ch7.3 对偶理论对偶理论5 57.3.2 对偶定理对偶定理对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即1. 1. 弱对偶定理弱对偶定理Ch7.3 对偶理论6Ch7.3 对偶理论72. 2. 凸规划与凸规划与SlaterSlat

107、er约束规格约束规格Ch7.3 对偶理论8Ch7.3 对偶理论93. 强对偶定理强对偶定理Ch7.3 对偶理论10证明:先证第一部分:(1)无解=(2)有解. 令集合Ch7.3 对偶理论11Ch7.3 对偶理论12Ch7.3 对偶理论13Ch7.3 对偶理论14例 考虑如下约束优化问题显然该问题无最优解,但目标函数的下确界fmin=0.该问题的Lagrange对偶函数Ch7.3 对偶理论157.3.3 鞍点定理鞍点定理Ch7.3 对偶理论16o1 鞍点与最优解Ch7.3 对偶理论17Ch7.3 对偶理论18对于(2),在假设条件成立时,根据强对偶定理5.11,对于问题(PNLP)的最优解 ,存

108、在 ,使得Ch7.3 对偶理论192. 鞍点与鞍点与KKT点点最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8148， 算法第八章 算法算法概念算法收敛问题ch8 算法-概念8.1.1 算法映射下降，即对某个函数，在每次迭代中后继点处的函数值要有所减小。迭代下降算法考虑极小化问题 f(x) s.t. xS 这里f是目标函数，S是可行域。对于求解这一问题的解答程序或算法可以看作是一个迭代过程，这过程按照规定的一组指令和终止准则一起产生一个点序列。ch8 算法概念Df 8.1.1 算法A是定义在空间X上的点到集映射,即对每一个点xX,给定一个子集A(x

109、)X.Ch8 算法-概念ch8 算法概念如图所示,应用算法A时,经A作用得到一个闭区间,从此区间中任取一点作为后继点,重复这个过程,得一由算法产生得点列,在一定条件下,它收敛于问题的解.如3,2,3/2,5/4, 3,3/2,9/8,33/32, etc.x*=1xk+1xkxk+1A(x)x*=1xk+1xkxk+1A(x)ch8 算法概念8.1.2 解集合为了求解上述问题，要求使用的算法具有这样的性质： 由算法产生的点列收敛于整体最优解然而，在许多情形下，要满足这一点很难做到。事实上由于非凸性，问题的规模和其它一些困难，达到整体最优几乎不可能，因此当达到属于预定集的某一点达到，则可以停止迭

110、代，这个预定集就称之为解集合常用的解集合有如下几种类型Ch8 算法概念ch8 算法概念8.1.3 下降函数Ch8 算法概念8.1.4 闭映射Ch8 算法概念设是整体最优解的集合，即=1。考虑算法映射，定义为映射在下图中说明Ch8 算法概念此例表明算法在区间此例表明算法在区间(-,2)上上收敛于集收敛于集 中点，而在中点，而在2，)上却不收敛于上却不收敛于 中点，中点，从而算法从而算法不是闭不是闭的显然对任何初始点显然对任何初始点x12, 由映射由映射A产生的任何序列都收敛于点产生的任何序列都收敛于点x*=2，对初始点对初始点x12, 由映射由映射A产生的任何序列都收敛于点产生的任何序列都收敛于

111、点x=1.Ch8 算法概念评注：上面例子表明初始点x1选取的重要性：若x1 2则达到收敛于中的点，否则就不能实现。另注意注意到，在上例中都满足如下条件：但对任何但对任何x12都不收敛于都不收敛于 x*=1 ,即算法不是闭的即算法不是闭的 1，给出一可行点xk 1,任何后继点xk也是可行的,即xk+1 12，给出一个不在解集内的可行点xk,任何后继点xk+1满足 f(xk+1)f (xk), 其中其中f(x)=x2. 即目标函数严格下降。3，给出一在内的可行点xk(=1),任何后继点xk+1也在内,即 xk+1 =1Ch8 算法概念l8.1.5, 合成映射合成映射x XYZB(x)yA (x)C

112、(y)BACCh8 算法概念Ch8 算法概念Ch8 算法-收敛定理8.2.1收敛定理Ch8 算法-收敛定理Ch8算法-收敛定理Ch8 算法-收敛定理Ch8 算法-收敛定理Ch8 算法-收敛定理8.2.2实用收敛准则正如在收敛定理中所指出，若我们达到解集中的一个点时，就终止算法。然而，在大多数情形下，收敛于中的点仅仅出现在极限意义上，因此我们必须依靠终止迭代过程的某些实际规则，下面给出一些常用的终止规则。这里0和正整数N是预先给定的。1)|xk+Nxk| 如果如果应用映射用映射A的的N次后移次后移动的距离小于的距离小于时，算法，算法终止止Ch8 算法-收敛定理Ch8 算法-收敛定理8.2.3 收

113、敛速率 最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼8149， 一维搜索第九章 一维搜索一维搜索的基本概念试探法函数逼近法9. 一维搜索一维搜索-概念1最优化方法的基本结构：给定初始点x0 (a)确定搜索方向dk，即按照一定规则，构造f在xk点处的下降方向 作为搜索方向;(b)确定步长因子k，使目标函数值有某种意义下的下降;(c)令 xk+1 = xk +kdk 若xk+1满足某种终止条件 则停止迭代，得到近似最优解xk+1， 否则，重复上述步骤。9.1 一维搜索概念一维搜索概念9. 9. 一维搜索一维搜索-概念29. 9. 一维搜索一维搜索-概

114、念3函数逼近法/插值法试探法一维搜索一维搜索算法的闭性一维搜索算法的闭性假设一维搜索是以x为起点,沿方向为d的进行的,并定义为算法映射算法映射M9. 9. 一维搜索一维搜索- -概念4Th9.1.1 设f是定义在Rn的连续函数,d0,则(9.1.4)定义的算法映射M在(x,d)处是闭的9. 9. 一维搜索一维搜索- -概念59. 9. 一维搜索一维搜索- -试探法19.2.1, 0.618法法9. 9. 一维搜索一维搜索- -试探法试探法2 单峰函数具有一些很有用的性质:如果f是a,b上单峰函数,则可通过计算此区间内两不同点的函数值,就能确定一个包含极小点的子区间,从而缩小了搜索区间.单峰函数

115、的一个等价定义：9. 一维搜索一维搜索-试探法试探法39. 一维搜索一维搜索-试探法试探法4 4证明:仅证(1),反证,如若不然,存在点x*a, x(1),使9. 一维搜索一维搜索-试探法试探法5 50.618法的基本思想:通过取试探点使包含极小点的区间(不确定区间)不断缩小,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,此时该区间内任一点都可以作为极小点的近似值.9. 一维搜索一维搜索-试探法试探法6 6由( 2.3)和(2.4)得到9. 一维搜索一维搜索-试探法试探法7 7今考虑( 2.1)的情形,此时新的搜索区间为9. 一维搜索一维搜索-试探法试探法8 89. 一维搜索一维搜

116、索-试探法试探法9 9这样,计算公式(2.5)(2.6)可写为9. 一维搜索一维搜索-试探法试探法10其几何意义:黄金分割率对应的点在单位长区间0,1中的位置相当于其对称点1-在区间0,中的位置ak+lbk+lk+lk+lk+lk+lbk+lak+lakbkkkStep 2Step 39. 一维搜索一维搜索-试探法试探法11算法算法(0.618法法)9. 一维搜索一维搜索-试探法试探法129. 一维搜索一维搜索-试探法试探法132.2 Fibonacci法 Fibonacci法是与0.618法类似的一种分割方法。 它与0.618法的主要区别之一在于：搜索区间 长度的缩短率不是采用黄金分割数，而

117、是采用 Fibonacci数：9. 一维搜索一维搜索-试探法试探法14显然, 这里Fn-k /Fn-k+1相当于0.618法(1.5)-(1.6)中的,每次的缩短率满足9. 一维搜索一维搜索-试探法试探法159. 一维搜索一维搜索-试探法试探法16算法算法(Fibonacci法法)上式表明当上式表明当n 趋于无穷时趋于无穷时,Finonacci法与法与0.618法的区间缩短法的区间缩短率相同率相同,因而也是以收敛比因而也是以收敛比r线性收敛。可以证明线性收敛。可以证明Fibonacci法法是分割方法求一维极小化问题的最优策略，而是分割方法求一维极小化问题的最优策略，而0.618法是近法是近似最

118、优的。似最优的。9. 一维搜索一维搜索-试探法试探法17计算函数值(1 ) , (1).置k=19. 一维搜索一维搜索-试探法试探法18Step 5, 置k:=k+1,转2.9. 一维搜索-试探法试探法192.3 进退法进退法9. 一维搜索-试探法试探法20算法算法( (进退法进退法) )输出a,b9. 一维搜索-函数逼近法函数逼近法11.1.牛顿法牛顿法考虑问题 min f(x), xR1 (3.1)令又令得到(x)的驻点，记做x(k1)，则9. 一维搜索-函数逼近法函数逼近法2在点x(k)附近，f(x)(x)，因此可用(x)的极小点作为目标函数f(x)的极小点的估计。如果x(k)是f(x)

119、的极小点,则利用(3.2)可以得到极小点的一个进一步的估计.于是得到一个序列x(k).9.一维搜索-函数逼近法函数逼近法39.一维搜索-函数逼近法函数逼近法49.一维搜索-函数逼近法函数逼近法59. 9. 一维搜索一维搜索- -函数逼近法函数逼近法6算法算法(牛顿法牛顿法)9.一维搜索-函数逼近法函数逼近法7 7基本思想：用割线逼近目标函数的导函数的曲线y=f (x)把割线的零点作为目标函数的驻点的估计。3.2. 割线法割线法9.一维搜索-函数逼近法函数逼近法8在一定的条件下，这个序列收敛于解：9.一维搜索-函数逼近法函数逼近法9由(3.11)和(3.12)得到9.一维搜索-函数逼近法函数逼近

120、法10上式两端取绝对值，则9.一维搜索-函数逼近法函数逼近法11下面考虑收敛速率，考虑k取充分大的情形。根据（3.14）9.一维搜索-函数逼近法函数逼近法129.一维搜索-函数逼近法函数逼近法139.一维搜索-函数逼近法函数逼近法14基本思想：在极小点附近用二次三项式x逼近目标函数f(x), 令x与f(x)在三点x (1) x(2) f (x(2) , f (x(2) 0 的点.9. 一维搜索-函数逼近法函数逼近法209. 一维搜索-函数逼近法函数逼近法21注意到当a=0时,b0,故当a=0时由(3.40)得这个结果恰好是(3.38).这表明(3.40)是在a=0和a0两种情形下极小点的统一表

121、达式.这样可以解方程组来求出系数a,b,c再代入(3.40),从而可得(x)的极小点x*.9. 一维搜索-函数逼近法函数逼近法22记9. 一维搜索-函数逼近法函数逼近法23算法(两点三次插值法)帅天平帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼81410， 使用导数的最优化方法最优化理论与算法第十章 使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法10.1最速下降法10.110.1最速下降法最速下降法 考虑无约束问题 min f(x), xRn (10.1.1)其中 f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一

122、个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。10.1最速下降法1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数求函数f(x)在点x处下降最快的方向,归结为求10.1最速下降法2由上式知.当时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向最速下降方向.注意注意:在不同的尺度下最速下降方向是不同的.10.1最速下降法3最速下降算法最速下降算法最速下降算法的迭代公式为10.1最速下降法4算法描述算法描述例1.1 用最速下降法求解下

123、列问题第一次迭代目标函数f(x)在点x处的梯度令搜索方向令在直线上的极小点第二次迭代令得到第三次迭代令此时已经满足精度要求,得近似解问题的最优解为x*=(0.0)算法的收敛性算法的收敛性证明证明:最速下降算法A可表示为合成映射A=MD其中D(x)=(x,-f(x),是En En En的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是En En En 映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当 f(x) 0时,M是闭映射.由于f(x)是连续可微实函数,

124、故D连续,据Th8.1.1推论2,A在x(f(x) 0)处是闭的. 其次,当x时, d=-f(x) 0,则f(x) T d0,因此对于yA(x),有f(y)f(x),由此知f(x)是关于A和的下降函数,因此根据Th8.2.1,算法收敛最后,按假设,x(k)含于紧集在上述定理中,若令r=A/a,则 定理表明:条件数越小,收敛越快;条件数越大,收敛越慢.最速下降法存在锯齿现象 容易证明,用最速下降法极小化目标函数时,相邻两个搜索方向是正交的.令10.2 牛顿法10.2.1 迭代格式迭代格式即10.2 牛顿法 (x)=0为求 (x)的驻点,令 注意注意:牛顿法的迭代格式也可以从最速下降方向的角度来理

125、解.下求A度量下的最速下降方向,为此,考虑10.2 牛顿法下面介绍一下A度量及其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为由A, A-1对称正定,故存在对称平方根A1/2 , A-1/2,使得于是10.2 牛顿法去掉绝对值符号,有根据Schwartz不等式,得到10.2 牛顿法即为得到在点x处下降最快的方向,按下式选取d这时上式等号成立,由此确定的方向即度量度量A A意义下意义下的最速下降方向的最速下降方向10.2 牛顿法若取则牛顿法的搜索方向实际上是关于向量椭球范数10.2 牛顿法10.2 牛顿法例 用牛顿法求解下列问题第1次迭代10.2牛顿法第2次迭代10.2 牛顿法第

126、3次迭代继续下去,第4次迭代,得到点列收敛于(1,0),此为最优解.10.2 牛顿法10.2.2 局部收敛性10.2 牛顿法证明:根据(10.2.2)，牛顿算法映射定义为下证(x) 是关于解集合和算法A的下降函数.10.2 牛顿法于是可得从而(x) 是关于解集合和算法A的下降函数10.2 牛顿法10.2 牛顿法当牛顿法收敛时,有下列关系特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数其中A是对称正定矩阵10.2 牛顿法先用极值条件求解.令得最优解下用牛顿法解,任取一初始点x(1)定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可

127、到达函数的极小值点,称此算法具有二次终止性.于是牛顿法具有二次终止性10.2 牛顿法注意,当初始点远离极小点时,牛顿法可能不收敛阻尼牛顿法阻尼牛顿法基本思想:增加了沿牛顿方向的一维搜索.迭代公式为10.2 牛顿法算法(阻尼牛顿法)10.2 牛顿法10.2.3 修正牛顿法修正牛顿法例 用阻尼牛顿法求解下列问题牛顿方向10.2 牛顿法显然,用阻尼牛顿法不能产生新点, 而点x(1) =(0,0) T并不是问题极小点.可见从x(1)出发,用阻尼牛顿法求不出问题的极小点, 原因在于 Hessian 矩阵 2f (x(1)非正定再令10.2 牛顿法考虑 (10.2.2),记搜索方向d(k) = x- x(

128、k) 阻尼牛顿法所用搜索方向是上述方程的解此处假设逆矩阵 存在10.2 牛顿法再沿此方向作一维搜索10.2 牛顿法算法 修正牛顿法10.2 牛顿法10.3共轭梯度法1 1 共轭方向与扩张子空间定理共轭方向与扩张子空间定理定义定义10.3.110.3.1 设A是nn对称矩阵,若Rn 中的两个方向d 1 和d2满足 (d 1)T Ad 2 =0 （10.3.1）则称这两个方向关于A共轭,或称它们关于A正交.则称这组方向是A共轭共轭,或称它们为A的的k个共轭方向个共轭方向10.3 共轭梯度法几何意义几何意义设有二次函数其中A是nn对称正定矩阵, x是一个定点.是以x为中心的椭球面,A正定,故x是f(

129、x)的极小值点.f(x)的等值面由于10.3共轭梯度法设 x(1)是在某等值面上一点,此面在点x(1)处的法向量又设d (1)是在该等值面在点x (1)处的一切向量.d (2) = x - x (1) 即等值面上一点x(1)处的切向量与由这点指向极小点的向量关于A共轭.10.3共轭梯度法10.3共轭梯度法10.3共轭梯度法10.3共轭梯度法用归纳法证之,为方便,用g j表示函数f(x)在x(j)处的梯度,即10.3共轭梯度法利用上式可以将 gm+2 和d (i) 的内积写成当i=m+1时,由一维搜索定义,知当1im+1时,由归纳假设知由二次函数梯度的表达式和点x(k+1)的定义,有10.3共轭

130、梯度法即由10.3.8-11,知10.3共轭梯度法上述定理表明,对于二次凸函数,若沿一组共轭方向(非零向量)搜索,经有限步迭代必到达极小点.2 线性共轭梯度法与二次终止性线性共轭梯度法与二次终止性Hesteness和Stiefel于1952年为解线性方程组而提出基本思想:把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿着这组方向进行搜索,求出目标函数的极小点10.3共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法10.3共轭梯度法10.3共轭梯度法10.3共轭梯度法 综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3.14,3.17-3.19就能伴随计算

131、点的增加,构造出一组搜索方向.10.3共轭梯度法 定理定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:证明: 显然m1,下用归纳法(对i)证之. 10.3共轭梯度法设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),由迭代公式两端左乘A,再加上b,得其中 由式(10.3.17)确定,即10.3共轭梯度法考虑到(10.3.20)和(10.3.18),则10.3共轭梯度法当ji时,根据归纳假设,式(10.3.22)等号右端各项均为0再证1),运用(10.3.18

132、)和(10.3.20),则当j=i时,把(10.3.19)代入上式第一个等号的右端,立得10.3共轭梯度法当ji时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此最后证3),易知综上,对i+1,上述三种关系成立10.3共轭梯度法注意,初始搜索方向选择最速下降方向十分重要, 如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.例例 考虑下列问题取初始点和初始搜索方向分别为10.3共轭梯度法显然, 不是目标函数在 处的最速下降方向.下面,我们用FR法构造两个搜索方向.令10.3共轭梯度法根据公式(10.3.19)

133、,有因此10.3共轭梯度法令根据公式(10.3.19),有10.3共轭梯度法注意注意,在在FR法中法中,初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向因此10.3共轭梯度法可以证明,对于正定二次函数,运用FR法时不作矩阵运算就能求出因子i定理定理10.3.4 对于正定二次函数,FR法中因子i具有下述表达式证明:10.3共轭梯度法10.3共轭梯度法FR法(对二次凸函数)10.3共轭梯度法例3.2 用FR法求解下列问题10.3共轭梯度法令第一次迭代，目标函数f(x)在点x处的梯度10.3共轭梯度法第2次迭代目标函数在点x 处的梯度(2)10.3共轭梯度法构造搜索方向d .先计算因子(

134、2)1令10.3共轭梯度法10.3 共轭梯度法一般迭代格式l3用于一般函数的共轭梯度法非线性共轭梯度法10.3共轭梯度法-PRP(Polak-Ribiere-Polyar-SW(Sorenson-Wolfe-Daniel -Dixon10.3共轭梯度法 FR共轭梯度法10.3共轭梯度法3,如果j n,转步4,否则,转5可以证明,对一般函数,共轭梯度法在一定条件下是收敛的,10.3共轭梯度法FR算法中使用精确线搜索，我们有如下收敛性结果4. 1 拟牛顿条件和算法步骤拟牛顿条件和算法步骤10.4 拟牛顿法基本思想基本思想:牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵

135、工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法,拟牛顿法就是利用目标函数值f和一阶导数g的信息,构造出目标函数的曲率近似，而不需要明显形成Hesse矩阵，同时具有收敛速度快的优点。牛顿法的迭代公式为10.4 拟牛顿法10.4拟牛顿法记10.4 拟牛顿法则(10.4.8)称为拟牛顿条件拟牛顿条件(方程方程)，也称为割线方程割线方程.怎样确定满足这个条件的H k+1 ?10.4 拟牛顿法算法 拟牛顿法拟牛顿法10.4 拟牛顿法4. 2 对称秩对称秩1 1校正校正Hk称为校正矩阵校正矩阵.确定Hk的一个方法是令10.4 拟牛顿法(10.4.10

136、)(10.4.11)从而(10.4.12)利用(10.4.10),(10.4.12-13),(10.4.9)可写成10.4 拟牛顿法(10.4.13)(10.4.14)-秩秩1 1校正公式校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向(10.4.15)10.4 拟牛顿法确定后继点(10.4.16)4.3 对称秩对称秩2 2校正校正10.4 拟牛顿法定义校正矩阵(10.4.17)DFP(Davidon-Fletcher-Power)公式(10.4.18)则1，DFP算法算法(变尺度法变尺度法)DFP算法10.4 拟牛顿法10.4拟牛顿法例1用DFP方法求解下列问题10.4拟牛

137、顿法初始点及初始矩阵分别为第1次迭代10.4拟牛顿法令搜索方向得到令10.4拟牛顿法第2次迭代10.4拟牛顿法10.4拟牛顿法令10.4拟牛顿法10.4拟牛顿法得到令于是得最优解10.4拟牛顿法2 DFP算法的正定性及二次终止性算法的正定性及二次终止性10.4拟牛顿法证明:用归纳法 DFP方法中, H1是给定的对称正定矩阵.设Hj是对称正定矩阵,下证Hj+1也是对称正定矩阵.根据定义,对称性是显然的,下证正定性(10.4.19)10.4拟牛顿法令10.4拟牛顿法则于是(10.4.19)可写为(10.4.21)由Schwartz不等式,有10.4拟牛顿法(10.4.22)考虑到一维搜索及方向的定

138、义,(10.4.21)右端第一项的分母于是10.4拟牛顿法下证(10.4.22)和(10.4.24)不同时为0.若不然,(10.4.22)为0,则p/q,即p=q(0).从而综上,知10.4拟牛顿法定理10.4.2 设用DFP方法求解下列问题其中A为n阶对称正定矩阵.取初点x(1) En ,令H1为n阶对称正定矩阵,则成立:证明:对k归纳. k=1时有10.4拟牛顿法(10.4.27)由于代入(10.4.27)即得即(10.4.26)成立.当k=2时,10.4拟牛顿法由此结果,易证k=2时(10.4.26)亦成立下设k=m时(10.4.25-26)成立,下证当k=m+1时上述关系式也成立.先证

139、k=m+1时(10.4.25)成立. 由归纳假设,只需证:由对(10.4.26)的归纳假设,当1im时有10.4拟牛顿法由此有(10.4.29)根据Th10.3.2的推论,有由(10.4.29),知10.4拟牛顿法再证当k=m+1时(10.4.26)成立对于1im+1有(10.4.30)当i=m+1时,由(10.4.28)知将其代入(10.4.30)得10.4拟牛顿法当im+1时,根据关于(10.4.26)的归纳假设及当k=m+1时(10.4.25)成立,考虑到(10.4.28),则有从而可得Q.E.D.推论:在Th10.4.2的条件下,必有10.4拟牛顿法DFP方法中构造出来的搜索方向是一组

140、A共轭方向DFP方法具有二次终止性.3 BFGS公式及 Broyden簇10.4拟牛顿法(10.4.33)可得修正公式-关于矩阵B的BFGS修正公式10.4拟牛顿法(10.4.35)上述公式由Broyden,Fletcher,Goldfarb,Shanno(1970)给出.10.4拟牛顿法定义-Broyden簇显示表达式10.4拟牛顿法(10.4.37)其中(10.4.38)10.4拟牛顿法定理10.4.3 设其中A为n阶对称正定矩阵. 则对于Broyden方法,成立:线搜索方法：每次迭代时产生一搜索方向，在此方向上进行精确或不精确一维搜索，得到下一迭代点。缺点：可能由于步长过大导致算法失败，

141、特别当问题病态时。Ch10.5 信赖域方法主要数值方法1：主要数值方法2：信赖域方法： 在每次迭代时，强制性要求新迭代点与当前迭代点之间的距离不超过某一控制量。实际上是，在以当前迭代点为中心的邻域内对一近似于原问题的简单模型求极值。优点：算法稳定性好、收敛性强。主要内容：1 无约束优化信赖域法： 1.1 算法描述 1.2 收敛性2 约束优化（带一个等式约束）： 2.1 逐步二次规划法（SQP） 2.2 Marotos 效应 2.3 信赖域方法1 无约束优化信赖域方法问题：基本思想：给定初始迭代点，确定一个以其为中心的邻域，在此域内优化目标函数的二次逼近式，得到下一迭代点。信赖域子问题：信赖域内

142、原问题的逼近问题：1.1 算法描述Step1 给定初始点Step2 若 ，则停止计算，得解；否则，解子问题得最优解Step3 计算 ，令选取下一信赖域半径使其满足Step4 产生 转step2定理： 是信赖域子问题的解当且仅当它是子问题的K-T点，且 是半正定矩阵。1.2 收敛性在一定条件下，信赖域方法具有全局收敛性。设 是 上的实函数， 是给定初始点， 是有界闭集， 和 在 上连续，用信赖域方法求得序列 ，则 .2 等式约束非线性优化问题(2.1)：其中：2.1 逐步二次规划(SQP)SQP方法是求解非线性规划的一般方法，是线搜索方法的一种。基本方法：求解原问题可以转化为求解一系列二次规划子

143、问题。 是原问题K-T点当且仅当：其实就是拉格朗日函数的稳定点SQP给定当前迭代点 通过下面的等式求迭代步 ，可得到下一个迭代点 . （2.2）其中，SQP解等式（2.2）相当于求解子问题得到的 作为第k次迭代的搜索方向收敛性：在一定条件下，算法产生的点列 的任何聚点都是原问题的K-T点。对原问题若 处的二阶充分条件成立 对子问题若 处的一阶必要条件成立，则 是一超线性收敛步，算法具有超线性收敛性：2.2 Marotos效应在无约束情形，超线性收敛步都是可以接受的：如果 是稳定点且二阶充分条件成立，则在算法迭代过程中，对所有充分大的k，都有：约束优化时不成立：尽管 是一超线性收敛步（ 比 远近

144、于 ），但无论从目标函数值或约束违反度来看， 都是一个“坏”点。Marotos效应指出，对于许多罚函数，超线性收敛步不一定能被接受，破坏了算法收敛性。例子：等式约束优化极小点为克服Marotos效应的方法放松接受试探步的条件引进二阶校正步在算法中用光滑精确罚函数作价值函数2.3 信赖域方法问题（3.1）将SQP中子问题与信赖域要求合并得到信赖域子问题： （3.2）2.3.1线性化约束不相容(1):将线性化约束的约束函数值项都乘上一个(0,1上的参数： （3.3）相当于将每个约束的可行域往远点方向压缩。参数取值：使（3.2）尽量可行，取值应尽量靠近1，但为使子问题有一定自由度，取值不能过大。参数

145、取值构造问题：其最小范数解为Gauss-Newton步当且仅当（3.3）有可行点，为不使参数太小，要求则2.3.1线性化约束不相容(2)：用一个平方和约束代替（3.2）中的等式约束条件 （3.4）2.3.2 CDT子问题由Celis，Dennis，Tapia(1985)提出 (3.5)只有在 时，(3.5)才相容。先考虑若仅有一可行点，则此点有如下形式：其中 ，如果 则 ； 只可能在 时才可能奇异若可行域不只一个点，则 (3.6)将（3.5）转化成无约束信赖域子问题由(3.6)必有 其中令 是由 零空间的一组正交基组成的矩阵，通过变换 可将(3.5)化为用前面的无约束信赖域算法求解在下面讨论中

146、，均假设定理（必要条件）：设 是（3.5）的解，则必存在Lagrange乘子 和 使得 （3.7）如果乘子是唯一的，则矩阵至多只有一个负特征值。定理（充分条件）：设 是子问题的可行点，如果存在 和 使得（3.7）成立， 且 是半正定矩阵，则 是子问题（3.5）的解。推论1：假定 正定，则 是子问题的解，当且仅当存在 和 使得（3.7）成立，此时，解有如下形式： （3.8）推论2：设 正定，前面定义的 是子问题的解当且仅当它是可行点，且下列之一成立：帅天平帅天平北京邮电大学数学系Email:,Tel:62281308, Rm:主楼81411，无约束最优化的直接方法最优化理论与算法Ch11 无约束

147、最优化的直接方法1 模式搜索法2 Rosenbrock算法3 Powell方法1.模式搜索法1 1 基本思想基本思想Hooke & Jeeves(1961)探测移动依次沿n个坐标轴进行,用以确定新的基点和有利于函数值下降的方向.模式移动沿相邻两个基点连线方向进行.从几何意义上看,寻找具有较小函数值的“山谷”力图使迭代产生的序列沿“山谷”走向逼近极小点,算法从初始基点基点开始,包括两种类型的移动-探测移动探测移动和模式移动模式移动.1.模式搜索法1.模式搜索法设目标函数为f(x), xEn.坐标方向给定初始步长,加速因子.任取初始点x(1)作为第1个基点.x(j) : 第j个基点.y(j) :

148、沿ej探测的出发点y(n+1) : 沿en探测得到的点1.模式搜索法首先,从y(1) = x(1)出发,进行探测移动.先沿e1探测并从y(2)出发,沿e2进行探测.否则,沿e1方向的探测失败,再沿- e1方向探测并从y(2)出发,沿e2进行探测.1.模式搜索法再从y(2)出发,沿e2进行探测.方法同上,得到的点记为y(3) .按此方式作下去直至沿n个方向探测完毕,得到点y(n+1).此时,可望d = x(2) - x(1)是有利于函数值减小的方向.1.模式搜索法下一步,沿方向x(2) - x(1)进行模式移动,令新的y(1)y(1) =x(2) +(x(2) - x(1) (1.5)模式移动后

149、,以y(1)为起点进行探测移动,这轮探测移动仍然沿坐标轴方向进行.探测完毕,得到的点仍记做y(n+1) 若f(y(n+1) ) f(x(2) ,则此次模式移动成功.于是取新的基点.x(3) = y(n+1)再沿x(3) - x(2)进行模式移动1.模式搜索法若f(y(n+1) ) f(x(2) ,则表明模式移动及此次模式移动之后的探测移动均无效.于是退回到基点x(2).减小步减小步长长 ,再从x(2) 出发,依次沿各坐标轴方向进行探测移动如此继续下去,直到满足精度为止,即步长小于事先给定的某个小的正数为止1.2 计算步骤1.模式搜索法进行步4.,否则转3进行步4.,否则令进行步4.y(j+1)

150、 = y(j)1.模式搜索法4. 若jn,则置j:=j+1,转步2,否则,进行步5.6.置x(k+1) = y(n+1),令y(1) =x(k+1) +(x(k+1) - x(k)置k:=k+1,j=1,转步2.7.若,则停止迭代,得点x(k) ,否则,置:=, y(1) = x(k), x(k+1) =x(k)置 k:=k+1,j=1,转步2. 1.模式搜索法例1.1 用模式搜索法求解下列问题计算结果如下1. 模式搜索法012(2,0) 81 012(1,1) 0(1,1) 0(1,1) 1 模式搜索法012(1,1) 0(1,1) 0(1,1) 012(1,1) 0(1,1) 0(1,1)

151、 2.Rosenbrock算法(转轴法)2.1, 方法概述算法每次迭代包括探测阶段和构造搜索方向两部分探测阶段:从一点出发,依次沿n个单位正交方向进行探测移动,一轮探测之后,再从第1个方向开始继续探测.经过若干轮探测移动,完成一个探测阶段.同时得到一组新的正交方向,将其单位化.称之为转轴转轴.1.探测阶段2. Rosenbrock算法它们是单位正交方向,沿各方向的步长为每轮探测的起点和终点用y(1) 和y(n+1) 表示.令y(1) = x(k) ,开始第1轮探测移动先从y(1) 出发,沿d(1)探测2. Rosenbrock算法再从y(2)出发,沿d(2)作探测移动.得y(3) .按此方式探

152、测下去,直至沿d(n)探测,得到y(n+1)2. Rosenbrock算法完成一轮探测后,令 y(1)= y(n+1)进行下一轮探测.往复下去,至某一轮沿n个方向的探测均失败,.第k次迭代的探测结束时,得到的点记为 x(k+1)= y(n+1)2. 构造新的搜索方向2. Rosenbrock算法2. Rosenbrock算法2. Rosenbrock算法将其正交化再单位化可证如下引理:2. Rosenbrock算法2.2 计算步骤2. Rosenbrock算法3. 若j0,故有又由(12.1.3)得 Ed=0下证充分性。设1. Zoutendijk可行方向法(12.1.6)和(12.1.7)即

153、1. Zoutendijk可行方向法Zoutendijk法把确定搜索方向归结为求解LP:显然d=0是可行解。由此可知,目标函数的最优值必小于等于0。若最优值小于0，则可得下降可行方向d,否则我们可证x是KKT点.1. Zoutendijk可行方向法证明:根据定义, x为KKT点的充要条件是,w和v,使得1. Zoutendijk可行方向法令v=p-q, p,q. (12.1.11)写成根据Farkars定理，上述方程有解的充要条件是(12.1.13)无解1. Zoutendijk可行方向法即所以x为KKT点的充要条件是问题(12.1.10)的目标函数最优值为0。根据上述定理，求解问题(12.1

154、.10)的结果或者是得到下降可行方向，或者得到KKT点。怎样确定一维搜索的步长？怎样确定一维搜索的步长？1. Zoutendijk可行方向法第二，使目标函数值尽可能减小。根据上述原则,可以通过求解下列一维搜索问题来确定步长：1. Zoutendijk可行方向法问题(12.1.15)可作进一步简化。因此,(12.1.15)中第2个约束是多余的1. Zoutendijk可行方向法于是,(12.1.15)中第1个约束可写成：自然成立。约束(12.1.19)化为1. Zoutendijk可行方向法这样,问题(12.1.15)化简为根据(12.1.21)的约束条件，易求出的上限,令1. Zoutendi

155、jk可行方向法由此得到的上限(12.1.24)问题(12.1.15)于是化为：于是，给定问题(12.1.1)和一个可行点，可以通过求解问题(12.1.10)得到下降可行方向，通过求解问题(12.1.25)确定沿此方向进行一维搜索的步长.1. Zoutendijk可行方向法于是，给定问题(12.1.1)和一个可行点，可以通过求解问题(12.1.10)得到下降可行方向，通过求解问题(12.1.25)确定沿此方向进行一维搜索的步长.可以通过解辅助LP得到一可行点：1. Zoutendijk可行方向法若(12.1.26)的最优解则x*是(12.1.1)的一个可行解可以通过解辅助LP得到一可行点：1.

156、Zoutendijk可行方向法计算步骤3，求解LP：1. Zoutendijk可行方向法6,置k:=k+1,转2。1. Zoutendijk可行方向法例 用Zoutendijk法求解下列问题1. Zoutendijk可行方向法第一次迭代：1. Zoutendijk可行方向法用单纯形法求得最优解1. Zoutendijk可行方向法解一维搜索：得令重复迭代最后可得最优解x*=(1/2,3/2)1. Zoutendijk可行方向法1.2 非线性约束考虑不等式约束问题1)选择下降可行方向.1. Zoutendijk可行方向法1. Zoutendijk可行方向法1. Zoutendijk可行方向法由上分

157、析,知对充分小的有因此d为x处的可行方向。因此d为x处的下降可行方向。1. Zoutendijk可行方向法进而归结为求解LP:因此求下降可行方向即求满足下述方程组的d。(12.1.31)1. Zoutendijk可行方向法设(12.1.31)的最优解为(x*,d*).若z*0.由引理13.1.1和1.2可知,13.1 外点罚函数法注意到(13.1.26),可以断言,对每个.存在正整数K(),使得当kK()时有 . 由(13.1.16)可知13.1 外点罚函数法由(13.1.28)和(1.29)可知13.1 外点罚函数法另一方面,由于f(x)连续,则又考虑到(13.1.24)和(13.1.30)

158、,则13.1 外点罚函数法于是由(13.1.25)得(13.1.33)13.2 内点罚函数法13.2.1 基本思想基本思想(13.2.1)因此,此方法适用于下列不等式约束的问题:记可行域为内点法产生的点列从可行域的内部逼近问题的解13.2 内点罚函数法内点罚函数法的基本思想:构造辅助(光滑)函数13.2 内点罚函数法保持迭代点含于可行域内部的方法是定义障碍函数障碍函数其中B(x)是连续函数,当点x趋向可行域边界时,B(x). 是很小的正数.这样,当x趋向边界时,函数F(x,)趋于无穷大;否则,由于很小,则函数F(x,)的取值近似f(x).因此可通过求解下列问题得到原问题的近似解:13.2 内点

159、罚函数法两种最重要的形式:13.2 内点罚函数法2.2 计算步骤13.2 内点罚函数法定义障碍函数例13.2.1 用内点法求解下列问题用解析法求解问题13.2 内点罚函数法解得令13.2 内点罚函数法2.3. 收敛性13.2 内点罚函数法设x*是问题(13.2.1)的最优解.又知(13.2.8)13.2 内点罚函数法故有从而(13.2.9)13.2 内点罚函数法即(13.2.10)13.2 内点罚函数法13.2 内点罚函数法13.2 内点罚函数法则上式必为等式.如若不然,不趋于0,矛盾。此与故822第15章 整数规划n第1节 整数线性规划问题的提出n第2节 分支定界解法n第3节 割平面解法n第

160、4节 0-1型整数线性规划n第5节 指派问题823第1节 整数线性规划问题的提出v在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。v为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。v因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming)，简称ILP。824第1节 整数线性规划问题的提出v整

161、数线性规划的分类如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programming)。整数线性规划的一种特殊情形是0-1规划，即变量的取值仅限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。 825第1节 整数线性规划问题的提出v现举例说明用单纯形法求得的解不能保证是整数最优解。v例例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、

162、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱，可使获得利润为最大?表5-1826第1节 整数线性规划问题的提出v解解：设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)，这就是一个(纯)整数线性规划问题，用数学模型可表示为： max z =20x1+10x2 5x1+4x224 2x1+5x213 (5.1) x1，x20 x1，x2整数 该问题和线性规划问题的区别仅在于最后一个约束条件。 现在我们暂不考虑这一条件，即解由构成的线性规划问题(以后我们称这样的问题为与原问题相应的线性规划问题)。827第1节 整数线性规划问题的提出v容易求得相应的线性规划问题的最优解

163、为 x1=4.8，x2=0，max z=96828第1节 整数线性规划问题的提出v现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解因为x1表示的是托运甲种货物的箱数，目前得到的最优解不是整数，所以不合条件的要求。是不是可以把所得的非整数最优解经过“化整”就可得到合于条件的整数最优解呢?o如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件(关于体积的限制)，因而它不是可行解；o如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0, 时z=80；而当x1=4，x2=

164、1(这也是可行解)时，z=90。829第1节 整数线性规划问题的提出 图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内，而C点又不合于条件。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值为z=96-90=6，表示利润的降低，这是由于变量的不可分性(装箱)所引起的。图5-1830第1节 整数线性规划问题的提出v由上例看出，将其相应的线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因

165、此有必要对整数线性规划的解法进行专门研究。831第2节 分支定界解法v在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举所有可行的整数解，即列出图5-1中所有标有“+”的整数点，然后比较它们的目标函数值，从而确定最优解。v对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。如在例1中，变量只有x1和x2。由条件，x1所能取的整数值为0、1、2、3、4共5个；由条件，x2所能取的整数值为0、1、2共3个。因此所有可能的整数组合(不都是可行的)数是35=15个，穷举法还是勉强可用的。v对于大型问题，可行的整数组合数会很大。例如在指派问题中，将n

166、项任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20，超过21018。显然，穷举法是不可取的。832第2节 分支定界解法v应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。v分支定界法可用于解纯整数或混合整数线性规划问题。20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的重要方法之一。v分支定界法的基本思想考虑最大化整数线性规划问题A，与它相应的线性规划记为问题B。我们从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数值z*的上界，记作 ；而

167、A的任意可行解的目标函数值将是z*的一个下界 。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小 和增大 ，最终求到z*。833第2节 分支定界解法v例2 求解问题A max z=40x1+90x2 9x1+7x256 7x1+20x270 (5.2) x1，x20 x1，x2整数 清华大学出版社清华大学出版社834第2节 分支定界解法v解：解：先不考虑条件，即解相应的线性规划B,(见图5-2)，得最优解x1=4.81，x2=1.82，z0=356 可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作z0= 。而在x1=0，x2=0时，显然是问题A的一个整数可

168、行解，这时z=0，是z*的一个下界，记作 =0，即0z*356。835第2节 分支定界解法v首先注意到相应的线性规划问题（问题B）的解中有一个非整数变量，如x1=4.81。v于是，在原问题中增加两个约束条件：x14和x15，将原问题分解为两个子问题B1和B2(即两支)。v给每支增加一个约束条件后，如图5-3所示，并不影响问题A的可行域。v仍然不考虑整数条件约束，解问题B1和B2，得到最优解为：836第2节 分支定界解法v x14，x15图5-3837第2节 分支定界解法v显然，仍没有得到全部变量是整数的解。因z1z2，故将 改为349，那么必存在最优整数解，得到z*，并且 0z*349v继续对

169、问题B1和B2进行分解。因z1z2，故先分解B1为两支。增加条件x22，称为问题B3；增加条件x23，称为问题B4。相当于在图5-3中再去掉x22与x33之间的区域，进行第二次迭代。838第2节 分支定界解法v继续对问题B2进行分解839第2节 分支定界解法 解题过程 840第2节 分支定界解法v从以上解题过程可得到用分支定界法求解整数线性规划(最大化)问题的步骤为（将要求解的整数线性规划问题称为问题A，将与它相应的线性规划问题称为问题B）：v(1) 解问题B，可能得到以下情况之一： B没有可行解，这时A也没有可行解，则停止。 B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停

170、止。 B有最优解，但不符合问题A的整数条件，记它的目标函数值为 v(2) 用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，n，试探，求得其目标函数值，并记作v以z*表示问题A的最优目标函数值；这时有841第2节 分支定界解法v进行迭代v第一步：分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件xjbj和xjbj+1 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界 。

171、从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无可行解， 。842第2节 分支定界解法v第二步：比较与剪支v各分支的最优目标函数中若有小于 者，则剪掉这支(用打表示)，即以后不再考虑了。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，n。v用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。843第3节 割平面解法v割平面解法的思想首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线

172、性规划问题。若得到非整数的最优解，则增加能割去非整数解的线性约束条件(或称为割平面)，使得由原可行域被切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。割平面方法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到这样的可行域，它的一个整数极点恰好是问题的最优解。以下仅讨论纯整数线性规划的情形。844第3节 割平面解法v例例3 3 求解 目标函数 max z=x1+x2 约束条件： -x1+x21 3x1+x24 (5-3) x1，x20 x1，x2 整数 845第3节 割平面解法v先不考虑条件，求得相应的线性规划的最优解为： x1=34，x2=74，max z=1

173、04 最优解是图5-5中域R的极点A，但不符合整数约束条件。846第3节 割平面解法v现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R的一个极点。 如在域R上求解，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。图5-6847第3节 割平面解法v在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束：x1+x2+x3 =1 3x1+x2 +x4=4 不考虑条件，用单纯形表解题，见表5-2。848第3节 割平面解法从表

174、5-2的最终计算表中，得到非整数的最优解： x1=3/4，x2=7/4，x3=x4=0，max z=5/2849第3节 割平面解法由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。可从最终计算表中得到非整数变量对应的关系式：850第3节 割平面解法v为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和 (1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 v然后将整数部分与分数部分分开，移到等式左右两边，得到：851第3节 割平面解法v现考虑整数条件v要求x1、

175、x2都是非负整数，于是由条件、可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在等式右边的()内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所代替： 即 3x3 x4 3 852第3节 割平面解法v这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。v引入松弛变量x5，得到等式 3x3 x4+x5= 3 将这新的约束方程加到表5-2的最终计算表，得表5-3。853第3节 割平面解法v这从表5-

176、3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。v选择x5为换出变量，计算854第3节 割平面解法v将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。855第3节 割平面解法v注意：新得到的约束条件 3x3 x4 3v如用x1、x2表示，由、式得3(1+x1 x2)+(4 3x1 x2)3x21 这就是(x1，x2)平面内形成的新的可行域，即包括平行于x1轴的直线x2=1和这直线下的可行区域，整数点也在其中，没有切割掉,见图5-7。图5-7856第3节 割平面解法v求一个切割方程的步骤为：v(1) 令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的

177、最终表得到其中iQ (Q指构成基变量号码的集合)kK (K指构成非基变量号码的集合)857第3节 割平面解法v(2) 将bi和ik都分解成整数部分N与非负真分数f之和，即 bi=Ni+fi，其中0fi1 ik=Nik+fik，其中0fik1 (5-5) 而N表示不超过b的最大整数。例如： 若b=2.35，则N=2，f=0.35 若b= 0.45，则N= 1,f=0.55 代入(5-4)式得858第3节 割平面解法v(3) 现在提出变量(包括松弛变量)为整数的条件(当然还有非负的条件)。v这时，上式由左边看必须是整数，但由右边看，因为0fi1，所以不能为正，即 这就是一个切割方程。v由(5-4)

178、式，(5-6)式，(5-7)式可知： 切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。 没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。859第4节 0-1型整数线性规划v0-1型整数线性规划是整数线性规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0-1变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件所代替: xi1, xi0，整数v它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题，

179、再研究解法。8604.1 引入0-1变量的实际问题1. 投资场所的选定相互排斥的计划 例例4 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置(点)Ai (i=1，2，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?8614.1 引入0-1变量的实际问题v解：先引入0-1变量xi (i=1,2，7) 于是问题可列成： 8624.1 引入0-1变量的实际问题2. 相互排斥的

180、约束条件 在本章开始的例1中，关于运货的体积限制为 5x1+4x224 (5-9) 今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x245 (5-10) 这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令 8634.1 引入0-1变量的实际问题 于是，(5-9)式和(5-10)式可由下述条件(5-11)式和(5-12)式来代替： 5x1+4x224+yM (5-11) 7x1+3x245+(1 y)M (5-12) 其中M是充分大的数。 可以验证 当y=0时，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而

181、是多余的。当y=1时，(5-12)式就是(5-10)式，而(5-11)式是多余的。 引入的变量y不必出现在目标函数内，即认为在目标函数内y的系数为0。 8644.1 引入0-1变量的实际问题v如果有m个互相排斥的约束条件(型)：i1x1+i2x2+inxnbi，i=1，2，,m 为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,，m)和一个充分大的常数M，且下面这一组m+1个约束条件 i1x+i2x2+inxnbi+yiM i=1,2,，m (5-13) y1+y2+ym=m 1 (5-14) 就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取0

182、值，设yi*=0，代入(5-13)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。8654.1 引入0-1变量的实际问题3. 固定费用的问题 在讨论线性规划时，有些问题是要求使成本为最小。这时，通常设固定成本为常数，不必在线性规划模型中明显列出。但有些固定费用(固定成本)问题不能用一般线性规划来描述，可改变为混合整数线性规划来解决。8664.1 引入0-1变量的实际问题v例例5 某工厂为生产某种产品，有几种生产方式供选择。如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，分配到每件产品的变动成本可能增加，

183、所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。 为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为8674.1 引入0-1变量的实际问题v在构成目标函数时，为了统一在一个问题中讨论，引入0-1变量yj，令于是，目标函数为 min z=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)8684.1 引入0-1变量的实际问题v(5-15)式的规定可由以下3个线性约束条件表示：xjyjM，j=1,2,3 (5-16) 其中M是个充分大的常数。 (5-

184、16)式说明 当xj0时，yj必须为1； 当xj=0时，只有yj为0时才有意义。 所以，(5-16)式完全可以代替(5-15)式。 8694.2 0-1型整数线性规划的解法v求解0-1型整数线性规划最容易想到的方法（和一般整数线性规划的情形一样），就是穷举法，即检查变量取值为0或1的每一种组合，并比较目标函数值以求得最优解。这就需要检查变量取值的2n个组合。当变量个数n较大(例如n10)时，这几乎是不可能的。v因此，需要设计一些特殊的方法，只需要检查变量取值组合中的一部分，就能求到问题的最优解。这样的方法称为隐枚举法(implicit enumeration)。分枝定界法就是一种隐枚举法。v下

185、面举例说明一种解0-1型整数线性规划的隐枚举法。8704.2 0-1型整数线性规划的解法例6 目标函数 max z=3x1-2x2+3x5 约束条件： x1+2x2x32 x1+4x2+x34 (5-17) x1+x23 4x1+x36 x1，x2，x3=0或1 8714.2 0-1型整数线性规划的解法v先通过试探的方法找一个可行解。容易看出(x1，x2，x3)=(1，0，0)就是合于条件的，算出相应的目标函数值z=3。v下面来求最优解。对于极大化问题，当然希望z3，于是增加一个约束条件： 3x1 2x2+5x33 后加上的条件称为过滤条件。这样，原问题的线性约束条件就变成了5个。用全部枚举的

186、方法，3个变量共有23=8个可能的解。原来的4个约束条件，共需32次运算。 现在增加了过滤条件，如按下述方法进行，就可减少运算次数。将5个约束条件按顺序排好(表5-5)。对每个可能的解，依次代入约束条件左侧，求出数值，看是否适合不等式条件。如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。8724.2 0-1型整数线性规划的解法v本例计算过程如表5-5，实际只作了24次运算。求得最优解为： (x1，x2，x3)=(1，0，1), max z=8 在计算过程中，若遇到z值已超过条件右边的值，应改变条件，使右边为迄今为止最大者，然后继续作。例如，当检查点(0，0，1)时因z=5(

187、3)，所以应将条件换成3x1 2x2+5x35 这种对过滤条件的改进，更可以减少计算量。 8734.2 0-1型整数线性规划的解法表5-58744.2 0-1型整数线性规划的解法v注意： 一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写 z=3x1 2x2+5x3= 2x2+3x1+5x3 因为 2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)， 这样，最优解容易比较早的发现。 再结合过滤条件的改进，更可使计算简化。8754.2 0-1型整数线性规划的解法v在上例中max z=-2x2+

188、3x1+5x3-2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 (5-18) x2+x13 4x2+x36 解题时按下述步骤进行(见表5-6)：8764.2 0-1型整数线性规划的解法8774.2 0-1型整数线性规划的解法v改进过滤条件，用-2x2+3x1+5x35 代替，继续进行。 再改进过滤条件，用2x2+3x1+5x38 代替，再继续进行。至此，z值已不能改进，即得到最优解，解答如前，但计算已简化。878第5节 指派问题v在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于

189、是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。879第5节 指派问题v例7 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少?表5-7880第5节 指派问题v类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij0

190、(i,j=1,2，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令 881第5节 指派问题v当问题要求极小化时数学模型是：882第5节 指派问题v约束条件说明第j项任务只能由1人去完成；约束条件说明第i人只能完成1项任务。v满足约束条件的可行解xij也可写成表格或矩阵形式，称为解矩阵。 如例7的一个可行解矩阵是显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最优解。883第5节 指派问题v指派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1 v当然可用整数线性规划，0-1规划或运输问题的解法去求解，这就

191、如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。v指派问题的最优解有这样性质，若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，v那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。 884第5节 指派问题v利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。v若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目

192、标函数中得到zb=0，它一定是最小。v这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。885第5节 指派问题v以下用例7来说明指派问题的解法。v第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。(1) 从系数矩阵的每行元素减去该行的最小元素；(2) 再从所得系数矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。例7的计算为886第5节 指派问题行列都有零元素887第5节 指派问题v第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。v经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些

193、独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为： 888第5节 指派问题(1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派。然后划去所在列(行)的其他0元素，记作。这表示这列所代表的任务已指派完，不必再考虑别人了。(2) 给只有一个0元素列(行)的0元素加圈，记作；然后划去所在行的0元素，记作。(3) 反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。(4) 若仍有没有划圈的0元素，且同行(列)的0元素至

194、少有两个(表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。(5) 若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若mn，则转入下一步。889第5节 指派问题v现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到注意：矩阵中符号

195、即是文中的符号。以下同。890第5节 指派问题v可见m=n=4,所以得最优解为这矩阵表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少891第5节 指派问题v例8求表5-8所示效率矩阵的指派问题的最小解。892第5节 指派问题v解解 按上述第一步，将这系数矩阵进行变换。经一次运算即得每行每列都有0元素的系数矩阵，893第5节 指派问题v再按上述步骤运算，得到这里的个数m=4，而n=5；所以解题没有完成，这时应按以下步骤继续进行。 894第5节 指派问题v第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：(1) 对没有的行打号

196、；(2) 对已打号的行中所有含元素的列打号；(3) 再对打有号的列中含元素的行打号；(4) 重复(2)，(3)直到得不出新的打号的行、列为止。(5) 对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有0元素的最少直线数。895第5节 指派问题v令这直线数为l。若ln，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：若l=n，而mn，应回到第二步(4)，另行试探。 在例8中，对矩阵按以下次序进行： 先在第五行旁打，接着可判断应在第1列下打，接着在第3行旁打。经检查不再能打了。对没有打行，画一直线以覆盖0元素，已打的列画一直线以覆盖0元素。得896第5节 指派问题由

197、此可见l=4n。所以应继续对矩阵进行变换。转第四步。897第5节 指派问题v第四步：v对矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵(它的最优解和原问题相同)。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。v在例8的矩阵中，在没有被覆盖部分(第3、5行)中找出最小元素为2，然后在第3、5行各元素分别减去2，给第1列各元素加2，得到新矩阵。按第二步，找出所有独立的0元素，得到矩阵。898第5节 指派问题899第5节 指派问题v已具有n个独立0

198、元素。这就得到了最优解，相应的解矩阵为v 由解矩阵得最优指派方案：甲B，乙D，丙E，丁C，戊A还可以得到另一最优指派方案甲B，乙C，丙E，丁D，戊A所需总时间为min z=32900第5节 指派问题v当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时。这时可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素。这时会出现多重解。 901第5节 指派问题v以上讨论限于极小化的指派问题。v对极大化的问题，即求可令 bij=M cij其中M是足够大的常数(如选cij中最大元素为M即可)，这时系数矩阵可变换为 B=(bij)这时bij0，符合匈牙利法的条件。目标函数经变换后，即解902第5节 指派问题v所得最小解就是原问题的最大解，因为因nM为常数，所以当取最小时，便为最大。