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

運(yùn)籌學(xué)例題解析（共6頁）-本頁僅作為預(yù)覽文檔封面，使用時(shí)請(qǐng)刪除本頁-

(一)線性規(guī)劃建模與求解B.樣題：活力公司準(zhǔn)備在5小時(shí)內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品。甲、乙兩種產(chǎn)品每生產(chǎn)1單位分別消耗2小時(shí)、1小時(shí)。又根據(jù)市場需求信息，乙產(chǎn)品的產(chǎn)量應(yīng)該至少是甲產(chǎn)品產(chǎn)量的3倍。已知甲、乙兩種產(chǎn)品每銷售1單位的利潤分別為3百元和1百元。請(qǐng)問：在5小時(shí)內(nèi)，甲、乙兩種產(chǎn)品各生產(chǎn)多少單位，才能夠使得總銷售利潤最大要求：1、建立該問題的線性規(guī)劃模型。2、用圖解法求出最優(yōu)解和最大銷售利潤值，并寫出解的判斷依據(jù)。如果不存在最優(yōu)解，也請(qǐng)說明理由。解：1、(1)設(shè)定決策變量：設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x、x「單T2⑵目標(biāo)函數(shù):maxz=2x+x■212尤+尤＜5尤＞3⑵目標(biāo)函數(shù):maxz=2x+x■212尤+尤＜5尤＞3尤21尤,尤＞0122、該問題中約束條件、目標(biāo)函數(shù)、可行域和頂點(diǎn)見圖1所示，其中可行域用陰影部分標(biāo)記，不等式約束條件及變量約束要標(biāo)出成立的方向，目標(biāo)函數(shù)只須畫出其中一條等值線，頂點(diǎn)用大寫英文字母標(biāo)記。(3)約束條件如下:s.t.〈1x2-240圖1x2^3穿(5,0B(1,3各個(gè)約束條件的邊界及其方向如圖1中直線和箭頭所示，其中陰影部分為可行域，由直線相交可得其頂點(diǎn)A(5,0)、B(1,3)和0(0,0)。畫出目標(biāo)函數(shù)的一條等值線CD：2x+x=0，它沿法線向上平移，目標(biāo)函數(shù)值2越來越大。當(dāng)目標(biāo)函數(shù)平移到線段AB^^2x結(jié)論：本題解的情形是：無窮多最優(yōu)解，理由:目標(biāo)函數(shù)等值線z=2x+x與約束條件2x+xW5的邊界平行。甲、乙兩種產(chǎn)品的最優(yōu)產(chǎn)量分別為&20)或(1,3)單位;「最大銷售利潤值等于5百元。(二)圖論問題的建模與求解樣題A.正考樣題(最短路問題的建模與求解，清華運(yùn)籌學(xué)教材編寫組第三版267-268頁例13)某企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)都要做出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購買一臺(tái)新設(shè)備，要付購買費(fèi)。但是變賣舊設(shè)備可以獲得殘值收入，連續(xù)使用1年、2年、3年、4年以上賣掉的設(shè)備殘值分

