物流運(yùn)籌學(xué)題庫(kù)

1、物流運(yùn)籌學(xué)題庫(kù)1、物流運(yùn)籌學(xué)的研究對(duì)象是什么？運(yùn)籌學(xué)的研究對(duì)象是有組織的系統(tǒng)， 解決的是其中的管理問(wèn)題。物流運(yùn)籌學(xué) 的研究對(duì)象就是物流系統(tǒng)中所遇到的與運(yùn)籌相關(guān)的問(wèn)題。2、運(yùn)籌學(xué)的開(kāi)展經(jīng)歷了哪些階段？運(yùn)籌學(xué)的開(kāi)展大致可以劃分為四個(gè)階段： 一戰(zhàn)、二戰(zhàn)以前的萌芽時(shí)期、二戰(zhàn) 期間的產(chǎn)生時(shí)期、二戰(zhàn)以后的開(kāi)展時(shí)期和成熟時(shí)期。3、物流運(yùn)籌學(xué)的主要內(nèi)容有哪些？物流運(yùn)籌學(xué)主要是運(yùn)用運(yùn)籌學(xué)的理論與方法研究物流領(lǐng)域的管理與決策問(wèn) 題。其具體內(nèi)容主要包括：規(guī)劃論包括線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃、整數(shù)規(guī)劃和動(dòng) 態(tài)規(guī)劃等、圖與網(wǎng)絡(luò)分析、工程方案技術(shù)、決策論、對(duì)策論、排隊(duì)論、存儲(chǔ)論4、某加工配送中心負(fù)責(zé)加工配送 A、B、C、D、E

2、五種產(chǎn)品，具體約束見(jiàn)表4, 應(yīng)如何安排生產(chǎn)可使該廠在現(xiàn)有條件下日產(chǎn)值最大？表4相關(guān)數(shù)據(jù)ABCDE生產(chǎn)能力件甲43200200乙10032100丙04212150價(jià)格元35222解 設(shè)Xj j=1, 2,，5是生產(chǎn)的A、B、C、D、E五種產(chǎn)品的數(shù)量,目標(biāo)函數(shù)是使日產(chǎn)值最大，得到以下線(xiàn)性規(guī)劃模型:maxz 3x1 5x2 2x3 2x4 2x54x-i3x22x3200X1 st.,4x23x42x5 1002x3x4 2x5 150Xj 0, j 1,2,5解之得最優(yōu)解為xi 27,X230,X31,X423,X52，最大目標(biāo)值為283。(2)線(xiàn)性規(guī)劃問(wèn)題寫(xiě)出它的對(duì)偶問(wèn)題，假設(shè)其對(duì)偶問(wèn)題的最優(yōu)解

3、為y： 4，y：1，試應(yīng)用對(duì)偶問(wèn)maxz2x1X25X36X42X3X48s.t 2為2x2X32X412Xj0,j1-111,4題的性質(zhì)，求原問(wèn)題的最優(yōu)解解其對(duì)偶問(wèn)題為min w 8y：12 y22 yi 2 y222y21st. y1 y25y1 2y26y1, y2 0由強(qiáng)對(duì)偶性知原問(wèn)題的最優(yōu)值為44。設(shè)最優(yōu)解為* t(X1 , X2,X3,X4)，,_ r *那么 2x1 x2 5x3 6x4 44，又y11, y1y25, y12y26由互補(bǔ)松弛性條件知2x1 x3 x48,2x1 2x2X32x412, X10, x20從而解得X；0, x20, x34, X44，即 X*(0,0

4、,4,4)t即為原問(wèn)題的最優(yōu)解。5、用對(duì)偶單純形法求解min z 2x1 3x2 4x3x1 2x2X32X| x23x3Xi,X2,X30先將約束不等式化為等式:maxz2x1 3x2 4x3Xi2X2 X3X42x1X23X3 X5Xj o, j 1,6其對(duì)應(yīng)初始單純形表見(jiàn)表1CjCiC2C3C4C5CB基bX1X2X3X4X50X4-3-1-2-1100X5-4【-2】1-301j9Zj-2T-3-400單純形表2CjCiC2C3C4C5CB基bX1X2X3X4X50X4-10【-2.5】0.51-0.5-2Xi21-0.51.50-0.5jCjZj0-4T-10-1最終單純形表3CjC

5、iC2C3C4C5CB基bX1X2X3X4X5-3X20.401-0.2-0.40.2-2Xi2.2101.4-0.2-0.4jCjZj00-1.8-1.6-0.2從表中可以看出檢驗(yàn)數(shù)行均小于等于零，基變量對(duì)應(yīng)的解均大于等于零，此時(shí)求得最終單純形表。從最終單純形表中可以看出，x*= 2.2, 0.4, 0，0，0，對(duì)應(yīng)目標(biāo)函數(shù)值為z*=5.6。&線(xiàn)性規(guī)劃問(wèn)題:maxz 5x1 5x2 13x3X x? 3x320s.t 12% 4x2 10x3 90X 0,j 1,川,3先用單純形法求出最優(yōu)解，然后分析在以下各種條件下，最優(yōu)解分別有什么 變化？ 約束條件一的右端由20變?yōu)?0; 目標(biāo)函數(shù)中Xj

