最优化方法练习题答案Word文档格式.docx
《最优化方法练习题答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《最优化方法练习题答案Word文档格式.docx（40页珍藏版）》请在冰点文库上搜索。
[1]
-2
3
cj-zj
因检验数02<
0，故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。
[3]
因检验数03<
0,故确定X3为换入非基变量，以X3的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X5作为换出的基变量。
a—
CB
8/3
5/3
1/3
2/3
-1/3
11/3
-4/3
Cj-zj
7/3
因检验数q>
0，表明已求得最优解：
X*（0,8/3,1/3,0,0,11/3），去除添加的松弛变量，原问题
的最优解为：
X*（0,8/3,1/3）。
（2）根据题意选取X1，X4，X5，为基变量：
ci—
Cb基b
0x12
cj-z
因检验数C2<
0最小，故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。
cjT
0x16
-3
-1X22
0X53
0最小，故确定X3为换入非基变量，以X1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X5作为换出的基变量。
0x19
一工-”
-1X24
1X31
因检验数Oj>
X*（9,4,1,0,0）。
4、分别用大M法、两阶段法和Matlab软件求解下列线性规划问题:
minz
4x1
x2
maxz
10x1
15x2
12X3
3x1
5x1
3x2
x3
9
（1）s.t.9X1
6；
（2）
st
6x2
15X3
15
2x2
2x
1x2
X1,X2
X1,X2,X30
（1）大M法
根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题
M
4-3M
1-M
[5/3]
M-4/3
3/5
2/5
-1/5
6/5
M-7/5
1/5
因检验数oj>
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，所以原问题无可行解
请同学们自己求解。
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];
[x,fval]=linprog（f,[],[],Aeq,beq,lb）
1.3333
2.3333
0.0000
5.0000
&
用分支定界法求解下列问题:
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）
50
-35
最优解[50];
最优值35
7、用隐枚举法和Matlab软件求解下列问题:
z
3x12x
25x
32X43X5
2X1
5x2
3X3
x2x3
2x4
x5
（1）s.t.
7x1
4x4
3X5
8
11x1
3x4
Xj
0或1（j
1,2,3）
xj
0或1（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软件求解：
调用代码：
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。
注意两个空数组的占位作用。
输出结果
（2）
f=[-3;
-2;
5;
2;
A=[1,1,1,2,1;
7,0,3,-4,3;
-11,6,0,-3,3];
8;
[x,fval]=bintprog（f,A,b,[],[]）;
%价值向量f
%不等式约束系数矩阵A，［］中的分号；
%不等式约束右端常数向量b
%调用函数bintprog。
-5
最优值5。
8某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。
已知各化肥厂可
供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。
试
制定一个使总运费最少的化肥调拨方案。
表2-错误!
未指定顺序
运价/产粮\
（元/吨［区、化肥厂
甲
J
乙
丙
丁
各厂供应量/万吨
A1
7
A2
10
A3
各区需要量/万吨
6
设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，框外右侧的一列数
bj）:
解答略。
10、一公司经理要分派4位推销员去4个地区推销某种商品。
推销员各有不同的经验和能力,
因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。
公司经理应怎样分派才使
总利润最大?
■地K
推销员、
35
27
28
37
34
29
40
24
32
25
“匈牙利法”求解。
未指定顺序。
用求极大值的效率矩阵表示为：
513
12
12M-Cij
11
516
16M=40
210
（0）
*
1別约简6
（0）11
8标号（0）
（求能覆盖所有
需要继续变换矩阵
行约简
所画
（）0兀素少于n（n=4）,未得到最优解,
0元素的最少数直线集合）：
（
y
0）
）
（0）1102
8（0）44
未被直线覆盖的最小元素为Cj=2,在未被直线覆盖处减去2,在直线交叉处加上2
00
二得最优解：
01
标号C
-••使总利润为最大的分配任务方案为:
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
2,-
f
x
8X2,
2x3，则由f
X
0得X1
1,X20,X30
再用充分条件进行检验:
2fc
2f
8,
2,
0,-
2f门
22,
X-!
X2
X1X3
X2X3
即2f
为正定矩阵得极小点为
X*
（1,0,0）
T,最优值为-1。
解二：
目标函数改写成
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）
（X1）f（x）（X2）
4x-i2x2
2X|2x2
f（X（0））
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⑴）
令d
（2）
f（X⑴）
令步长变量为，最优步长为
2，则有
故f（x）f（X⑴d⑵）
1）
（1）
1）（
1）
22
1）5212（）令
2（）10
20可得2
2d
（2）
0.8
1.2
f（X⑵）
0.2
此时所达到的精度f（X⑵）
0.2828
本题最优解
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）（x|）
（X2）
计算If（X⑴）||0
本题最优解X1.5，f（X）侶
除了第3题建立两个M文件外，还需建立Hesse矩阵的M文件
利用matlab程序求解
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（'
hess'
xO）
k=1
5、用Fletcher—Reeves法求解问题
其中X（x「X2）T，要求选取初始点X0（2,2）t,
Qf（x）
0x1
C（X1,X2）
G
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）
I
f=x
（1）A2+25*x
（2）*x
（2）;
g=[2*x
（1）,50*x
（2）];
调用frcg.m文件
x0=[2,2]'
;
epsilon=1e-6;
[x,val,k]=frcg（'
x0,epsilon）
x=1.0e-006*[0.2651,0.0088]
val=7.2182e-014
k=61
6、试用外点法（二次罚函数方法）求解非线性规划问题
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
P（x,r）r
；
120
（X11）
X2X2
从而当r
0时，
x（r）
■,r/3）1/21
■.r
（建议同学自己编程序计算）
minf（X）x：
8、用乘子法求解下列问题h（X）xx20
lh|（X）x〔X220
建立乘子法的增广目标函数：
令：
_区丄丄2x1（人x,2）0
解上述关于x的二元一次方程组得到稳定点
当乘子取2时，或发参数趋于无穷时，得到xx*即最优解。
练习题四
1、石油输送管道铺设最优方案的选择问题：
考察网络图4-6,设A为出发地，F为目的地，B，
C，D，E分别为四个必须建立油泵加压站的地区。
图中的线段表示管道可铺设的位置，线段旁的
数字表示铺设这些管线所需的费用。
问如何铺设管道才能使总费用最小？
图4-错误!
？
第五阶段：
E1—F4；
E2—F3；
第四阶段：
D1—E1?
—F?
7;
D2—E2—F?
?
D3—E1—F?
第三阶段：
C1—D1—E1?
12;
C2—D2—E2—F?
10;
C3—D2—E2—F?
C4—D3—E1—F?
第二阶段：
B1—C2—D2—E2—F?
13;
B2—C3—D2—E2—F?
?
第一阶段：
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阶段第一、第
升级会员 