數(shù)學(xué)建模運(yùn)籌學(xué)模型(一)匯總

1、運(yùn)籌學(xué)模型本章重點(diǎn)：線性規(guī)劃根底模型、目標(biāo)規(guī)劃模型、運(yùn)輸模型及其應(yīng)用、圖論模型、最小樹(shù)問(wèn)題、最短路問(wèn)題復(fù)習(xí)要求：1 .進(jìn)一步理解根本建模過(guò)程,掌握類比法、圖示法以及問(wèn)題分析、合理假設(shè)的內(nèi)涵.2 .進(jìn)一步理解數(shù)學(xué)模型的作用與特點(diǎn).本章復(fù)習(xí)重點(diǎn)是線性規(guī)劃根底模型、運(yùn)輸問(wèn)題模型和目標(biāo)規(guī)劃模型.具體說(shuō)來(lái),要求大家會(huì)建立簡(jiǎn)單的線性規(guī)劃模型,把實(shí)際問(wèn)題轉(zhuǎn)化為線性規(guī)劃模型的方法要掌握,當(dāng)然比擬簡(jiǎn)單.運(yùn)輸問(wèn)題模型主要要求善于將非線性規(guī)劃模型轉(zhuǎn)化為運(yùn)輸規(guī)化模型,這種轉(zhuǎn)化后求解相當(dāng)簡(jiǎn)單.你至少把一個(gè)很實(shí)際的問(wèn)題轉(zhuǎn)化為用表格形式寫出的模型,至于求解是另外一回事,一般不要求.目標(biāo)模型一般是比擬簡(jiǎn)單的線性規(guī)模模型在提出

