优化小练习

《优化小练习》由会员分享，可在线阅读，更多相关《优化小练习（14页珍藏版）》请在装配图网上搜索。

1、1优化模型及其求解1.1案例：背包问题有一组物品S,共有9件，其中第i件重”.，价值七，从S中取出一些物品出来装背包，使总价值最大，而不超过总重量的给定上限30kg。i123456789wi(kg)2112.5106543七(元)104530100150902001803001.1.1问题分析这是一个典型的最优化问题，优化目标是总价值最大，决策是决定装哪些物 品，而装载物品又受到背包所能承受重量30kg的限制。因此可以建立该问题的 最优化数学模型，而且是01整数规划模型。1.1.2变量与符号说明七：用来表示是否装载第i件物品，如果 =0表示不装载该物品，如果七二1表 示装载该物品(i = 1,

2、2,9 )，令x = G,%,xj。w :第i件物品重量(i = 1,2,.,9 )，单位：kg。七：第i件物品价值(i = 1,2,.,9 )，单位：元。f (X):表示按照决策x，得到的装载物品的总价值，单位：元。1.1.3模型建立通过前面的分析及变量的定义，可得f (X) = 29 U.X.。i=1原问题抽象为如下的01整数线性规划模型：min f (x) = 8 v xi=18 w x 30 s.t. i i i=1x = 0或x = 1(i = 1,2, ,9)ii1.1.4模型求解及结果可以采用求解线性规划的Lindo软件求解，下面采用求解可以求解非线性规划的 Lingo软件求解。

3、Lingo功能非常强大，其语法本身较复杂，这里只用到最简单的语法。直接参看 代码。Lindo基本语法(1) 模型用“MODEL:”开始，“END”结束，参考下面的Lingo程序；(2) 语句用分号中断。注释行用感叹号开头，通样是分号结束。(3) 如果变量只取0或1，则用BIN设置，比如BIN(x2)，表示变量x2只 能取0或1。(4) 如果变量只取整数，则用GIN设置，比如GIN(x2)，表示变量x2为整 数变量。Lingo程序如下：!求解背包问题的线性整数规划模型(0 1整数规划)；MODEL:!目标函数；max = 10*x1+ 45*x2+30*x3+100*x4+150*x5+90*x

4、6+200*x7+180*x8+300*x9;!重量约束；2*x1+x2+x3+2.5*x4 +10*x5 +6*x6+ 5*x7 + 4*x8+ 3*x9=30;!整数约束的设置;BIN(x1);BIN(x2);BIN(x3);BIN(x4);BIN(x5);BIN(x6);BIN(x7);BIN(x8);BIN(x9);END求解显示结果:Global optimal solution found at iteration:0Objective value:1015.000VariableValueReduced CostX11.000000-10.00000X21.000000-45.0

5、0000X31.000000-30.00000X41.000000-100.0000X51.000000-150.0000X60.000000-90.00000X71.000000-200.0000X81.000000-180.0000X91.000000-300.0000RowSlack or SurplusDual Price11015.0001.00000021.5000000.000000结果显示已经找到了最优解。通过结果可见：除了不装载第6件物品外，其余全部装载，这种装包方法达 到总价值最大为1015元。下面介绍其它求解方法。1.1.5贪婪法建立优选指标gj = W（i = 1，2,

6、 ,n），即第i件物品单位重量的价值（元/kg）。i选择装背包的物品时，就从优选指标gi中最大的开始选，直到不能再装为止。由已知数据，可得i123456789gi5453040151540451001.1.6贪婪法求解程序%背包问题求解得贪婪算法实现 w=2 1 1 2.5 10 6 5 4 3;v=1045 30 100 150 90 200 180 300;g=v./w; %单位质量的价值（指标） maxw=30;%对指标排序，以便根据指标选择物品 y,idx=sort（g）;curw =0;%存储当前装的总重curv =0;%存储当前装的价值hasidx=; %存储当前装的物品序号for

