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

可编辑1最优化理论与算法2023/8/19可编辑1最优化理论与算法2023/8/5可编辑2提纲1.

线性规划

对偶定理2.非线性规划K-K-T定理3.组合最优化

算法设计技巧使用教材：最优化理论与算法陈宝林参考书：数学规划黄红选，韩继业

清华大学出版社2023/8/19可编辑2提纲1.线性规划对偶定理使用教材：2023/可编辑3其他参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.2023/8/19可编辑3其他参考书目NonlinearProgrammin可编辑4LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性CombinatorialOptimization

蔡茂诚、刘振宏 AlgorithmsandComplexity清华大学出版社，1988

Printice-HallInc.,1982/1998

其他参考书目2023/8/19可编辑4LinearProgrammingandNet可编辑51,绪论----学科概述最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.2023/8/19可编辑51,绪论----学科概述最优化是从所有可能的方案中选可编辑6绪论---运筹学（OperationsResearch-OR）运筹学方法随机过程方法统计学方法最优化/数学规划方法连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等离散优化：组合优化、网络优化、整数规划等几何规划动态规划不确定规划：随机规划、模糊规划等多目标规划对策论等统计决策理论马氏过程排队论更新理论仿真方法可靠性理论等回归分析群分析模式识别实验设计因子分析等2023/8/19可编辑6绪论---运筹学（OperationsResear可编辑7优化树2023/8/19可编辑7优化树2023/8/5可编辑8最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=02023/8/19可编辑8最优化的发展历程费马:1638;牛顿,1670欧拉,可编辑9欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m2023/8/19可编辑9欧拉，拉格朗日：无穷维问题，变分学拉格朗日，1797可编辑101930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；

KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划

6-70年代：Cook等复杂性理论，组合优化迅速发展

电子计算机----------

最优化2023/8/19可编辑101930年代，康托诺维奇：线性规划电子计算机---可编辑11最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）2023/8/19可编辑11最优化应用举例具有广泛的实用性2023/8/5可编辑121.

食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。2023/8/19可编辑121.食谱问题我每天要求一定量的两种维生素，Vc和可编辑131.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解2023/8/19可编辑131.食谱问题（续）令x表示要买的奶的量，y为要买可编辑142

运输问题设某种物资有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问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。2023/8/19可编辑142运输问题设某种物资有m个产地A1,A2,…Am可编辑15令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2

运输问题（续）2023/8/19可编辑15令xij表示由产地Ai运往销地Bj的物品数量，则产可编辑16以价格qi

购买了si份股票i,i=1,2,…,n股票i的现价是pi你预期一年后股票的价格为ri

在出售股票时需要支付的税金=资本收益×30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50×1000-0.3(50-30)1000-0.1×50×1000=390003

税下投资问题2023/8/19可编辑16以价格qi购买了si份股票i,i=1,2,…,n可编辑17我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3

税下投资问题（续）2023/8/19可编辑17我们的目标是要使预期收益最大。3税下投资问题（续可编辑184

选址问题（1）实例:一组潜在位置（地址）,一组顾客集合及相应的利润和费用数据；解:

设施开放(使用)的数目，他们的位置，以及顾客

被哪个设施服务的具体安排方案；目标：总的利润最大化。数据与约束J={1,2,…,n}:放置设施的可能的潜在位置集合I={1,2,…,m}:顾客集合,其要求的服务需要某设施所提供.2023/8/19可编辑184选址问题（1）实例:一组潜在位置（地址）,一可编辑194

选址问题（2）2023/8/19可编辑194选址问题（2）2023/8/5可编辑204选址问题（3）2023/8/19可编辑204选址问题（3）2023/8/5可编辑215负载平衡(1)实例:网络G(V,E)

及一组m

个数的集合{

s,d>0}，表示

连接源点

s与汇点d

之间的流量解:{

s,d>0}的一组路由,即G(V,E)

中m

条s

与

d间的路,

表示连接s与d

的负载流量的路径。目标:极小化网络负载2023/8/19可编辑215负载平衡(1)实例:网络G(V,E)及一组m可编辑225

负载平衡(2)2023/8/19可编辑225负载平衡(2)2023/8/5可编辑236.结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。2023/8/19可编辑236.结构设计问题两杆桁架的最优设计问题。2023/可编辑24

受力分析图圆杆截面图桁杆示意图6.结构设计问题2023/8/19可编辑24受力分析图圆杆截可编辑256.结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：2023/8/19可编辑256.结构设计问题此应力要求小于材料的屈吸极限，即解

圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为

由此得稳定约束：6.结构设计问题2023/8/19TPSHUAI26圆杆中应力小于等于压杆稳定的临界应力。由此得稳定约束

