下载文档原格式
1. 假设有一百万元可以投资到三支股票上，设随机变量iR 表示投资到股票i 上的一元钱每年能够带来的收益。
通过对历史数据分析，知期望收益1()0.09E R =，2()0.07E R =，3()0.06E R =，三支股票的协方差矩阵为0.200.030.040.030.200.050.040.050.15⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦。
假设使用股票涨跌稳定性来评测风险，试构建优化模型，在保证期望年收益率不低于0.075的情况下，风险最小，同时表示为非线性优化的向量形式。
解：设123(,,)T X x x x =，其中123,,x x x 分别表示投资组合中123,,R R R 的所占的比例，有1231x x x ++= ……①保证期望收益率不低于0.075：112233()()()0.075x E R x E R x E R ++≥ ……②建立如下优化模型：222123121323min ()0.200.200.150.060.080.10f X x x x x x x x x x =+++++ ..s t 1231x x x ++=1230.090.070.060.075x x x ++≥123,,0x x x ≥记：0.200.030.040.030.200.050.040.050.15A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦表示成向量形式：min ()T f X X AX =..s t 1111T X ⎛⎫⎪= ⎪ ⎪⎝⎭0.090.070.0750.06T X ⎛⎫ ⎪≥ ⎪ ⎪⎝⎭123,,0x x x ≥2. 用伪算法语言描述“成功-失败”搜索方法。
解：1s ：初始化：0x , h,ε>02s ：x=0x ；1f =f(x) 3s ：2f =f(x+h)4s ： if 2f <1f go to 5s ;elsego to 6s ; end5s : x=x+h;2f =1f ;h=2h6s : if ||h ε<go to 7s ; else go to 8s ; end7s : x x *=8s : 4h h =-; go to 3s . □3. 请简述黄金分割法的基本思想，并尝试导出区间收缩比率φ≈0.618.基本思想：黄金分割法就是用不变的区间缩短率ϕ，来代替Fibonacci 法每次不同的缩短率，因而可以看成是Fibonacci 法的近似。
《运筹学》试题及参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。
2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。
3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。
4、在图论中，称无圈的连通图为树。
5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。
二、（每小题5分，共10分）用图解法求解下列线性规划问题：1）max z =6x 1+4x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ，解：此题在“《运筹学》复习参考资料.doc ”中已有，不再重复。
2）min z =－3x 1+2x 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-≤-≤+-≤+0,137210422422121212121x x x x x x x x x x 解：可行解域为abcda ，最优解为b 点。
⑴⑵⑶⑷⑸⑹、⑺由方程组⎩⎨⎧==+02242221x x x 解出x 1=11，x 2=0∴X *=⎪⎪⎭⎫⎝⎛21x x =（11，0）T∴min z =－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A 、B 、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：AB C 甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。
（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x 1、x 2，则x 1、x 2≥0，设z 是产品售后的总利润，则max z =70x 1+120x 2s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0300103200643604921212121x x x x x x x x ，2）用单纯形法求最优解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：max z =70x 1+120x 2+0x 3+0x 4+0x 5s.t.⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++5,...,2,1,03001032006436049521421321j x x x x x x x x x x j 列表计算如下：四、（10分）用大M 法或对偶单纯形法求解如下线性规划模型：min z =5x 1＋2x 2＋4x 3⎪⎩⎪⎨⎧≥≥++≥++0,,10536423321321321x x x x x x x x x 解：用大M 法，先化为等效的标准模型：max z /=－5x 1－2x 2－4x 3s.t.⎪⎩⎪⎨⎧=≥=-++=-++5,...,2,1,010********214321j y x x x x x x x x j增加人工变量x 6、x 7，得到：max z /=－5x 1－2x 2－4x 3－M x 6－M x 7s.t⎪⎩⎪⎨⎧=≥=+-++=+-++7,...,2,1,010*********2164321j x x x x x x x x x x x j大M 法单纯形表求解过程如下：五、（15分）给定下列运输问题：（表中数据为产地A i 到销地B j 的单位运费）B 1B 2B 3B 4s iA 1A 2A 312348765910119108015d j82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。
《高级运筹学》试题一、模型应用分析1、线性规划模型与解（要求：1）建立问题的线性规划模型，使用运筹学软件进行求解；2）写出问题的最优解及目标函数的最优值；3）针对求解结果进行分析：各价值系数的范围、各个资源数量的变化范围；4）哪些资源是紧缺资源？应采取哪些措施或对策进行改进？5）任意完成2题，多选无效。
）1）某公司已开发一种新型洗衣皂，广告部门正在制订宣传计划，决定使用电视、无线电广播和直接邮寄广告单等三种宣传手段。
广告费分别是：电视节目2600元，无线电节目1000元，直接邮寄广告单1500元。
可采用的各种方法的套数为：电视节目不超过12套，无线电节目不超过40套，直接邮寄不超过25套；并且无线电至少要9套，直接邮寄广告单至少要5套。
每套广告宣传手段的有效覆盖量取决于该广告所达到的地区，这里先考虑两个区：一区内电视节目、无线电节目和直接邮寄广告单的有效覆盖量分别被限制为7万、10万和7.5万人；二区内的有效覆盖量大大增加，相应为65万、30万和45万人。
三种宣传手段相应每套广告对未婚人的覆盖量是10万、8万和9.5万人；每套广告对已婚人的覆盖量是40万、50万和25万人。
公司要求：从事广告活动的开支不得超过60000元。
一区覆盖量至少要达到250万人，二区覆盖量至少达到1000万人。
在未婚人中的覆盖量不超过350万人，已婚人中覆盖量至少为280万人。
试确定要作广告手段的最佳套数，以获得最大有效覆盖量。
2）某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。
已知各种牌号糖果中A，B，C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价见表2所示。
问该厂每月生产这三种牌号糖果各多少kg，使该厂获利最大？3）某构件厂生产甲、乙两种商品混凝土拌合料，该厂每小时可以生产甲种混凝土拌合料14车，或生产乙种混凝土拌合料7车。
由于运输条件的限制，每小时可运输甲种混凝土拌合料7车，或运输乙种混凝土拌合料12车。
判断题判断正误，如果错误请更正第二章线形规划的对偶理论1.原问题第i个约束是<=约束,则对偶变量yi>=0.2.互为对偶问题,或则同时都有最优解,或则同时都无最优解.3.原问题有多重解,对偶问题也有多重解.4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.5.原问题无最优解,则对偶问题无可行解.6.设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝和｛maxw=Yb｜YA<=C,Y>=0｝的可行解,则有(1)CX<=Yb;(2)CX是w的上界;(3)当X,Y为最优解,CX=Yb;(4)当CX=Yb 时,有YXs+YsX=0;(5)X为最优解且B是最优基时,则Y=CB-1是最优解;(6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优解.7.原问题与对偶问题都可行,则都有最优解.8.原问题具有无界解,则对偶问题可行.9.若X,Y是原问题与对偶问题的最优解.则X=Y.10.若某种资源影子价格为0,则该资源一定有剩余.11影子价格就是资源的价格.12.原问题可行对偶问题不可行,可用对偶单纯形法计算.13.对偶单纯形法比值失效说明原问题具有无界解.14.对偶单纯形法是直接解对偶问题的一种解法.15.减少一个约束,目标值不会比原来变差.16.增加一个约束,目标值不会比原来变好.17增加一个变量, 目标值不会比原来变差.18.减少一个非基变量, 目标值不变.19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。
选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第二章线性规划的对偶理论1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同B目标函数相同 C最优目标函数值相同 D以上结论都不对2.对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题保持可行C逐步消除原问题不可行性 D逐步消除对偶问题不可行性3.互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相同 B原问题无可行解，则对偶问题也无可行解 C对偶问题无可行解，原问题可能无可行解 D一个问题无界，则另一个问题无可行解 E一个问题无可行解，则另一个问题具有无界解4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为 A—（λ1，λ2，……λn） B （λ1，λ2，……λn） C —（λn+1,λn+2,……λn+m）D（λn+1,λn+2,……λn+m）5.原问题与对偶问题都有可行解，则 A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解 C可能一个问题有最优解，另一个问题具有无界解D 原问题与对偶问题都有最优解计算题线性规划问题和对偶问题对于如下的线性规划问题min z = 3x1 + 2x2+x3. x1 + x2+ x3 ≤ 15 (1)2x1 - x2+ x3≥ 9 (2)-x1 + 2x2+2x3≤ 8 (3)x1 x2x3 ≥ 01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3. y1 + 2y2- y3 ≤ 3 (1)y1 - y2+ 2y3≤ 2 (2)y1 + y2+ 2y3≤ 1 (3)y1≤0、 y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3. x1 + x2+ x3+ x4= 15 (1)-2x1 + x2- x3+ x5= -9 (2)-x1 + 2x2+2x3+x6= 8 (3)x1 x2x3x4x5x6 ≥ 0原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11对于以下线性规划问题max z = -x1 - 2x2. -2x1 + 3x2≤ 12 (1)-3x1 + x2≤ 6 (2)x1 + 3x2≥ 3 (3)x1≤ 0， x2≥ 01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。
五邑大学 试 卷学期： 2014 至 2015 学年度 第 1 学期 课程：高级运筹学 任课教师（命题人）： 使用班级： 经管研2014 姓名： 学号： 2111401002一、构建下述问题的线性规划数学模型并用系统软件求解（10分）生产需要2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。
说明利用的是什么软件，求解的结果和重要的截图。
解：分析可得，每一根原材料的下料方案有如下几种：87654321x x x x x x x x 、、、、、、、根，所需要的原材料的总根数为z 根.数学模型如下：目标函数为：87654321min x x x x x x x x Z +++++++=10024321≥+++x x x x10023276532≥++++x x x x x 1004323876431≥+++++x x x x x x087654321≥x x x x x x x x 、、、、、、、且为整数这是一个线性规划问题，我用的软件lingo 来解这道题，以下就是我用软件解这道题的重要步骤：1、打开lingo 软件2、输入上述线性规划模型3、运行软件，结果如下由软件的运行结果可知，最优解如下，耗费原材料90根，其中按方案一下料的原材料为40根，按方案二下料的原材料为20根，按方案六下料的原材料为30根。
二、用图解法求解下述线性规划问题（5分）2153max x x Z +=123221≤+x x204521≤+x x321≥+x x0,021≥≥x x解：由题意可得，以21x x 、为坐标轴建立直角坐标系（1）根据约束条件画出与约束条件相应方程的直线，由这些直线共同确定出一个 区域，即可行解的区域可行区域如下图所示：为纵轴为横轴，21x x其中，01232:121=-+x x Y Y2：0204521=-+x x Y3：0321=-+x x其中阴影部分的每一个点都是这个线性规划问题的解。
运筹学试卷及参考答案运筹学试卷一、选择题（每小题2分，共20分）1、下列哪个不是线性规划的标准形式？（） A. min z = 3x1 + 2x2B. max z = -4x1 - 3x2C. s.t. 2x1 - x2 <= 1D. s.t. x1 + x2 >= 0答案：C2、以下哪个是最小生成树的Prim算法？（） A. 按照权值从小到大的顺序选择顶点 B. 按照权值从大到小的顺序选择顶点 C. 按照距离从小到大的顺序选择顶点 D. 按照距离从大到小的顺序选择顶点答案：B3、下列哪个不是网络流模型的典型应用？（） A. 道路交通流量优化 B. 人员部署 C. 最短路径问题 D. 生产计划答案：C4、下列哪个是最小化问题中常用的动态规划解法？（） A. 自顶向下的递推求解 B. 自底向上的递推求解 C. 分治算法 D. 回溯法答案：A5、下列哪个是最大流问题的 Ford-Fulkerson 算法？（） A. 增广路径的寻找采用深度优先搜索 B. 增广路径的寻找采用广度优先搜索 C. 初始流采用最大边的二分法求解 D. 初始流采用最小边的二分法求解答案：B二、简答题（每小题10分，共40分）1、请简述运筹学在现实生活中的应用。
答案：运筹学在现实生活中的应用非常广泛。
例如，线性规划可以用于生产计划、货物运输和资源配置等问题；网络流模型可以用于解决道路交通流量优化、人员部署和生产计划等问题；动态规划可以用于解决最短路径、货物存储和序列安排等问题；图论模型可以用于解决最大流、最短路径和最小生成树等问题。
此外，运筹学还可以用于医疗资源管理、金融风险管理、军事战略规划等领域。
总之，运筹学的理论和方法可以帮助人们更好地解决实际生活中的问题，提高决策的效率和准确性。
2、请简述单纯形法求解线性规划的过程。
答案：单纯形法是一种求解线性规划问题的常用方法。
它通过不断迭代和修改可行解，最终找到最优解。
具体步骤如下： (1) 将线性规划问题转化为标准形式； (2) 根据标准形式构造初始可行基，通常选取一个非基变量，使其取值为零，其余非基变量的取值均为零； (3) 根据目标函数的系数，计算出目标函数值； (4) 通过比较目标函数值和已选取的非基变量的取值，选取最优的非基变量进行迭代； (5) 在迭代过程中，不断修正基变量和非基变量的取值，直到找到最优解或确定无解为止。
一、填空题：（每空格2分，共16分）1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。
2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。
3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X1≤1 和 X1≥2 。
5、在用逆向解法求动态规划时，f k (s k )的含义是： 从第k 个阶段到第n 个阶段的最优解 。
6. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D 和B 的关系为 D 包含 B7. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约问：（1）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛---1003/20.3/1312(2)对偶问题的最优解： Y ＝（5，0，23，0，0）T8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________； 10. 若整数规划的松驰问题的最优解不符合整数要求，假设X i =b i 不符合整数要求，INT （b i ）是不超过b i 的最大整数，则构造两个约束条件：Xi ≥INT （b i ）＋1 和 Xi ≤INT （b i ） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。
11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛611401102二、计算题（60分）1、 已知线性规划（20分） MaxZ=3X 1+4X 2 X 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤8 X 1,X 2≥02） 若C 2从4变成5，最优解是否会发生改变，为什么？3） 若b 2的量从12上升到15，最优解是否会发生变化，为什么？4） 如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产？为什么？ 解：1)对偶问题为Minw=5y1+12y2+8y3y1+2y2+3y3≥3 y1+4y2+2y3≥4 y1,y2≥02)当C 2从4变成5时， σ4=-9/8 σ5=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。
运筹学考研真题及答案运筹学考研真题及答案一、选择题1. 在线性规划中，若最优化问题的对偶问题有最优解，则原始问题也有最优解。
（正确）解析：线性规划理论中对偶定理：“若原始问题的对偶问题有可行解，且存在最优解，则原始问题也有最优解。
”2. 若在线性规划的单纯形法中，某一回路上的所有非基变量（非基变量为0）均为0，则这一问题无有限最优解。
（错误）解析：所有非基变量为0时，相应的基变量可以任意非负，问题有无穷多最优解。
3. 在线性规划中，若某元组在原始问题和对偶问题下都是可行解，则该元组是原始问题和对偶问题的最优解。
（错误）解析：若某元组在原始问题和对偶问题下都是可行解，则该元组满足原始问题的可行性和对偶问题的可行性，但并不一定是最优解。
4. 线性规划的最优性条件是原始问题的可行解和对偶问题的可行解所对应的目标函数值相等。
（正确）解析：线性规划理论中最优性条件：“若原始问题的可行解与对偶问题的可行解所对应的目标函数值相等，则解是原始问题和对偶问题的最优解。
”5. 线性规划的可行性要求约束条件为不等式约束。
（错误）解析：线性规划的可行性要求是所有约束条件都满足，包括等式约束和不等式约束。
二、填空题1. 与线性规划的相对论证法相对应的是（单纯形法）。
解析：线性规划的相对论证法和单纯形法是互为相对的两种求解方法。
2. 在线性规划中，若最优差异为0，则最优解是（非唯一）。
解析：最优差异为0意味着最优解是非唯一的，有多个最优解。
3. 线性规划的最优性条件是（对偶定理）与最优条件相对应。
解析：线性规划的最优性条件是对偶定理，而最优条件是原始问题的可行解和对偶问题可行解所对应的目标函数值相等。
4. 在线性规划中，若一个可行解在原始问题和对偶问题下都是最优解，则称为（互补性）条件。
解析：若一个可行解在原始问题和对偶问题下都是最优解，则满足互补性条件。
三、应用题1.某公司生产两种产品A和B，每个产品的制造工序及所需时间如下表，在一天内，公司有8小时的工时可用，每个工序只能由一名员工负责完成。
1. 假设有一百万元可以投资到三支股票上，设随机变量iR 表示投资到股票i 上的一元钱每年能够带来的收益。
通过对历史数据分析，知期望收益1()0.09E R =，2()0.07E R =，3()0.06E R =，三支股票的协方差矩阵为0.200.030.040.030.200.050.040.050.15⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦。
假设使用股票涨跌稳定性来评测风险，试构建优化模型，在保证期望年收益率不低于0.075的情况下，风险最小，同时表示为非线性优化的向量形式。
解：设123(,,)T X x x x =，其中123,,x x x 分别表示投资组合中123,,R R R 的所占的比例，有1231x x x ++= ……①保证期望收益率不低于0.075：112233()()()0.075x E R x E R x E R ++≥ ……②建立如下优化模型：222123121323min ()0.200.200.150.060.080.10f X x x x x x x x x x =+++++ ..s t 1231x x x ++=1230.090.070.060.075x x x ++≥123,,0x x x ≥记：0.200.030.040.030.200.050.040.050.15A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦表示成向量形式：min ()T f X X AX =..s t 1111T X ⎛⎫⎪= ⎪ ⎪⎝⎭0.090.070.0750.06T X ⎛⎫ ⎪≥ ⎪ ⎪⎝⎭123,,0x x x ≥2. 用伪算法语言描述“成功-失败”搜索方法。
解：1s ：初始化：0x , h,ε>02s ：x=0x ；1f =f(x) 3s ：2f =f(x+h)4s ： if 2f <1f go to 5s ;elsego to 6s ; end5s : x=x+h;2f =1f ;h=2h6s : if ||h ε<go to 7s ; else go to 8s ; end7s : x x *=8s : 4h h =-; go to 3s . □3. 请简述黄金分割法的基本思想，并尝试导出区间收缩比率φ≈0.618.基本思想：黄金分割法就是用不变的区间缩短率ϕ，来代替Fibonacci 法每次不同的缩短率，因而可以看成是Fibonacci 法的近似。
在搜索区间[a,b]内取两点x<y ，然后在x,y 中选取一个作为端点，将搜索区间缩小，直至搜索区间足够小，然后在其内取一点作为最优解的近似。
一维搜索时，在区间内取两对称点1λ，'1λ作为搜多点，并满足：1λ= a+(1-ϕ)(b-a) '1λ= a+ϕ(b-a)ϕ取近似值0.618证明：设在第k 次迭代时的搜索区间为[k a ,k b ]，则在区间内取两对称点1k λ+，'1k λ+作为探索点，并满足：1(1)()k k k k a b a λϕ+=+-- ……① '1()k k k k a b a λϕ+=+- ……②由于对称性，即： '11k k k k a b λλ++-=-在第k+1次迭代中，不妨取收缩区间为'1,k k a λ+⎡⎤⎣⎦ 这样，收缩率ρ表示为：'1()0.618k kk k k kk ka b a b a b a λϕρϕ+--====≈-- □ 4. 请简述牛顿（Newton ）法的基本原理，并指出可能会出现的“坏现象”。
基本思想：牛顿法是二阶近似仿照切线法思想，推导出下降方向 11()()k k k k X X H X f X +-=-∇每次计算 1()()k k k D H X f X -=∇，可看成是椭球范数||||k D 下的最速下降法。
对于正定二次函数，一次可达最优解。
一定条件下，具有二阶收敛速度。
坏现象：对初始点的依赖性很大，要求初始点接近极小点。
若初始点远离极小点，不能保证收敛，甚至连Newton 方向2()1()()()k k f x f x --∇∇都不一定是下降方向，导致算法达不到极小点。
□ 5. 叙述Powell 算法思想.（方向加速法）算法思想：又称方向加速法。
是在研究正定二次函数的极小化问题时形成的，由于迭代过程中构造一组共个方向，其本质属于共轭方向法。
每一轮迭代过程中由n+1个相继的一维搜索组成，先依次沿着n 个已知的线性无关方向搜索，然后沿本轮迭代的初始点和第n 次搜索所得点的连线方向搜索，得到这一轮迭代的最好点并作为下一阶段的起点，再用第n+1个方向（最后的搜索方向）代替前n 个方向的一个，开始下一轮的迭代。
□ 6. 简述有约束优化时既约梯度法的基本思想。
基本思想：将线性规划的单纯形法推广到带线性约束的非线性问题上。
把线性约束优化问题min ()f XX=b..0A s t X ⎧⎨≥⎩ 简化为仅在非负限制下的极小化问题min ()N F X11X =B 0..0B N N b B NX s t X --⎧-≥⎪⎨≥⎪⎩其中，(,)A B N =，B N X X X ⎡⎤=⎢⎥⎣⎦，B 为m ×m 的可逆矩阵，B X 为m 维的基向量，N X 为n-m 维的非基向量。
求出目标函数()N F X 的梯度，此时的梯度是n-m 维函数的梯度，称为()f X 的既约梯度1()()[(),]()[(),]N B T N N X B N N X B N N r X F X f X X X B N f X X X -=∇=∇-∇。
N X 沿负既约梯度方向()N r X -移动，可使目标函数值降低。
□7. 利用罚函数法求解非线性规划的收敛点12211221min ()()0.. ()0f X x xg X x x s t g X x =+⎧=-+≥⎨=≥⎩ 分别假设初始可行点满足1)12()0,()0g X g X <<； 2) 12()0,()0g X g X <>.解：马良书69页8. 设()(1,2,)j g X j l -=为凸函数，则{|()0,1,2,}j R X g X j l =≥=为凸集。
证明：设 (), 0,1x y R α∈∈，，有()()00j j g x g y ≥≥，， 1,2,,j l =()(1,2,)j g X j l -=为凸函数，则有()()11[()]()j j j g x y g x g y αααα+-≤----，1,2,,j l =两边变号()()[()]11()0j j j g x y g x g y αααα-≥+-≥+, 1,2,,j l =即1()x y R αα+-∈。
R 为凸集□ 9. 设2,1,2,k k x k -==，则{}k x 收敛阶数为1，且线性收敛。
证明：显然，0X *=。
由于(1)(1)()00||||21lim lim ||||22k k k k k k X X X X +*-+*-→→-==- 所以由收敛定义和α阶收敛知，{}k x 收敛阶数为α=1，且β=1/2知为线性收敛。
□10. 设1()2TT f X X AX b X c =++，A 是对称矩阵。
给定初始点0X ，试证明由最速下降法产生的迭代点列{}k X 有如下公式：1()()k T k k kkk T kg g XX g g Ag +=-，0,1,2,3,k =其中k k g AX b =+。
证明：由数学分析知，在k X 的领域中，使()f X 下降最快的方向是负梯度方向，取()()K k P f X =-∇ ……①下面确定步长k λ：由于()f X 为二次函数，故二阶连续可导，作二阶Taylor 展开：()()()()1()()()()()()2k k k k T k k T k f X P f X f X P P A P λλλλ+≈+∇+令()()()()()0k T k k T k dff X P P AP d λλ≈∇+= 可得最优步长为()()()()()k T k k k T k f X P P APλ∇=- ……②记()k k k g f X AX b =∇=+ 则1()()()k T k k kkkkk k T kg g XX f X X g g Ag λ+=-∇=-， 0,1,2,3,k =□11. 试证在最速下降法中，相邻两次搜索方向必正交，即1()()0k Tk f Xf X +∇∇=证明：设第k 步的步长为k λ，梯度为k P ，则有第k+1步的梯度为(1)(1)k k P b AX ++=-()()()k k k b A X P λ=-+ ()()k k k b AX AP λ=--()()k k k P AP λ=-()2()()()()()()||||(,)()(,)k k k k k T k k k P P P P AP AP P λ==(1)()()()()()(,)(,)(,)0k k k k k k k P P P P AP P λ+∴=-=即1()()0k Tk f Xf X +∇∇=，两次搜索方向必正交。
□12. ()f x 在凸集R 内是凸函数的充要条件是对于任意的,x y R ∈，()[(1)]g f x y ααα=+-在[0,1]内是凸函数。
证明：必要性：设[0,1]αλβ∈，，，由于R 是凸集，所以对于任意的,x y R ∈，有(1)x y R αα+-∈，(1)x y R ββ+-∈[(1)]([(1)]{1[(1)]})g f x y λαλβλαλβλαλβ+-=+-+-+-[(1)][(1)(1)(1)(1)]([(1)](1)[(1)])f x x y y y y f x y x y f x y x y λαλβλαβλβλαλαλβλβλααλββ=+-+--+=+-+-+--=+-+-+- 由()f x 为R 上凸函数可知[(1)][(1)](1)[(1)]g f x y f x y λαλβλααλββ+-≤+-+-+-()(1)()g g λαλβ=+-所以，()[(1)]g f x y ααα=+-在[0,1]内是凸函数。
充分性：若对于任意的,x y R ∈，()[(1)]g f x y ααα=+-在[0,1]内是凸函数，则有[(1)]f x y αα+-=()[1(1)0]g g ααα=+-(1)(1)(0)g g αα≤+- ()(1)()f x f y αα=+-所以()f x 是凸函数。
□ 13. 考虑二次函数f(x)=x x x x x x 2122212132+-++1) 写出它的矩阵—向量形式: f(x)=x Qx b xTT +21 221()(1,1)262T f x X X X ⎛⎫=+- ⎪⎝⎭2) 矩阵Q 是不是奇异的?|Q|＝8≠0，非奇异 3) 证明: f(x)是正定的显然Q 正定，故f(x)正定 4) f(x)是凸的吗?由于f(x)正定，所以f(x)是凸的5) 写出f(x)在点x =T )1,2(处的支撑超平面(即切平面)方程()10f X =，22-15()26111f X X ⎛⎫⎛⎫⎛⎫∇=+= ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭切平面方程：()()()()T f X f X f X X X -=∇-即2211221223610110x x x x x x ++--+= □ 14. 设δ++=x r Gx x x f T T21)(是正定二次函数，证明一维问题 )()(min k k ad x f a +=ϕ的最优步长为.)(kTk kT k k Gdd dx f a ∇-=证明： 同（10）题15. 考虑约束优化问题()221212min 4..3413f x x x s t x x =++≥初始点(2,2)，用两种惩罚函数法求解. 解：标准化()2212min 4f x x x =+ 112..()34130s t g x x x =+-≥（1）外罚函数法构造罚函数2221212(,)4{min(0,3413)}P X M x x M x x =+++-当1()0g x <时，2221212(,)4(3413)P X M x x M x x =+++-112126(3413)0P x M x x x ∂=++-=∂， 212188(3413)0Px M x x x ∂=++-=∂ 解得：(3,1)M X =。
