《第五版運(yùn)籌學(xué)基礎(chǔ)與應(yīng)用大題模擬試題及答案.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《第五版運(yùn)籌學(xué)基礎(chǔ)與應(yīng)用大題模擬試題及答案.doc(14頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、計(jì)算題一1. 下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型。(10分) 滿足 2. 寫出下列問題的對(duì)偶問題 (10分)滿足 3. 用最小元素法求下列運(yùn)輸問題的一個(gè)初始基本可行解(10分) 4某公司有資金10萬元,若投資用于項(xiàng)目問應(yīng)如何分配投資數(shù)額才能使總收益最大?(15分)5 求圖中所示網(wǎng)絡(luò)中的最短路。(15分) 計(jì)算題二1、某工廠擁有A,B,C三種類型的設(shè)備,生產(chǎn)甲、乙兩種產(chǎn)品,每件產(chǎn)品在生產(chǎn)中需要使用的機(jī)時(shí)數(shù),每件產(chǎn)品可以獲得的利潤,以及三種設(shè)備可利用的機(jī)時(shí)數(shù)見下表:求:(1)線性規(guī)劃模型;(5分)(2)利用單純形法求最優(yōu)解;(15分)4. 如圖所示的單行線交通網(wǎng),每個(gè)弧旁邊的數(shù)字表示這條單行線的長度?,F(xiàn)在
2、有一個(gè)人要從出發(fā),經(jīng)過這個(gè)交通網(wǎng)到達(dá),要尋求使總路程最短的線路。(15分)5. 某項(xiàng)工程有三個(gè)設(shè)計(jì)方案。據(jù)現(xiàn)有條件,這些方案不能按期完成的概率分別為0.5,0.7,0.9,即三個(gè)方案均完不成的概率為0.50.70.9=0.315。為使這三個(gè)方案中至少完成一個(gè)的概率盡可能大,決定追加2萬元資金。當(dāng)使用追加投資后,上述方案完不成的概率見下表,問應(yīng)如何分配追加投資,才能使其中至少一個(gè)方案完成的概率為最大。(15分) 追加投資(萬元)各方案完不成的概率1230120.500.300.250.700.500.300.900.700.40計(jì)算題三1、某工廠要制作100套專用鋼架,每套鋼架需要用長為2.9m
3、 , 2.1m , 1.5m的圓鋼各一根。已知原料每根長7.4m ,現(xiàn)考慮應(yīng)如何下料,可使所用的材料最?。?產(chǎn)品甲產(chǎn)品乙設(shè)備能力/h設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤/(元/件)15002500求:(1)寫出線性規(guī)劃模型(10分) (2)將上述模型化為標(biāo)準(zhǔn)型(5分)2、求解下列線性規(guī)劃問題,并根據(jù)最優(yōu)單純形法表中的檢驗(yàn)數(shù),給出其對(duì)偶問題的最優(yōu)解。(15分) 滿足 3 斷下表中方案是否可作為運(yùn)輸問題的初始方案,為什么?(10分) 4. 用Dijkstra算法計(jì)算下列有向圖的最短路。(15分)5某集團(tuán)公司擬將6千萬資金用于改造擴(kuò)建所屬的A、B、C三個(gè)企業(yè)。每個(gè)企業(yè)的利潤增長額與所分配到
4、的投資額有關(guān),各企業(yè)在獲得不同的投資額時(shí)所能增加的利潤如下表所示。集團(tuán)公司考慮要給各企業(yè)都投資。問應(yīng)如何分配這些資金可使公司總的利潤增長額最大?(15分) 計(jì)算題答案一1、 max(-z)= 2、 寫出對(duì)偶問題maxW= 3、解: 4解:狀態(tài)變量為第k階段初擁有的可以分配給第k到底3個(gè)項(xiàng)目的資金額;決策變量為決定給第k個(gè)項(xiàng)目的資金額;狀態(tài)轉(zhuǎn)移方程為;最優(yōu)指標(biāo)函數(shù)表示第k階段初始狀態(tài)為時(shí),從第k到第3個(gè)項(xiàng)目所獲得的最大收益,即為所求的總收益。遞推方程為: 當(dāng)k=3時(shí)有 當(dāng)時(shí),取得極大值2,即: 當(dāng)k=2時(shí)有:令 用經(jīng)典解析方法求其極值點(diǎn)。由 解得: 而 所以 是極小值點(diǎn)。極大值點(diǎn)可能在0,端點(diǎn)取
5、得: , 當(dāng)時(shí),解得 當(dāng)時(shí),此時(shí),當(dāng)時(shí),此時(shí),當(dāng)k=1時(shí), 當(dāng) 時(shí), 但此時(shí) ,與矛盾,所以舍去。當(dāng)時(shí),令 由 解得: 而 所以 是極小值點(diǎn)。比較0,10兩個(gè)端點(diǎn) 時(shí), 時(shí), 所以再由狀態(tài)轉(zhuǎn)移方程順推: 因?yàn)?所以 ,因此 最優(yōu)投資方案為全部資金用于第3個(gè)項(xiàng)目,可獲得最大收益200萬元。5. 解:用Dijkstra算法的步驟如下,P()0T()(2,37)第一步:因?yàn)?,且,是T標(biāo)號(hào),則修改上個(gè)點(diǎn)的T標(biāo)號(hào)分別為: = =所有T標(biāo)號(hào)中,T()最小,令P()2第二步:是剛得到的P標(biāo)號(hào),考察,且,是T標(biāo)號(hào) =所有T標(biāo)號(hào)中,T()最小,令P()5第三步:是剛得到的P標(biāo)號(hào),考察= 所有T標(biāo)號(hào)中,T()最小
6、,令P()6第四步:是剛得到的P標(biāo)號(hào),考察= 所有T標(biāo)號(hào)中,T(),T()同時(shí)標(biāo)號(hào),令P()=P()7第五步:同各標(biāo)號(hào)點(diǎn)相鄰的未標(biāo)號(hào)只有 至此:所有的T標(biāo)號(hào)全部變?yōu)镻標(biāo)號(hào),計(jì)算結(jié)束。故至的最短路為10。計(jì)算題答案二1. 解:(1) 滿足 (2)150025000000653210032.5040210104007503001250150025000000153010-2/350152001-1/37.525002501001/3_-625001500000-2500/3-15005101/30-2/9_0500-2/311/9_25002501001/3_-7000000-5000-500最優(yōu)
7、解 最優(yōu)目標(biāo)值 = 70000元2. 解:此規(guī)劃存在可行解,其對(duì)偶規(guī)劃 滿足: 對(duì)偶規(guī)劃也存在可行解,因此原規(guī)劃存在最優(yōu)解。3、解:可以作為初始方案。理由如下: (1)滿足產(chǎn)銷平衡(2)有m+n-1個(gè)數(shù)值格(3)不存在以數(shù)值格為頂點(diǎn)的避回路4.解: 5.解:此題目等價(jià)于求使各方案均完不成的概率最小的策略。把對(duì)第k個(gè)方案追加投資看著決策過程的第k個(gè)階段,k1,2,3。-第k個(gè)階段,可給第k, k+1,3個(gè)方案追加的投資額。-對(duì)第k個(gè)方案的投資額階段指標(biāo)函數(shù),這里的是表中已知的概率值。過程指標(biāo)函數(shù)以上的k1,2,3用逆序算法求解k3時(shí), 得表: 最優(yōu)策略:1,=1, =0或0,=2, =0,至少有
8、一個(gè)方案完成的最大概率為1-0.135=0.865計(jì)算題答案三1. 解 分析:利用7.4m 長的圓鋼截成2.9m , 2.1 m ,1.5m 的圓鋼共有如下表所示的8中下料方案。方案毛胚/m方案1方案2方案3方案4方案5方案6方案7方案82.9211100002.1021032101.510130234合計(jì)7.37.16.57.46.37.26.66.0剩余料頭0.10.30.901.10.20.81.4設(shè),分別為上面8中方案下料的原材料根數(shù)。 2. 解 :引入松弛變量將模型化為標(biāo)準(zhǔn)型,經(jīng)求解后得到其最優(yōu)單純型表: 最優(yōu)單純型表基變量 25253/4 1 0 3/4 1/2 5/4 0 1 1
9、/4 1/2-25010/4 0 0 1/2 2由此表可知,原問題的最優(yōu)解,最優(yōu)值為250.表中兩個(gè)松弛變量的檢驗(yàn)數(shù)分別為1/2 , 2 ,由上面的分析可知,對(duì)偶問題的最優(yōu)解為。3.解:不能作為初始方案,因?yàn)閼?yīng)該有n+m-1=5+4-1=8有數(shù)值的格。 4.解:P()0T()(2,37)第一步:因?yàn)?,且,是T標(biāo)號(hào),則修改上個(gè)點(diǎn)的T標(biāo)號(hào)分別為: = = =所有T標(biāo)號(hào)中,T()最小,令P()2第二步:是剛得到的P標(biāo)號(hào),考察,且,是T標(biāo)號(hào) =所有T標(biāo)號(hào)中,T()最小,令P()3第三步:是剛得到的P標(biāo)號(hào),考察 所有T標(biāo)號(hào)中,T()最小,令P()4第四步:是剛得到的P標(biāo)號(hào),考察 所有T標(biāo)號(hào)中,T()最小
10、,令P()7第五步:是剛得到的P標(biāo)號(hào),考察 所有T標(biāo)號(hào)中,T()最小,令P()8第6步:是剛得到的P標(biāo)號(hào),考察 T()P()13至此:所有的T標(biāo)號(hào)全部變?yōu)镻標(biāo)號(hào),計(jì)算結(jié)束。故至的最短路為13。5. 解:第一步:構(gòu)造求對(duì)三個(gè)企業(yè)的最有投資分配,使總利潤額最大的動(dòng)態(tài)規(guī)劃模型。(1) 階段k :按A、B、C的順序,每投資一個(gè)企業(yè)作為一個(gè)階段,k1,2,3,4(2) 狀態(tài)變量:投資第k個(gè)企業(yè)前的資金數(shù)。(3) 決策變量:對(duì)第k個(gè)企業(yè)的投資。(4) 決策允許集合:。(5) 狀態(tài)轉(zhuǎn)移方程:。(6) 階段指標(biāo):見表中所示。(7) 動(dòng)態(tài)規(guī)劃基本方程: (終端條件) 第二步:解動(dòng)態(tài)規(guī)劃基本方程,求最有值。 k=
11、4, k=3, 計(jì)算結(jié)果(一)11044044121044+04722077+0731244+04932177073099+094134404144227707319909401414014k=2, , 計(jì)算結(jié)果(二)21133+477131233+71010121554941333+9121432255+71231310+41451433+1417171,3,42355+914321010+717411313+417k=1, , 計(jì)算結(jié)果(三)61522+17192242466+1420331111+1021421515+722第三步:回溯求得最優(yōu)策略最有解即最優(yōu)策略?。海?;,;,;返回原問題的解,即企業(yè)A投資4千萬元,企業(yè)B投資1千萬元,企業(yè)C投資1千萬元,最大效益為22千萬元。14