別為8萬元、6萬元、3萬元和0萬元。試制定一個(gè)5年的更新計(jì)劃，使總支出最少。已知設(shè)備在各年的購買費(fèi)與維修費(fèi)如表2所示。要求：（1）建立某種圖論模型；（2）求出最少總支出金額。表2.；.?-：:'■：-；■-站1年策？年茹$年第4年第5年VIIIJ212機(jī).蚱年船D?1］?Uf44心56301B解：（1）建立圖論一一最短路問題模型。設(shè)點(diǎn)V表示第i年年初，虛設(shè)一個(gè)點(diǎn)V,表示第五年年底；弧（V,’V）表示第i年初購進(jìn)一臺(tái)設(shè)備一直使用到第j年初（即第i-1年年底）再賣掉并獲得殘值收入；?。╒,V）上的權(quán)數(shù)表示第i年初購進(jìn)一臺(tái)設(shè)備，一直使用到第j年初所需支付的購買、j維修及抵扣殘值收入以后的全部費(fèi)用（單位：萬元）。例如：?。╒,V）上的費(fèi)用權(quán)數(shù)30=11+（5+6+8）-3=27（萬元）。_59898圖2v127（2）用Dijkstra法求解從V到V的最短路?！?16給起點(diǎn)V1標(biāo)號(hào)（0,v1）；={v_59898圖2v127（2）用Dijkstra法求解從V到V的最短路?！?16給起點(diǎn)V1標(biāo)號(hào)（0,v1）；={v};J={v,v,v,v,v}弧集合{［v,v］、［v,v］、1234561213［v1,v6］}s=l+b=0+8=8;s=l+b=0+16=16;s=l+b=0+27=27;121121311314114s=l+b=0+41=41;s=l+b=0+59=59151,1516116r、■/min{s,s,s,s,s}=min{8,16,27,41,59}=8=s=l1213141516122={v,v}J={v,v,v,v}一，1.23456弧集合{［v,v］、［v,v］［v2,v6］}1314s=l+b=8+8=16;s=l+b■/min{ss23=l={v,［v2［v3s:34=8+16=24;sE、［v2，v3［v1,v4］［v1，V5］、二給七標(biāo)號(hào)（8,v1）］、［v2,v4］、［v/J、=l+b=8+27=35;s=l+b=8+41=4923242242522526226,s,s,s,s,s,s,s}=min{16,27,41,59,16,24,35,49}=16二1314151623242526■,二任選一^s,選擇給v標(biāo)號(hào)（16,3U’vJJ={v4,,v］、［v,v］'526,v］'［v,v］、=l3+b3「16+9=25;s13，選擇給v3標(biāo)號(hào)（16,v1）。,v,v｝弧集合｛［v,v］、［v,v］、［v,v］、56141516［v3，v6］}s3=|6+b=16+27=35;s=l+b=8+41=493533526226s13或1415,16,24252634353624=l4二給v4標(biāo)號(hào)（24,v2）={v,v,v,v}J={v,v}弧集合{［v,v］、［v,v］、［v,v］、［v,v］、12345615162526

［v,v］、［v,v］、［v,v］、［v,v}TOC\o"1-5"\h\z35364546s=l+b=24+9=33;s=l+b=24+17=414544546446■/minis,s,s,s,s,s,s,s}=min{41,59,35,49,35,49,33,41}=33二s=l…，1516252635364546455二給v標(biāo)號(hào)（33,v）54={v,v,v,v,v}J={v}弧集合{［v,v］、［v,v］、［v,v］、［v,v］、12345616263646［v5,v6］}s=l+b=33+10=43/min{s,s,s,s,s}=min{59,49,49,41,43}=41二s=l565561626364656466二給v標(biāo)號(hào)（41,v）={饑6J={。}計(jì)算終止。由終點(diǎn)v標(biāo)號(hào)反向追蹤，可得到v到v的最短路：vTvTvTv,長度為l=41,即5年內(nèi)該設(shè)備的最小總支出金額為41萬元。1246B6考題復(fù)習(xí)知識(shí)點(diǎn)：最短路問題求解的基本思想請(qǐng)查閱課本或其他參考書籍，自行簡答總結(jié)。掌握用上述“Dijkstra標(biāo)號(hào)法”求解的步驟和處理方法，考試時(shí)書寫格式請(qǐng)參照本樣題。掌握最短路確定的反向追蹤方法和最短距離。考試題比此題計(jì)算量小。掌握?qǐng)D論問題建模的程序，會(huì)說明圖論模型各組分（弧或邊、節(jié)點(diǎn)、權(quán)數(shù)）的實(shí)際涵義。（三）動(dòng)態(tài)規(guī)劃一一“復(fù)合系統(tǒng)工作可靠性問題”建模和求解）A.正考樣題及其解答：某廠設(shè)計(jì)一種電子設(shè)備，由三種元件D1XD2XD3組成。已知這三種元件的單位價(jià)格、單位重量和可靠性如表4,要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過105元，重量不超過21克。問應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大。解：（1）建立動(dòng)態(tài)規(guī)劃模型按元件的種類數(shù)劃分階段，k=1,2,3。每階段階段第k種元件并聯(lián)幾個(gè)。狀態(tài)變量X表示第k階段初尚未使用的費(fèi)用；狀態(tài)變量y表示第k階段初剩余的可增加重量。顯然x=105,y=21,x>0,y>0。kkx-￡cy-￡kkk1wukx-￡cy-￡kkk1wuwmin（［k1wucy-乙w_kkk-j=k+i］,［j=k+i］,k=1,2cwkkwmin（［七］,［、］cwwkx-c?u；kkkDk（xk，yk）=l表示第k種元件的單位重量c表示第k種元件的單位費(fèi)用；狀態(tài)轉(zhuǎn)移方程：x=x-c-u；y=y-w-u。表示第k種元件的單位重量；最優(yōu)指標(biāo)階段指標(biāo)函數(shù)d（u）表示芫件S正常工作的概率1-（1-01<函數(shù)f（x,y）表示從元件D到元件D正常運(yùn)行的最大概率。；最優(yōu)指標(biāo)逆序^解法的基本方程如下；3f（尤，y）=max［d（u）-f（尤，y）］k=3,2,1kkkkkk+1k+1k+1uk6k（xk，yk）f4（氣,y4）=1

