管理運(yùn)籌學(xué)考試題型整理

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)線性規(guī)劃問題建模(除排隊(duì)論，都可以線性規(guī)劃)關(guān)鍵：決策變量（維度），目標(biāo)函數(shù)、約束條件； a, b, c 例：例：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，這些產(chǎn)品分別需要在A、B、C、D四種不同的設(shè)備上加工。按工藝規(guī)定：產(chǎn)品和在個(gè)設(shè)備上所需要的加工時(shí)數(shù)于下表中。已知各設(shè)備在計(jì)劃期內(nèi)的有效臺(tái)時(shí)數(shù)分別是12、8、16和12。該工廠每生產(chǎn)一件產(chǎn)品可得利潤2圓，每生產(chǎn)一件產(chǎn)品可得利潤3圓，問：應(yīng)如何安排生產(chǎn)，可獲得最大利潤。 設(shè)備產(chǎn)品ABCD21423214解 設(shè)生產(chǎn)產(chǎn)品和分別為

2、和件，則由條件可得關(guān)系 練習(xí)：轉(zhuǎn)化為標(biāo)準(zhǔn)型 關(guān)鍵：決策變量0，目標(biāo)函數(shù)Max、約束條件= （b0）圖解法（兩維）關(guān)鍵：縱軸X2系數(shù)的正負(fù)，目標(biāo)求大求小Max(Z)Min(Z)X20X20 例 用圖解法求解線性規(guī)劃問題 極大化 Max (? min或 -3x2) 解：最優(yōu)解簡單計(jì)算(包括大M法,兩階段法)關(guān)鍵： 標(biāo)準(zhǔn)型轉(zhuǎn)化，步驟 （換基，入基， “Xb=B”） 例 用單純形法求解線性規(guī)劃 極大化 解 引入松弛變量，得到原規(guī)劃的標(biāo)準(zhǔn)型 極大化 單純形表為 所以，最優(yōu)解為最優(yōu)解值為21.利用大M法或兩階段法求解下列問題復(fù)雜計(jì)算關(guān)鍵：目標(biāo)函數(shù)和檢驗(yàn)數(shù) (Z1新 和 Z0 舊的對比)Max(Z)Min(

3、Z)Cj-Zj Z1-Z0*Zj-Cj Z0-Z1解類型的判斷關(guān)鍵：填表題關(guān)鍵：（若干行變換）左乘B-1， 基變量對應(yīng)的I，2-4 已知某求極大值線性規(guī)劃問題用單純形法求解時(shí)的初始單純形表及最終單純形表如表所示，求表中各括弧內(nèi)未知數(shù)的值。c j322000CB基bx1x2x3x4x5x60 x4（b）1111000 x515(a)120100 x6202(c)1001cjz j3220000 x45/400（d）( l )1/41/43x125/410（e）03/4（i）2x25/201（f）0（h）1/2c jz j0（k）（g）0-5/4（j）求解I,kI=1K=0, , , 即得出： 1

4、5*h+20/2=5/2 h=-1/2 或（另一種方法：0-3*3/4 -2*h=-5/4 h= -1/2）b-15/4-20/4=5/4 b=40/4=1015*3/4+20*i=25/4 i= -1/4于是：，之后： 1-1/4*a-1/4*2=0 a=2 1-1/4-1/4*c=0 c=3得出：于是得出：g=2-3*5/4-2*(-1/2)=-3/45.已知下表為求解某線性規(guī)劃問題的最終單純形表，表中x4和x5為松弛變量，問題的約束為形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040- 4-2（1）寫出原線性規(guī)劃問題對偶問題寫出對偶問

5、題關(guān)鍵：口訣 例 求下面問題的對偶規(guī)劃極大化 Max 無非負(fù)限制。 解 極小化 Min 對偶單純型法關(guān)鍵：與傳統(tǒng)互置（翻） 利用對偶性質(zhì)廣泛：如(1) 對稱性 (2)弱對偶性CXYb; (3) 無界性 (4)可行解相等是最優(yōu)解; (5) 對偶定理 都有最優(yōu)解；且目標(biāo)函數(shù)值相等; (6) 兼容性，松弛變量-變量，剩余變量-原變量；(7)互補(bǔ)松弛性. （8）對偶變量的經(jīng)濟(jì)含義1）.已知下表為求解某線性規(guī)劃問題的最終單純形表，表中x4和x5為松弛變量，問題的約束為形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040- 4-2（1）寫出原線性規(guī)劃問題