另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题2023/8/19TPSHUAI27另外还要考虑到设计变量d和h有界。6.结构设计问题20可编辑28基本概念在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.2023/8/19可编辑28基本概念在上述例子中,有的目标函数和约束函数202可编辑29基本概念最优化问题可写成如下形式:2023/8/19可编辑29基本概念最优化问题可写成如下形式:2023/8/5可编辑30基本概念Df1.1

设f(x)为目标函数，S为可行域，x0

S,若对每一个x

S,成立f(x)f(x0),则称x0为极小化问题min

f(x),xS的最优解（整体最优解）则称x0为极小化问题min

f(x),xS的局部最优解Df1.2设f(x)为目标函数，S为可行域，2023/8/19可编辑30基本概念Df1.1设f(x)为目标函数，S为可编辑31Thankyouverymuchforyourattendance!优化软件

/

/neos/solvers/index.html2023/8/19可编辑31ThankyouverymuchforyTPSHUAI32最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@,Tel:62281308,Rm:主楼814§1预备知识2023/8/19TPSHUAI32TPSHUAI32最优化理论与算法帅天平2023/8/5TTPSHUAI331，预备知识1.线性空间2.范数3.集合与序列4.矩阵的分解与校正2023/8/19TPSHUAI33TPSHUAI331，预备知识1.线性空间2023/8/TPSHUAI341.线性空间Df1.3:给定一非空集合G以及在G上的一种代数运算+:G×G→G(称为加法),若下述条件成立:则<G,+>称为一个群.若还满足对任意的a,b∈G,有a+b=b+a,则<G,+>称为一个阿贝尔群(&交换群)2023/8/19TPSHUAI34TPSHUAI341.线性空间Df1.3:给定一非空集合TPSHUAI351.线性空间Df1.4:给定一非空集合V和一个域F,并定义两种运算加法+:V×V→V以及数乘

:F×V→V.若<V,+>构成一交换群,且两种运算满足下面性质:则称V在域F上关于加法和数乘

运算构成一线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.2023/8/19TPSHUAI35TPSHUAI351.线性空间Df1.4:给定一非空集合TPSHUAI361.线性空间例子2023/8/19TPSHUAI36TPSHUAI361.线性空间例子2023/8/5TPSTPSHUAI371.线性空间2023/8/19TPSHUAI37TPSHUAI371.线性空间2023/8/5TPSHUTPSHUAI381.线性空间Th1.1

线性空间V(F)的非空子集S的线性扩张L(S)是V中包含S的最小子空间.2023/8/19TPSHUAI38TPSHUAI381.线性空间Th1.1线性空间V(F)TPSHUAI391.线性空间2023/8/19TPSHUAI39TPSHUAI391.线性空间2023/8/5TPSHUTPSHUAI401.线性空间2023/8/19TPSHUAI40TPSHUAI401.线性空间2023/8/5TPSHUTPSHUAI412.范数2023/8/19TPSHUAI41TPSHUAI412.范数2023/8/5TPSHUAITPSHUAI422.范数2023/8/19TPSHUAI42TPSHUAI422.范数2023/8/5TPSHUAITPSHUAI432.范数2023/8/19TPSHUAI43TPSHUAI432.范数2023/8/5TPSHUAITPSHUAI443.集合与序列2023/8/19TPSHUAI44TPSHUAI443.集合与序列2023/8/5TPSHTPSHUAI453，集合与序列2023/8/19TPSHUAI45TPSHUAI453，集合与序列2023/8/5TPSHTPSHUAI463.集合与序列2023/8/19TPSHUAI46TPSHUAI463.集合与序列2023/8/5TPSHTPSHUAI473.集合与序列2023/8/19TPSHUAI47TPSHUAI473.集合与序列2023/8/5TPSHTPSHUAI484.矩阵的分解与校正Th1.5

若n阶矩阵A可逆，则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LU2023/8/19TPSHUAI48TPSHUAI484.矩阵的分解与校正Th1.5若n阶矩TPSHUAI494.矩阵的分解与校正Th1.6

设A为对称正定矩阵，则（1）矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵，D为对角矩阵（2）存在可逆的下三角矩阵L，使得A=LLT.当L的对角元素为正时，分解是唯一的。(Cholesky分解)2023/8/19TPSHUAI49TPSHUAI494.矩阵的分解与校正Th1.6设A为对TPSHUAI504.矩阵的分解与校正2023/8/19TPSHUAI50TPSHUAI504.矩阵的分解与校正2023/8/5TPTPSHUAI514.矩阵的分解与校正2023/8/19TPSHUAI51TPSHUAI514.矩阵的分解与校正2023/8/5TPTPSHUAI525.函数的可微性与展开2023/8/19TPSHUAI52TPSHUAI525.函数的可微性与展开2023/8/5TTPSHUAI535.函数的可微性与展开当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为2023/8/19TPSHUAI53TPSHUAI535.函数的可微性与展开当f(x)在x点存TPSHUAI545.函数的可微性与展开2023/8/19TPSHUAI54TPSHUAI545.函数的可微性与展开2023/8/5TTPSHUAI555.函数的可微性与展开2023/8/19TPSHUAI55TPSHUAI555.函数的可微性与展开2023/8/5TTPSHUAI565.函数的可微性与展开2023/8/19TPSHUAI56TPSHUAI565.函数的可微性与展开2023/8/5TTPSHUAI57最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@,Tel:62281308,Rm:主楼814§2，凸分析与凸函数2023/8/19TPSHUAI57TPSHUAI57最优化理论与算法帅天平2023/8/5TTPSHUAI582.

