最优化问题及其基本概念

最优化问题及其基本概念第1页，课件共24页，创作于2023年2月一、最优化问题举例利用最优化理论和方法解决生产实践以及科学研究中的具体问题，一般分为如下两个步骤：建立数学模型；进行数学加工和求解第2页，课件共24页，创作于2023年2月1、运输问题第3页，课件共24页，创作于2023年2月运输问题数据表销地产地B1B2

…Bn产量A1A2┇

Amc11c12

…c1nc21c22

…c2n┇┇┇┇cm1cm2

…cmns1s2┇

sm销量d1d2

…dn

第4页，课件共24页，创作于2023年2月销地产地B1B2

…Bn产量A1A2

┇Amx11x12

…x1nx21x22

…x2n┇┇┇┇xm1xm2

…xmns1s2

┇sm销量d1d2

…dn

设xij为从产地Ai

运往销地Bj

的运输量，根据这个运输问题的要求，可以建立运输变量表。第5页，课件共24页，创作于2023年2月

m

nMinf=cijxij

i=1j=1

n

s.t.xij

si

i=1,2,…,m

j=1

mxij

(=,)dj

j=1,2,…,n

i=1xij0(i=1,2,…,m;j=1,2,…,n)

于是得到下列一般运输问题的模型：第6页，课件共24页，创作于2023年2月

mn

Minf=cijxij

i=1j=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

xij≥0(i=1,2,…,m;j=1,2,…,n)

对于产销平衡问题，可得到下列运输问题的模型：第7页，课件共24页，创作于2023年2月在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；

产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，当产量大于销量时可加入一个虚设的销地去消化多余的物资。第8页，课件共24页，创作于2023年2月2、生产计划问题第9页，课件共24页，创作于2023年2月一般数学模型第10页，课件共24页，创作于2023年2月二、最优化方法的基本概念基本概念最优化问题的一些典型分类第11页，课件共24页，创作于2023年2月基本概念第12页，课件共24页，创作于2023年2月第13页，课件共24页，创作于2023年2月基本概念第14页，课件共24页，创作于2023年2月基本概念第15页，课件共24页，创作于2023年2月最优化问题的一些典型的分类函数优化问题与组合优化问题

线性规划问题与非线性最优化问题

多目标规划

第16页，课件共24页，创作于2023年2月最优化问题的一些典型的分类

第17页，课件共24页，创作于2023年2月由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km）（沿管道建有公路）引例钢管订购和运输

第18页，课件共24页，创作于2023年2月钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）第19页，课件共24页，创作于2023年2月（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形第20页，课件共24页，创作于2023年2月问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,

i=1,…7;j=1,…15

），铺设管道AjAj+1（j=1,…14)由Si至Aj的最小购运费用路线及最小费用cij

由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度zj及向AjAj+1段铺设的长度yj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；

yj与

zj+1之和等于AjAj+1段的长度lj第21页，课件共24页，创作于2023年2月基本模型由Aj向AjAj-1段铺设的运量为1+…+zj