最优化方法讲稿

《最优化方法讲稿》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章最优化方法第五章最优化方法在国民经济各部门和科学技术的各个领域中普遍存在着最优化问题(如工业设计中的参数选择,资源合理分配等等).最优化问题的解就是从所有可能的方案中选出最合理的,以达到最优目标的方案--最优方案.搜寻最优方案的方法就是最优化方法.随着计算机科学的发展和广泛应用,应用最优化方法解决问题的领域不断扩大,解决问题的深度不断深化,最优化的理论和方法也不断得到普及和发展.近几年的大学生数学建模竞赛题目很多都与最优化问题有关(如飞行管理问题(95A),最优捕鱼策略(96A),节水洗衣机(96B),零件参数设计(97A),投资的收益和风险(98A),钢管订购和运输

2、(2000B)).这里,我们主要介绍最典型的优化模型及应用背景、相关的优化理论和最常用的优化算法.建立最优化问题的数学模型,首先要确定问题的决策变量,用n维向量表示Tx(x,x,,x),然后构造模型的目标函数f(X)和决策变12n量的允许取值范围,称可行域,常用一组不等式g(x)0(i1,2,,m)来i界定,称为约束条件.一般地,这类模型可表述成如下形式:min(max)zf(x)(0.1)xs.t.g(x)0,i1,2,,m(0.2)i*只满足(0.2)的解x称可行解,同时满足(0.1)、（0.2）的解xx127第五章最优化方法称为最优解.

3、§1线性规划如果(0.1)(0.2)中的目标函数f(x)和约束条件g(x)都是线性j函数,该模型称为线性规划.模型为minf(x)cx（LP）s.t.Axb,x01．1线性规划模型的标准型:minfcx(1)s.t.Axb(2)其中TTA(a),x(x,x,,x),b(b,b,,b),c(c,c,,c)ijmn12n12m12n线性规划的其他形式可通过形式变换和添加松弛变量而化为标准型.1．2求解方法:单纯形方法是通过迭代来求问题（LP）的最优解，在一个基本可行解非最优时，确定一个更优的基本可行解，形成一个使目标函数单调减的基本可行解序

4、列(1)(2)x,x,，经有限步即可求得最优解1．3模型示例:例1.1运输问题:设有m个生产地点A,A,,A可供应物资,12m其供应量(产量)分别为a,a,,a.有n个销售地点B,B,,B,12m12nmn其需求量分别为b1,b2,,bn,假设供需平衡既aibi.用cij表i1i1128第五章最优化方法示由A到B运输单位物资的运价,如何确定一种调运方案才能ii使总运输费用I最小.用x表示由A到B调运物资的数量,则运输问题的数学模ijii型为:mnminIcijxiji1j1nxijai,i1,2,,mj1ms.t.xijbi,j

5、1,2,,ni1x0ij1．4利用MATLAB优化工具箱解线性规划Matlab求解线性规划的命令为1)x=linprog(c,A,b,Aeq,beq)2)x=linprog(c,A,b,Aeq,beq,vlb,vub)3)x=linprog(c,A,b,Aeq,beq,vlb,vub,x0);x0表示初始点4)x=lp(c,A,b,Aeq,beq,vlb,vub,x0,options);x0表示初始点其中1)用于求解模型minZcxAxbs.t.Aeqxbeq2)、3)、4)用于求解minZcx129第五章最优化方法Axbs.t.Aeqxbeqvlbx

6、vub例1求解线性规划问题maxzcxAxbs.t.x0其中c=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6]A=[0.010.010.010.030.030.030.02000.050000.02000.050000.03000.08]b=[850;700;100;900]vlb=[0;0;0;0;0;0]vub=[]解用命令2）l11.mc=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.0

7、8];b=[850;700;100;900];vlb=[0;0;0;0;0;0];vub=[];x=linprog(c,A,b,[],[],vlb,vub)f=c*x130第五章最优化方法例2求解线性规划问题minz6x3x4x123s.t.xxx120123x30,10x502x203解用命令3)l12.mc=[6,3,4];A=[1,1,1;0,1,0];b=[120;50];vlb=[30,0,20];vub=[];x0=[0;0;0];Aeq=[1,1,1];Beq=120;x=lp(c