第八章--非线性规划模型课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,非线性规划模型,第八章,非线性规划模型第八章,1,1 非线性规划问题建模举例,例1 防洪优化问题,为了使位于河边的城市免受洪水的侵害，采取了两项措施：一项是筑堤，另一项是在河的上游修一水库以调解下泄的流量。欲使防洪的总费用最小，试建立数学模型。,m=0，,无约束非线性规划，,否则称为约束非线性规划,1 非线性规划问题建模举例 例1 防洪,2,解 设修水库后可将洪峰流量Q,0,调节到x,筑堤费用:,f,1,=bx,水库建设费用:,f,2,=a/x,数学模型:,最优解:,最优值:,例2 投资决策问题,某钢铁厂准备用5000万用于A、B两个项目技术改造投资，设x,1,x,2,分别表示分配给项目A、B的投资。据专家预估投资项目A、B的年收益分别为20%和16%，同时投资后的风险损失将随着总投资和单项投资的增长而增加。已知总的风险损失为,。问如何分配资金才能使期望的收益最大，同时风险损失为最小。,解 这个问题有两个指标函数: 收益函数和风险损失函数,收益函数:,风险损失函数:,解 设修水库后可将洪峰流量Q0调节到x 筑堤费用: f1,3,目标函数:,数学模型:,例3 权向量问题,为了进行多属性问题的综合评价，就需要确定每个属性的相对重要性，即求他们的权重。为此将各属性进行两两比较，从而得到如下判别矩阵。,目标函数: 数学模型: 例3 权向量问题 为了进行多属性问,4,其中元素a,ij,是第i属性的重要性与第j属性的重要性之比,数学模型:,例4 飞行管理问题（1995年全国大学生数学建模竞赛试题 A）,问题：在约10000米高空的正方形区域内，有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均由计算机记录数据，以便进行飞行管理，当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判别是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。,其中元素aij是第i属性的重要性与第j属性的重要性之比 数学,5,假定条件:,1.不碰撞的标准是任意两架飞机的距离大于8km；,2.飞机飞行方向角调整幅度不应超过30度，而要尽可能小；,3.所有飞机的飞行速度为800km/h，不受其他因素影响；,4.进入该区域的飞机在到达边缘时，与该区域内的飞机的距离应在,60km以上；,5.不考虑飞机离开区域后的情况；,6.建模时暂考虑6架飞机；,建模时补充假定条件:,1.飞机在所定区域内作直线飞行，不偏离航向；,2.飞机管理系统内不发生意外，如发动机失灵，或其他意外原因迫,使飞机改变航向；,3.飞机管理系统发出的指令应被飞机立即执行，即认为转向是瞬间,完成的。,假定条件: 1.不碰撞的标准是任意两架飞机的距离大于8km；,6,设飞机初始时刻为新飞机到达区域边缘时刻。记,表为初始时刻第i架飞机的坐标和方向角，,i,为初始瞬间第i架飞机调整后的方向角。d,ij,(,i,j,)为i,，j两架飞机分别以方向角,i,j,飞行时在区域内的最短距离。,建立模型:,数学模型:,其中:,飞机的速度为v，T,ij,表示第i，j两架飞机在区域内飞行的时间。,设飞机初始时刻为新飞机到达区域边缘时刻。记建立模型: 数学模,7,2 非线性规划的求解方法,一、无约束NLP问题的解法,取得极值的必要条件,迭代法的基本思想：首先给出,f（x）,的极小点的一个初始估计x,(0),（称为初始点），然后计算一系列的点,x,(1),x,(2),x,(k),，,希望点列,x,(k),的极限就是f（x）的极小点x,*,。,迭代法的基本思想,迭代公式的一般形式,x,(k),x,(k+1),=,k,s,(k),选择,k,，s,(k),的要求,或x,（k+1),=x,(k),+,k,s,(k),（1）要求极小化序列对应的函数值是逐次减少的，至少不增，即,（2）或者序列x,(k),中某一x,(N),本身是f（x）的极小点，或者x,(k),有一个子列的极限为x,*,，此时称算法是收敛的。,2 非线性规划的求解方法 一、无约束NLP问题的解法,8,无约束非线性规划迭代的步骤,（1）选择初始点x,(0),;,（2）如果x,(k),已求得，且x,(k),不是极小点，选取一个方向s,(k),，使目标函数f（x）沿s,(k),是下降的，至少是不增的， s,(k),称为搜索方向。,（3）在方向s,(k),确定以后，在射线x,(k),+,k,s,(k),上选取适当的步长,k,使,，如此确定下一个点x,（k+1),=x,(k),+,k,s,(k),。,确定,k,的一维搜索法,（4）检验所得的新点x,(k+1),是否为极小点或满足精度要求的近似极小点。若是极小值点，则停止迭代，否则转（2）继续迭代。,最优解的检验方法,常见的无约束非线性规划的算法,阻尼Newton法、共轭方向法和变尺度法等等。,最速下降法、Newton法、,无约束非线性规划迭代的步骤（1）选择初始点x(0); （2）,9,1最速下降法（梯度法）,基本思想,设f(x)可微,最速下降法的迭代步骤,（1）给定初始点x,(0),，精度 ，令k=0；,（2）计算,（3）若 ，则迭代结束，取x,*,=x,(k),，否则转（4）；,（4）这时 ，用一维搜索求,的一个极小点 ，使；,1最速下降法（梯度法） 基本思想 设f(x)可微最速下降法,10,最速下降法的迭代框图,给出x,(0),，精度 ，令k=0,打印x,*,，f(x,(k),),是,确定,否,k=k+1,优缺点分析,优点：（1）方法简单，每次迭代工作量小，所需存储量小。（2）从一个不好的初始点出发也往往能收敛到极小点。,缺点：在极小点附近收敛速度慢。,计算,停,最速下降法的迭代框图 给出x(0)，精度 ，令k,11,2变尺度法(DFP法),变尺度法是由W.C.Davidon于1959年首先提出来，1963年为R.Fletcher和M.J.D.Powell所发展和修正，形成著名的DFP变尺度算法。,基本思想,2变尺度法(DFP法) 变尺度法是由W,12,DFP算法的迭代步骤,（1）给定初始点x,(0),，精度 ，H,0,=I，令k=0；,（2）计算S,(k),=H,k,g,k,，沿S,(k),方向进行精确一维搜索，求步长,，使,（3） ，则迭代结束，取x,*,=x,(k+1),，计算结束；否则，若k,n1,则,计算,令k=k+1，返回（2）；若k=n1，令x,(0),=x,(k+1),，返回（2）,优缺点分析,优点：收敛速度较快。,缺点：存贮量较大。,DFP算法的迭代步骤（1）给定初始点x(0)，精度,13,二、约束非线性规划的算法（四种）,1用线性规划、二次规划来逐次逼近非线性规划。,2把约束NLP问题转化为无约束NLP问题，如：外点法，内点法，,罚函数法，乘子法等。,3对约束非线性规划问题不预先作转换，直接进行处理的分析法，,如：可行方向法，梯度投影法，既约梯度法，凸单纯形法，作,用集法等。,4对约束非线性规划问题不预先作转换的直接求解方法，如复形,法，随机试验法等。,目前，非线性规划的发展趋势是把非线性规划转化为一系列二次规划来求解。,二、约束非线性规划的算法（四种） 1用线性规划、二次规划来,14,再见,再见,15,