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

1、一、最优化问题举例 利用最优化理论和方法解决生产实践以及科学研究中的具体问题，一般分为如下两个步骤： 建立数学模型； 进行数学加工和求解1、运输问题运输问题数据表 销地产地B1 B2 Bn产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量d1 d2 dn 销地产地B1 B2 Bn产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量d1 d2 dn 设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表。 m nMin f = cij xij

2、 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）当某些

3、运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，当产量大于销量时可加入一个虚设的销地去消化多余的物资。2、生产计划问题利润最大化）利润最大化）目标函数目标函数(约束条件约束条件 一般数学模型0, 8023 4022 60243 . .342 max321321321321321xxxxxxxxxxxxtsxxxz二、最优化方法的基本概念 基本概念 最优化问题的一些典型分类基本概念基本概念基本概念最优化问题的一些典型的分类最优化问题的一些典型的分类 函数优化问题函数优化问题与组合优化问题组合优化问题 线性规

4、划问题线性规划问题与非线性最优化问题非线性最优化问题 多目标规划多目标规划 最优化问题的一些典型的分类最优化问题的一些典型的分类 由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A1

5、5S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km）（沿管道建有公路）引例 钢管订购和运输钢管订购和运输 钢 厂 i1234567产 量 上 限 is80080010002000200020003000销 价ip（ 万 元 ）160155155160155150160钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601单位钢管的铁路运价

6、1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）（1）制定钢管的订购和运输计划，使总费用最小）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003061952027

7、20690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（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段铺设的长度

8、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)6(0, 0)5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1)3(15, 2 , 1)2(7 , 2 , 1,5000.) 1 ()1() 1(21 . 0min15117115171151151 yzjiyzxjlzyjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次规划模型求解模型求解利用利用MATLAB软件包求解得：软件包求解得：钢 厂S1S2S3S4S5S6S7订购量 800 800 10000 101515500总费用1278632