2025年运筹学考试试卷及答案

2025年运筹学考试试卷及答案一、单项选择题（每题3分，共30分）1.线性规划问题的标准型中，决策变量要求为（）。A.非负B.任意实数C.正整数D.非正2.若原线性规划问题的可行域非空且有界，则其最优解（）。A.必存在且唯一B.必存在但可能不唯一C.可能不存在D.必不存在3.运输问题中，当总供给量大于总需求量时，通常的处理方法是（）。A.增加一个虚拟产地B.增加一个虚拟销地C.调整供给量D.调整需求量4.整数规划中，分支定界法的核心步骤是（）。A.求解松弛问题B.对非整数解变量分支C.计算上下界D.剪枝5.动态规划的基本方程中，状态转移方程描述的是（）。A.阶段之间的状态变化B.决策变量的取值范围C.指标函数的递推关系D.初始状态的确定6.图论中，Dijkstra算法适用于求解（）。A.无向图的最小提供树B.有向图的最长路径C.非负权图的最短路径D.任意权图的最短路径7.排队系统M/M/2/∞/∞中，第二个“M”表示（）。A.到达间隔时间服从泊松分布B.服务时间服从负指数分布C.系统容量无限D.顾客源无限8.对偶线性规划问题中，若原问题存在可行解但无界，则对偶问题（）。A.无可行解B.有可行解C.有最优解D.可能无界9.割平面法求解整数规划时，割平面方程的作用是（）。A.缩小松弛问题的可行域B.扩大可行域C.保持可行域不变D.改变目标函数10.目标规划中，优先因子P₁对应的偏差变量应（）。A.尽可能小B.尽可能大C.等于零D.无约束二、填空题（每题4分，共20分）1.线性规划问题中，若某基变量的检验数为0，则说明该问题存在________解。2.运输问题的初始可行解中，基变量的个数为________（设产地数为m，销地数为n）。3.动态规划的最优性原理可表述为：最优策略的子策略________。4.最小提供树的Kruskal算法是按边的权值________顺序选择边，同时避免形成环。5.排队系统M/M/1/∞/∞中，系统的平均队长L_s与平均等待队长L_q的关系为________（用ρ表示服务强度）。三、计算题（每题15分，共60分）1.用单纯形法求解以下线性规划问题：maxz=3x₁+5x₂s.t.x₁≤42x₂≤123x₁+2x₂≤18x₁,x₂≥02.某公司有3个工厂（A、B、C）生产新能源电池，产量分别为50、60、50单位；4个销售点（甲、乙、丙、丁）的需求量分别为40、40、30、50单位。单位运输成本（百元）如下表，用表上作业法求最小总运输成本。甲乙丙丁A3527B4638C54633.用分支定界法求解整数规划问题（要求x₁,x₂为非负整数）：maxz=4x₁+3x₂s.t.2x₁+3x₂≤122x₁+x₂≤8x₁,x₂≥04.某项目需在5天内完成4项任务（任务1-4），每天只能完成1项任务，任务i在第j天完成的成本为c_ij（单位：千元），如下表。用动态规划法求总成本最小的任务分配方案。第1天第2天第3天第4天任务15327任务24615任务38243任务43596四、综合题（每题15分，共30分）1.某新能源企业生产两种产品：光伏组件（产品1）和储能电池（产品2）。生产1单位产品1需消耗3单位原材料A、2单位原材料B，利润为5万元；生产1单位产品2需消耗1单位原材料A、4单位原材料B，利润为4万元。企业现有原材料A可用量为20单位，原材料B可用量为24单位。（1）建立线性规划模型，求最大利润；（2）若原材料A的可用量增加到25单位，分析最优解的变化；（3）若产品1的利润降至4万元，判断原最优解是否仍为最优。2.某物流中心有2台装卸设备，顾客（货车）到达服从泊松分布，平均每小时到达8辆；每台设备的服务时间服从负指数分布，平均每小时服务6辆。假设系统容量无限，顾客源无限。（1）写出排队系统的符号表示；（2）计算系统的服务强度ρ；（3）计算系统中无顾客的概率P₀；（4）计算平均队长L_s和平均等待队长L_q；（5）若增加1台设备，分析L_s的变化趋势（无需具体计算）。答案一、单项选择题1.A2.B3.B4.B5.A6.C7.B8.A9.A10.A二、填空题1.多重最优2.m+n-13.必为最优4.从小到大5.L_s=L_q+ρ三、计算题1.单纯形法求解引入松弛变量x₃,x₄,x₅，标准型为：maxz=3x₁+5x₂+0x₃+0x₄+0x₅s.t.x₁+x₃=42x₂+x₄=12→x₂+0.5x₄=63x₁+2x₂+x₅=18x_j≥0初始基变量为x₃,x₄,x₅，初始单纯形表：基变量x₁x₂x₃x₄x₅右端项x₃101004x₄0201012x₅3200118z-3-50000检验数最小为-5（x₂列），选x₂进基。θ=min(4/0,12/2,18/2)=6（x₄行），x₄出基。迭代后表（x₂,x₃,x₅为基变量）：基变量x₁x₂x₃x₄x₅右端项x₃101004x₂0100.506x₅300-116z-3002.5030检验数-3（x₁列），选x₁进基。θ=min(4/1,6/0,6/3)=2（x₅行），x₅出基。迭代后表（x₂,x₃,x₁为基变量）：基变量x₁x₂x₃x₄x₅右端项x₃0011/3-1/32x₂0100.506x₁100-1/31/32z0001.5136所有检验数非负，最优解为x₁=2,x₂=6，z=36。2.运输问题求解总供给=50+60+50=160，总需求=40+40+30+50=160，供需平衡。（1）初始解：用最小元素法。最小成本为A→丙（2），分配30单位（丙需求30）；次小为C→丁（3），分配50单位（丁需求50）；次小为A→甲（3），分配40单位（甲需求40）；A剩余50-30-40=-20（错误，应为A产量50，已分配甲40、丙30，超量，需调整）。正确步骤：A产量50，甲需求40，A→甲40，剩余A=10；丙需求30，A→丙10，剩余丙=20；B→丙20（B→丙成本3），B剩余60-20=40；B→乙40（乙需求40）；C→丁50（丁需求50），C剩余50-50=0。初始解：A→甲40，A→丙10；B→乙40，B→丙20；C→丁50。（2）最优性检验（位势法）：设u₁=0，计算v_j：A→甲：u₁+v₁=3→v₁=3A→丙：u₁+v₃=2→v₃=2B→乙：u₂+v₂=6→v₂=6-u₂B→丙：u₂+v₃=3→u₂=3-2=1→v₂=6-1=5C→丁：u₃+v₄=3→v₄=3-u₃非基变量检验数σ_ij=c_ij(u_i+v_j)：A→乙：5(0+5)=0；A→丁：7(0+3-u₃)（需补u₃，由B→乙基变量u₂=1，C无基变量，假设C→乙为基变量？初始解可能有误，改用伏格尔法更准确。重新用伏格尔法：行罚数：A行最小差=3-2=1（次小3，最小2）；B行=4-3=1（次小4，最小3）；C行=3-4=-1（次小4，最小3）。列罚数：甲=3-4=-1（次小4，最小3）；乙=5-4=1（次小5，最小4）；丙=2-3=-1（次小3，最小2）；丁=3-7=-4（次小7，最小3）。最大罚数为乙列1，选乙列最小成本C→乙（4），分配乙需求40，C剩余50-40=10；C→丁10（丁需求50，剩余40）；A→丙30（丙需求30）；A→甲20（甲需求40，剩余20）；B→甲20，B→丁40（丁剩余40）。初始解总成本=40×4（C→乙）+10×3（C→丁）+30×2（A→丙）+20×3（A→甲）+20×4（B→甲）+40×8（B→丁）=160+30+60+60+80+320=710。检验数计算后，若存在负检验数，调整闭回路。最终最优解为A→丙30，A→甲20；B→乙40，B→丁20；C→乙0，C→丁50。总成本=30×2+20×3+40×6+20×8+50×3=60+60+240+160+150=670（百元）。3.分支定界法求解松弛问题（不考虑整数约束）：maxz=4x₁+3x₂s.t.2x₁+3x₂≤12，2x₁+x₂≤8，x₁,x₂≥0用图解法，交点为(3,2)，z=4×3+3×2=18。x₁=3（整数），x₂=2（整数），直接为整数解，最优解x₁=3,x₂=2，z=18。4.动态规划求解阶段k=1-4（对应第1-4天），状态s_k表示前k-1天已分配的任务集合，决策x_k表示第k天分配的任务。状态转移s_{k+1}=s_k∪{x_k}，指标函数为累计成本。定义f_k(s_k)为前k天分配s_k任务的最小成本。k=1（第1天）：f₁({1})=5，f₁({2})=4，f₁({3})=8，f₁({4})=3k=2（第2天）：f₂({1,2})=min(5+6,4+3)=7（任务2第2天成本3）；f₂({1,3})=min(5+2,8+3)=7（任务3第2天成本2）；f₂({1,4})=min(5+5,3+3)=6（任务4第2天成本5，任务1第1天+任务4第2天=5+5=10，任务4第1天+任务1第2天=3+3=6）；f₂({2,3})=min(4+2,8+1)=5（任务2第1天+任务3第2天=4+2=6，任务3第1天+任务2第2天=8+1=9）；f₂({2,4})=min(4+5,3+1)=4（任务2第1天+任务4第2天=4+5=9，任务4第1天+任务2第2天=3+1=4）；f₂({3,4})=min(8+5,3+2)=5（任务3第1天+任务4第2天=8+5=13，任务4第1天+任务3第2天=3+2=5）k=3（第3天）：以状态{1,2,3}为例，剩余任务4，f₃({1,2,3})=f₂({1,2})+c_4,3=7+9=16（任务4第3天成本9）；状态{1,2,4}：剩余任务3，f₃({1,2,4})=f₂({1,2})+c_3,3=7+4=11；状态{1,3,4}：剩余任务2，f₃({1,3,4})=f₂({1,3})+c_2,3=7+1=8；状态{2,3,4}：剩余任务1，f₃({2,3,4})=f₂({2,3})+c_1,3=5+2=7k=4（第4天）：所有任务已分配，f₄({1,2,3,4})=min{f₃({1,2,3})+c_4,4,f₃({1,2,4})+c_3,4,f₃({1,3,4})+c_2,4,f₃({2,3,4})+c_1,4}计算得最小成本为7+7=14（任务1第4天成本7，对应状态{2,3,4}第3天成本7，任务1第4天分配）。最优方案：第1天任务4（成本3），第2天任务3（成本2），第3天任务2（成本1），第4天任务1（成本7），总成本=3+2+1+7=13（千元）。四、综合题1.（1）模型：设x₁为产品1产量，x₂为产品2产量maxz=5x₁+4x₂s.t.3x₁+x₂≤20（原材料A）2x₁+4x₂≤24（原材料B）x₁,x₂≥0用图解法，交点为(4,8)（3x₁+x₂=20与2x₁+4x₂=24联立：x₁=4,x₂=8），z=5×4+4×8=52万元。（2）原材料A增至25单位，约束变为3x₁+x₂≤25，与原材料B约束交点为((25×4-24)/10,(24×3-25×2)/10)=((100-24)/10,(72-50)/10)=(7.6,2.2)，z=5×7.6+4×2.2=38+8.8=46.8（低于原52，说明原约束B仍为紧约束，最优解不变？需重新计算：原最优解x₂=8，代入3x₁+8≤25→x₁≤17/3≈5.67，x₁=(24-4x₂)/2=12-2x₂，当x₂=8时x₁=-4（矛盾），说明原交点错误。正确联立：3x₁+x₂=20，2x₁+4x₂=24→x₁=(80-24)/10=5.6，x₂=20-3×5.6=3.2，z=5×5.6+4×3.2=28+12.8=40.8。原材料A增加后，新交点为3x₁+x₂=25与2x₁+4x₂=24→x₁=(100-24)/10=7.6，x₂=25-3×7.6=2.2，z=5×7.6+4×2.2=38+8.8=46.8，仍小于原最优解？可能原计算错误，正确单纯形法求解：标准型加入松弛变量x₃,x₄：maxz=5x₁+4x₂+0x₃+0x₄s.t.3x₁+x₂+x₃=202x₁+4x₂+x₄=24初始基x₃,x₄，检验数-5,-4，选x₁进基，θ=min(20/3,24/2)=6.67（x₄行），x₄出基。迭代后x₁=12-0.5x₄-2x₂，代入z=5(12-0.5x₄-2x₂)+4x₂=60-2.5x₄-6x₂，检验数-6（x₂列），选x₂进基，θ=min((20-3x₁)/1,(24-2x₁)/4)=当x₁=0时，x₂=6（x₄行），x₄=24-4×6=0，x₃=20-0-6=14。迭代后基变量x₁=(20-x₂-x₃)/3，代入z=5(20-x₂-x₃)/3+4x₂=100/3+(7x₂-5x₃)/3，检验数7/3>0，x₂进基，θ=min(20/1,24/4)=6（x₄行），最终最优解x₁=4,x₂=4（3×4+4=16≤20，2×4+4×4=24），z=5×4+4×4=36。原模型错误，正确最优解应为x₁=4,x₂=4，z=36。原材料A增至25后，约束3x₁+x₂≤25，x₂=(24-2x₁)/4=6-0.5x₁，代入得3x₁+6-0.5x₁≤25→2.5x₁≤19→x₁≤7.6，x₂=6-0.5×7.6=2.2，z=5×7.6+4×2.2=38+8.8=46.8>36，最优解变化。（3）产品1利润降至4万元，原最