2、新的要求之后轉(zhuǎn)化為目標(biāo)規(guī)劃模型.另外,關(guān)于圖論模型的問(wèn)題涉及到最短路問(wèn)題,具體說(shuō)來(lái)用雙標(biāo)號(hào)法來(lái)求解一個(gè)最短路模型.這之前恐怕要善于將一個(gè)實(shí)際問(wèn)題轉(zhuǎn)化為圖論模型.還有一個(gè)最小數(shù)的問(wèn)題,該如何把一個(gè)網(wǎng)絡(luò)中的最小數(shù)找到.另外在個(gè)別場(chǎng)合可能會(huì)涉及一筆劃問(wèn)題.1 .營(yíng)養(yǎng)配餐問(wèn)題的數(shù)學(xué)模型miZn=C1x1+C2x+Cnxn?a11x1+a12x2+a1nxnb?,a21x1+a22x2+a2nxn?s?b2,?ax+ax+axb,m22mmn1m?xj0(j=1,2,n或更簡(jiǎn)潔地表為miZn=ECxjj=1nj?n?Eaijxj?j=1S?t?x0(i=1,2,m?jj=1,2,n?其中的常數(shù)Cj表示第

3、j種食品的市場(chǎng)價(jià)格,aij表示第j種食品含第i種營(yíng)養(yǎng)的數(shù)量,bi表示人或動(dòng)物對(duì)第i種營(yíng)養(yǎng)的最低需求量.2.合理配料問(wèn)題的數(shù)學(xué)模型有m種資源B1,B2,Bm,可用于生產(chǎn)n種代號(hào)為A1,A2,An的產(chǎn)品.單位產(chǎn)品Aj需用資源Bi的數(shù)量為aij,獲利為Cj單位,第i種資源可供應(yīng)總量為bi個(gè)單位.問(wèn)如何安排生產(chǎn),使總利潤(rùn)到達(dá)最大設(shè)生產(chǎn)第j種產(chǎn)品xj個(gè)單位(j=1,2,n),那么有maZx=C1x1+C2x2+Cnxn?a11x1+a12x2+a1nxn?ba121x1+a22x2+a2nxn?s?電bl,?ax+ax+ax0(j=1,2,n或更簡(jiǎn)單地寫為mazx=Z2Cj=1njxj?n?Eaijxj

4、?j=1bsi?t?i=1,2,m?x0j=1,2,?j?3.運(yùn)輸問(wèn)題模型運(yùn)輸問(wèn)題也是一種線性規(guī)劃問(wèn)題,只是決策變量設(shè)置為雙下標(biāo)變量.假設(shè)問(wèn)題具有m個(gè)產(chǎn)地和n個(gè)銷地,第i個(gè)產(chǎn)地用Ai表示,其產(chǎn)量為ai(i=1,2,m),第j個(gè)銷地用Bj表示,其銷量為bj(j=1,2,n),從Ai運(yùn)往Bj的運(yùn)價(jià)為cij,而寫成為Eai=1mi=Ebj加產(chǎn)銷平衡.那么產(chǎn)銷平衡運(yùn)輸問(wèn)題的一般模型可以minZ=ZjZjcijxij1 =1j=1mn?n?Exij=ai?j=1?ms?t?Exij=bj?i=1?i=1,2,m?xij0j=1,2?4.目標(biāo)規(guī)劃模型某工廠生產(chǎn)代號(hào)為I、R的兩種產(chǎn)品,這兩種產(chǎn)品都要經(jīng)甲、乙

5、兩個(gè)車間加工,并經(jīng)檢驗(yàn)與銷售兩部門處理.甲、乙兩車間每月可用生產(chǎn)工時(shí)分別為120小時(shí)和150小時(shí),每小時(shí)費(fèi)用分別為80元和20元,其它數(shù)據(jù)如下表表4-1產(chǎn)、甲車間加工乙車間加工(時(shí)/許)檢驗(yàn)錯(cuò)S?元州0利涮?死/件)1個(gè)1100n1330T5工廠領(lǐng)導(dǎo)希望給出一個(gè)可行性生產(chǎn)方案,使生產(chǎn)銷售及檢驗(yàn)等方面都能達(dá)標(biāo)問(wèn)題分析與模型假設(shè)經(jīng)與工廠總經(jīng)理交談,確定以下幾條：p1:檢驗(yàn)和銷售費(fèi)每月不超過(guò)4600元；p2:每月售出產(chǎn)品I不少于50件；p3:兩車間的生產(chǎn)工時(shí)充分利用重要性權(quán)系數(shù)按兩車間每小時(shí)費(fèi)用比確定；p4:甲車間加班不超過(guò)20小時(shí)；p5:每月售出產(chǎn)品II不少于80件；p6:兩車間加班總時(shí)數(shù)要有限制

6、對(duì)權(quán)系數(shù)分配參照第三優(yōu)先級(jí)模型建立設(shè)x1,x2分別為產(chǎn)品I和R的月產(chǎn)量,先建立一般約束條件組,依題設(shè)50x1+30x2x2802x1+x2飄初向總工時(shí)x1+3x20,dl,dl0=4600=50=120=150=20=80(l=1,2,65 .最小樹(shù)問(wèn)題一個(gè)圖中假設(shè)有幾個(gè)頂點(diǎn)及其邊的交替序列形成閉回路,我們就說(shuō)這個(gè)圖有圈；假設(shè)圖中所有連頂點(diǎn)間都有邊相接,就稱該圖是連通的；假設(shè)兩個(gè)頂點(diǎn)間有不止一條邊連接,那么稱該圖具有多重邊.一個(gè)圖被稱為是樹(shù)意味著該圖是連通的無(wú)圈的簡(jiǎn)單圖.在具有相同頂點(diǎn)的樹(shù)中,總賦權(quán)數(shù)最小的樹(shù)稱為最小樹(shù)最小樹(shù)的求法有兩種,一種稱為避圈法,一種是被圈法,兩法各具優(yōu)缺點(diǎn),它們具有共

7、同的特征一一去掉圖中的圈并且每次都是去掉圈中邊權(quán)較大的邊.6 .最短路問(wèn)題的數(shù)學(xué)模型最短路問(wèn)題一般描述如下：在一個(gè)圖(或者說(shuō)網(wǎng)絡(luò))中,給定一個(gè)始點(diǎn)vs和一個(gè)終點(diǎn)vt,求vs到vt的一條路,使路長(zhǎng)最短(即路的各邊權(quán)數(shù)之和最小).狄克斯屈(E.D.Dijkstra)雙標(biāo)號(hào)法該法亦稱雙標(biāo)號(hào)法,適用于所有權(quán)數(shù)均為非負(fù)(即一切wij0w表示頂點(diǎn)vi與vj的邊的權(quán)數(shù))的網(wǎng)絡(luò),能夠求出網(wǎng)絡(luò)的任一點(diǎn)vs到其它各點(diǎn)的最短路,為目前求這類網(wǎng)絡(luò)最短路的最好算法.該法在施行中,對(duì)每一個(gè)點(diǎn)vj都要賦予一個(gè)標(biāo)號(hào),并分為固定標(biāo)號(hào)P(vj)和臨時(shí)標(biāo)號(hào)T(vj)兩種,其含義如下：P(vj)從始點(diǎn)vs到vj的最短路長(zhǎng)；T(vj)

8、從始點(diǎn)vs到vj的最短路長(zhǎng)上界.一個(gè)點(diǎn)vj的標(biāo)號(hào)只能是上述兩種標(biāo)號(hào)之一.假設(shè)為T標(biāo)號(hào),那么需視情況修改,而一旦成為P標(biāo)號(hào),就固定不變了.開(kāi)始先給始點(diǎn)vs標(biāo)上P標(biāo)號(hào)0,然后檢查點(diǎn)vs,對(duì)其一切關(guān)聯(lián)邊(vs,vj)的終點(diǎn)vj,給出vj的T標(biāo)號(hào)wij;再在網(wǎng)絡(luò)的已有T標(biāo)號(hào)中選取最小者,把它改為P標(biāo)號(hào).以后每次都檢查剛得到P標(biāo)號(hào)那點(diǎn),按一定規(guī)那么修改其一切關(guān)聯(lián)邊終點(diǎn)的T標(biāo)號(hào),再在網(wǎng)絡(luò)的所有T標(biāo)號(hào)中選取最小者并把它改為P標(biāo)號(hào).這樣,每次都把一個(gè)T標(biāo)號(hào)點(diǎn)改為P標(biāo)號(hào)點(diǎn),由于網(wǎng)絡(luò)中總共有n個(gè)結(jié)點(diǎn),故最多只需n-1次就能把終點(diǎn)vt改為P標(biāo)號(hào).這意味著已求得了vs到vt的最短路.狄克斯屈標(biāo)號(hào)法的計(jì)算步驟如下：1令S=vs為固定標(biāo)號(hào)點(diǎn)集,=Vvs為臨時(shí)標(biāo)號(hào)點(diǎn)集,再令P(vi=0,vtCS;2檢查點(diǎn)vi,對(duì)其一切關(guān)聯(lián)邊(vi,vj)的終點(diǎn)vjC,計(jì)算并令minT(vj,P(vi+wij?T(vj3從一切vjC中選取并令minT(vj=T(vr?T(vr選取相應(yīng)的弧(vi,vr).再令Svr?S,vr?=?,那么停止,P(vj即vs至IJvj的最短路長(zhǎng),特另IP(v