數(shù)學(xué)建模運籌學(xué)模型一

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

2、線性規(guī)模模型在提出新的要求之后轉(zhuǎn)化為目標(biāo)規(guī)劃模型. 另外，關(guān)于圖論模型的問題涉及到最短路問題，具體說來用雙標(biāo)號法來求解一個最短路模型. 這之前恐怕要善于將一個實際問題轉(zhuǎn)化為圖論模型. 還有一個最小數(shù)的問題，該如何把一個網(wǎng)絡(luò)中的最小數(shù)找到. 另外在個別場合可能會涉及一筆劃問題.1. 營養(yǎng)配餐問題的數(shù)學(xué)模型或更簡潔地表為其中的常數(shù)C j 表示第 j 種食品的市場價格， a ij 表示第 j 種食品含第i 種營養(yǎng)的數(shù)量， b i 表示人或動物對第i 種營養(yǎng)的最低需求量 .2. 合理配料問題的數(shù)學(xué)模型有m種資源1， 2 ， ，m，可用于生產(chǎn)n種代號為1 ， 2， ，n 的產(chǎn)品 . 單位產(chǎn)品j 需用資源

3、i 的數(shù)量為ij ，獲利為j 單B BBA AAABaC位，第 i 種資源可供給總量為bi 個單位 . 問如何安排生產(chǎn)，使總利潤達(dá)到最大？設(shè)生產(chǎn)第 j種產(chǎn)品 xj 個單位（ j =1，2， ， n），則有或更簡單地寫為3. 運輸問題模型運輸問題也是一種線性規(guī)劃問題， 只是決策變量設(shè)置為雙下標(biāo)變量. 假如問題具有 m個產(chǎn)地和 n 個銷地，第 i 個產(chǎn)地用Ai表示，mn其產(chǎn)量為a（ii=1，2， ， ），第個銷地用j 表示，其銷量為j （=1，2， ， ），從 i 運往j 的運價為cij ， 而aibjmjBb jnABi1j1表示產(chǎn)銷平衡 . 那么產(chǎn)銷平衡運輸問題的一般模型可以寫成為4. 目標(biāo)規(guī)

4、劃模型某工廠生產(chǎn)代號為、的兩種產(chǎn)品，這兩種產(chǎn)品都要經(jīng)甲、乙兩個車間加工，并經(jīng)檢驗與銷售兩部門處理. 已知甲、乙兩車間每月可用生產(chǎn)工時分別為120 小時和 150 小時，每小時費用分別為80 元和 20 元，其它數(shù)據(jù)如下表表 4-1項目甲車間加工乙車間加工檢驗銷售利 潤數(shù)據(jù)（時/ 件）（元 /件）（元/件）（時/ 件）產(chǎn)品2150100133075工廠領(lǐng)導(dǎo)希望給出一個可行性生產(chǎn)方案，使生產(chǎn)銷售及檢驗等方面都能達(dá)標(biāo).問題分析與模型假設(shè)經(jīng)與工廠總經(jīng)理交談，確定下列幾條：p1 ： 檢驗和銷售費每月不超過4600 元；p2 ： 每月售出產(chǎn)品I 不少于 50 件；p3 ： 兩車間的生產(chǎn)工時充分利用（重要性

5、權(quán)系數(shù)按兩車間每小時費用比確定）p4 ：甲車間加班不超過20 小時；p5 ：每月售出產(chǎn)品不少于80 件；p6 ：兩車間加班總時數(shù)要有控制（對權(quán)系數(shù)分配參照第三優(yōu)先級）.；模型建立設(shè) x1 ，x2 分別為產(chǎn)品和的月產(chǎn)量，先建立一般約束條件組，依題設(shè)50 x130x24600檢驗銷售費用售出量x2802x1x2120設(shè) d兩車間總工, 相應(yīng)的目標(biāo)約束為1 表檢驗銷售費偏差，則希望d1 達(dá)最小，有p1d15x130 x2d1d1= 4600 ；d 2 表產(chǎn)品 I售量偏差，則希望d2 達(dá)最小，有p2 d2 , 相應(yīng)的目標(biāo)約束以d3、 4 表兩車間生產(chǎn)工時偏差， 則由于充分利用， 故希望d3, d4 達(dá)

