动态最优化第3、4、6章 习题

最优化复习题及答案一、选择题1. 最优化问题中，目标函数的值随着决策变量的变动而变动，我们称之为：A. 约束条件B. 可行域C. 目标函数D. 决策变量答案：C2. 在线性规划问题中，如果所有约束条件和目标函数都是线性的，则该问题被称为：A. 非线性规划B. 整数规划C. 线性规划D. 动态规划答案：C3. 以下哪个算法是用于求解无约束最优化问题的？A. 单纯形法B. 梯度下降法C. 拉格朗日乘子法D. 分支定界法答案：B二、填空题4. 在最优化问题中，满足所有约束条件的解称为________。

答案：可行解5. 当目标函数达到最大值或最小值时的可行解称为________。

答案：最优解6. 拉格朗日乘子法主要用于求解带有等式约束条件的________问题。

答案：最优化三、简答题7. 简述单纯形法的基本思想。

答案：单纯形法是一种用于求解线性规划问题的算法。

它通过在可行域的顶点之间移动，逐步逼近最优解。

在每一步中，选择一个进入基的变量，使得目标函数值增加最多，同时选择一个离开基的变量，使得目标函数值不降低。

通过这种方法，单纯形法能够找到线性规划问题的最优解。

8. 解释什么是局部最优解和全局最优解。

答案：局部最优解是指在目标函数的邻域内没有其他解比当前解更优的解。

而全局最优解是指在整个可行域内没有其他解比当前解更优的解。

局部最优解不一定是全局最优解，但全局最优解一定是局部最优解。

四、计算题9. 假设有一个生产问题，需要最小化成本函数 C(x, y) = 3x + 4y，其中 x 和 y 分别表示生产两种产品的产量，且满足以下约束条件： - 2x + y ≤ 12- x + 2y ≤ 18- x, y ≥ 0请求解该最优化问题。

答案：首先，我们可以画出约束条件所形成的可行域。

然后，检查可行域的顶点，这些顶点分别是 (0,0), (0,9), (6,0), (3,6)。

计算这些顶点处的成本函数值，我们得到：- C(0,0) = 0- C(0,9) = 36- C(6,0) = 18- C(3,6) = 30成本函数的最小值为 18，对应的最优解为 (x, y) = (6, 0)。

树形动态规划动态规划： 问题可以分解成若⼲相互联系的阶段，在每⼀个阶段都要做出决策，全部过程的决策是⼀个决策序列。

要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

动态规划就是解决多阶段决策最优化问题的⼀种思想⽅法。

阶段： 将所给问题的过程，按时间或空间（树归中是空间，即层数）特征分解成若⼲相互联系的阶段，以便按次序去求每阶段的解。

状态： 各阶段开始时的客观条件叫做状态。

决策： 当各段的状态取定以后，就可以做出不同的决定，从⽽确定下⼀阶段的状态，这种决定称为决策。

（即孩⼦节点和⽗亲节点的关系）策略： 由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

状态转移⽅程： 前⼀阶段的终点就是后⼀阶段的起点，前⼀阶段的决策选择导出了后⼀阶段的状态，这种关系描述了由k阶段到k+1阶段（在树中是孩⼦节点和⽗亲节点）状态的演变规律，称为状态转移⽅程。

⽬标函数与最优化概念： ⽬标函数是衡量多阶段决策过程优劣的准则。

最优化概念是在⼀定条件下找到⼀个途径，经过按题⽬具体性质所确定的运算以后，使全过程的总效益达到最优。

树的特点与性质：1、有n个点，n-1条边的⽆向图，任意两顶点间可达2、⽆向图中任意两个点间有且只有⼀条路3、⼀个点⾄多有⼀个前趋，但可以有多个后继4、⽆向图中没有环；拿到⼀道树规题，我们有以下3个步骤需要执⾏：1. 判断是否是⼀道树规题：即判断数据结构是否是⼀棵树，然后是否符合动态规划的要求。

如果是，那么执⾏以下步骤，如果不是，那么换台。

2. 建树：通过数据量和题⽬要求，选择合适的树的存储⽅式。

