2025年大学《数学与应用数学》专业题库- 离散最优化问题的求解

2025年大学《数学与应用数学》专业题库——离散最优化问题的求解考试时间：______分钟总分：______分姓名：______一、1.写出线性规划问题$\maxz=3x_1+5x_2$s.t.$\begin{cases}x_1+x_2\leq4\\2x_1+x_2\leq5\\x_1\geq0,x_2\geq0\end{cases}$的对偶问题。2.已知线性规划问题$\maxz=c^Tx$s.t.$Ax\leqb,x\geq0$的一个可行解为$x=(x_1,x_2,\dots,x_n)^T$，且对应的基本解$x_B=(b_1,b_2,\dots,b_m)^T$。若$c_B^TB^{-1}A\leqc_B^T$，请根据单纯形法的判别准则说明$x$是否为该线性规划问题的最优解。3.简述单纯形法中，当进行基变量与非基变量之间的换基操作时，选择主元（进基变量对应的列向量中的正元素）时遵循的原则。二、1.用单纯形法求解以下线性规划问题：$\maxz=5x_1+3x_2$s.t.$\begin{cases}x_1+x_2\leq6\\x_1+2x_2\leq8\\x_2\leq3\\x_1\geq0,x_2\geq0\end{cases}$2.用对偶单纯形法求解以下线性规划问题：$\minw=4x_1+6x_2+8x_3$s.t.$\begin{cases}x_1+3x_2+2x_3\geq5\\2x_1+4x_2\geq12\\x_1+2x_2+4x_3\geq8\\x_1\geq0,x_2\geq0,x_3\geq0\end{cases}$三、1.已知整数规划问题：$\maxz=5x_1+8x_2$s.t.$\begin{cases}3x_1+2x_2\leq12\\5x_1+2x_2\leq10\\x_1\geq0,x_2\geq0,x_1,x_2\text{为整数}\end{cases}$用分支定界法求解该问题。2.某工厂计划生产两种产品A和B，产品A每件利润为3元，产品B每件利润为2元。生产产品A需要消耗原料甲1公斤，生产产品B需要消耗原料甲0.5公斤。工厂每月可供应原料甲共6公斤。生产产品A和产品B还需使用另一种原料乙，产品A每件消耗0.4公斤，产品B每件消耗0.3公斤，工厂每月可供应原料乙共3公斤。为了获得最大利润，工厂应如何安排两种产品的生产计划？（要求建立该问题的整数规划模型，并说明为什么需要使用整数规划模型）四、1.用动态规划方法求解以下最优化问题：求从点A到点E的最短路径长度。路径及相邻点间的距离如下图所示（图中数字表示距离）。```A——3——B——1——C||||6|5|2||||D——4——E```（注：此处无图，请根据描述想象路径结构：A与B、D相连；B与C、E相连；D与E相连；A与D直接相连）2.设有4项任务需要在4台不同的机器上加工。每项任务$i$加工在机器$j$上的时间$t_{ij}$如下表所示：||机器|M1|M2|M3|M4||---|---|---|---|---|---||任务||3|6|2|6||1||2|5|4|3||2||4|3|7|2||3||1|5|8|4||4||6|2|3|7|求安排任务在机器上的加工顺序，使得总加工时间最短。请先写出该问题的动态规划基本方程。试卷答案一、1.对偶问题：$\minw=4y_1+5y_2$s.t.$\begin{cases}y_1+2y_2\geq3\\y_1+y_2\geq5\\y_1\geq0,y_2\geq0\end{cases}$2.是。根据单纯形法判别准则，若$c_B^TB^{-1}A\leqc_B^T$，则当前基本可行解$x$为该线性规划问题的最优解。这里$c_B^TB^{-1}A$表示检验数向量，$c_B^T$表示目标函数系数向量。条件$c_B^TB^{-1}A\leqc_B^T$意味着所有检验数都不大于零，表明当前解已是最优解。3.选择主元的原则是在换入变量$x_k$对应的检验数行（$\sigma_k$行，即$c_B^TB^{-1}p_k-c_k$行）中，找到所有正元素（即$B^{-1}p_k\leqe_k$中对应$a_{ik}>0$的$a_{ik}$），然后在这些正元素中，选择对应比率$b_i/a_{ik}$（$b_i$是当前基本解向量$B^{-1}b$的第$i$个分量，$a_{ik}>0$）最小的那个元素$a_{rk}$。对应的基变量$x_r$将被换出。这个最小比率原则保证了在新的迭代中目标函数值有最大幅度的增加（或最小幅度的减少，对于minimization问题）。二、1.单纯形法求解过程：原问题化为标准型：$\maxz=5x_1+3x_2+0x_3+0x_4+0x_5$s.t.$\begin{cases}x_1+x_2+x_3=6\\x_1+2x_2+x_4=8\\x_2+x_5=3\\x_1,x_2,x_3,x_4,x_5\geq0\end{cases}$初始基本解$x=(0,0,6,8,3)^T$，$z=0$。选$x_1$进基，$x_3,x_4,x_5$出基中，$\min\{6/1,8/1,3/\infty\}=6/1$，选$x_1$对应的列（第一列）主元为1。换基后得新基本解$x=(6,0,0,2,3)^T$，$z=30$。继续迭代...最终最优解$x=(4,2,0,0,1)^T$，$\maxz=26$。2.对偶单纯形法求解过程：化为标准型（引入剩余变量$s_1,s_2,s_3\geq0$）：$\minw=4x_1+6x_2+8x_3+0s_1+0s_2+0s_3$s.t.$\begin{cases}-x_1-3x_2-2x_3-s_1=-5\\-2x_1-4x_2-s_2=-12\\-x_1-2x_2-4x_3-s_3=-8\\x_1,x_2,x_3,s_1,s_2,s_3\geq0\end{cases}$初始检验数$c_B^TB^{-1}N-c_N=(0,0,0)^T-(4,6,8)^T=(-4,-6,-8)^T$，$w=0$。选$x_3$进基，$s_1,s_2,s_3$出基中，$\min\{-4/-2,-6/-4,-8/-4\}=-4/-2=2$，选$x_3$对应的列（第三列）主元为-2。换基后得新基本解，$w=8$。继续迭代...最终最优解（可能需要检验整数性，根据具体分支定界法要求，此处假设已满足）$x=(0,3,2,0,0,0)^T$，$\minw=28$。三、1.分支定界法求解过程：（1）考虑对应于$x_1,x_2$的0-1整数规划问题。松弛变量$x_3,x_4,x_5\geq0$。$\maxz=5x_1+8x_2$s.t.$\begin{cases}3x_1+2x_2+x_3=12\\5x_1+2x_2+x_4=10\\x_1+x_2+x_5=6\\x_1,x_2\in\{0,1\},x_3,x_4,x_5\geq0\end{cases}$用枚举法或解松弛问题（LPRelaxation）：松弛问题的最优解为$x_1=2,x_2=2$（非整数），$z=18$。这是整数规划问题的上界$Z^*\leq18$。（2）分支：在松弛问题最优解中，取第一个非整数变量$x_1=2$进行分支。构造两个子问题：*子问题1（B1）：增加约束$x_1\leq1$。*子问题2（B2）：增加约束$x_1\geq2$。（3）解子问题B1：LP模型变为$\maxz=5x_1+8x_2$s.t.$\begin{cases}3x_1+2x_2\leq12\\5x_1+2x_2\leq10\\x_1+x_2\leq6\\x_1\leq1\\x_1,x_2\geq0\end{cases}$用图解法或单纯形法求解，最优解为$x_1=1,x_2=5$，$z=45$。此解满足整数约束，为整数可行解，故$Z^*\leq45$。由于$z=45>18$，此为当前整数最优解的候选，更新下界$Z\geq45$。（4）解子问题B2：LP模型变为$\maxz=5x_1+8x_2$s.t.$\begin{cases}3x_1+2x_2\leq12\\5x_1+2x_2\leq10\\x_1+x_2\leq6\\x_1\geq2\end{cases}$化简为$x_1\leq2$，$3x_1+2x_2\leq6$，$5x_1+2x_2\leq0$。此约束无解（$5x_1\leq0$且$x_1\leq2$），故子问题B2被剪掉。（5）最优解：当前最优整数解为$x_1=1,x_2=5$，$\maxz=45$。2.整数规划模型：设生产产品A的数量为$x_1$件，生产产品B的数量为$x_2$件。目标函数：$\maxz=3x_1+2x_2$约束条件：原料甲：$x_1+0.5x_2\leq6$原料乙：$0.4x_1+0.3x_2\leq3$非负整数：$x_1\geq0,x_2\geq0,x_1,x_2\text{为整数}$需要使用整数规划模型是因为题目要求“安排生产计划”，通常隐含着生产数量必须是整数件，而线性规划允许非整数解。四、1.动态规划求解最短路径：定义状态$f_i(v)$为从点$v$到终点E的最短路径长度。状态转移方程：$f_E(E)=0$$f_i(A)=\min\{f_A(B)+1,f_A(D)+6\}=\min\{f_B(B)+1+1,f_D(D)+6+6\}=\min\{f_B(B)+2,f_D(D)+12\}$$f_i(B)=\min\{f_B(C)+2,f_B(E)+1\}=\min\{f_C(C)+2+2,f_E(E)+1+1\}=\min\{f_C(C)+4,0+2\}$$f_i(C)=\min\{f_C(E)+2\}=\min\{f_E(E)+2\}=\min\{0+2\}=2$$f_i(D)=\min\{f_D(E)+4\}=\min\{f_E(E)+4\}=\min\{0+4\}=4$逆向递推计算：$f_C(C)=2$$f_B(B)=\min\{2+4,2\}