運(yùn)籌學(xué)例題解析

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

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

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

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

5、ijkstra法求解從V1到V6的最短路。給起點(diǎn)V1標(biāo)號(hào)（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標(biāo)號(hào)（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 ， 任選一個(gè)s13，選擇給v3標(biāo)號(hào)（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標(biāo)號(hào)（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標(biāo)號(hào)（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標(biāo)號(hào)（41,v4）6.I= J= 計(jì)算終止。由終點(diǎn)v6標(biāo)號(hào)反向追蹤，可得到v1到v6的最短路：v1v2v4v6,長(zhǎng)度為l6=41,即5年內(nèi)該設(shè)備的最小總支出金額為41萬(wàn)元。B.考題復(fù)習(xí)知識(shí)點(diǎn)：1.最短路問題求解的基本思想？請(qǐng)查閱課本或其他

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

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

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

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

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

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