2026年运筹学考试b试卷及答案

2026年运筹学考试b试卷及答案一、单项选择题（每题3分，共15分）1.线性规划问题中，若原问题存在可行解但无界，则其对偶问题（）。A.无可行解B.有可行解且最优值与原问题相等C.可能有可行解也可能无可行解D.有可行解但无界2.整数规划问题中，分支定界法的“定界”步骤是指（）。A.对松弛问题的最优解进行上下界估计B.对原问题的目标函数值设定可行范围C.在分支后的子问题中确定新的约束条件D.通过割平面法缩小可行域3.动态规划中，状态转移方程的建立需要满足（）。A.无后效性B.递推性C.最优子结构D.以上均是4.图与网络分析中，Dijkstra算法适用于（）。A.带负权边的无向图最短路B.不带负权边的有向图最短路C.任意权值的有向图最长路D.带负权环的无向图最短路5.排队论中，M/M/1/∞/∞模型的服务强度ρ=λ/μ，当ρ≥1时，系统（）。A.稳定，平均队长有限B.不稳定，平均队长趋于无穷大C.服务效率最高D.等待时间方差最小二、填空题（每题3分，共15分）1.线性规划标准型中，松弛变量在目标函数中的系数为______。2.对偶问题的对偶是______。3.整数规划中，0-1变量的取值只能是______。4.动态规划的阶段划分通常依据______的顺序。5.最短路问题中，Floyd算法的时间复杂度为______。三、计算题（共60分）1.（12分）求解线性规划问题：maxz=3x₁+5x₂s.t.x₁≤42x₂≤123x₁+2x₂≤18x₁,x₂≥0要求：（1）用图解法确定可行域顶点；（2）计算各顶点的目标函数值，找出最优解。2.（12分）已知原线性规划问题：minw=2y₁+3y₂s.t.y₁+2y₂≥42y₁+y₂≥3y₁,y₂≥0（1）写出其对偶问题；（2）用图解法求解对偶问题的最优解；（3）根据对偶理论，说明原问题的最优值。3.（12分）用分支定界法求解整数规划问题：maxz=2x₁+3x₂s.t.2x₁+2x₂≤11x₁+4x₂≤10x₁,x₂≥0且为整数要求：画出分支定界树，标注各子问题的松弛解及是否整数解。4.（12分）某企业需将5台设备分配给3个车间，各车间分配不同数量设备的收益如下表（单位：万元）：设备数车间1车间2车间3000013542797310121041214125131513用动态规划法求最优分配方案及最大收益。5.（12分）某物流网络的节点间距离（单位：公里）如下表，求节点1到节点6的最短路（节点编号1-6）：起点\终点23456135---2-24--3--16-4---275----3四、综合题（10分）某公司计划生产A、B两种产品，需消耗甲、乙两种资源。A产品每件需甲资源3单位、乙资源2单位，利润50元；B产品每件需甲资源1单位、乙资源4单位，利润40元。甲资源总量20单位，乙资源总量24单位。由于市场需求，A产品产量不超过4件，B产品产量至少2件且为整数。（1）建立整数规划模型；（2）用割平面法求解，写出至少一个割平面方程；（3）分析若甲资源增加2单位，最优解是否变化（需计算影子价格）。答案一、单项选择题1.A2.A3.D4.B5.B二、填空题1.02.原问题3.0或14.时间或空间5.O(n³)三、计算题1.（1）可行域顶点为(0,0)、(0,6)、(2,6)、(4,3)、(4,0)；（2）目标函数值分别为0、30、36、27、12，最优解为(x₁,x₂)=(2,6)，z=36。2.（1）对偶问题：maxz=4x₁+3x₂s.t.x₁+2x₂≤22x₁+x₂≤3x₁,x₂≥0（2）图解得最优解(x₁,x₂)=(4/3,1/3)，z=19/3；（3）原问题最优值w=19/3。3.分支定界树：根节点松弛解(x₁=3.5,x₂=1.5)，z=11.5；分支x₁≤3，子问题1松弛解(x₁=3,x₂=1.75)，z=11.25；分支x₁≥4，子问题2无可行解；子问题1分支x₂≤1，子问题1-1解(x₁=3,x₂=1)，z=9；子问题1分支x₂≥2，子问题1-2松弛解(x₁=2.5,x₂=2)，z=11；子问题1-2分支x₁≤2，子问题1-2-1解(x₁=2,x₂=2)，z=10；子问题1-2分支x₁≥3，子问题1-2-2解(x₁=3,x₂=2)，检查约束2×3+2×2=10≤11，1×3+4×2=11≤10？不满足，无可行解；最终最优解(x₁=2,x₂=2)，z=10。4.阶段k=1,2,3（车间1-3），状态s表示剩余设备数，决策x_k表示分配给第k车间的设备数。阶段3：f₃(s)=max{收益(3,s)}，s=0-5；阶段2：f₂(s)=max{收益(2,x₂)+f₃(s-x₂)}，x₂=0-s；阶段1：f₁(5)=max{收益(1,x₁)+f₂(5-x₁)}，x₁=0-5；计算得最优分配：车间1分配1台（收益3），车间2分配2台（收益9），车间3分配2台（收益7），总收益3+9+7=19万元。5.Dijkstra算法标号过程：初始：d(1)=0，其他∞；节点1更新邻居：d(2)=3，d(3)=5；选d(2)=3，更新节点2的邻居：d(3)=min(5,3+2)=5，d(4)=3+4=7；选d(3)=5，更新节点3的邻居：d(4)=min(7,5+1)=6，d(5)=5+6=11；选d(4)=6，更新节点4的邻居：d(5)=min(11,6+2)=8，d(6)=6+7=13；选d(5)=8，更新节点5的邻居：d(6)=min(13,8+3)=11；最短路为1→2→3→4→5→6，总距离11公里。四、综合题（1）模型：maxz=50x₁+40x₂s.t.3x₁+x₂≤202x₁+4x₂≤24→x₁+2x₂≤12x₁≤4x₂≥2，x₁,x₂∈Z⁺（2）松弛问题最优解(x₁=3.5,x₂=4.25)，非整数。取x₁=3.5=3+0