2025年大學《數(shù)理基礎(chǔ)科學》專業(yè)題庫——離散優(yōu)化問題的數(shù)學求解考試時間：______分鐘總分：______分姓名：______一、選擇題1.下列問題中，屬于離散優(yōu)化問題的是（）。A.最小二乘法擬合B.曲線擬合C.最優(yōu)路徑規(guī)劃D.熱傳導方程求解2.在整數(shù)規(guī)劃中，要求決策變量取整數(shù)值的規(guī)劃問題是（）。A.線性規(guī)劃B.混合整數(shù)規(guī)劃C.0-1規(guī)劃D.非線性規(guī)劃3.下列算法中，屬于求解整數(shù)規(guī)劃問題的算法是（）。A.單純形法B.割平面法C.迭代法D.牛頓法4.在圖論中，連接兩個頂點的邊稱為（）。A.節(jié)點B.邊C.路徑D.回路5.最短路問題在圖論中通常使用（）算法進行求解。A.單純形法B.Dijkstra算法C.割平面法D.動態(tài)規(guī)劃6.下列說法中，正確的是（）。A.所有的線性規(guī)劃問題都可以用單純形法求解B.整數(shù)規(guī)劃問題一定比線性規(guī)劃問題難求解C.動態(tài)規(guī)劃適用于解決所有優(yōu)化問題D.啟發(fā)式算法一定能夠找到最優(yōu)解7.在0-1規(guī)劃中，決策變量只能取值（）。A.0或1B.正整數(shù)C.任意實數(shù)D.負整數(shù)8.下列說法中，錯誤的是（）。A.圖論是離散優(yōu)化的重要基礎(chǔ)B.網(wǎng)絡(luò)流問題是圖論的一個重要應(yīng)用C.整數(shù)規(guī)劃問題一定沒有最優(yōu)解D.啟發(fā)式算法可以在合理的時間內(nèi)找到近似最優(yōu)解9.分支定界法是一種用于求解（）的算法。A.線性規(guī)劃問題B.整數(shù)規(guī)劃問題C.非線性規(guī)劃問題D.動態(tài)規(guī)劃問題10.在動態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述了（）。A.當前狀態(tài)與下一個狀態(tài)之間的關(guān)系B.當前狀態(tài)與初始狀態(tài)之間的關(guān)系C.最優(yōu)解與次優(yōu)解之間的關(guān)系D.目標函數(shù)與約束條件之間的關(guān)系二、填空題1.離散優(yōu)化問題的目標函數(shù)通常是一個__________函數(shù)。2.離散優(yōu)化問題的約束條件通常是一組__________不等式或等式。3.整數(shù)規(guī)劃問題可以分為__________整數(shù)規(guī)劃和混合整數(shù)規(guī)劃。4.圖論中的頂點也稱為__________。5.網(wǎng)絡(luò)流問題的目標是最大化或最小化__________。6.單純形法是一種用于求解__________的算法。7.割平面法是一種用于求解__________的算法。8.動態(tài)規(guī)劃通常用于解決具有__________性質(zhì)的優(yōu)化問題。9.啟發(fā)式算法是一種用于求解__________的算法。10.離散優(yōu)化問題在實際中的應(yīng)用包括__________、__________和__________等。三、計算題1.用分支定界法求解以下整數(shù)規(guī)劃問題：MaxZ=3x1+2x2s.t.2x1+x2<=10x1+3x2<=15x1,x2>=0,且為整數(shù)2.用單純形法求解以下線性規(guī)劃問題：MinZ=2x1+3x2s.t.x1+x2>=42x1+x2<=8x1,x2>=03.用動態(tài)規(guī)劃求解以下背包問題：MaxZ=10x1+6x2s.t.2x1+3x2<=12x1,x2>=0,且為整數(shù)四、證明題1.證明：單純形法在有限步內(nèi)一定能夠找到線性規(guī)劃問題的最優(yōu)解（假設(shè)最優(yōu)解存在）。2.證明：動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。五、綜合應(yīng)用題1.某工廠生產(chǎn)兩種產(chǎn)品，每件產(chǎn)品A的利潤為3元，每件產(chǎn)品B的利潤為2元。生產(chǎn)每件產(chǎn)品A需要消耗2單位原料，生產(chǎn)每件產(chǎn)品B需要消耗3單位原料。工廠每月最多能夠消耗18單位原料。請問工廠應(yīng)該如何安排生產(chǎn)計劃，才能獲得最大利潤？請建立數(shù)學模型，并選擇合適的算法進行求解。2.某城市有n個路口，路口之間有道路連接。每條道路都有一個長度。請問如何規(guī)劃一條從路口1到路口n的最短路？請建立數(shù)學模型，并選擇合適的算法進行求解。試卷答案一、選擇題1.C2.C3.B4.B5.B6.D7.A8.C9.B10.A二、填空題1.線性2.線性3.純整數(shù)4.頂點5.流量6.線性規(guī)劃7.整數(shù)規(guī)劃8.無后效性9.難求解的離散優(yōu)化問題10.生產(chǎn)調(diào)度、資源分配、路徑規(guī)劃三、計算題1.解：(1)首先不考慮整數(shù)約束，求解相應(yīng)的線性規(guī)劃問題，得到最優(yōu)解x1=4.8,x2=2.4,Z=22.8。(2)取x1=4和x1=5分別為兩個分支，得到兩個子問題。(3)對x1=4的子問題，其最優(yōu)解為x1=4,x2=2.6667,Z=22.3333，不滿足整數(shù)約束，繼續(xù)分支。(4)對x1=4的子分支，取x2=2和x2=3分別為兩個分支，得到四個子問題。(5)對x1=4,x2=2的子問題，其最優(yōu)解為x1=4,x2=2,Z=22，滿足整數(shù)約束，為當前最優(yōu)解。(6)對x1=4,x2=3的子問題，其最優(yōu)解為x1=4.5,x2=3,Z=23.5，不滿足整數(shù)約束，繼續(xù)分支。(7)對x1=4,x2=3的子分支，取x1=4和x1=5分別為兩個分支，得到兩個子問題。(8)對x1=4,x2=3,x1=4的子問題，其最優(yōu)解為x1=4,x2=3,Z=23，滿足整數(shù)約束，但不如x1=4,x2=2的子問題好。(9)對x1=4,x2=3,x1=5的子問題，無解。(10)對x1=5的子問題，其最優(yōu)解為x1=5,x2=0,Z=15，不如x1=4,x2=2的子問題好。(11)綜上，最優(yōu)解為x1=4,x2=2,Z=22。2.解：(1)將目標函數(shù)和約束條件標準化，得到：MinZ=2x1+3x2s.t.-x1-x2<=-42x1+x2<=8x1,x2>=0(2)加入松弛變量x3,x4，將約束條件轉(zhuǎn)化為等式：-x1-x2+x3=-42x1+x2+x4=8x1,x2,x3,x4>=0(3)初始單純形表如下：|基變量|x1|x2|x3|x4|RHS||-------|----|----|----|----|-----||x3|-1|-1|1|0|-4||x4|2|1|0|1|8||Z|-2|-3|0|0|0|(4)選擇Z行中最大負系數(shù)對應(yīng)的變量x2作為入基變量，選擇x3行和x4行中正系數(shù)與RHS的比值最小的行x3行作為出基變量，進行初等行變換，得到新的單純形表：|基變量|x1|x2|x3|x4|RHS||-------|----|----|----|----|-----||x2|-1/2|1|-1/2|0|-4||x4|5/2|0|1/2|1|12||Z|-1/2|0|-3/2|0|12|(5)Z行已無負系數(shù)，停止迭代，最優(yōu)解為x1=0,x2=4,Z=12。3.解：(1)定義狀態(tài)dp[i][j]表示前i件物品恰好放入容量為j的背包中能夠獲得的最大價值。(2)狀態(tài)轉(zhuǎn)移方程為：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(3)邊界條件為：dp[0][j]=0,dp[i][0]=0(4)按照狀態(tài)轉(zhuǎn)移方程計算dp數(shù)組，最終dp[3][12]即為所求的最大價值，為15。四、證明題1.證明：(1)單純形法每次迭代都會將當前解移動到可行域的一個相鄰頂點，并且目標函數(shù)值得到改善（或保持不變）。(2)線性規(guī)劃問題的可行域是凸集，頂點數(shù)量有限。(3)因此，單純形法最多經(jīng)過可行域的頂點數(shù)量次迭代，就會找到最優(yōu)解（如果存在）。(4)每次迭代都通過檢查檢驗數(shù)來確定入基變量和出基變量，保證目標函數(shù)值得到改善或保持不變。(5)因此，單純形法在有限步內(nèi)一定能夠找到線性規(guī)劃問題的最優(yōu)解（假設(shè)最優(yōu)解存在）。2.證明：(1)假設(shè)問題具有最優(yōu)解，記為S*。(2)根據(jù)最優(yōu)解的定義，對于任意的子問題，其最優(yōu)解也必須是原問題最優(yōu)解的子結(jié)構(gòu)。(3)即，原問題的最優(yōu)解可以由其子問題的最優(yōu)解組合而成。(4)這正是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程所表達的含義。(5)因此，動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。五、綜合應(yīng)用題1.解：(1)設(shè)生產(chǎn)產(chǎn)品A的數(shù)量為x1，生產(chǎn)產(chǎn)品B的數(shù)量為x2，則數(shù)學模型為：MaxZ=3x1+2x2s.t.2x1+3x2<=18x1,x2>=0,且為整數(shù)(2)選擇分支定界法進行求解：(a)首先不考慮整數(shù)約束，求解相應(yīng)的線性規(guī)劃問題，得到最優(yōu)解x1=6,x2=2,Z=22。(b)取x1=6和x1=7分別為兩個分支，得到兩個子問題。(c)對x1=6的子問題，其最優(yōu)解為x1=6,x2=2,Z=22，滿足整數(shù)約束，為當前最優(yōu)解。(d)對x1=7的子問題，無解。(e)綜上，最優(yōu)解為x1=6,x2=2,Z=22。2.解：(1)設(shè)從路口i到路口j的路的長度為c[i][j]，則數(shù)學模型為：MinZ=sum(c[i][j]*x[i][j])s.t.sum(x[i][j])=1(i=1)sum(x[i][j])=1(j=n)x[i][j]<=1x[i][j]>=0(2)選擇Dijks