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

一、最优化问题举例利用最优化理论和方法解决生产实践以及科学研究中的具体问题，一般分为如下两个步骤：建立数学模型；进行数学加工和求解一、最优化问题举例利用最优化理论和方法解决生产实践以及11、运输问题1、运输问题2运输问题数据表销地产地B1B2…Bn产量A1A2┇

Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇

sm销量d1d2…dn

运输问题数据表销地B1B2…B3销地产地B1B2…Bn产量A1A2

┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2

┇sm销量d1d2…dn

设xij

为从产地Ai

运往销地Bj

的运输量，根据这个运输问题的要求，可以建立运输变量表。销地B1B2…Bn产量A1x114

m

nMinf=

cijxij

i=1j=1

n

s.t.

xij

si

i=1,2,…,m

j=1

m

xij

(=,

)dj

j=1,2,…,n

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

于是得到下列一般运输问题的模型：mn5

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)

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

产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，当产量大于销量时可加入一个虚设的销地去消化多余的物资。在实际问题建模时，还会出现如下一些变化：产销不72、生产计划问题2、生产计划问题8一般数学模型一般数学模型9二、最优化方法的基本概念基本概念最优化问题的一些典型分类二、最优化方法的基本概念基本概念10基本概念基本概念11最优化问题及其基本概念课件12基本概念基本概念13基本概念基本概念14最优化问题的一些典型的分类函数优化问题与组合优化问题

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

多目标规划

最优化问题的一些典型的分类函数优化问题与组合优化问题15最优化问题的一些典型的分类

最优化问题的一些典型的分类16由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7

钢管厂火车站450里程（km）（沿管道建有公路）引例钢管订购和运输

由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A13217钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限18（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购19问题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问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输20基本模型由Aj向AjAj-1段铺设的运量为1