6、最小，考慮到費用比例為80：20=4：1，有 p3 (4d3d 4 ) .d相應(yīng)的目標(biāo)約束應(yīng)為2x1x2d3d3120 和 x1 3x2d 4d 4=150，以 d5 表甲車間加班偏差，則有p4 d5 , 相應(yīng)目標(biāo)約束為d3d5d520 ，以 d6 表產(chǎn)品售量偏差，則希望d6 達(dá)最小，有相應(yīng)約束為x2d6d680 .最后優(yōu)先級p6 可利用 d3d4 表示，考慮到權(quán)系數(shù)，有p6 ( 4d3d4 ), 其目標(biāo)約束由于利用超生產(chǎn)工時，已在工時限制中體現(xiàn)，于是得到該問題的目標(biāo)規(guī)劃模型為5. 最小樹問題一個圖中若有幾個頂點及其邊的交替序列形成閉回路，我們就說這個圖有圈；若圖中所有連頂點間都有邊相接，就稱

7、該圖是連通的；若兩個頂點間有不止一條邊連接，則稱該圖具有多重邊.一個圖被稱為是樹 意味著該圖是連通的無圈的簡單圖.在具有相同頂點的樹中，總賦權(quán)數(shù)最小的樹稱為最小樹.最小樹的求法有兩種，一種稱為“避圈法”，一種是“破圈法” ，兩法各具優(yōu)缺點，它們具有共同的特征去掉圖中的圈并且每次都是去掉圈中邊權(quán)較大的邊.6. 最短路問題的數(shù)學(xué)模型最短路問題一般描述如下：在一個圖（或者說網(wǎng)絡(luò)）中，給定一個始點vs 和一個終點 vt ，求 vs 到 vt 的一條路，使路長最短（即路的各邊權(quán)數(shù)之和最?。?.狄克斯屈（）雙標(biāo)號法該法亦稱雙標(biāo)號法，適用于所有權(quán)數(shù)均為非負(fù)（即一切wij 0wij表示頂點 vi 與 vj 的

8、邊的權(quán)數(shù)）的網(wǎng)絡(luò)，能夠求出網(wǎng)絡(luò)的任一點 vs 到其它各點的最短路，為目前求這類網(wǎng)絡(luò)最短路的最好算法.該法在施行中，對每一個點vj 都要賦予一個標(biāo)號，并分為固定標(biāo)號（j ）和臨時標(biāo)號（j ）兩種，其含義如下：PvT v（ j ）從始點vs 到vj 的最短路長；P v（ j ）從始點vs 到vj 的最短路長上界 .T v一個點 vj 的標(biāo)號只能是上述兩種標(biāo)號之一. 若為 T 標(biāo)號，則需視情況修改，而一旦成為P 標(biāo)號，就固定不變了 .P 標(biāo)號點，因為網(wǎng)絡(luò)中總共有開始先給始點vs 標(biāo)上 P 標(biāo)號 0，然后檢查點vs，對其一切關(guān)聯(lián)邊（vs， v j ）的終點 vj ，給出 vj 的 T 標(biāo)號標(biāo)號中選取最

9、小者，把它改為P 標(biāo)號 . 以后每次都檢查剛得到P標(biāo)號那點，按一定規(guī)則修改其一切關(guān)聯(lián)邊終點的的所有 T 標(biāo)號中選取最小者并把它改為P 標(biāo)號 . 這樣，每次都把一個T 標(biāo)號點改為wij ；再在網(wǎng)絡(luò)的已有TT 標(biāo)號，再在網(wǎng)絡(luò)n 個結(jié)點，故最多只需 n-1 次就能把終點vt 改為 P 標(biāo)號 . 這意味著已求得了vs 到 vt 的最短路 .狄克斯屈標(biāo)號法的計算步驟如下：1°令 S= vs 為固定標(biāo)號點集，SV vs 為臨時標(biāo)號點集，再令 P( vi )0 ， vtS ；2°檢查點i ，對其一切關(guān)聯(lián)邊（vi ，vj ）的終點v jS ，計算并令v3°從一切 vjS 中選取并令選取相應(yīng)的弧（vi ， v r） . 再令4°若 S，則停止， P( vj) 即 vs 到 vj 的最短路長，特別P(vt ) 即 vs 到 vt 的最短路長，而已選出的弧即給出v