工程硕士研究生《最优化方法》试卷

作用：①仿真的过程也是实验的过程，而且还是系统地收集和积累信息的过程。

尤其是对一些复杂的随机问题，应用仿真技术是提供所需信息的唯一令人满意的方法。

②仿真技术有可能对一些难以建立物理模型或数学模型的对象系统，通过仿真模型来顺利地解决预测、分析和评价等系统问题。

③通过系统仿真，可以把一个复杂的系统化降阶成若干子系统以便于分析，并能指出各子系统之间的各种逻辑关系。

④通过系统仿真，还能启发新的策略或新思想的产生，或能暴露出在系统中隐藏着的实质性问题。

同时，当有新的要素增加到系统中时，仿真可以预先指出系统状态中可能会出现的瓶颈现象或其它的问题。

2.简述两个Wardrop 均衡原理及其适用范围。

答：Wardrop提出的第一原理定义是：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。

在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个 OD对的各条被使用的径路具有相等而且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行驶时间。

Wardrop提出的第二原理是：系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。

第一原理对应的行为原则是网络出行者各自寻求最小的个人出行成本，而第二原理对应的行为原则是网络的总出行成本最小。

3.系统协调的特点。

答：（1）各子系统之间既涉及合作行为，又涉及到竞争行为。

（2）各子系统之间相互作用构成一个反馈控制系统，通过信息作为“中介”而构成整体（3）整体系统往往具有多个决策人，构成竞争决策模式。

（4）系统可能存在第三方介入进行协调的可能。

6．对已经建立了概念模型的系统处理方式及其特点、适用范围。

答：对系统概念模型有三种解决方式。

1.建立解析模型方式对简单系统问题，如物流系统库存、城市公交离线调度方案的确定、交通量不大的城市交叉口交通控制等问题，可以运用专业知识建立系统的量化模型（如解析数学模型），然后采用优化方法确定系统解决方案，以满足决策者决策的需要，有关该方面的内容见第四、五章。