凸集与凸函数2.1凸集与锥2023/8/19TPSHUAI58TPSHUAI582.凸集与凸函数2.1凸集与锥202TPSHUAI592.

凸集与凸函数2023/8/19TPSHUAI59TPSHUAI592.凸集与凸函数2023/8/5TPTPSHUAI602.

凸集与凸函数x0xx-x0px0xx-x0p2023/8/19TPSHUAI60TPSHUAI602.凸集与凸函数x0xx-x0px0xTPSHUAI612.

凸集与凸函数2023/8/19TPSHUAI61TPSHUAI612.凸集与凸函数2023/8/5TPTPSHUAI62运用定义不难验证如下命题：2.

凸集与凸函数2023/8/19TPSHUAI62TPSHUAI62运用定义不难验证如下命题：2.凸集与凸TPSHUAI632.

凸集与凸函数多面体(polyhedralset)是有限闭半空间的交.(可表为Ax

b).x4x3x2x1x5xy2023/8/19TPSHUAI63TPSHUAI632.凸集与凸函数多面体(polyhedTPSHUAI642.

凸集与凸函数2023/8/19TPSHUAI64TPSHUAI642.凸集与凸函数2023/8/5TPTPSHUAI65多面集{x|Ax

0}也是凸锥，称为多面锥。2.

凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx|λ>0,x

S}是包含S的最小凸锥.锥C称为尖锥,若0

S.尖锥称为突出的,若它不包含一维子空间.约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}2023/8/19TPSHUAI65TPSHUAI65多面集{x|Ax0}也是凸锥，称为多TPSHUAI662.

凸集与凸函数Df2.5

非空凸集中的点x

称为极点,若x=

x1+(1-

)x2,

(0,1),x1,x2

S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2023/8/19TPSHUAI66TPSHUAI662.凸集与凸函数Df2.5非空凸TPSHUAI672.

凸集与凸函数Def2.6.设非空凸集S

Rn,Rn中向量d0

称为S的一个回收方向(方向),

若对每一x

S,

R(x.d)={x+

d|

0

}

S.S的所有方向构成的尖锥称为S的回收锥,记为0+S

方向d1和d2

称为S的两个不同的方向,若对任意

>0,都有

d1

d2；方向d称为S的极方向extremedirection,若d=

d1+(1-

)d2,

(0,1),d1

,d2

是S的两个方向,则有

d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0x0ddd2023/8/19TPSHUAI67TPSHUAI672.凸集与凸函数Def2.6.设非TPSHUAI682.

凸集与凸函数2023/8/19TPSHUAI68TPSHUAI682.凸集与凸函数2023/8/5TPTPSHUAI692.

凸集与凸函数表示定理Th2.4

若多面体P={x

Rn|Ax

b},r(A)=n则:(1)P的极点集是非空的有限集合,记为{x}kkK则j(2)记P的极方向集为{d}jJ(约定P不存在极方向时J=)(3)指标集J是空集当且仅当P是有界集合,即多胞形.2023/8/19TPSHUAI69TPSHUAI692.凸集与凸函数表示定理Th2.4若TPSHUAI702.

凸集与凸函数表示定理直观描述:设X

为非空多面体.则存在有限个极点x1,…,xk,k>0.进一步,存在有限个极方向d1,…,dl,l>0

当且仅当X

无界.进而,x

X

的充要条件是x

可以表为

x1,…,xk

的凸组合和d1,…,dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论2.1

若多面体S={x|Ax=b,x≥0}非空,则S必有极点.2023/8/19TPSHUAI70TPSHUAI702.凸集与凸函数表示定理直观描述:设TPSHUAI712.2凸集分离定理2.

凸集与凸函数2023/8/19TPSHUAI71TPSHUAI712.2凸集分离定理2.凸集与凸函数TPSHUAI722.

凸集与凸函数2023/8/19TPSHUAI72TPSHUAI722.凸集与凸函数2023/8/5TPTPSHUAI73证明：令2.

凸集与凸函数2023/8/19TPSHUAI73TPSHUAI73证明：令2.凸集与凸函数2023/8/TPSHUAI74所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.

