运筹学试题及答案

运筹学试题及答案一、选择题（每题2分，共20分）1.在线性规划问题中，若可行解区域为空集，则该问题（）A.有唯一最优解B.有无穷多最优解C.无可行解D.有无界最优解2.下列哪项不是运筹学的基本特征？（）A.系统性B.最优性C.随机性D.实践性3.对于运输问题，以下说法正确的是（）A.运输问题一定是平衡的B.运输问题一定有最优解C.运输问题的基变量个数等于m+n-1D.运输问题可以用单纯形法求解4.动态规划的核心思想是（）A.分治策略B.贪心算法C.最优性原理D.回溯法5.在排队论中，M/M/1模型表示（）A.到达过程为泊松过程，服务时间为指数分布，1个服务台B.到达过程为马尔科夫过程，服务时间为指数分布，1个服务台C.到达过程为泊松过程，服务时间为指数分布，多个服务台D.到达过程为泊松过程，服务时间为马尔科夫过程，1个服务台6.下列哪项不属于图的最小生成树算法？（）A.Prim算法B.Kruskal算法C.Dijkstra算法D.Boruvka算法7.在整数规划中，对于纯整数规划问题，以下说法正确的是（）A.可通过四舍五入得到最优解B.可通过取整得到最优解C.可通过割平面法求解D.可通过单纯形法直接求解8.对于无向图G=(V,E)，若|E|=|V|-1，则G（）A.一定是树B.一定是连通图C.可能不连通D.一定没有环9.在库存管理中，EOQ模型的基本假设不包括（）A.需求率恒定B.不允许缺货C.订货提前期为零D.库存持有成本与库存量成正比10.在对策论中，对于零和博弈，以下说法正确的是（）A.一方的收益等于另一方的损失B.双方的收益之和为零C.一定存在纳什均衡D.可以用线性规划求解二、填空题（每题2分，共20分）1.线性规划问题的标准形式要求所有变量取____值，约束条件为等式。2.在单纯形法中，检验数全部____时，当前解为最优解。3.运输问题中，当基变量个数为m+n-1时，称为____。4.动态规划中，用来表示决策过程不同阶段的量称为____。5.排队系统中，顾客到达服务机构的时间间隔服从____分布时，称为泊松到达过程。6.图论中，从一个顶点到另一个顶点的路径中，边数最少的路径称为____。7.在整数规划中，如果要求部分变量取整数值，其余变量可取任意实数值，则称为____整数规划。8.在网络计划技术中，不影响整个项目完成时间的活动称为____。9.库存管理中，在允许缺货的情况下，最优订货批量EOQ与不允许缺货时的EOQ相比，会____。10.在对策论中，如果博弈双方都知道对方的策略且都选择最优应对策略，则称为____。三、计算题（每题10分，共30分）1.某工厂生产A、B两种产品，每吨产品消耗的原材料、设备台时和利润如下表所示：|产品|原材料(吨)|设备台时(小时)|利润(万元/吨)||------|------------|----------------|---------------||A|2|3|4||B|4|2|5|工厂每天可使用的原材料为20吨，设备台时为24小时。问：如何安排生产计划使利润最大？（要求：建立数学模型并用单纯形法求解）2.某公司有3个工厂，向4个仓库运输产品，各工厂的供应量、各仓库的需求量以及单位运输成本如下表所示（单位：百元/吨）：|工厂\仓库|W1|W2|W3|W4|供应量||----------|----|----|----|----|--------||F1|3|6|5|4|50||F2|7|4|8|6|60||F3|5|3|7|9|40||需求量|30|50|40|30||试用最小元素法求初始可行解，并计算总运输成本。3.某商店销售某种商品，根据历史数据，每天的需求量服从泊松分布，均值为5件。商店每天早上进货，当天销售不完的商品第二天全部报废。每件商品的进价为10元，售价为20元。问：该商店每天应进货多少件才能使期望利润最大？四、应用题（15分）某物流公司需要在5个城市之间建立配送网络，各城市之间的距离（公里）如下表所示：|城市\城市|A|B|C|D|E||----------|----|----|----|----|----||A|0|12|25|30|40||B|12|0|18|22|35||C|25|18|0|15|28||D|30|22|15|0|20||E|40|35|28|20|0|要求：(1)用Prim算法求出该配送网络的最小生成树；(2)如果需要在城市A、B、C、D、E之间建立一条巡回路线，使得每个城市恰好访问一次且总距离最短，请用动态规划方法求解最短哈密尔顿回路。五、案例分析题（15分）某医院急诊科面临患者排队等待服务的问题。根据统计数据，患者到达急诊科的时间间隔服从均值为10分钟的指数分布，医生服务时间服从均值为8分钟的指数分布，目前只有1名医生值班。该医院正在考虑两种改进方案：方案一：增加1名医生，使服务台数变为2，但每增加一名医生每天需要额外支付500元成本。方案二：引进一套新的医疗设备，可以将医生的服务时间减少到均值为6分钟，但设备每天需要折旧成本300元。假设医院每天运营24小时，患者等待的单位时间成本为每人每小时50元，医院每天接待患者带来的平均收入为每人100元。请通过运筹学方法分析：(1)当前情况下（1名医生）的平均队长、平均等待时间和系统中的平均患者数；(2)比较两种改进方案下的系统性能指标和每天的总成本（包括等待成本和额外成本）；(3)为该医院提出最优决策建议，并说明理由。标准答案及解析一、选择题1.C【解析】在线性规划问题中，若可行解区域为空集，表示不存在满足所有约束条件的解，因此该问题无可行解。选项A、B、D都是在存在可行解情况下的结果。2.C【解析】运筹学的基本特征包括系统性、最优性和实践性，而随机性不是运筹学的基本特征，虽然某些运筹学模型会考虑随机因素。3.C【解析】运输问题不一定是平衡的，当总供应量不等于总需求量时，需要添加虚拟的供应点或需求点使其平衡；运输问题不一定有最优解，可能存在无界解的情况；运输问题可以用单纯形法求解，但通常使用专门的方法如位势法；对于m个供应点和n个需求点的运输问题，基变量个数为m+n-1。4.C【解析】动态规划的核心思想是最优性原理，即一个最优策略具有这样的性质：无论初始状态和初始决策如何，对于前面的决策所形成的状态而言，余下的决策必须构成最优策略。选项A、B、D是其他算法的核心思想。5.A【解析】在排队论中，M/M/1模型表示到达过程为泊松过程（M代表Markov，即无记忆性），服务时间为指数分布，1个服务台。第一个M表示到达过程服从泊松分布，第二个M表示服务时间服从指数分布，1表示服务台数量。6.C【解析】Prim算法、Kruskal算法和Boruvka算法都是求最小生成树的经典算法，而Dijkstra算法是求单源最短路径的算法。7.C【解析】纯整数规划问题要求所有变量都取整数值，不能通过简单的四舍五入或取整得到最优解，需要使用专门的算法如割平面法、分支定界法等求解。单纯形法不能直接用于求解整数规划问题。8.C【解析】对于无向图G=(V,E)，若|E|=|V|-1，则G可能不连通，只有当G连通时，G才是树。例如，由两个不连通的树组成的图满足|E|=|V|-1，但不是连通图。9.D【解析】EOQ模型的基本假设包括需求率恒定、不允许缺货、订货提前期为零等，但库存持有成本与库存量成正比不是基本假设，而是库存持有成本的计算方式。10.A【解析】在零和博弈中，一方的收益等于另一方的损失，双方的收益之和为零。选项B描述的是零和博弈的特征，但选项A更准确地描述了零和博弈的本质；零和博弈不一定存在纳什均衡；零和博弈可以用线性规划求解，但不是所有博弈都可以。二、填空题1.非负【解析】线性规划问题的标准形式要求所有变量取非负值，约束条件为等式，目标函数为最大化或最小化。2.非负【解析】在单纯形法中，当所有检验数非负时，当前解为最优解。对于最大化问题，检验数非负表示无法通过增加非基变量的值来改进目标函数；对于最小化问题，检验数非负表示无法通过减少非基变量的值来改进目标函数。3.非退化【解析】在运输问题中，当基变量个数为m+n-1时，称为非退化问题；当基变量个数小于m+n-1时，称为退化问题。退化问题可能导致循环，需要特殊处理。4.阶段【解析】在动态规划中，用来表示决策过程不同阶段的量称为阶段。动态规划将问题分解为若干个阶段，每个阶段需要做出决策，并形成状态转移。5.指数【解析】在排队系统中，如果顾客到达服务机构的时间间隔服从指数分布，则称为泊松到达过程。这是因为指数分布的无记忆性使得到达过程具有马尔科夫性质。6.最短路径【解析】图论中，从一个顶点到另一个顶点的路径中，边数最少的路径称为最短路径。最短路径问题可以通过Dijkstra算法、Floyd算法等方法求解。7.混合【解析】在整数规划中，如果要求部分变量取整数值，其余变量可取任意实数值，则称为混合整数规划。当所有变量都要求取整数值时，称为纯整数规划。8.关键活动【解析】在网络计划技术中，不影响整个项目完成时间的活动称为关键活动。关键活动的总时差为零，任何延迟都会导致整个项目延迟。9.减少【解析】在库存管理中，当允许缺货时，最优订货批量EOQ与不允许缺货时的EOQ相比会减少。这是因为允许缺货可以降低库存持有成本，从而减少最优订货量。10.完全信息博弈【解析】在对策论中，如果博弈双方都知道对方的策略且都选择最优应对策略，则称为完全信息博弈。如果双方不知道对方的策略，则称为不完全信息博弈。三、计算题1.【解析】(1)建立数学模型：设生产A产品x₁吨，B产品x₂吨。目标函数：maxZ=4x₁+5x₂约束条件：2x₁+4x₂≤20（原材料约束）3x₁+2x₂≤24（设备台时约束）x₁,x₂≥0（非负约束）(2)将问题转化为标准形式：引入松弛变量x₃,x₄：目标函数：maxZ=4x₁+5x₂+0x₃+0x₄约束条件：2x₁+4x₂+x₃=203x₁+2x₂+x₄=24x₁,x₂,x₃,x₄≥0(3)列出初始单纯形表：|基变量|x₁|x₂|x₃|x₄|解||--------|----|----|----|----|----||x₃|2|4|1|0|20||x₄|3|2|0|1|24||Z|-4|-5|0|0|0|(4)选择x₂为入基变量（检验数最小），计算θ值：θ₁=20/4=5θ₂=24/2=12选择θ₁对应的行，x₃为出基变量。(5)进行行变换，使x₂的列变为单位向量：第一行除以4：|基变量|x₁|x₂|x₃|x₄|解||--------|----|----|----|----|----||x₂|0.5|1|0.25|0|5||x₄|2|0|-0.5|1|14||Z|-1.5|0|1.25|0|25|(6)检验行仍有负数，x₁为入基变量，计算θ值：θ₁=5/0.5=10θ₂=14/2=7选择θ₂对应的行，x₄为出基变量。(7)进行行变换，使x₁的列变为单位向量：第二行除以2：|基变量|x₁|x₂|x₃|x₄|解||--------|----|----|----|----|----||x₂|0|1|0.375|-0.25|1.5||x₁|1|0|-0.25|0.5|7||Z|0|0|0.625|0.75|36|(8)检验行无负数，得到最优解：x₁=7，x₂=1.5，Z=36因此，最优生产计划是每天生产A产品7吨，B产品1.5吨，最大利润为36万元。2.【解析】(1)用最小元素法求初始可行解：从表格中找出最小运输成本3，对应F3到W2的运输，取min(40,50)=40，即F3向W2运输40吨，F3供应量用完，W2需求量剩余10。更新表格：|工厂\仓库|W1|W2|W3|W4|供应量||----------|----|----|----|----|--------||F1|3|6|5|4|50||F2|7|4|8|6|60||F3|5|3|7|9|40||需求量|30|10|40|30||找出剩余最小运输成本3，对应F1到W1的运输，取min(50,30)=30，即F1向W1运输30吨，W1需求量满足，F1剩余供应量20。更新表格：|工厂\仓库|W1|W2|W3|W4|供应量||----------|----|----|----|----|--------||F1|3|6|5|4|20||F2|7|4|8|6|60||F3|5|3|7|9|0||需求量|0|10|40|30||找出剩余最小运输成本4，对应F2到W2的运输，取min(60,10)=10，即F2向W2运输10吨，W2需求量满足，F2剩余供应量50。更新表格：|工厂\仓库|W1|W2|W3|W4|供应量||----------|----|----|----|----|--------||F1|3|6|5|4|20||F2|7|4|8|6|50||F3|5|3|7|9|0||需求量|0|0|40|30||找出剩余最小运输成本4，对应F1到W4的运输，取min(20,30)=20，即F1向W4运输20吨，F1供应量用完，W4需求量剩余10。更新表格：|工厂\仓库|W1|W2|W3|W4|供应量||----------|----|----|----|----|--------||F1|3|6|5|4|0||F2|7|4|8|6|50||F3|5|3|7|9|0||需求量|0|0|40|10||F2向W3运输40吨，向W4运输10吨，完成所有运输。初始可行解为：F1→W1:30吨F1→W4:20吨F2→W2:10吨F2→W3:40吨F2→W4:10吨F3→W2:40吨(2)计算总运输成本：总成本=30×3+20×4+10×4+40×8+10×6+40×3=90+80+40+320+60+120=710（百元）=71000元3.【解析】这是一个报童问题，属于单周期库存模型。设每天进货量为Q件，需求量为D件，服从泊松分布，均值为5件。每件商品的进价为10元，售价为20元，因此每件商品的利润为10元，缺货损失为10元（因为缺货意味着失去一次销售机会）。最优进货量Q满足：P(D≤Q)≥Cu/(Cu+Co)其中，Cu为每件商品的利润（10元），Co为每件商品的缺货损失（10元）。因此，P(D≤Q)≥10/(10+10)=0.5查泊松分布表，当λ=5时：P(D≤4)=0.4405P(D≤5)=0.6160因为P(D≤5)>0.5>P(D≤4)，所以最优进货量Q=5件。验证：当Q=4时，P(D≤4)=0.4405<0.5当Q=5时，P(D≤5)=0.6160>0.5因此，该商店每天应进货5件才能使期望利润最大。四、应用题【解析】(1)用Prim算法求最小生成树：①选择顶点A作为起始点，与A相连的边有AB(12),AC(25),AD(30),AE(40)，其中最小的是AB(12)，选择边AB，顶点B加入树中。②当前树包含顶点A和B，与树相连的边有AC(25),AD(30),AE(40),BC(18)，其中最小的是BC(18)，选择边BC，顶点C加入树中。③当前树包含顶点A、B和C，与树相连的边有AD(30),AE(40),CD(15)，其中最小的是CD(15)，选择边CD，顶点D加入树中。④当前树包含顶点A、B、C和D，与树相连的边有AE(40)，选择边AE，顶点E加入树中。因此，最小生成树由边AB、BC、CD、AE组成，总距离为12+18+15+40=85公里。(2)用动态规划方法求解最短哈密尔顿回路：这是一个旅行商问题(TSP)，可以用动态规划方法求解。定义状态为(S,j)，表示从顶点1出发，经过集合S中的所有顶点，最后到达顶点j的最短路径长度。设顶点编号为：A=1,B=2,C=3,D=4,E=5。初始化：d(i,j)为顶点i到顶点j的距离。C({i},i)=0，对于所有i。递推关系：C(S,j)=min{C(S-{j},k)+d(k,j)}，其中k∈S-{j}最终解：min{C({1,2,3,4,5},j)+d(j,1)}，其中j=2,3,4,5计算过程：①集合大小为2：C({1,2},2)=C({1},1)+d(1,2)=0+12=12C({1,3},3)=C({1},1)+d(1,3)=0+25=25C({1,4},4)=C({1},1)+d(1,4)=0+30=30C({1,5},5)=C({1},1)+d(1,5)=0+40=40类似地，可以计算其他集合大小为2的状态。②集合大小为3：C({1,2,3},3)=min{C({1,2},2)+d(2,3),C({1,3},3)+d(3,2)}=min{12+18,25+18}=min{30,43}=30C({1,2,4},4)=min{C({1,2},2)+d(2,4),C({1,4},4)+d(4,2)}=min{12+22,30+22}=min{34,52}=34C({1,2,5},5)=min{C({1,2},2)+d(2,5),C({1,5},5)+d(5,2)}=min{12+35,40+35}=min{47,75}=47类似地，可以计算其他集合大小为3的状态。③集合大小为4：C({1,2,3,4},4)=min{C({1,2,3},3)+d(3,4),C({1,2,4},4)+d(4,3),C({1,3,4},4)+d(4,2)}=min{30+15,34+15,45+15}=min{45,49,60}=45C({1,2,3,5},5)=min{C({1,2,3},3)+d(3,5),C({1,2,5},5)+d(5,3),C({1,3,5},5)+d(5,2)}=min{30+28,47+28,65+28}=min{58,75,93}=58类似地，可以计算其他集合大小为4的状态。④集合大小为5：C({1,2,3,4,5},5)=min{C({1,2,3,4},4)+d(4,5),C({1,2,3,5},5)+d(5,4),C({1,2,4,5},5)+d(5,3),C({1,3,4,5},5)+d(5,2)}=min{45+20,58+20,60+20,70+20}=min{65,78,80,90}=65最终解：min{C({1,2,3,4,5},2)+d(2,1),C({1,2,3,4,5},3)+d(3,1),C({1,2,3,4,5},4)+d(4,1),C({1,2,3,4,5},5)+d(5,1)}=min{65+12,70+25,75+30,65+40}=min{77,95,105,105}=77因此，最短哈密尔顿回路的长度为77公里。回路线可以通过回溯得到：1→2→3→4→5→1。五、案例分析题【解析】(1)当前情况下（1名医生）的系统性能指标：这是一个M/M/1排队模型，其中：-到达率λ=1/10=0.1（患者/分钟）-服务率μ=1/8=0.125（患者/分钟）系统利用率ρ=λ/μ=0.1/0.125=0.8系统中的平均患者数L=ρ/(1-ρ)=0.8/(1-0.8)=4（人）队列中的平均患者数Lq=ρ²/(1-ρ)=0.8²/(1-0.8)=3.2（人）患者在系统中的平均时间W=1/(μ-λ)=1/(0.125-0.1)=40（分钟）患者在队列中的平均等待时间Wq=ρ/(μ-λ)=0.8/(0.125-0.1)=32（分钟）(2)比较两种改进方案下的系统性能指标和每天的总成本：方案一：增加1名医生，服务台数变为2（M/M/2模型）到达率λ=0.1（患者/分钟）每个服务台的服务率μ=0.125（患者/分钟）服务台数c=2系统利用率ρ=λ/(cμ)=0.1/(2×0.125)=0.4计算P₀（系统中没有患者的概率）：P₀=[1+(cρ)¹/1!+(cρ)²/(2!(1-ρ))]⁻¹=[1+0.8/1!+0.8²/(2!(1-0.4))]⁻¹=[1+0.8+0.64/(2×0.6)]⁻¹=[1+0.8+0.533]⁻¹=2.333⁻¹=0.4286队列中的平均患者数Lq=(cρ)^(c+1)P₀/[c!(1-ρ)²]=0.8³×0.4286/[2!(1-0.4)²]=0.512×0.4286/[2×0.36]=0.2196/0.72=0.305（人）系统中的平均患者数L=Lq+cρ=0.305+2×0.4=1.105（人）患者