2025年大學(xué)《數(shù)學(xué)與應(yīng)用數(shù)學(xué)》專業(yè)題庫(kù)——數(shù)學(xué)優(yōu)化與運(yùn)籌學(xué)考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題3分，共15分。請(qǐng)將正確選項(xiàng)的字母填在題后的括號(hào)內(nèi)）1.下列關(guān)于線性規(guī)劃問(wèn)題的說(shuō)法中，正確的是（）。(A)線性規(guī)劃問(wèn)題的可行解集一定是凸多邊形(B)線性規(guī)劃問(wèn)題若有最優(yōu)解，則一定存在唯一最優(yōu)解(C)線性規(guī)劃問(wèn)題的最優(yōu)解一定在可行解集的頂點(diǎn)上取得(D)線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定在可行解集的內(nèi)部達(dá)到最優(yōu)值2.在單純形法迭代中，若某非基變量的檢驗(yàn)數(shù)σj>0，且其對(duì)應(yīng)的系數(shù)列向量πj全部非正，則該線性規(guī)劃問(wèn)題（）。(A)有唯一最優(yōu)解(B)無(wú)界(C)最優(yōu)解不止一個(gè)(D)無(wú)可行解3.已知某線性規(guī)劃問(wèn)題采用單純形法求解，當(dāng)前基本解對(duì)應(yīng)的檢驗(yàn)數(shù)有正有負(fù)。若負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列向量中，存在某分量大于0，則該問(wèn)題（）。(A)一定存在無(wú)窮多最優(yōu)解(B)無(wú)界(C)可能存在無(wú)窮多最優(yōu)解(D)一定無(wú)最優(yōu)解4.在運(yùn)輸問(wèn)題的表上作業(yè)法中，若某次迭代得到的檢驗(yàn)數(shù)均非正，則該解（）。(A)一定不是最優(yōu)解(B)可能是最優(yōu)解(C)一定是最優(yōu)解(D)一定不是可行解5.指派問(wèn)題的數(shù)學(xué)模型是（）。(A)一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題(B)一個(gè)整數(shù)規(guī)劃問(wèn)題(C)一個(gè)非線性規(guī)劃問(wèn)題(D)一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題二、填空題（每小題4分，共20分。請(qǐng)將答案填在題后的橫線上）6.線性規(guī)劃問(wèn)題(s.t.Ax≤b,x≥0)的對(duì)偶問(wèn)題是__________。7.若線性規(guī)劃問(wèn)題的某個(gè)基本解不是可行解，則該基本解對(duì)應(yīng)的單純形表中的檢驗(yàn)數(shù)一定存在________。8.在單純形法中，若某次迭代中所有檢驗(yàn)數(shù)均滿足σj≤0，且存在檢驗(yàn)數(shù)σj=0，則該線性規(guī)劃問(wèn)題________。9.運(yùn)輸問(wèn)題的目標(biāo)是實(shí)現(xiàn)總運(yùn)輸成本________。10.在圖論中，連通圖是指該圖存在________條路徑可以連接其任意兩個(gè)頂點(diǎn)。三、計(jì)算題（每小題10分，共30分）11.用單純形法求解下列線性規(guī)劃問(wèn)題：MaxZ=3x1+5x2s.t.x1+x2≤42x1+x2≤6x1,x2≥012.某公司生產(chǎn)兩種產(chǎn)品A和B，需要消耗兩種資源甲和乙。資源甲每月可用量為300單位，資源乙每月可用量為400單位。生產(chǎn)每單位產(chǎn)品A需消耗資源甲3單位，資源乙2單位，利潤(rùn)為40元；生產(chǎn)每單位產(chǎn)品B需消耗資源甲1單位，資源乙3單位，利潤(rùn)為50元。問(wèn)該公司應(yīng)如何安排生產(chǎn)計(jì)劃，才能使每月總利潤(rùn)最大？請(qǐng)建立該問(wèn)題的線性規(guī)劃模型。13.用圖上作業(yè)法求解下列運(yùn)輸問(wèn)題（單位：元/噸）：產(chǎn)地B1B2產(chǎn)量A13117A2194銷量369四、證明題（共15分）14.證明：若線性規(guī)劃問(wèn)題(L)的最優(yōu)解x*在頂點(diǎn)Bi處取得，且存在另一個(gè)頂點(diǎn)Bj，使得對(duì)應(yīng)于Bi和Bj的兩個(gè)相鄰單純形表的檢驗(yàn)數(shù)向量相同，則(L)存在無(wú)窮多最優(yōu)解。五、應(yīng)用題（共20分）15.某公司計(jì)劃在未來(lái)三個(gè)月內(nèi)生產(chǎn)三種產(chǎn)品P1,P2,P3。每月的工時(shí)限制為400小時(shí)，原材料供應(yīng)限制為600單位。生產(chǎn)每單位產(chǎn)品P1需要工時(shí)10小時(shí)，原材料20單位，利潤(rùn)為30元；生產(chǎn)每單位產(chǎn)品P2需要工時(shí)8小時(shí)，原材料15單位，利潤(rùn)為25元；生產(chǎn)每單位產(chǎn)品P3需要工時(shí)12小時(shí)，原材料10單位，利潤(rùn)為40元。公司希望在滿足工時(shí)和原材料限制的前提下，最大化總利潤(rùn)。此外，由于市場(chǎng)需求原因，產(chǎn)品P2的產(chǎn)量不能超過(guò)50單位。請(qǐng)建立該問(wèn)題的線性規(guī)劃模型。試卷答案一、選擇題1.C2.B3.B4.C5.A二、填空題6.Maxw=y1b1+y2b2+...+ymbms.t.y1a1+y2a2+...+yma≥c1y1a1+y2a2+...+yma≥c2...y1a1+y2a2+...+yma≥cny1,y2,...,ym≥07.正數(shù)8.可能存在無(wú)窮多最優(yōu)解9.最小10.一條三、計(jì)算題11.解：引入松弛變量x3,x4，化為標(biāo)準(zhǔn)型：MaxZ=3x1+5x2s.t.x1+x2+x3=42x1+x2+x4=6x1,x2,x3,x4≥0初始單純形表：|基變量|x1|x2|x3|x4|RHS||------|----|----|----|----|-----||x3|1|1|1|0|4||x4|2|1|0|1|6||Z|-3|-5|0|0|0|選擇入基變量：max{3,5}=5，對(duì)應(yīng)x2。選擇出基變量：min{4/1,6/1}=4/1=4，對(duì)應(yīng)x3。主元為1。進(jìn)行初等行變換：|基變量|x1|x2|x3|x4|RHS||------|----|----|----|----|-----||x2|1|1|1|0|4||x4|1|0|-1|1|2||Z|-3|-5|0|0|0|更新檢驗(yàn)數(shù)：-3-5*1=-8，-5-5*0=-5，0-5*(-1)=5，0-5*1=-5。檢驗(yàn)數(shù)仍存在正數(shù)（5），選擇入基變量：max{-8,-5,5}=5，對(duì)應(yīng)x3。選擇出基變量：min{4/1,2/-1}=min(4,-2)=-2(取倒數(shù)比較)，對(duì)應(yīng)x4。主元為-1。進(jìn)行初等行變換：|基變量|x1|x2|x3|x4|RHS||------|----|----|----|----|-----||x2|0|1|2|-1|6||x3|1|0|1|-1|2||Z|0|0|5|-5|20|檢驗(yàn)數(shù)均非正，最優(yōu)解為x1=0,x2=6,x3=2,x4=0。最大利潤(rùn)Z=20。12.解：設(shè)每月生產(chǎn)產(chǎn)品Ax1單位，生產(chǎn)產(chǎn)品Bx2單位。目標(biāo)函數(shù)：MaxZ=40x1+50x2約束條件：x1+x2≤4(工時(shí)限制)2x1+x2≤6(資源乙限制)x1,x2≥0(非負(fù)限制)模型為：MaxZ=40x1+50x2s.t.x1+x2≤42x1+x2≤6x1,x2≥013.解：（1）用最小元素法給出初始調(diào)運(yùn)方案：產(chǎn)地B1B2產(chǎn)量A13117A2194銷量369調(diào)運(yùn)方案：A1→B2:min(7,6)=6，費(fèi)用36。A1→B1:7-6=1，費(fèi)用3。A2→B1:min(4,3)=3，費(fèi)用3。A2→B2:4-3=1，費(fèi)用9?？傔\(yùn)費(fèi)=36+3+3+9=51元。（2）計(jì)算空格檢驗(yàn)數(shù)（閉回路法）：△A1B1:(3-1)+(9-11)=1△A2B2:(1-9)+(11-3)=-4△A1B2:(3-9)+(11-1)=-5△A2B1:(1-11)+(9-3)=-4由于存在負(fù)檢驗(yàn)數(shù)（△A1B1=1,△A2B2=-4,△A1B2=-5），該解不是最優(yōu)解。選擇最小的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格（△A2B2）為調(diào)整格。（3）調(diào)整方案：從△A2B2出發(fā)，沿閉回路調(diào)整：A1B2:+1(最大可調(diào)量min(7,1)=1)A1B1:-1A2B1:+1(最大可調(diào)量min(3,1)=1)A2B2:-1新調(diào)運(yùn)方案：A1→B2:6+1=7，費(fèi)用77。A1→B1:1-1=0，費(fèi)用0。A2→B1:3+1=4，費(fèi)用12。A2→B2:1-1=0，費(fèi)用0?？傔\(yùn)費(fèi)=77+0+12+0=89元。（4）計(jì)算新空格檢驗(yàn)數(shù)：△A1B1:(3-1)+(9-11)=1△A1B2:(3-9)+(11-1)=-5△A2B1:(1-11)+(9-3)=-4仍存在負(fù)檢驗(yàn)數(shù)（△A1B2=-5,△A2B1=-4），繼續(xù)調(diào)整。選擇最小的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格（△A1B2）為調(diào)整格。（5）調(diào)整方案：從△A1B2出發(fā)，沿閉回路調(diào)整：A1B2:+2(最大可調(diào)量min(7,2)=2)A1B1:-2A2B1:+1(最大可調(diào)量min(4,1)=1)A2B2:-1新調(diào)運(yùn)方案：A1→B2:7+2=9，費(fèi)用99。A1→B1:0-2=-2(調(diào)整后為0)，費(fèi)用0。A2→B1:4+1=5，費(fèi)用15。A2→B2:0-1=-1(調(diào)整后為0)，費(fèi)用0?？傔\(yùn)費(fèi)=99+0+15+0=114元。（6）計(jì)算新空格檢驗(yàn)數(shù)：△A1B1:(3-1)+(9-11)=1△A1B2:(3-9)+(11-1)=-5△A2B1:(1-11)+(9-3)=-4仍存在負(fù)檢驗(yàn)數(shù)，繼續(xù)調(diào)整。選擇最小的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格（△A1B2）為調(diào)整格。（7）調(diào)整方案：從△A1B2出發(fā)，沿閉回路調(diào)整：A1B2:+1(最大可調(diào)量min(7,1)=1)A1B1:-1A2B1:+1(最大可調(diào)量min(5,1)=1)A2B2:-1新調(diào)運(yùn)方案：A1→B2:9+1=10，費(fèi)用110。A1→B1:0-1=-1(調(diào)整后為0)，費(fèi)用0。A2→B1:5+1=6，費(fèi)用18。A2→B2:0-1=-1(調(diào)整后為0)，費(fèi)用0?？傔\(yùn)費(fèi)=110+0+18+0=128元。（8）計(jì)算新空格檢驗(yàn)數(shù)：△A1B1:(3-1)+(9-11)=1△A1B2:(3-9)+(11-1)=-5△A2B1:(1-11)+(9-3)=-4檢驗(yàn)數(shù)均非負(fù)，最優(yōu)解為：A1→B2:10A1→B1:0A2→B1:6A2→B2:0最小總運(yùn)費(fèi)為128元。四、證明題14.證明：設(shè)最優(yōu)解為x*在頂點(diǎn)Bi處取得，對(duì)應(yīng)的基本解為xBi。若存在另一個(gè)頂點(diǎn)Bj，使得對(duì)應(yīng)的基本解為xBj。對(duì)偶問(wèn)題的最優(yōu)解y對(duì)應(yīng)于原問(wèn)題最優(yōu)解x*的值為yxBi。由題設(shè)，Bi和Bj是相鄰頂點(diǎn)，意味著從xBi到xBj的轉(zhuǎn)換是通過(guò)單純形法的一次迭代實(shí)現(xiàn)的。設(shè)這次迭代中，非基變量k進(jìn)入基，基變量l離開(kāi)基。在單純形法迭代中，新的檢驗(yàn)數(shù)向量（對(duì)應(yīng)于原始問(wèn)題）可以表示為舊檢驗(yàn)數(shù)向量加上某個(gè)向量（與原問(wèn)題系數(shù)矩陣的列向量和基本解有關(guān)）的倍數(shù)。具體地，若原檢驗(yàn)數(shù)為σ，新的檢驗(yàn)數(shù)為σ'，則有：σ'=σ+Cλ其中C是與原問(wèn)題系數(shù)矩陣、基本解、新進(jìn)入基變量k有關(guān)的一個(gè)向量，λ是迭代步長(zhǎng)。題設(shè)表明，對(duì)于所有與Bi和Bj相關(guān)的變量，新的檢驗(yàn)數(shù)向量在Bi處和在Bj處是相同的。這意味著從xBi到xBj的迭代沒(méi)有改變?nèi)魏螜z驗(yàn)數(shù)的值（或者說(shuō)，變化向量Cλ對(duì)于從xBi出發(fā)到xBj的路徑