当前位置：文档之家 › 最优化技术1-2

最优化技术1-2

  • 格式：doc
  • 大小：707.00 KB
  • 文档页数：59

最优化原理优化问题 1.1线性规划1．线性规划问题描述线性规划问题（Linear Programming ）是目标函数和约束条件均为线性函数的问题，MA TLAB 中的线性规划问题的标准形式描述如下：min nR x x f ∈' sub.to ：b x A ≤⋅ beq x Aeq =⋅ ub x lb ≤≤其中f 、x 、b 、beq 、lb 、ub 为矢量；A 、Aeq 为矩阵。

提示：其它形式的线性规划都能够经过适当变换化成上述标准形式。

接下来，使用MA TLAB 中的函数求解线性规划问题。

在MA TLAB6.0及以上版本中，求解线性规划问题的函数是linprog 。

调用格式1： x = linprog(f,A,b)2数学软件与实验2 功能说明：求min f ' *x sub.to bx A ≤⋅线性规划的最优解。

调用格式2：x = linprog(f,A,b,Aeq,beq)功能说明： 等式约束beq x Aeq =⋅，若没有不等式约束b x A ≤⋅，则A=[ ]，b=[ ]。

调用格式3：x = linprog(f,A,b,Aeq,beq,lb,ub)功能说明：约束x ：ub x lb ≤≤，若没有等式约束beq x Aeq =⋅ ，则Aeq=[ ]，beq=[ ]调用格式4：x = linprog(f,A,b,Aeq,beq,lb,ub,x0) 功能说明：设置初值x0调用格式5：x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 功能说明： options 为指定的优化参数，参数详情请查看optimset 和optimget 函数。

调用格式6：[x,fval] = linprog(…)功能说明：返回目标函数最优值，即fval= f ' *x 。

调用格式7：[x,lambda,exitflag] = linprog(…)功能说明： lambda 为解x 的Lagrange 乘子。

若lambda=lower 表示下界lb ，lambda=upper 表示上界ub ，lambda=ineqlin 表示不等式约束，lambda=eqlin 表示等式约束，lambda 中的非0元素表最优化原理 33示对应的约束是有效约束。

调用格式8：[x, lambda,fval,exitflag] = linprog(…) 功能说明：exitflag 为终止迭代的错误条件；若exitflag>0表示函数收敛于解x ，exitflag=0表示超过函数估值或迭代的最大数字，exitflag<0表示函数不收敛于解x 。

应用实例例2-1： 求下面的线性规划问题。

min43215342x x x x --+约束条件：20234321≤++-x x x x 364234321≤++-x x x x6023321≤+-x x x205431≤++x x x43211,0,0,0x x x x ≤≤≤≤解：编写的MA TLAB 指令如下（源代码见光盘\2\m0208.m ）： f = [2;4; -3; -5];%线性函数 A = [1 -1 3 2;3 -2 1 4;1 -3 2 0;5 0 1 1]; %参数 b = [20 ; 36; 60; 20];%约束条件4数学软件与实验lb = [0 0 0 1]; %约束参数初始条件%调用linprog函数求解线性规划[x,fval,exitflag,lambda] = linprog(f,A,b,[],[],lb)运行M文件，得到的结果为：>> Optimization terminated successfully.x = %最优解0.00000.00000.80008.8000fval = %最优值-46.4000exitflag = %收敛情形1lambda =iterations: 7 %迭代次数cgiterations: 04最优化原理 55algorithm: 'lipsol'%使用规则1.2非线性规划常用的非线性规划函数如表2-1所示。