6、的系數(shù)由13變?yōu)?；為系數(shù)列向量由變?yōu)樵黾右粋€(gè)約束條件2 3x2 5x3 50；增加一個(gè)變量X4，對(duì)應(yīng)系數(shù)為解化為標(biāo)準(zhǔn)型后用單純形法計(jì)算，如下表所示單純形法初始表1CjC1C2C3C4C5Cb基bX1X2X3X4X50X420-11【3】100X5901241001jCjZj-5513 t00單純形法表2CjC1C2C3C4C5CB基bX1xX3X4X513X320/3-1/3【1/3】11/300X580/346/32/30-1/31jCj可-2/32/3 t013/30單純形法表3CjC1C2C3C4C5CB基bX1X2X3X4X5X220-113100X510160-2-41j5Zj00

7、-2-50至此，所有的j 0, j 1,川,5，那么X (0,20,0,0,0)T是該線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解，對(duì)應(yīng)的目標(biāo)函數(shù)值為z5x, 5x2 13x3 100。 當(dāng)約束條件一的右端由20變?yōu)?0時(shí)，最優(yōu)解變?yōu)閄 (0,0,9,0,0)T，此對(duì)應(yīng)的目標(biāo)函數(shù)值為z5x! 5x2 13x3 117。 當(dāng)目標(biāo)函數(shù)中溝的系數(shù)由13變?yōu)?時(shí)，最優(yōu)解不變，目標(biāo)函數(shù)值也不變。1 、 0一 當(dāng)為系數(shù)列向量由變?yōu)闀r(shí)，最優(yōu)解不變，目標(biāo)函數(shù)值也不變。125 當(dāng)增加一個(gè)約束條件2x 3x 5x3 50時(shí)，最優(yōu)解變?yōu)閄 (0,50/3,0,0,0)T，此對(duì)應(yīng)的目標(biāo)函數(shù)值為z5x1 5x2 13x3 250/3。-3一一

8、 當(dāng)增加一個(gè)變量x4,對(duì)應(yīng)系數(shù)為2時(shí)，最優(yōu)解不變，目標(biāo)函數(shù)值也不變。7、某公司面臨一個(gè)是外包協(xié)作還是自行車(chē)生產(chǎn)的問(wèn)題。該問(wèn)題生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車(chē)間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可以自行生產(chǎn)，但產(chǎn)品丙必須由本廠鑄造才能保證質(zhì)量。 有關(guān)情況見(jiàn)表2-12,該公司種可利用的總工時(shí)為：鑄造8 000小時(shí)、機(jī)加工12 000 小時(shí)和裝配10 000小時(shí)。為使該公司獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品應(yīng)各 生產(chǎn)多少件？甲、乙兩種產(chǎn)品由該公司鑄造及外包協(xié)作鑄造各多少件？表2-12甲、乙、丙三種產(chǎn)品的工時(shí)與本錢(qián)、產(chǎn)品 工時(shí)與本錢(qián) 甲乙丙每時(shí)鑄造工時(shí)小時(shí)5107每

9、件機(jī)加工工時(shí)小時(shí)648每件裝配工時(shí)小時(shí)322自產(chǎn)鑄件每件成本元354外協(xié)鑄件每件成本元56機(jī)加工每件本錢(qián)元213裝配每件本錢(qián)元322每件產(chǎn)品售價(jià)元231816解 設(shè)捲、X2、X3分別為三道工序都有公司加工的甲、乙、丙三種產(chǎn)品的 件數(shù)，X4、X5分別為由外協(xié)鑄造再由該公司加工、 裝配的甲乙兩種產(chǎn)品的件數(shù) 每件產(chǎn)品的利潤(rùn)分別如下：每件產(chǎn)品甲全部自制的利潤(rùn)=233+2+3=15 元；每件產(chǎn)品甲由外協(xié)鑄造，其余自制的利潤(rùn) =235+2+3=13 元；每件產(chǎn)品乙全部自制的利潤(rùn)=18(5+1+2) =10 (元)；每件產(chǎn)品乙由外協(xié)鑄造，其余自制的利潤(rùn) =18(6+1+2) =9 (元);每件產(chǎn)品丙的利潤(rùn)=

