运筹学习题集

设有某物资要从A1,A2,A3调往B,B2B3,B4,平衡表及运价表如下问应怎样调运才能 使总运费最少? 平衡表(单 运价表(单位:元吨 B B B2 B BB2 B lI A 6 7 105 ④ (答案;初始基本可行解为{x13,x1,x2x2,x2,x3x}=43,316,3} 相应运价为{C13C14、C21,C2,C2C4}=312,2,4.5,} 总运费S=4×3+3×12+3×1+1×2+6×4+3×5=92(元)) 32对上题用最小元素法已编制出初始调运方案 ①再用左上角法编制一个初始调运方案 ②用闭回路法或位势法,对其中任一方案,判别是否为最优?并对方案进行调整. (答案:对空格是非基变量的x1x12,x2x24,x31,x3分别作闭回路求出其检验数,若 检验数中有正数,则对方案进行调整,方法见教材 P127129,2=1>0,24=2>0,A1=2.0得3个调整量最终调整方案为 有数字格的基变量是x1,x32,x21x242x2,x4分别乘相应运价得 S=2×3+5×3+1×1+3×8+6×4+3×5=85(元)为最优调运方案) 33(运输问题的图上作业法)某物资25吨由发点A1,A2,A3,A4,A发货,发货量分别是7 24102吨运往收点B1,B2,B3,B4收货收货量分别是66,10.3吨交通图如下 B4国 B2回 A4⑩ B 6 A1⑦ A② B2回

9 设有某物资要从 1 2 3 A , A , A 调往 1 2 3 4 B ,B ,B ,B ,平衡表及运价表如下.问应怎样调运,才能 使总运费最少? 平衡表(单位:吨) 运价表(单位:元/吨) 销地 产地 B1 B2 B3 B4 产 量 B1 B2 B3 B4 A1 4 3 7 3 11 3 12 -⑤ A2 3 1 4 1 9 2 8 - ② A3 6 3 9 7 4 10 5 - ⑥ 销 量 3 6 5 6 20 ① ④ ③ (答案; 初始基本可行解为 x13 , x14 , x21x23 , x32 , x34= 4,3,3,1,6,3 相应运价为 C13 ,C14 ,C21,C23 ,C32C14= 3,12,1,2,4,5, 总运费 S = 43+312+31+12+ 64+35 = 92 (元) ) 32.对上题,用最小元素法已编制出初始调运方案, ① 再用左上角法编制一个初始调运方案. ② 用闭回路法或位势法,对其中任一方案,判别是否为最优?并对方案进行调整. （答案: 对空格是非基变量的 11 12 22 24 31 33 x , x , x , x , x , x 分别作闭回路,求出其检验数,若 检验数中有正数 , 则对方案进行调整 , 方法见教材 P.127,129, 22 =1 0,24 = 2  0,11 = 2.0 得3个调整量,最终调整方案为: 有 数 字 格 的 基 变 量 是 11 13 21 24 32 34 x , x , x x , x , x 分 别 乘 相 应 运 价 得 S = 23+53+11+38+ 64+35 = 85 (元)为最优调运方案.） 33.(运输问题的图上作业法) 某物资 25 吨,由发点 1 2 3 4 5 A , A , A , A , A 发货,,发货量分别是 7, 2,4,10,2 吨,运往收点 1 2 3 4 B ,B ,B ,B 收货,收货量分别是 6,6,10,3 吨,交通图如下: B4 □3 B3 □10 A5 ② A4 ⑩ B1 □6 A3 ④ A1 ⑦ A2 ② B2 □6