表2-1 常用的非线性规划函数2．有约束函数的一元函数的最小值有约束条件的一元函数求最小值的标准形式为：)x (f minx约束条件：21x x x <<在MA TLAB 中可以使用fminbnd 函数来求其最小值。

调用格式1： x = fminbnd(fun,x1,x2)说 明：fun 为目标函数的表达式字符串；结果返回自变量x 在21x x x<<区间上函数fun 取最小值时的x 值。

调用格式2：x = fminbnd(fun,x1,x2,options) 说 明：options 为指定优化参数选项。

6数学软件与实验6 调用格式3：[x,fval] = fminbnd(…) 说 明：fval 为目标函数的最小值 调用格式4：[x,fval,exitflag] = fminbnd(…)说 明：exitflag 为终止迭代的条件，若参数exitflag>0，表示函数收敛于x ；若exitflag=0，表示超过函数估计值或迭代的最大次数；exitflag<0表示函数不收敛于x 。

调用格式5：[x,fval,exitflag,output] = fminbnd(…) 说 明：output 为优化信息：若参数output=iterations 表示迭代次数，output=funccount 表示函数赋值次数，output=algorithm 表示所使用的算法。

例2-2：计算下面函数1)3()(2--=x x f 在区间(0，5)内的最小值。

解：可以先自定义一个函数： 编写内容如下的M 文件： function f = myfun(x) f = (x-3).^2 - 1;然后在命令窗口键入命令：[x,fval,exitflag,output]= fminbnd(@myfun,0,5) 运行以上指令得到的显示结果如下：最优化原理 77x = 3 fval = -1 exitflag = 1 output = iterations: 6 funcCount: 6algorithm: 'golden section search, parabolic interpolation' 1.3无约束多元函数最小值无约束条件的多元函数最小值的标准形式为：)x (f minx其中：x 为矢量，如]x ,,x,x [x n 21在MA TLAB 中使用fminsearch 函数求其最小值。

调用格式1： x = fminsearch(fun,x0)说 明：fun 为目标函数的表达式字符串，x0为初始点。

调用格式2：x = fminsearch(fun,x0,options)说 明：options 为指定优化参数选项（查看optimset 函8数学软件与实验8 数）。

调用格式3：[x,fval,exitflag] = fminsearch(...)说 明：exitflag 与fminbnd 函数里的exitflag 参数使用一致调用格式4：[x,fval,exitflag,output] = fminsearch(...)说 明：output 与fminbnd 函数里的output 参数使用一致 例2-3： 求32312133221652x x x x x x x x x y -+---=的最小值点及最小值。

解：编写内容如下所示的M 文件：function f=myfun(x)f=x(1)^-x(2)^2-x(3)^3-2*x(1)*x(2)+5*x(1)*x(3)-6*x(2)*x(3);在命令窗口键入指令：>>[X,fval,exitflag,output]=fminsearch(@m0210,[0,0,0])运行以上指令得到的显示结果如下： X =%最小值点-0.0000 -0.1769 0.1132 fval = %最小值0.1187 + 0.0001i最优化原理 99exitflag = %收敛状况1 output =iterations: 142 %叠代次数funcCount: 274algorithm: 'Nelder-Mead simplex direct search' %采用的算法1.4有约束的多元函数最小值非线性有约束的多元函数的标准形式为：)x (f minx约束条件：)x (C ≤，0)x (Ceq =，b x A ≤⋅，beq x Aeq =⋅，ub x lb ≤≤其中：x 、b 、beq 、lb 、ub 是矢量，A 、Aeq 为矩阵，C(x)、Ceq(x)是返回矢量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)都可以是非线性函数。

在MA TLAB 中，求解有约束的多元函数最小值由函数fmincon 实现。

fmincon 函数的调用格式如下： x = fmincon(fun,x0,A,b)10数学软件与实验10 x = fmincon(fun,x0,A,b,Aeq,beq) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, ...)[x,fval] = fmincon(...) [x,fval,exitflag] = fmincon(...) [x,fval,exitflag,output] = fmincon(...) [x,fval,exitflag,output,lambda] = fmincon(...) [x,fval,exitflag,output,lambda,grad] = fmincon(...)其中，fun 为目标函数；x0为初始值；A 、b 满足线性不等式约束b x A ≤⋅，若没有不等式约束，则取A=[ ]，b=[ ]；Aeq 、beq 满足等式约束beq x Aeq =⋅，若没有，则取Aeq=[ ]，beq=[ ]；lb 、ub 满足ub x lb ≤≤，若没有界，可设lb=[ ]，ub=[ ]；lambda 是Lagrange 乘数，它体现有效约束的个数；output 输出优化信息；grad 表示目标函数在x 处的梯度。

合集下载

小学六年级数学毕业考试难题：最优化问题(一、二)答案

小学六年级数学毕业考试难题：最优化问题(一、二)答案

