天大2018年12月考试《运筹学》离线作业考核试题【标准答案】

天大2018年12月考试《运筹学》离线作业考核试题【标准答案】一、单选题1.线性规划具有无界解是指（）A.可行解集合无界B.有相同的最小比值C.存在某个检验数λj＞0且aik≤0（i=1，2，...，m）D.最优表中所有非基变量的检验数非零

答案：C

解析：线性规划具有无界解的充分必要条件是：存在某个检验数λj＞0且aik≤0（i=1，2，...，m），这意味着目标函数可以沿着某个方向无限增大，所以可行域是无界的，选C。

2.关于线性规划的最优解判定，说法不正确的是（）A.如果是求最小化值，则所有检验数都小于等于零的基可行解是最优解B.如果是求最大化值，则所有检验数都大于等于零的基可行解是最优解C.求最大化值时，如果所有检验数都小于等于零，则有唯一最优解D.如果运算到某步时，存在某个变量的检验数大于零，且该变量所对应约束方程中的系数列向量均小于等于零，则存在无界解

答案：C

解析：求最大化值时，如果所有检验数都小于等于零，可能有无穷多最优解，而不是唯一最优解，C说法错误。A、B选项是正确的最优解判定条件，D选项也是无界解的判定条件，所以本题选C。

3.线性规划可行域的顶点一定是（）A.基本可行解B.非基本解C.非可行解D.最优解

答案：A

解析：线性规划可行域的顶点对应着基可行解，这是线性规划的一个重要性质，选A。

4.线性规划的图解法适用于（）A.只含有一个变量的线性规划问题B.只含有2～3个变量的线性规划问题C.含有多个变量的线性规划问题D.任何情况

答案：B

解析：线性规划的图解法直观地适用于只含有2～3个变量的线性规划问题，通过在平面直角坐标系中绘制可行域和目标函数等值线来求解，对于多个变量难以用图形表示，所以选B。

5.对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）A.b列元素不小于零B.检验数都大于零C.检验数都不小于零D.检验数都不大于零

答案：D

解析：对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中检验数都不大于零，这是对偶单纯形法的基本要求，选D。

6.下列说法正确的是（）A.线性规划问题的基本解对应可行域的顶点B.若线性规划问题的可行域可以伸展到无限，则该问题一定有最优解C.线性规划问题的最优解一定可以在可行域的顶点上达到D.单纯形法求解线性规划问题时每换基迭代一次必使目标函数值下降一次

答案：C

解析：线性规划问题的最优解一定可以在可行域的顶点上达到，这是线性规划的基本定理之一，C正确。基本解不一定对应可行域顶点，A错误；可行域无限时不一定有最优解，B错误；单纯形法换基迭代目标函数值不一定下降，D错误。所以选C。

7.求解纯整数规划的方法是（）A.割平面法B.分枝定界法C.匈牙利法D.隐枚举法

答案：B

解析：求解纯整数规划的常用方法是分枝定界法，通过不断分枝和定界来逐步逼近最优整数解，选B。割平面法主要用于求解混合整数规划，匈牙利法用于指派问题，隐枚举法用于求解0-1整数规划等。

8.对于目标函数极大值型的线性规划问题，用单纯形法求解时，当基变量检验数（）时，当前解为最优解。A.＜0B.＞0C.=0D.≥0

答案：C

解析：对于目标函数极大值型的线性规划问题，用单纯形法求解时，当基变量检验数=0时，当前解为最优解，这是单纯形法最优解的判定条件，选C。

9.用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）A.原解B.上界C.下界D.最优解

答案：C

解析：用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界，通过不断改进可行解来逼近最优解，选C。

10.线性规划问题的可行解（）是基本可行解。A.一定B.一定不C.不一定D.无法判断

答案：C

解析：线性规划问题的可行解不一定是基本可行解，基本可行解是可行解中的特殊情况，可行解包含了基本可行解以及其他满足约束条件的解，选C。

11.设线性规划的约束条件为则基本可行解为（）A.(0,0,4,3)B.(3,4,0,0)C.(2,0,1,0)D.(3,0,4,0)

答案：C

解析：将选项代入约束条件进行验证，满足所有约束条件的就是基本可行解。选项A不满足\(x_1+2x_2≤8\)；选项B不满足\(2x_1+x_2≤10\)；选项D不满足\(x_1≥0\)，\(x_2≥0\)等约束，只有选项C满足所有约束条件，所以选C。

12.关于线性规划的原问题和对偶问题，下列说法正确的是（）A.若原问题为无界解，则对偶问题也为无界解B.若原问题无可行解，其对偶问题具有无界解或无可行解C.若原问题存在可行解，其对偶问题必存在可行解D.若原问题存在可行解，其对偶问题无可行解

答案：B

解析：原问题与对偶问题的关系中，若原问题无可行解，其对偶问题具有无界解或无可行解，B正确。原问题无界解时，对偶问题无可行解，A错误；原问题有可行解时，对偶问题不一定有可行解，C、D错误。所以选B。

13.对偶单纯形法的迭代是从（）开始的。A.正则解B.最优解C.可行解D.基本解

答案：D

解析：对偶单纯形法的迭代是从基本解开始的，通过不断调整基本解来找到最优解，选D。

14.在线性规划模型中，没有非负约束的变量称为（）A.多余变量B.松弛变量C.自由变量D.人工变量

答案：C

解析：在线性规划模型中，没有非负约束的变量称为自由变量，选C。多余变量一般指在模型中不影响目标函数和约束条件的变量；松弛变量是为了将不等式约束转化为等式约束而引入的非负变量；人工变量是在求解线性规划时为了构造初始可行基而引入的变量。

