2025年《运筹学》期末考试试题及参考答案

2025年《运筹学》期末考试试题及参考答案一、填空题（每空2分，共20分）1.线性规划问题标准型要求目标函数为______，所有约束条件为______，决策变量满足______。2.对偶问题的基本性质中，若原问题存在可行解且目标函数无界，则对偶问题______；若原问题与对偶问题均存在可行解，则两者的最优目标函数值______。3.动态规划的核心是______，其求解过程需满足______，即某阶段的状态只与当前阶段的决策有关，与之前状态无关。4.在运输问题中，若总供给量大于总需求量，需构造一个______虚拟需求点，其单位运价为______，以转化为平衡运输问题。5.排队系统M/M/1/∞/∞中，λ表示______，μ表示______，系统稳定的条件是______。二、简答题（每题8分，共24分）1.简述单纯形法求解线性规划问题的基本步骤，并说明检验数的经济含义。2.整数规划中分支定界法的“分支”与“定界”分别指什么？简述其求解整数规划的核心逻辑。3.说明Dijkstra算法求解最短路问题的适用条件，并对比其与Floyd-Warshall算法的主要区别。三、计算题（共56分）1.（12分）用单纯形法求解以下线性规划问题，并判断是否存在多重解。maxz=3x₁+5x₂s.t.x₁≤42x₂≤123x₁+2x₂≤18x₁,x₂≥02.（14分）某企业拟采购A、B两种设备扩大生产，A设备单价15万元，年产能800件；B设备单价10万元，年产能500件。企业预算不超过60万元，且设备总数不超过5台。若产品年利润为2元/件，要求设备数量为整数，求利润最大的采购方案（用分支定界法求解）。3.（12分）某公司需将500万元研发资金分配到三个新产品研发阶段（阶段1、阶段2、阶段3），各阶段投入资金x_i（万元）与收益r_i(x_i)的关系如下表所示。用动态规划求解总收益最大的分配方案。投入x_i（万元）0100200300400500r₁(x₁)0306590110120r₂(x₂)025558095100r₃(x₃)04070951151304.（10分）某物流网络节点为A-B-C-D-E，各边权值（距离，单位：km）为：A-B(3)、A-C(5)、B-C(2)、B-D(4)、C-D(1)、C-E(6)、D-E(3)。用Dijkstra算法求A到E的最短路径及总距离。5.（8分）某银行服务窗口服从M/M/1排队模型，客户平均到达率λ=12人/小时，柜员平均服务率μ=15人/小时。计算系统中客户的平均数量（L_s）、排队等待的平均客户数（L_q）及客户在系统中的平均逗留时间（W_s）。四、应用题（共50分）某制造企业生产甲、乙两种产品，需经过三个车间加工：车间1：甲需2小时/件，乙需1小时/件，总工时≤80小时；车间2：甲需1小时/件，乙需3小时/件，总工时≤90小时；车间3：甲需3小时/件，乙需2小时/件，总工时≤120小时；甲产品利润50元/件，乙产品利润40元/件。（1）（20分）建立线性规划模型，用两阶段法求解是否存在可行解？若存在，求最优生产计划及最大利润。（2）（15分）若车间1工时增加10小时（变为90小时），分析最优解的变化（要求计算影子价格并说明）。（3）（15分）若乙产品利润提升至50元/件，其他条件不变，判断原最优解是否仍为最优？若否，重新求解。参考答案一、填空题1.最大化（或最小化，需统一）；等式；非负2.无可行解；相等3.最优化原理；无后效性4.需求；05.客户平均到达率；柜员平均服务率；ρ=λ/μ<1二、简答题1.步骤：①将问题化为标准型，引入松弛变量；②确定初始可行基，列出初始单纯形表；③计算检验数，若所有检验数≤0（最大化问题），则当前解为最优；否则选择正检验数最大的变量作为进基变量；④计算θ值，确定出基变量；⑤用初等行变换更新单纯形表，重复③-④直至最优。检验数的经济含义：表示对应变量增加1单位时，目标函数的增量（或资源的边际贡献）。2.分支：将非整数解的变量x_i分为x_i≤floor(x_i)和x_i≥ceil(x_i)两个子问题，缩小可行域；定界：对每个子问题求解松弛问题（不考虑整数约束），得到目标函数值作为当前分支的上界（最大化问题）或下界（最小化问题）。核心逻辑：通过分支逐步缩小可行域，通过定界剪枝无潜力的分支，最终找到整数最优解。3.Dijkstra算法适用于边权非负的图，求解单源点到所有其他点的最短路。与Floyd-Warshall算法的区别：①Dijkstra是单源点，Floyd是多源点（所有点对）；②Dijkstra时间复杂度O(n²)，Floyd为O(n³)；③Dijkstra要求边权非负，Floyd允许边权为负（但不能有负权环）。三、计算题1.标准型引入松弛变量x₃,x₄,x₅：maxz=3x₁+5x₂+0x₃+0x₄+0x₅s.t.x₁+x₃=42x₂+x₄=12→x₂≤63x₁+2x₂+x₅=18x_i≥0初始单纯形表：基x₁x₂x₃x₄x₅右端项x₃101004x₄0201012x₅3200118z-3-50000检验数x₂=-5最小（最大化问题取最负），进基；θ=min(4/0（无）,12/2=6,18/2=9)→x₄出基。第一次迭代（x₂进基，x₄出基）：x₂行除以2得x₂=6-0.5x₄更新x₅行：3x₁+2(6-0.5x₄)+x₅=18→3x₁-x₄+x₅=6→x₅=6-3x₁+x₄z=3x₁+5(6-0.5x₄)=3x₁+30-2.5x₄→检验数x₁=3>0，x₄=-2.5≤0第二次迭代（x₁进基，x₅出基）：x₅行：3x₁=6+x₄-x₅→x₁=2+(1/3)x₄(1/3)x₅更新x₃行：x₁=4-x₃→2+(1/3)x₄(1/3)x₅=4-x₃→x₃=2(1/3)x₄+(1/3)x₅x₂=6-0.5x₄z=3(2+(1/3)x₄(1/3)x₅)+30-2.5x₄=6+x₄-x₅+30-2.5x₄=36-1.5x₄-x₅此时检验数x₄=-1.5≤0，x₅=-1≤0，最优解为x₁=2,x₂=6，z=32+56=36。无多重解（所有非基变量检验数均<0）。2.设采购A设备x台，B设备y台，目标函数max利润=2(800x+500y)=1600x+1000y约束：15x+10y≤60（预算），x+y≤5（数量），x,y≥0且为整数。松弛问题（去掉整数约束）：maxz=1600x+1000ys.t.3x+2y≤12（预算约束除以5），x+y≤5，x,y≥0图解法得交点：3x+2y=12与x+y=5联立，解得x=2,y=3（整数解？x=2,y=3时，152+103=60≤60，x+y=5≤5，满足。利润=16002+10003=6200元。但需验证是否为整数最优。若松弛问题解非整数，假设松弛解为x=2.5,y=2.5（例如调整约束），则分支：分支1：x≤2，分支2：x≥3。分支1：x≤2，松弛问题为maxz=1600x+1000y，s.t.3x+2y≤12（x≤2），x+y≤5。x=2时，32+2y≤12→y≤3，x+y≤5→y≤3，故y=3，利润=16002+10003=6200。分支2：x≥3，x=3时，33+2y≤12→2y≤3→y≤1.5，取y=1，利润=16003+10001=5800；y=1.5时松弛解利润=16003+10001.5=6300，但y非整数，需进一步分支y≤1和y≥2。y≥2时，33+22=13>12，不可行。故分支2最优为5800。比较分支1和分支2，最大利润为6200元，方案为A=2台，B=3台。3.阶段k=1,2,3（对应三个阶段），状态s_k表示分配给第k到第3阶段的资金总额，决策x_k为第k阶段投入的资金（x_k≤s_k，且x_k为100的整数倍）。递推关系式：f_k(s_k)=max{r_k(x_k)+f_{k+1}(s_k-x_k)}，k=3,2,1，f_4(s_4)=0（边界条件）。阶段3（k=3）：s_3=0→x3=0,f3=0s_3=100→x3=100,f3=40s_3=200→x3=200,f3=70s_3=300→x3=300,f3=95s_3=400→x3=400,f3=115s_3=500→x3=500,f3=130阶段2（k=2）：s_2=0→f2=0s_2=100：x2=0→f3(100)=40；x2=100→r2(100)+f3(0)=25+0=25→max=40s_2=200：x2=0→f3(200)=70；x2=100→25+f3(100)=25+40=65；x2=200→55+0=55→max=70s_2=300：x2=0→f3(300)=95；x2=100→25+f3(200)=25+70=95；x2=200→55+f3(100)=55+40=95；x2=300→80+0=80→max=95（x2=0,100,200）s_2=400：x2=0→f3(400)=115；x2=100→25+f3(300)=25+95=120；x2=200→55+f3(200)=55+70=125；x2=300→80+f3(100)=80+40=120；x2=400→95+0=95→max=125（x2=200）s_2=500：x2=0→f3(500)=130；x2=100→25+f3(400)=25+115=140；x2=200→55+f3(300)=55+95=150；x2=300→80+f3(200)=80+70=150；x2=400→95+f3(100)=95+40=135；x2=500→100+0=100→max=150（x2=200或300）阶段1（k=1）：s1=500x1=0→f2(500)=150；x1=100→30+f2(400)=30+125=155；x1=200→65+f2(300)=65+95=160；x1=300→90+f2(200)=90+70=160；x1=400→110+f2(100)=110+40=150；x1=500→120+f2(0)=120+0=120→max=160（x1=200或300）当x1=200时，s2=500-200=300，阶段2取x2=0,100,200均可。若x2=0，则x3=300，收益=65+0+95=160；若x2=100，x3=200，收益=65+25+70=160；若x2=200，x3=100，收益=65+55+40=160。当x1=300时，s2=500-300=200，阶段2取x2=0，x3=200，收益=90+0+70=160；或x2=100，x3=100，收益=90+25+40=155（舍去）；或x2=200，x3=0，收益=90+55+0=145（舍去）。最优分配方案：x1=200万元（阶段1），x2=200万元（阶段2），x3=100万元（阶段3）或其他组合，总收益1600万元。4.Dijkstra算法步骤（节点A为起点，距离初始化为∞，A到A=0）：初始：dist[A]=0，其他∞；已选节点{}选A（最小距离0），更新邻接节点：B=3，C=5；已选{A}选B（距离3），更新邻接节点：C=min(5,3+2=5)，D=3+4=7；已选{A,B}选C（距离5），更新邻接节点：D=min(7,5+1=6)，E=5+6=11；已选{A,B,C}选D（距离6），更新邻接节点：E=min(11,6+3=9)；已选{A,B,C,D}选E（距离9），结束。最短路径：A→B→C→D→E，总距离9km（或A→C→D→E：5+1+3=9km，两条路径）。5.M/M/1模型参数：λ=12，μ=15，ρ=λ/μ=0.8<1（稳定）。L_s=λ/(μ-λ)=12/(15-12)=4人；L_q=ρ²/(1-ρ)=0.64/0.2=3.2人；W_s=L_s/λ=4/12=1/3小时=20分钟。四、应用题（1）模型：maxz=50x₁+40x₂s.t.2x₁+x₂≤80（车间1）x₁+3x₂≤90（车间2）3x₁+2x₂≤120（车间3）x₁,x₂≥0两阶段法：引入松弛变量x3,x4,x5（均≥0），第一阶段目标minw=x6+x7+x8（若原约束为不等式，无需人工变量，直接用松弛变量为初始基）。实际本题约束均为≤，初始基为x3,x4,x5，可行解存在（x1=x2=0时满足所有约束）。用单纯形法求解：初始表：基x1x2x3x4x5右端x32110080x41301090x532001120z-50-400000检验数x1=-50（最负），进基；θ=min(80/2=40,90/1=90,120/3=40)→x3或x5出基（选x5，因θ相同取后者）。第一次迭代（x1进基，x5出基）：x5行除以3得x1=40(2/3)x2(1/3)x5更新x3行：2(40(2/3)x2(1/3)x5)+x2+x3=80→80(4/3)x2(2/3)x5+x2+x3=80→x3=(1/3)x2+(2/3)x5更新x4行：(40(2/3)x2(1/3)x5)+3x2+x4=90→40+(7/3)x2(1/3)x5+x4=90→x4=50(7/3)x2+(1/3)x5z=50(40(2/3)x2(1/3)x5)+40x2=2000(100/3)x2(50/3)x5+40x2=2000+(20/3)x2(50/3)x5检验数x2=20/3>0，进基；θ=min((80-2x1)/1当x1=40时x2=0，此处计算x3行x2系数1/3>0→θ=(x3右端)/(1/3)=(80-240)/(1/3)=0/(1/3)=0？实际x3行当前右端为x3=(1/3)x2+(2/3)x5，当x2增加时，x3≥0自动满足；x4行θ=50/(7/3)=150/7≈21.43；x5已出基。取θ=150/7，x4出基。第二次迭代（x2进基，x4出基）：x4行乘以3/7得x2=(150/7)(3/7)x4+(1/7)x5更新x1=40(2/3)(150/7(3/7)x4+(1/7)x5)(1/3)x5=40(100/7)+(2/7)x4(2/21)x5(7/21)x5=(180/7)+(2/7)x4(9/21)x5=(180/7)+(2/7)x4(3/7)x5x3=(1/3)(150/7(3/7)x4+(1/7)x5)+(2/3)x5=(50/7)(1/7)x4+(1/21)x5+(14/21)x5=(50/7)(1/7)x4+(15/21)x5=(50/7)(1/7)x4+(5/7)x5z=2000+(20/3)(150/7(3/7)x4+(1/7)x5)(50/3)x5=2000+(1000/7)(20/7)x4+(20/21)x5(350/21)x5=2000+1000/7(20/7)x4(330/21)x5=(15000/7)(20/7)x4(110/7)x5此时检验数均≤0，最优解为x1=180/7≈25.71，x2=150/7≈21.43，z=15000/7≈2142.86元。（2）车间1工时增加10小时，即约束变为2x1+x2≤90。影子价格为该约束的对偶变量值，原问题对偶变量y1对应车间1工时，根据互补松弛性，原最优解中x3=0（松弛变量=0），故y1>0。对偶问题：minw=80y1+90y2+120y3s.t.2y1+y2+3y3≥50（x1的系数）y1+3y2+2y3≥40（x2的系数）y1,y2,y3≥0原最优解中x1=180/7,x2=150/7，非基变量x3=0（车间1无松弛），x4=0（车间2无松弛？原x4=50(7/3)x2+(1/3)x5，当x2=150/7，x5=0时，x4=50(7/3)(150