运筹学常见面试题目与解答

运筹学常见面试题目与解答考试时间：______分钟总分：______分姓名：______一、选择题1.下列关于线性规划问题的说法中，正确的是：(A)线性规划问题一定存在最优解。(B)线性规划问题的可行域一定是凸多边形。(C)若线性规划问题的可行域有界，则最优解一定在可行域的顶点处取得。(D)线性规划问题的目标函数一定在可行域的内部达到最优。2.在单纯形法中，若某个非基变量的检验数为正，则说明：(A)当前解为唯一最优解。(B)当前解已不是可行解。(C)当前解不是最优解，增加该变量的值有可能使目标函数值增大。(D)当前解不是最优解，但增加该变量的值不会使目标函数值增大。3.若一个线性规划问题存在无穷多最优解，则下列说法中正确的是：(A)目标函数线与某个约束条件线平行。(B)目标函数线与某个约束条件线重合。(C)可行域无界。(D)至少有一个基变量的检验数为零。4.在运输问题的表上作业法中，若在某一步迭代后，存在不止一个检验数为负的最小值组合，则可以选择其中任意一个进行换入变量选择。(A)正确(B)错误5.在整数规划问题中，若用线性规划松驰问题求解得到的最优解中含有非整数分量，则该整数规划问题的最优解：(A)一定与线性规划松驰问题的最优解相同。(B)一定存在，但用线性规划松驰问题的最优解无法直接得到。(C)一定不存在。(D)可能存在，也可能不存在。6.某排队系统的输入过程是泊松流，服务时间服从负指数分布，且服务台数量为n（n≥1），则该排队系统是：(A)M/M/1queue(B)M/M/cqueue(C)M/M/cqueuewithfinitecallingpopulation(D)M/D/cqueue7.在决策分析中，若决策者对未来的自然状态存在一定的不确定性，但可以知道各种自然状态发生的概率，这种决策问题称为：(A)确定型决策(B)风险型决策(C)不确定型决策(D)马尔可夫决策8.用决策树进行风险型决策分析时，通常采用期望值准则进行决策。(A)正确(B)错误9.库存控制模型中，经济订货批量（EOQ）模型主要考虑的是：(A)单位物品的存储成本和订货成本。(B)单位物品的存储成本和缺货成本。(C)单位物品的生产成本和缺货成本。(D)单位物品的生产成本和订货成本。10.下列关于影子价格的描述中，正确的是：(A)影子价格等于对应约束条件的对偶变量值。(B)影子价格表示最优解中某个约束条件的右端项每增加一个单位时，目标函数值的改变量。(C)影子价格只在线性规划问题的最优解处才有意义。(D)影子价格总是大于零。二、简答题1.请简述线性规划问题的标准形式，并说明如何将一个一般形式的线性规划问题转化为标准形式。2.请解释单纯形法中“对偶变量”的含义，并写出对偶问题的基本形式。3.在网络最大流问题中，什么是割集？什么是割集的容量？试述最大流最小割集定理。4.请简述决策分析中“期望收益决策准则”和“期望后悔值决策准则”的区别。5.在库存论中，什么是安全库存？设置安全库存的主要原因是什么？三、综合应用题1.某工厂生产两种产品A和B，需要使用两种资源：劳动力和原材料。生产每单位产品A需要1个劳动力和2个原材料，生产每单位产品B需要3个劳动力和1个原材料。工厂每天可使用的劳动力最多为90个单位，可使用的原材料最多为120个单位。每单位产品A的利润为5元，每单位产品B的利润为4元。工厂希望确定每天生产多少单位产品A和产品B，才能使总利润最大？请建立该问题的线性规划模型，并用单纯形法（或说明单纯形法求解步骤）求解最优解。2.假设一个排队系统为M/M/1queue，顾客到达的速率为每小时平均到达10人（λ=10人/小时），服务速率每小时平均服务12人（μ=12人/小时）。请计算该系统的平均队长（Ls）、平均等待队长（Lq）、平均等待时间（Ws）和平均服务时间（Ws）。若顾客到达速率增加到每小时15人，其他条件不变，重新计算上述指标，并比较变化情况。3.某公司需要决定是否现在投资一个新项目。若投资成功，可获得100万元的收益；若投资失败，则损失50万元。根据市场调研，预测项目投资成功的机会为60%，失败的机会为40%。公司也可以选择不投资，此时收益为零。请用决策树方法分析该公司的决策方案，并选择最优方案（要求分别用期望值准则和后悔值准则进行分析）。试卷答案一、选择题1.(C)2.(C)3.(A)4.(A)5.(B)6.(B)7.(B)8.(A)9.(A)10.(A)二、简答题1.解析思路：线性规划标准形式要求目标函数为最大化形式，约束条件均为等式，所有变量均为非负。转化方法：对于“≤”型约束，加松弛变量；对于“≥”型约束，减去剩余变量；对于目标函数最小化问题，将其转化为最大化问题（取负号）；对于变量无符号限制问题，引入非负变量替换。2.解析思路：对偶变量是线性规划对偶问题的决策变量，其值等于原问题最优解时对应约束条件的右端项（资源）的影子价格。对偶问题的基本形式是：若原问题是MaxZ=Cxs.t.Ax=b,x≥0，则其对偶问题是MinW=ybs.t.yA≥C,y≥0。3.解析思路：割集是分割网络源点与汇点，且包含所有从源点到汇点的路径的最小割集。割集的容量是该割集中所有边的容量之和。最大流最小割集定理指出：网络的最大流量等于该网络中所有割集的容量中的最小值。4.解析思路：期望收益决策准则选择期望收益最大的方案。期望后悔值决策准则首先计算每种自然状态下各方案的后悔值（实际收益与最优收益之差），然后计算各方案的期望后悔值，选择期望后悔值最小的方案。5.解析思路：安全库存是为了应对需求或leadtime的随机波动而额外持有的库存量。设置安全库存的主要原因是降低因缺货造成的损失（如失去销售机会、客户满意度下降等）和延迟交货的风险。三、综合应用题1.解析思路：*模型建立：*决策变量：设x1为产品A的产量，x2为产品B的产量。*目标函数：MaxZ=5x1+4x2*约束条件：*劳动力约束：x1+3x2≤90*原材料约束：2x1+x2≤120*非负约束：x1≥0,x2≥0*单纯形法求解步骤（概述）：*将约束条件转化为等式：x1+3x2+s1=90,2x1+x2+s2=120(s1,s2为松弛变量)*初始单纯形表：以(s1,s2)为基变量，计算检验数。*选择检验数最大的非基变量x1进入基变量，计算最小比值，确定离开基变量的变量（s2离开）。*进行旋转运算，得到新的单纯形表。*重复上述步骤，直到所有检验数小于等于0。*最终得到最优解：x1=30,x2=30,MaxZ=270。2.解析思路：*计算指标（λ=10,μ=12）：*平均到达率/服务率比：ρ=λ/μ=10/12=5/6*平均队长Ls=λ²/μ(μ-λ)=10²/[12(12-10)]=100/24=25/6*平均等待队长Lq=ρ²Ls=(5/6)²*(25/6)=625/216*平均等待时间Ws=Lq/λ=(625/216)/10=625/2160*平均服务时间Ws=1/μ=1/12*计算指标（λ'=15）：*ρ'=λ'/μ=15/12=5/4*Ls'=λ'²/μ(μ-λ')=15²/[12(12-15)]=225/-39=-225/39(注意：此时ρ'>1，系统不稳定，队列无限增长，计算结果无实际意义，但按公式计算Lq'=ρ'²Ls'=(625/16)*(-225/39)=-140625/624)*Lq'=ρ'²Ls'=(625/16)*(-225/39)=-140625/624*Ws'=Lq'/λ'=(-140625/624)/15=-140625/9360*Ws'=1/μ=1/12*比较：当到达率增加，ρ增大，系统负载增加。虽然服务时间不变，但平均队长、等待队长和等待时间都会显著增加（或趋于无穷大），系统性能变差。3.解析思路：*决策树构建：*根节点：投资决策(Invest/NotInvest)*分支1（投资成功）：收益=100万；分支2（投资失败）：收益=-50万。*加上概率：成功概率=0.6，失败概率=0.4。*期望值分析：*投资期望收益=0.6*100+0.4*(-50)=60-20=40万*不投资期望收益=0万*比较两个期望值，40万>0万，按期望值准则应选择投资。*后悔值分析：*构建后悔值矩阵（按列找最大值，再按行找最小值）：*投资成功时，不投资的后悔值=100万；投资失败的后悔值=50万。*不投资成功时，投资的后悔值=0万；不投资失败的后悔值=0万。*后悔值矩阵：*投资列：