2025年大學(xué)《系統(tǒng)科學(xué)與工程》專業(yè)題庫——系統(tǒng)優(yōu)化算法與數(shù)值計算方法考試時間：______分鐘總分：______分姓名：______一、簡述線性規(guī)劃問題的標(biāo)準(zhǔn)形式及其與一般形式之間的轉(zhuǎn)換方法。二、已知非線性規(guī)劃問題：$\minf(x)=x_1^2+x_2^2+4x_1x_2+4x_1+3x_2+4$$s.t.\quadx_1+x_2\leq3$$\quad\quadx_1,x_2\geq0$（1）試用斐波那契法或黃金分割法求$f(x)$在約束$x_1+x_2=3$下的最小值（要求迭代兩次）。（2）分析該問題是否存在唯一最優(yōu)解，并說明理由。三、某工程項目的子工程及其相互關(guān)系如下圖所示（僅列出活動及緊前活動）：活動A，無緊前活動?；顒覤，緊前活動為A?；顒覥，緊前活動為A?；顒覦，緊前活動為B。活動E，緊前活動為C?；顒覨，緊前活動為D,E。試用繪圖方法（如AOA或AON圖）表示該項目的網(wǎng)絡(luò)計劃，并計算各活動的最早開始時間（ES）、最早完成時間（EF）、最晚開始時間（LS）、最晚完成時間（LF），確定關(guān)鍵路徑和總工期。四、解釋什么是模擬退火算法？簡述其核心思想、主要參數(shù)（如初始溫度T、終止溫度T_0、降溫速率α）的含義，以及該算法解決優(yōu)化問題時的主要優(yōu)點。五、試推導(dǎo)梯形求積公式$\int_a^bf(x)dx\approx(b-a)(f(a)+f(b))/2$的誤差表達(dá)式（即截斷誤差）。六、給定數(shù)據(jù)點(1,2),(2,3),(3,5),(4,4)。（1）求經(jīng)過這四個點的最小二乘擬合直線方程$y=ax+b$。（2）若采用三次Hermite插值，寫出利用數(shù)據(jù)點(1,2),(2,3)計算函數(shù)值$P_3(x)$在$x=1.5$處的插值結(jié)果表達(dá)式（不必計算具體值）。七、求解線性方程組$Ax=b$，其中$A=\begin{pmatrix}4&1&-2\\1&2&0\\-2&0&3\end{pmatrix},\quadb=\begin{pmatrix}10\\5\\-7\end{pmatrix}$要求：（1）用高斯消元法（或Doolittle分解）求矩陣$A$的LU分解。（2）利用LU分解求解方程組$Ax=b$。八、已知函數(shù)$y=f(x)$的數(shù)值表如下：|$x$|0.0|0.1|0.2|0.3|0.4||------|------|------|------|------|------||$f(x)$|1.000|1.210|1.440|1.690|1.960|試用四階龍格-庫塔方法（RK4）求$f'(0.1)$的近似值（計算到小數(shù)點后四位）。試卷答案一、標(biāo)準(zhǔn)形式為$\maxZ=\mathbf{c}^T\mathbf{x}$,$\mathbf{A}\mathbf{x}\leq\mathbf$,$\mathbf{x}\geq0$。將一般形式$\maxZ=\mathbf{c}^T\mathbf{x}$,$\mathbf{A}\mathbf{x}=\mathbf$,$\mathbf{x}\geq0$轉(zhuǎn)換為標(biāo)準(zhǔn)形式：對于等式約束$\mathbf{A}_i\mathbf{x}=b_i$，若$\mathbf{A}_i$為行向量，可分解為$\mathbf{A}_i\mathbf{x}\leqb_i$和$-\mathbf{A}_i\mathbf{x}\leq-b_i$；若$\mathbf{A}_i$為列向量，可引入新變量$x_i',x_i''\geq0$，轉(zhuǎn)換為此不等式約束。對于$\leq$形式的約束$\mathbf{A}_i\mathbf{x}\leqb_i$，引入松馳變量$x_i\geq0$，轉(zhuǎn)換為$\mathbf{A}_i\mathbf{x}+x_i=b_i$。對于$\geq$形式的約束$\mathbf{A}_i\mathbf{x}\geqb_i$，引入剩余變量$x_i\geq0$，轉(zhuǎn)換為$\mathbf{A}_i\mathbf{x}-x_i=b_i$。目標(biāo)函數(shù)若為$\minW=-\mathbf{c}^T\mathbf{x}$，可等價轉(zhuǎn)換為$\maxZ=\mathbf{c}^T\mathbf{x}$。二、（1）采用黃金分割法。令$a=0,b=3,\lambda=\frac{\sqrt{5}-1}{2}\approx0.618,\mu=1-\lambda\approx0.382$。迭代0:$x_1=a+\mub=0+0.382\times3=1.146$,$x_2=a+\lambdab=0+0.618\times3=1.854$。$f(x_1)=1.146^2+1.146\times3+4\times1.146\times1.854+4\times1.146+3\times1.854+4\approx14.931$$f(x_2)=1.854^2+1.854\times3+4\times1.854\times1.146+4\times1.854+3\times1.146+4\approx19.838$因$f(x_1)<f(x_2)$，舍去區(qū)間$[1.854,3]$，令$b'=b,a'=a+\lambdab=1.854,x_1'=x_1,x_2'=x_1$。迭代1:$x_1'=a'+\mub'=1.854+0.382\times(3-1.854)=1.146$,$x_2'=a'+\lambdab'=1.854+0.618\times(3-1.854)=2.292$。$f(x_1')=f(x_1)\approx14.931$$f(x_2')=2.292^2+2.292\times3+4\times2.292\times1.146+4\times2.292+3\times1.146+4\approx18.826$因$f(x_1')<f(x_2')$，舍去區(qū)間$[2.292,3]$，令$b''=b',a''=a'+\lambdab'=2.292,x_1''=x_1',x_2''=x_1'$。近似最優(yōu)解$x^*\approxx_1''=1.146$，近似最優(yōu)值$f(x^*)\approx14.931$。（2）該問題的等式約束為$x_1+x_2=3$，目標(biāo)函數(shù)$f(x_1,x_2)=x_1^2+4x_1x_2+3x_2+4$關(guān)于$x_1,x_2$的海森矩陣為$H=\begin{pmatrix}2&4\\4&3\end{pmatrix}$。計算其特征值：$\det(H-\lambdaI)=\det(\begin{pmatrix}2-\lambda&4\\4&3-\lambda\end{pmatrix})=(2-\lambda)(3-\lambda)-16=\lambda^2-5\lambda-10$。解得$\lambda_1=\frac{5+\sqrt{65}}{2}>0,\lambda_2=\frac{5-\sqrt{65}}{2}<0$。由于存在負(fù)特征值，海森矩陣非正定，故該二次函數(shù)不是嚴(yán)格凸函數(shù)。因此，該非線性規(guī)劃問題可能存在多個局部最優(yōu)解，不一定存在唯一最優(yōu)解。三、（1）采用AOA圖表示：```A(1,0)---->B(4,1)---->D(7,4)\^\/|\/|\/|A(1,0)---->C(5,2)---->E(8,5)---->F(11,8)```（2）計算時間參數(shù)：活動：A(1,0,1,1),B(4,1,5,5),C(5,2,7,7),D(7,4,10,10),E(8,5,10,10),F(11,8,11,11)。關(guān)鍵路徑為A-B-D或A-C-E，總工期為10。四、模擬退火算法是一種隨機(jī)搜索算法，用于在大規(guī)模搜索空間中尋找問題的近似最優(yōu)解。其核心思想來源于物理中固體物質(zhì)的退火過程：將固體加熱到足夠高的溫度使其內(nèi)部粒子呈無序狀態(tài)，然后緩慢冷卻，粒子會逐漸趨于能量最低的晶格點。算法模擬這一過程，允許在搜索過程中接受一些“壞”解（即目標(biāo)函數(shù)值更差的解），以跳出局部最優(yōu)，增加找到全局最優(yōu)解的概率。主要參數(shù)：初始溫度T是算法開始時的“溫度”，控制初始階段接受較差解的程度，T越高，搜索空間越大，跳出局部最優(yōu)能力越強(qiáng)；終止溫度T_0是算法停止搜索的“低溫”，當(dāng)溫度降至T_0時，算法停止接受壞解，強(qiáng)制收斂到一個較優(yōu)解；降溫速率α(0<α<1)控制溫度下降的速度，α越小，降溫越慢，搜索過程越穩(wěn)定，但可能耗時更長。優(yōu)點包括：能跳出局部最優(yōu)，找到全局最優(yōu)解；算法參數(shù)相對簡單；對目標(biāo)函數(shù)形式無特殊要求（只需能計算函數(shù)值）；具有理論上收斂到最優(yōu)解的概率。五、令$x_0=a,x_1=b,y_0=f(a),y_1=f(b)$。梯形公式可視為對$f(x)$在$[a,b]$上的分段線性插值近似積分。將$[a,b]$等分為$n=1$段，每個小區(qū)間長度$h=b-a$。梯形公式為$\int_a^bf(x)dx\approx\frac{h}{2}(y_0+y_1)=\frac{b-a}{2}(f(a)+f(b))$。誤差來源于將曲線段近似為直線段產(chǎn)生的誤差。使用積分余項公式，對$f(x)$在$[a,b]$上進(jìn)行兩次泰勒展開：$f(a+h)=f(a)+hf'(a)+\frac{h^2}{2}f''(\xi_1)$,其中$\xi_1\in(a,a+h)$。$f(a-h)=f(a)-hf'(a)+\frac{h^2}{2}f''(\xi_2)$,其中$\xi_2\in(a-h,a)$。令$h=b-a$，則$f(b)=f(a+h)$,$f(a)=f(a-h)$。將兩式相加得：$2f(a)+2f(b)=2f(a)+2f(a+h)-2hf'(a)+\frac{h^2}{2}f''(\xi_1)+2hf'(a)-\frac{h^2}{2}f''(\xi_2)$$2f(a)+2f(b)=2f(a)+2f(b)+\frac{h^2}{2}(f''(\xi_1)-f''(\xi_2))$整理得：$\frac{b-a}{2}(f(a)+f(b))=f(a)+f(b)-\frac{h^2}{4}(f''(\xi_1)+f''(\xi_2))$因此，誤差為$E=\int_a^bf(x)dx-\frac{b-a}{2}(f(a)+f(b))=-\frac{h^2}{4}(f''(\xi_1)+f''(\xi_2))$。由于$f''(x)$在$[a,b]$上連續(xù)，由介值定理存在$\xi\in(a,b)$，使得$f''(\xi_1)+f''(\xi_2)=2f''(\xi)$。故截斷誤差為$E=-\frac{(b-a)^2}{8}f''(\xi)$。六、（1）最小二乘擬合直線方程為$y=ax+b$。法方程為$(\mathbf{X}^T\mathbf{X})\begin{pmatrix}a\\b\end{pmatrix}=\mathbf{X}^T\mathbf{Y}$，其中$\mathbf{X}=\begin{pmatrix}1&1\\2&1\\3&1\\4&1\end{pmatrix}$,$\mathbf{Y}=\begin{pmatrix}2\\3\\5\\4\end{pmatrix}$。$\mathbf{X}^T\mathbf{X}=\begin{pmatrix}30&10\\10&4\end{pmatrix}$,$\mathbf{X}^T\mathbf{Y}=\begin{pmatrix}14\\14\end{pmatrix}$。解$(\mathbf{X}^T\mathbf{X})\mathbf{p}=\mathbf{X}^T\mathbf{Y}$得$\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}1/2\\3/2\end{pmatrix}$。故擬合直線方程為$y=\frac{1}{2}x+\frac{3}{2}$。（2）三次Hermite插值利用每個數(shù)據(jù)點$(x_i,y_i)$處的函數(shù)值$y_i$及其一階導(dǎo)數(shù)值$y'_i$(此處未給出，假設(shè)為$y'_1,y'_2$)。插值多項式$P_3(x)$滿足$P_3(x_i)=y_i$,$P_3'(x_i)=y'_i$。在$[x_1,x_2]$區(qū)間，利用點$(x_1,y_1)$和$(x_2,y_2)$及其導(dǎo)數(shù)$y'_1,y'_2$構(gòu)造插值多項式。$P_3(x)$可表示為：$P_3(x)=y_1\cdotH_1(x)+y_2\cdotH_2(x)+y'_1\cdotK_1(x)+y'_2\cdotK_2(x)$其中，基函數(shù)$H_i(x),K_i(x)$滿足：$H_i(x_1)=H_i(x_2)=K_i(x_1)=K_i(x_2)=0$$H_i'(x_1)=H_i'(x_2)=K_i'(x_1)=K_i'(x_2)=0$$H_1(x_1)=1,H_2(x_2)=1$$K_1(x_1)=1,K_2(x_2)=1$具體表達(dá)式為：$H_1(x)=(x-x_2)^2(x-x_1)/[(x_1-x_2)(x_1-2x_2+3x)]$$H_2(x)=(x-x_1)^2(x-x_2)/[(x_2-x_1)(2x_2-x_1-x)]$$K_1(x)=(x-x_2)^2(x-x_1)/[(x_1-x_2)(x_1-2x_2+3x)]$$K_2(x)=(x-x_1)^2(x-x_2)/[(x_2-x_1)(2x_2-x_1-x)]$將$x=1.5$代入上述表達(dá)式，得到$P_3(1.5)$的值。該表達(dá)式即為所求。七、（1）對增廣矩陣$(A|b)$進(jìn)行高斯消元（或LU分解）：$(\begin{pmatrix}4&1&-2&|&10\\1&2&0&|&5\\-2&0&3&|&-7\end{pmatrix})$用第一行消去第二行、第三行中的第一列元素：$R_2\leftarrowR_2-\frac{1}{4}R_1\rightarrow(\begin{pmatrix}4&1&-2&|&10\\0&7/4&1/2&|&15/2\\-2&0&3&|&-7\end{pmatrix})$$R_3\leftarrowR_3+\frac{1}{2}R_1\rightarrow(\begin{pmatrix}4&1&-2&|&10\\0&7/4&1/2&|&15/2\\0&1/2&2&|&3\end{pmatrix})$用第二行消去第三行中的第二列元素：$R_3\leftarrowR_3-\frac{1}{7}R_2\rightarrow(\begin{pmatrix}4&1&-2&|&10\\0&7/4&1/2&|&15/2\\0&0&13/7&|&6/7\end{pmatrix})$矩陣$A$的LU分解為：$L=\begin{pmatrix}1&0&0\\1/4&1&0\\-1/2&-1/7&1\end{pmatrix},\quadU=\begin{pmatrix}4&1&-2\\0&7/4&1/2\\0&0&13/7\end{pmatrix}$（注意：此處$U$為上三角，$L$為單位下三角，若要求Doolittle分解，$U$為主對角線元素為1。）（2）利用LU分解求解$Ax=b$，即$Ly=b$,$Ux=y$。先解$Ly=b$：$\begin{pmatrix}1&0&0\\1/4&1&0\\-1/2&-1/7&1\end{pmatrix}\begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}=\begin{pmatrix}10\\15/2\\3\end{pmatrix}$得$y_1=10,y_2=15/2-1/4y_1=15/2-10/4=15/2-5/2=5,y_3=3+1/7y_2-(-1/2)y_1=3+5/7+5=3+5/7+10/2=3+5/7+35/7=38/7$。再解$Ux=y$：$\begin{pmatrix}4&1&-2\\0&7/4&1/2\\0&0&13/7\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}10\\5\\38/7\end{pmatrix}$得$x_3=38/7\div13/7=38/13,x_2=(5-1/2x_3)/(7/4)=(5-19/26)/(7/4)=(130/26-19/26)/(7/4)=111/26/(7/4)=111/26\times4/7=444/182=222/91,x_1=(10+2x_3-x_2)/4=(10+76/13-222/91)/4=(130/13+76/13-222/91)/4=(206/13-222/91)/4=(206\times7/91-222/91)/4=(1442/91-222/91)/4=1220/91/4=305/91$。解為$x_1=305/91,x_2=222/91,x_3=38/13$。八、采用四階龍格-庫塔方法（RK4）。函數(shù)$f(x)=x^2+4x^2+4x+3x+4=5x^2+7x+4$。步長$h=0.1$。初始點$x_0=0.0$，$y_0=f(x_0)=f(0.0)=4$。計算$k_i$值：$k_1=hf(x_0,y_0)=0.1\timesf(0.0,4)=0.1\times