運籌學例題解析

1、(一)線性規(guī)劃建模與求解B.樣題：活力公司準備在5小時內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品。甲、乙兩種產(chǎn)品每生產(chǎn)1單位分別消耗2小時、1小時。又根據(jù)市場需求信息，乙產(chǎn)品的產(chǎn)量應該至少是甲產(chǎn)品產(chǎn)量的3倍。已知甲、乙兩種產(chǎn)品每銷售1單位的利潤分別為3百元和1百元。請問：在5小時內(nèi)，甲、乙兩種產(chǎn)品各生產(chǎn)多少單位，才能夠使得總銷售利潤最大？要求：1、建立該問題的線性規(guī)劃模型。2、用圖解法求出最優(yōu)解和最大銷售利潤值，并寫出解的判斷依據(jù)。如果不存在最優(yōu)解，也請說明理由。解：1、(1)設定決策變量： 設甲、乙兩種產(chǎn)品分別生產(chǎn)x1、x2單位 。(2)目標函數(shù)： max z=2 x1+x2 (3)約束條件如下：求解過程如下：1

2、.各個約束條件的邊界及其方向如圖1中直線和箭頭所示，其中陰影部分為可行域，由直線相交可得其頂點A(5,0)、B(1,3)和O(0,0)。2. 畫出目標函數(shù)的一條等值線CD：2x1+x2=0，它沿法線向上平移，目標函數(shù)值z越來越大。3. 當目標函數(shù)平移到線段AB時時，zMax z。2、該問題中約束條件、目標函數(shù)、可行域和頂點見圖1所示，其中可行域用陰影部分標記，不等式約束條件及變量約束要標出成立的方向，目標函數(shù)只須畫出其中一條等值線，頂點用大寫英文字母標記。2x1+x25O54 3 2 1-1 x2-2 -1 0 1 2 3 4 5x1圖1A(5,0)B(1,3)CDMaxx23 x1結論：本題

3、解的情形是： 無窮多最優(yōu)解 ，理由： 目標函數(shù)等值線z=2 x1+x2與約束條件2 x1+x25的邊界平行 。甲、乙兩種產(chǎn)品的最優(yōu)產(chǎn)量分別為 (5,0)或(1,3)單位；最大銷售利潤值等于 5 百元。（二）圖論問題的建模與求解樣題A.正考樣題（最短路問題的建模與求解，清華運籌學教材編寫組第三版267-268頁例13）某企業(yè)使用一臺設備，每年年初，企業(yè)都要做出決定，如果繼續(xù)使用舊的，要付維修費；若購買一臺新設備，要付購買費。但是變賣舊設備可以獲得殘值收入，連續(xù)使用1年、2年、3年、4年以上賣掉的設備殘值分別為8萬元、6萬元、3萬元和0萬元。試制定一個5年的更新計劃，使總支出最少。已知設備在各年的

4、購買費與維修費如表2所示。要求：（1）建立某種圖論模型；（2）求出最少總支出金額。表2解：（1）建立圖論最短路問題模型。設點Vi表示第i年年初，虛設一個點V6，表示第五年年底；弧(Vi, Vj)表示第i年初購進一臺設備一直使用到第j年初(即第i-1年年底)再賣掉并獲得殘值收入；171741282741v6v527v4v2v31616988v110959圖2弧(Vi, Vj)上的權數(shù)表示第i年初購進一臺設備，一直使用到第j年初所需支付的購買、維修及抵扣殘值收入以后的全部費用（單位：萬元）。例如：弧(V1, V4)上的費用權數(shù)30=11+(5+6+8)-3=27(萬元)。模型如圖2所示：（2）用D

5、ijkstra法求解從V1到V6的最短路。給起點V1標號（0,v1）；1.I=v1 ; J=v2,v3,v4,v5,v6 弧集合v1,v2、v1,v3 、v1,v4 、v1,v5 、v1,v6 s12=l1+b12=0+8=8;s13=l1+b13=0+16=16;s14=l1+b14=0+27=27; s15=l1+b15=0+41=41;s16=l1+b16=0+59=59mins12,s13,s14,s15,s16=min8,16,27,41,59=8= s12=l2 給v2標號（8,v1）2.I=v1,v2 J= v3,v4,v5,v6 弧集合v1,v3 、v1,v4 、v1,v5 、