10、16( 4+3+2)=8 (元)。建立此問(wèn)題的線(xiàn)性規(guī)劃問(wèn)題如下：maxz15x110X27X313x49x55x110X27X380006x14X28x36x44x512000s.t.3x12X22x33x42x510000Xj 0( j 1,2,3,4,5)經(jīng)計(jì)算得結(jié)果： X* (x1,x2,x3,x4,x5)T (1600,0,0,0,600)T , maxz 29400。 故最優(yōu)方案為：產(chǎn)品甲生產(chǎn)1 600件，全部由該公司自己鑄造；產(chǎn)品乙生產(chǎn) 600 件，由外協(xié)鑄造后再有該公司加工、裝配；產(chǎn)品丙不生產(chǎn)。8、A公司需制造2 000件的某種產(chǎn)品，這種產(chǎn)品可利用 A，B，C設(shè)備的任意一種 加工

11、，每種設(shè)備的生產(chǎn)準(zhǔn)備結(jié)束費(fèi)用， 生產(chǎn)該產(chǎn)品時(shí)的單件本錢(qián)，以及每種 設(shè)備的最大加工量如表8所示，試對(duì)此問(wèn)題建立整數(shù)規(guī)劃模型并求解。表8產(chǎn)品的準(zhǔn)備結(jié)束費(fèi)、生產(chǎn)本錢(qián)和最大加工量設(shè)備準(zhǔn)備結(jié)束費(fèi)(元)生產(chǎn)本錢(qián)(元:/ 件)最大加工數(shù)(件)A10010600B3002800C20051 200解設(shè)Xj為采用第j(j 1,2,3)種設(shè)備生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費(fèi)用為kj 5Xj(Xj0)Cj(Xj)式屮，kj為固疋本錢(qián)準(zhǔn)備結(jié)束費(fèi)，Cj為生產(chǎn)成0(Xj0)本。設(shè)0-1變量yj ，令 yj1采用第j種設(shè)備生產(chǎn)，即Xj 0時(shí)不采用第j種設(shè)備生產(chǎn)，即Xj 0時(shí)1,2,30目標(biāo)函數(shù)為mi nz (100yi 10xJ (

12、300y2 2x2)(200y3 5x3)Xj Myj 0 j 1,2,3為 x2 x32000為 600s.t.x2800x31200x1,x2,x3 0,且均為整數(shù) yj1 或0, j 1,2,3解之得最優(yōu)解為X (0,800,1200)T,Y (0,1,1)T即用設(shè)備B和C生產(chǎn)，分別生產(chǎn) 800件和 1200件09、某物流企業(yè)要從以下10個(gè)可供選擇的地點(diǎn)中確定5個(gè)轉(zhuǎn)運(yùn)中心，使總的物流費(fèi) 用最小。假設(shè)10個(gè)地點(diǎn)位的代號(hào)為3,川心0，相應(yīng)的鉆探費(fèi)用為g,|,g。，并且井 位選擇上要滿(mǎn)足以下限制條件： 選擇3和S7，或選擇S9 ； 選擇了 S3或S4就不能選S5，反之亦然； 在S5,Sb,S7

13、, S3中最多只能選兩個(gè)。試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型。解令xi1，當(dāng)Si被選用,0,當(dāng)Sj沒(méi)被選用i 1,2,1010maxzi 110i 1Xi5X1X91于是問(wèn)題可列成：X2X91X4X51X3X51X5X6X7X82Xj0，當(dāng)Si未選用1,當(dāng)Si選用10、用分枝定界法求解下面的整數(shù)規(guī)劃問(wèn)題maxz 3捲 2x22x1 x29s.t2x1 3x2 14為,x20且取整解 解該問(wèn)題(IP)的松弛問(wèn)題(LP)得最優(yōu)解X。 (3.25,2.5)，目標(biāo)函 數(shù)值為zo 14.75，xo不滿(mǎn)足取整條件。分枝與定界定界：zo 14.5是原問(wèn)題最優(yōu)目標(biāo)函數(shù)值 z*的一個(gè)上界，記為z 14.75 ； 顯然

14、x (0,0)是原問(wèn)題的一個(gè)可行解，相應(yīng)目標(biāo)函數(shù)值z(mì)=0是z*的一個(gè)下界，記 作 z=0，即有 0 z*14.75。分枝：在x0中任取一非整分量，比方取x22.5作為分枝變量。在LP中分別增加約束X2 2和x 2 3，得兩個(gè)分枝LP1和LP2。求各分枝最優(yōu)解，填入分枝圖， 如以下列圖所示。LP1maxz 3x1 2x22x1 x292x1 3x214s.t.x22x1 ,x20maxz 3為2x22為 x292為 3x214LP2s.t.2X2 3x1, x20可求得LP1的最優(yōu)解為(3.5,2), Z=14.5LP2的最優(yōu)解為(2.5,3),z=13.5,應(yīng)選取邊界值較大的子問(wèn)題由于兩個(gè)子問(wèn)

15、題的最優(yōu)解仍非原問(wèn)題的可行解LP1繼續(xù)分枝.在LP1上分別加上約束X1 4得LP11和LP122x1 x292x1 x292x1 3x2142x1 3x214LP11s.t. x22LP12s.t. x22x13x14x1, x20x1 ,x20可求得LPii最優(yōu)解為3,2, z=13; LP12的最優(yōu)解為4,1, z=14。因此保留可行解中較大的z=14。求解過(guò)程如下列圖：11、用匈牙利解法求解下面的指派問(wèn)題791012131216171516141511121516解 每行減掉其所在行最小值，然后每列再減其所在列最小值，得新的矩陣0234104412 0 00144此時(shí)，C中各行各列都已出

16、現(xiàn)零元素。為了確定C中的獨(dú)立零元素，對(duì)C中零元素加圈，即0234c 1 4 41 2 0 0.0144由于只有3個(gè)獨(dú)立零元素，少于系數(shù)矩陣階數(shù)n=5,不能進(jìn)行指派，為了增加 獨(dú)立零元素的個(gè)數(shù)，需要對(duì)矩陣作進(jìn)一步的變換，變換步驟如下：用最少的直線(xiàn)覆蓋所有的“ 0得3 44 40044 從矩陣未被直線(xiàn)覆蓋的數(shù)據(jù)中找出一個(gè)最小的 k并且減去k，矩陣中k=3 直線(xiàn)相交處的元素加上k，被直線(xiàn)覆蓋沒(méi)有相交的元素不變，得到以下矩 陣0 2 0 110 11c450 00 111此時(shí)，有四個(gè)獨(dú)立零元素，獨(dú)立零元素的個(gè)數(shù)與效率矩陣的階數(shù)相同， 那么該 指派問(wèn)題的最優(yōu)解為0 0 100 10 0x0 0 0 11

17、0 0 012、某公司運(yùn)輸車(chē)隊(duì)完成各項(xiàng)運(yùn)輸任務(wù)的效率矩陣如下，解效率矩陣最小化指派問(wèn)題。101149711142569121311107每行減掉其所在行最小值，然后每列再減其所在列最小值，得新的矩陣用最少的直線(xiàn)覆蓋所有的65066803012435070065066803012-43 0這里直線(xiàn)數(shù)為3 等于4時(shí)停止計(jì)算，要進(jìn)行下一輪計(jì)算。從矩陣未被直線(xiàn)覆蓋的數(shù)據(jù)中找出一個(gè)最小的 k并且減去k，矩陣中k=3。直線(xiàn)相交處的元素加上k，被直線(xiàn)覆蓋沒(méi)有相交的元素不變，得到以下矩陣33 ()553 1200)77103)3J0c此時(shí)得到指派問(wèn)題的最優(yōu)解001000011000001013、試述運(yùn)輸問(wèn)題數(shù)

