2025年大学《数理基础科学》专业题库- 线性规划与整数规划的解法比较

2025年大学《数理基础科学》专业题库——线性规划与整数规划的解法比较考试时间：______分钟总分：______分姓名：______一、1.写出线性规划问题的标准形式，并说明其中各符号的含义。2.简述单纯形法的基本思想和主要步骤。3.解释对偶单纯形法的适用条件和与标准单纯形法的主要区别。二、4.已知线性规划问题：$\maxZ=3x_1+5x_2$s.t.$\begin{cases}x_1+x_2\leq4\\2x_1+x_2\leq5\\x_1,x_2\geq0\end{cases}$求解该问题的初始单纯形表，并指出基变量和非基变量。三、5.什么是线性规划的对偶问题？请写出上述第4题所示问题的对偶问题。6.简述对偶理论中的强对偶定理，并说明其在线性规划求解中的应用价值。7.解释线性规划灵敏度分析的基本思想，它可以分析哪些方面的参数变化？四、8.写出纯整数规划与混合整数规划的定义，并举例说明。9.简述整数规划问题的可行域与相应的线性规划松弛问题的可行域之间的关系。10.解释分支定界法的基本思想，并说明在分支定界过程中如何进行剪枝？五、11.什么是整数规划的松弛问题？求解整数规划的松弛问题有何意义？12.简述割平面法的基本思想，并说明它是如何改进线性规划松弛问题的解界的。13.比较单纯形法求解线性规划松弛问题和分支定界法求解整数规划问题在基本思路上的主要不同点。六、14.对于一个标准形式的线性规划问题，若其所有检验数均为非正数，且最优解中存在取值为零的基变量，试问该最优解是唯一最优解吗？请说明理由。15.已知一个整数规划问题，其线性规划松弛问题的最优解为$x_1=3.6,x_2=2.4,Z=16.8$。请构造一个有效的Gomory割平面，并将其添加到松弛问题的最优单纯形表中（无需完成后续计算）。16.在比较线性规划与整数规划的求解难度时，通常提到多项式时间算法与非多项式时间算法。请简要解释什么是多项式时间算法，并说明为什么LP被认为有较好的计算复杂性而IP的计算复杂性相对较差。试卷答案一、1.线性规划问题的标准形式为：$\maxZ=\mathbf{c}^T\mathbf{x}$s.t.$\mathbf{Ax}=\mathbf{b}$,$\mathbf{x}\geq\mathbf{0}$，其中$\mathbf{c}=(c_1,c_2,\dots,c_n)^T$是价值向量，$\mathbf{x}=(x_1,x_2,\dots,x_n)^T$是决策变量向量，$\mathbf{A}$是$m\timesn$的系数矩阵，$\mathbf{b}=(b_1,b_2,\dots,b_m)^T$是资源向量，$\mathbf{0}$是零向量。$\mathbf{c}^T\mathbf{x}$表示目标函数，$\mathbf{Ax}=\mathbf{b}$表示约束条件（等式），$\mathbf{x}\geq\mathbf{0}$表示变量的非负限制。2.单纯形法的基本思想是：从可行域的一个顶点（通常是原点）开始，通过迭代寻找相邻的顶点，使得目标函数值得到改善（增大或减小），直到找到使目标函数达到最优值的顶点为止。主要步骤包括：确定初始基本可行解和初始单纯形表；计算检验数，判断是否达到最优解；若未达到最优解，选择入基变量和出基变量，进行基变换，得到新的基本可行解和单纯形表，然后返回第一步；若检验数均不大于零（对于最大化问题），则当前解为最优解。3.对偶单纯形法的适用条件是：当前解是基本解，且该基本解对应的检验数全非正（对于最大化问题）。与标准单纯形法的主要区别在于：标准单纯形法从可行解出发，沿着可行方向移动到最优解（检验数全非正），而对偶单纯形法从最优检验数条件出发，沿着非可行方向（通过出基变量）移动到新的基本解，同时保持检验数全非正，最终到达可行解（最优解）。二、4.将约束条件变为等式：$\begin{cases}x_1+x_2+x_3=4\\2x_1+x_2+x_4=5\end{cases}$，其中$x_3,x_4$为松弛变量。目标函数变为$\maxZ=3x_1+5x_2+0x_3+0x_4$。初始单纯形表如下（仅列出核心部分）：|基变量|$x_1$|$x_2$|$x_3$|$x_4$|RHS||:-----|:----|:----|:----|:----|:-:||$x_3$|1|1|1|0|4||$x_4$|2|1|0|1|5||$Z$|-3|-5|0|0|0|基变量为$x_3,x_4$；非基变量为$x_1,x_2$。三、5.线性规划的对偶问题是指，原问题（称为原始问题）的目标函数系数向量构成对偶问题的资源向量，原始问题的资源向量构成对偶问题的目标函数系数向量，原始问题的约束系数矩阵转置成为对偶问题的约束系数矩阵，原始问题的约束类型（等式或不等式）决定对偶问题的约束类型（对应），原始问题的变量类型（非负）决定对偶问题的变量类型（对应）。对于上述第4题问题，其对偶问题为：$\minW=4y_1+5y_2$s.t.$\begin{cases}y_1+2y_2\geq3\\y_1+y_2\geq5\\y_1,y_2\geq0\end{cases}$6.强对偶定理指出：若原始问题有最优解，则对偶问题也有最优解，且两者对应的最优目标函数值相等。其在线性规划求解中的应用价值在于：可以不直接求解对偶问题，而是利用原始问题的最优解来得到对偶问题的最优解；当求解对偶问题比原始问题更容易时（例如，约束条件多而变量少），可以利用对偶理论求解；对偶理论也为灵敏度分析提供了理论基础。7.线性规划灵敏度分析的基本思想是：当线性规划模型中的参数（如目标函数系数、约束右端项、约束系数矩阵元素）发生微小变化时，分析这些变化对原最优解（最优值、最优基）的影响。它可以分析目标函数系数$c_i$在什么范围内变化不会改变最优基；约束右端项$b_i$在什么范围内变化时，最优基保持不变，最优解如何变化（通过对偶价格）；增加新的变量或新的约束条件对最优解可能产生的影响。四、8.纯整数规划是指所有决策变量都必须取整数值（0,1,2,...）的整数规划问题。混合整数规划是指决策变量中有一部分必须取整数值，另一部分可以取连续值的整数规划问题。例如：纯整数规划：$\maxZ=3x_1+2x_2$s.t.$x_1+x_2\leq4$,$x_1,x_2\geq0$且均为整数；混合整数规划：$\maxZ=3x_1+2x_2$s.t.$x_1+x_2\leq4$,$x_1\geq0$且为整数,$x_2\geq0$可以为连续值。9.整数规划问题的可行域是其定义域中所有整数解的集合。对于纯整数规划，这个可行域是原始线性规划可行域的一个子集，通常表现为原始可行域中由整数格点构成的区域。对于混合整数规划，其可行域是原始可行域中，对整数变量取整数值、对连续变量取连续值的部分。因此，整数规划的可行域通常比其对应的线性规划松弛问题的可行域小（或相同，当最优解本身就是整数时）。10.分支定界法的基本思想是：首先求解与整数规划问题相应的线性规划松弛问题。若松弛问题的最优解满足整数约束，则该解即为整数规划的最优解。否则，松弛问题的最优解不满足整数约束，选择一个取非整数值的变量进行分支，将原问题分解为若干子问题（通过添加不等式约束来限制该变量的取值范围），然后对每个子问题重复求解其松弛问题或进行评估。通过不断分支和评估（计算目标函数值、更新上界和下界），最终找到整数规划的最优解。剪枝是指在分支过程中，如果一个子问题的松弛解的目标函数值已经严格小于当前已知的整数最优解的目标函数值（上界），或者该子问题不可能包含整数最优解（例如，其搜索分支已经无法满足整数约束），则可以放弃该子问题的进一步搜索，这个过程称为剪枝。五、11.整数规划的松弛问题是指将整数规划问题中的整数约束（要求变量取整数值）去掉后得到的线性规划问题。求解整数规划的松弛问题有以下意义：它是整数规划问题的一个下界（对于最大化问题）；它是分支定界法的基础，即从松弛问题的最优解开始进行搜索；对于某些特殊结构的整数规划问题，其松弛问题的解可能本身就满足整数约束，从而直接得到整数最优解。12.割平面法的基本思想是：从一个不满足整数约束的线性规划松弛问题的最优解出发，构造一个能够“切割掉”松弛解可行域中一部分非整数区域，但又不过于严格地切割掉任何整数可行解的线性不等式（即割平面），然后将这个不等式添加到原松弛问题中，形成一个新的大些的线性规划问题。对新问题进行求解，若得到整数解，则停止；若仍得到非整数解，则重复构造割平面并添加的过程，直到找到整数最优解。割平面法的目的是通过逐步缩小非整数解的可行域，最终逼向整数最优解。13.单纯形法求解线性规划松弛问题是一个迭代过程，从一个初始基本可行解出发，通过判断检验数选择入基变量和出基变量，沿着可行方向（使目标函数改善）移动到相邻的基本可行解，直到检验数全非正为止。其核心在于保证每一步得到的解都是线性规划可行域的顶点，并且目标函数值不断改善或保持最优。而分支定界法求解整数规划问题，是从松弛问题的最优解开始，首先判断其整数可行性。若不可行，则进行分支，将搜索空间划分为多个子问题（对应于对某个非整数变量取值的限制），然后对每个子问题求解其松弛问题或进行评估（比较目标函数值与当前上界），并决定是否剪枝。其核心在于利用整数约束将搜索空间逐步缩小，并通过比较上界和下界来逼近最优整数解。单纯形法是局部搜索方法，每次移动到更好的相邻顶点；分支定界法是全局搜索方法，通过分支和剪枝系统地探索解空间的不同部分。六、14.不唯一。根据单纯形法原理，若所有检验数均为非正数，则当前解为最优解。若最优解中存在取值为零的基变量，这表明存在多个最优解。因为该基变量对应的解是对偶可行基（非基变量检验数非正），当该基变量从零变为非零时，只要保持其他基变量在约束条件的范围内，目标函数值$Z$仍保持不变，从而得到另一组最优解。因此，存在取值为零的基变量是存在多重最优解的标志。15.已知松弛问题的最优解为$x_1=3.6,x_2=2.4,Z=16.8$。取取整值为零的基变量，例如$x_3$（其值为4）。根据Gomory割平面法的构造方法，割平面为：$\sum_{j\inJ}a_{ij}x_j\leqb_i-\lfloorb_i^*\rfloor$，其中$J$是非基变量集合，$a_{ij}$是原约束条件的系数，$b_i$是原约束条件的右端项，$b_i^*$是当前最优解中对应约束条件的RHS值（即松弛变量的值）。对于$x_3$对应的约束$x_1+x_2+x_3=4$，有$a_{11}=1,a_{12}=1,a_{13}=1,b_i=4,b_i^*=4$。将非基变量代入当前最优解：$1\cdot3.6+1\cdot2.4+x_3=4$，即$6+x_3=4$，所以$x_3=4-6=-2$。割平面为：$3.6+2.4\leq4-\lfloor4\rfloor$，即$6\leq4-4$，即$6\leq0$。将此不等式标准化为$-6\geq-4$，即$6-4\leq0$。添加到单纯形表中为：$\begin{array}{ccccccc}x_1&x_2&x_3&x_4&\text{RHS}\\\hline\text{(行号需根据原单纯形表确定)}&-6&0&-4&\leq&0\end{array}$（此行需插入到原单纯形表中适当位置，例如作为新的约束行）。16.多项式时间算法是指求解问题的计算时间随问题规模$n$的增长而最多以多项式函数（如$n^2,n^3$）的速度增长。线性规划（及线性规划松弛问题）存在有效的多项式时间算法，如Khachian的ellipsoid算法和Karmark