2025年《運(yùn)籌學(xué)》期末考試試題及參考答案一、單項(xiàng)選擇題（每題2分，共20分）1.下列關(guān)于線性規(guī)劃標(biāo)準(zhǔn)型的描述中，錯(cuò)誤的是（）A.目標(biāo)函數(shù)為最大化或最小化B.所有約束條件均為等式C.決策變量非負(fù)D.右端常數(shù)項(xiàng)可為任意實(shí)數(shù)2.若原線性規(guī)劃問題存在可行解但無界，則其對(duì)偶問題（）A.無可行解B.有可行解且最優(yōu)值為0C.有可行解但無界D.可能有可行解也可能無可行解3.運(yùn)輸問題中，當(dāng)總供給量大于總需求量時(shí)，通常的處理方法是（）A.增加一個(gè)虛擬產(chǎn)地，其供給量為差額，單位運(yùn)價(jià)為0B.增加一個(gè)虛擬銷地，其需求量為差額，單位運(yùn)價(jià)為0C.調(diào)整現(xiàn)有產(chǎn)地的供給量，使供需平衡D.調(diào)整現(xiàn)有銷地的需求量，使供需平衡4.動(dòng)態(tài)規(guī)劃的核心思想是（）A.貪心選擇B.分治策略C.最優(yōu)性原理D.枚舉所有可能5.用Dijkstra算法求解無負(fù)權(quán)邊的最短路徑問題時(shí)，每次選擇的節(jié)點(diǎn)是（）A.距離起點(diǎn)最近的未標(biāo)記節(jié)點(diǎn)B.距離終點(diǎn)最近的未標(biāo)記節(jié)點(diǎn)C.邊權(quán)最小的節(jié)點(diǎn)D.路徑中節(jié)點(diǎn)數(shù)最少的節(jié)點(diǎn)6.排隊(duì)論中，M/M/2模型表示（）A.到達(dá)過程為泊松分布，服務(wù)時(shí)間為指數(shù)分布，2個(gè)服務(wù)臺(tái)B.到達(dá)過程為指數(shù)分布，服務(wù)時(shí)間為泊松分布，2個(gè)服務(wù)臺(tái)C.到達(dá)過程為泊松分布，服務(wù)時(shí)間為正態(tài)分布，2個(gè)服務(wù)臺(tái)D.到達(dá)過程為正態(tài)分布，服務(wù)時(shí)間為指數(shù)分布，2個(gè)服務(wù)臺(tái)7.對(duì)于目標(biāo)規(guī)劃問題，若優(yōu)先因子P?對(duì)應(yīng)的偏差變量未被完全滿足，則（）A.后續(xù)優(yōu)先因子P?及之后的目標(biāo)無法被滿足B.后續(xù)優(yōu)先因子的目標(biāo)仍可部分滿足C.問題無可行解D.需調(diào)整目標(biāo)函數(shù)的優(yōu)先級(jí)順序8.下列關(guān)于整數(shù)規(guī)劃分支定界法的描述中，正確的是（）A.分支時(shí)需選擇一個(gè)非整數(shù)解變量，將其分解為小于等于下取整和大于等于上取整兩個(gè)子問題B.定界時(shí)只需計(jì)算松弛問題的目標(biāo)值，無需比較子問題C.當(dāng)子問題無可行解時(shí)，直接剪枝D.最終最優(yōu)解一定來自某個(gè)子問題的整數(shù)解9.若某線性規(guī)劃問題的最優(yōu)單純形表中，松弛變量的檢驗(yàn)數(shù)為-3，則其對(duì)應(yīng)的對(duì)偶變量值為（）A.3B.-3C.0D.無法確定10.最大流問題中，增廣路徑是指（）A.從源點(diǎn)到匯點(diǎn)的路徑中所有邊的剩余容量均大于0B.從源點(diǎn)到匯點(diǎn)的路徑中至少有一條邊的剩余容量大于0C.從源點(diǎn)到匯點(diǎn)的路徑中所有邊的流量均為0D.從源點(diǎn)到匯點(diǎn)的路徑中至少有一條邊的流量等于容量二、填空題（每題2分，共10分）1.線性規(guī)劃問題中，松弛變量在目標(biāo)函數(shù)中的系數(shù)為______，剩余變量的系數(shù)為______。2.運(yùn)輸問題的初始可行解中，基變量的個(gè)數(shù)為______（設(shè)產(chǎn)地?cái)?shù)為m，銷地?cái)?shù)為n）。3.動(dòng)態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述的是從第k階段狀態(tài)到第k+1階段狀態(tài)的______關(guān)系。4.排隊(duì)系統(tǒng)的服務(wù)強(qiáng)度ρ=λ/(μc)，當(dāng)ρ______時(shí)，系統(tǒng)達(dá)到穩(wěn)定狀態(tài)。5.最小生成樹的邊數(shù)為______（設(shè)圖有n個(gè)節(jié)點(diǎn)）。三、計(jì)算題（共60分）1.（15分）某新能源企業(yè)生產(chǎn)A、B兩種型號(hào)的電池，需消耗鋰資源、生產(chǎn)線工時(shí)和包裝材料三種資源。已知生產(chǎn)1單位A電池消耗鋰資源3kg、工時(shí)2小時(shí)、包裝材料1kg，利潤(rùn)為800元；生產(chǎn)1單位B電池消耗鋰資源2kg、工時(shí)4小時(shí)、包裝材料3kg，利潤(rùn)為1000元。企業(yè)現(xiàn)有鋰資源120kg、工時(shí)160小時(shí)、包裝材料90kg。（1）建立線性規(guī)劃模型，求最大利潤(rùn)；（2）若鋰資源可增加至130kg，求新的最優(yōu)利潤(rùn)；（3）分析包裝材料的影子價(jià)格，并說明其經(jīng)濟(jì)意義。2.（15分）某運(yùn)輸公司需將500噸農(nóng)產(chǎn)品從3個(gè)產(chǎn)地（甲、乙、丙）運(yùn)往4個(gè)銷地（A、B、C、D），各產(chǎn)地的供給量分別為200噸、200噸、100噸，各銷地的需求量分別為150噸、150噸、100噸、100噸。單位運(yùn)價(jià)（元/噸）如下表：|銷地\產(chǎn)地|A|B|C|D||-----------|-----|-----|-----|-----||甲|12|15|10|8||乙|9|11|14|13||丙|7|10|5|6|（1）用伏格爾法求初始可行解；（2）用位勢(shì)法檢驗(yàn)初始解是否最優(yōu)，若否，用閉回路法調(diào)整至最優(yōu)。3.（12分）某企業(yè)考慮更新一臺(tái)使用了k年的設(shè)備（k=1,2,3），已知設(shè)備使用第t年（t=1,2,3,4）的收益為R(t)=12-2t（萬元），維修成本為C(t)=1+0.5t（萬元），更新設(shè)備的成本為K=8萬元。要求用動(dòng)態(tài)規(guī)劃法確定設(shè)備使用4年的最優(yōu)更新策略（假設(shè)第4年末設(shè)備無殘值）。4.（10分）某城市道路網(wǎng)絡(luò)如圖1所示（節(jié)點(diǎn)1為起點(diǎn)，節(jié)點(diǎn)6為終點(diǎn)，邊權(quán)為距離），用Dijkstra算法求1到6的最短路徑及距離。（圖1：節(jié)點(diǎn)1-2（3）、1-3（5）、2-3（1）、2-4（6）、3-4（2）、3-5（4）、4-5（3）、4-6（7）、5-6（5））5.（8分）某銀行柜臺(tái)服務(wù)系統(tǒng)為M/M/1模型，顧客平均到達(dá)率λ=6人/小時(shí)，平均服務(wù)率μ=8人/小時(shí)，求：（1）系統(tǒng)中無顧客的概率；（2）系統(tǒng)中的平均顧客數(shù)；（3）顧客在系統(tǒng)中的平均等待時(shí)間（小時(shí)）。四、應(yīng)用題（共10分）某電商企業(yè)計(jì)劃在兩個(gè)倉(cāng)庫(kù)（W1、W2）間分配1000件商品，運(yùn)往三個(gè)銷售點(diǎn)（S1、S2、S3）。W1的最大發(fā)貨量為700件，W2為500件；S1需求400件，S2需求300件，S3需求300件。運(yùn)輸成本（元/件）如下：W1到S1=5，W1到S2=8，W1到S3=6；W2到S1=7，W2到S2=4，W2到S3=9。要求：（1）建立運(yùn)輸問題模型（需明確變量、目標(biāo)函數(shù)、約束條件）；（2）若W1實(shí)際發(fā)貨量不超過650件，調(diào)整模型并說明是否需要引入虛擬節(jié)點(diǎn)。參考答案一、單項(xiàng)選擇題1.D2.A3.B4.C5.A6.A7.B8.A9.A10.A二、填空題1.0；0（松弛變量和剩余變量為輔助變量，目標(biāo)函數(shù)中系數(shù)為0）2.m+n-1（運(yùn)輸問題基變量個(gè)數(shù)為產(chǎn)地?cái)?shù)加銷地?cái)?shù)減1）3.轉(zhuǎn)移（狀態(tài)轉(zhuǎn)移方程描述狀態(tài)間的遞推關(guān)系）4.<1（服務(wù)強(qiáng)度小于1時(shí)系統(tǒng)穩(wěn)定）5.n-1（最小生成樹為連通n個(gè)節(jié)點(diǎn)的無環(huán)圖，邊數(shù)為n-1）三、計(jì)算題1.（1）設(shè)生產(chǎn)A電池x?單位，B電池x?單位，模型為：maxz=800x?+1000x?s.t.3x?+2x?≤120（鋰資源）2x?+4x?≤160（工時(shí)）x?+3x?≤90（包裝材料）x?,x?≥0用單純形法求解，初始表引入松弛變量s?,s?,s?，目標(biāo)函數(shù)標(biāo)準(zhǔn)化為maxz=800x?+1000x?+0s?+0s?+0s?。第一次迭代：檢驗(yàn)數(shù)σ?=800,σ?=1000（最大），選x?進(jìn)基。約束行比值：120/2=60，160/4=40，90/3=30（最?。?，s?出基。主元素為3，行變換后得到：x?=(90-x?-s?)/3=30-(1/3)x?-(1/3)s?代入其他約束：3x?+2(30-(1/3)x?-(1/3)s?)=(7/3)x?-(2/3)s?≤60→s?=60-(7/3)x?+(2/3)s?2x?+4(30-(1/3)x?-(1/3)s?)=(2/3)x?-(4/3)s?≤40→s?=40-(2/3)x?+(4/3)s?目標(biāo)函數(shù)z=800x?+1000(30-(1/3)x?-(1/3)s?)=30000+(1400/3)x?-(1000/3)s?第二次迭代：σ?=1400/3>0，選x?進(jìn)基。約束行比值：s?行60/(7/3)=180/7≈25.71，s?行40/(2/3)=60（最小），s?出基。主元素為2/3，行變換后：x?=(403/2)-(2/33/2)s?+(4/33/2)s?=60-s?+2s?代入x?=30-(1/3)(60-s?+2s?)-(1/3)s?=30-20+(1/3)s?-s?=10+(1/3)s?-s?s?=60-(7/3)(60-s?+2s?)+(2/3)s?=60-140+(7/3)s?-(14/3)s?+(2/3)s?=-80+(7/3)s?-4s?（出現(xiàn)負(fù)松弛變量，說明需繼續(xù)迭代？實(shí)際計(jì)算中可能出錯(cuò)，正確步驟應(yīng)為：正確單純形表迭代：初始可行解為(0,0,120,160,90)，檢驗(yàn)數(shù)(800,1000,0,0,0)。選x?進(jìn)基，最小比值90/3=30（包裝材料約束），故x?=30，s?=0。此時(shí)約束：3x?+230=3x?+60≤120→x?≤202x?+430=2x?+120≤160→x?≤20故x?=20，s?=120-320-230=0，s?=160-220-430=0，s?=0。此時(shí)解為(x?=20,x?=30)，z=80020+100030=16000+30000=46000元。（2）鋰資源增加到130kg，原約束變?yōu)?x?+2x?≤130。原最優(yōu)解x?=20,x?=30時(shí)，320+230=120≤130，仍滿足。此時(shí)是否需調(diào)整？計(jì)算鋰資源的影子價(jià)格：原對(duì)偶問題中，鋰資源的對(duì)偶變量y?=檢驗(yàn)數(shù)s?的相反數(shù)（標(biāo)準(zhǔn)型中松弛變量s?對(duì)應(yīng)對(duì)偶變量y?，檢驗(yàn)數(shù)σ?=c?-∑a_ijy_j=0-(3y?+2y?+1y?)=-3y?-2y?-y?=800（原變量x?的檢驗(yàn)數(shù)應(yīng)為0，可能之前描述有誤，正確對(duì)偶變量求解：原問題最優(yōu)時(shí)，對(duì)偶變量等于原問題松弛變量的檢驗(yàn)數(shù)相反數(shù)。原最優(yōu)表中，s?=0（鋰資源用盡），s?=0（工時(shí)用盡），s?=0（包裝材料用盡），故對(duì)偶問題的三個(gè)約束均為等式：3y?+2y?+y?=800（x?的系數(shù)）2y?+4y?+3y?=1000（x?的系數(shù)）y?,y?,y?≥0（對(duì)偶變量非負(fù)）解得：聯(lián)立方程，用消元法，第一式乘2得6y?+4y?+2y?=1600，減第二式得4y?-y?=600→y?=4y?-600。代入第一式：3y?+2y?+(4y?-600)=800→7y?+2y?=1400→y?=700-3.5y?。由于y?≥0，y?≥0，故700-3.5y?≥0→y?≤200；4y?-600≥0→y?≥150。取y?=150，則y?=700-3.5150=700-525=175，y?=4150-600=0。此時(shí)滿足所有條件。因此，鋰資源的影子價(jià)格為y?=150元/kg。當(dāng)鋰資源增加10kg（130-120），最優(yōu)利潤(rùn)增加15010=1500元，新利潤(rùn)為46000+1500=47500元。（3）包裝材料的影子價(jià)格為y?=0元/kg，說明在當(dāng)前最優(yōu)解下，包裝材料未用盡（原解中x?+3x?=20+90=110≤90？錯(cuò)誤，原計(jì)算有誤！正確原約束應(yīng)為x?+3x?≤90，當(dāng)x?=20,x?=30時(shí)，20+90=110>90，明顯矛盾，說明初始單純形法迭代錯(cuò)誤。正確解法應(yīng)為：重新建立約束：鋰資源：3x?+2x?≤120工時(shí)：2x?+4x?≤160→x?+2x?≤80包裝材料：x?+3x?≤90求交點(diǎn)：工時(shí)與包裝材料交點(diǎn)：x?=80-2x?，代入包裝材料得80-2x?+3x?=90→x?=10，x?=60。此時(shí)鋰資源：360+210=200>120，不滿足。鋰資源與工時(shí)交點(diǎn)：3x?+2x?=120，x?+2x?=80→相減得2x?=40→x?=20，x?=30。此時(shí)包裝材料：20+330=110>90，不滿足。鋰資源與包裝材料交點(diǎn)：3x?+2x?=120，x?+3x?=90→x?=90-3x?，代入得3(90-3x?)+2x?=120→270-7x?=120→x?=150/7≈21.43，x?=90-3(150/7)=(630-450)/7=180/7≈25.71。此時(shí)工時(shí)：2(180/7)+4(150/7)=(360+600)/7=960/7≈137.14≤160，滿足。工時(shí)與包裝材料交點(diǎn)不滿足鋰資源，故可行域頂點(diǎn)為：(0,0),(0,30)（包裝材料x?=30，x?=0，鋰資源0+60=60≤120，工時(shí)0+120=120≤160），(20,30)（鋰資源與工時(shí)交點(diǎn)，包裝材料超），(180/7,150/7)（鋰資源與包裝材料交點(diǎn)），(40,0)（鋰資源x?=40，x?=0，工時(shí)80≤160，包裝材料40≤90）。計(jì)算各頂點(diǎn)利潤(rùn)：(0,30):z=0+100030=30000(180/7,150/7):z=800(180/7)+1000(150/7)=(1