7、 i=length(g):-1:1, %从指标g最大的开始选择id = idx(i);%important if curw + w(id) = maxw, curw = curw + w(id); curv = curv + v(id); hasidx = hasidx ,id; elsebreak;%结束，不能再装end enddisp(sprintf(总共装载物品数=%5d件 ,length(hasidx)disp(sprintf(质量=%10.2fkg ,curw)disp(sprintf(价值=%10.2f元，sum(v(hasidx)% 实际上 curw = sum(w(hasidx

8、)% curv =sum(v(hasidx)1.1.7贪婪法求解结果运行程序输出为：总共装载物品数=7件质量=22.50kg价值=945.00元按照贪婪法策略，得到装载物品的顺序依次为：9，8, 2, 7, 4，3，6。思考：以上装载结果是否达到最优？1.1.8穷举法求解程序%背包问题求解得穷举法得到最优解的程序w=2 1 1 2.510 6 5 4 3;%各件物品重量v=1045 30 10015090 200180300;%价值maxw=30; %背包承受重量上限optvalue = -1; %最优目标(最大价值)初始化for x1=0:1,for x2=0:1,for x3=0:1,fo

9、r x4=0:1,for x5=0:1,for x6=0:1,for x7=0:1,for x8=0:1,for x9=0:1,x=x1 x2 x3 x4 x5 x6 x7 x8 % 决策向量%不超过重量限制，也要比以前装包方案好if (dot(x,w)optvalue),op%存储；optvalue=dot(% 存储；endendendendendendendendendendhasidx = find(optx=0);optxdisp(sprintf(总共装载物品数=%5d件 ,length(hasidx)disp(sprintf(质量=%10.2fkg ,dot(optx,w)disp(

10、sprintf(价值=%10.2f元，dot(optx,v)%实际上： dot(optx,v)=sum(v(hasidx) %dot(optx,w)=sum(w(hasidx)1.1.9穷举法程序运行结果总共装载物品数=8件质量=28.50kg价值=1015.00元hasidx =12345789只有编号为6的物品没有装上。1.2案例：高速公路问题A城和B城之间准备建一条高速公路，B城位于A城正南20公里和正东 30公里交汇处，它们之间有东西走向连绵起伏的山脉。公路造价与地形特点有 关，图4.2.4给出了整个地区的大致地貌情况，显示可分为三条沿东西方向的地 形带。你的任务是建立一个数学模型，在

11、给定三种地形上每公里的建造费用的情 况下，确定最便宜的路线。图中直线AB显然是路径最短的，但不一定最便宜。 而路径ARSB过山地的路段最短，但是否是最好的路径呢？你怎样使你的模型 适合于下面两个限制条件的情况呢？1. 当道路转弯是，角度至少为1400。2. 道路必须通过一个已知地点（如P）。1.2.1问题分析在建设高速公路时，总是希望建造费用最小。如果要建造的起点、终点在同 一地貌中，那么最佳路线则是两点间连接的线段，这样费用则最省。因此本问题 是一个典型的最优化问题，以建造费用最小为目标，需要作出的决策则是确定在 各个地貌交界处的汇合点。1.2.2变量说明七：在第i个汇合点上的横坐标（以左下

12、角为直角坐标原点），1=1，2,。，4；x =30 （指目的地B点的横坐标），设x = x ,x ,x ,x T ;51234七：第，段南北方向的长度（=1，2，。，5）；S.：在第，段上地所建公路的长度（=1，2，。，5）； 由问题分析可知S = J l; + x：平原每公里的造价 C2:高地每公里的造价 C3:高山每公里的造价（单位（单位（单位S 2 = J12 + （X- x）2S =3S4 = Jl2 + （X3 - X4）2S =弋 12 + （X 一 X ）2 万元/公里）5 万元/公里） 万元/公里）,a；+（ x2 - x3）21.2.3模型假设1、假设在相同地貌中修改高速公路

13、，建造费用与公路长度成正比；2、假设在相同地貌中修改高速为直线。在理论上，可以使得建造费用最少， 当然实际中一般达不到。1.2.4模型建立在A城与B城之间建造一条高速公路的问题可以转化为下面的非线性规划 模型。优化目标是在A城与B城之间建造高速公路的费用。min f （x） = CS + C S + C S + C S + CS1 12 23 32 41 5s .t. 0 x 30（i = 1,2,3,4）1.2.5模型求解这里采用Matlab编程求解。模型求解时，分别去C.如下。平原每公里的造价C1：=400 （单位：万元）高地每公里的造价C2：=800 （单位：万元）高山每公里的造价C3：

14、=1200 （单位：万元）（注意：实际建模时必须查找资料来确定参数或者题目给定有数据）输入主程序model_p97.m，运行结果如下：model_p97optans =2.2584e+004len =38.9350ans =12.173114.332315.667717.8269求解程序见附录。1.2.6模型结果及分析通过求解可知，为了使得建造费用最小。建造地点的选择宜采取下列结果。x =12.1731,x =14.3323,x =15.6677,x： =17.8269.建造总费用为2.2584亿元。总长度为38.9350公里。1.2.7求解模型的主程序文件程序名：model_p97funct

15、ion x=model_p97%数学建模教材 P97高速公路clear allglobal C LC=4008001200;L=4 4 4 4 4;x=fmincon（objfun 97,1,1,1,1,zeros（1,4）,on es(1,4)*30,mycon_p97);optans=objfun_97(x)C=ones(3,1);len = objfun_97(x)2、模型中描述目标函数的Matlab程序objfun_97.mfunction obj=objfun_97(x) global C Lobj= C(1)*sqrt(L(1)A2+x(1)A2) +C(2)*sqrt(L(2)A

16、2+(x(2)-x(1)A2) + .C(3)*sqrt(L(3)A2+(x(3)-x(2)A2) + C(2)*sqrt(L(4)A2+(x(4)-x(3)A2)+.C(1)*sqrt(L(5)A2+(30-x(4)A2);3、模型中描述约束条件的Matlab函数mycon_p97.mfunction c,ceq=mycon_p97(x) %c(1)=x(1)-x(2);c(2)=x(2)-x(3);c(3)=x(3)-x(4);c(4)=x(4)-30;ceq=;1.3随机跳跃法1.3.1随机跳跃法简介对于如下的优化模型，可以采用随机跳跃法求解。min f (X)Xs.t. l x u ,

17、 i = 1,2, , n, X g Eni i i思路：产生若干组0,1均匀分布的随机数，然后求出对应每组随机数的X，随机 产生m组这样的点X，然后从这些点中找出目标函数的最小值，则找到一个近似 最优解。I +七()1 + r (u -l )2 222特点：1、方法简单，但并不适用于变量很多的情形。如果不考虑运行效率，倒 是可以用该方法一试。随机产生的点越多，就越接近于最优解。2、一般不用于实时系统。1.3.2求解高速公路问题的随机跳跃法程序程序：solvP97rand.m%2004-12-3%随机跳跃法示例：求解高速公路问题%global C LC=4008001200;L=4 4 4 4

18、 4;time_begin = clock;N=4;%决策变量个数TotalCount=1e5;a=0;b=30;opt_obj = inf;%initopt_dec = zeros(1,4);for c=1:TotalCount,for i=1:N,x(i)=a + rand*(b-a);end %for icur_obj = objfun_97(x);if cur_obj opt_obj,opt_obj = cur_obj;opt_dec = x;endend %for cdisp(sprintf(最优目标= %20.6f,opt_obj)for i=1:N,disp(sprintf(x(

19、%d)=%20.4f,i,x(i)endexp_time =etime(clock,time_begin)C=ones(3,1);%相对于讲目标函数中单价设为1,则计算结果应为总长度S1+S2+S3+S4+S5len = objfun_97(opt_dec)1.3.3程序运行结果运用随机跳跃法搜索高速问题的近似最优解，程序输出结果如下：最优目标= 22623.036913x(1)=18.1229x(2)=0.5607x(3)=28.1015x(4)=24.4806exp_time =15.5500len =38.6446发现超出最优值0.17%，可见已经非常接近最优值了，这里采用随机跳跃法 的

20、效果较好。思考：为什么随机跳跃法在这里运用的效果这么好？1.4网格法1.4.1网格法简介对于如下的优化模型，也可以采用网格法求解。min f (X)Xs.t. l x u , i = 1,2, , n, X g Eni i i思路：将各决策变量的取值区间等分为多个区间，比如m等分，而在搜索中对 各决策变量的取值，只从这等分点上取出组合，各变量有m+1个可能的取值。 由于m等分后，各决策变量就只搜索m+1个点，模型有n个决策变量，则要搜 索(m +1)n个可行解。然后从这些点中找出目标函数的最小值，则找到一个近似最优解。特点：1、 方法简单，并不适用于变量很多的情形。如果不考虑运行效率，倒是 可

21、以用该方法一试。2、 如果要结果更精确，m可以取更大些，就越接近于最优解，当如搜索 点更多，更费时。3、 一般不用于实时系统。1.4.2求解高速公路问题的网格法程序%2004-12-3%网格法示例：求解高速公路问题%clear allglobal C LC=4008001200;L=4 4 4 4 4;time_begin = clock;N=4;%决策变量个数a=0;b=30;opt_obj = inf;%initopt_dec = zeros(1,4);gridnum=30;step=b/gridnumcount=0;for x1=0:step: b,for x2=0:step:b,for

22、 x3=0:step:b,for x4=0:step:b,x = x1 x2 x3 x4;count=count+1;cur_obj = objfun_97(x);if cur_obj opt_obj, opt_obj = cur_obj; opt_dec = x;endend %for x4end %for x3end %for x2end %for x1countdisp(sprintf(最优目标= %20.6f,opt_obj)for i=1:N,disp(sprintf(x(%d)=%20.6f,i,x(i) endexp_time =etime(clock,time_begin)C=

23、ones(3,1);%相对于讲目标函数中单价设为1,则计算结果应为总长度S1+S2+S3+S4+S5len = objfun_97(opt_dec)1.4.3程序运行结果count =923521最优目标= 22603.376739x(1)=30.000000x(2)=30.000000x(3)=30.000000x(4)=30.000000exp_time =105.7900len =39.31801.5实验：开放式基金的投资问题某开放式基金现有总额为15亿元的资金可用于投资，目前共有8个项目可 供投资者选择。每个项目可以重复投资，根据专家经验，对每个项目投资总额不 能太高，且有个上限。这些

24、项目所需要的投资额已经知道，在一般情况下，投资 一年后各项目所得利润也可估计出来，见表一：表1投资项目所需资金及预计一年后所得利润单位：万元项目编号A 1A2A3A4A5A 6A7A8投资额67006600485055005800420046004500预计利润11391056727.51265116071418401575上限3400027000300002200030000230002500023000请帮助该公司解决以下问题:1、就表一提供的数据，试问应该选取哪些项目进行投资，使得第一年所得利润 最大？2、在具体对这些项目投资时，实际还会出现项目之间相互影响等情况。公司在 咨询了有关专家

25、后，得到如下可靠信息：1）如果同时对第1个和第3个项目投资，它们的预计利润分别为1005万元 和1018. 5万元；2）如果同时对第4、5个项目投资，它们的预计利润分别为1045万元和1276 万元；3）如果同时对第2、6、7、8个项目投资，它们的预计利润分别为1353万 元、840万元、1610万元、1350万元；4）如果考虑投资风险，则应该如何投资使得收益尽可能大，而风险尽可能 的小。投资项目总风险可用所投资项目中最大的一个风险来衡量。专家 预测出的投资项目A.的风险损失率为，数据见表二。表2投资项目的风险损失率项目编号风险损失率A1A2A3A4A 5A6A7A 8q(%)3215.52331356.54235由于专家的经验具有较高的可信度，公司决策层需要知道以下问题的结果:（1）如果将专家的前3条信息考虑进来，该基金该如何进行投资呢？（2）如果将专家的4条信息都考虑进来，该基金又应该如何决策？开放式基金一般要保留适量的现金，降低客户无法兑付现金的风险。在这种情况 下，将专家的4条信息都考虑进来，那么基金该如何决策，使得尽可能的降低风 险，而一年后所得利润尽可能多？