凸集与凸函数下证明唯一性2023/8/19TPSHUAI74TPSHUAI74所以为柯西列，必有极限,且由S为闭集知。TPSHUAI752.

凸集与凸函数2023/8/19TPSHUAI75TPSHUAI752.凸集与凸函数2023/8/5TPTPSHUAI762.

凸集与凸函数2023/8/19TPSHUAI76TPSHUAI762.凸集与凸函数2023/8/5TPTPSHUAI772.

凸集与凸函数xpX(i)(x-)(y-

)0

对任意x

X.(ii)令p=y-

，

=pp.

Txxxyx

证明提纲2023/8/19TPSHUAI77TPSHUAI772.凸集与凸函数xpXTxxxyx证TPSHUAI78由此可得2.

凸集与凸函数2023/8/19TPSHUAI78TPSHUAI78由此可得2.凸集与凸函数2023/8/TPSHUAI792.

凸集与凸函数Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理2023/8/19TPSHUAI79TPSHUAI792.凸集与凸函数Th2.7表明，S为闭TPSHUAI80证明2.

凸集与凸函数2023/8/19TPSHUAI80TPSHUAI80证明2.凸集与凸函数2023/8/5TTPSHUAI81推论2.2：设S为Rn

中的非空集合，yS,则存在非零向量p，使对xclS,pT

(x-y)02.

凸集与凸函数2023/8/19TPSHUAI81TPSHUAI81推论2.2：设S为Rn中的非空集合，yTPSHUAI822.

凸集与凸函数2023/8/19TPSHUAI82TPSHUAI822.凸集与凸函数2023/8/5TPTPSHUAI832.

凸集与凸函数2023/8/19TPSHUAI83TPSHUAI832.凸集与凸函数2023/8/5TPTPSHUAI84

作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。2.

凸集与凸函数2.3择一定理2023/8/19TPSHUAI84TPSHUAI84作为凸集分离定理的应用，下面介绍两个TPSHUAI852.

凸集与凸函数2023/8/19TPSHUAI85TPSHUAI852.凸集与凸函数2023/8/5TPTPSHUAI862.

凸集与凸函数2023/8/19TPSHUAI86TPSHUAI862.凸集与凸函数2023/8/5TPTPSHUAI872.

凸集与凸函数2023/8/19TPSHUAI87TPSHUAI872.凸集与凸函数2023/8/5TPTPSHUAI882.

凸集与凸函数2023/8/19TPSHUAI88TPSHUAI882.凸集与凸函数2023/8/5TPTPSHUAI892.

凸集与凸函数2023/8/19TPSHUAI89TPSHUAI892.凸集与凸函数2023/8/5TPTPSHUAI902.

凸集与凸函数2023/8/19TPSHUAI90TPSHUAI902.凸集与凸函数2023/8/5TPTPSHUAI912.

凸集与凸函数2023/8/19TPSHUAI91TPSHUAI912.凸集与凸函数2023/8/5TPTPSHUAI922.

凸集与凸函数2023/8/19TPSHUAI92TPSHUAI922.凸集与凸函数2023/8/5TPTPSHUAI932.

凸集与凸函数2.4凸函数Df2.10设S

Rn是非空凸集,函数f:SR,若对任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)则称f是S上的凸函数.若上面的不等式对于x

y严格成立,则称f是S上的严格凸函数.

若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.2.4.1基本性质2023/8/19TPSHUAI93TPSHUAI932.凸集与凸函数2.4凸函数Df2.TPSHUAI942.

凸集与凸函数2023/8/19TPSHUAI94TPSHUAI942.凸集与凸函数2023/8/5TPTPSHUAI95Th2.13设f是一凸函数，则对任意的xRn

和d(0)Rn，f在x处沿方向d的方向导数存在。2.

凸集与凸函数2023/8/19TPSHUAI95TPSHUAI95Th2.13设f是一凸函数，则对任TPSHUAI962.

凸集与凸函数2023/8/19TPSHUAI96TPSHUAI962.凸集与凸函数2023/8/5TPTPSHUAI972.凸集与凸函数2023/8/19TPSHUAI97TPSHUAI972.凸集与凸函数2023/8/5TPSTPSHUAI98命题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,y

R,y≥f(x)}都是凸集2023/8/19TPSHUAI98TPSHUAI98命题2.3设f是定义在凸集S上的凸函TPSHUAI992.

凸集与凸函数设S为Rn中的非空凸集,则f(x)是凸的当且仅当上镜图

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集对上镜图事实上我们有如下定理2023/8/19TPSHUAI99TPSHUAI992.凸集与凸函数设S为Rn中的非空凸TPSHUAI1002.

凸集与凸函数2023/8/19TPSHUAI100TPSHUAI1002.凸集与凸函数2023/8/5TPTPSHUAI101定理2.14设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。2.