15.线性规划的标准形有如下特征（）A.目标函数求极小值B.右端常数非负C.变量非负D.约束条件为等式约束，且右端常数非负

答案：D

解析：线性规划的标准形特征是约束条件为等式约束，且右端常数非负，变量非负，目标函数求极大值，选D。

二、判断题1.线性规划问题的每一个基本解对应可行域的一个顶点。（）答案：×

解析：线性规划问题的基本解不一定对应可行域的顶点，只有基本可行解才对应可行域的顶点，所以该说法错误。

2.若线性规划无最优解则其可行域无界。（）答案：×

解析：线性规划无最优解可能是可行域无界，也可能是问题无可行解，所以该说法错误。

3.可行解集非空时，则在极点上至少有一点达到最优值。（）答案：×

解析：可行解集非空时，最优值不一定在极点上达到，也可能在可行域的其他点或边界上达到，所以该说法错误。

4.求最大值的线性规划问题中，人工变量在目标函数中的系数都为零。（）答案：×

解析：求最大值的线性规划问题中，人工变量在目标函数中的系数都为-M（M为充分大的正数），而不是零，所以该说法错误。

5.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（）答案：√

解析：当人工变量变为非基变量后，其对后续计算已无影响，可以从单纯形表中删除，该说法正确。

6.原问题求最大值，其对偶问题也求最大值。（）答案：×

解析：原问题求最大值，其对偶问题求最小值，原问题与对偶问题在目标函数的最值类型上是相反的，所以该说法错误。

7.对偶问题有可行解，则原问题也有可行解。（）答案：×

解析：对偶问题有可行解时，原问题不一定有可行解，它们之间的可行解情况没有必然的对应关系，所以该说法错误。

8.匈牙利法只能用于解决平衡分配问题。（）答案：√

解析：匈牙利法主要用于解决平衡分配问题，通过对效率矩阵进行变换来找到最优分配方案，该说法正确。

9.整数规划的最优解是先求相应的线性规划的最优解然后取整得到。（）答案：×

解析：整数规划的最优解不能简单地通过求相应线性规划的最优解然后取整得到，因为取整后的解不一定是整数规划的可行解或最优解，整数规划需要专门的方法求解，所以该说法错误。

10.用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取一个作为下界值，再进行比较剪枝。（）答案：×

解析：用分枝定界法求解极大化整数规划问题时，应取所有可行解中的最大目标函数值作为下界值，再进行比较剪枝，而不是任取一个，所以该说法错误。

三、解答题1.用图解法求解线性规划问题：答案：首先，将约束条件转化为等式方程：\(x_1+x_2=3\)，\(x_1-x_2=1\)，\(x_1=0\)，\(x_2=0\)。然后，画出可行域：对于\(x_1+x_2≤3\)，取直线\(x_1+x_2=3\)，可行域在直线下方；对于\(x_1-x_2≤1\)，取直线\(x_1-x_2=1\)，可行域在直线下方；\(x_1≥0\)，\(x_2≥0\)表示可行域在第一象限。可行域是一个四边形区域，顶点分别为\((0,0)\)，\((1,0)\)，\((2,1)\)，\((0,3)\)。接下来，求目标函数\(z=2x_1+3x_2\)在可行域顶点处的值：在\((0,0)\)处，\(z=2×0+3×0=0\)；在\((1,0)\)处，\(z=2×1+3×0=2\)；在\((2,1)\)处，\(z=2×2+3×1=7\)；在\((0,3)\)处，\(z=2×0+3×3=9\)。比较可得，当\(x_1=0\)，\(x_2=3\)时，目标函数取得最大值\(9\)。

解析：通过将约束条件转化为等式，画出可行域，再计算目标函数在可行域顶点处的值，从而找到最优解。这是线性规划图解法的基本步骤，通过直观的图形展示，能清晰地看到可行域的范围以及目标函数在可行域内的变化情况，进而确定最优解。

2.已知线性规划问题用单纯形法求解该问题。答案：首先，将线性规划问题化为标准形：引入松弛变量\(x_3\)，\(x_4\)，\(x_5\)，得到\(\maxz=3x_1+5x_2\)\(\begin{cases}x_1+2x_2+x_3=8\\2x_1+x_2+x_4=10\\x_1+x_2+x_5=6\\x_1,x_2,x_3,x_4,x_5≥0\end{cases}\)列出初始单纯形表：|基变量|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(x_5\)|常数项||---|---|---|---|---|---|---||\(x_3\)|1|2|1|0|0|8||\(x_4\)|2|1|0|1|0|10||\(x_5\)|1|1|0|0|1|6||\(z\)|-3|-5|0|0|0|0|计算检验数：\(\lambda_1=-3\)，\(\lambda_2=-5\)，\(\lambda_3=0\)，\(\lambda_4=0\)，\(\lambda_5=0\)。因为\(\lambda_1\)和\(\lambda_2\)为负，选择\(x_2\)进基。计算最小比值：\(\theta_1=\frac{8}{2}=4\)，\(\theta_2=\frac{10}{1}=10\)，\(\theta_3=\frac{6}{1}=6\)，最小比值为4，所以\(x_3\)出基。进行换基迭代，得到新的单纯形表：|基变量|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(x_5\)|常数项||---|---|---|---|---|---|---||\(x_2\)|\(\frac{1}{2}\)|1|\(\frac{1}{2}\)|0|0|4||\(x_4\)|\(\frac{3}{2}\)|0|-\(\frac{1}{2}\)|1|0|6||\(x_5\)|\(\frac{1}{2}\)|0|-\(\frac{1}{2}\)|0|1|2||\(z\)|-\(\frac{1}{2}\)|0