18、學(xué)模型的特征，為什么模型的m+n個(gè)約束中最多只有m+n -1個(gè)是獨(dú)立的？nm nm答 如果將全部發(fā)量約束Xjj ai相加，就得到Xjjai ;將全部收mn mnmn量約束 Xjj bj相加，就得到Xjbj ,由于收發(fā)平衡，有 aibj ,i 1j 1 i 1j 1i 1j 1所以模型4-1 中m n個(gè)等式約束不是相互獨(dú)立的?？梢宰C明，在這m n個(gè)等式約束中任取m n 1個(gè)，貝U它們是相互獨(dú)立的，即不存在多余的約束條件。在m n個(gè)等式約束中刪除任何一個(gè)，運(yùn)輸問(wèn)題的可行域不變。所以，運(yùn)輸問(wèn)題 的基解僅有m n 1個(gè)基變量。14、如何把一個(gè)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題含產(chǎn)大于銷(xiāo)和銷(xiāo)大于產(chǎn)轉(zhuǎn)化為產(chǎn)銷(xiāo)平 衡的運(yùn)

19、輸問(wèn)題？答對(duì)于總產(chǎn)量不等于總需求量的運(yùn)輸問(wèn)題，不能直接采用表上作業(yè)法求最 優(yōu)調(diào)運(yùn)方案。而是將產(chǎn)銷(xiāo)不平衡問(wèn)題轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題，然后再采用表上 作業(yè)法進(jìn)行求解。產(chǎn)大于銷(xiāo)問(wèn)題：對(duì)于此類(lèi)問(wèn)題，設(shè)有一個(gè)假想銷(xiāo)地Bn 1，其銷(xiāo)量為mnbn 1aibji 1j 1但實(shí)際上沒(méi)有運(yùn)輸，故其單位運(yùn)價(jià)為 0,這樣就轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題，但沒(méi) 有破壞原問(wèn)題的性質(zhì)，表4-44為產(chǎn)銷(xiāo)平衡表。表4-44 產(chǎn)銷(xiāo)平衡表銷(xiāo)產(chǎn)地B1B2BnBn+1產(chǎn)量A1C11C12C1n0a1A2C21C22C2n0a2-IBHEia-AmCm1Cm2+ Cmn0am銷(xiāo)量b1b2+ 4-1bnbn+1銷(xiāo)大于產(chǎn)的問(wèn)題：對(duì)于此類(lèi)問(wèn)題，設(shè)有一個(gè)假

