最优化问题及其基本概念课件.ppt

一、最优化问题举例,利用最优化理论和方法解决生产实践以及科学研究中的具体问题，一般分为如下两个步骤：建立数学模型；进行数学加工和求解,1、运输问题,运输问题数据表,设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表。,m nMin f=cij xij i=1 j=1 n s.t.xij si i=1,2,m j=1 m xij(=,)dj j=1,2,n i=1 xij 0(i=1,2,m;j=1,2,n),于是得到下列一般运输问题的模型：,m n Min f=cij xij i=1 j=1 n s.t.xij=si i=1,2,m(4-5)j=1 m xij=dj j=1,2,n(4-6)i=1 xij0(i=1,2,m;j=1,2,n),对于产销平衡问题，可得到下列运输问题的模型：,在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；,产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，当产量大于销量时可加入一个虚设的销地去消化多余的物资。,2、生产计划问题,一般数学模型,二、最优化方法的基本概念,基本概念最优化问题的一些典型分类,基本概念,基本概念,基本概念,最优化问题的一些典型的分类,函数优化问题与组合优化问题 线性规划问题与非线性最优化问题 多目标规划,最优化问题的一些典型的分类,由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道,引例 钢管订购和运输,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的基本模型和解法,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道Aj Aj+1（j=1,14),由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij由Aj向Aj Aj-1段铺设的长度zj及向Aj Aj+1段铺设的长度yj,最优购运计划,约束条件,钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj 加yj；yj与 zj+1之和等于Aj Aj+1段的长度lj,基本模型,由Aj向Aj Aj-1段铺设的运量为 1+zj=zj(zj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+yj=yj(yj+1)/2,二次规划,模型求解,利用MATLAB软件包求解得：,