数学思维策略培训——最优化问题（一）姓名评价例如我们家里做饭时，通常有以下步骤，择菜，洗菜，切菜，炒菜，洗米，煮饭等.如果一个人做这些事时，若能比较合理地安排前后顺序，就会在最短的时间内做好饭。

再比如同学们的父母为家人做衣服.在裁剪衣料时，如果能够精打细算，就可以在衣料一定量的前提下裁剪出更多或更好的衣服。

又比如我们上街购物时，如果事先计划好路线，就可以少走冤枉路，节省时间。

这样的事例可以举出很多.这种问题大致可以分为两类：一类是确定一项任务后，精打细算，使用最少的人力、物力去完成它；另一类是已有一定数量的人力、物力，合理调配，使之发挥最大效力，从而多、快、好省地完成任务。

华罗庚爷爷非常重视数学在科学技术和工农业生产中的应用，他生前曾积极推广、普及了“统筹方法”和“优选法”。

在这一讲，我们通过几个简单的“最优化”问题，使大家对统筹和优化的方法有个初步了解。

【例1】一只平底锅上只能煎两只饼，用它煎1只饼需要2分钟（正面、反面各1分钟）。

问煎三只饼需几分钟？怎样煎？【例2】6个人各拿一只水桶到水龙头接水，水龙头注满6个人的水桶所需时间分别是5分钟、4分钟、3分钟、10分钟、7分钟、6分钟。

现在只有这一个水龙头可用，问怎样安排这6人的打水次序，可使他们总的等候时间最短？这个最短时间是多少？【例3】工地上有手推车20辆，其中10辆从A1到B1运垃圾，要60车次运完。

另外10辆从A2到B2运砖头，要40车次运完。

工地上的可行道路及路程如右图24-1（单位：米）。

有人说上面的安排不合理，因为跑空车的路程还可以更少些。

那么，怎样安排才算合理呢？【例4】40名师生参加义务植树活动，他们的任务是挖树坑和运树苗.经过上午的劳动实践，40名师生大致可分成甲、乙、丙三类人员.每类人员的劳动效率见表.下午给他们分配的任务是：挖树坑30个，运树苗不限，如何安排人员能使树苗运得最多？【例5】现有2.8米长的方木条原料，要截成1.2米、0.9米两种长度的木条作镜框（每个镜框要用长、短木条各两根）.要做30个镜框，如何下料可以最省？【例6】某学校调整教室桌椅，图1中标出了教室的位置，图中“方块”表示的教室要搬出桌椅，“圆”所表示的教室要搬入桌椅，搬出、搬入桌椅的套数为图中所标数字.试作出“最佳”搬运方案。

第二章 系统工程基础概述

第二章 系统工程基础概述


产品 研究 规划
生产 工程 规划
制造 规划
分配和 仓库储 存规划
已核准 的产品 设想
包装 设计 规划
销售 规划
广告 与推销 规划
广告 实施 规划
产品 的商 品化
市场 调查 规划划
图2-4 按过程描述的新产品规划网络
总经理
总经理助理
人
事
营
销
工
程
生
产
（一）典型定义
• 日本工业标准JIS的定义：“系统工程是为 了更好地达到系统目标，而对系统的构成 要素、组织结构、信息流动和控制机制等 进行分析与设计的技术。”
（一）典型定义
• 系统分析是研究相互影响的因素的组成和 运用情况。 • 综上所述，系统工程是以研究大型复杂的 人造系统和复合系统为对象的一门交叉科 学，它既是一个技术过程又是一个管理过 程。
（三）功能分析的思路
• • • • • • • 1、系统功能的制约因素 （1）外界输入与环境因素的制约 （2）系统结构的制约 2、功能分析的步骤 （1）对系统的输入输出关系进行准确描述； （2）进行输入输出关系的整体评价和分析； （3）对某一特定功能进行流程分析及流程再设计。
客户电话咨询
接线员理 解问题？
二、系统工程发展历程及趋势
• （一）发展简史 • 在第二次世界大战前夕，经济、生产等领域的系 统问题已促使人们努力揭示系统的一般运行规律 和创造组织管理系统的技术。 • 在第二次世界大战期间，系统分析的方法和技术 得到突飞猛进的发展。二次世界大战期间还培养 了一批系统工程人才，促进了系统工程学科的形 成与发展。 • 第二次世界大战结束，各种社会经济系统和工程 管理系统的规模日益扩大和复杂化，导致一些新 的问题的出现，人们又一次寻求通过科学的系统 方法作为解决复杂经济社会系统问题的技术 。
系统工程导论 第二章系统工程的基础理论与方法论 第一节系统最优化理论

