文档介绍:运筹学II Operations Research II
华中科技大学管理学院
管理科学与信息管理系
授课教师傅小华
Telephone:**********
E-mail:fuxhua@
2/1/2018
1
第九章非线性规划
非线性规划的数学模型
一维最优化
无约束极值的解析方法
约束极值条件下的基本方法
2/1/2018
2
非线性规划的数学模型
例(资金使用方案)
设有400万元资金,要求4年内使用完,若在一年内使用资金x万元,则可获得效益万元(效益不能再使用),当年不用的资金可存入银行,年利率为1%。试制定出这笔资金的使用方案,以使4年的经济效益总和为最大。
分析:设xj(j=1,2,3,4)表示第j年使用的资金数;z表示4年效益的总和。
目标函数
由于每年使用的资金既不能为负值,又不能超过当年的资金拥有量,于是需要满足以下约束:
(1) 非线性规划问题举例
2/1/2018
3
第一年:
第二年:
第三年:
第四年:
所以,资金使用问题的数学模型为:
2/1/2018
4
非线性规划问题可以有约束也可以没有约束(没有约束时目标函数必须是非线性的)。尽管如此,它的一般形式仍然被描述成一个约束优化问题。
非线性规划问题的一般形式为:
目标函数或约束条件中至少有一个非线性函数,这类问题称之为非线性规划问题,简记为(NP)
(2) 非线性规划模型
2/1/2018
5
如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到。
如果线性规划的最优解存在,其必然为全局或整体最优解;而非线性规划的最优解则可能为整体最优解也可能为局部最优解。(由于线性规划的目标函数为线性函数,可行域为凸集,因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然,有时求出的某个解虽是一部分可行域上的极值点,但并不一定是整个可行域上的全局最优解。)
(3)非线性规划问题的最优解
线性规划与非线性规划最优解的区别
2/1/2018
7
记(NP)的可行域为,
若,并且
则称是(NP)的整体最优解, 是(NP)的整体最优值。如果有
则称是(NP)的严格整体最优解, 是(NP)的严格整体最优值。
若,并且存在的邻域,使
则称是(NP)的局部最优解, 是(NP)的局部最优值。
整体最优解与局部最优解
2/1/2018
8
如果有
则称是(NP)的严格局部最优解, 是(NP)的严格局部最优值。
f(x)
局部最优解
整体最优解
2/1/2018
9
定义: 设集合 S Rn 为凸集,函数 f :SR
若 x(1), x(2) S, ( 0 , 1 ) ,均有
f( x(1)+(1- ) x(2) ) ≤f(x(1))+(1- )f(x(2)) ,
则称 f(x) 为凸集 S 上的凸函数。
若进一步有上面不等式以严格不等式成立,则称 f(x) 为凸集 S 上的严格凸函数。
当- f(x) 为凸函数(严格凸函数)时,则称 f(x) 为凹函数(严格凹函数)。
线性函数既是凸函数又是凹函数。
(4) 几个重要概念
凸函数和凹函数
2/1/2018
10