6、（2）寫出原問題的對偶問題。（3）直接由表寫出對偶問題的最優(yōu)解。2、已知線性規(guī)劃問題（20分） 其最優(yōu)解為1求k的值；2求出對偶問題的最優(yōu)解解：寫出原問題的對偶問題得 由互補(bǔ)松弛定理：得 得 聯(lián)立得 而代入 則 綜上，對偶問題最優(yōu)解為敏感性分析除了單純性表，運(yùn)輸問題等許多問題都可以敏感性分析關(guān)鍵：找到B-1，“左乘”b變動(dòng)C變動(dòng)A變動(dòng)出現(xiàn)新系數(shù)，最優(yōu)解變化最優(yōu)不變的區(qū)間范圍C，A同時(shí)變化B, C, A同時(shí)出現(xiàn)變化引入一行新約束（）B變動(dòng)； （2）若b2 變?yōu)?0，求新的最優(yōu)解 15 b2 25 時(shí)，最優(yōu)基不變。變化后基變量的 取值為: 兩種求解方法，1）直接相乘；2）B+B C變動(dòng)；注：也可以

7、直接讓2+= K (c1)a變動(dòng)(有時(shí)C同時(shí)變動(dòng))；1）增加一個(gè)新產(chǎn)品2）技術(shù)變革后面利用對偶單純型法，大M法，兩階段法B, C, A同時(shí)出現(xiàn)變化引入一行新約束（）運(yùn)輸問題運(yùn)輸問題建模；關(guān)鍵：明確產(chǎn)地（輸出）和銷地（輸入），變量、約束和目標(biāo) 運(yùn)輸問題：產(chǎn)地、銷地、產(chǎn)量、銷量 引例：有A1，A2，A3三座鐵礦，每天要把生產(chǎn)的鐵礦石運(yùn)往B1，B2，B3，B4四個(gè)煉鐵廠。各礦的產(chǎn)量、各廠的銷量以及各廠礦間的運(yùn)價(jià)如下表所示。問應(yīng)如何組織調(diào)運(yùn)才能使運(yùn)費(fèi)最少？B1 B2 B3 B4產(chǎn)量A1A2A36 3 2 57 5 8 43 2 9 7523銷量2 3 1 4供求“平衡”下的表上作業(yè)法；關(guān)鍵：明確計(jì)算方

8、法，初始方案最優(yōu)方案（基變量，非基變量，檢驗(yàn)數(shù)）（1.西北角法2.最小元素法3. Vogel法1.閉回路法2.位勢法） 例 求下面運(yùn)輸問題的最小值解：12341311310721923437410593656重新計(jì)算位勢及影響系數(shù)，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此時(shí)，故當(dāng)前解為最優(yōu)解。最優(yōu)解值為：供求“不平衡”下的表上作業(yè)法；關(guān)鍵：使之平衡，增加或 敏感性分析；關(guān)鍵：設(shè)變量，求檢驗(yàn)數(shù) 3154134另外，有求范圍的，我們以前做過最大化問題（如收益，利潤）；關(guān)鍵：最大數(shù)一各個(gè)運(yùn)價(jià) 轉(zhuǎn)運(yùn)下的

9、運(yùn)輸問題；關(guān)鍵：加上總運(yùn)轉(zhuǎn)量 隨便運(yùn)輸整數(shù)規(guī)劃分支定界法；關(guān)鍵：上界，下界，范圍縮小，剪枝 運(yùn)輸問題：產(chǎn)地、銷地、產(chǎn)量、銷量割平面法；關(guān)鍵：等號(hào)一邊為整數(shù)，另一邊為“真”分?jǐn)?shù)；可用原變量X表示; 真分?jǐn)?shù)大的收斂性好0-1規(guī)劃建模；關(guān)鍵：基本形式y(tǒng)1+y2=1, b*y1，M*y （相互排斥的計(jì)劃、約束條件，固定費(fèi)用）0-1規(guī)劃隱枚舉法；關(guān)鍵：（Max）從大到小，設(shè)定門檻(后設(shè))，01互換并剪枝 0-1規(guī)劃分支定界法；關(guān)鍵：（Max）從大到小， 01互換并剪枝 , 非可行解另外：指派建模；關(guān)鍵：目標(biāo)，約束，變量(二維)，近似運(yùn)輸運(yùn)輸問題：產(chǎn)地、銷地、產(chǎn)量、銷量指派基本求解；關(guān)鍵：橫列最少?。╩個(gè)

