大连海事大学-刘巍-高等运筹第三讲

1、高等运筹学,第二篇 运筹学中的数学规划,第三章 线性规划 第四章 非线性规划 第五章 锥规划 第六章 矩阵规划 第七章 变分不等式与互补问题 第八章 整数规划 第九章 动态规划 第十章 向量优化（多目标优化） 第十一章 全局优化,第三讲,5.1基本概念 5.2凸函数和凸规划 5.3一维搜索方法 5.4无约束最优化方法 5.5约束最优化方法,第四章 非线性规划,非线性规划问题,例1 曲线的最优拟合问题,例2 构件容积问题,某钢铁厂准备用5000万元用于A、B两个项目技改进行投资。预估投资项目的年收益分别为20%和16%。同时，投资后总的风险损失随总投资和单项投资的增加而增加，应如何分配资金，才能

2、使期望收益达最大，同时又使风险损失为最小？,例3: 投资决策问题,问题假设,1、设x1, x2分别表示分配给项目A、B的投资资金； 2、总的风险损失与总投资的平方成正比，也与单项投资的平方成正比，即风险损失函数为： g(x1,x2)= (x1+x2)2 +2x12+x22 3、收益函数为：f(x1,x2)=20 x1+16x2 (高收益，高风险),数学模型,max f(x1,x2)- g(x1,x2) max 20 x1+16x2- (x1+x2)2 +2x12+x22 s.t. x1+ x25000 x1, x20 其中，0为权系数。 特殊情形： =0，不考虑风险； = 1，考虑收益和风险同

3、等重要； 1，表示风险最小是第一目标， 其次才考虑收益目标。,投资决策问题另外一种提法:,某公司在一个时期内可用于投资的总资本为b万元, 可供选择的项目有n个。假定对第i个项目的投资总额为ai万元，收益总额为ci万元。 问如何确定投资方案，使总的利润率达最高？ 设投资决策变量为：,数学模型,关于决策变量xi的非线性约束整数规划问题。,收益占总投资 的比率,1.非线性规划模型：,数学规划模型的一般形式：,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数,简记为MP(Mathematical Programming),退 出,前一页,后一页,2.1 基本概念,可

4、行域和可行解：,称,为MP问题的约束集或可行域。,若x在X内，称x为MP的可行解或者可行点。,退 出,前一页,后一页,简记形式：,引入向量函数符号：,退 出,前一页,后一页,数学规划问题的分类：,若f(x),gi(x),hj(x)为线性函数，即为线性规划(LP)；,若f(x),gi(x),hj(x)至少一个为非线性，即为非线性规划(NLP)；,对于非线性规划，若没有gi(x),hj(x)即X=Rn,称为无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。,退 出,前一页,后一页,最优解和极小点,对于数学规划（MP），若 ，并且有,如果有,定义:,退 出,前一页,后一页,

5、如果有,定义,退 出,前一页,后一页,例,退 出,前一页,后一页,三角形表示的是可行域。,同心圆表示的是目标函数的等值线。,最优解为（1/2，1/2） 最优值为1/2,问题：(1/2,1/2)是整体的还是局部的？是严格的还是非严格的？,1/2,1/2,退 出,前一页,后一页,2.非线性规划方法概述,微分学方法的局限性：,实际的问题中，函数可能是不连续或者不可微的。 需要解复杂的方程组，而方程组到目前仍没有有效的算法。 实际的问题可能含有不等式约束，微分学方法不易处理。,退 出,前一页,后一页,数值方法的基本思路：迭代,给定初始点x0,根据x0,依次迭代产生点列xk,xk的最后一点为最优解,xk

6、收敛于最优解,退 出,前一页,后一页,迭代格式,xk,xk+1,称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。,产生tk和pk的不同方法，形成了不同的算法。,退 出,前一页,后一页,定义：下降方向,退 出,前一页,后一页,定义,解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。 这样的方向称为可行下降方向。,退 出,前一页,后一页,1.凸函数及其性质：,定义,退 出,前一页,后一页,2.2 凸函数和凸规划,退 出,前一页,后一页,定理:,关于凸函数的一些结论,定理:,是凸集。,函数f在集合S上关于c的水平集,退 出,前一页,后一页,定理,? 还

7、有什么方法判断一个函数是凸函数呢？,退 出,前一页,后一页,退 出,前一页,后一页,2.凸规划及其性质：,凸规划定义：,退 出,前一页,后一页,凸规划性质：,凸规划的任一局部最优解都是它的整体最优解。,凸规划是以后重点讨论的一类非线性规划,线性函数,退 出,前一页,后一页,解：,（1）目标函数是不是凸函数？ （2）gi(x)是不是凸函数？,退 出,前一页,后一页,t为实数,一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：,什么叫一维搜索问题？,或,退 出,前一页,后一页,2.3一维搜索方法,一维搜索问题的算法分类：,精确一维搜索（最优一维搜索） 非精确一维搜索（可接

