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

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

2、線性規(guī)模模型在提出新的要求之后轉(zhuǎn)化為目標(biāo)規(guī)劃模型. 另外，關(guān)于圖論模型的問題涉及到最短路問題，具體說來用雙標(biāo)號法來求解一個(gè)最短路模型. 這之前恐怕要善于將一個(gè)實(shí)際問題轉(zhuǎn)化為圖論模型. 還有一個(gè)最小數(shù)的問題，該如何把一個(gè)網(wǎng)絡(luò)中的最小數(shù)找到. 另外在個(gè)別場合可能會(huì)涉及一筆劃問題.1. 營養(yǎng)配餐問題的數(shù)學(xué)模型或更簡潔地表為其中的常數(shù)C j 表示第 j 種食品的市場價(jià)格， a ij 表示第 j 種食品含第i 種營養(yǎng)的數(shù)量， b i 表示人或動(dòng)物對第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 個(gè)單位 . 問如何安排生產(chǎn)，使總利潤達(dá)到最大？設(shè)生產(chǎn)第 j種產(chǎn)品 xj 個(gè)單位（ j =1，2， ， n），則有或更簡單地寫為3. 運(yùn)輸問題模型運(yùn)輸問題也是一種線性規(guī)劃問題， 只是決策變量設(shè)置為雙下標(biāo)變量. 假如問題具有 m個(gè)產(chǎn)地和 n 個(gè)銷地，第 i 個(gè)產(chǎn)地用Ai表示，mn其產(chǎn)量為a（ii=1，2， ， ），第個(gè)銷地用j 表示，其銷量為j （=1，2， ， ），從 i 運(yùn)往j 的運(yùn)價(jià)為cij ， 而aibjmjBb jnABi1j1表示產(chǎn)銷平衡 . 那么產(chǎn)銷平衡運(yùn)輸問題的一般模型可以寫成為4. 目標(biāo)規(guī)

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

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

6、最小，考慮到費(fèi)用比例為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)工時(shí)，已在工時(shí)限制中體現(xiàn)，于是得到該問題的目標(biāo)規(guī)劃模型為5. 最小樹問題一個(gè)圖中若有幾個(gè)頂點(diǎn)及其邊的交替序列形成閉回路，我們就說這個(gè)圖有圈；若圖中所有連頂點(diǎn)間都有邊相接，就稱

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

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

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