10、），口訣（P2網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)性質(zhì)；關(guān)鍵：點(diǎn)線的有關(guān)系 , 奇點(diǎn)、偶點(diǎn)等1.一個(gè)硬幣正面為幣值，反面為國徽圖案。將這個(gè)硬幣隨機(jī)擲10次， 如果用樹圖表示所有可能出現(xiàn)的結(jié)果，試問這個(gè)樹圖有多少個(gè)節(jié)點(diǎn)，多少條邊。. . . . 正反解：有個(gè)節(jié)點(diǎn)，條邊3.有八種化學(xué)藥品A，B，C，D，P，R，S，T要放進(jìn)貯藏室保管。出于安全原因，下列各組藥品不能貯在同一室內(nèi)：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，D-C，R-S，R-B，P-D，S-C，S-D，問貯藏這八種藥品至少需要多少間貯藏室。解：用八個(gè)點(diǎn)分別代表八種藥品，哪兩種藥品不能貯于同一室 內(nèi)，就在代表它們的兩個(gè)點(diǎn)間連一條邊。其中S

11、，P，R兩兩相鄰，必須占用3間貯藏室。與S不相鄰，彼此也不相鄰的有A，B點(diǎn)，可與S貯于一室。類似可推出此題最少需要3間貯藏室。(不與黑線重合)ABCDPRST最小樹；關(guān)鍵：破圈法（去大），避圈法（加?。?，頂點(diǎn)擴(kuò)充法（連線的最短邊在最小支撐樹內(nèi)）大連銀行計(jì)劃采用專用的加密網(wǎng)絡(luò)將總部的計(jì)算機(jī)與市內(nèi)五個(gè)區(qū)的分支銀行的計(jì)算機(jī)互聯(lián)起來（不一定是每一個(gè)支行都與總部直接相連）。這種專用的加密網(wǎng)絡(luò)的鋪設(shè)費(fèi)用是連接距離的100倍。表8-1給出了總部和五個(gè)分支機(jī)構(gòu)之間的連接距離。銀行的管理者希望能夠在使得所有分支結(jié)構(gòu)和總部都能直接或間接互聯(lián)的前提下最小化專用網(wǎng)絡(luò)的鋪設(shè)費(fèi)用，請你給出最優(yōu)的鋪設(shè)方案。 距離（km）總

12、部分支1分支2分支3分支4分支5總部1.90.711.52.71.6分支11.91.01.12.20.5分支20.71.01.41.22.2分支311.51.11.41.80.8分支42.72.21.21.83.1分支51.60.52.20.83.1最短路Dijkstra求解關(guān)鍵：累積值最小，逐一標(biāo)號(hào)（Dijkstra）五、求V1到各點(diǎn)的最短路及最短路徑。（20分） 0* 11 9* 10 11 10* 20 11* 21 20 21 21* 21* 28 25* 11 ： 9 ： 10 ： 21 ： 20 ： 25 ： 最短路Floyed求解關(guān)鍵：算子(+，) ，負(fù)權(quán)，理解，較小計(jì)算最短路建

13、模應(yīng)用關(guān)鍵：累積值最小，逐一標(biāo)號(hào)單源和單匯最大流建模；關(guān)鍵：源匯=f，中間點(diǎn)平衡單源和單匯最大流求解；關(guān)鍵：增廣鏈，非飽和流+，非零流-（調(diào)整-非飽和、非零，原則：最大，近源匯），最大流=最小割 多源和多匯最大流求解；關(guān)鍵：增加虛擬源點(diǎn)和匯點(diǎn) 最小費(fèi)用最大流；關(guān)鍵：對偶網(wǎng)絡(luò)（可調(diào)整的單位成本，F(xiàn)loyd算法），最短路徑確定原網(wǎng)絡(luò)路線 決策問題不確定型決策；關(guān)鍵：樂觀, 悲觀, 折衷和最小機(jī)會(huì)損失3）3） S1和S2皆可決策樹問題；關(guān)鍵：從后向前，方框去枝（方策點(diǎn)），圓圈求均（不同狀態(tài) ）某工廠，有六臺(tái)自動(dòng)車床同時(shí)生產(chǎn)一種產(chǎn)品，這種產(chǎn)品的銷售量一直在增加，工廠所面臨的問題，是再裝一臺(tái)自動(dòng)車床，還是讓職工加班，通過對市場的調(diào)查發(fā)現(xiàn)，這種產(chǎn)品在下一年銷售量增加的概率是0.656，通過計(jì)算，得到下一年兩個(gè)方案在不同銷售量情況下的純利潤如下表所示，那么，在下一年內(nèi)是加班好，還是再加一臺(tái)機(jī)床更好？請用決策樹法說明 銷售情況 收益 概率方案銷售量增加S1 銷售量增加S20.656 0.344裝一臺(tái)A1加班A2 2 3.25 2.8答案：本題的目的是想選擇一個(gè)方案，使工廠在下一年內(nèi)獲得的純利潤最