2025年大学《数学与应用数学》专业题库- 运筹学算法与资源调度

2025年大学《数学与应用数学》专业题库——运筹学算法与资源调度考试时间：______分钟总分：______分姓名：______一、选择题（每小题3分，共15分。请将正确选项的字母填在题后的括号内）1.已知线性规划问题：maxZ=c₁x₁+c₂x₂，s.t.ax₁+bx₂≤b₀,x₁,x₂≥0。若将其目标函数改为minZ'=-c₁x₁-c₂x₂，约束条件不变，则Z'的最优值与Z的最优值之间的关系是（）。A.Z'=ZB.Z'=-ZC.Z'≥ZD.Z'≤Z2.在单纯形法迭代中，若某非基变量的检验数αj>0，且其对应的列向量(a₁j,a₂j,...,amj)中所有元素都大于或等于0，则该线性规划问题（）。A.已找到最优解，最优解唯一B.已找到最优解，最优解可能不唯一C.无界D.可能存在最优解，也可能无界3.若一个线性规划问题的对偶问题是不可行的，则原问题（）。A.必定可行，但最优值可能不存在B.必定不可行C.可能可行，也可能不可行，但最优值必定不存在D.必定最优，最优值存在4.在整数规划问题中，若用分支定界法求解，则每次分支后得到的子问题集合中，最优整数解的值（）。A.一定严格增大B.一定严格减小C.不一定会改变D.总是保持不变5.在最大流问题中，若将某条容量为c(u,v)的弧(u,v)的容量减半，则原图的最大流量F的值（）。A.一定不变B.一定严格减小C.可能不变，也可能减小D.一定严格增大二、填空题（每小题4分，共20分。请将答案填在题后的横线上）6.线性规划问题的基是可行域顶点的__________。7.若单纯形表中某非基变量的检验数为0，则该线性规划问题可能处于__________状态。8.整数规划问题是线性规划问题的__________。9.在网络最大流问题中，增广路径上的所有弧称为__________弧。10.动态规划的核心思想是__________。三、计算题（每小题10分，共40分）11.用单纯形法求解下列线性规划问题：maxZ=3x₁+5x₂s.t.x₁+x₂≤42x₁+x₂≤6x₁,x₂≥012.已知某线性规划问题的对偶问题为：minW=4y₁+2y₂s.t.2y₁+y₂≥1y₁+2y₂≥3y₁,y₂≥0求原问题的最优解。13.某公司需要安排两种产品的生产。生产每单位产品A需要消耗原料甲1公斤，能源B2小时；生产每单位产品B需要消耗原料甲1.5公斤，能源B1小时。原料甲的可用量为4公斤，能源B的可用量为6小时。产品A的利润为3元/单位，产品B的利润为2.5元/单位。问该公司应如何安排生产计划，才能使总利润最大？请建立该问题的线性规划模型。14.某工程包含6道工序，它们的先后关系及所需时间（天）如下表所示（箭头指向表示紧前工序）：工序紧前工序时间（天）A-3BA4CA5DB2EC,D6FE3（1）请绘制该工程的双向箭线图（AOA网络）。（2）求该工程的总工期，并指出关键路径。四、应用题（共25分）15.某公司有3台机器可用于加工3种不同的零件。已知每台机器加工每种零件所需的时间（小时/件）以及各机器的总可用时间（小时）如下表所示：零件机器1机器2机器3总可用时间123240212350331260每加工一件零件1，公司获利10元；每加工一件零件2，获利15元；每加工一件零件3，获利12元。问公司应如何安排各机器加工各零件的数量，才能使总获利最大？请建立该问题的整数规划模型（无需求解）。试卷答案一、选择题1.B2.C3.A4.C5.C二、填空题6.基变量7.最优解8.加约束9.增广10.最优性原理三、计算题11.解：引入松弛变量x₃,x₄≥0，将问题化为标准形：maxZ=3x₁+5x₂s.t.x₁+x₂+x₃=42x₁+x₂+x₄=6x₁,x₂,x₃,x₄≥0初始单纯形表：|B|x₁|x₂|x₃|x₄|RHS||---|----|----|----|----|-----||x₃|1|1|1|0|4||x₄|2|1|0|1|6||---|----|----|----|----|-----||Z|-3|-5|0|0|0|选择入基变量：max{-3,-5}=-5，对应x₂。选择出基变量：min{4/1,6/1}=4，对应x₃。主元为1。进行初等行变换：|B|x₁|x₂|x₃|x₄|RHS||---|----|----|----|----|-----||x₂|1|1|1|0|4||x₄|1|0|-1|1|2||---|----|----|----|----|-----||Z|0|0|5|0|20|检验数：-3,0,5,0。max{0,5}=5，对应x₃。选择入基变量x₃。选择出基变量：min{4/1,2/-1}=2，对应x₄。主元为-1。进行初等行变换：|B|x₁|x₂|x₃|x₄|RHS||---|----|----|----|----|-----||x₂|0|1|0|1|2||x₃|1|0|-1|-1|-2||---|----|----|----|----|-----||Z|0|0|0|5|30|检验数：0,0,0,5。全部非正，最优解达到。最优解：x₁=0,x₂=2,x₃=0,x₄=0。最优值Z=30。12.解：原问题为：minZ=c₁x₁+c₂x₂s.t.a₁x₁+a₂x₂≤b₀x₁,x₂≥0其对偶问题为：maxW=b₀y₁s.t.a₁y₁≤c₁a₂y₁≤c₂y₁≥0由对偶问题最优解可知，y₁=1是最优解，且对应a₁y₁=c₁，a₂y₁=c₂同时成立。根据“对偶互补松弛定理”，若y₁j>0，则必有aᵢxᵢ=0。因此，x₁=0或x₂=0。由原问题对偶最优解y₁=1可知，原问题最优解x₁,x₂必须满足a₁x₁+a₂x₂=b₀。结合x₁=0或x₂=0，可以推断原问题最优解为x₁=0,x₂=b₀/a₂（若a₂≠0）或x₁=b₀/a₁（若a₁≠0）。此时，原问题目标函数值为Z=c₁x₁+c₂x₂=c₂(b₀/a₂)=c₁(b₀/a₁)。由于c₁y₁+c₂y₂=c₁+c₂y₂≤b₀，最优值W=b₀是可能的最优值。当且仅当c₂y₂=0时取到。若y₂>0，则c₂=0。此时原问题变为minZ=c₁x₁，最优解为x₁=0(若a₁≠0)，目标函数值Z=0。综上，原问题的最优解为x₁=0,x₂=b₀/a₂（若a₂≠0且c₂≠0），或x₁=b₀/a₁（若a₁≠0且c₁≠0），或x₁=0,x₂=0（若c₁=0且c₂=0），最优值Z=0或Z=c₁(b₀/a₁)或Z=c₂(b₀/a₂)。13.解：设该公司生产产品Ax₁件，生产产品Bx₂件。目标函数：最大化总利润Z=3x₁+2.5x₂。约束条件：1.原料甲约束：x₁+1.5x₂≤42.能源B约束：2x₁+x₂≤63.非负约束：x₁,x₂≥0建立线性规划模型如下：maxZ=3x₁+2.5x₂s.t.x₁+1.5x₂≤42x₁+x₂≤6x₁,x₂≥014.解：（1）双向箭线图（AOA网络）：(A)---3-->(B)---4-->(D)---2-->(E)---6-->(F)\/\/55\/(C)---5--->（2）求总工期及关键路径：计算各节点的最早开始时间（ES）和最早完成时间（EF）：ES(A)=0,EF(A)=ES(A)+3=3ES(B)=EF(A)=3,EF(B)=ES(B)+4=7ES(C)=EF(A)=3,EF(C)=ES(C)+5=8ES(D)=EF(B)=7,EF(D)=ES(D)+2=9ES(E)=max{EF(C),EF(D)}=max{8,9}=9,EF(E)=ES(E)+6=15ES(F)=EF(E)=15,EF(F)=ES(F)+3=18总工期=EF(F)=18天。计算各节点的最晚开始时间（LS）和最晚完成时间（LF）：LF(F)=EF(F)=18,LS(F)=LF(F)-3=15LF(E)=EF(E)=15,LS(E)=LF(E)-6=9LF(D)=min{LS(F),LS(E)}=min{15,9}=9,LS(D)=LF(D)-2=7LF(C)=min{LS(E)}=min{9}=9,LS(C)=LF(C)-5=4LF(B)=min{LS(D)}=min{7}=7,LS(B)=LF(B)-4=3LF(A)=min{LS(B),LS(C)}=min{3,4}=3,LS(A)=LF(A)-3=0关键路径为：A→B→D→E→F。该路径上的活动（A,B,D,E,F）的最早开始时间等于最晚开始时间，总时差为零。四、应用题15.解：设该公司安排机器1加工零件1x₁₁件，机器2加工零件1x₁₂件，机器3加工零件1x₁₃件；机器1加工零件2x₂₁件，机器2加工零件2x₂₂件，机器3加工零件2x₂₃件；机器1加工零件3x₃₁件，机器2加工零件3x₃₂件，机器3加工零件3x₃₃件。目标函数：最大化总获利Z=10(x₁₁+x₁₂+x₁₃)+15(x₂₁+x₂₂+x₂₃)+12(x₃₁+x₃₂+x₃₃)。约束条件：1.机器1时间约束：2x₁₁+3x₂₁+3x₃₁≤402.机器2时间约束：3x₁₂+2x₂₂+x₃₂≤503.机器3时间约束：2x₁₃+3x₂₃+2x₃₃≤604.零件产量非负约束：x₁₁+x₁₂+x₁₃=Q₁(总需求量)x₂₁+x₂₂+x₂₃=Q₂(总需求量)x₃₁+x₃₂+x₃₃=Q₃(总需求量)x₁j,x₂j,x₃j≥0(j=1,2,3)整数规划模型：