20、想產(chǎn)地 Am1，其產(chǎn)量為am 1bjaij 1i 1但實(shí)際上沒(méi)有運(yùn)輸，故其單位運(yùn)價(jià)為無(wú)窮大M，這樣就轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題，但沒(méi)有破壞原問(wèn)題的性質(zhì)，表 4-45為產(chǎn)銷(xiāo)平衡表。表4-45 產(chǎn)銷(xiāo)平衡表銷(xiāo)產(chǎn)地B1B2+ + *Bn產(chǎn)量A1C11C12C1na1AC21C22C2na2HFBBBBeAmCm1Cm2+ + CmnamAm+1MM+ + Mam+1銷(xiāo)量b1b2+ + bn15、運(yùn)輸問(wèn)題的供需關(guān)系表與單位運(yùn)價(jià)表如表15所示，試用表上作業(yè)法求最優(yōu)解。表15運(yùn)輸表產(chǎn)地、甲乙丙丁產(chǎn)量132765027523603254525銷(xiāo)量60402015解 用最小元素法求解的整個(gè)求解過(guò)程如運(yùn)算表 1、運(yùn)算表2

21、所示:運(yùn)算表1Vj32-2-1aiUiBiB2B3B40Ai3276501040XX00974A275236025X20150-100-1A325452525XXX0477bj60402015運(yùn)算表2Vj32-2-1aiUiB1B2B3B40X00973A2752360X2520151000-1A325452525XXX0477bj60402015由上表知該運(yùn)輸問(wèn)題的最優(yōu)解為:* TX BX11 , X12 , X22 , X23 , X24 , X31* TX NX13 , X14 , X21 , X32 , X33 , X3435,15,25,20,15,25 T

22、T0,Q0,0,0,0最優(yōu)值為:z*35 3 15 225 520 215 325 2395。16、某運(yùn)輸問(wèn)題的一個(gè)產(chǎn)銷(xiāo)量及調(diào)運(yùn)方案見(jiàn)表16-1,單位運(yùn)價(jià)表見(jiàn)表16-2判斷所給出的調(diào)運(yùn)方案是否為最優(yōu)？并說(shuō)明理由。U10,U21,U31,U40, V12,V21,V3 1,V41,V52, V60求得檢驗(yàn)數(shù)ijCij(ui Vj)11C11(U1V1)2(11)0，同理可知132,142,165,242, 263,323,332,351,412,421431,46表16-1 調(diào)運(yùn)方案銷(xiāo) 產(chǎn)地、B1B2B3B4B5B6產(chǎn)量A1401050A251020540A325241160A4161531銷(xiāo)量

23、305020403011表16-2 單位運(yùn)價(jià)表、銷(xiāo)地 產(chǎn)地、B1B2B3B4B5B6A1213325A2322434A3354241A4422122解 調(diào)運(yùn)方案是最優(yōu)，因?yàn)槿绻?上表是最優(yōu)解，可以求得位勢(shì)數(shù)為st min ij 0 i m,0 j n0所以上表為最優(yōu)解。17、某糖廠每月最多生產(chǎn)糖270噸，先運(yùn)至三個(gè)倉(cāng)庫(kù)，然后再分別供應(yīng)五個(gè)地區(qū)需要。各倉(cāng)庫(kù)容量分別為 50噸，100噸，150噸，各地區(qū)的需要量分別為 25噸，105噸，60噸，30噸，70噸。從糖廠經(jīng)由各倉(cāng)庫(kù)然后供應(yīng)各地區(qū)的 運(yùn)費(fèi)和儲(chǔ)存費(fèi)如表17所示。試確定一個(gè)總運(yùn)費(fèi)最低的調(diào)運(yùn)方案。表17運(yùn)費(fèi)及存儲(chǔ)費(fèi)用表B1B2B3B4B5A11