凸集与凸函数2023/8/19TPSHUAI101TPSHUAI101定理2.14设SRn为一非空凸集，TPSHUAI1022.

凸集与凸函数2023/8/19TPSHUAI102TPSHUAI1022.凸集与凸函数2023/8/5TPTPSHUAI1032.

凸集与凸函数2023/8/19TPSHUAI103TPSHUAI1032.凸集与凸函数2023/8/5TPTPSHUAI1042.

凸集与凸函数2.5.2凸函数的判别Th2.16.设S是Rn

中的非空开凸集,f(x):SR

是可微的函数则

f(x)

是凸函数当且仅当对任意的x*

S,我们有f(x)

f(x*)+

f(x*)(x-x*),

任意

x

S.

类似的,f(x)

严格凸当且仅当对每一x*

S,f(x)>

f(x*)+

f(x*)(x-x*),

任意

x

S.2.4.2凸函数的判别2023/8/19TPSHUAI104TPSHUAI1042.凸集与凸函数2.5.2凸函数的TPSHUAI1052.

凸集与凸函数2023/8/19TPSHUAI105TPSHUAI1052.凸集与凸函数2023/8/5TPTPSHUAI1062.

凸集与凸函数Th2.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.

2023/8/19TPSHUAI106TPSHUAI1062.凸集与凸函数Th2.16*.TPSHUAI1072.

凸集与凸函数2023/8/19TPSHUAI107TPSHUAI1072.凸集与凸函数2023/8/5TPTPSHUAI1082.

凸集与凸函数Def2.11.设S是Rn

上的非空开集,f(x)f(x):SR

的函数则

f(x)

在点x*int(S)称为二次可微的,若存在向量

f(x*),和

n

n

(Hessian)矩阵

H(x*),及函数

:Rn

R

使得对所有的

x

S,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*x

x*Th2.17设S是

Rna上的非空开凸集,f(x)为S

到R上的二次可微函数.则(1)

f(x)

是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2)f(x)

是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.2023/8/19TPSHUAI108TPSHUAI1082.凸集与凸函数Def2.11.TPSHUAI109凸规划2.

凸集与凸函数2023/8/19TPSHUAI109TPSHUAI109凸规划2.凸集与凸函数2023/8/TPSHUAI110最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@,Tel:62281308,Rm:主楼814§3，线性规划的基本性质2023/8/19TPSHUAI110TPSHUAI110最优化理论与算法帅天平2023/8/5TPSHUAI111第二章线性规划的基本性质标准形式与图解法基本性质2023/8/19TPSHUAI111TPSHUAI111第二章线性规划的基本性质标准形式与图TPSHUAI112我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。2.线性规划-

例子-食谱问题2023/8/19TPSHUAI112TPSHUAI112我每天要求一定量的两种维生素，Vc和VTPSHUAI113令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解2.线性规划-

例子-食谱问题2023/8/19TPSHUAI113TPSHUAI113令x表示要买的奶的量，y为要买的蛋的量TPSHUAI1141标准形式矩阵表示其中A是m

n矩阵，c是n维行向量，b是m维列向量。注：为计算需要，一般假设b

0.否则，可在方程两端乘以(-1)即可化为非负。2.线性规划-形式2023/8/19TPSHUAI114TPSHUAI1141标准形式矩阵表示其中A是mn矩阵，TPSHUAI115任意非标准形式均可化为标准形式，如引入松弛变量xn+1，xn+2,…xn+m.2.线性规划-形式2023/8/19TPSHUAI115TPSHUAI115任意非标准形式均可化为标准形式，如引入TPSHUAI116则有2.线性规划-形式2023/8/19TPSHUAI116TPSHUAI116则有2.线性规划-形式2023/8/5TPSHUAI117Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.例如，考虑食谱问题2.图解法当自变量个数少于3时,可以用较简便的方法求解.2.线性规划-图解法2023/8/19TPSHUAI117TPSHUAI117Min3x+2.5y例如，考虑食TPSHUAI11830104020501020304050yx03x+2.5y2x+4y

403x+2y

50(15,2.5)可行区域的极点：(0,25)(15,2.5)最优解(20,0)Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.2.线性规划-图解法2023/8/19TPSHUAI118TPSHUAI1183010402050102030405TPSHUAI1193基本性质3.1线性规划的可行域定理

2.2