(2)用逆序解法求解[d(u)]=1-(1-0.5)u333①第3階段，k=3f(x,y)=max%Sin]/】,【專】]②第2階段，k=2f(x,y)=max|[1-(1-0.8)u2]-f(x-cu,y-wu)I222x/nv—53222222」第1階■檔1(【寸]嚀)f(x,y)=max[1-(1-0.9)u1]-f(x一30u,y一3u111x-20-15y_5-421111叫smin(【130]，【氣一4])由于xi=105,yi=21,故問題為求出f1(105,21)即可。而u1]?f(105-30u,21-[d(u)]=1-(1-0.5)u333u1]?f(105-30u,21-3u)]c11」[1-(1-0.9)max||105-20-1521—5—4,、1?u1■min([30】，【3】)=max[0.9f(75,18),0.9921Mu1S2f(75,18)=max2/5—2U18-5..1Su2Mmin([15],[4])max[0.8f(60,14),0.96

_31Mu2M33max45—2015^5,、1Mu2Mm邛15]，【4])max[0.8f(30,11)]=0.8f(30,11)u2=133max[1-(1-0.5)u3]=max(0.5,1Mu3mmin([票],[：])1Mu3M23205f(105,21)=1f(45,15)]20.8)u2]?f(753-15u,18

2f2(45,15)f3(60'14)],[f(45,10),0.9923[1-(1-0.8)u2]?f3(45f(30,6)]3-15u2,15-4u2)]0.75)=0.75u3]=max(0.5,0.75)=0.751Su3S2f(30,11)=max[1-(1-0.5)%]=max(0.5)=0.53-3U111Mummin([30],[11])f(45,15)u3]=max(0.5,0.75)=0.751Su3S2f(30,11)=max[1-(1-0.5)%]=max(0.5)=0.53-3U111Mummin([30],[11])f(45,15)=0.8f(3011)=0.8x0.5=0.4f(75,18)=max[0.8x0.75,096x075,0.992"3=1X0.5]=0.7231mummin([*],[6])u3-13205f](105,21)=max[0.9x0.72,0.99x0.4]=0.648狀態(tài)轉(zhuǎn)移圖如下:求得u*=1,u*=2,u*=2為最優(yōu)方案，即D、D、。三種元件分別并聯(lián).1231231個(gè)、2個(gè)和2個(gè)?？傎M(fèi)用為100元，總重量為21克，可靠性為。B.正考復(fù)習(xí)知識(shí)點(diǎn)：會(huì)按照樣題解答那樣分六步建立動(dòng)態(tài)規(guī)劃模型。文字說明方面：準(zhǔn)確說明各種變量的實(shí)際涵義；數(shù)學(xué)表達(dá)方面：能正確、規(guī)范地寫出逆序解法的基本方程，階段變量必須逆著寫取值，明確邊界條件；在建模時(shí)對(duì)取值明確的狀態(tài)變量應(yīng)該說明其具體值；會(huì)以規(guī)范的集合語言寫出允許決策集合的具體形式；具體寫出狀態(tài)轉(zhuǎn)移方程函數(shù)形式；寫出階段指標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式?？荚囶}目比此題的計(jì)算量要小，而且未必會(huì)考兩個(gè)狀態(tài)的情形。比照樣題中的解答步驟來書寫答題過程，會(huì)繪制“狀態(tài)轉(zhuǎn)移圖”并以此得出結(jié)論，會(huì)得出全過程最優(yōu)指標(biāo)函數(shù)值并給出依據(jù)。清華大學(xué)教材編寫組編寫《運(yùn)籌學(xué)》第三版237-238頁例8計(jì)算過程可以參考（但f（s）中乂的范圍有錯(cuò)，請(qǐng)按照課件第四章50-53張例來改正，答題格式也須參照后者；（四）線性目標(biāo)規(guī)劃或運(yùn)輸問題的建模和求解A.正考樣題一一非標(biāo)準(zhǔn)運(yùn)輸問題的建模與“表上作業(yè)法求解”有三個(gè)發(fā)電站產(chǎn)地B，B,B需要從兩個(gè)煤礦A,A購買煤炭，各自的產(chǎn)量、需求量以及每萬噸煤炭的運(yùn)價(jià)（千元）如表5所示：問如何調(diào)運(yùn)煤炭，使得總運(yùn)輸費(fèi)用最小表5產(chǎn)銷平衡表和單位運(yùn)價(jià)表發(fā)電站B煤礦AjB1B2B3產(chǎn)量（萬噸）iA2362236A21577212每月對(duì)煤的需求量（萬噸）315要求：（1）請(qǐng)建立該問題的線性規(guī)劃模型，如果有必要再化為標(biāo)準(zhǔn)問題。（2）用表上作業(yè)法求解：用最小元素法確定初始方案；用閉回路法或者位勢法驗(yàn)證初始方案是否最優(yōu)如果非最優(yōu)，請(qǐng)用閉回路法調(diào)整，直至求出最優(yōu)方案。解：（1）設(shè)產(chǎn)地A（i=1,2）調(diào)運(yùn)到銷地B（j=1,2,3）的煤炭為x萬噸，可建立以下模型：’jijTOC\o"1-5"\h\zminz=22S3c-x=23x+62x+23x+15x+77x+21xijij111213212223i=1j=1x11+x12+x13=6x+x+x=2212223x+x<3x+x<1x+x<5x">0(i=1,2;j=1,2,3)(2)因?yàn)榭偖a(chǎn)量8萬噸(=6+2)小于總需求量9萬噸(=3+1+5)，所以本問題不是標(biāo)準(zhǔn)運(yùn)輸問題。增加一個(gè)虛擬產(chǎn)地A3，它的單位運(yùn)價(jià)c31=c32=c33=0，產(chǎn)量為9-8=1（萬噸）。3（3）第一步：用最小元素法確定初始方案（方案可能有以下三種，隨著添加0位置不同而不同：。

，?小CXl、，?小CXl、rr-i23(0)62(1)23⑶6(1)(0)15(2)77212(0)0(1)001(0)315(2)(0)(0)(0)15151方法二：伏格爾法（本題用此法求出的初始基可行解就是最優(yōu)解）__，(1)6Ti(0)I2,;2__，(1)6Ti(0)I2,;2[0](5)(0)，(2)712[6](0)〔1[(!58]J01[7(0(1)7])([2(1j12：■01[0](0)105法一：用位勢法求檢驗(yàn)數(shù)。求解見表6所示：表6銷地產(chǎn)地B1B2B3UiA0230620230A0152377621-82A300-39000-23V236223因?yàn)閙in%,%,%為海|變」<0）二。32=-39<0,所以初始方案并非最優(yōu)方法二：用閉回路法求檢2驗(yàn)數(shù)土23(0)62(1)23(5)15(2)7721o22=77-15+23-62=23;o疽21-15+23-23=6;o33=0-0+23-0(1)0022233323=0；o=0-0+23-62=-39(注：圖中畫出了非基變量x的閉回路)；因?yàn)閙in(o22,o,o32,o3|0「<