24、015202040A22040153030A33035405525解 倉(cāng)庫(kù)總?cè)萘繛?00噸，各地區(qū)需要量總計(jì)270噸。倉(cāng)庫(kù)有30噸裝不滿(mǎn)，各地區(qū)有20噸不能滿(mǎn)足。可虛設(shè)一庫(kù)容 20噸的倉(cāng)庫(kù)A4來(lái)滿(mǎn)足需要，相應(yīng)虛設(shè)一地區(qū)B6來(lái)虛購(gòu)倉(cāng)庫(kù)中未裝進(jìn)的30噸糖。由此列出產(chǎn)銷(xiāo)平衡表與單位運(yùn)價(jià)表如下：B1B2B3B4B5B6aiA11015202040050A220401530300100A330354055250150A400000M20bj2510560307030按上表用表上作業(yè)法求之得最優(yōu)調(diào)運(yùn)方案為X110, X1250, X130,為40,X150,X2125, X220, X2360, X241

25、5, X250,x；10, x；2*50, X330,x；40, x；570最優(yōu)解為z*50 152520 6015 1530 503570 256100 018、公司有資金8萬(wàn)元，投資A、B、C三個(gè)工程，一個(gè)單位投資為 2萬(wàn)元。每 個(gè)工程的投資效益率與投入該工程的資金有關(guān)。三個(gè)工程 A、B、C的投資效益萬(wàn)元和投入資金萬(wàn)元的關(guān)系見(jiàn)下表。求對(duì)三個(gè)工程的最優(yōu)投資分配，使 總投資效益最大。工程投入資金/萬(wàn)元ABC28910415202863035358384043解 設(shè)Xk為第k個(gè)工程的投資，該問(wèn)題的靜態(tài)規(guī)劃模型為max ZVixJ V2X2 V3X3Xi X2 X38Xj 0,2, 4, 6,8階

26、段k:每投資一個(gè)工程作為一個(gè)階段，k=1,2,3,4。k=4為虛設(shè)的階段狀態(tài)變量Sk：投資第k個(gè)工程前的資金數(shù)決策變量Xk：第k個(gè)工程的投資額決策允許集合：OW Xk Sk狀態(tài)轉(zhuǎn)移方程：Sk+l=Sk Xk階段指標(biāo)：VkSk, Xk見(jiàn)表中的數(shù)據(jù)遞推方程：fkXk max Vk Sk, Xk fkiSki終端條件：f4S4=0數(shù)學(xué)模型為fkXk maX VkSk,Xk fkiSJ,k 3,2,1S 1 Sk Xkf4%0Xk 0,2,4,6,8, k 1,2,3k=4,終端條件 f4S4=0。k=3, 0 X3W S3, S4=S3 X3狀態(tài)決策狀態(tài)轉(zhuǎn)移方程階段指標(biāo)過(guò)程指標(biāo)最優(yōu)指標(biāo)最優(yōu)決策S3X

27、3S3S4=S3 X3V3S3,X3V3S3,X3+f4S4f3S3X3*00000+0=00020200+0=0102201010+0=10*40400+0=0284221010+0=10402828+0=28*60600+0=0356241010+0=10422828+0=28603535+0=35*80800+0=0438261010+0=10442828+0=28623535+0=35804343+0=43*k=2, 0 X2 S2, S3=S2 X2S2X2S2S3V2S2,X2f3S3V2S2,X2+f3S3f2S2X2*000000+0=0002020100+10=10*1002

28、0909+0=94040280+28=28*280229109+10=194020020+0=206060350+35=35372249289+28=37*42201020+10=306035035+0=358080430+43=43484269359+35=4444202820+28=48*62351035+10=458040040+0=40k=1 , 0 X1 S1 , S2=S1 X1S1X1S1S2V1S1,X1f2S2V1S1,X1+f2S2f1 S1X1 *8080480+48=48*480268378+37=4544152815+28=4362301030+10=40803803

29、8+0=38最優(yōu)解為:S1=8, X1*=0 , S2=S1 X1=8, X2*=4 , S3=S2 X2*=4 , X3=4, S4=S3 X3= 0。投資 的最優(yōu)策略是，工程A不投資，工程B投資4萬(wàn)元，工程C投資4萬(wàn)元，最大 效益為48萬(wàn)元。19、一個(gè)工廠生產(chǎn)某種產(chǎn)品，16月份生產(chǎn)本錢(qián)和產(chǎn)品需求量的變化情況見(jiàn)表19。表19每月需求量與生產(chǎn)本錢(qián)表月份k123456需求量dk203035402545單位產(chǎn)品本錢(qián)Ck151216191816沒(méi)有生產(chǎn)準(zhǔn)備本錢(qián)，單位產(chǎn)品一個(gè)月的存儲(chǔ)費(fèi)為hk= 0.6元，月底交貨。分別求以下兩種情形6個(gè)月總本錢(qián)最小的生產(chǎn)方案。 1月初與6月底存儲(chǔ)量為零，不允許缺貨，倉(cāng)

