2025年大學(xué)《數(shù)理基礎(chǔ)科學(xué)》專業(yè)題庫——最優(yōu)化問題的實際應(yīng)用考試時間：______分鐘總分：______分姓名：______一、1.解釋線性規(guī)劃問題的基本要素。2.說明為什么單純形法通常適用于求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題。3.給出目標(biāo)函數(shù)和約束條件均為線性時，求解該問題的常用算法名稱。二、4.對于非線性規(guī)劃問題`f(x)`約束于`g_i(x)≤0(i=1,2,...,m)`，簡述使用KKT條件判斷局部最優(yōu)解是否為全局最優(yōu)解的充分條件涉及哪些關(guān)鍵要素。5.比較梯度下降法和牛頓法在求解無約束優(yōu)化問題`minf(x)`時，收斂速度和所需計算量的主要差異。6.描述動態(tài)規(guī)劃解決最優(yōu)化問題的核心思想，并舉例說明其適用條件。三、7.某工廠生產(chǎn)兩種產(chǎn)品A和B，每單位產(chǎn)品A需要消耗原材料1千克和能源2千瓦時，利潤為3元；每單位產(chǎn)品B需要消耗原材料1.5千克和能源1千瓦時，利潤為2.5元。工廠每周可獲取原材料300千克，能源800千瓦時。請建立此生產(chǎn)計劃問題的線性規(guī)劃模型。8.在求解非線性規(guī)劃問題`minf(x)`時，若當(dāng)前點(diǎn)xk處的海森矩陣H(xk)為負(fù)定，根據(jù)梯度法迭代方向的選擇原則，應(yīng)如何確定下一步搜索方向？9.一個設(shè)備需要在三周內(nèi)完成三項任務(wù)。第一周和第二周各有兩種活動可以選擇，第三周必須完成一項活動?；顒娱g的先后關(guān)系及所需時間（周）如下：活動1完成后活動2才能開始（需1周），活動2完成后活動3才能開始（需1周）。若選擇活動1或2，則收益分別為10或8；選擇活動3，則收益為12。請建立此任務(wù)安排問題的動態(tài)規(guī)劃模型。四、10.假設(shè)一個物資配送問題，需要在多個倉庫向多個客戶配送商品，目標(biāo)是使得總配送成本最低。簡述如何將此問題轉(zhuǎn)化為線性規(guī)劃模型，并說明需要引入哪些變量和約束條件。11.考慮一個參數(shù)`ε>0`，解釋如何通過罰函數(shù)法將帶不等式約束的優(yōu)化問題`minf(x)`約束于`g_i(x)≤0(i=1,2,...,m)`轉(zhuǎn)化為無約束優(yōu)化問題。12.某公司計劃進(jìn)行一項為期五年的投資，每年初有資金可用于投資。投資項目的回報率不同，但投資額和回收期受限。項目A，投資額100萬，一年后回收110萬；項目B，投資額200萬，三年后回收240萬；項目C，投資額150萬，五年后回收200萬。公司初始資金為300萬。請建立此投資組合問題的整數(shù)規(guī)劃模型。13.某網(wǎng)絡(luò)路由選擇問題，需要在節(jié)點(diǎn)間尋找一條路徑，使得總傳輸時延最小。若網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已知，且各鏈路的時延固定。簡述如何使用動態(tài)規(guī)劃思想來求解此問題，需要定義哪些狀態(tài)？14.比較多目標(biāo)優(yōu)化問題與單目標(biāo)優(yōu)化問題的求解難點(diǎn)，并簡述一種常用的多目標(biāo)優(yōu)化方法及其基本思想。15.設(shè)想一個機(jī)器學(xué)習(xí)模型訓(xùn)練中的超參數(shù)優(yōu)化問題，目標(biāo)是最小化驗證集上的損失函數(shù)。簡述如何將此問題形式化為一個優(yōu)化問題，并說明可能涉及哪些類型的約束或限制條件。試卷答案一、1.線性規(guī)劃問題的基本要素包括：決策變量（表示資源分配或活動水平的未知數(shù)）、目標(biāo)函數(shù)（表示要最大化或最小化的線性函數(shù)，通常代表利潤、成本等）、約束條件（表示資源限制或其他限制的線性不等式或等式）以及非負(fù)性約束（決策變量通常非負(fù)）。2.單純形法通過在可行域的頂點(diǎn)之間移動來尋找最優(yōu)解。標(biāo)準(zhǔn)形式的線性規(guī)劃問題（所有約束為等式，右側(cè)為正，目標(biāo)函數(shù)系數(shù)任意）的可行域頂點(diǎn)對應(yīng)于基礎(chǔ)解。單純形法從一個基本可行解（通常是原點(diǎn)或其鄰近頂點(diǎn)）開始，通過檢驗相鄰頂點(diǎn)是否帶來目標(biāo)函數(shù)值的改善，有系統(tǒng)地移動到更好的頂點(diǎn)，直到找到最優(yōu)解或確定無界解。這種移動方式在標(biāo)準(zhǔn)形式下易于實現(xiàn)，因為等式約束天然地定義了頂點(diǎn)。3.求解線性規(guī)劃問題的常用算法名稱包括單純形法、內(nèi)點(diǎn)法等。單純形法是早期發(fā)展且應(yīng)用廣泛的算法，內(nèi)點(diǎn)法是后來提出的數(shù)值更穩(wěn)定、在大規(guī)模問題中效率更高的算法。二、4.使用KKT條件判斷非線性規(guī)劃局部最優(yōu)解是否為全局最優(yōu)解的充分條件，關(guān)鍵要素通常涉及：目標(biāo)函數(shù)和約束函數(shù)的連續(xù)性和可微性；解滿足KKT條件（包括梯度關(guān)系、約束有效、乘子非負(fù)等）；約束函數(shù)是凸函數(shù)；目標(biāo)函數(shù)是凸函數(shù)。在凸優(yōu)化問題的背景下，滿足KKT條件的解必定是全局最優(yōu)解。對于非凸問題，除了KKT條件，還需要考慮解所在的原域是否唯一，以及在該原域內(nèi)目標(biāo)函數(shù)是否為嚴(yán)格凸函數(shù)，才能保證局部最優(yōu)解即為全局最優(yōu)解。5.梯度下降法在每一步只利用目標(biāo)函數(shù)在當(dāng)前點(diǎn)的梯度信息來確定搜索方向，方向指向函數(shù)值下降最快的方向。其收斂速度通常較慢，尤其當(dāng)目標(biāo)函數(shù)等值線接近圓形或扁平時，步長選擇不當(dāng)可能導(dǎo)致收斂非常緩慢。牛頓法利用目標(biāo)函數(shù)的二階導(dǎo)數(shù)（海森矩陣）信息，能夠構(gòu)造出更精確的搜索方向，理論上具有二次收斂速度，即在接近最優(yōu)解時收斂非?？?。但牛頓法需要計算和求解海森矩陣，計算量通常比梯度下降法大，且對初始點(diǎn)的選取和矩陣的正定性有要求。6.動態(tài)規(guī)劃解決最優(yōu)化問題的核心思想是“最優(yōu)子結(jié)構(gòu)”和“重疊子問題”。最優(yōu)子結(jié)構(gòu)指問題的最優(yōu)解包含其子問題的最優(yōu)解；重疊子問題指在問題的求解過程中，許多相同的子問題會被多次計算。動態(tài)規(guī)劃通過存儲子問題的最優(yōu)解（通常使用表格），避免重復(fù)計算，從而高效地求解原問題。適用條件通常是問題具有無后效性（當(dāng)前狀態(tài)決策只依賴于當(dāng)前狀態(tài)，與過去狀態(tài)無關(guān)）和可劃分性（問題可分解為相互獨(dú)立的子問題）。三、7.決策變量：設(shè)每周生產(chǎn)產(chǎn)品A的數(shù)量為x1，生產(chǎn)產(chǎn)品B的數(shù)量為x2。目標(biāo)函數(shù)：最大化總利潤，maxZ=3x1+2.5x2。約束條件：(1)原材料約束：1x1+1.5x2≤300(2)能源約束：2x1+1x2≤800(3)非負(fù)約束：x1≥0,x2≥0。模型為：maxZ=3x1+2.5x2s.t.x1+1.5x2≤3002x1+x2≤800x1,x2≥08.梯度法的目標(biāo)是沿著負(fù)梯度方向`-?f(xk)`下降。若海森矩陣H(xk)為負(fù)定，意味著在xk處函數(shù)f(x)的“山峰”形狀是向下凹的（局部嚴(yán)格凹函數(shù)）。在這種情況下，負(fù)梯度方向`-?f(xk)`已經(jīng)指向函數(shù)值下降最快的方向，因此下一步的搜索方向應(yīng)選擇為負(fù)梯度方向`-?f(xk)`。梯度法本身不利用海森矩陣信息來調(diào)整搜索方向。9.決策變量：設(shè)狀態(tài)變量`d_k`表示第k周（k=1,2,3）安排的任務(wù)（1表示活動1，2表示活動2，3表示活動3，0表示未安排任務(wù)）。階段變量：k=1,2,3。狀態(tài)轉(zhuǎn)移：d_1∈{0,1,2},d_2∈{0,1,2}且d_2≠0(若d_1=1),d_3=3(必須完成)。狀態(tài)轉(zhuǎn)移條件（根據(jù)任務(wù)先后關(guān)系）：-若d_k=1，則d_{k+1}∈{0,1,3}。-若d_k=2，則d_{k+1}∈{0,3}。（注意：d_{k+1}不能為2，因為活動3必須在活動2之后）收益：r(d_k)={0,10,8}(對應(yīng)d_k=0,1,2)。動態(tài)規(guī)劃遞歸方程：V_k(d_k)=max{r(d_k)+V_{k+1}(d_{k+1})}(k=3時V_4(d_4)=0){0}(若不允許安排任務(wù)d_k)邊界條件：V_4(d_4)=0。四、10.引入變量：設(shè)`x_ij`為從倉庫i配送給客戶j的商品數(shù)量。目標(biāo)函數(shù)：min總成本=ΣΣc_ij*x_ij(i=1,...,I,j=1,...,J)，其中c_ij為從倉庫i到客戶j的單位運(yùn)輸成本。約束條件：(1)倉庫供應(yīng)約束：Σ_jx_ij≤S_i(對每個倉庫i)，其中S_i為倉庫i的最大供應(yīng)能力。(2)客戶需求約束：Σ_ix_ij≥D_j(對每個客戶j)，其中D_j為客戶j的需求量。(3)非負(fù)約束：x_ij≥0(對所有i,j)。該模型是一個標(biāo)準(zhǔn)的運(yùn)輸問題或分配問題，是線性規(guī)劃的一種特殊形式。11.罰函數(shù)法通過在目標(biāo)函數(shù)中加入一個懲罰項來“懲罰”違反約束條件的解。對于不等式約束`g_i(x)≤0`，懲罰項通常形式為`ε*Σ_imax(0,g_i(x))^2`或`ε*Σ_imax(0,-g_i(x))^2`，其中`ε>0`是一個足夠大的常數(shù)，稱為罰因子。當(dāng)解`x`滿足`g_i(x)≤0`時，懲罰項為0，原目標(biāo)函數(shù)`f(x)`保持不變；當(dāng)解`x`違反約束`g_i(x)>0`時，懲罰項`ε*max(0,g_i(x))^2`會變得很大，使得目標(biāo)函數(shù)值顯著增加。這迫使優(yōu)化過程傾向于尋找更接近滿足約束條件的解。通過適當(dāng)選擇罰因子`ε`并逐步增大其值進(jìn)行迭代，可以希望得到逐漸逼近可行解的無約束問題的解序列。12.決策變量：設(shè)投資于項目A的金額為x1，投資于項目B的金額為x2，投資于項目C的金額為x3。目標(biāo)函數(shù)：最大化總回收額，maxZ=110/(1+1)x1+240/(1+3)x2+200/(1+5)x3=110x1+60x2+40x3。約束條件：(1)初始資金約束：x1+x2+x3≤300。(2)項目A投資額約束：x1=100。(3)項目B投資額約束：x2=200。(4)項目C投資額約束：x3=150。由于投資額是固定的，此模型實際上是一個等式約束的優(yōu)化問題。更準(zhǔn)確地說，這是一個確定性的投資組合問題，目標(biāo)函數(shù)是回收額，約束是總投資不超過初始資金，且各項目投資額固定。如果題目意圖是選擇部分項目投資，則需要將投資額約束改為`x1≤100,x2≤200,x3≤150`且`x1,x2,x3≥0`，目標(biāo)函數(shù)可能需要調(diào)整為`maxZ=110x1+60x2+40x3`。但根據(jù)描述，更像是固定額度的選擇問題。按固定額度描述，模型為：maxZ=110x1+60x2+40x3s.t.x1+x2+x3≤300x1=100x2=200x3=150x1,x2,x3≥0（此非負(fù)約束在此特定問題下是多余的）13.設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)集合為N，源節(jié)點(diǎn)為s，匯節(jié)點(diǎn)為t。定義狀態(tài)變量`V(i,j)`表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑時延（或距離），其中i,j∈N。狀態(tài)轉(zhuǎn)移可以基于動態(tài)規(guī)劃思想，從匯節(jié)點(diǎn)t開始反向遞推。例如，對于每個節(jié)點(diǎn)k（k≠t），可以計算`V(k,t)=min{V(k,j)+L_jk}`，其中j是k的鄰接節(jié)點(diǎn)，L_jk是節(jié)點(diǎn)j到節(jié)點(diǎn)k的鏈路時延。需要初始化`V(t,t)=0`，對于其他節(jié)點(diǎn)，初始時延無窮大。通過迭代計算所有`V(i,t)`的值，最終`V(s,t)`即為所求最短路徑時延。適用條件是網(wǎng)絡(luò)拓?fù)涔潭ǎ溌窌r延已知且為常數(shù)。14.多目標(biāo)優(yōu)化問題的難點(diǎn)在于：可能存在無窮多個解滿足所有約束，這些解在各個目標(biāo)之間難以取舍；目標(biāo)之間可能存在沖突，即提高一個目標(biāo)的值可能會降低另一個目標(biāo)的值。單目標(biāo)優(yōu)化問題只有一個目標(biāo)函數(shù)，解空間通常更集中，且最優(yōu)解是唯一的（在滿足約束的條件下）。常用的多目標(biāo)優(yōu)化方法有：(1)重量級法（加權(quán)和方法）：將多個目標(biāo)函數(shù)加權(quán)組合成一個單目標(biāo)函數(shù)進(jìn)行優(yōu)化。難點(diǎn)在于權(quán)重的確定往往是主觀的或需要額外信息。(2)ε-約束法：固定一個或多個目標(biāo)的高優(yōu)先級，將其作為約束，僅優(yōu)化剩余的目標(biāo)。(3)目標(biāo)規(guī)劃：為每個目標(biāo)設(shè)定一個期望值或目標(biāo)值，然后最小化目標(biāo)函數(shù)與期望值之間的偏差（正負(fù)偏差）。(4)基于帕累托最優(yōu)的概念：尋找一組非支配解（Pareto最優(yōu)解集），其中不存在任何一個解能在所有目標(biāo)上同時優(yōu)于另一個解。然后通過某種方法（如排序法、妥協(xié)法）從帕累托最優(yōu)集中選擇一個最終解?；舅枷胧且搿胺侵洹备拍睿ㄟ^迭代或進(jìn)化算法探索解空間，找到不同目標(biāo)間的平衡點(diǎn)。15.超參數(shù)優(yōu)化問題可以形式化為：優(yōu)化超參數(shù)向量`θ`，使得模型在驗證