第六章 非线性规划(管理运筹学,李军)

非线性规划问题及其数学模型 极值问题 凸规划 一维搜索 无约束极值问题 约束极值问题2014-1-281

1. 非线性规划问题及其数学模型 非线性规划问题举例： Example1:第82页例6-1 Example2:第82页例6-2 非线性规划问题的数学模型 非线性规划问题的图示

2014-1-28

1.1 非线性规划问题举例Example1: 某商店经销A、B两种产品，售价分别 为20和380元。据统计，售出一件A 产品 的平均时间为0.5小时，而售出一件B 产品 的平均时间与其销售的数量成正比，表达 式为1 + 0.2n。若该商店总的营业时间为 1000小时，试确定使其营业额最大的营业 计划。2014-1-283

1.1 非线性规划问题举例[解] 设x1和x2分别为商店经销A、B两种产品 的件数，于是有如下数学模型：max f ( x) 20x1 380x2

0.5x1 x2 0.2x 10002 2

x1 0, x2 02014-1-284

1.1 非线性规划问题举例Example 2: 在层次分析(Analytic Hierarchy Process, 简记为 AHP)中，为进行多属性的综合评 价，需要确定每个属性的相对重要性，即 它们的权重。为此，将各属性进行两两比 较，从而得出如下判断矩阵：

2014-1-28

1.1 非线性规划问题举例J=

a11 … … an1 …

a1n … ann

,

其中： aij是第i个属性与第j个属性的重 要性之比。

2014-1-28

1.1 非线性规划问题举例现需要从判断矩阵求出各属性的权重， 为使求出的权重向量W在最小二乘意义上 能最好地反映判断矩阵的估计，由 aij=wi/wj可得： min f ( w) (a w w )n n 2

wi 1

n

i 1

j 1

ij

j

i

i

1

wi 02014-1-287

1.2 非线性规划问题的数学模型min f ( X ), X Es.t.n

hi ( X ) 0, (i 1,2, , m)g j ( X ) 0, ( j 1,2, , l )

其中 X ( x1 , x2 , , xn )T 是n维欧氏空间En中 的向量点。

2014-1-28

1.2 非线性规划问题的数学模型由于，max f ( X ) min[ f ( X )] ,“≤”不等式仅乘 “-1”即可转换为“≥”不等式；因此上述 数学模型具有一般意义。又因为等价于两 hi ( X ) 0 个不等式： ; hi ( X ) 0 ,因此非线性 规划的数学模型也可以表示为：min f ( X ), X E ng j ( X ) 0, ( j 1,2, , l )2014-1-289

1.3 非线性规划问题的图示min f ( X ) ( x1 2) ( x2 2)2 2

h( X ) x1 x2 6 0若令其目标函数f (X)=c,目标函数成为一 条曲线或一张曲面；通常称为等值线或等 值面。此例，若设f (X)=2和f (X)=4可得两 个圆形等值线，见下图：2014-1-2810

1.3 非线性规划问题的图示x2 6

f(X)=4 32 0 x1 2 3 6

f(X)=2

由左图可见,等值线 f (X)=2和约束条件直 线6-6相切，切点D即 为此问题的最优解， X*=(3, 3),其目标函 数值 f (X*)=2。

2014-1-28

1.3 非线性规划

问题的图示在此例中，约束h( X ) x1 x2 6 0 对最优解发生 了影响，若以 h( X ) x1 x2 6 0 代替原约束， 则非线性规划的最优解是X (2,2) ,即图中的 C点，此时 f ( X ) 0 。由于最优点位于可行域 的内部，故事实上约束 h( X ) x1 x2 6 0 并未 发挥作用，问题相当一个无约束极值问题。

2014-1-28

1.3 非线性规划问题的图示[注] 线性规划存在最优解，最优解只能在 其可行域的边缘上(特别能在可行域的顶 点上)得到；而非线性规划的最优解(如 果存在)则可能在可行域的任意一点上得 到。

2014-1-28

2. 极值问题 局部极值与全局极值 极值点存在的条件 凸函数和凹函数 凸函数的性质 函数凸性的判定

2014-1-28

2.1 局部极值与全局极值 线性规划 最优解 非线性规划 局部最优解 全局最优解 未必全局最优

2014-1-28

局部极值 对于 X-X* < 均有不等式 f (X) ≥ f (X*) , 则称 X*为 f (X)在 R上的局部极小点，f (X*) 为局部极小值； 对于 X-X* < 均有不等式 f (X) > f (X*) , 则称 X*为 f (X)在 R上的严格局部极小点， f (X*)为严格局部极小值；

2014-1-28

全局极值 对于X,X* ∈R均有不等式 f (X) ≥ f (X*) , 则称 X*为 f (X)在 R上的全局极小点，f (X*) 为全局极小值； 对于X,X* ∈R均有不等式f (X) > f (X*) , 则称X*为f (X)在R上的严格全局极小点， f (X*)为严格全局极小值。2014-1-2817

2.2 极值点存在的条件 必要条件 设R是En上的一个开集，f (X)在R上有一阶 连续偏导数，且在点 X R 取得局部极值， 则必有

或

f ( X ) x1

f ( X ) x2

f ( X ) xn

0

f ( X ) 02014-1-2818

必要条件 f ( X ) f ( X ) f ( X ) f ( X ) T ( x , x , , x ) 为函数 1 2 n

f (X)

在 X*点处的梯度。 由数学分析可知， f ( X ) 的方向为X*点处 等值面(等值线)的法线方向，沿这一方 向函数值增加最快，如图所示。

2014-1-28