《最优化方法》复习题
一、简述题
1、怎样判断一个函数是否为凸函数．
（例如：判断函数212
2
212151022)(x x x x x x x f-=是否为凸函数）2、写出几种迭代的收敛条件．
3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.
见书本61页(利用单纯形表求解);
69页例题(利用大M法求解、二阶段法求解);4、简述牛顿法和拟牛顿法的
优缺点．简述共轭梯度法的基本思想．
写出Goldstein、Wolfe非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式．
（1）0.618法的迭代公式：(1)(),
().k k k k k
k k k a b a a b aλτμτ＝--??=-?
（2）Fibonacci法的迭代公式：111(),(1,2,,1)()
n k k
k k k n k n k k k k k n k F a b a F k n F a b a Fλμ-----? =-??
=-?
?=-??
L．（3）Newton一维搜索法的迭代公式：1
1k k k。

硕士研究生最优化复习题硕士研究生最优化复习题1.线性规划问题CX z =min ,0,≥=X b AX 其可行域为R ，最优目标函数值为z ，若分别发生下列情形之一时，其新的可行域为R *，新的最优目标函数值为z *，试分别写出下列三个问题中R 与R *及z 与z *之间的关系：（1）增添一个新的约束条件。

（2）减少一个原有的约束条件。

（3）目标函数变为λCXz =min ，同时约束条件方程变为1,0,>≥=λλX b AX 。

2.线性规划问题CX z =min ，0,≥=X b AX ，设X （0）为问题的最优解，若目标函数中用C *代替C 后，问题的最优解变为X *，求证：(C *-C )(X *-X （0）)≤03.若线性规划问题min z =CX ,AX ＝b, X ≥0具有最优解，试应用对偶理论证明下述线性规划问题min z =CX ,AX ＝d, X ≥0不可能具有无界解，d 可以是取任意值的向量。

4.试将图所示的求v 1到v 7点的最短路问题归结为求整数规划问题（建立整数规划模型），具体说明模型中变量、目标函数和约束条件的含义。

v 2 1 v 539 2 2v 1 5 v 4 4 v 7 8 38 4v 3 v 65．已知线性规划问题min Z=2x 1-x 2 +2x 3≥≤≤-+=++无约束 3 213 213 21x ,0x 0,x 6x x x - 4x x x -k 其最优解为x 1 = -5, x 2 =0, x 3 =-1（1）求k 的值。

（2）写出并求其对偶问题的最优解。

6.某公司要建立一线性规划模型，此模型受约束条件1或约束条件2约束。

如果满足约束条件1，必须同时满足另外p 1个约束条件中的k 1个(k 1 < p 1)约束；如果满足约束条件2，必须同时满足另外p 2个约束条件中的k 2个(k 2 < p 2)约束；要求建立整数规划的约束条件，满足上述要求。

华东理工大学研究生《最优化方法》考试卷专业 ________ 班级 ________ 学号 ________ 姓名 ________ 成绩 ________2014年12月11日 一、简答题（40分，每小题4分）1．请写出最优化问题的一般模型形式。

2．试叙述局部最优解和全局最优解的定义。

3．请给出优化算法收敛速度的定义。

4．请给出优化算法的终止准则。

5．给出下降方向的定义和判别方法？ 6．简述下降迭代法的基本步骤。

7．何谓共轭方向？你知道由线性无关向量组构造共轭向量组的方法吗？ 8．最速下降法是最好的优化算法吗？为什么？ 9．何谓可行方向及如何判别？10．优化问题的最优解与可行下降方向有什么关系？二、（10分）试用最速下降法（梯度法）求解如下问题，初始点⎪⎪⎭⎫⎝⎛=110x ，只迭代一次，并判断迭代结果是否为最优解。

21222122)(min 2x x x x x f Rx -+=∈三、（10分）试叙述Powell 基本算法步骤或单纯形替换法的步骤，并简述其特点。

四、（10分）试用惩罚函数求解如下的优化问题8 ..)3()(min 2≥--=x t s x x f五、（10分）考虑下述线性规划问题1223 1832 ..233)(max 321321321321≥=++=+++-=x x x x x x x x x t s x x x x f ，，1．求出该问题的所有基本解，并指出哪些是基本可行解； 2．该问题是否有最优解？若有，请求出其最优解。

六、（10分）考虑问题010)3( 010)3( ..)(max 211323212≥≤---≤+-+=x x x x x x t s x x f ，1．写出上述问题的Kuhn —Tucker 条件。

2．这个问题的最优解满足Kuhn —Tucker 条件吗？为什么？七、（10分）已知某化工反应y 与因数x 和时间t 之间的依赖关系为xa t a ta x a y 43211+++=其中4321,,,a a a a 是待定参数，为确定这三个参数，实验测得有关y x t ,,的五组数据如下：1．试用最小二乘法建立确定参数4321,,,a a a a 的数学模型；2．对于列出的非线性最小二乘问题，你知道有哪些优化算法可求解该问题，并请给出求解该问题的修正Gauss-Newton 算法的迭代公式。

《最优化方法》1一、填空题：1．最优化问题的数学模型一般为：____________________________，其中___________称为目标函数，___________称为约束函数，可行域D 可以表示为_____________________________，若______________________________，称*x 为问题的局部最优解，若_____________________________________，称*x 为问题的全局最优解。

2．设f(x)= 212121522x x x x x +-+，则其梯度为___________，海色矩阵___________,令,)0,1(,)2,1(T T d x ==则f(x)在x 处沿方向d 的一阶方向导数为___________，几何意义为___________________________________,二阶方向导数为___________________，几何意义为____________________________________________________________。

3．设严格凸二次规划形式为：012..222)(min 2121212221≥≥≤+--+=x x x x t s x x x x x f则其对偶规划为___________________________________________。

24．求解无约束最优化问题：n R x x f ∈),(min ，设k x 是不满足最优性条件的第k 步迭代点，则：用最速下降法求解时，搜索方向k d =___________ 用Newton 法求解时，搜索方向k d =___________ 用共轭梯度法求解时，搜索方向k d =___________________________________________________________________________。

一、 填空题1.若()()⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫⎝⎛⎪⎪⎭⎫ ⎝⎛=212121312112)(x x x x x x x f ，则=∇)(x f ，=∇)(2x f .2.设f 连续可微且0)(≠∇x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。

3.向量T)3,2,1(关于3阶单位方阵的所有线性无关的共轭向量有 . 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算法： .6.以下约束优化问题：)(01)(..)(min 212121≥-==+-==x x x g x x x h t s x x f的K-K-T 条件为：. 7.以下约束优化问题：1..)(min 212221=++=x x t s x x x f的外点罚函数为（取罚参数为μ） .二、证明题（7分+8分）1.设1,2,1,:m i R R g n i =→和m m i R R h ni ,1,:1+=→都是线性函数，证明下面的约束问题：},,1{,0)(},1{,0)(..)(min 1112m m E j x h m I i x g t s x x f j i nk k+=∈==∈≥=∑=是凸规划问题。

2.设R R f →2:连续可微，n i R a ∈，R h i ∈，m i ,2,1=，考察如下的约束条件问题：},1{,0}2,1{,0..)(min 11m m E i b x a m I i b x a t s x f i T i i Ti +=∈=-=∈≥-设d 是问题1||||,0,0..)(min ≤∈=∈≥∇d E i d a Ii d a t s d x f Ti Ti T的解，求证：d 是f 在x 处的一个可行方向。

三、计算题（每小题12分）1.取初始点T x )1,1()0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题（迭代2步）：22212)(m in x x x f +=2.采用精确搜索的BFGS 算法求解下面的无约束问题：21222121)(min x x x x x f -+=3.用有效集法求解下面的二次规划问题：.0,001..42)(min 2121212221≥≥≥+----+=x x x x t s x x x x x f4.用可行方向算法（Zoutendijk 算法或Frank Wolfe 算法）求解下面的问题（初值设为)0,0()0(=x,计算到)2(x 即可)：.0,033..221)(min 21211222121≥≥≤+-+-=x x x x t s x x x x x x f参考答案一、填空题 1. ⎪⎪⎭⎫⎝⎛++++3421242121x x x x ⎪⎪⎭⎫⎝⎛4224 2. 0)(<∇d x f T3. T)0,1,2(-，T)1,0,3(-（答案不唯一）。

最优化方法试题及答案一、选择题1. 下列哪项不是最优化方法的特点？A. 目标性B. 可行性C. 多样性D. 随机性答案：D2. 在最优化问题中，约束条件的作用是什么？A. 限制解的可行性B. 增加问题的复杂性C. 提供额外的信息D. 以上都是答案：A3. 线性规划问题中，目标函数与约束条件之间的关系是什么？A. 无关B. 相等C. 线性D. 非线性答案：C二、简答题1. 简述最优化问题的基本构成要素。

答案：最优化问题的基本构成要素包括目标函数、决策变量、约束条件和解的可行性。

目标函数是衡量最优化问题解的质量的函数，决策变量是问题中需要确定的参数，约束条件是对决策变量的限制，解的可行性是指解必须满足所有约束条件。

2. 什么是局部最优解和全局最优解？请举例说明。

答案：局部最优解是指在问题的邻域内没有其他解比当前解更优的解，而全局最优解是指在整个解空间中最优的解。

例如，在山峰攀登问题中，局部最优解可能是到达了一个小山丘的顶部，而全局最优解是到达了最高峰的顶部。

三、计算题1. 假设一个农民有一块矩形土地，长为100米，宽为80米，他想在这块土地上建一个矩形的养鸡场，但只能沿着土地的长边布置。

如果养鸡场的一边必须靠在土地的长边上，另一边与土地的宽边平行，求养鸡场的最大面积。

答案：为了使养鸡场的面积最大，养鸡场的一边应该靠在土地的宽边上，另一边与土地的长边平行。

这样，养鸡场的长将是80米，宽将是100米，所以最大面积为80米 * 100米 = 8000平方米。

2. 一个工厂需要生产三种产品A、B和C，每种产品都需要使用机器X 和机器Y。

生产一个单位的产品A需要机器X工作2小时和机器Y工作1小时；产品B需要机器X工作3小时和机器Y工作2小时；产品C需要机器X工作1小时和机器Y工作3小时。

工厂每天有机器X总共300小时和机器Y总共200小时的使用时间。

如果工厂每天需要生产至少100单位的产品A，50单位的产品B和20单位的产品C，请问工厂应该如何安排生产以最大化产品的总产量？答案：设生产产品A的单位数为x，产品B的单位数为y，产品C的单位数为z。

《最优化方法》1一、填空题:1. _______________________________________________________ 最优化问题的数学模型一般为：_____________________________________________ ,其中___________ 称为目标函数，___________ 称为约束函数，可行域D可以表示为_______________________________ ，若 ________________________________ ，称/为问题的局部最优解，若为问题的全局最优解。

2.设f(x)= 2斤+2“2-兀|+5花，则其梯度为__________ ^x = (l,2)r?6/ = (l,0)r,则f(x)在壬处沿方向d的一阶方向导数为___________ ，几何意义为_____________________________________ ，二阶方向导数为____________________ ,几何意义为_____________________________3.设严格凸二次规划形式为：min /(%) = 2兀］2 + 2x； - 2兀］-x2s.t. 2%! 4- x2 < 1> 0x2 > 0则其对偶规划为_______________________________________________min%（d ） = f （x k +ad k ）的最优步长为务=—叫）F.d kT Gd k2. （10分）证明凸规划min/（x ）,x G D （其中子（兀）为严格凸函数，D 是凸集）的最优解是唯一的3. （13分）考虑不等式约束问题min /（x ）s.t. c i （x ） < 0, Z G / = {1,2,…，加}其中/（x ）,6 （兀）a e /）具有连续的偏导数，设X 是约束问题的可行点，若在元处 d 满足巧（计<0,VC,（元）（可则d 是元处的可行下降方向。