线性规划的可行域是凸集.3.2最优极点观察上例，最优解在极点(15,2.5)达到，我们有如下事实:线性规划若存在最优解,则最优解一定可在某极点上达到.2.线性规划-性质12023/8/19TPSHUAI119TPSHUAI1193基本性质定理2.2线性规划的TPSHUAI120考察线性规划的标准形式(2.2)根据表示定理，任意可行点x可表示为2.线性规划-性质22023/8/19TPSHUAI120TPSHUAI120考察线性规划的标准形式(2.2)根据TPSHUAI121把x的表达式代入(2.2),得等价的线性规划:2.线性规划-性质32023/8/19TPSHUAI121TPSHUAI121把x的表达式代入(2.2),得等价的TPSHUAI122于是,问题简化成在(2.6)中令显然,当时目标函数取极小值.2.线性规划-性质42023/8/19TPSHUAI122TPSHUAI122于是,问题简化成在(2.6)中令显然,TPSHUAI123因此极点x(p)是问题(2.2)的最优解.即(2.5)和(2.8)是(2.4)的最优解,此时2.线性规划-性质52023/8/19TPSHUAI123TPSHUAI123因此极点x(p)是问题(2.2)的最优TPSHUAI1242,若(2.2)存在有限最优解,则目标数的最优值可在某极点达到.定理2.3设线性规划(2.2)的可行域非空,则1,(2.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向d(j)2.线性规划-性质62023/8/19TPSHUAI124TPSHUAI1242,若(2.2)存在有限最优解,则目TPSHUAI1254最优基本可行解前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.2.线性规划-性质72023/8/19TPSHUAI125TPSHUAI1254最优基本可行解前面讨论知道们最优解可TPSHUAI126于是,Ax=b可写为于是特别的令Nx=0,则2.线性规划-性质82023/8/19TPSHUAI126TPSHUAI126于是,Ax=b可写为于是特别的令Nx=TPSHUAI127称为方程组Ax=b的一个基本解.定义2.6B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为非基变量.xN为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵称为一组可行基.2.线性规划-性质92023/8/19TPSHUAI127TPSHUAI127称为方程组Ax=b的一个基本解.定义2TPSHUAI128Bb>0,称基本可行解是非退化的,若-1若Bb

0,-1且至少有一个分量为0,称基本可行解是退化的.2.线性规划-性质102023/8/19TPSHUAI128TPSHUAI128Bb>0,称基本可行解是非退化的TPSHUAI1292.线性规划-性质112023/8/19TPSHUAI129TPSHUAI1292.线性规划-性质112023/8/5TPSHUAI1302.线性规划-性质122023/8/19TPSHUAI130TPSHUAI1302.线性规划-性质122023/8/5TPSHUAI1312.线性规划-性质132023/8/19TPSHUAI131TPSHUAI1312.线性规划-性质132023/8/5TPSHUAI132容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过2.线性规划-性质142023/8/19TPSHUAI132TPSHUAI132容易知道,基矩阵的个数是有限的,因此基TPSHUAI133定理2.4令K={x|Ax=b,x

0},A是m×n矩阵,r(A)=m则K的极点集与Ax=b,x

0的基本可行解集合等价.证明:(提纲)1)设x是K的极点,则x是Ax=b,x

0的基本可行解.2)设x是Ax=b,x

0的基本可行解,则x是K的极点.2.线性规划-性质152023/8/19TPSHUAI133TPSHUAI133定理2.4令K={x|Ax=b,TPSHUAI1341),先证极点x的正分量所对应的A的列线性无关.2.线性规划-性质162023/8/19TPSHUAI134TPSHUAI1341),先证极点x的正分量所对应的A的列TPSHUAI1352.线性规划-性质172023/8/19TPSHUAI135TPSHUAI1352.线性规划-性质172023/8/5TPSHUAI1362.线性规划-性质182023/8/19TPSHUAI136TPSHUAI1362.线性规划-性质182023/8/5TPSHUAI1372)设x是Ax=b,x

0的基本可行解,记2.线性规划-性质192023/8/19TPSHUAI137TPSHUAI1372)设x是Ax=b,x0的基本可行解TPSHUAI138即2.线性规划-性质202023/8/19TPSHUAI138TPSHUAI138即2.线性规划-性质202023/8/TPSHUAI139总结,线性规划存在最优解,目标函数的最优值一定能在某极点上达到.可行域K={x|Ax=b,x

0}的极点就是其基本可行解.

从而,求线性规划的最优解,只需要求出最优基本可行解即可.2.线性规划-性质212023/8/19TPSHUAI139TPSHUAI139总结,线性规划存在最优解,目标函数的最TPSHUAI1405基本可行解的存在问题定理2.5

若Ax=b,x

0有可行解,则一定存在基本可行解,其中A是秩为m的m

