最优化理论与算法第2版课后答案pdf

8¹

3Ã å`z3.1 `5^ .....................................3.2 { Ú½9Âñ5.............................3.3 eü{.....................................3.4Úî{.......................................3.5[Úî{......................................3.6

ÝFÝ{.....................................

11412152227

8¹·ii·

1nÙÃ å`z

â1 Ü© {nØÐÚ §3¦) 55y¯K L§¥§· I (½|¢ Ú

最优化理论与算法（数学专业研究生）

第一章 引论

§1.1 引言

一、历史与现状

最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John最优性条件（1948），Kuhn-Tucker最优性条件（1951），和Karush最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题

minf(x) （1.1）

x?Rn2、约束最优化问题

minf(x)

?ci(x)?0, i?E （1.2）

s.t.??ci(x)?0, i?I这里E和I均为指标集。

§1.2数学基

第二章 5 生成树算法

定义2·13 （1）图G的每条边e赋与一个实数?(e)，称为e的权。图G称为加权图。 （2）设G1是G的子图，则G1的权定义为： ?(G1)???(e)

e?E(G1)定理2·10 Kruskal算法选得的边的导出子图是最小生成树。

l法所得子图T0显然是生成树，下证它的最优性。设证：Kruska算T0?G??e1,e2,?,e??1??不是最小生成树，T1是G的任给定的一个生成树，f(T)是

?e1,e2,?,e??1?中不在T1又E(T0)??e1,e2,?,e??1?，故e1,e2,?,e??1中必有不在E(T)中的

边。设f(T)?k，即e1,e2,?,ek?1在T与T0上，而ek不在T上，于是T?ek中有一个圈C，

?，使ek?在T上而不是在T0上。令T???，显然也是生成树，又（T?ek)?ekC上定存在ek?)，由算法知，ek是使G??e1,e2,?,ek??无圈的权最小的边，?(T?)??(T)??(ek)??(ek???是T之子图，也无圈，则有?(ek?)??(ek)，于是?(T?)??(T)，又G??e1,e2,?,ek

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

《最优化理论与方法》复习内容要求和题型

一、复习内容要求

1、最优化问题及其分类，最优解的相关概念，最优化问题的算法的一般迭代格式及其收敛性和停止准则。

2、建立一个实际最优化问题的数学模型的思想和方法，包括线性规划、非线性规划、动态规划及多目标规划模型。

3、掌握单纯形法的理论依据、基本思想和最优性检验定理，熟练用大M法和两阶段求解线性规划问题，特别是构造的新问题与原问题的解的关系。

4、了解内点法的基本思想，掌握线性规划和0-1规划问题的计算机求解方法。

5、知道解决特殊线性规划问题的解法（含分支定界法、隐枚举法、表上作业法和匈牙利法）的思想方法。

6、了解非线性规划问题及数学模型，了解非线性规划的相关概念及理论，知道非线性规划的最优性条件。

7、掌握一维搜索的黄金分割法（0.618法）与Fibonacci法，知道二分法，特别注意这些算法的适用条件。

8、掌握最速下降法、牛顿类算法、FR共轭梯度法的算法步骤，并熟练使用它们求解多维无约束非线性规划，特别注意这些算法的异同点及它们与一维优化的关系。

9、了解惩罚函数法的算法思想，熟练掌握用内、外点法求解多维约束非线性规划问题，特别注意它们的异同点及适用条件。

10、了解乘子法的算法思想，熟练

第6章 约束最优化方法

6.1

可行方向法 罚函数法 乘子法

主 要 内 容

6.2 6.3

6.4 6.5

二次规划问题 网格法

求解约束最优化问题比求解无约束最优化问题要困 难的多，因为每次迭代不仅要使目标函数值下降 (对最小化问题),同时还要考虑解的可行性问题。

求解约束非线性优化问题的方法很多。 有些是将约束非线性优化问题转化为无约束非线 性优化问题(SUMT),如罚函数法(外点法)、 障碍函数法(内点法)等， 有些是通过构造下降可行方向进行迭代，如 Zoutengijk可行方向法、Rosen梯度投影法、简约 梯度法等， 有些是将非线性优化问题转化为线性规划问题， 如线性逼近法等；还有网格法等等。

6.1 可行方向法

可行方向法是求解约束最优化问题的一类常用方法，

是无约束最优化问题下降迭代算法的自然推广。

可行方向法的典型策略是从某可行点出发，沿该点

的下降可行方向进行搜索，求出使目标函数值下降的新的可行点,

算法的主要步骤是选择搜索方向和确定沿此方向搜索的步长。

搜索方向的选择方式不同就形成不同的可行方向法。

6.1.1 可行方向法概述

6.1.2 Zoutendijk可行方向法

第一章 最优化问题总论

无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．

概括地说，凡是追求最优目标的数学问题都属于最优化问题．作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题．

§1.1 最优化问题数学模型

最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题．

例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？

解 设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为

f(x)?(a?2x)2x．

令

f'(x)?2(a?2x)(?2)x?(a?2x)2?(a?2x)(a?6x)?0，

得两个驻点：

x?

最优化方法习题1答案

《最优化方法》（研究生）期末考试练习题答案

二.简答题

min -5y1 9y2, s.t. 4y1 3y2 3, -2y1 y2 2, 1．

3y1 4y2 8, y1,y2 0;

x3 x4 0, （以x1为源行生成的割平面方程） 2．

注意：在x1为整数的情况下，因为x3,x4 0，该方程自然满足，这是割平面的退化情形

1

656

111

x3 x4 , （以x2为源行生成的割平面方程）

442

3．

a1 0,b1 3

1 a1 0.382(b1 a1) 0 0.382*3 1.146

1 a1 0.618(b1 a1) 0 0.618*3 1.854 ( 1) (1.146)3 2*1.146 1 0.2131 ( 1) (1.854)3 2*1.854 1 3.6648

事实上,不经计算也可以看出

( 1) ( 1)，所以a2 0,b2 1.854。

即：初始的保留区间为[0，1.854]。近似的最优解：x*

0 1.854

0.927.2

f1(x) x1e x2*( 1) 2.7 x1ex2 2.7

4．令

f2(x) x1

实现

x RArmijo搜索准则,并利用22Armijo准则求解无约束优化问题2mifnx( x)1 (x2 x) 12(的步长因子1) k.设当前迭代点x(k) ( 1,1)T,下降方向d(k) (1, 2)T.

参考代码

程序3 (Armijo 准则程序)

function mk=armijo(xk,dk )

beta=0.5; sigma=0.2;

m=0; mmax=20;

while (m<=mmax)

if(fun(xk+beta^m*dk)<=fun(xk)+sigma*beta^m*gfun(xk)’*dk)

mk=m; break;

end

m=m+1;

end

alpha=beta^mk

newxk=xk+alpha*dk

fk=fun(xk)

newfk=fun(newxk)

说明: fun 和gfun 分别是指目标函数和它的梯度函数的子程序. 执行上述过程时这两个子程序必须事先准备好.