30、庫(kù)容量為 S=50件，生產(chǎn)能 力無(wú)限制； 其他條件不變，1月初存量為10。解動(dòng)態(tài)規(guī)劃求解過(guò)程如下。階段k：月份，k=1, 2,，7狀態(tài)變量Sk：第k個(gè)月初的庫(kù)存量決策變量Xk：第k個(gè)月的生產(chǎn)量狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk+Xk dk決策允許集合：Dk(sk) xk xk 0,0 sk xk dk 50階段指標(biāo):Vk(Sk,Xk)CkXkhkSkCkXk 0.6 Sk終端條件：f7(S7)=0, S7=0遞推方程：fk(Xk)nDin( )vk(Sk,Xk) fki(Ski)Xk Dk(Sk)min Vk (Sk , Xk)fk 1 (Sk Xk dk)Xk Dk(sk)當(dāng)k=6時(shí)，因?yàn)镾7=0

31、，有S7Ss X6 d6 Ss X6 45 0,X645 S6，S6 45f6(S6)min16x6X645 S6=min 16 x6X645 S615.4 S67200.6 S6 f 7 ( S7 ) 0.6 S6 *X645 S670 S565 s4當(dāng) k=5 時(shí)，由0&45, 0 S5 X5 d5 S5 X52545,得 25 S X5由于S525矛盾。因此有f ( )18令1930 0 S 40兒 40 s 并且0S525x525 S4(S4)16.$1866 40 勻 50x4 0 并且025xs25 k=3，當(dāng) 0 s4 40 時(shí)，0 S3+X3 35 40f3(S3)D36)X3

32、 max0,35 S3 X3 75 Ssmin 16x3 0.6s3f4()X3 D3 ( 3)16x3 0.6s3 18.4s4 1930min2.4X3 17.8S3 2574X3 D3(S3)75 S315.4S3 2394取上界：X3當(dāng) 40 S4 50 時(shí),40 S3+ X3 35 50D3(S3)x3 75 s x385 S3f3(s3)min 16x30.6s3X3 D3(3)f4(S4)16.8S4 1866minX3 D3( S3)0.8x3 16.2S3 245415.4S32386取上界:min 16x3 0.6s3X D3(Sb)*X385 S3當(dāng) k=2 時(shí)，由40

33、S450,0 S350, 0 S2 x2 30 50,有30 s2 x280 S2X2的決策允許集合為D2(S2)x2 max0,30s2 x2 80 S2f2(S2)m min12x20.6S2f3(S3)30 S2 X2 65 S2min12x20.6s215.4s3238630 S2 X2 65 S2min3.4x2 14.8q 284830 s2 x2 65 s211.4S2 2576取上界：x2 80 S2當(dāng)k=1時(shí)，由S250,0$ 捲 2050, 20$ X 70 S|只要期初存量s1 40,X4 = 0,S5=50 0 40= 10v 25,X5 = 25 s5= 15,ss=

34、10+ 15 25= 0,X6 = 45?？偙惧X(qián)為2876。16月份生產(chǎn)、存儲(chǔ)詳細(xì)方案表見(jiàn)下表所示月份(k)123456合計(jì)需求量(dk)203035402545195單位產(chǎn)品本錢(qián)(Ck)11216191816單位存儲(chǔ)費(fèi)hk0.60.60.60.60.60.6產(chǎn)量Xk20803501545195期初存量Sk005050100110生產(chǎn)本錢(qián)Ck(xk)30096056002707202810存儲(chǔ)本錢(qián)Hk(sk)0030306066合計(jì)2876 期初存儲(chǔ)量S1 = 10,與前面計(jì)算類(lèi)似，得到 X1 = 10, X2= 80, X3= 35, X4 =0, X5 = 15, X6 = 45。20、某

35、廠新買(mǎi)了一間25平米的房間做生產(chǎn)車(chē)間，有4種機(jī)床可以放置于此安排 生產(chǎn)，各種機(jī)床各臺(tái)的收益情況估計(jì)表 20所示。為了獲得最大收益，各種機(jī)床 各放置幾臺(tái)為最好？表20幾床占地面積與收益機(jī)床母臺(tái)占地/ m每臺(tái)收益/(兀天1)第一臺(tái)第二臺(tái)第三臺(tái)第四臺(tái)A410741B59988C6111098D38642解 為了獲得最大收益應(yīng)放置 A機(jī)床2臺(tái)，B機(jī)床1臺(tái)，C機(jī)床1臺(tái)，D機(jī) 床2臺(tái)。此時(shí)，能獲得最大收益51。21、求圖21中從V1到v的最短路圖21解 從Vi到V8的最短路徑是V1 f V3 f V6 f V8，目標(biāo)值為14o22、用Floyd算法求圖22中所有點(diǎn)之間的最短路圖22解 (1)第一步：確定權(quán)

