优化模型实训

提要12几类典型优化问题及其软件解法3举例4最优化概论MATLAB优化工具箱简介最优化概论当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。数学建模竞赛中的优化问题2000B钢管订购和运输问题—二次规划2001B公交车优化调度2001C基金使用的最优策略-----线性规划2002B彩票中的数学2003B露天矿生产的车辆安排问题

2004A奥运会临时超市网点设计问题

2004D公务员招聘工作中录用方案—多目标规划2005BDVD在线租赁2006A出版社的资源配置问题

2007A乘公交，看奥运

2008B高等教育学费探讨2009B眼科病床的合理安排

数学建模竞赛中的优化问题2002B，彩票中的数学—约束非线性规划从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型．无约束最优化问题目标函数二、最优化问题的一般形式约束最优化问题约束函数最优解；最优值三、最优化问题分类分类1：无约束最优化约束最优化

非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数；

线性规划：目标函数与约束函数均为线性函数；分类2：线性规划非线性规划三、最优化问题分类(续）分类3（根据决策变量、目标函数和要求不同）整数规划动态规划网络规划随机规划几何规划多目标规划三、最优化问题分类(续）函数最优化组合最优化分类４函数最优化：决策变量是一定区间内的连续变量．组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合典型组合优化问题：旅行商问题；加工调度问题；0-1背包问题；图着色问题四、求解最优化问题的方法（1）传统优化方法-----基于导数的优化方法

无约束规划：梯度法、共轭梯度法、拟牛顿法

约束规划：序列二次规划法，罚函数法

线性规划：单纯形方法等（2）现代优化方法-----智能优化方法

遗传算法，模拟退火法，蚁群算法，粒子群算法神经网络算法，禁忌搜索算法等

为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法通常采用迭代法求最优解，过程是：五、构造数值优化算法的一般过程或迭代公式六、最优化方法的基本结构七、搜索算法结构框图线性搜索求，使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件？停k=k+1YesNo八、最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。九、MATLAB优化工具箱简介

1.功能（1）求解无约束条件非线性极小值；（2）求解约束条件下非线性极小值，包括目标逼近问题、极大-极小值问题和半无限极小值问题；（3）求解二次规划和线性规划问题；（4）非线性最小二乘逼近和曲线拟合；（5）非线性系统的方程求解；（6）约束条件下的线性最小二乘优化；（7）求解复杂结构的大规模优化问题。2.常用函数：

一元函数极小值X=fminbnd(‘F’,x1,x2,options)无约束极小值X=fminunc(‘F’,X0,options)X=fminsearch(‘F’,X0,options)线性规划

X=linprog(c,A,b,options)0-1整数规划X=bintprog(F

,options)二次规划X=quadprog(H,c,A,b,options)约束非线性规划极小值X=fmincon(‘FG’,X0,options)非线性最小二乘X=lsqnonlin(F,X0,options)目标达到问题X=fgoalattain(‘F’,x,goal,w)极小极大问题X=fminimax(‘FG’,x0)3.Options选项说明输入参数中可以用options，用于所有函数，其中包括有一下参数。（1）Display：结果显示方式，off不显示，iter显示每次迭代的信息，final为最终结果，notify只有当求解不收敛的时候才显示结果。（2）MaxFunEvals：允许函数计算的最大次数，取值为正整数。（3）MaxIter：允许迭代的最大次数，正整数。（4）TolFun：函数值（计算结果）精度，正整数。（5）TolX：自变量的精度，正整数。而且可以用函数optimset创建和修改。4.输出变量说明变量描述调用函数x由优化函数求得的值.若exitflag>0,则x为解;否则,x不是最终解,它只是迭代制止时优化过程的值所有优化函数fval解x处的目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflag描述退出条件:exitflag>0,表目标函数收敛于解x处exitflag=0,表已达到函数评价或迭代的最大次数exitflag<0,表目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:函数评价次数所有优化函数eg1

在区间（0，2π）上求函数sin(x)的最小值：eg2

对边长为3m的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？学会使用fminbnd函数:功能：找到固定区间内单变量函数的最小值。线性规划问题及其MATLAB解法1.线性规划的一般形式或线性规划问题及其MATLAB解法2.线性规划的matlab解法问题形式1：minz=CTx

S.t.Ax

≤b指令：（x，z）=linprog(f,A,b)问题形式2：minz=CTx

S.t.Ax

≤b

Aeqx

=beq指令：（x，z）=linprog(f,A,b,Aeq,beq)线性规划问题及其MATLAB解法问题形式3：minz=CTx

S.t.Ax

≤b

Aeqx

=beqlb≤x≤ub指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub)注：

若没有不等式约束,可用[]替代A和b,

若没有等式约束,可用[]替代Aeq和beq,

若某个xi下无界或上无界,可设定-inf或inf；x1+x2

5,-6

x1

10,

-1

x24;例:minZ=4x1

+3x2s.t.解：程序如下c=[4,3];a=[1,1];b=[5];vlb=[-6;-1];

%lowerboundofvector

x%vub=[10;4];%upperboundofvectorx%[X,z]=linprog(c,a,b,[],[],vlb,vub)例题：裁料问题在某建筑工程施工中需要制作10000套钢筋，每套钢筋由2.9m、2.1m和1.5m三种不同长度的钢筋各一根组成，它们的直径和材质不同。目前在市场上采购到的同类钢筋的长度每根均为7.4m，问应购进多少根7.4m长的钢筋才能满足工程的需要？

首先分析共有多少种不同的套裁方法，该问题的可能材料方案如表所示。表

材料方案表下料长度(m)裁料方案编号i123456782.9211100002.1021032101.510130234料头长度(m)0.10.30.901.10.20.81.4设以xi(i=1,2,…,8)表示按第i种裁料方案下料的原材料数量，则可得该问题的数学模型为：首先输入下列系数：f=[1;1;1;1;1;1;1;1];Aeq=[200000000210321010130234];beq=[100001000010000];lb=zeros(8,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,[],[],Aeq,beq,lb);习题1：生产计划的最优化问题某工厂生产A和B两种产品，它们需要经过三种设备的加工，其工时如表所示。设备一、二和三每天可使用的时间分别不超过12、10和8小时。产品A和B的利润随市场的需求有所波动，如果预测未来某个时期内A和B的利润分别为4和3千元/吨，问在那个时期内，每天应安排产品A、B各多少吨，才能使工厂获利最大？表生产产品工时表产品设备一设备二设备三A（小时/吨）334B（小时/吨）432设备每天最多可工作时数（小时）12108习题2：厂址选择问题

考虑A、B、C三地，每地都出产一定数量的原料，也消耗一定数量的产品（见表）。已知制成每吨产品需3吨原料，各地之间的距离为：A-B：150km，A-C：100km，B-C：200km。假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。表

A、B、C三地出产原料、消耗产品情况表地点年产原料（万吨）年销产品（万吨）生产费用（万元/万吨）A207150B1613120C240100

1.整数线性规划一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、0－1整数规划。整数线性规划(ILP)及其lindo解法部分或者全部为整数多目标规划及其求解方法多目标规划的一般形式则称为线性多目标规划。其中x=(x1,x2,…,xn)为一个n维向量；fi(x)为目标函数，hj(x)

gi(x)为约束函数。求解多目标规划的方法1、降维法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、极大极小法、理想点法等；2、分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。3、层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。主要目标法

其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。

线性加权法

其基本思想是：按照多目标fi(x)(i=1,2,…,m)的重要程度，分别乘以一组权系数λj(j=1,2,…,m)然后相加作为目标函数而构成单目标规划问题。即其中极大极小法

其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小.为此，对每个x∈R，我们先求诸目标函数值fi(x)的最大值，然后再求这些最大值中的最小值。即构造单目标规划：

为权值系数向量。于是多目标规划问题化为：

理想点法

对于多目标规划：

s.tgj(x)≤0j=1,2,…,n先设计与目标函数相应的一组目标值理想化向量

再设γ为一松弛因子标量。设

在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为：

minγ F(x)-weight·γ≤goal c(x)≤0非线性不等式约束

ceq(x)=0非线性等式约束

Ax≤b线性不等式约束

Aeqx=beq

线性等式约束

lb≤x≤ub

其中，x,weight,goal,b,beq,lb和ub为向量，A和Aeq为矩阵，c(x),ceq(x)和F(x)为函数调用格式：x=fgoalattain(F,x0,goal,weight)[x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例1：

投资组合模型市场上有n种资产Si(i=1,2,…,n)可以选择，现用数额为M的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买Si的平均收益率为ri

,风险损失率为qi,在多项投资组合中，总体风险可用投资的Si中最大的一个风险来度量。购买Si时要付交易费，费率pi(不买无须付费).当购买额不超过给定值ui时，交易费按购买ui计算.另外，假定同期银行存款利率是r0,既无交易费又无风险。(r0=5%)SiriqipiuiS1282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定达到资金M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。已知n=4时的相关数据如下:基本假设1.投资数额M相当大,为了便于计算，假设M=1;2.投资越分散，总的风险越小；3.总体风险Si用投资项目中最大的一个风险来度量；4.n种资产Si之间是相互独立的；5.在投资的这一时期内,ri,pi,qi,r0为定值，不受意外因素影响；6.净收益和总体风险只受ri,pi,qi影响，不受其他因素干扰。符号规定Si——第i种投资项目，如股票，债券ri

,pi,qi

——分别为Si的平均收益率,风险损失率，交易费率ui

——Si的交易定额,r0——同期银行利率xi——投资项目Si的资金,a——投资风险度Q——总体收益,∆Q——总体收益的增量

模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…n}2．购买Si所付交易费是一个分段函数,即

pixixi>ui

交易费=

piui

xi≤ui而题目所给定的定值ui(单位:元)相对总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi净收益尽可能大建立模型总体风险尽可能小多目标规划问题采用主要目标法化为单目标规划

方法一.

固定风险水平，优化收益

在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/M≤a，可找到相应的投资方案。

模型一线性规划模型若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。

模型二线性规划模型方法二：固定盈利水平，极小化风险采用线性加权法化为单目标规划

投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0＜s≤1)，s称为投资偏好系数.

模型三线性规划模型模型一的求解

将具体数据代入,模型一如下:

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];

Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];

vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')计算结果：风险大，收益也大。曲线上的任一点表示该风险水平的最大可能收益。对于不同风险的承受能力，选择该风险水平下的最优投资组合。在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是：

a*=0.6%，Q*=20%。

此时所对应投资方案为:

风险度=0.0060；收益=0.2019；

x0=0，x1=0.2400，x2=0.4000，

x