四*、非线性规划 第7章无约束问题 第8章约束极值问题 清华大学出版社
四*、非线性规划 ◼第7章 无约束问题 ◼第8章 约束极值问题 清华大学出版社 1
令在科学管理和其他领域中,很多实际问题可归结为线性 规划问题。但也有很多问题,其目标函数和(或)约束条 件很难用线性函数表达。如果目标函数或约束条件中含 有非线性函数,就称这种问题为非线性规划问题。 解这类问题需要用非线性规划方法。目前,非线性规划 已成为运筹学一个重要分支,在最优设计、管理科学 系统控制等许多领域得到越来越广泛的应用。 一般说来,由于非线性函数的复杂性,解非线性规划问 题要比解线性规划问题困难得多。而且,也不像线性规 划那样有单纯形法等通用方法。非线性规划目前还没有 适于各种问题的一般性算法,各个方法都有自己特定的 适用范围。 清华大学出版社
引 言 ❖ 在科学管理和其他领域中，很多实际问题可归结为线性 规划问题。但也有很多问题，其目标函数和(或)约束条 件很难用线性函数表达。如果目标函数或约束条件中含 有非线性函数，就称这种问题为非线性规划问题。 ❖ 解这类问题需要用非线性规划方法。目前，非线性规划 已成为运筹学一个重要分支，在最优设计、管理科学、 系统控制等许多领域得到越来越广泛的应用。 ❖ 一般说来，由于非线性函数的复杂性，解非线性规划问 题要比解线性规划问题困难得多。而且，也不像线性规 划那样有单纯形法等通用方法。非线性规划目前还没有 适于各种问题的一般性算法，各个方法都有自己特定的 适用范围。 清华大学出版社 2
第7章无约束问题 第1基本概念 第2节一维搜索 第3节无约束极值问题的解法 3 清华大学出版社
第7章 无约束问题 ◼第1节 基本概念 ◼第2节 一维搜索 ◼第3节 无约束极值问题的解法 清华大学出版社 3
第1节基本概念 今1.1引言 o1.问题的提出 例1某公司经营两种产品,第一种产品每件售价30元,第二种产品每 件售价450元。根据统计,售出一件第一种产品所需要的服务时间平 均是05小时,第二种产品是(2+0.25x2)小时,其中x2是第二种产品的 售出数量。已知该公司在这段时间内的总服务时间为800小时,试决 定使其营业额最大的营业计划。 设该公司计划经菅第一种产品x件,第二种产品x2件。根据 题意,其营业额为f(X)=30x1+450x2 由于服务时间的限制,该计划必须满足0.5x+(2+025x2)x2≤800 此外,这个问题还应满足x1≥0,x2≥0,得到本问题数学模型为: max f(X)=30x,+ 450x2 0.5x1+2x,+0.25x2≤800 x≥0,x2≥0 清华大学出版社
第1节 基本概念 ❖ 1.1 引言 1. 问题的提出 例1 某公司经营两种产品，第一种产品每件售价30元，第二种产品每 件售价450元。根据统计，售出一件第一种产品所需要的服务时间平 均是0.5小时，第二种产品是(2+0.25x2 )小时，其中x2是第二种产品的 售出数量。已知该公司在这段时间内的总服务时间为800小时，试决 定使其营业额最大的营业计划。 1 2 f X x x ( ) 30 450 = + 0.5 2 0.25 800 x x x 1 2 2 + + ( ) 1 2 x x 0, 0 ( ) 1 2 2 1 2 2 1 2 max 30 450 0.5 2 0.25 800 0, 0 f X x x x x x x x = + + + 设该公司计划经营第一种产品x1件，第二种产品x2件。根据 题意，其营业额为 由于服务时间的限制，该计划必须满足 此外，这个问题还应满足 ，得到本问题数学模型为： 清华大学出版社 4
第1节基本概念 例2为了进行多属性问题(假设有n个属性)的综合评价,需要确定每个属 性的相对重要性,即求它们的权重。为此将各属性的重要性进行两两比 较,从而得出如下判断矩阵 a1 a1 J= 其中元素②是第个属性的重要性与第个属性的重要性之比。 现需从判断矩阵求出各属性的权重w(=1,2…,n) 为了使W=(m,w2…,w)在最小二乘意义上能最好反映判断矩阵的估计,由 a,≈1/可得 min∑∑(a1-) ∑v=1 清华大学出版社
第1节 基本概念 11 1 1 = n n nn a a J a a ij a w n i (=1,2, , ) ( ) T 1 2 , , , W w w w = n / i j i j a w w ( ) 2 1 1 1 min 1 n n i j j i i j n i i a w w w = = = − = 例2 为了进行多属性问题(假设有n个属性)的综合评价，需要确定每个属 性的相对重要性，即求它们的权重。为此将各属性的重要性进行两两比 较，从而得出如下判断矩阵 其中元素 是第i个属性的重要性与第j个属性的重要性之比。 为了使 在最小二乘意义上能最好反映判断矩阵的估计，由 ，可得 现需从判断矩阵求出各属性的权重 清华大学出版社 5
第1节基本概念 2.非线性规划问题的数学模型 非线性规划的数学模型常表示成以下形式 min f(X) (6-1) h,(X)=0,1=1,2,…m(6-2) 8(X)≥0,j=12,…,l(6-3) 其中自变量X=(x,x2…“x)是n维欧氏空间E中的向量(点) f(X)为目标函数, h(X)=0和g(X)≥0为约束条件。 清华大学出版社
第1节 基本概念 2．非线性规划问题的数学模型 min ( ) (6 1) ( ) 0, =1, 2, (6 2) ( ) 0, 1, 2, , (6 3) … − = − = − i j f X h X i m g X j l T 1 2 ( , , , ) X x x x = … n n E f X( ) ( ) 0 i h X = ( ) 0 j g X 非线性规划的数学模型常表示成以下形式 其中自变量 是n维欧氏空间 中的向量(点)； 为目标函数， 和 为约束条件。 清华大学出版社 6
第1节基本概念 由于 maxf(X)=-min-f(X) 当需使目标函数极大化时,只需使其负值极小化即可。因而仅考虑目标 函数极小化,这无损于一般性。 若某约束条件是“s”不等式时,仅需用“-1”乘该约束的两端,即可 将这个约束变为“≥”的形式 由于等式约(X)=0等价于下述两个不等式约束: h(X)≥0 h(X)≥0 因而,也可将非线性规划的数学模型写成以下形式 min f(x) (6-4) g,(X)≥0,=1,2,…l(6-5) 清华大学出版社
第1节 基本概念 max ( ) min ( ) f X f X = − − ( ) 0 i h X = ( ) 0 ( ) 0 i i h X h X − min ( ) (6 4) ( ) 0, 1,2, , (6 5) ＝ … − − j f X g X j l 由于 当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标 函数极小化，这无损于一般性。 若某约束条件是“≤”不等式时，仅需用“-1”乘该约束的两端，即可 将这个约束变为“≥”的形式。 由于等式约束 等价于下述两个不等式约束： 因而，也可将非线性规划的数学模型写成以下形式 清华大学出版社 7
第1节基本概念 o3.非线性规划问题的图示 图示法可以给人以直观概念,当只有两个自变量时,非线性规划问 题也可像线性规划那样用图示法来表示如图6-1所示 考虑非线性规划问题 ∫min(x)=(x-2)2+(x2-2)2(6-6) h(X)=x1+x26=0 (6-7 若令其目标函数 f(X)=c(68) 其中c为某一常数,则(68)式代表目标函数值等于c的点的集合,它 般为一条曲线或一张曲面,通常称其为等值线或等值面。对于这个例 子来说,若令目标函数6-6)式分别等于2和4,就得到相应的两条圆形 等值线(图6-1)。由图可见,等值线(X)=2和约束条件直线AB相切,切 点D即为此问题的最优解:x1x2=3,其目标函数值八X)=2。 清华大学出版社
第1节 基本概念 3．非线性规划问题的图示 图示法可以给人以直观概念，当只有两个自变量时，非线性规划问 题也可像线性规划那样用图示法来表示(如图6-1所示)。 2 2 1 2 1 2 min ( ) ( 2) ( 2) (6 6) ( ) 6 0 (6 7) ＝ － ＋ － ＝ ＋ － ＝ − − f X x x h X x x f X c ( ) (6-8) ＝ 考虑非线性规划问题 若令其目标函数 其中c为某一常数，则(6-8)式代表目标函数值等于c的点的集合，它一 般为一条曲线或一张曲面，通常称其为等值线或等值面。对于这个例 子来说，若令目标函数(6-6)式分别等于2和4，就得到相应的两条圆形 等值线(图6-1)。由图可见，等值线f(X)=2和约束条件直线AB 相切，切 点D即为此问题的最优解：x1 *=x2 *=3，其目标函数值f(X* )=2。 清华大学出版社 8
第1节基本概念 在这个例子中,约束条件(6-7)式对最优解是有影响的。现若以 h(X)=x+x26≤0(6-9 代替约束条件67)式,则非线性规划问题6)心 式、(6-9)式的最优解是x=x2=2,即图61中的 C点(这时(X)=0)。由于最优点位于可行域的 f(X)=4 内部,故对这个问题的最优解来说,约束(6-9)3 式事实上是不起作用的。在求这个问题的最 D f(X)=2 优解时,可不考虑约束条件(69)式,就相当 于没有这个约束一样 由第一章知道,如果线性规划问题的最优解 23 存在,其最优解只能在其可行域的边界上达 到(特别是在可行域的顶点上达到):而非线性 规划问题的最优解(如果最优解存在)则可能在 图6-1 其可行域中的任意一点达到。 清华大学出版社
第1节 基本概念 图6-1 在这个例子中，约束条件(6-7)式对最优解是有影响的。现若以 1 2 h X x x ( ) 6 0 (6 9) ＝ ＋ － − 代替约束条件(6-7)式，则非线性规划问题(6-6) 式、(6-9)式的最优解是x1=x2=2，即图6-1中的 C点(这时f(X)=0)。由于最优点位于可行域的 内部，故对这个问题的最优解来说，约束(6-9) 式事实上是不起作用的。在求这个问题的最 优解时，可不考虑约束条件(6-9)式，就相当 于没有这个约束一样。 由第一章知道，如果线性规划问题的最优解 存在，其最优解只能在其可行域的边界上达 到(特别是在可行域的顶点上达到)；而非线性 规划问题的最优解(如果最优解存在)则可能在 其可行域中的任意一点达到。 清华大学出版社 9
第1节基本概念 1.2极值问题 o1.局部极值和全局极值 于线性规划的日标函数为线性西数,可行域为凸集,因而求出的 最优解就是在整个可行域上的全局最优解。非线性规划却不然, 有的求出的某个解虽是一部分可行域上的极值点,但却并不一定 是整个可行域上的全后最优解。 清华大学出版社
第1节 基本概念 ❖ 1.2 极值问题 1．局部极值和全局极值 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的 最优解就是在整个可行域上的全局最优解。非线性规划却不然， 有时求出的某个解虽是一部分可行域上的极值点，但却并不一定 是整个可行域上的全局最优解。 清华大学出版社 10