36、矩陣D(0)。0 101615063012525061205D(0)0第二步：計(jì)算兩步最短距離矩陣對(duì)得矩陣 DL(j1)min 5 ,內(nèi)，例如V經(jīng)過(guò)兩步(最多一個(gè)中間點(diǎn))到達(dá) v4的最短距r離為l2； min I：I(0) I(0)I(0)1 44，1 21114I (0) ，1 23I (0)I 34I (0) ，I 22I (0)I 24min( 3,3)301016132127063915012510所以D0611050同理可得出三步最短距離矩陣D。0 1016131924063914D(1)0125100611050此時(shí)得到最有矩陣，即兩點(diǎn)之間的距離都為最短。23、求從Vi到v的最大流

37、。解；給定初始可行流，見(jiàn)圖16-(61圖1增廣鏈卩二(1,2),(3,2) , (3,4) , (4,7) ,卩 +=(1,2),(3,4) , (4,7),卩=(3 , 2)，調(diào)整量為增廣鏈上點(diǎn)標(biāo)號(hào)的最小值9 = min, 2, 3, 3, 7 = 2 調(diào)整后的可行流為以下列圖圖3oo4圖4第二輪標(biāo)號(hào):,調(diào)整量為增廣鏈卩=卩+= (1,3) , (3,4) , (4,7)0 = min X, 4, 1, 5 = 1調(diào)整后得到可行流:圖5第三輪標(biāo)號(hào):增廣鏈卩=卩+= (1,3) , (3,6) , (6,4) , (4,7)，調(diào)整量為9 = min, 3, 1, 2, 4 = 1調(diào)整后得到可行

38、流圖7圖8v7得不到標(biāo)號(hào)，不存在v1到V7的增廣鏈，圖6-22所示的可行流是最大流,最大流量為v= f12+f13= 8+12=2024、將3個(gè)天然氣田Ai、A2、A3的天然氣輸送到2個(gè)地區(qū)Ci、C2，中途有2個(gè)加壓站Bi、B2,天然氣管線(xiàn)如圖24所示。輸氣管道單位時(shí)間的最大通過(guò)量q及單位流量的費(fèi)用dj標(biāo)在弧上cj, dj。求最小費(fèi)用最大流。圖24解虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)得最小費(fèi)用最大流如以下列圖，最大流量等于 27,總費(fèi)用等于35125、求圖25中的最小生成樹(shù)。解對(duì)上圖各結(jié)點(diǎn)表字母得圖25可以得出最小生成樹(shù)為:它的權(quán)為3426、請(qǐng)指出圖26(a) (b) (c) (d)所示網(wǎng)絡(luò)圖的錯(cuò)誤，假設(shè)

39、能改正，試給予改正(a)g(b)(c)2(d)圖26解 (a)工序d、e具有完全相同的箭尾結(jié)點(diǎn)與箭頭結(jié)點(diǎn)。應(yīng)在結(jié)點(diǎn)和 之間增加一個(gè)結(jié)點(diǎn)和一個(gè)虛工序。(b) 圖中有和兩個(gè)終端結(jié)點(diǎn)，應(yīng)去掉一個(gè)，將工序f，g歸結(jié)到一個(gè)結(jié) 點(diǎn)。此外，虛工序一可省略。(c) 圖中有兩個(gè)始點(diǎn)和兩個(gè)終點(diǎn)，均可合并。(d) 工序a，d，e形成循環(huán)，不允許。27、表27所列資料:表27工序時(shí)間表工序緊前工序工序時(shí)間/d工序緊前工序工序時(shí)間/da一3fc8ba4gc4ca5hd,e2db,c7ig3eb,c7jh,i2要求： 繪制工程方案圖； 計(jì)算各結(jié)點(diǎn)的最早時(shí)間和最遲時(shí)間； 計(jì)算各工序的最早開(kāi)工、最早完工、最遲開(kāi)工及最遲完工時(shí)間; 計(jì)算各工序的時(shí)差； 確定關(guān)鍵路線(xiàn)。解工程方案圖如下: 結(jié)點(diǎn)1的最早時(shí)間是0,最晚時(shí)間是0;結(jié)點(diǎn)2的最早時(shí)間是3,最晚時(shí) 間是3;結(jié)點(diǎn)3的最早時(shí)間是7,最晚時(shí)間是8;結(jié)點(diǎn)4的最早時(shí)間是8,最晚時(shí) 間是8;結(jié)點(diǎn)5的最早時(shí)間是12,最晚時(shí)間是14；結(jié)點(diǎn)6的最早時(shí)間是15,最 晚時(shí)間是17；結(jié)點(diǎn)7的最早時(shí)間是15,最晚時(shí)間是15;結(jié)點(diǎn)8的最早時(shí)間是15, 最晚時(shí)間是15;結(jié)點(diǎn)9