n矩阵.2.线性规划-性质222023/8/19TPSHUAI140TPSHUAI1405基本可行解的存在问题定理2.5TPSHUAI141否则,我们通过如下步骤构造出一基本可行解2.线性规划-性质232023/8/19TPSHUAI141TPSHUAI141否则,我们通过如下步骤构造出一基本可行TPSHUAI1422.线性规划-性质242023/8/19TPSHUAI142TPSHUAI1422.线性规划-性质242023/8/5最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@,Tel:62281308,Rm:主楼814§4，线性规划的单纯形方法2023/8/19TPSHUAI143最优化理论与算法帅天平2023/8/5TPSHUAI143第三章单纯形方法1，单纯形方法原理2，两阶段法和大Mf法3，退化情形4，修正单纯形方法2023/8/19TPSHUAI144第三章单纯形方法1，单纯形方法原理2023/8/5TPS单纯形法的基本思路

是有选择地取（而不是枚举所有的）基本可行解，即是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，要求新顶点的目标函数值不比原目标函数值差，如此迭代，直至找到最优解，或判定问题无界。

初始基本可行解是否最优解或无界解?结束沿边界找新的基本可行解NY单纯形法的基本过程

3.1线性规划-单纯形方法1怎么判断达到最优解?如何给出初始基可行解?迭代如何进行?2023/8/19TPSHUAI145单纯形法的基本思路是有选择地取（而不是枚举所有的）基本可行

3.1线性规划-单纯形方法2给定标准形式的LP利用分块矩阵2023/8/19TPSHUAI1463.1线性规划-单纯形方法2给定标准形式的LP利用分块矩阵3.1线性规划-单纯形方法3于是目标函数于是有

基本可行解x与基B关联;2023/8/19TPSHUAI1473.1线性规划-单纯形方法3于是目标函数于是有基本可行解x3.线性规划-单纯形方法4于是我们有如下定理：2023/8/19TPSHUAI1483.线性规划-单纯形方法4于是我们有如下定理：2023/8/3.1.线性规划-单纯形方法5由上知,要减少费用,只有当C0时才可能，即2023/8/19TPSHUAI1493.1.线性规划-单纯形方法5由上知,要减少费用,只有当3.1线性规划-单纯形方法6令y=x+

