运筹学习题集

设有某物资要从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 , 缩短后的区间长度为