《运筹学学》课程考试试题及答案

《运筹学学》课程考试试题及答案一、选择题（每题3分，共30分）1.线性规划模型中，决策变量（）A.只能取整数B.只能取非负实数C.可以取任意实数D.只能取大于零的实数答案：B。在线性规划模型中，决策变量通常代表实际问题中的资源分配、生产数量等，一般要求非负，以符合实际意义。2.若线性规划问题的可行域是无界的，则该问题（）A.一定有最优解B.一定无最优解C.可能有最优解，也可能无最优解D.有唯一最优解答案：C。可行域无界时，目标函数可能有最优解（如目标函数在无界可行域上有最值），也可能无最优解（如目标函数在无界可行域上可以无限增大或减小）。3.对偶问题的对偶是（）A.原问题B.松弛问题C.无可行解问题D.不确定答案：A。根据对偶理论，对偶问题的对偶就是原问题。4.运输问题中，产地个数为m，销地个数为n，则基变量的个数为（）A.m+nB.m+n1C.mnD.m×n答案：B。在运输问题中，基变量的个数等于产地个数与销地个数之和减1。5.动态规划的基本方程是由（）导出的。A.贪心算法B.最优性原理C.分治法D.搜索算法答案：B。动态规划的基本方程是基于最优性原理推导出来的，最优性原理指出一个最优策略的子策略也是最优的。6.对于一个排队系统，顾客到达率为λ，服务率为μ，当（）时，系统可以达到稳定状态。A.λ>μB.λ<μC.λ=μD.与λ和μ无关答案：B。当顾客到达率λ小于服务率μ时，系统中不会出现顾客无限堆积的情况，系统可以达到稳定状态。7.整数规划问题中，若所有决策变量都要求取整数，则称为（）A.纯整数规划B.混合整数规划C.01整数规划D.线性整数规划答案：A。纯整数规划是指所有决策变量都要求取整数的整数规划问题。8.图论中，若一个图中任意两个顶点之间都有边相连，则该图称为（）A.连通图B.完全图C.树D.有向图答案：B。完全图是指图中任意两个顶点之间都有边相连的图。9.目标规划中，若要求恰好达到目标值，则应引入（）A.正偏差变量B.负偏差变量C.正、负偏差变量D.无偏差变量答案：C。在目标规划中，若要求恰好达到目标值，需要同时考虑正偏差变量（超过目标值的部分）和负偏差变量（未达到目标值的部分）。10.线性规划问题的标准型中，约束条件必须是（）A.等式B.不等式C.大于等于不等式D.小于等于不等式答案：A。线性规划问题的标准型中，约束条件必须是等式，且决策变量非负，目标函数求最大化。二、判断题（每题2分，共20分）1.线性规划问题的可行解一定是基本可行解。（）答案：错误。可行解不一定是基本可行解，基本可行解是可行域的顶点，是满足一定条件的可行解。2.对偶问题的最优解对应的目标函数值与原问题的最优解对应的目标函数值相等。（）答案：正确。根据对偶理论，在满足一定条件下，对偶问题的最优解对应的目标函数值与原问题的最优解对应的目标函数值相等。3.运输问题一定有最优解。（）答案：正确。运输问题是一类特殊的线性规划问题，由于其可行域非空且有界，所以一定有最优解。4.动态规划的求解过程是从初始状态开始，逐步向后递推。（）答案：错误。动态规划的求解过程可以是从初始状态开始向后递推（顺推法），也可以是从终止状态开始向前递推（逆推法）。5.排队系统中，顾客的平均等待时间和平均逗留时间相等。（）答案：错误。顾客的平均逗留时间等于平均等待时间加上平均服务时间，二者一般不相等。6.整数规划问题的最优解一定是其对应的线性规划问题的最优解。（）答案：错误。整数规划问题的可行域是其对应的线性规划问题可行域的子集，整数规划的最优解不一定是线性规划的最优解。7.图论中，树是一种无回路的连通图。（）答案：正确。树的定义就是无回路的连通图。8.目标规划中，优先级高的目标总是优先考虑。（）答案：正确。目标规划中，按照优先级的高低依次考虑各个目标，优先级高的目标优先满足。9.线性规划问题的最优解一定在可行域的顶点上。（）答案：正确。对于线性规划问题，若存在最优解，则最优解一定在可行域的顶点上。10.若一个线性规划问题有可行解，则一定有最优解。（）答案：错误。线性规划问题有可行解时，可能无最优解，如可行域无界且目标函数无最值的情况。三、计算题（每题15分，共30分）1.求解线性规划问题：\(\maxz=3x_1+2x_2\)\(\begin{cases}x_1+x_2\leq6\\x_1+2x_2\leq8\\x_1,x_2\geq0\end{cases}\)解：首先，将不等式约束化为等式约束，引入松弛变量\(x_3\)和\(x_4\)，得到标准型：\(\maxz=3x_1+2x_2+0x_3+0x_4\)\(\begin{cases}x_1+x_2+x_3=6\\x_1+2x_2+x_4=8\\x_1,x_2,x_3,x_4\geq0\end{cases}\)列出初始单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|1|1|0|6||1|2|0|1|8||3|2|0|0|0|选择\(x_1\)作为进基变量，计算\(\theta\)值：\(\theta_1=\frac{6}{1}=6\)，\(\theta_2=\frac{8}{1}=8\)，\(\theta=\min\{6,8\}=6\)，所以\(x_3\)为出基变量。进行初等行变换，得到新的单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|1|1|0|6||0|1|1|1|2||0|1|3|0|18|选择\(x_2\)作为进基变量，计算\(\theta\)值：\(\theta_1=\frac{6}{1}=6\)，\(\theta_2=\frac{2}{1}=2\)，\(\theta=\min\{6,2\}=2\)，所以\(x_4\)为出基变量。进行初等行变换，得到最终单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|0|2|1|4||0|1|1|1|2||0|0|4|1|20|此时，所有检验数均非负，得到最优解\(x_1=4\)，\(x_2=2\)，最优值\(z=20\)。2.某运输问题的产销平衡表和单位运价表如下：|产地|销地1|销地2|销地3|产量||||||||产地1|3|1|7|5||产地2|2|4|5|3||销量|2|3|3||用最小元素法求初始调运方案，并计算总运费。解：（1）用最小元素法求初始调运方案：首先，单位运价最小的是\(c_{12}=1\)，将产地1的3个单位产品运往销地2，此时销地2需求满足，产地1剩余产量\(53=2\)。接着，剩下的单位运价中最小的是\(c_{21}=2\)，将产地2的2个单位产品运往销地1，此时销地1需求满足，产地2剩余产量\(32=1\)。然后，最小的单位运价是\(c_{23}=5\)，将产地2的1个单位产品运往销地3，此时产地2产量用完，销地3还需\(31=2\)。最后，将产地1的2个单位产品运往销地3，此时所有产地的产量和销地的需求都得到满足。初始调运方案如下：|产地|销地1|销地2|销地3|产量||||||||产地1|0|3|2|5||产地2|2|0|1|3||销量|2|3|3||（2）计算总运费：总运费\(Z=3\times0+1\times3+7\times2+2\times2+4\times0+5\times1\)\(=0+3+14+4+0+5=26\)四、应用题（20分）某工厂生产甲、乙两种产品，生产甲产品每件需用A原料3千克、B原料2千克；生产乙产品每件需用A原料1千克、B原料3千克。已知A原料每天有12千克，B原料每天有15千克。甲产品每件利润为5元，乙产品每件利润为4元。问该工厂每天应生产甲、乙产品各多少件，才能使利润最大？解：设该工厂每天生产甲产品\(x_1\)件，生产乙产品\(x_2\)件。（1）建立数学模型：目标函数：\(\maxz=5x_1+4x_2\)约束条件：\(\begin{cases}3x_1+x_2\leq12\\2x_1+3x_2\leq15\\x_1,x_2\geq0\end{cases}\)（2）将不等式约束化为等式约束，引入松弛变量\(x_3\)和\(x_4\)，得到标准型：\(\maxz=5x_1+4x_2+0x_3+0x_4\)\(\begin{cases}3x_1+x_2+x_3=12\\2x_1+3x_2+x_4=15\\x_1,x_2,x_3,x_4\geq0\end{cases}\)（3）列出初始单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||3|1|1|0|12||2|3|0|1|15||5|4|0|0|0|选择\(x_1\)作为进基变量，计算\(\theta\)值：\(\theta_1=\frac{12}{3}=4\)，\(\theta_2=\frac{15}{2}=7.5\)，\(\theta=\min\{4,7.5\}=4\)，所以\(x_3\)为出基变量。进行初等行变换，得到新的单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|\(\frac{1}{3}\)|\(\frac{1}{3}\)|0|4||0|\(\frac{7}{3}\)|\(\frac{2}{3}\)|1|7||0|\(\frac{7}{3}\)|\(\frac{5}{3}\)|0|20|选择\(x_2\)作为进基变量，计算\(\theta\)值：\(\theta_1=\frac{4}{\frac{1}{3}}=12\)，\(\theta_2=\frac{7}{\frac{7}{3}}=3\)，\(\theta=\min\{12,3\}=3\)，所以\(x_4\)为出基变量。进行初等行变换，得到最终单纯形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)|||