2025年大学《数理基础科学》专业题库- 最优化问题的实际应用

2025年大学《数理基础科学》专业题库——最优化问题的实际应用考试时间：______分钟总分：______分姓名：______一、1.解释线性规划问题的基本要素。2.说明为什么单纯形法通常适用于求解标准形式的线性规划问题。3.给出目标函数和约束条件均为线性时，求解该问题的常用算法名称。二、4.对于非线性规划问题`f(x)`约束于`g_i(x)≤0(i=1,2,...,m)`，简述使用KKT条件判断局部最优解是否为全局最优解的充分条件涉及哪些关键要素。5.比较梯度下降法和牛顿法在求解无约束优化问题`minf(x)`时，收敛速度和所需计算量的主要差异。6.描述动态规划解决最优化问题的核心思想，并举例说明其适用条件。三、7.某工厂生产两种产品A和B，每单位产品A需要消耗原材料1千克和能源2千瓦时，利润为3元；每单位产品B需要消耗原材料1.5千克和能源1千瓦时，利润为2.5元。工厂每周可获取原材料300千克，能源800千瓦时。请建立此生产计划问题的线性规划模型。8.在求解非线性规划问题`minf(x)`时，若当前点xk处的海森矩阵H(xk)为负定，根据梯度法迭代方向的选择原则，应如何确定下一步搜索方向？9.一个设备需要在三周内完成三项任务。第一周和第二周各有两种活动可以选择，第三周必须完成一项活动。活动间的先后关系及所需时间（周）如下：活动1完成后活动2才能开始（需1周），活动2完成后活动3才能开始（需1周）。若选择活动1或2，则收益分别为10或8；选择活动3，则收益为12。请建立此任务安排问题的动态规划模型。四、10.假设一个物资配送问题，需要在多个仓库向多个客户配送商品，目标是使得总配送成本最低。简述如何将此问题转化为线性规划模型，并说明需要引入哪些变量和约束条件。11.考虑一个参数`ε>0`，解释如何通过罚函数法将带不等式约束的优化问题`minf(x)`约束于`g_i(x)≤0(i=1,2,...,m)`转化为无约束优化问题。12.某公司计划进行一项为期五年的投资，每年初有资金可用于投资。投资项目的回报率不同，但投资额和回收期受限。项目A，投资额100万，一年后回收110万；项目B，投资额200万，三年后回收240万；项目C，投资额150万，五年后回收200万。公司初始资金为300万。请建立此投资组合问题的整数规划模型。13.某网络路由选择问题，需要在节点间寻找一条路径，使得总传输时延最小。若网络拓扑结构已知，且各链路的时延固定。简述如何使用动态规划思想来求解此问题，需要定义哪些状态？14.比较多目标优化问题与单目标优化问题的求解难点，并简述一种常用的多目标优化方法及其基本思想。15.设想一个机器学习模型训练中的超参数优化问题，目标是最小化验证集上的损失函数。简述如何将此问题形式化为一个优化问题，并说明可能涉及哪些类型的约束或限制条件。试卷答案一、1.线性规划问题的基本要素包括：决策变量（表示资源分配或活动水平的未知数）、目标函数（表示要最大化或最小化的线性函数，通常代表利润、成本等）、约束条件（表示资源限制或其他限制的线性不等式或等式）以及非负性约束（决策变量通常非负）。2.单纯形法通过在可行域的顶点之间移动来寻找最优解。标准形式的线性规划问题（所有约束为等式，右侧为正，目标函数系数任意）的可行域顶点对应于基础解。单纯形法从一个基本可行解（通常是原点或其邻近顶点）开始，通过检验相邻顶点是否带来目标函数值的改善，有系统地移动到更好的顶点，直到找到最优解或确定无界解。这种移动方式在标准形式下易于实现，因为等式约束天然地定义了顶点。3.求解线性规划问题的常用算法名称包括单纯形法、内点法等。单纯形法是早期发展且应用广泛的算法，内点法是后来提出的数值更稳定、在大规模问题中效率更高的算法。二、4.使用KKT条件判断非线性规划局部最优解是否为全局最优解的充分条件，关键要素通常涉及：目标函数和约束函数的连续性和可微性；解满足KKT条件（包括梯度关系、约束有效、乘子非负等）；约束函数是凸函数；目标函数是凸函数。在凸优化问题的背景下，满足KKT条件的解必定是全局最优解。对于非凸问题，除了KKT条件，还需要考虑解所在的原域是否唯一，以及在该原域内目标函数是否为严格凸函数，才能保证局部最优解即为全局最优解。5.梯度下降法在每一步只利用目标函数在当前点的梯度信息来确定搜索方向，方向指向函数值下降最快的方向。其收敛速度通常较慢，尤其当目标函数等值线接近圆形或扁平时，步长选择不当可能导致收敛非常缓慢。牛顿法利用目标函数的二阶导数（海森矩阵）信息，能够构造出更精确的搜索方向，理论上具有二次收敛速度，即在接近最优解时收敛非常快。但牛顿法需要计算和求解海森矩阵，计算量通常比梯度下降法大，且对初始点的选取和矩阵的正定性有要求。6.动态规划解决最优化问题的核心思想是“最优子结构”和“重叠子问题”。最优子结构指问题的最优解包含其子问题的最优解；重叠子问题指在问题的求解过程中，许多相同的子问题会被多次计算。动态规划通过存储子问题的最优解（通常使用表格），避免重复计算，从而高效地求解原问题。适用条件通常是问题具有无后效性（当前状态决策只依赖于当前状态，与过去状态无关）和可划分性（问题可分解为相互独立的子问题）。三、7.决策变量：设每周生产产品A的数量为x1，生产产品B的数量为x2。目标函数：最大化总利润，maxZ=3x1+2.5x2。约束条件：(1)原材料约束：1x1+1.5x2≤300(2)能源约束：2x1+1x2≤800(3)非负约束：x1≥0,x2≥0。模型为：maxZ=3x1+2.5x2s.t.x1+1.5x2≤3002x1+x2≤800x1,x2≥08.梯度法的目标是沿着负梯度方向`-∇f(xk)`下降。若海森矩阵H(xk)为负定，意味着在xk处函数f(x)的“山峰”形状是向下凹的（局部严格凹函数）。在这种情况下，负梯度方向`-∇f(xk)`已经指向函数值下降最快的方向，因此下一步的搜索方向应选择为负梯度方向`-∇f(xk)`。梯度法本身不利用海森矩阵信息来调整搜索方向。9.决策变量：设状态变量`d_k`表示第k周（k=1,2,3）安排的任务（1表示活动1，2表示活动2，3表示活动3，0表示未安排任务）。阶段变量：k=1,2,3。状态转移：d_1∈{0,1,2},d_2∈{0,1,2}且d_2≠0(若d_1=1),d_3=3(必须完成)。状态转移条件（根据任务先后关系）：-若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}(对应d_k=0,1,2)。动态规划递归方程：V_k(d_k)=max{r(d_k)+V_{k+1}(d_{k+1})}(k=3时V_4(d_4)=0){0}(若不允许安排任务d_k)边界条件：V_4(d_4)=0。四、10.引入变量：设`x_ij`为从仓库i配送给客户j的商品数量。目标函数：min总成本=ΣΣc_ij*x_ij(i=1,...,I,j=1,...,J)，其中c_ij为从仓库i到客户j的单位运输成本。约束条件：(1)仓库供应约束：Σ_jx_ij≤S_i(对每个仓库i)，其中S_i为仓库i的最大供应能力。(2)客户需求约束：Σ_ix_ij≥D_j(对每个客户j)，其中D_j为客户j的需求量。(3)非负约束：x_ij≥0(对所有i,j)。该模型是一个标准的运输问题或分配问题，是线性规划的一种特殊形式。11.罚函数法通过在目标函数中加入一个惩罚项来“惩罚”违反约束条件的解。对于不等式约束`g_i(x)≤0`，惩罚项通常形式为`ε*Σ_imax(0,g_i(x))^2`或`ε*Σ_imax(0,-g_i(x))^2`，其中`ε>0`是一个足够大的常数，称为罚因子。当解`x`满足`g_i(x)≤0`时，惩罚项为0，原目标函数`f(x)`保持不变；当解`x`违反约束`g_i(x)>0`时，惩罚项`ε*max(0,g_i(x))^2`会变得很大，使得目标函数值显著增加。这迫使优化过程倾向于寻找更接近满足约束条件的解。通过适当选择罚因子`ε`并逐步增大其值进行迭代，可以希望得到逐渐逼近可行解的无约束问题的解序列。12.决策变量：设投资于项目A的金额为x1，投资于项目B的金额为x2，投资于项目C的金额为x3。目标函数：最大化总回收额，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。由于投资额是固定的，此模型实际上是一个等式约束的优化问题。更准确地说，这是一个确定性的投资组合问题，目标函数是回收额，约束是总投资不超过初始资金，且各项目投资额固定。如果题目意图是选择部分项目投资，则需要将投资额约束改为`x1≤100,x2≤200,x3≤150`且`x1,x2,x3≥0`，目标函数可能需要调整为`maxZ=110x1+60x2+40x3`。但根据描述，更像是固定额度的选择问题。按固定额度描述，模型为：maxZ=110x1+60x2+40x3s.t.x1+x2+x3≤300x1=100x2=200x3=150x1,x2,x3≥0（此非负约束在此特定问题下是多余的）13.设网络节点集合为N，源节点为s，汇节点为t。定义状态变量`V(i,j)`表示从节点i到节点j的最短路径时延（或距离），其中i,j∈N。状态转移可以基于动态规划思想，从汇节点t开始反向递推。例如，对于每个节点k（k≠t），可以计算`V(k,t)=min{V(k,j)+L_jk}`，其中j是k的邻接节点，L_jk是节点j到节点k的链路时延。需要初始化`V(t,t)=0`，对于其他节点，初始时延无穷大。通过迭代计算所有`V(i,t)`的值，最终`V(s,t)`即为所求最短路径时延。适用条件是网络拓扑固定，链路时延已知且为常数。14.多目标优化问题的难点在于：可能存在无穷多个解满足所有约束，这些解在各个目标之间难以取舍；目标之间可能存在冲突，即提高一个目标的值可能会降低另一个目标的值。单目标优化问题只有一个目标函数，解空间通常更集中，且最优解是唯一的（在满足约束的条件下）。常用的多目标优化方法有：(1)重量级法（加权和方法）：将多个目标函数加权组合成一个单目标函数进行优化。难点在于权重的确定往往是主观的或需要额外信息。(2)ε-约束法：固定一个或多个目标的高优先级，将其作为约束，仅优化剩余的目标。(3)目标规划：为每个目标设定一个期望值或目标值，然后最小化目标函数与期望值之间的偏差（正负偏差）。(4)基于帕累托最优的概念：寻找一组非支配解（Pareto最优解集），其中不存在任何一个解能在所有目标上同时优于另一个解。然后通过某种方法（如排序法、妥协法）从帕累托最优集中选择一个最终解。基本思想是引入“非支配”概念，通过迭代或进化算法探索解空间，找到不同目标间的平衡点。15.超参数优化问题可以形式化为：优化超参数向量`θ`，使得模型在验证