2026年哈尔滨工业大学运筹学研究生入学考试试题及答案

2026年哈尔滨工业大学运筹学研究生入学考试试题及答案一、单项选择题（每题3分，共30分）1.对于线性规划问题的标准型，下列说法正确的是（）A.基可行解的非零分量个数必须等于约束方程的个数mB.线性规划问题的基可行解与其可行域的顶点一一对应C.若线性规划问题存在可行解，则一定存在最优基可行解D.基可行解中的基变量取值可以为负数答案B解析选项A错误，存在退化的基可行解，其非零分量个数小于m；选项C错误，若线性规划问题可行域无界，则问题可能无最优解，不存在最优基可行解；选项D错误，基可行解要求所有变量取值非负。2.若原线性规划问题为无界解，则其对偶问题（）A.存在唯一最优解B.存在无穷多最优解C.无可行解D.无界解答案C解析根据对偶问题的基本性质，若原问题存在无界解，则对偶问题一定无可行解；反之若对偶问题无界，则原问题无可行解。3.对于供需平衡的运输问题，已知产地数量为，销地数量为，则该问题的基变量个数为（）A.mB.mC.mD.m答案C解析运输问题的系数矩阵秩为m+n−4.在用割平面法求解整数规划问题时，下列说法正确的是（）A.割平面可以割掉部分整数可行解B.割平面会割掉当前松弛问题的非整数最优解，但不会割掉任何整数可行解C.每添加一个割平面约束，就会增加一个整数变量D.割平面法求解所有整数规划问题的效率都高于分枝定界法答案B解析割平面方程由整数规划的整数约束推导得到，其作用是切除松弛问题可行域中不包含整数点的部分，不会切除任何整数可行解。5.动态规划方法的核心基础是最优性原理，该原理要求问题的状态必须具备的性质是（）A.无后效性B.连续性C.可分离性D.单调性答案A解析无后效性（马尔可夫性）是动态规划状态的核心要求，即给定某阶段的状态后，后续过程的演化不受之前阶段的状态和决策影响。6.对于包含个顶点的连通无向图，下列关于树的说法错误的是（）A.树是包含n−B.树中任意两点之间存在唯一的路径C.树中去掉任意一条边则图不连通D.树中至少存在2个度数为1的顶点，且不存在环，边数可以小于n答案D解析n个顶点的树必须恰好包含n−1条边，边数小于7.在标准排队模型中，系统能够达到稳态的充要条件是服务强度满足（）A.ρB.ρC.ρD.ρ答案B解析服务强度ρ=λ/8.在经典的经济订货批量（EOQ）模型中，假设订货提前期为0、不允许缺货、瞬时到货，若每次订货的固定订货成本变为原来的4倍，单位货物年存储成本不变，需求速率不变，则经济订货批量变为原来的（）A.1/2倍B.2倍C.4倍D.不变答案B解析经济订货批量公式为Q*=2DS/H9.在关键路径法（CPM）中，某活动的总时差是指（）A.不影响其紧后活动最早开始时间的前提下，该活动可以延迟的最大时间B.不影响整个项目总工期的前提下，该活动可以延迟的最大时间C.该活动的最迟结束时间与最早结束时间的差值的最小值D.该活动的最早开始时间与最迟开始时间的和答案B解析选项A描述的是自由时差，总时差是活动在不影响总工期前提下的最大可延迟时间，等于活动最迟开始时间与最早开始时间的差值。10.在不确定型决策中，决策者从最不利的情况出发，选择在最不利情况下收益最大的方案作为最优方案，该决策准则是（）A.乐观准则B.悲观准则C.最小后悔值准则D.等概率准则答案B解析悲观准则（小中取大准则）的决策逻辑是先找出每个方案在最差自然状态下的收益，再选择收益最大的方案。二、计算与建模题（共120分）1.（20分）某工厂利用甲、乙两种原材料生产A、B、C三种产品，生产每单位产品所需的原材料消耗、单位产品利润，以及原材料的每日可用量如下表所示：原材料产品A（单位消耗）产品B（单位消耗）产品C（单位消耗）每日原材料可用量（千克）甲12230乙31240单位利润（元）354——回答以下问题：（1）建立使得每日总利润最大的线性规划模型；（6分）（2）用单纯形法求解该模型，写出最优生产计划和最大利润；（10分）（3）说明最优解是否唯一，为什么？（4分）答案（1）设x1（2）引入松弛变量x4基变量510010.80.6-0.2310100.4-0.20.4-8000-1.2-2.4-0.2最优生产计划为每日生产A产品10单位、B产品10单位、C产品0单位，最大每日利润为80元。（3）该问题最优解唯一。因为最优表中所有非基变量x3解析：单纯形迭代过程需保持检验数计算、主元选择和行变换的正确性，最终所有检验数非正时达到最优；非基变量检验数严格小于0是最优解唯一的判定条件。2.（15分）已知某线性规划问题如下：其最优单纯形表如下（其中x3基变量241001/400400-21/2132011/2-1/80-1400-3/2-1/80回答以下问题：（1）写出该原问题的对偶问题；（5分）（2）利用对偶性质直接写出对偶问题的最优解；（4分）（3）若第一种资源（第一个约束右端项）从8增加到10，求新的最优解和最优目标函数值。（6分）答案：（1）根据原问题与对偶问题的对应关系，对偶问题为：（2）根据对偶理论，原问题松弛变量检验数的相反数为对偶问题的最优解。原问题松弛变量x3,x4,x5（3）最优基的逆矩阵B−新的右端项向量为b=(10,16,12解析：右端项变化时，若基变量新的取值全部非负，则基不变，检验数不变，可直接通过B−1计算新的解；第一种资源的影子价格为y13.（15分）某公司从三个加工厂A1、A2、A3运送货物到四个销售点B1、B2、B3、B4，各加工厂的产量、各销售点的需求量，以及各工厂到各销售点的单位运价如下表所示：B1B2B3B4产量（吨）A13113107A219284A37410510需求量（吨）3656要求：（1）判断该运输问题是否供需平衡，若不平衡，将其转化为平衡运输问题；（3分）（2）用最小元素法确定初始调运方案；（6分）（3）用位势法判断初始方案是否为最优方案，若不是，调整得到最优调运方案及最小总运费。（6分）答案（1）总产量为7+4+（2）用最小元素法得到初始调运方案（基变量分配量）：A2→B1运3吨，A2→B3运1吨，A1→B3运4吨，A3→B2运6吨，A3→B4运3吨，A3→B5运1吨，A1→B4运3吨，基变量共3+（3）通过位势法检验初始方案，发现存在负检验数，经两次闭回路调整后得到最优调运方案：A1→B3运5吨、A1→B4运1吨、A1→B5运1吨；A2→B1运3吨、A2→B4运1吨；A3→B2运6吨、A3→B4运4吨。最小总运费为5×解析产大于销的运输问题需通过虚拟销地转化为平衡问题；最小元素法从最小运价开始分配，满足基变量数要求；调整时沿负检验数对应的闭回路调整，直到所有检验数非负，达到最优。4.（15分）某公司有4台设备准备分配给甲、乙、丙三个工厂，各工厂获得不同数量设备后可创造的年利润如下表所示（单位：万元）：设备台数01234甲工厂03578乙工厂04689丙工厂025810要求：用动态规划方法确定设备的最优分配方案，使得总年利润最大。答案将问题按工厂分为3个阶段，状态变量sk表示分配给第k个到第3个工厂的设备台数，决策变量xk表示分配给第k个工厂的设备台数，状态转移方程为sk+1=s(0)=0,f_3(1)=2,f_3(2)=5,f_3(3)=8,f_3(4)=10。2(0)=0,f_2(1)=4,f_2(2)=6,f_2(3)=9,f_2(4)=12。3.第(4)=\max\{12,12,11,11,8\}=12$，对应两个最优分配方案：•方案1：分配给甲工厂0台、乙工厂1台、丙工厂3台，总利润0+•方案2：分配给甲工厂1台、乙工厂1台、丙工厂2台，总利润3+最大年利润为12万元。解析一维资源分配是动态规划的典型应用，逆序递推时需枚举所有可能的决策，计算各状态下的最优值，最后顺序回溯得到最优方案。5.（20分）给定有向网络包含源点vs、中间节点v1,v2,v3、汇点vt，各条有向弧的容量（单位：吨/小时）如下：vs→v1（1）用Ford-Fulkerson标号法求该网络从vs到v（2）写出对应的最小割集，并验证最大流-最小割定理。（8分）答案：（1）从0流开始，通过多次寻找增广链并增广，最终得到最大流的流量分配：vs→v1流量8，vs→v2流量6；v1→v2流量3，（2）最小割集为将节点划分为S={vs,v1,v（1）判断系统是否稳定，计算服务强度；（3分）（2）计算系统空闲的概率、系统内平均顾客数、排队等待的平均顾客数、顾客在系统内的平均逗留时间、平均排队等待时间；（8分）（3）若银行希望顾客的平均排队等待时间不超过1分钟，求最低的平均服务率应达到多少（人/小时）。（4分）答案：首先统一单位，平均到达率λ=12人/小时，平均服务率（1）服务强度ρ=（2）系统空闲概率P0=1−ρ=0.4；系统内平均顾客数L（3）要求平均等待时间Wq≤1/60小时，代入公式λ（1）计算经济订货批量、年最低总费用（包含采购成本、订货成本、存储成本）、每年的订货次数；（9分）（2）若每次订货量达到2000件时，供应商给予5%的价格折扣，其余成本不变，判断企业是否应该接受该折扣政策，说明理由；（6分）（3）若允许缺货，已知单位原材料每年的缺货成本为8元，其他