數(shù)學建模運籌學模型(一)匯總

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

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

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

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

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

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

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

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