最优化理论复习题

最优化方法复习题一、填空题1、设DX，npR，若0，对),0(，都有向量Xp均在D内部，则称p为点X处的一个方向。2、函数是Matlab主要的求解0-1规划的函数。3、表上作业法是在求解运输问题时的一种简化方法，其实质是单纯形法。4、牛顿法的迭代公式为(1)()2()1()[()]()kkkkXXfXfX，而拟牛顿法的迭代公式为，其中kB是Hesse近似的正定对称阵。5、对于约束非线性规划问题一类重要的求解方法就是通过解一系列无约束非线性规划问题以获取原非线性约束问题解的方法，它包括外（二次）罚函数法和内（内点障碍）罚函数法。6、0-1背包问题用动态规划求解时，其体积的状态转移方程为1kkkkssax，质量的状态转移方程为。8、多目标规划问题(VP)的最优解一定是解，有效解一定是弱有效解，即。9、评价函数方法是处理多目标规划问题的主要方法之一，其基本思想是利用评价函数化多目标规划为规划。10、MATLAB用于求解多目标优化问题的函数有两个：和fgoalattain。11、设序列kx收敛于*x，若对于1p有(1)*()*lim,0kpkkxxxx则称迭代过程是收敛的。12、若存在与的一个邻域}|||||{)(**XXRXXNn（0为实数），使得对DXNX)(*都有)()(*XfXf，则称*X是非线性规划问题的最优解。13、设1:RRfn在点nRX*处二阶可导，若*()fX=且)(*2Xf正定，则*X是无约束非线性规划问题的严格局部最优解。14、Fibonacci法与0.618法的主要区别之一在于：搜索区间长度的缩短率不是采用0.618而是采用。15、内点障碍罚函数法（或内点法）只适用于只有约束而无等式约束的非线性规划问题。abpawpRRRDX**X16、动态规划是解决决策过程的一种有效方法。17、多目标规划问题(VP)的最优解一定是有效解，有效解一定是解。18、在动态规划的逆序解法中，如果选取求和型指标函数，则其基本方程为：11()(,)()kkkkkkkkufxoptvxufx，，(,1,,1)knn。19、评价函数方法是处理多目标规划问题的主要方法之一，其基本思想是利用评价函数化规划为单目标规划。20、写出用乘子法求解问题的221212min.20fxxxstxx的增广拉格朗日函数,,xM=。二、简答题1、阐述黄金分割法的基本思想2、写出下列问题的Matlab调用代码1312312323max3421..390,1,2,3jzxxxxxxxxstxxxj。（10分）3、确定线性规划min..0TcxstAxbx初始内点可行解的大M问题，并指出Maxxx与原线性规划问题的解的关系。4、请写出建立动态规划模型的步骤。5、阐述改进的内点法——原仿射尺度法的基本思想6、动态规划的顺序解法和逆序解法的主要区别见下表，请将其填写完整。不同点方法逆序解法顺序解法状态变量的含义不同决策过程不同kx第阶段状态转移方向不同指标函数的定义不同整体最优函数值不同7、用单纯形方法求解123123123123max101512539561515..250,1,2,3jzxxxxxxxxxstxxxxj8、请写出标准线性规划min..0TcxstAxbx的大M问题，并指出它的解Maxxx与原线性规划问题的解的关系。三、建模题1、某化工厂拟生产两种新产品A和B，其生产设备费用分别为3万元/吨和7万元/吨。这两种产品均将造成环境污染，设由公害所造成的损失可折算为A为4万元/吨，B为1万元/吨。由于条件限制，工厂生产产品A和B的最大生产能力各为每月5吨和6吨，而市场需要这两种产品的总量每月不少于7吨。试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达最小。2、一个旅行者要在背包里装一些最有用的旅行物品。背包容积为a，携带物品总重量最多为b。现有物品m种，第i种物品体积为ai，重量为bi（i=1,2,…,m）。为了比较物品的有用程度，假设第i种物品的价值为ci（i=1,2,…,m）。若每件物品只能整件携带，每件物品都能放入背包中，并且不考虑物品放入背包后相互的间隙。问旅行者应当携带哪几件物品，才能使携带物品的总价值最大、总重量最轻？试建立问题的数学模型，并写出其用函数“fminimax”的Matlab代码。四、计算题k()kkfx1、用两阶段法求解线性规划问题：1212121212max433936..23,0zxxxxxxstxxxx的第一阶段的线性规划问题，并指出其最优解对应的基变量是否可作为第二阶段的初始基变量？2、用乘子法求解问题：22121211max26..1fxxxstxx3、用最速下降法求解问题2212122min44412fxxxxxx，要求选取初始点(0)60.5,101x。4、用大M法求解线性规划问题：12312312123max32231..238,,0zxxxxxxstxxxxx。5、用内罚函数法求解：。解：将原问题化为标准型为：22122min12.10fxxxstx222122,(1)2min0,1PxMxxMx221222221222(1)2,10,(1)21,10xxxPxMxxMxx22122min12.10fxxxstx即于是令于是当时，，故6、用FR共轭梯度法求解问题22121min2fxxx，要求选取初始点(0)64,104x。112(1)Pxx2222224,1421,1xxPxMxxx021xPxP1212MxMxMMM121,1xMxM**1,,21xMxPxMfx