如果节点数⼩于5000，那么我们可以⽤邻接矩阵存储，如果更⼤可以⽤邻接表来存储(注意边要开到2*n，因为是双向的。

这是⾎与泪的教训)。

如果是⼆叉树或者是需要多叉转⼆叉，那么我们可以⽤两个⼀维数组brother[]，child[]来存储（这⼀点下⾯会仔细数的）。

3. 写出树规⽅程：通过观察孩⼦和⽗亲之间的关系建⽴⽅程。

动态规划练习题[题1] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。

现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。

顶行和底行的差值是2。

这个差值是两行点数之和的差的绝对值。

每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。

对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

输入格式：文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。

接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。

第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。

输出格式：只有一个整数在文件的第一行。

这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

[题2] Perform巡回演出题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入: 样例输出：3 6 4602 130 150 03 75 0 807 120 110 0 100 110 120 04 60 70 60 503 0 135 1402 70 802 32 0 701 800 0[题3] 复制书稿（BOOKS）问题描述：假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。

动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。

该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。

他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。

他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。

动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。

由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。

第一节动态规划的基本方法多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。

例1：最短路线问题某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？下面引进几个动态规划的基本概念和相关符号。

(1)阶段(Stage)把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。

如例l中 (最短路线问题)可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。

(2)状态(State)状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。

描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。

如例l中，第一阶段的状态为A（即出发位置）。

第二阶段有三个状态：B1 、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。

最优化理论试题及答案一、单项选择题1. 以下哪个函数是凸函数？A. f(x) = x^2B. f(x) = -x^2C. f(x) = x^3D. f(x) = e^x答案：A2. 线性规划问题的基本解是：A. 基本可行解B. 可行解C. 基本解D. 基本最优解答案：A3. 单纯形法中，如果目标函数的最优值是无界的，则对应的解是：A. 无解B. 可行解C. 基本可行解D. 基本最优解答案：A4. 在拉格朗日乘数法中，拉格朗日函数是：A. 目标函数和约束条件的乘积B. 目标函数和约束条件的和C. 目标函数和约束条件的差D. 目标函数和约束条件的商答案：B5. 以下哪个算法用于解决非线性规划问题？A. 单纯形法B. 内点法C. 匈牙利法D. 动态规划答案：B二、多项选择题1. 以下哪些条件是凸优化问题的必要条件？A. 目标函数是凸函数B. 所有约束条件是凸集C. 目标函数是凹函数D. 所有约束条件是凹集答案：A, B2. 在线性规划中，以下哪些是可行域的性质？A. 非空B. 凸集C. 闭集D. 有界答案：A, B, C3. 以下哪些方法可以用于解决整数规划问题？A. 分支定界法B. 割平面法C. 单纯形法D. 动态规划答案：A, B, D4. 以下哪些是拉格朗日乘数法的用途？A. 寻找局部最优解B. 寻找全局最优解C. 确定约束条件的活跃性D. 确定目标函数的梯度答案：A, C5. 以下哪些是动态规划的基本要素？A. 状态B. 决策C. 阶段D. 策略答案：A, B, C三、填空题1. 一个函数f(x)是凸函数，当且仅当对于任意的x1, x2和任意的λ∈[0,1]，有f(λx1 + (1-λ)x2) ≤ λf(x1) + (1-λ)f(x2)。

2. 线性规划问题的标准形式是：最大化或最小化目标函数z = c^T x，满足约束条件Ax ≤ b和x ≥ 0。

3. 单纯形法的基本思想是通过不断地从一个基本可行解移动到另一个基本可行解，直到找到最优解。

博弈论判断题第一章导论（1)单人博弈就是个人最优化决策，与典型的博弈问题有本质区别。

(2)博弈方的策略空问必须是数量空间，博弈的结果必须是数量或者能够数量化。

