资源描述：
《最优化方法讲稿new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章最优化方法第五章最优化方法在国民经济各部门和科学技术的各个领域中普遍存在着最优化问题(如工业设计中的参数选择,资源合理分配等等).最优化问题的解就是从所有可能的方案中选出最合理的,以达到最优目标的方案--最优方案.搜寻最优方案的方法就是最优化方法.随着计算机科学的发展和广泛应用,应用最优化方法解决问题的领域不断扩大,解决问题的深度不断深化,最优化的理论和方法也不断得到普及和发展.近几年的大学生数学建模竞赛题目很多都与最优化问题有关(如飞行管理问题(95A),最优捕鱼策略(96A),节水洗衣机(96B),零件参数设计(97A),投资的收益和风险(98A),钢管订购和
2、运输(2000B)).这里,我们主要介绍最典型的优化模型及应用背景、相关的优化理论和最常用的优化算法.建立最优化问题的数学模型,首先要确定问题的决策变量,用n维向量表示,然后构造模型的目标函数f(X)和决策变量的允许取值范围,称可行域,常用一组不等式来界定,称为约束条件.一般地,这类模型可表述成如下形式:(0.1)s.t.(0.2)只满足(0.2)的解x称可行解,同时满足(0.1)、（0.2）的解152第五章最优化方法称为最优解.§1线性规划如果(0.1)(0.2)中的目标函数f(x)和约束条件都是线性函数,该模型称为线性规划.模型为（LP）1．1线性规划模型的标准型:
3、(1)s.t.(2)其中线性规划的其他形式可通过形式变换和添加松弛变量而化为标准型.1．2求解方法:单纯形方法是通过迭代来求问题（LP）的最优解，在一个基本可行解非最优时，确定一个更优的基本可行解，形成一个使目标函数单调减的基本可行解序列，经有限步即可求得最优解1．3模型示例:例1.1运输问题:设有m个生产地点可供应物资,其供应量(产量)分别为.有n个销售地点,其需求量分别为,假设供需平衡既.用152第五章最优化方法表示由运输单位物资的运价,如何确定一种调运方案才能使总运输费用最小.用表示由调运物资的数量,则运输问题的数学模型为:s.t.1．4利用MATLAB优化工具箱
4、解线性规划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)用于求解模型s.t.2)、3)、4)用于求解152第五章最优化方法s.t.例1求解线性规划问题s.t.其中c=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6]A=[0.010.010.010.030
5、.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.08];b=[850;700;100;900];vlb=[0;0;0;0;0;0];vub=[];x=linprog(c,A,b,[],[],vlb,vub)f=c*x152第五
6、章最优化方法例2求解线性规划问题解用命令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,A,b,Aeq,beq,vlb,vub,x0)z=c*x§2整数线性规划在某些线性规划问题中,决策变量只能取整数（如人数、机器的数量）,这时约束条件中还需添加变量取整的限制,这就是整数线性规划,模型的一般形式为152第五章最优化方法（ILP）如果其中只有部分变量取整数,称为混合整数规划.决策变量只能取整数0或1的称为0-1规划2
7、．1整数线性规划的求解方法2．1.1割平面法—用于求解纯整数规划2．1.2分枝定界法—用于求解混合整数规划.2．1．3穷举法-用于规模不大的整数问题的求解2．2建模示例例2.1背包问题：有一只背包(泛指仓库、船舱、卫星仓等)，最大装载重量为w单位。现有k种物品，每种的数量无限。第i种物品每件重量为，价值。每种物品各取多少装入背包，使其中的物品总价值最高。设取第i种物品件,则s.t.§3无约束优化无约束优化的模型为152第五章最优化方法它的最优解都是局部最优解,全局最优解只能从局部最优解的比较中得到.3．1最优解条件必要条件:若为的极小点，