6、v1,v6 、 v2,v3、v2,v4、v2,v5、v2,v6s23=l2+b23=8+8=16;s24=l2+b24=8+16=24;s25=l2+b25=8+27=35;s26=l2+b26=8+41=49mins13,s14,s15,s16,s23,s24,s25,s26=min16,27,41,59,16,24,35,49=16= s13或s23=l3 ， 任選一個s13，選擇給v3標號（16, v1）。3.I=v1,v2,v3 J=v4,v5,v6 弧集合v1,v4、v1,v5 、v1,v6 、v2,v4、v2,v5 、v2,v6、v3,v4、v3,v5 、v3,v6 s34=l3+

7、b34=16+9=25; s35=l3+b35=16+27=35;s26=l2+b26=8+41=49 mins14,s15,s16,s24,s25,s26,s34,s35,s36=min27,41,59,24,35,49,25,35,49=24=s24=l4 給v4標號（24,v2）4.I=v1,v2,v3,v4 J=v5,v6 弧集合 v1,v5 、v1,v6 、v2,v5 、v2,v6、 v3,v5 、v3,v6、v4,v5 、v4,v6 s45=l4+b45=24+9=33; s46=l4+b46=24+17=41 mins15,s16,s25,s26,s35,s36,s45,s46=

8、min41,59,35,49,35,49,33,41=33=s45=l5 給v5標號（33,v4）5.I=v1,v2,v3,v4,v5 J=v6 弧集合 v1,v6、v2,v6、v3,v6、v4,v6、v5,v6 s56=l5+b56=33+10=43 mins16,s26,s36,s46,s56=min59,49,49,41,43=41=s46=l6 給v6標號（41,v4）6.I= J= 計算終止。由終點v6標號反向追蹤，可得到v1到v6的最短路：v1v2v4v6,長度為l6=41,即5年內(nèi)該設備的最小總支出金額為41萬元。B.考題復習知識點：1.最短路問題求解的基本思想？請查閱課本或其他

9、參考書籍，自行簡答總結。2.掌握用上述“Dijkstra標號法”求解的步驟和處理方法，考試時書寫格式請參照本樣題。3.掌握最短路確定的反向追蹤方法和最短距離?？荚囶}比此題計算量小。4.掌握圖論問題建模的程序，會說明圖論模型各組分（弧或邊、節(jié)點、權數(shù)）的實際涵義。（三）動態(tài)規(guī)劃“復合系統(tǒng)工作可靠性問題”建模和求解）A正考樣題及其解答：某廠設計一種電子設備，由三種元件D1、D2、D3組成。已知這三種元件的單位價格、單位重量和可靠性如表4，要求在設計中所使用元件的費用不超過105元，重量不超過21克。問應如何設計使設備的可靠性達到最大。解：（1）建立動態(tài)規(guī)劃模型按元件的種類數(shù)劃分階段，k1,2,3。

10、每階段階段第k種元件并聯(lián)幾個。狀態(tài)變量xk表示第k階段初尚未使用的費用；狀態(tài)變量yk表示第k階段初剩余的可增加重量。顯然x1=105,y1=21,xk0,yk0 。決策變量uk表示第k階段元件Dk并聯(lián)的個數(shù)。允許決策集合：ck表示第k種元件的單位費用；wk表示第k種元件的單位重量；狀態(tài)轉(zhuǎn)移方程：xk+1 xk-ckuk ； yk+1yk-wkuk 。階段指標函數(shù)dk(uk)表示元件Dk正常工作的概率 ；最優(yōu)指標函數(shù)fk(xk ,yk)表示從元件Dk到元件D3 正常運行的最大概率。逆序解法的基本方程如下：（2）用逆序解法求解第3階段，k=3第2階段，k=2 第1階段，k=1由于x1=105,y1