(3）囚徒的困境博弈中两个因徒之所以会处于困境，无法得到较理想的结果，是因为两囚徒都不在乎坐牢时间长短本身，只在乎不能比对方坐牢的时间更长.(4)因为零和博弈中博奔方之间的关系都是竞争性的、对立的，因此零和博弈就是非合作博弈。

（5）凡是博弈方的选择、行为有先后次序的一定是动态博弈。

(6)多人博弈中的“破坏者"会对所有博弈方的利益产生不利影响.（7）合作博弈就是博弈方采取相互合作态度的博弈。

参考答案：（1）正确。

因为单人博弈只有一个博弈方,因此不可能存在博弈方之间行为和利益的交互作用和制约．因此实际上就是个人最优化决策，与存在博弈方之间行为和利益交互作用和制约的典型博弈问题有本质的区别。

（2)前半句错误，后半句正确.博弈方的策略空间不一定是数量空间，因为博弈方的策略除了可以是数量水平（如产量、价格等）以外，也可以是各种定性的行为取舍和方向选择，甚至也可能是各种函数或者其他更复杂的内容。

但一个博弈的结果必须是数量或者可以数量化，因为博弈分析只能以数量关系的比较为基础.(3）错误.结论恰恰相反，也就是囚徒的困境博弈中两囚徒之所以处于困境,根源正是因为两囚徒很在乎坐牢的绝对时间长短.此外，我们一开始就假设两囚徒都是理性经济人，而理性经济人都是以自身的（绝对）利益，而不是相对利益为决策目标的。

（4）错误。

虽然零和博弈中博弈方的利益确实是对立的．但非合作博弈的含义并不是博弈力之间的关系是竞争性的、对立的,而是指博弈方是以个体理性、个体利益最大化为行为的逻辑和依据,是指博弈中不能包含有约束力的协议。

(5）错误。

其实并不是所有选择、行为有先后次序的博弈问题都是动态博弈.例如两个厂商先后确定自己的产量，但只要后确定产量的厂商在定产之前不知道另一厂商定的产量是多少，就是静态博弈问题而非动态博弈问题.（6)错误。

第一章 习题（补充）1、判断下列问题是线性优化问题还是非线性优化问题：)0(..)(min >=+=c cx x t s b x A x f TT，（R c b R A R x n n ∈∈∈,,,）；2、判断对错：若多元函数)(x f 在点n R x ∈关于x 的各个分量的偏导数都存在，那么函数)(x f 在x 处连续。

[解答]错误。

例如：二元函数⎪⎩⎪⎨⎧=+≠++==00,),(2221222122212121x x x x x x x x x x f z ，在点()0,0处的偏导数都为0，但是这个函数在点()0,0处并不连续。

3、判断对错，如果错误，请给出正确叙述：如果多元连续函数R R f n →:在nTn Rx x x x ∈=),,,(21 对于x的各个分量i x 的二阶偏导数n j n i x x x f ji ,,2,1,,,2,1,)(2==∂∂∂都存在，那么)(2x f ∇是一个对称矩阵。

[解答]错误。

正确的叙述为：如果多元连续函数R R f n →:在nTn Rx x x x ∈=),,,(21 对于x的各个分量i x 的二阶偏导数n j n i x x x f ji ,,2,1,,,2,1,)(2==∂∂∂都存在且连续，那么)(2x f ∇是一个对称矩阵。

4、计算题：设n n R A ⨯∈是对称矩阵，向量n R b ∈，1R c ∈，求二次函数cx b Ax x x f TT++=21)(在任意点n R x ∈处的梯度和海森矩阵。

[解]设n n ij a A ⨯=)(，T n x x x x ),,,(21 =，T n b b b b ),,,(21 =，于是cxb x ax c xb x x ax f ni iini nj j ijini iini nj j i ij++=++=∑∑∑∑∑∑======1111112121)(。

将)(x f 关于n i x i ,,2,1, =求偏导得到：inj j iji nj j jinj j ij ib x ab x ax a x x f +=++=∂∂∑∑∑===111][21)(（因为A 是对称矩阵，ij jia a =），所以梯度b Ax b b b x a x a x a x x f x x f x x f x f n nj jnj n j jj nj j j n +=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∂∂∂∂∂∂=∇∑∑∑=== 211121121)()()()(。

第四章 动态最优化基础§4.1 动态最优化的基本问题例：最短路问题图4.1给出了从城市A 到城市B 的路线图（省略了距离单位标注）。

现求一条从A 到B 的最短路线。

图4.1显然，为了从A 到B ，必须先逐步经过C1、C2、C3、C4等诸城市。

而在C1、C2、C3、C4，又都有多种选择。

而关键性的困难是当前的最优选择不一定是全局的最优。

这类问题也称为多阶段决策问题。

§4.2 动态最优化的基本概念阶段：将全过程分为若干个有相互联系的阶段，常用字母t 、k 表示；状态：系统在不同阶段性态。

一般来说，系统在一个阶段有多个状态。

系统在某一阶段的所有可能的状态构成的集合成为状态集，记为S k ；状态变量：表示系统状态的变量，记为s k 。

它与阶段有关；决策：在某一阶段的某一状态下，系统由该状态演变到下一阶段某一状态的选择。

在第k 阶段，处于状态s k 时的所有可能的决策集记为D k （s k ）；决策变量：描述决策的变量，它与阶段与系统在该阶段的状态有关。

在第k 阶段，处于状态s k 时的决策记为d k （s k ）；状态转移：从当前阶段的某一状态转移到下一阶段的某一状态。

状态转移方程：描述状态转移规律的数学方程。

它是当前状态变量与决策变量的函数，即) ,(1k k k k d s T s =+；策略：从起点到终点的每一阶段的决策所构成的决策序列，称为（全局）策略。

自某一阶段起，至终点的决策称为子策略，记为))(,),(()(11,n n k n k s d s d s p =。

指标（目标）函数：性能指标或效用指标，它用来评价决策的效果。

它可分为阶段指标与全局指标两类。

阶段指标是指衡量某一阶段在某一状态下的决策效果的指标。

它仅依赖当前状态和当前决策。

记为))(,(k k k k s d s v ；全局指标是指衡量整个全过程或自某一阶段起至终点的各阶段决策的总体效果的指标。

它是所有各阶段的状态和决策的函数，即动态最优化的主要问题是寻找一个策略，使全局指标最优。

1.sehrwwrht2.sdhftdshtrsjhrtjutgkmj3.asgshgdf4.afsgsdahte5.可行解：在线性 规划中，把满足所有的约束条件的解称为该线性规划的可行解。

把使得目标函数值最大的解称为该线性规划的最优解，此函数值称为最优目标函数值简称最优值。

6.在线性规划中，一个“≦”约束条件中没使用得资源或能力称为松驰量。

7.对于“≧”约束条件可以增加一些最低限约束的超过量，称为剩余变量。

8.对fdjgdtefdjjet 偶价jjjjjjjjjjjjjjjjjjjjj 格：在约束条件中常数项增加一个单位而使得最优目标函数值得到改进的数量称为这个约束条件的对偶价格。

考点二：单纯形法9.在单纯形法中，可行jjjjjjjjjjjjjjjjjjjjjjjjjjjjj 域的顶点叫做tgjrtrkj 基本可行解。

找到第一个可行域的定点叫做初始基本可行解。

yyyyyyyyyyyy10.基本解：在约束方 程组系数矩阵中找到一个基，令这个基的非基变量为0，再求解这个m 元线性方程组就可得到唯一的fgjrk 解，这个解称为线性规划的基本解。

基本解可以是可行解，也可以是非jjjjjjjjjjjjjjjjjjjjjj 可行解，它们之间主要区jjjjjjjjjjjjjjjyyyyyyyyyyyy 别是在于所有的变量的解是否满足非负条件。

11.基本可行解jfdjtk ：满足非 负条件的一个基本解叫做基本可行解。

并把这样的基叫做可行基。

12.人工变量：为了fdhjteydk 在约束条件的系数矩阵中找到单位矩阵，人为加上的变量。

注意：人工变量是与松驰变量和剩余变量不同的。

松弛变量和剩余变量可以取零值，也可以取正值，而人工变量只能取零值。

考点三：对偶规则的基本性质9.对称性：对偶问题的对偶是原问题。

10.弱对偶性：即对于原问题trjtrji （1）和对偶问题（2）的可行解y xˆ,ˆ，都有y b x c Tˆˆ≤。

练习题三1、用0.618法求解问题12)(min 30+-=≥t t t t ϕ的近似最优解，已知)(t ϕ的单谷区间为]3,0[，要求最后区间精度0.5ε=。

答：t=0.8115；最小值-0.0886.（调用golds.m 函数）（见例题讲解5） 2、求无约束非线性规划问题min ),,(321x x x f =123222124x x x x -++的最优解解一：由极值存在的必要条件求出稳定点：1122f x x ∂=-∂，228f x x ∂=∂，332fx x ∂=∂，则由()0f x ∇=得11x =，20x =，30x = 再用充分条件进行检验：2212f x ∂=∂，2228f x ∂=∂，2232f x ∂=∂，2120fx x ∂=∂∂，2130f x x ∂=∂∂，2230f x x ∂=∂∂ 即2200080002f ⎛⎫⎪∇= ⎪ ⎪⎝⎭为正定矩阵得极小点为T *(1,0,0)x =，最优值为-1。

解二：目标函数改写成min ),,(321x x x f =222123(1)41x x x -++-易知最优解为（1,0,0），最优值为-1。

3、用最速下降法求解无约束非线性规划问题。

2221212122)(min x x x x x x X f +++-= 其中T x x X ),(21=，给定初始点T X )0,0(0=。

解一：目标函数()f x 的梯度112122()()142()122()()f x x x x f x x x f x x ∂⎡⎤⎢⎥∂++⎡⎤⎢⎥∇==⎢⎥-++∂⎢⎥⎣⎦⎢⎥∂⎣⎦(0)1()1f X ⎡⎤∇=⎢⎥-⎣⎦令搜索方向(1)(0)1()1d f X -⎡⎤=-∇=⎢⎥⎣⎦再从(0)X 出发，沿(1)d 方向作一维寻优，令步长变量为λ，最优步长为1λ，则有(0)(1)0101X d λλλλ--⎡⎤⎡⎤⎡⎤+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦故(0)(1)2221()()()2()2()2()f x f X d λλλλλλλλλϕλ=+=--+-+-+=-=令'1()220ϕλλ=-=可得11λ= (1)(0)(1)1011011X X d λ--⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦ 求出(1)X 点之后，与上类似地，进行第二次迭代：(1)1()1f X -⎡⎤∇=⎢⎥-⎣⎦ 令(2)(1)1()1d f X ⎡⎤=-∇=⎢⎥⎣⎦令步长变量为λ，最优步长为2λ，则有(1)(2)111111X dλλλλ--⎡⎤⎡⎤⎡⎤+=+=⎢⎥⎢⎥⎢⎥+⎣⎦⎣⎦⎣⎦故(1)(2)2222()()(1)(1)2(1)2(1)(1)(1)521()f x f X d λλλλλλλλλϕλ=+=--++-+-+++=--=令'2()1020ϕλλ=-=可得 215λ= (2)(1)(2)2110.8111 1.25X X d λ--⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦(2)0.2()0.2f X ⎡⎤∇=⎢⎥-⎣⎦ 此时所达到的精度(2)()0.2828f X ∇≈ 本题最优解11.5X *-⎡⎤=⎢⎥⎣⎦，()1,25f X *=-解二：利用matlab 程序求解首先建立目标函数及其梯度函数的M 文件 function f=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2); function g=gfun(x)g=[1+4*x(1)+2*x(2),-1+2*x(1) +2* x(2) ]; 调用grad.m 文件 x0=[0,0];[x,val,k]=grad('fun','gfun',x0)结果x=[ -1.0000 ,1.5000] val= -1.2500 k=33即迭代33次的到最优解x=[ -1.0000 ,1.5000]；最优值val= -1.2500。

天津大学《最优化方法》复习题（含答案）天津大学《最优化方法》复习题（含答案）第一章概述(包括凸规划)一、判断与填空题1)].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2{}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=?∈ ?3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(min x f D x ∈的全局最优解. ?4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最优解. ?5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √8 任意两个凸集的并集为凸集. ?9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ?11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。

√12 设{}kx 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法，则对{} ,2,1,0∈?k ，恒有)()(1k k x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。

第六章习题答案1．考虑以下最优化问题max y x1x12x121s.t.x1 , x20用图解法解本题。

并查验平衡解点能否知足（1）拘束规格；（ 2）库恩—塔克极大化条件解：x2ABOx1可行域为 OAB利用图解法求的平衡点为B(1,0) ， max y 1对于 B(1,0) 来说，有 x12x2211，所以该拘束规格是紧的。

建立拉格朗日函数L( x1 , x2 ,)x1(x12x221)L12x1 x20x1L2x20B(1,0) 切合K T 条件x2( x12x221)00, x12x22102．考虑以下最优化问题min y x1x12x20s.t.x1 , x20用图解法解本题。

并查验平衡解点能否知足（1）拘束规格；（ 2）库恩—塔克极大化条件解：利用图解法求的平衡点为o(0,0) ， min y0求法同上，可知拘束规范是紧的建立拉格朗日函数L( x1 , x2 , ) x1( x12x2 ) L12x10x1L0o(0,0) 切合K T 条件x2( x12x2 )00, x12x20x2Ox1 3.考虑以下最优化问题min yx13 s.t.x2x1x20 0查验平衡解点能否知足（ 1）拘束规格；（ 2）库恩—塔克极大化条件解：x2x1利用图解法求的平衡点为o(0,0) ， min y0求法同上，可知拘束规范是紧的建立拉格朗日函数L( x1 , x2 , ) x1( x13x2 )L 1 3 x 1 2 0x 1Lo(0,0) 不切合 K T 条件x 2( x 13 x 2 ) 00, x 1 3x 24．写出下边优化问题的一阶必需条件max f (x, y, z)x y zx 2 y 2z 2 2s.t.x, y, z解： L (x 1, x 2 , ) x y z( x 2y 2z 22)一阶必需条件为：L 1 2 x 0xL 1 2 y 0yL 1 2 z 0zy 2 z 20, ( x 2 2) 05．求解下边最优化问题min yx 1 x 2max x 2x 4y 2x 1 x 2 0 （1）2x 2 y 1（ 2）x 1 x 2 6s.t.x, ys.t.1x 2x 1, x 2 0min y 40x 15x 210x 3max f ( x 1 , x 2 ) x 1x 225x 1 x 210（3）（ 4）x 12x 22 42x 1 x 3 30s.t .s.t.x 10, x 2 0x 1 , x 2 , x 3 0max yx 1 x 2（5）x 1 x 2 16s.t. x 1, x 2解：（ 1） L( x, y, )x 2 x 4 y 2(2 x 2 y 1)一阶必需条件为：L2x120xL208yy(2 x 2 y1)00,2 x 2 y1解得 x 3, y 1 ,4 1055（2）图解法x2BA C0x1可行域为 x 3, y 1 ,4，平衡解点A(1,1)min y2 1055(3) L( x1, x2, x3,1,2)40x15x2 10 x31(105x1x2 ) 2 (30 2x1 x3 )一阶必需条件为：L5 120402x1L5x2L10 x310 21(10 5x1x2 )02(30 2x13x3 )01, 20,5x1x2102x1x330(4) L( x1, x2, ) x1x22( x12x224)一阶必需条件为：Lx11 2 x10L2x2 2 x20x2( x12x224)00, x12x224解得 x1 2, x20,1 4(5) L( x1, x2, )x1x2(x1 x2 16)一阶必需条件为：Lx20x1L x10x2( x1x216)00, x1x216解得 x1 x286．考虑以下最优化模型max y x1x2(1 x1 )30s.t.x1, x2证明：（ 1）平衡解x1, x21,0 不知足库恩-塔克条件；（ 2）当引进新乘数00，把拉格朗日函数改正成以下形式mr i g x1 , x2 ,, x n，Z00 f x1 , x2 ,, x nii 1则在点1,0处知足库恩-塔克条件。