d,>0,我们能降低费用吗？2023/8/19TPSHUAI1503.1线性规划-单纯形方法6令y=x+d,>0,3.1线性规划-单纯形方法72023/8/19TPSHUAI1513.1线性规划-单纯形方法72023/8/5TPSHUAI3.1线性规划-单纯形方法82023/8/19TPSHUAI1523.1线性规划-单纯形方法82023/8/5TPSHUAI3.1线性规划-单纯形方法9正确性如何？显然按上述取法，是可以保证y≥0的。y还是基本可行解吗？2023/8/19TPSHUAI1533.1线性规划-单纯形方法9正确性如何？2023/8/5TP3.1线性规划-单纯形方法102023/8/19TPSHUAI1543.1线性规划-单纯形方法102023/8/5TPSHUA3.1线性规划-单纯形方法11单纯形法2023/8/19TPSHUAI1553.1线性规划-单纯形方法11单纯形法2023/8/5TP3.1线性规划-单纯形方法12Th3.4(单纯形法的收敛性）对于相容的非退化(每个基可行解都是非退的)LP问题，那么经过有限次迭代后，单纯形法或者得到最优的BFS(最优可行基B）或有一个方向d:且最优的费用为-∞.2023/8/19TPSHUAI1563.1线性规划-单纯形方法12Th3.4(单纯形法的收敛性）3.1线性规划-单纯形方法13例12023/8/19TPSHUAI1573.1线性规划-单纯形方法13例12023/8/5TPSH3.1线性规划-单纯形方法142023/8/19TPSHUAI1583.1线性规划-单纯形方法142023/8/5TPSHUA3.1线性规划-单纯形方法15Tc

=(0702-300)2023/8/19TPSHUAI1593.1线性规划-单纯形方法15Tc=(07023.1线性规划-单纯形方法162023/8/19TPSHUAI1603.1线性规划-单纯形方法162023/8/5TPSHUA3.1线性规划-单纯形方法172023/8/19TPSHUAI1613.1线性规划-单纯形方法172023/8/5TPSHUA3.1线性规划-单纯形方法182023/8/19TPSHUAI1623.1线性规划-单纯形方法182023/8/5TPSHUA3.1线性规划-单纯形方法19新的基为B=(A1,A3,A4,A7)2023/8/19TPSHUAI1633.1线性规划-单纯形方法19新的基为B=(A1,A3,3.1线性规划-单纯形方法202023/8/19TPSHUAI1643.1线性规划-单纯形方法202023/8/5TPSHUA3.1线性规划-单纯形方法21新的基为B=(A3,A4,A5,A7)2023/8/19TPSHUAI1653.1线性规划-单纯形方法21新的基为B=(A3,A4,

3.1线性规划-单纯形方法22利用分块矩阵表格形式的单纯形方法2023/8/19TPSHUAI1663.1线性规划-单纯形方法22利用分块矩阵表格形式的单纯形

3.1线性规划-单纯形方法232023/8/19TPSHUAI1673.1线性规划-单纯形方法232023/8/5TPSHU3.1线性规划-单纯形方法240

Im

10ff右端2023/8/19TPSHUAI1683.1线性规划-单纯形方法240Im3.1线性规划-单纯形方法25进基变量离基变量旋转元右端向量返回单纯形表2023/8/19TPSHUAI1693.1线性规划-单纯形方法25进基变量离基变量旋转元右端向量例2：求解线性规划问题化成标准化形式

3.1线性规划-单纯形方法26

2023/8/19TPSHUAI170例2：求解线性规划问题化成标准化形式

3.1线性规划-单纯写出单纯形表25/136/20-3-20-2-7201/201-1/27/0.511/2101/218/0.5x271811/21/2x5x6离基，x2进基，x5离基，x1进基，3.1线性规划-单纯形方法272023/8/19TPSHUAI171写出单纯形表25/136/20-3-20-2-7201/200-4-2-2-1-860102-1101-11141100得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）minz’=-86，maxz=861

3.1线性规划-单纯形方法282023/8/19TPSHUAI1720-4-2-2-1-860102-1101-11141100例3：求解线性规划问题3.1线性规划-单纯形方法292023/8/19TPSHUAI173例3：求解线性规划问题3.1线性规划-单纯形方法292023.1线性规划-单纯形方法302023/8/19TPSHUAI1743.1线性规划-单纯形方法302023/8/5TPSHUAx3进基，x6离基3.1单纯形方法312023/8/19TPSHUAI175x3进基，x6离基3.1单纯形方法312023/8/5TP初始单纯型表最优单纯型表2023/8/19TPSHUAI176初始单纯型表最优单纯型表2023/8/5TPSHUAI173.2两阶段法&大M法1单纯形法三要素：初始基本可行解，解的迭代，最优性检验后两个已解决,现考虑如何获得一个初始基可行解.（一）两阶段法设标准LP为2023/8/19TPSHUAI1773.2两阶段法&大M法1单纯形法三要素：（一）两阶段法设标3.2两阶段法&大M法2若系数矩阵中有一个单位矩阵，则容易得到初始基可行解.所以我们希望幸运的碰到这种矩阵.没有的话，硬性加一个？2023/8/19TPSHUAI1783.2两阶段法&大M法2若系数矩阵中有一个单位矩阵，则容易3.2两阶段法&大M法3问题是如何由(3.2.3)的初始可行解获得原来LP的一个初始可行解？为此，考虑如下辅助LP(第一阶段)2023/8/19TPSHUAI1793.2两阶段法&大M法3问题是如何由(3.2.3)的初始可如果原问题有可行解，则辅助问题的最优值为0，反之亦然。就可以得到辅助问题的初始基可行解2．由于，所以以为基变量，,同时所以一定有最小值.3.2两阶段法&大M法4关系?2023/8/19TPSHUAI180如果原问题有可行解，则辅助问题的最优值为0，反之亦然。就可以3.2两阶段法&大M法5利用单纯形法求得一个最优可行解.这个解将会给我们带来什么？2023/8/19TPSHUAI1813.2两阶段法&大M法5利用单纯形法求得一个最优可行解.这3.2两阶段法&大M法6于是我们获得一个初始基可行解,从而可以以此基可行解出发利用单纯形法求出最优解.第一阶段：不考虑原LP问题是否有基可行解，添加人工变量，构造仅含人工变量的目标函数，得辅助规划(3.2.4)单纯型法求解上述模型，若有目标函数=0，说明原问题存在初始基本可行解，转入第二阶段。否则，原问题无可行解，计算停止。

第二阶段：将第一阶段计算得到的最终表，除去人工变量，从该初始基本可行解开始，用单纯形法求原问题的最优解或判定原问题无界。2023/8/19TPSHUAI1823.2两阶段法&大M法6于是我们获得一个初始基可行解,从而3.2两阶段法&大M法7写成标准化形式例1求解2023/8/19TPSHUAI1833.2两阶段法&大M法7写成标准化形式例1求解20233.2两阶段法&大M法8第1

阶段首先引入人工变量，构造辅助规划问题如果以为基变量，则可以得到该问题的BFS,其对应的单纯形表为2023/8/19TPSHUAI1843.2两阶段法&大M法8第1

阶段首先引入人工变量，构造3.2两阶段法&大M法9-50-210000000000-1-101-16-101021120-1011RHS-50-2100000208-1-10031-16-101021120-1011gzgz2023/8/19TPSHUAI1853.2两阶段法&大M法9-50-23.2两阶段法&大M法10-3/2-7/20-7/207/20-72/34/301/3-1-4/301/31/6-1/61-1/601/601/32/34/301/3-1-1/311/3RHSgz1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/21