简单优化模型

简单优化模型第一页，共五十页，编辑于2023年，星期一§3.1最优化理论与方法简介第二页，共五十页，编辑于2023年，星期一

引例

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

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

第三页，共五十页，编辑于2023年，星期一目标一：让仓库到各维修点距离之和为最小，其优化数学模型为第四页，共五十页，编辑于2023年，星期一目标二：让仓库离最远的维修点的距离为最小，则新的优化模型是

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

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

Ω~可行域

or第九页，共五十页，编辑于2023年，星期一数学规划无约束优化线性规划非光滑规划非线性规划整数规划半定规划第十页，共五十页，编辑于2023年，星期一

无约束优化

非线性规划(NLP)(NonlinearProgramming)其中均为定义在上的实值函数.第十一页，共五十页，编辑于2023年，星期一

线性规划（LP:LinearProgramming）

目标函数和所有的约束条件都是决策变量的线性函数。第十二页，共五十页，编辑于2023年，星期一三.优化问题的最优性条件无约束最优化问题的最优性条件定理1

(一阶必要条件)若是(1)的局部最优解,则必有:即第十三页，共五十页，编辑于2023年，星期一泰勒公式一元函数情形二元函数情形第十四页，共五十页，编辑于2023年，星期一第十五页，共五十页，编辑于2023年，星期一局部最优解与整体最优解

局部最优解(LocalOptimalSolution,如x1)

整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o第十六页，共五十页，编辑于2023年，星期一第十七页，共五十页，编辑于2023年，星期一多局部极小

唯一极小(全局极小)第十八页，共五十页，编辑于2023年，星期一

约束非线性规划问题的最优性条件KKT条件第十九页，共五十页，编辑于2023年，星期一四.最优化算法的结构

最优化算法通常采用迭代方法求它的最优解,其基本思想是:给定一个初始点，按照某一迭代规则产生一个点列,使得当是有限点列时,其最后一个点是最优解；当是无穷点列时,它有极限点,且其极限点是最优化模型问题的局部最优解（极小值点）。一个好的算法应具备的典型特征是：迭代点列能稳定地接近局部极小点的领域，然后迅速收敛于。当给定的某种收敛准则满足时，迭代即终止。理论上，我们要证明迭代点列的聚点（即子序列的极限点）为一局部极小点。第二十页，共五十页，编辑于2023年，星期一优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加

第二十一页，共五十页，编辑于2023年，星期一两种算法策略

线搜索方法（LineSearchMethods)

信赖域方法(Trust-RegionMethods)第二十二页，共五十页，编辑于2023年，星期一标准形式：五解无约束最优化问题的线搜索算法求解的基本思想

(以二元函数为例)531连续可微第二十三页，共五十页，编辑于2023年，星期一无约束优化问题的线搜索算法

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

1．最速下降法（共轭梯度法）算法步骤：第二十四页，共五十页，编辑于2023年，星期一2．牛顿法算法步骤：

如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.

牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.第二十五页，共五十页，编辑于2023年，星期一3．拟牛顿法（Quasi-NewtonMethods)第二十六页，共五十页，编辑于2023年，星期一第二十七页，共五十页，编辑于2023年，星期一第二十八页，共五十页，编辑于2023年，星期一搜索过程最优点(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第二十九页，共五十页，编辑于2023年，星期一

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

使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:第三十二页，共五十页，编辑于2023年，星期一3.优化函数的输出变量下表:第三十三页，共五十页，编辑于2023年，星期一§3.2

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

要求建立最佳生产周期、产量与需求量、准备费、贮存费之间的关系。第三十四页，共五十页，编辑于2023年，星期一问题分析与思考

每天生产一次，每次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元第三十五页，共五十页，编辑于2023年，星期一

这是一个优化问题，关键在建立目标函数。显然不能用一个周期的总费用作为目标函数目标函数——每天总费用的平均值

周期短，产量小

周期长，产量大问题分析与思考贮存费少，准备费多准备费少，贮存费多存在最佳的周期和产量，使总费用（二者之和）最小

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

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

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

回答问题第三十九页，共五十页，编辑于2023年，星期一

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

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

第四十四页，共五十页，编辑于2023年，星期一问题：

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

产销量的最佳安排第四十五页，共五十页，编辑于2023年，星期一基本假设1．价格与销量成线性关系2．成本与产量成负指数关系第四十六页，共五十页，编辑于2023年，星期一

模型建立

若根据大量的统计数据,求出系数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第四十七页，共五十页，编辑于2023年，星期一

模型求解(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);y2=((280-0.2*x(1)-2*x(2))-(100*exp(-0.02*x(2))+30))*x(2);f=-y1-y2;2.输入命令:x0=[50,70