山東財(cái)經(jīng)大學(xué)管理運(yùn)籌學(xué)期末考試復(fù)習(xí)題及參考答案一、選擇題（每題2分，共20分）1.線性規(guī)劃模型中，若原問題存在可行解但無界，則其對偶問題（）。A.無可行解B.有可行解且最優(yōu)C.可能有可行解D.無法判斷2.運(yùn)輸問題中，若總供給量大于總需求量，為轉(zhuǎn)化為平衡運(yùn)輸問題，需添加（）。A.虛擬需求點(diǎn)，需求量為供給與需求之差B.虛擬供給點(diǎn)，供給量為供給與需求之差C.調(diào)整原需求點(diǎn)需求量D.調(diào)整原供給點(diǎn)供給量3.整數(shù)規(guī)劃中，若變量要求為0-1變量，則該問題屬于（）。A.純整數(shù)規(guī)劃B.混合整數(shù)規(guī)劃C.0-1整數(shù)規(guī)劃D.非線性整數(shù)規(guī)劃4.動(dòng)態(tài)規(guī)劃的核心思想是（）。A.貪心算法B.分治策略C.最優(yōu)化原理D.枚舉法5.圖論中，Dijkstra算法適用于求解（）。A.無向圖最短路徑（邊權(quán)非負(fù)）B.有向圖最短路徑（邊權(quán)任意）C.無向圖最小生成樹D.有向圖最大流6.排隊(duì)系統(tǒng)中，M/M/1模型的服務(wù)強(qiáng)度ρ=λ/μ需滿足（）。A.ρ>1B.ρ<1C.ρ=1D.無限制7.對偶問題中，若原問題某約束為等式，則對偶變量（）。A.無符號(hào)限制B.非負(fù)C.非正D.等于08.單純形法中，若檢驗(yàn)數(shù)σ_j≤0（最大化問題），則當(dāng)前基可行解（）。A.是最優(yōu)解B.需換基C.無可行解D.無界9.整數(shù)規(guī)劃分支定界法中，若松弛問題最優(yōu)解為非整數(shù)，需選擇一個(gè)變量（）。A.向上取整和向下取整分別分支B.固定為整數(shù)分支C.保持原值分支D.隨機(jī)分支10.運(yùn)輸問題中，初始可行解的個(gè)數(shù)應(yīng)為（）。A.m+n-1B.m+nC.mnD.m×n---二、判斷題（每題1分，共10分。正確打“√”，錯(cuò)誤打“×”）1.線性規(guī)劃的可行解一定是基可行解。（）2.對偶問題的對偶是原問題。（）3.運(yùn)輸問題的解中，基變量的個(gè)數(shù)等于m+n。（）4.整數(shù)規(guī)劃的最優(yōu)解一定優(yōu)于其松弛問題的最優(yōu)解。（）5.動(dòng)態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述相鄰階段狀態(tài)的關(guān)系。（）6.最小生成樹的Kruskal算法是按邊權(quán)從小到大選擇，不形成環(huán)。（）7.排隊(duì)系統(tǒng)中，系統(tǒng)利用率越高，服務(wù)質(zhì)量越好。（）8.若原問題有可行解，對偶問題必有可行解。（）9.0-1整數(shù)規(guī)劃中，每個(gè)變量只能取0或1。（）10.圖的最短路徑可能不唯一，但最短路徑長度唯一。（）---三、計(jì)算題（共70分）1.線性規(guī)劃求解（15分）用單純形法求解以下線性規(guī)劃問題：maxz=3x?+5x?s.t.x?≤42x?≤123x?+2x?≤18x?,x?≥0參考答案：（1）標(biāo)準(zhǔn)化：引入松弛變量x?,x?,x?，得到：maxz=3x?+5x?+0x?+0x?+0x?s.t.x?+x?=42x?+x?=12→x?+0.5x?=63x?+2x?+x?=18x_j≥0（j=1,2,3,4,5）（2）初始基可行解：x?=4,x?=12,x?=18，x?=x?=0，z=0。（3）計(jì)算檢驗(yàn)數(shù)：σ?=3-0=3，σ?=5-0=5（均>0，需換基）。選擇σ最大的x?為進(jìn)基變量。（4）確定出基變量：計(jì)算比值θ=min{4/0（x?無系數(shù)）,6/1=6,18/2=9}，最小θ=6，對應(yīng)x?出基。（5）迭代后的單純形表：基變量|x?|x?|x?|x?|x?|常數(shù)項(xiàng)x?|1|0|1|0|0|4x?|0|1|0|0.5|0|6x?|3|0|0|-1|1|18-2×6=6檢驗(yàn)數(shù)|3|0|0|-2.5|0|z=5×6=30（6）此時(shí)σ?=3>0，x?進(jìn)基。計(jì)算θ=min{4/1=4,6/3=2}，最小θ=2，x?出基。（7）新的單純形表：基變量|x?|x?|x?|x?|x?|常數(shù)項(xiàng)x?|0|0|1|1/3|-1/3|4-1×2=2x?|0|1|0|0.5|0|6x?|1|0|0|-1/3|1/3|2檢驗(yàn)數(shù)|0|0|0|-1.5|-1|z=3×2+5×6=36所有檢驗(yàn)數(shù)≤0，最優(yōu)解為x?=2,x?=6，z=36。2.對偶問題分析（15分）已知原線性規(guī)劃問題：minz=2x?+3x?+5x?+2x?+3x?s.t.x?+x?+2x?+x?+3x?≥42x?-x?+3x?+x?+x?≥3x_j≥0（j=1,2,3,4,5）（1）寫出對偶問題；（2）若原問題最優(yōu)解為x?=1,x?=0,x?=1,x?=0,x?=0，求對偶問題最優(yōu)解。參考答案：（1）設(shè)對偶變量為y?,y?（對應(yīng)原問題兩個(gè)約束），對偶問題為：maxw=4y?+3y?s.t.y?+2y?≤2（x?系數(shù)）y?-y?≤3（x?系數(shù)）2y?+3y?≤5（x?系數(shù)）y?+y?≤2（x?系數(shù)）3y?+y?≤3（x?系數(shù)）y?,y?≥0（2）根據(jù)互補(bǔ)松弛性：原問題最優(yōu)解中x?=1>0，故對偶問題第一個(gè)約束取等：y?+2y?=2；x?=1>0，故第三個(gè)約束取等：2y?+3y?=5；x?=x?=x?=0，對偶問題對應(yīng)約束可能非緊（≤）；原問題約束：第一個(gè)約束左邊=1+0+2×1+0+0=3<4？不，原問題約束是≥，左邊=1+0+2×1+0+0=3，但原問題約束是≥4，這里可能題目數(shù)據(jù)有誤，假設(shè)原問題最優(yōu)解滿足約束，即x?+x?+2x?+x?+3x?=1+0+2×1+0+0=3≥4不成立，說明假設(shè)錯(cuò)誤。正確數(shù)據(jù)應(yīng)為原問題最優(yōu)解滿足約束，例如x?=1,x?=1，x?=1，則左邊=1+0+2×1+0+3×1=6≥4，第二個(gè)約束=2×1-0+3×1+0+1=6≥3，此時(shí)：原問題約束1：6≥4，松弛變量s?=6-4=2>0，故對偶變量y?=0（互補(bǔ)松弛：s?>0→y?=0）；原問題約束2：6≥3，松弛變量s?=6-3=3>0，故y?=0？這顯然矛盾，說明題目數(shù)據(jù)需調(diào)整。假設(shè)正確原問題最優(yōu)解滿足約束等式，例如x?=1,x?=0,x?=1,x?=1,x?=0，左邊約束1=1+0+2×1+1+0=4（等式），約束2=2×1-0+3×1+1+0=6≥3（松弛變量=3>0），則：對偶問題中，原問題約束1等式→y?無約束（但原問題是min，對偶是max，原約束≥對應(yīng)對偶變量y?≥0），互補(bǔ)松弛：原問題x?>0→對偶約束1等式：y?+2y?=2；x?>0→對偶約束3等式：2y?+3y?=5；x?>0→對偶約束4等式：y?+y?=2。解方程組：y?+2y?=2y?+y?=2→解得y?=0,y?=2。代入第三個(gè)約束：2×2+3×0=4≤5（成立）。此時(shí)對偶問題最優(yōu)解y?=2,y?=0，w=4×2+3×0=8，與原問題z=2×1+3×0+5×1+2×1+3×0=2+5+2=9不一致，說明數(shù)據(jù)仍需修正。正確數(shù)據(jù)下，通過互補(bǔ)松弛性可解得對偶變量。3.運(yùn)輸問題求解（15分）某公司有3個(gè)工廠（A、B、C），產(chǎn)量分別為7、5、7（噸）；4個(gè)銷售點(diǎn)（甲、乙、丙、丁），需求量分別為3、3、4、9（噸）。單位運(yùn)價(jià)如下表，求總運(yùn)費(fèi)最小的運(yùn)輸方案。||甲|乙|丙|丁||-------|----|----|----|----||A|3|1|5|3||B|7|3|4|8||C|2|3|6|9|參考答案：（1）判斷是否平衡：總供給=7+5+7=19，總需求=3+3+4+9=19，平衡。（2）用最小元素法求初始解：最小運(yùn)價(jià)1（A→乙），分配A給乙3噸（乙需求3），A剩余7-3=4噸；次小運(yùn)價(jià)2（C→甲），分配C給甲3噸（甲需求3），C剩余7-3=4噸；次小運(yùn)價(jià)3（A→甲或A→丁），A→甲運(yùn)價(jià)3，甲已滿足，選A→丁運(yùn)價(jià)3，分配A給丁4噸（A剩余4），丁剩余9-4=5噸；次小運(yùn)價(jià)3（B→乙），乙已滿足；次小運(yùn)價(jià)4（B→丙），分配B給丙4噸（丙需求4），B剩余5-4=1噸；次小運(yùn)價(jià)8（B→?。峙銪給丁1噸（B剩余1），丁剩余5-1=4噸；最后C→丁運(yùn)價(jià)9，分配C給丁4噸（C剩余4），丁需求滿足。初始解表格（運(yùn)量/運(yùn)價(jià)）：||甲|乙|丙|丁|產(chǎn)量||-------|----|----|----|----|------||A|0/3|3/1|0/5|4/3|7||B|0/7|0/3|4/4|1/8|5||C|3/2|0/3|0/6|4/9|7||需求|3|3|4|9||（3）用位勢法檢驗(yàn)是否最優(yōu)：設(shè)u?=0，計(jì)算v_j：u?+v?=1（A→乙）→v?=1；u?+v?=3（A→?。鷙?=3；u?+v?=2（C→甲）→v?=2-u?；u?+v?=4（B→丙）→v?=4-u?；u?+v?=8（B→?。鷘?+3=8→u?=5；則v?=4-5=-1；u?+v?=9（C→?。鷘?+3=9→u?=6；則v?=2-6=-4；計(jì)算非基變量檢驗(yàn)數(shù)σ_ij=c_ij-(u_i+v_j)：σ_A甲=3-(0+(-4))=7>0；σ_A丙=5-(0+(-1))=6>0；σ_B甲=7-(5+(-4))=6>0；σ_B乙=3-(5+1)=-3<0（需調(diào)整）；σ_C乙=3-(6+1)=-4<0（更小，優(yōu)先調(diào)整）；（4）調(diào)整C→乙的閉回路：C→乙（進(jìn)基），找閉回路：C→乙→A→乙→A→丁→C→丁→C→乙。閉回路上的運(yùn)量最小為min(3（A→乙）,4（C→丁）)=3。調(diào)整后：A→乙運(yùn)量=3-3=0（出基），C→乙運(yùn)量=0+3=3；A→丁運(yùn)量=4+3=7（A產(chǎn)量7），C→丁運(yùn)量=4-3=1（C剩余7-3（甲）-3（乙）=1，給丁1噸）；新解表格：||甲|乙|丙|丁|產(chǎn)量||-------|----|----|----|----|------||A|0/3|0/1|0/5|7/3|7||B|0/7|0/3|4/4|1/8|5||C|3/2|3/3|0/6|1/9|7||需求|3|3|4|9||重新計(jì)算位勢，檢驗(yàn)數(shù)均≥0，最優(yōu)解為：A→丁7噸，B→丙4噸、丁1噸，C→甲3噸、乙3噸、丁1噸，總運(yùn)費(fèi)=7×3+4×4+1×8+3×2+3×3+1×9=21+16+8+6+9+9=69元。4.整數(shù)規(guī)劃求解（10分）用分支定界法求解整數(shù)規(guī)劃：maxz=3x?+2x?s.t.2x?+3x?≤142x?+x?≤9x?,x?≥0，且為整數(shù)參考答案：（1）松弛問題（無整數(shù)約束）：maxz=3x?+2x?s.t.2x?+3x?≤14；2x?+x?≤9；x?,x?≥0用圖解法得交點(diǎn)：2x?+3x?=14與2x?+x?=9聯(lián)立，解得x?=(14-9)/2=2.5，x?=(9-2.5)/2=3.25，z=3×3.25+2×2.5=9.75+5=14.75。（2）分支：選擇x?=3.25，分支為x?≤3和x?≥4。分支1：x?≤3松弛問題：2×3+3x?≤14→3x?≤8→x?≤8/3≈2.666；2×3+x?≤9→x?≤3。取x?≤2.666，最優(yōu)解x?=3,x?=8/3≈2.666，z=3×3+2×(8/3)=9+16/3≈14.333。分支2：x?≥4松弛問題：2×4+3x?≤14→3x?≤6→x?≤2；2×4+x?≤9→x?≤1。x?≤1，最優(yōu)解x?=4,x?=1，z=3×4+2×1=14（整數(shù)解，記錄z=14）。（3）回到分支1，x?=2.666非整數(shù)，分支為x?≤2和x?≥3。分支1-1：x?≤3,x?≤2約束：2x?+3×2≤14→2x?≤8→x?≤4；2x?+2≤9→x?≤3.5。x?≤3，最優(yōu)解x?=3,x?=2，z=3×3+2×2=13（整數(shù)解，z=13<14）。分支1-2：x?≤3,x?≥3約束：2x?+3×3≤14→2x?≤5→x?≤2.5；2x?+3≤9→x?≤3。x?≤2.5，最優(yōu)解x?=2.5,x?=3，z=3×2.5+2×3=7.5+6=13.5（非整數(shù)，繼續(xù)分支x?≤2和x?≥3）。分支1-2-1：x?≤2,x?≥3約束：2×2+3x?≤14→3x?≤10→x?≤10/3≈3.333；2×2+x?≤9→x?≤5。x?=3或3.333，取x?=3，x?=2，z=3×2+2×3=12（整數(shù)，z=12<14）。分支1-2-2：x?≥3,x?≥3約束：2×3+3×3=6+9=15>14，無可行解。所有分支處理完畢，最大整數(shù)解為x?=4,x?=1，z=14。5.動(dòng)態(tài)規(guī)劃應(yīng)用（10分）某公司計(jì)劃將5萬元投資于3個(gè)項(xiàng)目，各項(xiàng)目投資x（萬元）的收益如下表，求最大總收益。|投資x（萬元）|0|1|2|3|4|5||---------------|---|---|---|---|---|---||項(xiàng)目1收益r?(x)|0|2|5|6|8|9||項(xiàng)目2收益r?(x)|0|3|5|7|8|9||項(xiàng)目3收益r?(x)|0|4|6|7|8|9|參考答案：階段k=1,2,3（對應(yīng)項(xiàng)目1-3）；狀態(tài)s_k為第k階段初剩余資金；決策x_k為第k階段投資金額（0≤x_k≤s_k）；狀態(tài)轉(zhuǎn)移s_{k+1}=s_k-x_k；指標(biāo)函數(shù)f_k(s_k)=max{r_k(x_k)+f_{k+1}(s_k-x_k)}，邊界條件f?(s?)=0。（1）k=3（項(xiàng)目3）：f?(s?)=max{r?(x?)}，x?=0到s?：s?=0:x?=0,f?=0s?=1:x?=1,f?=4s?=2:x?=2,f?=6s?=3:x?=3,f?=7s?=4:x?=4,f?=8s?=5:x?=5,f?=9（2）k=2（項(xiàng)目2）：f?(s?)=max{r?(x?)+f?(s?-x?)}，x?=0到s?：s?=0:x?=0,f?=0+0=0s?=1:x?=0→0+4=4；x?=1→3+0=3→max=4s?=2:x?=0→0+6=6；x?=1→3+4=7；x?=2→5+0=5→max=7（x?=1）s?=3:x?=0→0+7=7；x?=1→3+6=9；x?=2→5+4=9；x?=3→7+0=7→max=9（x?=1或2）s?=4:x?=0→0+8=8；x?=1→3+7=10；x?=2→5+6=11；x?=3→7+4=11；x?=4→8+0=8→max=11（x?=2或3）s?=5:x?=0→0+9=9；x?=1→3+8=11；x?=2→5+7=12；x?=3→7+6=13；x?=4→8+4=12；x?=5→9+0=9→max=13（x?=3）（3）k=1（項(xiàng)目1）：f?(5)=max{r?(x?)+f?(5-x?)}，x?=0到5：x?=0→0+f?(5)=13x?=1→2+f?(4)=2+11=13x?=2→5+f?(3)=5+9=14x?=3→6+f?(2)=6+7=13x?=4→8+f?(1)=8+4=12x?=5→9+f?(0)=9+0=9最大f?(5)=14，對應(yīng)x?=2，s?=5-2=3，f?(3)=9（x?=1或2）：若x?=1，