最优化方法练习题答案
练习题一
1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。
2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。
答：针对一般优化模型()()min ()
..
0,1,2, 0,1,,i j f x s t g x i m h x j p
≥=== ，讨论解的可行域D ，若存在一点*X D ∈，对于X D ?∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭
代算法的收敛性是指迭代所得到的序列(1)(2)(),,,K X X X ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<，
(1)()
()
k k k x x x ε+-<，
()()(1)()k k f x f x ε+-<，
()()()
(1)()()k k k f x f x f x ε+-<，()()k f x ε?<等等。
练习题二
1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R
2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。
解：确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。
确定目标函数 问题的目标很清楚——“收购价最小”。
确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。
因此有如下线性规划问题：123min 170100150w y y y =++
123123123
5210
..23518,,0y y y s t y y y y y y ++≥??++≥??≥? *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。
答：略。
3、用单纯形法求解下列线性规划问题：
（1）??????
?≥≤+-≤++≤-++-=0
,,4322
2..min
32131
3213213
21x x x x x x x x x x x t s x x x z ； （2）???????=≥=++=+-=+-+-=)5,,2,1(052222..4min
5324323213
2 i x x x x x x x x x x t s x x z i 解：（1）引入松弛变量x 4，x 5，x 6
123456min 0*0*0*z x x x x x x =-++++
12341232 =2
2 5 =3..1
3 6=41,2,3,4,5,60
x x x x x x x x s t x x x x x x x x x +-+??+++??-++??≥?
因检验数σ2<0，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。
因检验数σ3<0，故确定x 3为换入非基变量，以x 3的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 5作为换出的基变量。
因检验数σj >0，表明已求得最优解：*(0,8/3,1/3,0,0,11/3)X =，去除添加的松弛变量，原问题的最优解为：*(0,8/3,1/3)X =。
（2）根据题意选取x 1，x 4，x 5，为基变量：
??????
?=≥=++=+-=+-+-=)
5,,2,1(052222..4min
5324323
213
2 i x x x x x x x x x x t s x x z i
因检验数σ2<0最小，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。
因检验数σ3<0最小，故确定x 3为换入非基变量，以x 1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 5作为换出的基变量。
因检验数σj >0，表明已求得最优解：*(9,4,1,0,0)X =。
4、分别用大M 法、两阶段法和Matlab 软件求解下列线性规划问题：
（1）???????≥≤+≥+=++=0,3263933..4min
212121212
1x x x x x x x x t s x x z ； （2）????
??
?≥≥++≤++-≤++++=0,,52151565935..121510max
3213213213213
21x x x x x x x x x x x x t s x x x z
解：（1）大M 法
根据题意约束条件1和2可以合并为1，引入松弛变量x 3，x 4，构造新问题。
1234min z=4x +x +Mx +0*x
1231241
43 3
..2 3,0
x x x s t x x x x x ++=??++=??≥?
因检验数σj >0，表明已求得最优解：*(3/5,6/5)X =。 Matlab 调用代码： f=[4;1]; A=[-9,-3;1,2]; b=[-6;3]; Aeq=[3,1]; beq=3; lb=[0;0];
[x,fval] = linprog(f,A,b,Aeq,beq,lb) 输出结果：
Optimization terminated.
x = 0.6000 1.2000 fval = 3.6000 （2）大M 法
引入松弛变量x 4，x 5，x 6，x 7构造新问题。
1234567max 101512000z x x x x x x Mx =+++++-
12341235123671753 95615 15..2 5,,0
x x x x x x x x s t x x x x x x x +++=??-+++=??++-+=??≥?
单纯形表计算略；当所有非基变量为负数，人工变量7x =0.5，所以原问题无可行解。 请同学们自己求解。 Matlab 调用代码： f=[-10;-15;-12];
A=[5,3,1;-5,6,15;-2,-1,-1]; b=[9;15;-5]; lb=[0;0;0];
x = linprog(f,A,b,[],[],lb) 输出结果： 原题无可行解。
5、用内点法和Matlab 软件求解下列线性规划问题：
??
?
??≥=+=++++=0
,,52622..2min
321213213
21x x x x x x x x t s x x x z
解：用内点法的过程自己书写，参考答案：最优解[4/3 7/3 0]X =；最优值5 Matlab 调用代码： f=[2;1;1]; Aeq=[1,2,2;2,1,0];
beq=[6;5]; lb=[0;0;0];
[x,fval] = linprog(f,[],[],Aeq,beq,lb) 输出结果：
Optimization terminated. x = 1.3333 2.3333 0.0000 fval = 5.0000
6、用分支定界法求解下列问题：
（1） ?????≥≤+≤++=且均为整数0,45956..85max
2
12
1212
1x x x x x x t s x x z ； （2）?????
≥≤+≤+-+=为整数
且12121212
10,35763..97max
x x x x x x x t s x x z 解：（1）调用matlab 编译程序bbmethod
f=[-5; -8];G=[1 1;5 9];h=[6; 45]
[x,y]=bbmethod(f,G ,h,[],[],[0;0],[],[1;1],1) x =
3 3 y =
-39
最优解[3 3]；最优值39
（2）调用matlab 编译程序bbmethod
f=[-7; -9];G=[-1 3; 7 1];h=[6; 35]
[x,y]=bbmethod(f,G ,h,[],[],[0;0],[],[1;0],1) x =
5 0 y = -35
最优解[5 0]；最优值35
7、用隐枚举法和Matlab 软件求解下列问题：
（1）??
?
???
?==≥+≥++≤+-++=)3,2,1(1013
344352..234min
323213213
21j x x x x x x x x x t s x x x z j 或；（2）???
???
?==≥-+-≤+-+≤+++++--+=)5,,2,1(101336118
343742..32523max
54215
431543215
4321 j x x x x x x x x x x x x x x t s x x x x x z j 或
解： 隐枚举法：
（1）将（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（0，0，1），目标函数最优值2.
（2）将（0，0，0，0，0）（0，0，0，0，1）（0，0，0，1，0）（0，0，1，0，0）…. （1，1，1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（1，1，0，0，0），目标函数最优值-5。 Matlab 软件求解： （1）
调用代码：
f=[4; 3;2];
% 价值向量f
A=[2,-5,3; -4,-1,-3;0,-1,-1]; % 不等式约束系数矩阵A ，[ ]中的分号“；”% 为行分隔符 b=[4; -3;-1];
% 不等式约束右端常数向量b
[x, fval]=bintprog(f, A, b, [], []);
%调用函数bintprog 。注意两个空数组的占位作用。
输出结果
x= 0 0 1 fval=
2
（2）
调用代码：
f=[-3; -2;5;2;3];
% 价值向量f
A=[1,1,1,2,1; 7,0,3,-4,3;-11, 6,0,-3, 3]; % 不等式约束系数矩阵A ，[ ]中的分号“；”% 为行分隔符 b=[4; 8;-1];
% 不等式约束右端常数向量b
[x, fval]=bintprog(f, A, b, [], []);
%调用函数bintprog 。注意两个空数组的占位作用。
输出结果
x=
1 1
0 0 0
fval=
-5
最优值5。
8、某地区有A 、B 、C 三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。
表2- 1
解：设A 、B 、C 三个化肥厂为A 1、A 2、A 3，甲、乙、丙、丁四个产粮区为B 1、B 2、B 3、B 4；c ij 为由A i 运化肥至B j 的运价，单位是元/吨；x ij 为由A i 运往B j 的化肥数量（i=1,2,3;j=1,2,3,4）单位是吨；z 表示总运费，单位为元，依题意问题的数学模型为：
34
11
min ij ij i j z c x ===∑∑
112131122232
13233314243411121314
21222324313233346
63..3
787
x x x x x x x x x s t x x x x x x x x x x x x x x x ++=??++=??++=?
++=??+++=??+++=?
+++=? 该题可以用单纯形法或matlab 自带工具箱命令（linprog ）求解。
*9、求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格ij c ，框外右
侧的一列数为各发点的供应量
i a
，框底下一行数是各收点的需求量j b）：（1） 5
1 7 10
要求收点3的需求必须正好满足。
6 4 6 80
3 2 5 15
75 20 50
（2） 5 1 0 20 要求收点1的需求必须由发点4供应。
3 2
4 10
7 5 2 15
9 6 0 15
5 10 15
解答略。
10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。公司经理应怎样分派才使总利润最大？
表2- 2
解：用求极大值的“匈牙利法”求解。
效率矩阵表示为：
??
?
?
?
?
?
?
?
28
25
32
24
33
32
24
35
40
29
34
28
37
28
27
35
??
?
?
?
?
?
?
?
12
15
8
16
7
8
16
5
11
6
12
3
12
13
5
????
???
?
?47
082311001161209102
?
??
???
?
??44
)
0(8
2011)0(08612)0(6102**所画（）0元素少于n （n ＝4），未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：
ij 2，在直线交叉处加上2。
???????
?
?
64
0840110064100480????
??
??
?64
084)0(11006410048
)0(**）
（）（
∴得最优解：??????
?
?
?
00
1
010********* ∴使总利润为最大的分配任务方案为：
1→1，2→4，3→3，4→2
此时总利润W=35+40+32+32=139
练习题三
1、用0.618法求解问题
12)(min 30
+-=≥t t t t ?
的近似最优解，已知)(t ?的单谷区间为]3,0[，要求最后区间精度0.5ε=。
答：t=0.8115；最小值-0.0886.（调用golds.m 函数） 2、求无约束非线性规划问题
min ),,(321x x x f =12
3222124x x x x -++
的最优解
解一：由极值存在的必要条件求出稳定点：
1122f x x ?=-?，228f x x ?=?，33
2f
x x ?=?，则由()0f x ?=得11x =，20x =，30x = 再用充分条件进行检验：
22
12f x ?=?，2228f x ?=?，2232f x ?=?，212
0f
x x ?=??，2130f x x ?=??，2230f x x ?=?? 即2200080002f ??
?
?= ? ???
为正定矩阵得极小点为T *(1,0,0)x =，最优值为-1。
解二：目标函数改写成
min ),,(321x x x f =222
123(1)41x x x -++-
易知最优解为（1,0,0），最优值为-1。
3、用最速下降法求解无约束非线性规划问题。
2
2
21212122)(min x x x x x x X f +++-= 其中T x x X ),(21=，给定初始点T X )0,0(0=。
解一：目标函数()f x 的梯度112
122()()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。
4、试用Newton 法求解第3题。 解一：计算目标函数的梯度和Hesse 阵
目标函数()f x 的梯度112
122()()142()122()()f x x x x f x x x f x x ???
???++??
???==??-++?????????? 242()22f X G ???==????，其逆矩阵为1
0.50.50.51G --??=??-?? [][][](1)
(0)
1(0)
0.50.5()0,01,11,1.50.5
1T
T T
X
X
G f X
--??=-?=--=-??-?? 计算(1)()0f X ?=。
本题最优解11.5X *
-??
=????
，()1,25f X *=-
解二：除了第3题建立两个M 文件外，还需建立Hesse 矩阵的M 文件 利用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) ]; function h=hess(x) g=[4 2;2 2 ]; 调用newton.m 文件 x0=[0,0];
[x,val,k]=newton('fun','gfun','hess',x0) 结果
x=[ -1.0000 ,1.5000] val= -1.2500 k=1
5、用Fletcher —Reeves 法求解问题
22
2125)(min x x X f += 其中T x x X ),(21=，要求选取初始点6010,)2,2(-==εT X 。 解一：
1122201
()(,),0502x f x x x x ????=???????? 20050G ??=????，12()(2,50).T r f x x x =?= 第一次迭代：令00(4,100)T p r =-=--，
000004(4,100)100120450
(4,100)050100T T r r p Gp α??
??
??===-????--????
-???? 即，(1)(0)00(1.92,0)T X X p α=+= 第二次迭代：
1(3.84,0)T
r =，2102
0||||3
||||2000
r r β==，T 1100( 3.846,0.15)p r p β=-+=-- 11111 3.84(3.84,0)00.480220 3.846( 3.846,0.15)0500.15T T r r p Gp α????
??===-????
--????
-????
(2)(1)11(0.0732,0.072)T X X p α=+=-
第三次迭代：
2(0.1464, 3.6)T r =-……（建议同学们自己做下去，注意判别k r ε≤）
解二：利用matlab 程序求解
首先建立目标函数及其梯度函数的M 文件 function f=fun(x) f=x(1)^2+25* x(2)*x(2); function g=gfun(x) g=[2*x(1), 50* x(2) ]; 调用frcg.m 文件 x0=[2,2]?;epsilon=1e-6;
[x,val,k]=frcg('fun','gfun',x0, epsilon) 结果
x = 1.0e-006 *[ 0.2651, 0.0088] val =7.2182e-014 k = 61
6、试用外点法（二次罚函数方法）求解非线性规划问题
???≥-=+-=0
1)(..)2()(min 22
221x X g t s x x X f 其中221),(R x x X ∈=
解：设计罚函数 (,)
()
*[()]
P x M f X M g X =+ 采用Matlab 编程计算，结果x=[1 0]；最优结果为1。（调用waidianfa.m ） 7、用内点法（内点障碍罚函数法）求解非线性规划问题：
312
12min (1)..100x x s t x x ?++?
-≥??≥?
解：容易看出此问题最优解为x=[1 0]；最优值为8.
给出罚函数为 31212(,)(1)(1/
(1)1/
)
P x r x x r x x =+++-+ 令
21211(,)3(1)0(1)P x r r x x x ?=+-=-；2
22
(,)10P x r r
x x =-= 从而当0r +
→
时，1/2(11()0x r x ??+??=→=? ?????
（建议同学自己编程序计算）
8、用乘子法求解下列问题 22
12
112min ()()20
f X x x h X x x ?=+??=+-=??
解：建立乘子法的增广目标函数：
22
121212(,,)(2)(2)^22
x x x x x x x σ
ψλσλ=+-+-+
+-
令：
1121
(,,)
2(2)0x x x x x ψλσλσ?=-++-=? 2121
(,,)
2(2)0x x x x x ψλσλσ?=-++-=? 解上述关于x 的二元一次方程组得到稳定点
222222x σλσσλσ+????+=??+????+??
当乘子λ取2时，或发参数σ趋于无穷时，得到1*1x x ??
==????即最优解。
（建议同学自己编程序计算）
练习题四
1、石油输送管道铺设最优方案的选择问题：考察网络图4-6，设A 为出发地，F 为目的地，B ，C ，D ，E 分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？
图4- 1
解：
第五阶段：E1—F 4；E2—F 3；
第四阶段：D1—E1 —F 7；D2—E2—F 5；D3—E1—F 5；
第三阶段：C1—D1—E1 —F 12；C2—D2—E2—F 10；C3—D2—E2—F 8；C4—D3—E1—F 9；
第二阶段：B1—C2—D2—E2—F 13； B2—C3—D2—E2—F 15； 第一阶段：A —B1—C2—D2—E2—F 17； 最优解：A —B1—C2—D2—E2—F 最优值：17
2、 用动态规划方法求解非线性规划
123123max ()27,,0
f x x x x x x x =++=??
≥?解：1239,9,9x x x ===，最优值为9。 3、用动态规划方法求解非线性规划
22
112121212max 765..
21039,0z x x x s t x x x x x x ?=++?
+≤??
-≤?
?≥?
解：用顺序算法
阶段：分成两个阶段，且阶段1 、2 分别对应12,x x 。 决策变量：12,x x
状态变量：,i i v w 分别为第j 阶段第一、第二约束条件可供分配的右段数值。
11
11
*22211111111100(,)max {76}min{76,76}x v x w f v w x x v v w w ≤≤≤≤=+=++
*111min{,}x v w =
22*2*22221222205
2
22
2
2222222205
(,)max{5(2,3)}
max{5min{7(2)6(2),7(3)6(3)}}
x x f v w x f v x w x x v x v x w x w x ≤≤≤≤=+-+=+-+-+++
由于2210,9v w ==，
2**22
2222222205
(,)(10,9)max{min{33292760,68396621}x f v w f x x x x ≤≤==-+++
可解的129.6,0.2x x ==，最优值为702.92。
4、设四个城市之间的公路网如图4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。
21
4
3
58
6
7
4
图4- 2 城市公路网
解：城市1到城市4路线——1-3-4 距离10；
城市2到城市4路线——2-4 距离8；城市3到城市4路线——3-4 距离4。 5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表4-19所示。试问在各地区如何设置销售点可使每月总利润最大。
表4- 1
解：
将问题分为3个阶段，k =1，2，3；
决策变量x k 表示分配给第k 个地区的销售点数；
状态变量为s k 表示分配给第k 个至第3个地区的销售点总数； 状态转移方程：s k +1=s k －x k ，其中s 1=4； 允许决策集合：D k （s k ）=｛x k |0≤x k ≤s k ｝
阶段指标函数：g k （x k ）表示x k 个销售点分配给第k 个地区所获得的利润；
最优指标函数f k （s k ）表示将数量为s k 的销售点分配给第k 个至第3个地区所得到的最大利润，动态规划基本方程为：
1044()max [()()] 3,2,1()0
k k
k k k k k k k x s f s g x f s x k f s +≤≤=+-=???
=?? k =3时，33
3333()max[()]x s f s g x ==
2
110 4
17
17
4
31616
321414
10
1000
4
3210x 3*
f 3(s 3)
g 3（x 3）
k =2时，22
22223220()max [()()]x s f s g x f s x ≤≤=+-
02,3
31
22+0
21+10 17+14 12+16 0+17 4
2
2721+017+1012+140+16312217+012+100+142112
12+00+1010
004
321x 2*
f 2(s 2)
g 2(x 2)+f 3(s 2－x 2)
k =1时，1
1
11112110()max[()()]x s f s g x f s x ≤≤=+-，1
11112104
()max[()(4)]x f s g x f x ≤≤=+-
最优解为：x 1*=2，x 2*=1，x 3*=1，f 1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。
6、设某厂计划全年生产某种产品A 。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A 的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。
解：四个季度为四个阶段，采用阶段编号与季度顺序一致。 设 s k 为第k 季初的库存量，则边界条件为 s 1=s 5=0
设 x k 为第k 季的生产量，设 y k 为第k 季的订货量；s k ，x k ，y k 都取实数，状态转移方程为 s k +1=s k +x k - y k 仍采用反向递推，但注意阶段编号是正向的目标函数为：
1234
4
2
1,,,1
()min
(0.005)i
i x x x x i f x x
s ==+∑
第一步：(第四季度) 总效果 f 4(s 4,x 4)=0.005 x 42+s 4
由边界条件有： s 5= s 4 + x 4 – y 4=0，解得：x 4*=1200 – s 4 将x 4*代入 f 4(s 4,x 4)得：
f 4*(s 4)=0.005(1200 – s 4)2+s 4=7200 –11 s 4+0.005 s 42 第二步：(第三、四季度) 总效果 f 3(s 3,x 3)=0.005 x 32+s 3+ f 4*(s 4) 将 s 4= s 3 + x 3 – 500 代入 f 3(s 3,x 3) 得：
2
33333332
3322
333333333333333332
3333
(,)0.005720011(500)
0.005(500)0.010.01160.0051513950
(,)
0.020.011608000.5,
(,)()755070.0025f s x x s x s x s x x s x s s f s x x s x x s f s x f s s s **=++-+-++-=+-+-+?=+-=?=-=-+解得
代入得
第三步：(第二、三、四季度) 总效果 f 2(s 2,x 2)=0.005 x 22+s 2+ f 3*(s 3) 将 s 3= s 2 + x 2 -700 代入 f 2(s 2,x 2) 得：
2
22222222
22222222222222
2222
(,)0.00575507(700)
0.0025(700)(,)
0.0150.005(700)70700(1,
(,)()100006(0.0053)f s x x s x s x s f s x x s x x s f s x f s s s **=++-+-++-?=+--=?=-=-+解得
代入得
《最优化方法》复习题(含答案)
《最优化方法》复习题(含答案)
附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，
最优化方法复习题66882.docx
《最优化方法》复习题 第一章概述(包括凸规划) 一、判断与填空题 ar§ max /W =玄生min【―/(兀)】?7 1 xeR n xeR n 2max |/(x): x e D o }= - min [f(x): x e D Q R H\ x 3设f : D u RJ R?若T wR”,对于一切xeR n恒有/(Z)上的凸函数当且仅当—/为D上的凹函数.V 1()设f : D u R” T R为凸集D上的可微凸函数，Z G Z).则对V XG D,有/(x)-/(x*)
则对\^^{0,1,2,???},恒有____ /(x A.+1)< f(x k) ____________ :
13算法迭代时的终止准则（写出三种）： ____________________________ o 14凸规划的全体极小点组成的集合是凸集。V 15函数f : D u R“ T R在点（'沿着迭代方向d* eR n \ ｛（）｝进行精确一维线搜索的步长匕.，则其搜索公式为_____________________________ . 16函数f ?. D匚R“ T R在点*?沿着迭代方向d k e/?z, \｛0｝进行梢确一?维线搜索的步长匕，则V/（x A+a k d k Yd k = ___________ 0 . 17设d k eR n\｛0｝为点/ w D匸R“处关于区域D的一个下降方向，则对于Va >0, 3?G（0,a）使得x 二、简述题 1写出Wolfe-Powell非精确一维线性搜索的公式。 2怎样判断一个函数是否为凸函数. （例如:判断函数/（x） = xf +2兀|兀2 +2兀;一10兀1 +5兀2是否为凸函数） 三、证明题 1证明一个优化问题是否为凸规划.（例如 1Z* T —X Gx + c x + b 2 判断s.t. Ax = b（其小G是正定矩阵）是凸规划. x>0 2熟练掌握凸规划的性质及英证明.
北航最优化方法大作业参考
北航最优化方法大作业参考
1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求
1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T） 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40
《最优化方法》复习题
《最优化方法》复习题 一、 简述题 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 k x x G g -+=-． （4）推导最速下降法用于问题1min ()2 T T f x x Gx b x c = ++的迭代公式： 1()T k k k k k T k k k g g x x f x g G gx +=-? （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-??． （6）共轭方向法用于问题1min ()2 T T f x x Qx b x c = ++的迭代公式： 1()T k k k k k T k k f x d x x d d Qd +?=-． 二、计算题 双折线法练习题 课本135页 例3.9.1 FR 共轭梯度法例题：课本150页 例4.3.5 二次规划有效集：课本213页例6.3.2,
最优化练习题
最优化练习题 1．设A 为m n ?阶矩阵，n b R ∈，试证集合{|,,0}n S x x R Ax b x =∈=≥为凸集。 2．试证平面上椭圆22 221x y a b +=所包围的区域为凸集。 3．判断下列函数为凸函数或凹函数或严格凸函数或严格凹函数： （1）2 2 1212(,)23f x x x x =+；（2）2 2 2 1231231231(,,)22712f x x x x x x x x x x =+++--+ 4．设()f x 为定义在凸集D 上的凸函数，试证()f x 的任何局部极小点同时也必为全局极小点。 5．设n 阶矩阵0T Q Q =>，非零向量12,,,()n n p p p R m n ∈≤ 为Q 共轭的，证明： （1）12,,,n p p p 线性无关；（2）若n 维向量x 和12,,,n p p p 为Q 共轭的，则x=0。 6．设()T T f x x Ax b x =-，2112A ??=? ? ?? ，(3,3)T b =，取1(0,0)T x =，1(1,0)T p =，2(1,2)T p =-，试证由共轭方向法产生的3x 为()f x 的最优解。 7．设1()2 T T f x x Qx b x c = ++，0T Q Q =>，试证由精确线搜索的共轭梯度法中，有 T k k k T k k g d d Qd λ=- 8．取初始点0(0,0)T x =，并且设定净度误差0.01ε=，试利用最速下降法求解下面的优化 问题：2 22 112212min 243x R x x x x x x ∈-++- 9．考虑极小化问题1min ()2 n T T x R f x x Ax b x ∈=+，其中0T A A =>，n b R ∈。记函数()() g x f x Ax b =?=+。设从k x 点出发，利用精确搜索的最速下降法求出改进点1k x +， 证明： （1）最速下降法的迭代公式形如1T k k k k k T k k g g x x g g Ag +=-，其中()k k g g x =； （2）一步迭代中引起目标函数的下降量为2 1()()()2T k k k k T k k g g f x f x g Ag +-=。 10．研究形如1T k k k k k H H Z Z α+=+的迭代校正公式，使之满足拟牛顿方程，
最优化原理大作业
基于粒子群算法的神经网络在电液伺服系统中的应用 摘要：由于人工神经网络在解决具有非线性、不确定性等系统的控制问题上具有极大的潜力，因而在控制领域正引起人们的极大关注，并且已在一些响应较慢的过程控制中获得成功应用。由于电液伺服系统属 于非线性系统，因此本文利用神经网络控制电液伺服系统，并利用粒子群优化算法训练该神经网络的 权值。通过对神经网络的优化实现对电液伺服系统的控制。 关键词：神经网络电液伺服系统粒子群算法优化 近年来，由于神经网络具有大规模并行性、冗余性、容错性、本质的非线性及自组织自学习自适应能力，所以已成功地应用于众多领域。但在具有复杂非线性特性的机电设备的实时控制方面，虽然也有一些神经网络技术的应用研究，但距实用仍有一段距离。电液伺服系统就属于这类设备[1]。 神经网路在用于实时控制时，主要是利用了网络所具有的其输人——输出间的非线性映射能力。它实际上是通过学习来逼近控制对象的动、静态特性。也就是构造实际系统的神经网络模型[2]。本文利用神经网络控制一电液伺服系统，并利用粒子群优化算法训练该神经网络的权值，将结果与BP神经网络控制该系统的结果进行比较。从而得在电液伺服系统中引入神经网络是可行的。 1、粒子群算法 粒子群优化算法(Particle Swarm optimization, PSO)是一种进化计算技术, 由Eberhart博士和kennedy博士发明, 源于对鸟群捕食的行为研究, 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解[3]。算法最初受到飞鸟和鱼类集群活动的规律性启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间个体协作来实现对问题最优解的搜索[4]。 在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置 v[]=v[]+c1*rand()*(pbest[]-present[]) + c2*rand()*(gbest[]-present[]) present[]=persent[]+v[] 式中ω为惯性权重，ω取大值可使算法具有较强的全局搜索能力，ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4，这样就可以先侧重于全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解；c1、c2为两个学习因子，一般取为2；randl和rand2为两个均匀分布在(0，l)之间的随机数；i=1，2，?，m；k=1，2，?，d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度 超过该维上的最大速度Vmax，则该维的速度被限制为最大速度[5]。 粒子群算法流程如下： (一)初始化粒子群。设群体规模为m，在允许的范围内随机设置粒子的初始位置和速 度。 (二)评价每个粒子的适应值。 (三)调整每一个粒子的位置和速度。 (四)如果达到最大迭代次数genmax或误差达到最初设定数值终止迭代，否则返回(2)。 2、神经网络 神经网络一般由输入层、隐含层、输出层组成。对于输入信号，先向前传播到隐节点，经过节点作用函数后，再把隐节点的输出信息传播到输出节点，最后输出结果。节点的作用函数通常选取S 型函数f（x）=1/（1+e-x）。神经网络算法的学习过程分为正
最优化方法大作业答案
1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x 列成表格：
1 2 1 610011460105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 1 2 1 2102310401162010021212 11-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 2 12 32 30 210231040116201002121211- ------ 再从底行中选元素-3，和第二列正元素2，迭代一次得 4 2 3 3 410120280114042001112--- 再迭代一次得 10 2 30 2 10 6 221023 1010213000421021013-- 选取最优解：
最优化计算方法课后习题答案----高等教育出版社。施光燕
习题二包括题目：P36页5（1）（4） 5（4）
习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-
最优化方法大作业答案
武工院你们懂的 1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x
列成表格： 00001216 100114 60105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 0000 1 2 121023 10 40116201002 1 21 211-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 002 1232 30210231 040116201002121211-- ----- 再从底行中选元素-3，和第二列正元素2，迭代一次得 4002 3 03410120280114042001112--- 再迭代一次得
10 23021 062 21023 1010 213 000421 2 10 13- - 选取最优解： 01=x 42=x 23=x 3. 试用DFP 变尺度法求解下列无约束优化问题。 min f （X ）=4（x 1-5）2+（x 2-6）2 取初始点X=（8，9）T ，梯度精度ε=0.01。 解：取I H =0,初始点()T X 9,8= 2221)6()5(4)(-+-=x x x f ??????--=?122408)(21x x x f ???? ??=?624)() 0(x f T x f d )6,24()()0()0(--=-?= )0(0)0()1(d x x α+= T )69,248(00αα--= ])669()5248(4min[)(min 2020)0(0)0(--+--?=+αααd x f )6()63(2)24()2458(8) (00)0(0)0(=-?-+-?--=+ααααd d x df 13077.013017 0≈= α ???? ??=???? ??--?+???? ??=21538.886153.462413077.098)1(x
最优化方法试题
《最优化方法》试题 一、 填空题 1.设()f x 是凸集n S R ?上的一阶可微函数，则()f x 是S 上的凸函数的一阶充要条件是（ ），当n=2时，该充要条件的几何意义是（ ）； 2.设()f x 是凸集n R 上的二阶可微函数，则()f x 是n R 上的严格凸函数（ ）（填‘当’或‘当且仅当’）对任意n x R ∈，2()f x ?是 （ ）矩阵； 3.已知规划问题22211212121212min 23..255,0z x x x x x x s t x x x x x x ?=+---?--≥-??--≥-≥?，则在点55(,)66T x =处的可行方向集为（ ），下降方向集为（ ）。 二、选择题 1.给定问题222121212min (2)..00f x x s t x x x x ?=-+??-+≤??-≤?? ，则下列各点属于K-T 点的是（ ） A) (0,0)T B) (1,1)T C) 1(,22 T D) 11(,)22T 2.下列函数中属于严格凸函数的是（ ） A) 211212()2105f x x x x x x =+-+ B) 23122()(0)f x x x x =-< C) 2 222112313()226f x x x x x x x x =+++- D) 123()346f x x x x =+- 三、求下列问题
()22121212121211min 51022 ..2330420 ,0 f x x x x x s t x x x x x x =+---≤+≤≥ 取初始点()0,5T 。 四、考虑约束优化问题 ()221212min 4..3413f x x x s t x x =++≥ 用两种惩罚函数法求解。 五．用牛顿法求解二次函数 222123123123()()()()f x x x x x x x x x x =-++-++++- 的极小值。初始点011,1,22T x ??= ???。 六、证明题 1.对无约束凸规划问题1min ()2 T T f x x Qx c x =+，设从点n x R ∈出发，沿方向n d R ∈ 作最优一维搜索，得到步长t 和新的点y x td =+ ，试证当1T d Q d = 时， 22[() ()]t f x f y =-。 2.设12*** *3(,,)0T x x x x =>是非线性规划问题()112344423min 23..10f x x x x s t x x x =++++=的最优解，试证*x 也 是非线性规划问题 144423* 123min ..23x x x s t x x x f ++++=的最优解，其中****12323f x x x =++。
《最优化方法》复习题(含答案)
x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
最优化方法大作业
发动机空燃比控制器 引言：我主要从事自动化相关研究。这里介绍我曾经接触过的发动机空燃比控制器设计中的优化问题。 发动机空燃比控制器设计中的最优化问题 AFR =a f m m && (1) 空燃比由方程（1）定义，在发动机运行过程中如果控制AFR 稳定在14.7可以获 得最好的动力性能和排放性能。如果假设进入气缸的空气流量a m &可以由相关单元检测得到，则可以通过控制进入气缸的燃油流量f m &来实现空燃比的精确控制。由于实际发动机的燃油喷嘴并不是直接对气缸喷燃油，而是通过进气歧管喷燃油，这么做会在进 气歧管壁上液化形成油膜，因此不仅是喷嘴喷出的未液化部分燃油会进入气缸，油膜 蒸发部分燃油也会进入气缸，如方程（2）。这样如何更好的喷射燃油成为了一个问题。 1110101122211ττττ?? ?? -?? ??????????=+????????-????????????-???? ? ??? ?? ????????? ?f f f v X x x u x x X x y =x && (2) 其中12、,==ff fv x m x m &&=f y m &,=fi u m &这里面，表示油膜蒸发量ff m &、fv m &表示为液化部分燃油、fi m &表示喷嘴喷射的燃油，在τf 、τv 、X 都已知的情况下，由现代控制理论知识，根据系统的增广状态空间模型方程（3） 0000001 1 011011114.70ττττ????-?? ??????????=-+-??????????????? ??????????????? ?? ??=?????? f f v v a X X u +q q m y q x x x &&& (3) 其中()0 14.7?t a q = y -m &。由极点配置方法，只要设计控制器方程（4），就可以 使得y 无差的跟踪阶跃输入，那么y 也能较好的跟踪AFR *a m /&。 12-- u =K q K x (4) 这里面的12、K K 确定，可由主导极点概念降维成两个参数12C ,C ，虽然都是最终稳态无差，但是目标是使得瞬态过程中y 和阶跃输入y r 的差异尽可能的小。所以原问
最优化方法及其应用课后答案
1 2 ( ( 最优化方法部分课后习题解答 1.一直优化问题的数学模型为： 习题一 min f (x ) = (x ? 3)2 + (x ? 4)2 ? g (x ) = x ? x ? 5 ≥ ? 1 1 2 2 ? 试用图解法求出： s .t . ?g 2 (x ) = ?x 1 ? x 2 + 5 ≥ 0 ?g (x ) = x ≥ 0 ? 3 1 ??g 4 (x ) = x 2 ≥ 0 （1） 无约束最优点，并求出最优值。 （2） 约束最优点，并求出其最优值。 （3） 如果加一个等式约束 h (x ) = x 1 ? x 2 = 0 ，其约束最优解是什么？ * 解 ：（1）在无约束条件下， f (x ) 的可行域在整个 x 1 0x 2 平面上，不难看出，当 x =（3，4） 时， f (x ) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x * ) =0 （2）在约束条件下， f (x ) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是 在约束集合即可行域中找一点 (x 1 , x 2 ) ，使其落在半径最小的同心圆上，显然，从图示中可 以看出，当 x * = 15 , 5 ) 时， f (x ) 所在的圆的半径最小。 4 4 ?g (x ) = x ? x ? 5 = 0 ? 15 ?x 1 = 其中：点为 g 1 (x ) 和 g 2 (x ) 的交点，令 ? 1 1 2 ? 2 求解得到： ? 4 5 即最优点为 x * = ? ?g 2 (x ) = ?x 1 ? x 2 + 5 = 0 15 , 5 ) ：最优值为： f (x * ) = 65 ?x = ?? 2 4 4 4 8 （3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。 2.一个矩形无盖油箱的外部总面积限定为 S ，怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为： max f (x ) = x 1x 2 x 3 ?x 1x 2 + 2x 2 x 3 + 2x 1x 3 ≤ S
大连理工优化方法大作业MATLAB编程
function [x,dk,k]=fjqx(x,s) flag=0; a=0; b=0; k=0; d=1; while(flag==0) [p,q]=getpq(x,d,s); if (p<0) b=d; d=(d+a)/2; end if(p>=0)&&(q>=0) dk=d; x=x+d*s; flag=1; end k=k+1;
if(p>=0)&&(q<0) a=d; d=min{2*d,(d+b)/2}; end end %定义求函数值的函数fun，当输入为x0=（x1，x2）时，输出为f function f=fun(x) f=(x(2)-x(1)^2)^2+(1-x(1))^2; function gf=gfun(x) gf=[-4*x(1)*(x(2)-x(1)^2)+2*(x(1)-1),2*(x(2)-x(1)^2)]; function [p,q]=getpq(x,d,s) p=fun(x)-fun(x+d*s)+0.20*d*gfun(x)*s'; q=gfun(x+d*s)*s'-0.60*gfun(x)*s'; 结果： x=[0,1]; s=[-1,1]; [x,dk,k]=fjqx(x,s) x =-0.0000 1.0000 dk =1.1102e-016 k =54
function f= fun( X ) %所求问题目标函数 f=X(1)^2-2*X(1)*X(2)+2*X(2)^2+X(3)^2+ X(4)^2- X(2)*X(3)+2*X(1)+3*X(2)-X(3); end function g= gfun( X ) %所求问题目标函数梯度 g=[2*X(1)-2*X(2)+2,-2*X(1)+4*X(2)-X(3)+3,2*X(3)-X(2)-1,2*X(4)]; end function [ x,val,k ] = frcg( fun,gfun,x0 ) %功能：用FR共轭梯度法求无约束问题最小值 %输入：x0是初始点，fun和gfun分别是目标函数和梯度 %输出：x、val分别是最优点和最优值，k是迭代次数 maxk=5000;%最大迭代次数 rho=0.5;sigma=0.4;
天津大学最优化方法复习题
《最优化方法》复习题 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max 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 非空集合n R 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 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ .
最优化计算方法课后习题答案----高等教育出版社。施光燕
习题二包括题目： P36页 5（1）（4） 5（4） 习题三 包括题目：P61页 1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)11/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ? ++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0)1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-?? =?-?= ?-??
最优化方法习题一
习题一 一、考虑二次函数f(x)= x x x x x x 212 2212132+-++ 1) 写出它的矩阵—向量形式: f(x)=x Qx b x T T +2 1 2) 矩阵Q 是不是奇异的? 3) 证明: f(x)是正定的 4) f(x)是凸的吗? 5) 写出f(x)在点x =) 1,2(T 处的支撑超平面(即切平面)方程 解:1) f(x)= x x x x x x 212 2212 132+-++ =???? ??x x 2121???? ??6222???? ??x x 21+??? ? ??-1 1T ??? ? ??x x 21 其中 x=? ?? ? ??x x 21 ,Q=???? ??6222 , b=???? ??-11 2) 因为Q=??? ? ??6222 ,所以 |Q|=6222=8>0 即可知Q 是非奇异的 3) 因为|2|>0, 6 22 2=8>0 ,所以Q 是正定的,故f(x)是正定的 4) 因为 )(2 x f ? =??? ? ??6222,所以|)(2 x f ?|=8>0,故推出)(2 x f ? 是正定的,即 )(2 x f ? 是凸的 5) 因为)(x f ? = 1) x 6x 1,2-x 2x (22121+++T ,所以)(x f ?=(5,11) 所以 f(x)在点x 处的切线方程为5( 21-x )+11(12 -x )=0 二、 求下列函数的梯度问题和Hesse 矩阵 1) f(x)=2 x 12 +x x x x x 2392 312 1 +++x x x 2322+ 2) f(x)=ln( x 1 2 + x x x 22 21+) 解: 1) )(x f ?= (,94 3 2 1 x x x ++ 263 2 1 +++x x x , x x 2 1 9+)
最优化大作业
最优化方法大作业 ---------用优化算法求解函数最值问题
摘要 最优化(optimization) 是应用数学的重要研究领域.它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。最优化问题一般包括最小化问题和最大化问题，而最大化问题可以通过简单的转化使之成最最小化问题。最小化问题分为两类，即约束最小化和无约束最小化问题。在此报告中，前两个问题属于无约束最小化问题的求解，报告中分别使用了“牛顿法”和“共轭梯度法”。后两个问题属于有约束最小化问题的求解，报告中分别用“外点法”和“内点法”求解。虽然命名不一样，其实质都是构造“惩罚函数”或者“障碍函数”，通过拉格朗日乘子法将有约束问题转化为无约束问题进行求解。再此报告中，“外点法”和“内点法”分别用了直接求导和调用“牛顿法”来求解无约束优化问题。 在此实验中，用“共轭梯度法”对“牛顿法”所解函数进行求解时出现错误，报告中另取一函数用“共轭梯度法”求解得到正确的结果。此实验中所有的函数其理论值都是显见的，分析计算结果可知程序正确，所求结果误差处于可接受范围内。 报告中对所用到的四种方法在其使用以前都有理论说明，对“外点法”中惩罚函数和“内点法”中障碍函数的选择也有相应的说明，另外，对此次试验中的收获也在报告的三部分给出。 本报告中所用程序代码一律用MATLAB编写。 【关键字】函数最优化牛顿法共轭梯度法内点法外点法 MATLAB
一，问题描述 1， 分别用共轭梯度发法和牛顿法来求解一下优化问题 ()()()()()4 41432243221102510min x x x x x x x x x f -+-+-++= 2， 分别用外点法和内点发求解一下优化问题 ?? ?≥-++0 1.min 212 231x x t s x x 二、问题求解 用牛顿法求解 ()()()()()4 414 322 432 21102510min x x x x x x x x x f -+-+-++= 1.1.1问题分析： 取步长为1而沿着牛顿方向迭代的方法称为牛顿法，在牛顿法中，初始点的取值随意，在以后的每次迭代中，()[] ()k k k k x f x f x x ??-=-+1 21，直到终止条件成立时停止。 1.1.2 问题求解 注：本程序编程语言为MATLAB ，终止条件为()162 110-≤?x f ，初始取值为 [10 10 10 10] M 文件（求解函数）如下： function s=newton1(f,c,eps) %c 是初值，eps 为允许误差值 if nargin==2 eps=; elseif nargin<1 error('') % return end syms x1 x2 x3 x4
大连理工大学优化方法上机大作业
2016年大连理工大学优化 方法上机大作业 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
2016年大连理工大学优化方法上机大作业学院： 专业： 班级： 学号： 姓名： 上机大作业1： 1.最速下降法：
function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; end function g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)^2-x(2)); g(2) = 200*(x(2)-x(1)^2); end function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=1000 dk = -gk;
ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; gk = grad(xk); res = norm(gk); fprintf('--The %d-th iter, the residual is %f\n',k,res); end x_star = xk; end >> clear >> x0=[0,0]'; >> eps=1e-4; >> x=steepest(x0,eps)