简单优化模型课件.ppt

简单优化模型第1页，此课件共50页哦3.1 最优化理论与方法简介最优化理论与方法简介第2页，此课件共50页哦 引例引例 设有一条设有一条2OO2OO千米长的高速公路，沿千米长的高速公路，沿途有途有7个城镇，在每个城镇都有一个汽车维个城镇，在每个城镇都有一个汽车维修点，今计划建一座仓库供应这些维修点修点，今计划建一座仓库供应这些维修点的零配件。问题是，该仓库应建在何处最的零配件。问题是，该仓库应建在何处最好？好？问题假设和分析问题假设和分析:在长L2OO的直线上分布7个点，坐标分别是：X0=0，X1=，X6=200，设仓库建在x处，今问：x=？第3页，此课件共50页哦目标一：让仓库到各维修点距离之和为最小，其优化数学模型为 第4页，此课件共50页哦目标二：让仓库离最远的维修点的距离为最小，则新的优化模型是 目标三：让仓库到各维修点距离平方之和为最小，则第三个优化模型是 第5页，此课件共50页哦二二.优化问题的数学模型优化问题的数学模型一一.最优化问题的范畴及应用最优化问题的范畴及应用三三.优化问题的最优性条件优化问题的最优性条件四.最优化算法的结构最优化算法的结构五五.解无约束最优化问题的线搜索算法解无约束最优化问题的线搜索算法第6页，此课件共50页哦一一.最优化问题的范畴及应用最优化问题的范畴及应用数学规划动态规划随机规划多目标规划最优化(Optimization)运筹学 Operations Research几何规划网络优化组合优化最优控制第7页，此课件共50页哦最优化方法应用领域最优化方法应用领域日常生活日常生活科学研究科学研究工程设计工程设计经济计划经济计划交通运输交通运输生产管理生产管理第8页，此课件共50页哦二二.优化问题的数学模型优化问题的数学模型实际问题中的优化模型实际问题中的优化模型(数学规划模型数学规划模型)x决策变量决策变量f(x)目标函数目标函数 可行域可行域 or第9页，此课件共50页哦数学规划数学规划无约束优化线性规划非光滑规划非线性规划整数规划半定规划第10页，此课件共50页哦 无约束优化无约束优化 非线性规划非线性规划 (NLP)(Nonlinear Programming)其中均为定义在 上的实值函数.第11页，此课件共50页哦 线性规划线性规划（LP:Linear Programming）目标函数和所有的约束条件都是目标函数和所有的约束条件都是决策决策变量变量的线性函数。的线性函数。第12页，此课件共50页哦三三.优化问题的最优性条件优化问题的最优性条件无约束最优化问题的最优性条件无约束最优化问题的最优性条件定理1(一阶必要条件)若 是(1)的局部最优解,则必有 :即第13页，此课件共50页哦泰勒公式一元函数情形二元函数情形第14页，此课件共50页哦第15页，此课件共50页哦局部最优解与整体最优解局部最优解与整体最优解 局部最优解局部最优解(Local Optimal Solution,如如 x1)整体最优解整体最优解(Global Optimal Solution,如如 x2)x*f(x)x1x2o第16页，此课件共50页哦第17页，此课件共50页哦多局部极小 唯一极小(全局极小)第18页，此课件共50页哦l 约束非线性规划问题的最优性条件约束非线性规划问题的最优性条件KKT条件条件第19页，此课件共50页哦四四.最优化算法的结构最优化算法的结构 最优化算法通常采用迭代方法求它的最优解,其基本思想是:给定一 个初始点 ，按照某一迭代规则产生一个点列 ,使得当 是有限点列时,其最后一个点是最优解；当 是无穷点列时,它有极限点,且其极限点是最优化模型问题的局部最优解（极小值点）。一个好的算法应具备的典型特征是：迭代点列能稳定地接近局部极小点 的领域，然后迅速收敛于 。当给定的某种收敛准则满足时，迭代即终止。理论上，我们要证明迭代点列 的聚点（即子序列的极限点）为一局部极小点。第20页，此课件共50页哦优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加 第21页，此课件共50页哦两种算法策略两种算法策略 线搜索方法（Line Search Methods)信赖域方法(Trust-Region Methods)第22页，此课件共50页哦标准形式：标准形式：五五 解无约束最优化问题的线搜索算法解无约束最优化问题的线搜索算法求解的基本思想求解的基本思想 (以二元函数为例)531连续可微第23页，此课件共50页哦无约束优化问题的线搜索算法无约束优化问题的线搜索算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：第24页，此课件共50页哦2 2牛顿法算法步骤：牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.第25页，此课件共50页哦3 3拟牛顿法（拟牛顿法（Quasi-Newton Methods)Quasi-Newton Methods)第26页，此课件共50页哦第27页，此课件共50页哦第28页，此课件共50页哦搜索过程搜索过程最优点 (1 1)初始点 (-1 1)-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第29页，此课件共50页哦 MatlabMatlab优化工具箱简介优化工具箱简介1.MATLAB1.MATLAB求解优化问题的主要函数求解优化问题的主要函数第30页，此课件共50页哦MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog第31页，此课件共50页哦2.2.优化函数的输入变量优化函数的输入变量 使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:第32页，此课件共50页哦3.3.优化函数的输出变量下表优化函数的输出变量下表:第33页，此课件共50页哦3.2 存贮模型存贮模型背景及问背景及问 题题配件厂为装配线生产若干种产品，轮换产品时因更换设配件厂为装配线生产若干种产品，轮换产品时因更换设备要付一次性生产准备费，产量大于需求时要付贮存费。备要付一次性生产准备费，产量大于需求时要付贮存费。该厂生产能力非常大，即所需数量可在很短时间内产出。该厂生产能力非常大，即所需数量可在很短时间内产出。已知某产品日需求量已知某产品日需求量100件，生产准备费件，生产准备费5000元，贮存费元，贮存费每日每件每日每件1元。试安排该产品的生产计划，即多少天生产元。试安排该产品的生产计划，即多少天生产一次（生产周期），每次产量多少，使总费用最小。一次（生产周期），每次产量多少，使总费用最小。要要 求求建立最佳生产周期、产量与需求量、准备费、贮建立最佳生产周期、产量与需求量、准备费、贮存费之间的关系。存费之间的关系。第34页，此课件共50页哦问题分析与思考问题分析与思考 每天生产一次每天生产一次，每次，每次100件，无贮存费，准备费件，无贮存费，准备费5000元。元。日需求日需求100件，准备费件，准备费5000元，贮存费每日每件元，贮存费每日每件1元。元。10天生产一次天生产一次，每次，每次1000件，贮存费件，贮存费900+800+100 =4500元，准元，准备费备费5000元，总计元，总计9500元。元。50天生产一次天生产一次，每次，每次5000件，贮存费件，贮存费4900+4800+100=122500元，元，准备费准备费5000元，总计元，总计127500元。元。平均每天费用平均每天费用950元元平均每天费用平均每天费用2550元元1010天生产一次平均每天费用最小吗天生产一次平均每天费用最小吗?每天费用每天费用5000元元第35页，此课件共50页哦 这是一个优化问题，关键在建立目标函数。这是一个优化问题，关键在建立目标函数。显然不能用一个周期的总费用作为目标函数显然不能用一个周期的总费用作为目标函数目标函数目标函数每天总费用的平均值每天总费用的平均值 周期短，产量小周期短，产量小 周期长，产量大周期长，产量大问题分析与思考问题分析与思考贮存费少，准备费多贮存费少，准备费多准备费少，贮存费多准备费少，贮存费多存在最佳的周期和产量，使总费用（二者之和）最小存在最佳的周期和产量，使总费用（二者之和）最小 思考：为什么不考虑生产费用？在什么条件下才不考虑？思考：为什么不考虑生产费用？在什么条件下才不考虑？第36页，此课件共50页哦模模 型型 假假 设设1.产品每天的需求量为常数产品每天的需求量为常数 r；2.每次生产准备费为每次生产准备费为 c1,每天每件产品贮存费为每天每件产品贮存费为 c2；3.T天生产一次（周期）天生产一次（周期）,每次生产每次生产Q件，当贮存量件，当贮存量 为零时，为零时，Q件产品立即到来（生产时间不计）；件产品立即到来（生产时间不计）；建建 模模 目目 的的设设 r,c1,c2 已知，求已知，求T,Q 使每天总费用的平均值最小。使每天总费用的平均值最小。4.为方便起见，时间和产量都作为连续量处理。为方便起见，时间和产量都作为连续量处理。不允许缺货的存贮模型不允许缺货的存贮模型第37页，此课件共50页哦模模 型型 建建 立立0tq贮存量表示为时间的函数贮存量表示为时间的函数 q(t)TQrt=0生产生产Q件，件，q(0)=Q,q(t)以以需求速率需求速率r递减，递减，q(T)=0.一周期一周期总费用总费用每天总费用平均每天总费用平均值（目标函数）值（目标函数）离散问题连续化离散问题连续化一周期贮存费为一周期贮存费为A=QT/2第38页，此课件共50页哦模型求解模型求解求求 T 使使模型分析模型分析模型应用模型应用c1=5000,c2=1，r=100T=10(天天),Q=1000(件件),C=1000(元元)回答问题回答问题第39页，此课件共50页哦 经济订货批量公式经济订货批量公式（EOQ公式公式）每天需求量每天需求量 r，每次订货费，每次订货费 c1,每天每件贮存费每天每件贮存费 c2，用于存贮、用于存贮、订货订货、供应供应等情形等情形不允许缺货的存贮模型不允许缺货的存贮模型T天订货一次天订货一次(周期周期)，每次订货每次订货Q件，当贮存量降到件，当贮存量降到零时，零时，Q件立即到货。件立即到货。第40页，此课件共50页哦允许缺货的存贮模型允许缺货的存贮模型AB0qQrT1t当贮存量降到零时仍有需求当贮存量降到零时仍有需求r,出现出现缺货，造成损失缺货，造成损失原模型假设：贮存量降到零时原模型假设：贮存量降到零时Q件立即件立即生产出来生产出来(或立即到货或立即到货)现假设：允许缺货现假设：允许缺货,每天每件缺货损失费每天每件缺货损失费 c3,缺货需补足缺货需补足T一周期一周期贮存费贮存费一周期一周期缺货费缺货费假设周期为假设周期为T,T,订货量为订货量为Q Q，t=Tt=T1 1 时贮存量降到零。时贮存量降到零。一周期总费用一周期总费用第41页，此课件共50页哦每天总费用每天总费用平均值平均值（目标函数）（目标函数）一周期总费用一周期总费用求求 T,Q 使使为了与为了与不允许缺货的存贮模型相不允许缺货的存贮模型相比较，比较，T记作记作T,Q记作记作Q第42页，此课件共50页哦不允不允许缺许缺货模货模型型记记允许允许缺货缺货模型模型不不允允许许缺缺货货第43页，此课件共50页哦允许允许缺货缺货模型模型0qQ rT1tT注意：缺货需补足注意：缺货需补足Q 每周期初的存贮量每周期初的存贮量R每周期所需的生产每周期所需的生产量量(或订货量）或订货量）RQ Q不允许缺货时的产量不允许缺货时的产量不允许缺货时的产量不允许缺货时的产量(或订货量或订货量或订货量或订货量)第44页，此课件共50页哦问题问题：某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.3.3 产销量的最佳安排产销量的最佳安排第45页，此课件共50页哦基本假设基本假设1 1价格与销量成线性关系价格与销量成线性关系2 2成本与产量成负指数关系成本与产量成负指数关系第46页，此课件共50页哦 模型建立模型建立 若根据大量的统计数据,求出系数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 z(x x1 1,x,x2 2)=()=(p p1 1-q-q1 1)x x1 1+(+(p p2 2-q-q2 2)x x2 2第47页，此课件共50页哦 模型求解模型求解(MATLAB)(MATLAB)1.建立M-文件fun.m:function f=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;x=fminunc(fun,x0),z=fun(x)3.计算结果:x=23.9025,62.4977,z=6.4135e+003 即甲的产量为23.9025,乙的产量为62.4977,最大利润为6413.5.第48页，此课件共50页哦q2U(q1,q2)=cq103.4 消费者均衡消费者均衡问题问题消费者对甲乙两种商品的偏爱程度用无差别消费者对甲乙两种商品的偏爱程度用无差别曲线族表示，问他如何分配一定数量的钱，曲线族表示，问他如何分配一定数量的钱，购买这两种商品，以达到最大的满意度。购买这两种商品，以达到最大的满意度。设甲乙数量为设甲乙数量为q1,q2,消费消费者的无差别曲线族者的无差别曲线族(单调单调减、下凸、不相交），记减、下凸、不相交），记作作 U(q1,q2)=cU(q1,q2)效用函数效用函数已知甲乙价格已知甲乙价格 p1、p2,有钱有钱s，试分配，试分配s,购购买甲乙数量买甲乙数量 q1、q2,使使 U(q1,q2)最大最大.第49页，此课件共50页哦s/p2s/p1q2U(q1,q2)=cq10模型模型及及求解求解已知价格已知价格 p1、p2,钱钱 s,求求q1、q2,或或 p1q1/p2q2,使使 U(q1,q2)最大最大几几何何解解释释直线直线MN:最优解最优解Q:MN与与 l2切点切点斜率斜率MQN第50页，此课件共50页哦