系统工程导论 第二章系统工程的基础理论与方法论 第一节系统最优化理论


n 。最后，也要考虑到xij
的产品数量属性，即 xij 0,i 1, 2, m, j 1, 2, n ，因此，该运
输方案可由以下模型求解得到：
2.1 系统最优化理论
mn
min
cij xij
i 1 j 1
（2-3）
n
s.t. xij ai ,i 1, 2, m j 1 m xij bj , j 1, 2, n i 1 xij 0,i 1, 2, m, j 1, 2, n
2.1 系统最优化理论
mn
解
首先，在假设运输量为
xij
的条件下其总的运费为 i 1
j 1
cij
xij
。
其次，要考虑到从任意产地运出的量要等于该产地的产量，即
n
xij ai ,i 1, 2,
j 1
m 。第三，还要考虑到运到任意销地的量要等
m
于该销地能销出的量，即 xij bi , j 1, 2, i 1
不同的方案、设计、措施以达到最优目的。（2）目标函数，如例
2-1
中的 max
, 10x1 18x2
例
2-2
中的min
mn
cij xij
。目标函数通常是决策变
i 1 j 1
量的函数，表达了“何为最优”的准则和目标，规定了优化问题
的实际意义。
2.1 系统最优化理论
（3）约束条件，如例 2-1 和例 2-2 中由“s.t”规定的部分。 约束条件指决策变量取值时受到的各种资源和条件的限制，表 达了一种“有条件优化”的概念，通常为决策变量的等式或不 等式方程。如果决策变量的取值是连续的，且目标函数和约束 条件都是决策变量的线性函数，则称为线性规划问题。如果决 策变量的取值为整数点，则称为整数规划问题；如果部分决策 变量取值连续而其余取值为整数，则称为混合整数规划问题； 如果目标函数和约束条件中存在任何的非线性因子，则称为非 线性规划问题。
最优化第一次作业

最优化第一次作业

无约束优化算法最优化课程作业（一）姓名：丁敏学号：31130510012014/6/24一、无约束优化算法无约束优化计算方法是数值计算领域中十分活跃的研究课题。

快速地求解无约束优化问题已经成为当今的焦点，除了其自身的重要性外，还由于目前求解约束优化问题的基本思想之一就是把约束问题变换为一系列无约束子问题进行求解。

因此，无约束优化算法的求解效率将直接影响到约束问题的求解，尤其是在大规模优化问题中。

所以，对无约束优化算法的研究具有重要的理论意义和实际价值。

无约束优化问题，是指优化问题的可行集为n R ，无约束的标准形式（1-1）为：R R f x f n→:)(m i n求解无约束优化问题时将会涉及到以下概念：(1) 驻点、鞍点：若f (x )在点x*处可微，并且0f (x*)∇=，则称x*为f (x )的一个驻点(或者平稳点)。

既不是极小点，也不是极大点的驻点称为鞍点。

(2) 全局最优解：若n x*Z,x R ∈∀∈均有f (x )f (x*)≥，则称x*为问题(1-1)的全局 最优解(3) 局部最优解：若*x D ∈且存在0δ>使得()()()**f x f x ,x DN x δ≥∀∈则称x*为问题(1-1)的一个局部最优解（极小点）；若*x D ∈且存在0δ>使得()()()**f x f x ,x DN x δ≤∀∈则称x*为问题(1-1)的一个局部最优解（极大点）；当目标函数 f ( x )为凸函数时，我们认为全局最优解即是局部最优解，然而，通常寻求全局最优解并不容易。

因此，在非线性优化中我们认为局部最优解即为所求。

无约束优化算法可以分为两大类: 一类是借助目标函数的导数信息来构造下降的搜索方向。

另一类是由目标函数值信息直接搜索求解的方法。

本文章重点介绍最速下降法，阻尼牛顿法以及共轭梯度法。

二、最速下降法1、最速下降法思想经典最速下降法是由 Cauchy 于 1847 年提出的，Forsythe 和 Motzkin 在 1951 年对它做了初步的分析。