最優(yōu)化問題及其基本概念課件

一、最優(yōu)化問題舉例利用最優(yōu)化理論和方法解決生產(chǎn)實踐以及科學(xué)研究中的具體問題，一般分為如下兩個步驟：建立數(shù)學(xué)模型；進行數(shù)學(xué)加工和求解一、最優(yōu)化問題舉例利用最優(yōu)化理論和方法解決生產(chǎn)實踐以及11、運輸問題1、運輸問題2運輸問題數(shù)據(jù)表銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2┇

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

sm銷量d1d2…dn

運輸問題數(shù)據(jù)表銷地B1B2…B3銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2

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

┇sm銷量d1d2…dn

設(shè)xij

為從產(chǎn)地Ai

運往銷地Bj

的運輸量，根據(jù)這個運輸問題的要求，可以建立運輸變量表。銷地B1B2…Bn產(chǎn)量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)

對于產(chǎn)銷平衡問題，可得到下列運輸問題的模型：mn對于產(chǎn)銷平衡問題，可得6在實際問題建模時，還會出現(xiàn)如下一些變化：（1）有時目標(biāo)函數(shù)求最大，如求利潤最大或營業(yè)額最大等；（2）當(dāng)某些運輸線路上的能力有限制時，模型中可直接加入（等式或不等式）約束；

產(chǎn)銷不平衡的情況。當(dāng)銷量大于產(chǎn)量時可加入一個虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資，當(dāng)產(chǎn)量大于銷量時可加入一個虛設(shè)的銷地去消化多余的物資。在實際問題建模時，還會出現(xiàn)如下一些變化：產(chǎn)銷不72、生產(chǎn)計劃問題2、生產(chǎn)計劃問題8一般數(shù)學(xué)模型一般數(shù)學(xué)模型9二、最優(yōu)化方法的基本概念基本概念最優(yōu)化問題的一些典型分類二、最優(yōu)化方法的基本概念基本概念10基本概念基本概念11最優(yōu)化問題及其基本概念課件12基本概念基本概念13基本概念基本概念14最優(yōu)化問題的一些典型的分類函數(shù)優(yōu)化問題與組合優(yōu)化問題

線性規(guī)劃問題與非線性最優(yōu)化問題

多目標(biāo)規(guī)劃

最優(yōu)化問題的一些典型的分類函數(shù)優(yōu)化問題與組合優(yōu)化問題15最優(yōu)化問題的一些典型的分類

最優(yōu)化問題的一些典型的分類16由鋼管廠訂購鋼管，經(jīng)鐵路、公路運輸，鋪設(shè)一條鋼管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1~S7

鋼管廠火車站450里程（km）（沿管道建有公路）引例鋼管訂購和運輸

由鋼管廠訂購鋼管，經(jīng)鐵路、公路運輸，鋪設(shè)一條鋼管管道A13217鋼廠的產(chǎn)量和銷價（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管1單位鋼管的鐵路運價1000km以上每增加1至100km運價增加5萬元1單位鋼管的公路運價：0.1萬元/km（不足整公里部分按整公里計）鋼廠的產(chǎn)量和銷價（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限18（1）制定鋼管的訂購和運輸計劃，使總費用最小.（2）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的變化影響最大；哪個鋼廠鋼管產(chǎn)量上限的變化影響最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）討論管道為樹形圖的情形（1）制定鋼管的訂購和運輸計劃，使總費用最小.（2）分析對購19問題1的基本模型和解法總費用最小的優(yōu)化問題總費用：訂購，運輸（由各廠Si經(jīng)鐵路、公路至各點Aj,

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

），鋪設(shè)管道AjAj+1（j=1,…14)由Si至Aj的最小購運費用路線及最小費用cij

由Si至Aj的最優(yōu)運量xij由Aj向AjAj-1段鋪設(shè)的長度zj及向AjAj+1段鋪設(shè)的長度yj最優(yōu)購運計劃約束條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）運量約束：xij對i求和等于zj加yj；

yj與

zj+1之和等于AjAj+1段的長度lj問題1的基本模型和解法總費用最小的優(yōu)化問題總費用：訂購，運輸20基本模型由Aj向AjAj-1段鋪設(shè)的運量為1