8、受一维搜索）,本节内容：,两种精确一维搜索方法：0.618法，Newton法。 两种非精确一维搜索方法：Goldstein(戈德斯坦）法,Armijo（阿米霍）法。,退 出,前一页,后一页,1. 0.618法（近似黄金分割法）,问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？,单谷函数,退 出,前一页,后一页,搜索法求解：,或,基本过程： 给出a,b,使得t*在a,b中。a,b称为搜索区间。 迭代缩短a,b的长度。 当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。,退 出,前一页,后一页,假定：已经确定了单谷区间a,b,新搜索区间为a

9、,t2,新搜索区间为t1,b,退 出,前一页,后一页,区间缩小比例的确定：,区间缩短比例为(t2-a)/(b-a),缩短比例为(b-t1)/(b-a),缩短比例 满足： 每次插入搜索点使得两个区间a,t2和t1,b相等； 每次迭代都以相等的比例缩小区间。,退 出,前一页,后一页,确定a,b,计算探索点 t1=a+0.382(b-a) t2=a+0.618(b-a),0.618法解题步骤：,停止，输出t1,以a,t2为新的搜索区间,停止，输出t2,以t1,b为新的搜索区间,退 出,前一页,后一页,例：,解：,1.第一轮： t1=1.146, t2=1.854,t200.5,退 出,前一页,后一页

10、,2.第二轮： t2=1.146, t1=0.708,t20=1.1460.5,3.第三轮： t1=0.438, t2=0.708,b-t1=1.146-0.4380.5,退 出,前一页,后一页,4.第四轮： t2=0.876, t1=0.708,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,课下练习：分析上述迭代过程，体会0.618法的实质。,退 出,前一页,后一页,2.Newton法,Newton法基本思想：,用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。,退 出,前一页,后一页,解题步骤：,给

11、定初始点t1和精度,停止，输出t1,停止，解题失败,停止，输出t2,退 出,前一页,后一页,例：,解：,取t1=1,计算：,迭代过程如下表：,退 出,前一页,后一页,3.非精确一维搜索法,数值方法的关键是从一个点迭代到下一个点。,确定下一个点的关键是确定搜索方向和步长,如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。,所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：,这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。 这样的搜索方法称之为非精确一维搜索方法,退 出,前一页,后一页,Goldstein法原理：,Y=(0)+ (

12、0)t,Y=(0)+ m2(0)t,Y=(0)+ m1(0)t,退 出,前一页,后一页,是,Goldstein算法,确定m1,m2,t0, a=0,b=+,(t0) (0)+m1 (0)t0,(t0) (0)+m2(0)t0,是,停止,输出t0,否,a=a, b=t0, t1=(a+b)/2,否,a=t0,b=b, t1=(a+b)/2 (若b=+,则t1= a),退 出,前一页,后一页,Armijo法原理：,退 出,前一页,后一页,本节课讨论n元函数的无约束非线性规划问题：,求解此类模型(UMP)的方法称为无约束最优化方法。,无约束最优化方法通常有两类： 解析法：要使用导数的方法； 直接法：

13、无须考虑函数是否可导，直接使用函数值。,退 出,前一页,后一页,2.4无约束最优化方法,1.无约束问题的最优性条件,定理1,定理2,梯度为0的点称为函数的驻点。 驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的鞍点。 定理2说明：UMP问题的局部最优解必是目标函数的驻点。,注：,退 出,前一页,后一页,定理3,定理4,退 出,前一页,后一页,例,解： 1.先求出目标函数的全部驻点； 2.利用充分条件判断驻点是不是最优点。,退 出,前一页,后一页,关于梯度的复习： 梯度是一个向量。n元函数f(x1 ,x2 ,xn)在某点x处的梯度为：,梯度的方向与函数f的等值线的一个

14、法线方向相同，从较低的等值线指向较高的等值线。,梯度的方向就是函数f的值增加最快的方向，其相反方向就是函数值降低最快的方向。,2.最速下降法,退 出,前一页,后一页,最速下降法又称为梯度法，由Cauchy于1847年给出。,最速下降法解决的是具有连续可微的目标函数的UMP问题。,最速下降法的基本思想：从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向。,退 出,前一页,后一页,最速下降法计算步骤：,选区初始点x0和精度,计算,停止，输出x0,求p0=,计算t0,使,计算x1= x0+ t0 p0,退 出,前一页,后一页,例,解：,退 出,前一页,后一页,说明： 观察P119的图，可以

15、发现x1 x0垂直于目标函数的等值线（图中的虚线）在x0的切线； 最速下降方法相邻的两个搜索方向是相互垂直的，即x1 x0垂直x1 x2； 最速下降法解决UMP的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢； 优点：迭代点列总是收敛的，而且计算过程简单。,退 出,前一页,后一页,本节课讨论约束非线性规划问题MP,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数,求解此类模型(MP)的方法称为约束最优化方法。,退 出,前一页,后一页,2.5约束最优化方法,1.约束最优化问题的最优性条件,对于MP问题：,退 出,前一页,后一页,若x*有变化，则约束条件可能没

16、有破坏,若x*有变化，则约束条件一定被破坏,令J表示MP的全部等式约束的下标集合，即J=1,2q, I表示MP的全部不等式约束的下标集合，即I=1,2p,x*的积极约束的下标集合,退 出,前一页,后一页,定理1,对于,若x*是局部最优解,则,退 出,前一页,后一页,定理1的说明：,2、称下述表达式为MP的Kuhn-Tucker条件，简称K-T条件,满足K-T条件的点称为MP的K-T点，定理1说明MP的局部最优解一定是MP的K-T点。,为了求出MP的最优解，可以先找出MP的K-T点，再做进一步的判断。,退 出,前一页,后一页,3、定理1的实例说明,定理1表明：若(x1,x2)T是局部最优解，g1

17、和g2为积极约束，则：,退 出,前一页,后一页,4.定理1的特例1,退 出,前一页,后一页,5.定理1的特例2,退 出,前一页,后一页,6.定理1的改进：,对于,若x*是局部最优解,则,互补松紧条件,退 出,前一页,后一页,7.实例说明改 进后的定理1：,定理1改进后表明：若(x1,x2)T是局部最优解，则：,退 出,前一页,后一页,互补松紧条件,退 出,前一页,后一页,定理2,对于,注：定理2表明，在凸性条件下，K-T点是整体最优解。,退 出,前一页,后一页,例：写出K-T条件; 求出相应的K-T点; 判断K-T点是不是问题的最优解,解：由于全部函数都是连续可微的，所以应用以下K-T条件,退

18、 出,前一页,后一页,首先写出原MP问题的K-T条件：,根据定理1,K-T点还应该满足原问题的约束条件,互补松紧条件,退 出,前一页,后一页,利用互补松紧条件，可以求出K-T点：,利用定理2，由于全部函数都连续可微，并且f和g都是凸函数，h是线性函数，所以K-T点就是整体最优解。,退 出,前一页,后一页,2.惩罚函数法,惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。 惩罚函数法的分类：罚函数法（外部惩罚法），障碍函数法（内部惩罚法）,退 出,前一页,后一页,(1) 罚函数法,

19、罚函数法基本原理：,考虑：,构造惩罚函数：,很大的正数,无约束最优化问题min F(x)=f(x)+p(x)的最优解必定是原问题的最优解。,退 出,前一页,后一页,可选的惩罚函数：,惩罚函数法的经济解释： f(x)为产品成本，约束条件为产品质量约束； 如果违反质量约束，就给予一定的惩罚p(x)； 追求的目标就是成本f(x)和惩罚量p(x)的总和最小（即构造的无约束最优化问题）； 如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为MP的最优解）,退 出,前一页,后一页,(2) 障碍函数法,障碍函数法基本原理： 构造一个新的目标函数，它在可行区域的边界筑起一道墙； 当迭代

20、点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部； 迭代得到的点列就只可能在可行区域的内部。,退 出,前一页,后一页,可选的惩罚函数：,考虑：,构造最优化问题：,或：,当x靠近边界时，至少有一个gi(x)趋近于零，则F(x)将无限增大，从而使得迭代点保持在可行区域的内部。,退 出,前一页,后一页,应用实例： 供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B

21、两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij， 当不用临时料场时决策变量为：Xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨

22、千米数最小，这是线性规划问题. 线性规划模型为：,设X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 编写程序gying1.m,MATLAB（gying1）,clear a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; x=5 2; y=1 7; e=20 20; for i=1:6 for j=1:2 aa(i

23、,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2); end end,CC=aa(:,1); aa(:,2); A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1; B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 ; beq=d(1);d(2);d(3);d(4);d(5

24、);d(6); VLB=0 0 0 0 0 0 0 0 0 0 0 0;VUB=; x0=1 2 3 0 1 0 0 1 0 1 0 1; xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0),计算结果为：,x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000 fval = 136.2275,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性

25、规划模型为：,设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16,（1）先编写M文件liaoch.m定义目标函数。,MATLAB（liaoch）,function f=liaoch(x) a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; e=20 2

26、0; f1=0; for i=1:6 s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2); f1=s(i)*x(i)+f1; end f2=0; for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2); f2=s(i)*x(i)+f2; end f=f1+f2;,(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; 编写主程序gying2.m.,MATLAB（gying2）,x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0; B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0