11、=21,故問題為求出f1(105,21)即可。而狀態(tài)轉(zhuǎn)移圖如下：結論： 求得u*1=1, u*2=2,u*3=2為最優(yōu)方案，即D1、 D2、 D3三種元件分別并聯(lián)1個、2個和2個?？傎M用為100元，總重量為21克，可靠性為0.648。B.正考復習知識點：1.會按照樣題解答那樣分六步建立動態(tài)規(guī)劃模型。文字說明方面：準確說明各種變量的實際涵義；數(shù)學表達方面：能正確、規(guī)范地寫出逆序解法的基本方程，階段變量必須逆著寫取值，明確邊界條件；在建模時對取值明確的狀態(tài)變量應該說明其具體值；會以規(guī)范的集合語言寫出允許決策集合的具體形式；具體寫出狀態(tài)轉(zhuǎn)移方程函數(shù)形式；寫出階段指標函數(shù)的數(shù)學表達式?？荚囶}目比此題的

12、計算量要小，而且未必會考兩個狀態(tài)的情形。2.比照樣題中的解答步驟來書寫答題過程，會繪制“狀態(tài)轉(zhuǎn)移圖”并以此得出結論，會得出全過程最優(yōu)指標函數(shù)值并給出依據(jù)。3.清華大學教材編寫組編寫運籌學第三版237-238頁例8計算過程可以參考（但fk(sk)中xk的范圍有錯，請按照課件第四章50-53張例4.6.1來改正，答題格式也須參照后者。（四）線性目標規(guī)劃或運輸問題的建模和求解A.正考樣題非標準運輸問題的建模與“表上作業(yè)法求解”有三個發(fā)電站產(chǎn)地B1，B2，B3需要從兩個煤礦A1，A2購買煤炭，各自的產(chǎn)量、需求量以及每萬噸煤炭的運價（千元）如表5所示。問如何調(diào)運煤炭，使得總運輸費用最小？表5 產(chǎn)銷平衡表

13、和單位運價表 發(fā)電站Bj煤礦AiB1B2B3產(chǎn)量（萬噸）A12362236A21577212每月對煤的需求量（萬噸）315要求：（1）請建立該問題的線性規(guī)劃模型，如果有必要再化為標準問題。（2）用表上作業(yè)法求解：用最小元素法確定初始方案；用閉回路法或者位勢法驗證初始方案是否最優(yōu)？如果非最優(yōu)，請用閉回路法調(diào)整，直至求出最優(yōu)方案。解：（1）設產(chǎn)地Ai（i=1,2）調(diào)運到銷地Bj（j=1,2,3）的煤炭為xij萬噸，可建立以下模型： （2）因為總產(chǎn)量8萬噸（=6+2）小于總需求量9萬噸（=3+1+5），所以本問題不是標準運輸問題。增加一個虛擬產(chǎn)地A3，它的單位運價c31=c32=c33=0，產(chǎn)量為9

14、-8=1（萬噸）。（3）第一步：用最小元素法確定初始方案（方案可能有以下三種，隨著添加0位置不同而不同）。 或或方法二：伏格爾法（本題用此法求出的初始基可行解就是最優(yōu)解） 第二步：求非基變量檢驗數(shù)，驗證初始方案(最小元素法求得的第一種初始方案)是否最優(yōu)。法一：用位勢法求檢驗數(shù)。求解見表6所示： 表6銷地產(chǎn)地B1B2B3UiA10230620230A20152377621-8A300-39000-23Vj236223 因為min(22,23,32,33|ij0)=32=-390，所以初始方案并非最優(yōu)方案，需進一步調(diào)整，x32為進基變量。法二：用閉回路法求檢驗數(shù)22=77-15+23-62=23;23=21-15+23-23=6;33=0-0+23-23=0；32=0-0+23-62=-39（注：圖中畫出了非基變量x32的閉回路）；因為min(22,23,32,33|ij0)32=-390，所以方案二就是唯一最優(yōu)方案。決策結論：產(chǎn)地A1向銷地B1調(diào)運煤炭1萬噸，向銷地B3調(diào)運煤炭5萬噸；產(chǎn)地A2向銷地B1調(diào)運煤炭2萬噸；銷地B2的需求量由虛擬產(chǎn)地A3來滿足，實際上它的需求量1萬噸完全未得到滿足。最小總運費=231+062+235+152+01=168（千元）。B.正考復習知識點：（1）本題是“銷大于產(chǎn)”的非標準問題，但考試時也有可能考“產(chǎn)大于銷”的非標準化問題。那么