简单优化模型演示文稿

简单优化模型演示文稿（优选）简单优化模型

引例

设有一条2OO千米长的高速公路，沿途有7个城镇，在每个城镇都有一个汽车维修点，今计划建一座仓库供应这些维修点的零配件。问题是，该仓库应建在何处最好？

问题假设和分析:在长L＝2OO的直线上分布7个点，坐标分别是：X0=0，X1=…，X6=200，设仓库建在x处，今问：x=？

目标一：让仓库到各维修点距离之和为最小，其优化数学模型为目标二：让仓库离最远的维修点的距离为最小，则新的优化模型是

目标三：让仓库到各维修点距离平方之和为最小，则第三个优化模型是

二.优化问题的数学模型一.最优化问题的范畴及应用三.优化问题的最优性条件四.最优化算法的结构五.解无约束最优化问题的线搜索算法一.最优化问题的范畴及应用数学规划动态规划随机规划多目标规划最优化(Optimization)[运筹学OperationsResearch]几何规划网络优化组合优化最优控制最优化方法应用领域日常生活科学研究工程设计经济计划交通运输生产管理二.优化问题的数学模型实际问题中的优化模型(数学规划模型)x~决策变量f(x)~目标函数

Ω~可行域

or数学规划无约束优化线性规划非光滑规划非线性规划整数规划半定规划

无约束优化

非线性规划(NLP)(NonlinearProgramming)其中均为定义在上的实值函数.

线性规划（LP:LinearProgramming）

目标函数和所有的约束条件都是决策变量的线性函数。三.优化问题的最优性条件无约束最优化问题的最优性条件定理1

(一阶必要条件)若是(1)的局部最优解,则必有:即泰勒公式一元函数情形二元函数情形局部最优解与整体最优解

局部最优解(LocalOptimalSolution,如x1)

整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o多局部极小唯一极小(全局极小)

约束非线性规划问题的最优性条件KKT条件四.

最优化算法的结构

最优化算法通常采用迭代方法求它的最优解,其基本思想是:给定一个初始点，按照某一迭代规则产生一个点列,使得当是有限点列时,其最后一个点是最优解；当是无穷点列时,它有极限点,且其极限点是最优化模型问题的局部最优解（极小值点）。

一个好的算法应具备的典型特征是：迭代点列能稳定地接近局部极小点的领域，然后迅速收敛于。当给定的某种收敛准则满足时，迭代即终止。理论上，我们要证明迭代点列的聚点（即子序列的极限点）为一局部极小点。优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加

两种算法策略线搜索方法（LineSearchMethods)

信赖域方法(Trust-RegionMethods)标准形式：五解无约束最优化问题的线搜索算法求解的基本思想

(以二元函数为例)531连续可微无约束优化问题的线搜索算法

最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.

1．最速下降法（共轭梯度法）算法步骤：2．牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.3．拟牛顿法（Quasi-NewtonMethods)搜索过程最优点(11)初始点(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8

Matlab优化工具箱简介1.MATLAB求解优化问题的主要函数MATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonlinlsqcurvefit线性规划linprog纯0-1规划bintprog一般IP(暂缺)非线性规划fminconfminimaxfgoalattainfseminf上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性最小二乘lsqnonneglsqlin约束优化二次规划quadprog2.优化函数的输入变量

使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:3.优化函数的输出变量下表:§3.2

存贮模型背景及问题配件厂为装配线生产若干种产品，轮换产品时因更换设备要付一次性生产准备费，产量大于需求时要付贮存费。该厂生产能力非常大，即所需数量可在很短时间内产出。已知某产品日需求量100件，生产准备费5000元，贮存费每日每件1元。试安排该产品的生产计划，即多少天生产一次（生产周期），每次产量多少，使总费用最小。要求建立最佳生产周期、产量与需求量、准备费、贮存费之间的关系。问题分析与思考

每天生产一次，每次100件，无贮存费，准备费5000元。日需求100件，准备费5000元，贮存费每日每件1元。

10天生产一次，每次1000件，贮存费900+800+…+100=4500元，准备费5000元，总计9500元。

50天生产一次，每次5000件，贮存费4900+4800+…+100=122500元，准备费5000元，总计127500元。平均每天费用950元平均每天费用2550元10天生产一次平均每天费用最小吗?每天费用5000元这是一个优化问题，关键在建立目标函数。显然不能用一个周期的总费用作为目标函数目标函数——每天总费用的平均值周期短，产量小周期长，产量大问题分析与思考贮存费少，准备费多准备费少，贮存费多存在最佳的周期和产量，使总费用（二者之和）最小

思考：为什么不考虑生产费用？在什么条件下才不考虑？模型假设1.产品每天的需求量为常数r；2.每次生产准备费为c1,每天每件产品贮存费为c2；3.T天生产一次（周期）,每次生产Q件，当贮存量为零时，Q件产品立即到来（生产时间不计）；建模目的设r,c1,c2已知，求T,Q

使每天总费用的平均值最小。4.为方便起见，时间和产量都作为连续量处理。不允许缺货的存贮模型模型建立0tq贮存量表示为时间的函数q(t)TQrt=0生产Q件，q(0)=Q,q(t)以需求速率r递减，q(T)=0.一周期总费用每天总费用平均值（目标函数）离散问题连续化一周期贮存费为A=QT/2模型求解求T使模型分析模型应用c1=5000,

c2=1，r=100T=10(天),Q=1000(件),C=1000(元)

回答问题经济订货批量公式（EOQ公式）每天需求量r，每次订货费c1,每天每件贮存费c2，用于存贮、订货、供应等情形不允许缺货的存贮模型T天订货一次(周期)，每次订货Q件，当贮存量降到零时，Q件立即到货。允许缺货的存贮模型AB0qQrT1t当贮存量降到零时仍有需求r,出现缺货，造成损失原模型假设：贮存量降到零时Q件立即生产出来(或立即到货)现假设：允许缺货,每天每件缺货损失费c3,

缺货需补足T一周期贮存费一周期缺货费假设周期为T,订货量为Q，t=T1时贮存量降到零。一周期总费用每天总费用平均值（目标函数）一周期总费用求T,Q使为了与不允许缺货的存贮模型相比较，T记作T’,Q记作Q’不允许缺货模型记允许缺货模型不允许缺货允许缺货模型0qQrT1tT注意：缺货需补足Q~每周期初的存贮量R每周期所需的生产量(或订货量）RQ~不允许缺货时的产量(或订货量)

问题：

某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.§3.3

产销量的最佳安排基本假设1．价格与销量成线性关系2．成本与产量成负指数关系

模型建立

若根据大量的统计数据,求出系数b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,λ1=0.015,c1=20,r2=100,λ2=0.02,c2=30,则问题转化为无约束优化问题：求甲,乙两个牌号的产量x1，x2，使总利润z最大.为简化模型,先忽略成本,并令a12=0,a21=0,问题转化为求:z1=(b1-a11x1)x1+(b2-a22x2)x2

的极值.显然其解为x1=b1/2a11=50,x2=b2/2a22=70,我们把它作为原问题的初始值.总利润为：z(x1,x2)=(p1-q1)x1+(p2-q2)x2

模型求解(MATLAB)

1.建立M-文件fun.m:functionf=fun(x)y1=((100-x(1)-0.1*x(2))-(30*exp(-0.015*x(1))+20))*x(1);