最优化方法练习题答案.docx
- 文档编号:1427150
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:40
- 大小:84.98KB
最优化方法练习题答案.docx
《最优化方法练习题答案.docx》由会员分享,可在线阅读,更多相关《最优化方法练习题答案.docx(40页珍藏版)》请在冰点文库上搜索。
最优化方法练习题答案
练习题一
1建立优化模型应考虑哪些要素?
答:
决策变量、目标函数和约束条件'
2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。
minf(x)
答:
针对一般优化模型s.tgix0,i1,2,Lm,讨论解的可行域D,若存在一点X*D,
hjx0,j1,L,p
对于XD均有f(X*)f(X)则称X*为优化模型最优解,最优解存在;迭代算法的收敛性是指
迭代所得到的序列X⑴,X⑵丄,X(K)L,满足f(X(K1))f(X(K)),则迭代法收敛;收敛的停止准
练习题二
1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3,欲出价收购(可能用于生产附加值更高的产品)。
如果你是该公司的决策者,对这3种资源的收购报价是多少?
(该问题称为例2.1的对偶问题)。
解:
确定决策变量对3种资源报价y1,y2,y3作为本问题的决策变量。
确定目标函数问题的目标很清楚一一“收购价最小”。
确定约束条件资源的报价至少应该高于原生产产品的利润,这样原厂家才可能卖。
因此有如下线性规划问题:
minw170y1100y2150y3
’2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)答:
略。
3、用单纯形法求解下列线性规划问题:
minzx1
X2
X3
min
z4
X2
X3
X1X2
2X3
2
X12X2
X3
2
(1)
2x1X2
s.t.
X3
3;
(2)s.t.
X2
2x3
X4
2
X1
X3
4
X2
X3
X5
5
X1,X2,X3
0
xi0
(i
1,2,
5)
解:
(1)引入松弛变量
X4,X5
,X6
GjT
1
-1
1
0
0
0
Cb
基
b
X1
X2
X3
X4
X5
X6
0
X4
2
1
[1]
-2
1
0
0
0
X5
3
2
1
1
0
1
0
0
X6
4
-1
0
1
0
0
1
cj-zj
1
-1
1
0
0
0
因检验数02<0,故确定X2为换入非基变量,以X2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量X4作为换出的基变量。
GjT
1
-1
1
0
0
0
Cb
基
b
X1
X4
X3
X4
X5
X6
-1
X2
2
1
1
-2
1
0
0
0
X5
1
1
0
[3]
-1
1
0
0
X6
4
-1
0
1
0
0
1
cj-zj
2
0
-1
1
0
0
因检验数03<0,故确定X3为换入非基变量,以X3的系数列的正分量对应去除常数列,最小比值所在行对应的基变量X5作为换出的基变量。
a—
1
-1
1
0
0
0
CB
基
b
X1
X2
X5
X4
X5
X6
-1
X2
8/3
5/3
1
0
1/3
2/3
0
1
X3
1/3
1/3
0
1
-1/3
1/3
0
0
X6
11/3
-4/3
0
0
1/3
-1/3
1
Cj-zj
7/3
0
3
2/3
1/3
0
因检验数q>0,表明已求得最优解:
X*(0,8/3,1/3,0,0,11/3),去除添加的松弛变量,原问题
的最优解为:
X*(0,8/3,1/3)。
(2)根据题意选取X1,X4,X5,为基变量:
ci—
0
-1
1
0
0
Cb基b
X1
X2
X3
X4
X5
0x12
1
-2
1
0
0
0
X4
2
0
[1]
-2
1
0
0
X5
5
0
1
1
0
1
cj-z
0
-1
1
0
0
因检验数C2<0最小,故确定X2为换入非基变量,以X2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量X4作为换出的基变量。
cjT
0
-1
1
0
0
Cb基b
X1
X2
X3
X4
X5
0x16
1
0
-3
2
0
-1X22
0
1
-2
1
0
0X53
0
0
[3]
-1
1
cj-z
0
0
-1
1
0
因检验数03<0最小,故确定X3为换入非基变量,以X1的系数列的正分量对应去除常数列,最小比值所在行对应的基变量X5作为换出的基变量。
cjT
0
-1
1
0
0
Cb基b
X1
X2
X3
X4
X5
0x19
1
0
0
一工-”
1
1
-1X24
0
1
0
1/3
2/3
1X31
0
0
1
-1/3
1/3
cj-z
0
0
0
2/3
1/3
因检验数Oj>0,表明已求得最优解:
X*(9,4,1,0,0)。
4、分别用大M法、两阶段法和Matlab软件求解下列线性规划问题:
minz
4x1
x2
maxz
10x1
15x2
12X3
3x1
X2
3
1
5x1
3x2
x3
9
(1)s.t.9X1
3x2
6;
(2)
5x1
st
6x2
15X3
15
X1
2x2
3
2x
1x2
x3
5
X1,X2
0
X1,X2,X30
解:
(1)大M法
根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题
cjT
4
1
M
0
Cb
基
b
X1
X2
X3
X4
M
X3
3
[3]
1
1
0
0
X4
3
1
2
0
1
cj-z
4-3M
1-M
0
0
4
X1
1
1
1/3
1/3
0
0
X4
2
0
[5/3]
-1/3
1
cj-z
0
-1/3
M-4/3
0
4
X1
3/5
1
0
2/5
-1/5
1
X2
6/5
0
1
-1/5
3/5
cj-z
0
0
M-7/5
1/5
因检验数oj>0,表明已求得最优解:
X*(3/5,6/5)。
Matlab调用代码:
f=[4;1];
A=[-9,-3;1,2];
b=[-6;3];
Aeq=[3,1];
beq=3;
lb=[O;O];
[x,fval]=linprog(f,A,b,Aeq,beq,lb)
输出结果:
Optimizationterminated.
x=
0.6000
1.2000
fval=
3.6000
(2)大M法
a\mh////)j
引入松弛变量X4,X5,X6,X7构造新问题。
单纯形表计算略;当所有非基变量为负数,人工变量X7=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软件求解下列线性规划问题:
解:
用内点法的过程自己书写,参考答案:
最优解X[4/37/30];最优值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)
输出结果:
Optimizationterminated.
x=
1.3333
2.3333
0.0000
fval=
5.0000
&用分支定界法求解下列问题:
x=
33
y=
-39
最优解[33];最优值39
(2)调用matlab编译程序bbmethodf=[-7;-9];G=[-13;71];h=[6;35]
[x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;0],1)
x=
50
y=
-35
最优解[50];最优值35
7、用隐枚举法和Matlab软件求解下列问题:
min
z
4x1
3x2
2x3
maxz
3x12x
25x
32X43X5
2X1
5x2
3X3
4
X1
x2x3
2x4
x5
4
(1)s.t.
4x1
X2
3X3
3;
(2)
7x1
s.t.
3X3
4x4
3X5
8
X2
X3
1
11x1
6x2
3x4
3X5
1
Xj
0或1(j
1,2,3)
xj
0或1(j
1,2,
5)
解:
隐枚举法:
(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(fAb,[],[]);%调用函数bintprog。
注意两个空数组的占位作用。
输出结果
x=
fval=
2
(2)
调用代码:
f=[-3;-2;5;2;3];
A=[1,1,1,2,1;7,0,3,-4,3;-11,6,0,-3,3];
b=[4;8;-1];
[x,fval]=bintprog(f,A,b,[],[]);
%价值向量f
%不等式约束系数矩阵A,[]中的分号;”%为行分隔符
%不等式约束右端常数向量b
%调用函数bintprog。
注意两个空数组的占位作用。
输出结果
x=
1
1
0
0
0
fval=
-5
最优值5。
8某地区有A、B、C三个化肥厂,供应本地甲、乙、丙、丁四个产粮区。
已知各化肥厂可
供应化肥的数量和各产粮区对化肥的需要量,以及各厂到各区每吨化肥的运价如表2-28所示。
试
制定一个使总运费最少的化肥调拨方案。
表2-错误!
未指定顺序
运价/产粮\
(元/吨[区、化肥厂
甲
J
乙
丙
丁
各厂供应量/万吨
A1
5
8
7
3
7
A2
4
9
10
7
8
A3
8
4
2
9
3
各区需要量/万吨
6
6
3
3
解:
设A、B、C三个化肥厂为Ai、A2、A3,甲、乙、丙、丁四个产粮区为Bi、B2、B3、B4;
cj为由Ai运化肥至Bj的运价,单位是元/吨;xj为由Ai运往Bj的化肥数量(i=1,2,3;j=1,2,3,4)单位是吨;z表示总运费,单位为元,依题意问题的数学模型为:
该题可以用单纯形法或matlab自带工具箱命令(linprog)求解。
*9、求解下列不平衡运输问题(各数据表中,方框内的数字为单位价格cij,框外右侧的一列数
0
bj):
解答略。
10、一公司经理要分派4位推销员去4个地区推销某种商品。
推销员各有不同的经验和能力,
因而他们在不同地区能获得的利润不同,其获利估计值如表2-29所示。
公司经理应怎样分派才使
总利润最大?
■地K
推销员、
1
2
3
4
1
35
27
28
37
2
28
34
29
40
3
35
24
32
33
4
24
32
25
28
“匈牙利法”求解。
表2-错误!
未指定顺序。
解:
用求极大值的效率矩阵表示为:
35
27
28
37
513
12
3
28
34
29
40
12M-Cij
11
0
35
24
32
33
516
8
7
24
32
25
28
16M=40
15
12
210
6
(0)
2
10
9
0
*
12
0
6
11
11
3
0
2
1別约简6
(0)11
8
*
0
0
2
8
0
7
4
8标号(0)
4
4
(求能覆盖所有
需要继续变换矩阵
行约简
所画
()0兀素少于n(n=4),未得到最优解,
0元素的最少数直线集合):
2
10
6
(
y
0)
12
6
8
(
*
)
(0)1102
8(0)44
未被直线覆盖的最小元素为Cj=2,在未被直线覆盖处减去2,在直线交叉处加上2
1
0
00
二得最优解:
0
0
01
标号C
0
0
0
1
00
-••使总利润为最大的分配任务方案为:
1宀1,2宀4,3宀3,4宀2
此时总利润W=35+40+32+32=139
练习题三
1、用0.618法求解问题
的近似最优解,已知⑴的单谷区间为[0,3],要求最后区间精度0.5
答:
t=0.8115;最小值-0.0886.(调用golds.m函数)
2、求无约束非线性规划问题
minf(x「x2,x3)=x;4x;x;2x1
的最优解
解一:
由极值存在的必要条件求出稳定点:
2x1
X1
2,-
f
x
8X2,
f
X3
2x3,则由f
X
0得X1
1,X20,X30
再用充分条件进行检验:
2fc
2f
8,
2f
2,
2fc
2f
0,-
2f门
22,
2
2
0,-
0
X1
X2
X3
X-!
X2
X1X3
X2X3
2
0
0
即2f
0
8
0
为正定矩阵得极小点为
X*
(1,0,0)
T,最优值为-1。
0
0
2
解二:
目标函数改写成
minf(Xi,X2,X3)=(x
1)2
4x2x3
易知最优解为(1,0,0),最优值为-1。
3、用最速下降法求解无约束非线性规划问题。
其中X(X1,X2)T,给定初始点X0
(0,0)T。
解一:
目标函数f(x)的梯度
f(x)
f(x)
(X1)f(x)(X2)
4x-i2x2
2X|2x2
f(X(0))
1
1令搜索方向
1
d
(1)
f(X(0))
再从X(0)出发,
沿d⑴方向作一维寻优,令步长
变量为,最优步长为
则有
X(0)d
(1)
故f(x)f(X(0)
d
(1))(
2()2
2(
1(
令1()22
0可得1
x
(1)x(0)
1d
(1)
求出
X⑴点之后,与上类似地,
进行第二次迭代:
f(X⑴)
1
令d
(2)
1
f(X⑴)
令步长变量为,最优步长为
2,则有
故f(x)f(X⑴d⑵)
1)
(1)
2(
1)2
2(
1)(
1)
22
1)5212()令
2()10
20可得2
2d
(2)
0.8
1.2
f(X⑵)
0.2
0.2
此时所达到的精度f(X⑵)
0.2828
本题最优解
1
1.5,f(X)侶
解二:
利用
matlab程序求解
首先建立目标函数及其梯度函数的M文件
functionf=fun(x)
f=x
(1)-x
(2)+2*x
(1)*x
(1)+2*x
(1)*x
(2)+x
(2)*x
(2);
精心整理
functiong=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阵
14x-i2x2
12x12x2
f(x)
目标函数f(x)的梯度f(x)(x|)
f(x)
(X2)
计算If(X⑴)||0
1
本题最优解X1.5,f(X)侶
解二:
除了第3题建立两个M文件外,还需建立Hesse矩阵的M文件
利用matlab程序求解
首先建立目标函数及其梯度函数的M文件
functionf=fun(x)
f=x
(1)-x
(2)+2*x
(1)*x
(1)+2*x
(1)*x
(2)+x
(2)*x
(2);
functiong=gfun(x)
g=[1+4*x
(1)+2*x
(2),-1+2*x
(1)+2*x
(2)];
functionh=hess(x)
g=[42;22];
调用newton.m文件
精心整理
xO=[O,O];
[x,val,k]=newton('fun','gfun','hess',xO)
结果
x=[-1.0000,1.5000]
val=-1.2500
k=1
5、用Fletcher—Reeves法求解问题
10
其中X(x「X2)T,要求选取初始点X0(2,2)t,
Qf(x)
1
2
0x1
C(X1,X2)
0
G
2
50x2
第-
「次迭代:
令P0
r°
(4,100)T,
即,
X⑴X
(0)-
0p°
(1
.92,0)T
第二
二次迭代:
解一:
20,rf(x)(2x1,50x2)T.
050
ri(3.84,0)T,0也1!
3,piri。
p。
(3.846,0.15)T
l|r°『2000
第三次迭代:
D(0.1464,3.6)T……(建议同学们自己做下去,注意判别rj)
解二:
利用matlab程序求解
首先建立目标函数及其梯度函数的M文件
I
functionf=fun(x)
f=x
(1)A2+25*x
(2)*x
(2);
functiong=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、试用外点法(二次罚函数方法)求解非线性规划问题
22
minf(X)(x-i2)x2
s.t.g(X)X210
其中X(x1,x2)R2
解:
设计罚函数P(x,M)f(X)M*[g(X)F2
采用Matlab编程计算,结果x=[10];最优结果为1。
(调用waidianfa.m)
7、用内点法(内点障碍罚函数法)求解非线性规划问题:
解:
容易看出此问题最优解为x=[10];最优值为8.
给出罚函数为P(x,r)(为1)3X2r(1/(X11)1/X2)
令P(x,r)
3(x1)2
r
'2
0
P(x,r)r
;120
x
(X11)
X2X2
从而当r
0时,
x(r)
(1
■,r/3)1/21
X
■.r
0
(建议同学自己编程序计算)
minf(X)x:
x;
8、用乘子法求解下列问题h(X)xx20
lh|(X)x〔X220
解:
建立乘子法的增广目标函数:
令:
_区丄丄2x1(人x,2)0
x
解上述关于x的二元一次方程组得到稳定点
1
当乘子取2时,或发参数趋于无穷时,得到xx*即最优解。
1
(建议同学自己编程序计算)
练习题四
1、石油输送管道铺设最优方案的选择问题:
考察网络图4-6,设A为出发地,F为目的地,B,
C,D,E分别为四个必须建立油泵加压站的地区。
图中的线段表示管道可铺设的位置,线段旁的
数字表示铺设这些管线所需的费用。
问如何铺设管道才能使总费用最小?
图4-错误!
未指定顺序。
解:
?
第五阶段:
E1—F4;E2—F3;
第四阶段:
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、用动态规划方法求解非线性规划
解:
x-i9,x29,x39,最优值为9。
3、用动态规划方法求解非线性规划
解:
用顺序算法
阶段:
分成两个阶段,且阶段1、2分别对应“X2。
决策变量:
X!
X2
状态变量:
Vi,Wi分别为第j阶段第一、第
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法 练习题 答案