问应如何调运才能使吨公里最小? (答案:采用丢边破圈法,见教材P.136,最后得最优调运方案,总运输量为 S=7×10+1×6+3×3+10×6+4×5+2×9=183(吨公里)) 下篇非线性规划( Nonlinear programming) 第一章基本概念 1用图解法求下面两个变量的非线性规划的最优解 mnf(x)=4x2+(x,-2)2 2<x,≤2 1<x<1 (答案等高线与可行域的切点X=(0,)为 此问题的最优解) 复习思考题 2.试述非线性规划数学模型的一般形式及其与线性规划模型的主要区别 3分别说明在什么条件下,称X为f(x)在R”上的局部最小点严格局部最小点全局极小 点,严格全局极小点 4分别写出下述概念的数学表达式 (a)函数f(x)在X处的梯度 (b)f(x)在X处的Hese矩阵 (c)二次型 (d)正定、半正定、负定、半负定二次型的充要条件 5. 试计算以下各函数的梯度和Hese矩阵: (1)f(x)=x2+x2+x3(答案:Vf(x)= af(x) af(x)a(x) =(2x1,2x2,2x3), 「a2fx)a2f(x)a3/(x) ax, ax, ax ax, ax (X)=V2f(x) af(x)af(x) a2f(x020) ax a f(x)af(x)af(x) 002 ax,ax, ax,ax, ax3 (2)f(x)=h(x2+x1x2+x2 解V(x)=/~2x1+x2 x2+x1x2+x2x2+x2+x2

10 问应如何调运才能使吨公里最小? (答案:采用丢边破圈法,见教材 P.136,最后得最优调运方案,总运输量为 S = 710+16+33+106+ 45+ 29 =183 (吨公里) ) 下篇 非线性规划 (Nonlinear Programming) 第一章 基本概念 1.用图解法求下面两个变量的非线性规划的最优解: 2 2 2 1 min f (x) = 4x + (x − 2) s.t.    −   −   1 1 2 2 2 1 x x (答案:等高线与可行域的切点 T X (0,1) * = 为 此问题的最优解) 复习思考题: 2.试述非线性规划数学模型的一般形式及其与线性规划模型的主要区别. 3.分别说明在什么条件下,称 * X 为 f (x) 在 n R 上的局部最小点,严格局部最小点,全局极小 点,严格全局极小点. 4.分别写出下述概念的数学表达式: (a) 函数 f (x) 在 * X 处的梯度; (b) f (x) 在 * X 处的 Hesse 矩阵; (c) 二次型; (d) 正定、半正定、负定、半负定二次型的充要条件. 5. 试计算以下各函数的梯度和 Hesse 矩阵: (1) 2 3 2 2 2 1 f (x) = x + x + x (答案: ▽ T T x x x x f x x f x x f x f x (2 ,2 ,2 ) ( ) , ( ) , ( ) ( ) 1 2 3 1 2 3  =            = , H(X ) = ▽ 2                                           = 2 3 2 3 2 2 3 1 2 2 3 2 2 2 2 2 1 2 1 3 2 1 2 2 2 1 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) x f x x x f x x x f x x x f x x f x x x f x x x f x x x f x x f x f x =           0 0 2 0 2 0 2 0 0 ) (2) 2 1 2 2 2 1 f (x) = ln( x + x x + x 解 T x x x x x x x x x x x x f x       + + + + + +  = 2 1 2 2 2 1 1 2 2 1 2 2 2 1 1 2 2 , 2 ( )

HCX 2x2-2x2+x2-x2 x2+x1x2+x2 (3)f(x)=3x2+4e 解V(x)=(3x2+4x2e6x1x2+4x1e) 4x 6.求下列各函数的驻点,并判定它们是极小点或是鞍点 (1)f(x)=5x2+12xx2-16x1x3+10x2-26x2x3+17x3 (答案:驻点X'=(11,95,78)为严格极小点) (2)f(x)=f(x1,x2,x3)=x2-4x1x2+6xx3+5x2-10x2x3+8x3 (答案;驻点X=(00.0)7是鞍点) (3)f(x)=-x2+x1-x2+x2x3+2x3 (答案;驻点x=(124 233)为极大点) 第二章最优化方法 复习思考题 7.试述凸函数,严格凸函数,凹函数,严格凹函数的定义 8.判别一个函数是否为凸函数的一阶、二阶条件.(教材P.172定理14,15) 9试判定以下函数的凹凸性 (1)f(x)=x2+2x1x2+3x2(答案:由f(x)的Hese矩阵H(x)= 为正 04 定,知f(x)为严格凸函数) (2)f(x)=xx (答案由∫(x)的Hese矩阵H(X)= 不定,故f(x)为非凸也非凹函数) 10判定下述非线性规划是否为凸规划? 1)maxf(x)=x?+2x2 11

11       − − − − − − − + − − − + + = 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 4 2 2 1 2 2 4 ( ) x x x x x x x x x x x x x x x x x x x x H X (3) ( ) 3 4 2 f x = x1 x2 + 1 2 x x e 解 x x x x T f (x) (3x 4x e ,6x x 4x e ) 1 2 1 2 2 1 2 1 2  = 2 + +       + + + + + = 1 2 1 2 1 2 1 2 2 2 1 2 1 1 2 1 2 2 2 6 4 (1 ) 6 4 4 6 4 (1 ) ( ) x x x x x x x x x e x x x x e x e x e x x H X 6.求下列各函数的驻点,并判定它们是极小点或是鞍点: (1) 3 2 3 3 2 1 2 1 3 2 2 f (x) = 5x1 +12x x −16x x +10x − 26x x +17x (答案: 驻点 T X (11,95,78) * = 为严格极小点.) (2) 2 2 3 3 2 1 2 1 3 2 2 f (x) = f (x1 , x2 , x3 ) = x1 − 4x x + 6x x + 5x −10x x + 8x (答案;驻点 T X (0,0,0) * = 是鞍点.) (3) 2 2 3 3 2 1 2 2 f (x) = −x1 + x − x + x x + 2x (答案;驻点 T X ) 3 4 , 3 2 , 2 1 ( * = − 为极大点.) 第二章 最优化方法 复习思考题: 7.试述凸函数,严格凸函数,凹函数,严格凹函数的定义. 8.判别一个函数是否为凸函数的一阶 、二阶条件.(教材 P.172 定理 1.4,1.5) 9.试判定以下函数的凹凸性: (1) 2 1 2 2 2 f (x) = x1 + 2x x + 3x (答案:由 f (x) 的 Hesse 矩阵 H(X )       = 0 4 2 0 为正 定,知 f (x) 为严格凸函数.) (2) 1 2 f (x) = x x (答案:由 f (x) 的 Hesse 矩阵       = 0 0 0 0 H(X ) 为 不定,故 f (x) 为非凸也非凹函数.) 10.判定下述非线性规划是否为凸规划? (1) 2 2 2 max f (x) = x1 + 2x

x1+x2≤9 x2≥0 (2)maxf(x)=x1+x2-2x1+x1x2+1 81(x)=3x1+5x2-4≥0 st.{g:(x)=-3x2+x2-12x2-8x+10 x1x2≥0 (答案:(1)H(104/为正定故f(x)为凸函数g(x)=-x2-x2+920的 海赛矩阵H(X) 0-2为负定,g(x)为凹函数故此线性规划为凸规划) 21 (2)H(X) 为正定,f(x)为凸函数.H(X) 定,g2(x)为凹函数故原非线性规划为凸规划) 复习思考题 ll分述一维搜索中斐波那契( Fibonacci)法及黄金分割法的主要思想,主要步骤及适用范 下面简介 Fibonacci数 十三世纪初,意大利比萨的一位叫伦纳地绰号叫斐波那契( Fibonacci,1170-1250是 filius Bonacci意思是“波那契之子”)的数学家在一本题为《算盘书》的数学著作中,提出下面 个有趣订的问题: 兔子出生以后两个月就能生小兔,若每次不多不少恰好生一对(一雌一雄),假如养了初生 的小兔一对,试问一年后可有多少对兔子(如果生下的小兔子都不死的话)? 推算如下 第一个月:只有一对小兔; 第二个月:小兔子没有长成不会生殖,仍然是一对兔子 第三个月:这对兔子生了一对小兔子,这是共有二对兔子 第四个月:老兔子又生了一对小兔,而上月生的小兔还未成熟,这时共对兔子 第五个月:这时已有两对兔子可以生殖(原老兔和第三月初生的小兔),于是生了两对,共 对兔子 如此推算下去,得结果:1,1,2,3,5,8,13,21,34,55,…,233 一年后(第13个月)共有兔子233对 我们把数列{En}:1,1,2,3,5,.8,13,21,34,…叫 Fibonacci数列 1634年(斐氏死后400年)数学家奇拉特发现, Fibonacci数列的通项公式

12 s.t.    0 9 2 2 2 2 1  +  x x x (2) max ( ) 2 1 1 2 1 2 2 2 f x = x1 + x − x + x x + s.t.       = − + − − + = + −  0 ( ) 3 12 8 10 ( ) 3 5 4 0 1 2 1 2 2 2 2 2 2 1 1 1 2 x x g x x x x x x g x x x (答案: (1)       = 0 4 2 0 H(X ) 为正定,故 f (x) 为凸函数, ( ) 9 0 2 2 2 g x = −x1 − x +  的 海赛矩阵       − − = 0 2 2 0 H(X ) 为负定, g(x) 为凹函数,故此线性规划为凸规划. ) (2)       = 1 2 2 1 H(X ) 为正定 , f (x) 为凸函数 .       − − − = 12 2 6 12 H(X ) 负 定, ( ) 2 g x 为凹函数,故原非线性规划为凸规划. ) 复习思考题: 11.分述一维搜索中斐波那契( Fibonacci) 法及黄金分割法的主要思想,主要步骤及适用范 围. 下面简介 Fibonacci 数. 十三世纪初,意大利比萨的一位叫伦纳地,绰号叫斐波那契(Fibonacci ,1170-1250 是 filius Bonacci 意思是“波那契之子”)的数学家在一本题为《算盘书》的数学著作中,提出下面一 个有趣订的问题: 兔子出生以后两个月就能生小兔,若每次不多不少恰好生一对(一雌一雄),假如养了初生 的小兔一对,试问一年后可有多少对兔子(如果生下的小兔子都不死的话)? 推算如下: 第一个月:只有一对小兔; 第二个月:小兔子没有长成不会生殖,仍然是一对兔子; 第三个月:这对兔子生了一对小兔子,这是共有二对兔子; 第四个月:老兔子又生了一对小兔,而上月生的小兔还未成熟,这时共对兔子; 第五个月:这时已有两对兔子可以生殖(原老兔和第三月初生的小兔),于是生了两对,共 5 对兔子: …………………………………………………………………………… 如此推算下去,得结果: 1,1,2,3,5,8,13,21,34,55,…,233 一年后(第 13 个月)共有兔子 233 对. 我们把数列 Fn  :1,1,2,3,5,8,13,21,34,…叫 Fibonacci 数列. 1634 年(斐氏死后 400 年)数学家奇拉特发现,Fibonacci 数列的通项公式:

设 F。=0,F1 F=F,+F 通项公式(内比公式)为:F √52 (这公式是18世纪初,棣美佛在其所著《分析集锦》( Miscellanea Analytica)中给出的) 由此数列引出许多重要的发现 173,希姆松发现斐氏数列中前后两项之比r,是连分数1—的第n个渐近 1+ 分数 1884年,拉姆斯证明了(利用了斐氏数列):应用辗转相除(欧几里德除法)法的步数(辗转 除的次数)不大于较小的那个数的位数的5倍 1876年,鲁卡斯发现 方程x2-x-1=0的两个根r 的任何次幂的线性组合都满 足关系式FnFn+Fn=1 卡鲁斯还利用斐氏数列的性质证明了227-1是一个质数(有39位,验证非轻而易 举),“斐波那契数列”名称正是出自卡鲁斯之口. 本世纪50年代数学家华罗庚教授在推广运筹学的优选法工作中也找到了斐氏数列的巧妙 应用,这就是黄金分割数:im ≈0.618 由于这个数列越来越多的性质被人们所发现(例如:植物的叶序,菠萝的鳞片,树枝的生长, 蜂进蜂房,上楼方式,雄蜂家族,钢琴键盘以及几何、代数、概率、…的问题都与斐氏数列有 关.)和应用,因而引起了数学家的关注,一本专门研究它的杂志《斐波那契季刊》 Fibonacci Quarterly于1963年开始发行 12.用 Fibonacci法求函数 f(x)=-3x2+216x+1 在区间[025]上的极大点,要求缩短后的区间长度不大于原区间长度的8% (答案:l3=3.8642为近似最优点,maxf(x)=396705) 13.用 Fibonacci数求 mn2-1+21-1≤1≤3},设最终区间长度不超过0.08 (答案:t5=0.538为近似极小点,mnf(m)=1.751,缩短后的区间长度为

13 设    = +  = = − − , 2 0, 1 1 2 0 1 F F F n F F n n n 通项公式(内比公式)为:       − − + = n n Fn ) 2 1 5 ) ( 2 1 5 ( 5 1 (这公式是 18 世纪初,棣美佛在其所著《分析集锦》(Miscellanea Analytica)中给出的) 由此数列引出许多重要的发现: 1753 年,希姆松发现斐氏数列中前后两项之比 n−1 n F F 是连分数 1 ... 1 1 1 1 1 + + + 的第 n 个渐近 分数. 1884 年,拉姆斯证明了(利用了斐氏数列):应用辗转相除(欧几里德除法)法的步数(辗转 除的次数)不大于较小的那个数的位数的 5 倍. 1876 年,鲁卡斯发现: 方程 1 0 2 x − x − = 的两个根 2 1 5 , 2 1 5 1 2 − = +  =  的任何次幂的线性组合都满 足关系式 Fn+1Fn + Fn−1 . 卡鲁斯还利用斐氏数列的性质证明了 2 1 127 − 是一个质数(有 39 位,验证非轻而易 举),“斐波那契数列”名称正是出自卡鲁斯之口. 本世纪 50 年代数学家华罗庚教授在推广运筹学的优选法工作中也找到了斐氏数列的巧妙 应用,这就是黄金分割数: 0.618 2 5 1 lim 1  − = − → n n n F F . 由于这个数列越来越多的性质被人们所发现(例如:植物的叶序,菠萝的鳞片,树枝的生长, 蜂进蜂房,上楼方式,雄蜂家族,钢琴键盘以及几何、代数、概率、…的问题都与斐氏数列有 关.)和应用,因而引起了数学家的关注,一本专门研究它的杂志-《斐波那契季刊》(Fibonacci Quarterly 于 1963 年开始发行. 12.用 Fibonacci 法求函数 ( ) 3 21.6 1 2 f x = − x + x + 在区间 0,25 上的极大点,要求缩短后的区间长度不大于原区间长度的 8%. (答案: t 3 = 3.8642 为近似最优点,max f (x) = 39.6705 ) 13.用 Fibonacci 数求 min  2 2 t − t + 〡 −1 t  3  , 设 最 终 区 间 长 度 不 超 过 0.08 . ( 答 案 : t 5 = 0.538 为近似极小点 , min f (t) = 1.751 , 缩短后的区间长度为

0.545-0.231=0.314,0.314÷4=00785<008) 14.用黄金分割法求解下述函数的极小值 f()=t-153+7212-1351 l≤t≤15 要求|(tn)-f(n-)≤005=6 (答案:经过7次迭代,因为b1-a2=048<0.05,精度满足要求迭代终止,包含最优 解的区间是[,b2]=63486.828]) 第三章无约束极值问题 15.用最速下降法(梯度法)求下述函数的极大点,给定初始点X0)=(0,0),要求迭代4 f(x)=2x2+2x2-x2-2 要求梯度精度E=0.3 (答案:函数的极大点为x=X4)=(3/43/4)且f(X+)=15/16) 16.试用 Newton法求解 2 取初始点X=(40),并将采用最佳步长和固定步长A=10时的情形做比较 (答案:取步长λ=1.0时,不收敛,取最佳步长时收敛,极小点为 (0,0)2,f(x)=-0.5 17.试用牛顿法求解第15题 由戴维顿于1959年提出,佛莱彻-鲍威尔于1963年改进的变尺度法,有更快的收敛速度, 且避免了二阶导数矩阵及其求逆过程,特别适于求解高维最优化问题. 18.用DFP法(变尺度法)求解 min f(x)=x1(x2+1)4 (答案 (0-1)X为极小点.) 第四章约束极值问题 复习思考题 19.什么是库恩-塔克条件和库恩一塔克点,为什么满足库恩-塔克条件是点X成为最优点 的必要条件? 答:假定X是非线性规划

14 0.545-0.231=0.314, 0.3144 = 0.0785  0.08 ) 14.用黄金分割法求解下述函数的极小值 f (t) t 15t 72t 135t 4 3 2 = − + − , 1 t 15 要求 −  =  f (t n ) f (t n−1 ) 0.05 (答案:经过 7 次迭代,因为 b7 − a7 = 0.48  0.05,精度满足要求,迭代终止,包含最优 解的区间是  ,  6.348,6.828 a7 b7 = ) 第三章 无约束极值问题 15.用最速下降法(梯度法)求下述函数的极大点,给定初始点 T X (0,0) (0) = ,要求迭代 4 步, 2 2 2 f (x) = 2x1 x2 + 2x2 − x1 − 2x 要求梯度精度  = 0.3 (答案:函数的极大点为 T X X (3/ 4,3/ 4) * (4) = = 且 ( ) 15/16 (4) f X = ) 16.试用 Newton 法求解 2 1 min ( ) 2 2 2 1 + + = − x x f x 取初始点 T X (4,0) (0) = ,并将采用最佳步长和固定步长  =1.0 时的情形做比较. ( 答 案 : 取步长  =1.0 时 , 不 收 敛 , 取 最 佳 步 长 时 收 敛 , 极 小 点 为 (0,0) , ( ) 0.5 * * X = f X = − T 17.试用牛顿法求解第 15 题. 由戴维顿于 1959 年提出,佛莱彻-鲍威尔于 1963 年改进的变尺度法,有更快的收敛速度, 且避免了二阶导数矩阵及其求逆过程,特别适于求解高维最优化问题. 18.用 D.F.P 法(变尺度法)求解 2 2 4 1 min f (x) = x (x +1) (答案: T X (0, 1) (2) = − X 为极小点. ) 第四章 约束极值问题 复习思考题: 19.什么是库恩-塔克条件和库恩-塔克点,为什么满足库恩-塔克条件是点 * X 成为最优点 的必要条件? 答:假定 * X 是非线性规划

min f(x) g,(x)≥0.i=1,2…,m s. t h(x)=0,j=12…,P (4.1) 的极小点该点可能位于可行域的内部这是无约束问题,X必满足Vf(x)=0若X位于 可行域的边界上,不失一般性设X位于第一个约束形成的可行域边界上,即第易个约束是 X点的起作用的约束(g1(X')=0)X是极小点则Vg1(X)必与Vf(X)在一条直线上 且方向相反这说明在上述条件下存在实数A1≥0使 vf(r)-AVg,(X0=0 若有m个起作用约束,Vg1(X)Vg2(X),Vgn(X)线性无关,即存在 1≥0,…,m≥0,使 V(x)-∑Vg,(X 为了把不起作用的约束也包括在上式中增加条件 1g(X)=0 1≥0 我们用 h,(x)≥0 h,(x)≤0 代替约束条件b(x)=0 这样可得如下条件 v(x)-∑lh,(x)=0 t,h, (X)=0 ly20.(=12…,P) 这样设x”是(41)式极小点而且X点的所有起作用约束的梯度V(X,j=12…P和 Vg(X,=12,,m线性无关则存在A=(,2,…,篇)及U=(u,2,…,n),使 下述条件成立

15 min f (x) s.t.    = =  = h x j p g x i m j i ( ) 0, 1,2,..., ( ) 0, 1,2,..., (4.1) 的极小点,该点可能位于可行域的内部,这是无约束问题, * X 必满足 ( ) 0 * f X = .若 * X 位于 可行域的边界上,不失一般性,设 * X 位于第一个约束形成的可行域边界上,即第易个约束是 * X 点的起作用的约束( ( ) 0 * g1 X = ) * X 是极小点,则 ( ) * g1 X 必与 ( ) * f X 在一条直线上 且方向相反,这说明在上述条件下存在实数 1  0 使 ( ) ( 0 0 * 1 1 * f X −  g X = 若 有 m 个 起 作 用 约 束 , ( ), ( ),..., ( ) * * 2 * g1 X g X gn X 线性无关 , 即存在 1  0,..., m  0,使 =  −  = m i f X i gi X 1 * * ( )  ( ) 0 为了把不起作用的约束也包括在上式中,增加条件     = = 0( 1,2,..., ) ( ) 0 * i m g X i i i   我们用    −   ( ) 0 ( ) 0 h x h x j j 代替约束条件 hj (x) = 0 这样可得如下条件           = =  − = = 0,( 1,2,..., ) ( ) 0 ( ) ( ) 0 * 1 * * u j p u h X f X u h X j j j p j j j 这样,设 * X 是(4.1)式极小点,而且 * X 点的所有起作用约束的梯度 hj (X ), j 1,2,..., p *  = 和 gi (X ),i 1,2,...,m *  = 线性无关,则存在 T m ( , ,..., ) * * 2 * 1 *  =    及 T U u u up ( , ,..., ) * * 2 * 1 * = ,使 下述条件成立

V(x)-∑g(X)-2h(x)=0 1g1(X)=0 (4.3) λ1≥0, 条件(43)叫库恩-塔克条件(最优性条件),满足条件的点叫库恩-塔克点 条件中的2,22”…m,21,2…,n称为广义 Lagrange乘子 根据定理42,满足库恩塔克条件是点X成为最优点的必要条件,这比无条件极值问题中 使目标函数的偏导数为零的点不一定是目标函数的极值点一样,单如假定了凸性则可保证最 优点了(定理43) 20用库恩-塔克条件解非线性规划 min f(x=(x-3) 0≤x≤5 (答案:由于该非线性规划为凸规划,故X=3为K-T点,是全局极小点是可行域的内 点其目标函数值f(x)=0此题比书例42少约束条件h,(x)=0,解K-T点及判断最优 化较简单) 复习思考题 21叙述用线性規划逼近非线性规划的基本思想,及为了克服可行域无阶或近似解不可行时, 应加进对变量变化范围的限制,即MAP法(此法适于求解变量及约束条件比较多的问题,单 只有少量的约束是非线性的规划问题) 22将教材例44用MAP法重做一遍求解下述非线性规划问题 mn f(x)=x,+x2 st.g(x)=1xx2-x2≥0设初始点X=(0,1) 解先将约束函数g(x)在X点线性化 g(X0)+(x-x°)yVg(x)=(-03-1)+(=2x1-2Xx) 得线性规划问题 f(x)=x St +2≥0

16           = =  − − = = = i m g X f X g X u h X i i i m i p j i i j j 0, 1,2,..., ( ) 0 ( ) ( ) ( ) 0 * * 1 1 * * * * *    (4.3) 条件(4.3)叫库恩-塔克条件(最优性条件),满足条件的点叫库恩-塔克点, 条件中的 * * 2 * 1 * * 2 * 1 , ,..., , , ,...,   m u u up 称为广义 Lagrange 乘子. 根据定理 4.2,满足库恩-塔克条件是点 * X 成为最优点的必要条件,这比无条件极值问题中 使目标函数的偏导数为零的点不一定是目标函数的极值点一样,单如假定了凸性,则可保证最 优点了(定理 4.3). 20.用库恩-塔克条件解非线性规划 2 min f (x) = (x − 3) 0  x  5 (答案:由于该非线性规划为凸规划,故 3 * X = 为 K − T 点,是全局极小点,是可行域的内 点,其目标函数值 ( ) 0 * f X = .此题比书例 4.2 少约束条件 h (x) = 0, j 解 K − T 点及判断最优 化较简单.) 复习思考题: 21.叙述用线性规划逼近非线性规划的基本思想,及为了克服可行域无阶或近似解不可行时, 应加进对变量变化范围的限制,即 MAP 法.(此法适于求解变量及约束条件比较多的问题,单 只有少量的约束是非线性的规划问题.) 22.将教材例 4.4 用 MAP 法重做一遍.求解下述非线性规划问题 1 2 min f (x) = x + x s.t. g(x)=1-x 0 2 2 2 x1 − x  设初始点 T X (0,1) * = 解 先将约束函数 g(x) 在 * X 点线性化. ( ) ( ) ( ) (1 0 1 ) ( 2 2 ) 1 2 (0) (0) (0) 2 2 g X x x g X X X T + −  = − − + − − 1 0 2 1 = = x x =0+ (0, 2) 2( 1) 2 2 1 2 2 2 1 − − − = − +         − x x x x 得线性规划问题 1 2 min f (x) = x + x s.t. − 2x2 + 2  0

此可行域无阶.给定上问题的一个可行点X)=(00.7)步长界限 0=07,6=2×07=14精度要求E1=E,=0.02 经单纯行法第一次迭代得下线性规划问题为 f(x)=x1+x2 0.7≤x1≤0.7 x-0≤=07 14≤x,-0.7≤14 2-07≤09=14(附加条件 解得X=(-0.7,-0.7),g(X)=1-(-0.7)2-(-07)2=0.02>0 X是原问题的可行解,则令XD=X=(-0.7,-0.7) 用单纯行法经第二次迭代得线性规划问题为 f(x)=x1+x2 x1+14x2+1.98≥0 -0.7≤x1-0.7≤0.7 07≤ S. t 4≤x,+0.7≤1.4 x2+07 得X=(-14,-2 X对原问题不可行,缩小步长1/100,及令 "=-6(=0007 60=0.014 用单纯行法解下列线性规划问题 min f(x)=x,+x, 4x1+1.4x2+1.98≥0 0.007≤x1+0.7≤0.007 0014≤x2+0.7≤0.014 得X=(-0.7070.714)2,g(X)=1-(-0.70)2-(-0.714)2=-00096>-001,是原问 题的近似可行解,故令 (-0.707,-0.714) 经检验‖x2)-X0=0707+07-0714+0700157<002=6 √00072+0014=0004+000095=00157

17 此可行域无阶 . 给定上问题的一个可行点 T X (0,0.7) (0) = 步长界限 0.7, 2 0.7 1.4 (0) 2 (0)  1 =  =  = 精度要求  1 =  2 = 0.02 经单纯行法第一次迭代,得下线性规划问题为 1 2 min f (x) = x + x s.t.      −  −  −   − +  1.4 0.7 1.4 0.7 0.7 1.4 1.49 0 2 1 2 x x x 0.7 1.4 0 0.7 0 2 2 0 1 1 −  = −  =   x x (附加条件) 解得 T X = (−0.7,−0.7) , ( ) 1 ( 0.7) ( 0.7) 0.02 0 2 2 g X = − − − − =  X 是原问题的可行解,则令 T X X ( 0.7, 0.7) (1) = = − − 用单纯行法经第二次迭代,得线性规划问题为 1 2 min f (x) = x + x s.t.      −  +  −  −  + +  1.4 0.7 1.4 0.7 0.7 0.7 1.4 1.4 1.98 0 2 1 1 2 x x x x 0.7 1.4 0.7 0.7 2 1 +  +  x x 得 T X = (−1.4,−2.1) ( ) 1 ( 1.4) ( 2.1) 5.37 2 2 g X = − − − − = − X 对 原 问 题 不 可 行 , 缩 小 步 长 1/100, 及 令 0.014 100 1 0.007, 100 1 (0) 2 (1) 2 (0) 1 (1)  1 =  =  =  = 用单纯行法解下列线性规划问题: 1 2 min f (x) = x + x s.t.      −  +  −  +  + +  0.014 0.7 0.014 0.007 0.7 0.007 1.4 1.4 1.98 0 2 1 1 2 x x x x 得 ( 0.707, 0.714) , ( ) 1 ( 0.70) ( 0.714) 0.0096 0.01 2 2 X = − − g X = − − − − = −  − T , 是原问 题的近似可行解,故令 T X X ( 0.707, 0.714) (2) = = − − 经检验 2 (2) (1) X − X = − 0.707 + 0.7,−0.714 + 0.7  0.0157  0.02 =  0.007 0.014 0.00004 0.000195 0.0157 2 2 + = + =

故此问题的近似最优解是X'=X(2)=(-0.707,-0.714) 23用MAP法解求解教材例45 mn f(x)=-2x g1(x)=25-x2-x20 S. t g2(x)=7-x2+x2≥0 0≤x1≤5,0≤x2≤10 解设初始点X0=(2,2),则fx0)=-2×2-2=-6,取610=1.5.620=2 在X处将上非线性规划问题线性化Y=X-X(),X=Y+X() 令H=Y 1,2,,nH≥0,X≥0 y+=(yy…,y)-=(y,y2,yn) f((o)+(Y+) Vf(Xo))-(")'V(r(o) (-2)×2+(H1+,y2+)(-2,-1)-(H-,2)( 2X1+2X-Y2+Y2 g1(X)+(+)vg(X)-(Y)g1(X =25-2-2+(x,H2)y(-2x1-2x2)x2-(Y)(-2x1-2x2 =17-4X+4Y1-4X2-42≥0 g2(Xo)+(Y)vg2(X0)-(y)g2(x(0) 7-22+22+(+,2)(-44)-(F1,Y2)(-44) 7--4+4H+42-4H2≥0 0≤H+≤=150≤H≤=15 0≤H2≤2=2.50≤Y2≤2(<o20=2.5)(Y2=H2-2,X2≥0 Y2≥-2,Y2=Y-Y2故Y2≤2) 这样得

18 故此问题的近似最优解是 T X X ( 0.707, 0.714) * (2) = = − − 23.用 MAP 法解求解教材例 4.5 2 1 2 min f (x) = − x − x s.t.          = − +  = − −  0 5,0 10 ( ) 7 0 ( ) 25 0 1 2 2 2 2 2 1 2 2 2 1 1 x x g x x x g x x x 解 设初始点 T X (2,2) (0) = ,则 f( ) 2 2 2 6 (0) X = −  − = − ,取 1.5, 2.5 (0) 2 (0)  1 =  = 在 (0) X 处将上非线性规划问题线性化 ( ) ( ) , k k Y = X − X X = Y + X 令 Yi = Yi −Yi ,i = 1,2,...,n + −  0,  0 + − Yi Yi T n Y ( y , y ,..., y ) 1 2 + + + + = T n Y ( y , y ,..., y ) 1 2 − − − − = ( ) ( ) ( ) ( ) ( ) (0) (0) (0) f X Y f X Y f X T T +  −  + − = ( 2) 2 ( , ) ( 2, 1) ( , ) ( 2, 1) −  + 1 2 − − − 1 2 − − + + T − − T Y Y Y Y = − 2 1 + 2 1 − 2 + 2 − 6 + − + − Y Y Y Y ( ) ( ) ( ) ( ) ( ) (0) 1 (0) 1 (0) g1 X Y g X Y g X + T − T +  − = 2 1 2 2 2 1 2 1 2 2 2 2 2 1 2 1 25 2 2 ( , ) ( 2 , 2 ) ( ) ( 2 , 2 ) = = − = = + + − − + − − − − − x x T x x T Y Y x x Y x x =17 − 4 1 + 4 1 − 4 2 − 4 2  0 + − + − Y Y Y Y ( ) ( ) ( ) ( ) ( ) 2 (0) (0) 2 (0) g2 X Y g X Y g X + T − T +  − = 7 2 2 ( , ) ( 4,4) ( , ) ( 4,4) 1 2 1 2 2 2 − + + − − − + + T − − T Y Y Y Y = 7 − −4 1 + 4 1 + 4 2−4 2  0 + − + − Y Y Y Y 0 1.5 (0)  1  1 = + Y  0 1.5 (0)  1  1 = − Y  0 2.5 (0)  2  2 = + Y  0  2  2 − Y ( 2.5) (0)   2 = ( Y2 = X2 − 2, X2  0 + − 2  − 2 = 2 − 2 Y 2,Y Y Y 故 − Y2  2 ) 这样得