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

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

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

sm銷(xiāo)量d1d2…dn

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

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

┇sm銷(xiāo)量d1d2…dn

設(shè)xij

為從產(chǎn)地Ai

運(yùn)往銷(xiāo)地Bj

的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸變量表。銷(xiāo)地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)

于是得到下列一般運(yùn)輸問(wè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)

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

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

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

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

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

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

鋼管廠火車(chē)站450里程（km）（沿管道建有公路）引例鋼管訂購(gòu)和運(yùn)輸

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

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

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

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

yj與

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