最优化方法练习题答案 下载本文

内容发布更新时间 : 2024/6/18 3:35:32星期一 下面是文章的全部内容请认真阅读。

(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软件求解下列问题:

minz?4x1?3x2?2x3maxz?3x1?2x2?5x3?2x4?3x5?2x1?5x2?3x3?4?4x?x?3x?3123(1)s.t.??x2?x3?1??xj?0或1(j?1,2,3)??x1?x2?x3?2x4?x5?4?7x?3x?4x?3x?81345;(2)s.t.???11x1?6x2?3x4?3x5?1?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];

A=[2,-5,3; -4,-1,-3;0,-1,-1]; b=[4; -3;-1];

[x, fval]=bintprog(f, A, b, [], []);

% 价值向量f

% 不等式约束系数矩阵A,[ ]中的分号“;”% 为行分隔符 % 不等式约束右端常数向量b

%调用函数bintprog。注意两个空数组的占位作用。

输出结果

x=

0 0

fval=

1

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- 1

运价/ 产粮 (元/吨) 区 化肥厂 A1 A2 A3 各区需要量/万吨 5 4 8 6 8 9 4 6 7 10 2 3 3 7 9 3 7 8 3 甲 乙 丙 丁 各厂供应量/万吨 解:设A、B、C三个化肥厂为A1、A2、A3,甲、乙、丙、丁四个产粮区为B1、B2、B3、B4;cij为由Ai运化肥至Bj的运价,单位是元/吨;xij为由Ai运往Bj的化肥数量(i=1,2,3;j=1,2,3,4)单位是吨;z表示总运费,单位为元,依题意问题的数学模型为:

该题可以用单纯形法或matlab自带工具箱命令(linprog)求解。

*9、求解下列不平衡运输问题(各数据表中,方框内的数字为单位价格cij,框外右侧的一列数为各发点的供应量ai,框底下一行数是各收点的需求量bj):

(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

地区 推销员 1 2 3 4 1 35 28 35 24 2 27 34 24 32 3 28 29 32 25 4 37 40 33 28 解:用求极大值的“匈牙利法”求解。 效率矩阵表示为:

?35??28?35??24?273424322829322537??M-Cij 40? 33??M=40 28???5??12?5??16?13616812118153??行约简 0? 7??12???2??12?0??8?10611091137?2?0??列约简 ?120? ??(0)2??标号 ?4???810611(0)680*4(0)??*0??2?所画()0元素少于n4??(n=4),未得到最优解,需要继续变换矩阵(求能覆盖所有0元素的最少数直线集合):

?2??12??(0)?8?10611(0)680*4(0)?√ ?*0?√ ?2? 4??√ 未被直线覆盖的最小元素为cij=2,在未被直线覆盖处减去2,在直线交叉处加上2。

??∴得最优解:?????100000010??01?标号 ? 10?00??0∴使总利润为最大的分配任务方案为:

1→1,2→4,3→3,4→2

此时总利润W=35+40+32+32=139

练习题三

1、用法求解问题

的近似最优解,已知?(t)的单谷区间为[0,3],要求最后区间精度??0.5。 答:t=;最小值.(调用函数) 2、求无约束非线性规划问题

22?x3?2x1 min f(x1,x2,x3)=x12?4x2的最优解

解一:由极值存在的必要条件求出稳定点:

?f?f?f?2x1?2,?8x2,?2x3,则由?f?x??0得x1?1,x2?0,x3?0 ?x1?x2?x3再用充分条件进行检验:

?2f?2f?2f?2f?2f?2f?0,?0,?0 ?2,2?8,2?2,2?x1?x2?x1?x3?x2?x3?x1?x2?x3?200???即?2f??080?为正定矩阵得极小点为x*?(1,0,0)T,最优值为-1。

?002???解二:目标函数改写成

22?x3?1 min f(x1,x2,x3)=(x1?1)2?4x2易知最优解为(1,0,0),最优值为-1。

3、用最速下降法求解无约束非线性规划问题。 其中X?(x1,x2)T,给定初始点X0?(0,0)T。

??f(x)???(x)??1?4x?2x?112???解一:目标函数f(x)的梯度?f(x)?? ??1?2x?2x?f(x)???12???(x)??2??1???1??f(X(0))???令搜索方向d(1)???f(X(0))???再从X(0)出发,沿d(1)方向作一维寻

??1??1??0???1?????优,令步长变量为?,最优步长为?1,则有X(0)??d(1)??????????

?0??1????故f(x)?f(X(0)??d(1))?(??)???2(??)2?2(??)???2??2?2???1(?)

?0???1???1?令?1'(?)?2??2?0可得?1?1 X(1)?X(0)??1d(1)????????? 求出X(1)点之后,

?0??1??1???1??1?(2)(1)与上类似地,进行第二次迭代:?f(X)??? 令d???f(X)???

??1??1?(1)令步长变量为?,最优步长为?2,则有 故

f(x)?f(X(1)??d(2))?(??1)?(??1)?2(??1)2?2(??1)(??1)?(??1)2?5?2?2??1??2(?)'(?)?10??2?0可得 ?2?令?2??1?1?1???0.8?1 X(2)?X(1)??2d(2)???????? ?5?1?5?1??1.2?