《运筹学学》课程考试试题及答案

《运筹学学》课程考试试题及答案第一部分：试题一、单项选择题（本大题共10小题，每小题2分，共20分）1.在线性规划的标准型中，约束方程组的形式为（）。A.∑B.∑C.∑D.∑2.若线性规划问题具有可行解，且可行域有界，则该线性规划问题（）。A.一定有最优解B.不一定有最优解C.一定有无界解D.一定无可行解3.在单纯形法迭代中，若所有检验数σj=cj-A.有唯一最优解B.有无穷多最优解C.无最优解D.解无界4.线性规划原问题的目标函数是求最大值（maxz），则其对偶问题的目标函数是（）。A.maxzB.minzC.maxwD.minw5.影子价格的经济含义是（）。A.单位资源的市场价格B.单位资源的成本价格C.在最优解基础上，增加单位资源时目标函数值的增量D.资源的损耗价值6.运输问题中，若产地数为m，销地数为n，则基变量的个数应为（）。A.m+nB.m+n-1C.m×nD.m+n+17.求解运输问题时，用来检验当前调运方案是否最优的方法是（）。A.闭回路法或位势法B.单纯形法C.匈牙利法D.分支定界法8.动态规划的最优性原理是（）。A.一个过程的最优策略具有这样的性质：无论其初始状态和初始决策如何，其后的诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略B.局部最优之和即为全局最优C.只关心当前状态的最优决策D.所有的决策都必须是离散的9.在图论中，连通图G具有n个顶点，若其生成树包含（）条边。A.nB.n-1C.n+1D.2(n-1)10.某排队系统中，顾客到达服从泊松分布，服务时间服从负指数分布，有c个服务台，系统容量无限，该模型记为（）。A.M/M/1B.M/G/1C.M/M/cD.G/M/c二、填空题（本大题共10小题，每小题2分，共20分）11.线性规划问题的可行基是指满足________条件的基。12.在对偶理论中，若原问题具有无界解，则其对偶问题________。13.大M法中，人工变量在目标函数中的系数为________（当求最大化时）。14.灵敏度分析主要研究当线性规划问题的参数（如cj15.表上作业法求解运输问题时，初始基可行解的确定常用方法有最小元素法和________。16.整数规划中，若要求变量只能取0或1，则该变量称为________。17.动态规划模型的四个要素是：阶段、状态、决策和________。18.在网络计划图中，关键路径是指________的路径。19.求解最短路径问题的常用算法是________。20.在风险型决策中，期望值准则是指根据每个方案的________来选择最优方案。三、简答题（本大题共4小题，每小题5分，共20分）21.简述线性规划问题中基可行解与可行解的区别与联系。22.什么是影子价格？影子价格在企业经营管理中有何指导意义？23.简述动态规划方法求解多阶段决策过程问题的基本思想。24.简述最大流问题中“增广链”的概念及其在求解算法中的作用。四、计算分析题（本大题共4小题，共90分）25.（本题25分）某工厂用A、B两种原料生产甲、乙、丙三种产品，有关数据如下表：资源/产品产品甲产品乙产品丙资源限量原料A(kg)63545原料B(kg)34530单位利润(万元)423(1)建立该问题的线性规划模型，并化为标准型。（5分）(2)用单纯形法求解该线性规划问题。（15分）(3)写出该问题的对偶问题，并根据最终单纯形表确定原料A和原料B的影子价格。（5分）26.（本题20分）某公司有三个工厂A1,A产地\销地$B_1$$B_2$$B_3$$B_4$产量$A_1$3113107$A_2$19284$A_3$741059销量3656(1)判断该运输问题是否为产销平衡问题。（2分）(2)用最小元素法确定初始调运方案。（8分）(3)用闭回路法检验上述初始方案是否为最优方案，若不是，求出最优调运方案及最小总运费。（10分）27.（本题25分）设有资金8万元，拟投资于三个项目：A、B、C。每个项目的投资额及相应的收益如下表所示（单位：万元）：投资额项目A收益项目B收益项目C收益000028910415201863035308384042(1)建立该问题的动态规划模型。（需明确阶段、状态、决策、状态转移方程和指标函数）（10分）(2)求出资金的最优分配方案，使得总收益最大。（15分）28.（本题20分）某工程项目的各项工序及其所需时间、紧前工序关系如下表所示：工序代号紧前工序工序时间(天)A-3B-4CA2DA5EB3FC,D4GE,F6(1)绘制该工程项目的网络图。（6分）(2)计算各节点的最早开始时间和最迟结束时间。（6分）(3)确定关键路径，并计算工程的总工期。（8分）第二部分：参考答案与解析一、单项选择题1.C解析：线性规划的标准型要求约束条件为等式方程，即∑j=1na2.A解析：线性规划的可行域是凸集。若可行域非空且有界，则目标函数一定可以在可行域的顶点上达到最大值或最小值，即一定有最优解。3.B解析：当所有非基变量的检验数σj4.D解析：根据对偶理论，原问题（Max）的对偶问题为Min问题。若原问题为maxz=CX，对偶问题为minw=Yb。5.C解析：影子价格（ShadowPrice）表示在其他条件不变的情况下，单位资源变化所引起的目标函数最优值的变化量。它反映了资源的边际贡献。6.B解析：运输问题是一个特殊的线性规划问题，其系数矩阵的秩为m+n-1，因此基变量的个数必须是m+n-1。7.A解析：运输问题的检验数计算通常使用闭回路法（针对具体的空格寻找闭回路计算运费调整量）或位势法（利用对偶理论计算ui8.A解析：这是R.Bellman提出的动态规划最优化原理的准确表述，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。9.B解析：树的定义是包含图中所有顶点的无圈连通子图。对于n个顶点的连通图，其生成树必有且仅有n-1条边。10.C解析：排队论符号标记为A/B/c。其中A表示到达间隔时间分布，B表示服务时间分布，c表示服务台数量。M代表泊松流（负指数分布），c代表多个服务台。二、填空题11.非负性（或满足XB解析：基解只要求满足约束方程，而基可行解还要求基变量取值非负。12.无可行解解析：根据对偶理论，若原问题为无界解，则其对偶问题无可行解。13.-M解析：在大M法中，为了在目标函数中惩罚人工变量，最大化问题中人工变量的系数取-M（M为足够大的正数），最小化问题中取+M。14.最优解（或最优基、目标函数值）解析：灵敏度分析旨在确定参数变化范围，使得当前的最优基保持不变，或者最优解的结构保持稳定。15.伏格尔法(VogelApproximationMethod,VAM)解析：常用的确定初始方案的方法包括最小元素法（LeastCostMethod）、伏格尔法（差值法）和西北角法（NorthwestCornerMethod）。16.0-1变量（或二进制变量）解析：这是整数规划中的特殊变量，常用于表示逻辑关系，如选址问题（1为选，0为不选）。17.状态转移方程（或指标函数/最优值函数）解析：动态规划模型的四个核心要素通常是：阶段、状态、决策、状态转移方程。有时也将指标函数包含在内。18.耗时最长（或总时间最长）解析：关键路径决定了整个项目的最短完成时间，即从始点到终点的所有路径中时间最长的路径。19.Dijkstra算法解析：Dijkstra算法是求解权值为正的有向图或无向图中单源最短路径问题的经典算法。20.期望收益（或期望损益值）解析：期望值准则是通过计算每个方案在各种自然状态下的加权平均值（期望值），选择最大期望收益（或最小期望损失）对应的方案。三、简答题21.简述线性规划问题中基可行解与可行解的区别与联系。答：区别：可行解是指满足线性规划所有约束条件（包括非负约束）的解向量。基可行解不仅是可行解，而且它对应于线性规划约束矩阵的一个基，即非基变量取值为0，基变量通过求解基方程组得出，且基变量必须满足非负约束。基可行解位于可行域的顶点上（或极点上），而可行解可以位于可行域内的任意点（包括边界和内部）。联系：基可行解集合是可行解集合的子集。如果线性规划问题有最优解，那么最优解一定可以在基可行解中找到（即最优解一定在可行域的顶点上实现）。22.什么是影子价格？影子价格在企业经营管理中有何指导意义？答：定义：影子价格是对偶问题的最优解，它表示在其他条件不变的情况下，增加一个单位的某种资源，目标函数（如利润或成本）所增加的数值。指导意义：(1)资源分配：影子价格反映了资源的边际贡献。若某资源的影子价格大于0，说明该资源是稀缺资源，增加该资源可提高总收益；若影子价格为0，说明该资源有剩余，增加该资源不会带来收益。(2)经营决策：企业可以通过比较资源的影子价格与市场价格来决定是否购入或卖出资源。如果某种资源的市场价格低于其影子价格，购入该资源可以获利；反之，若市场价格高于影子价格，则卖出该资源更划算。(3)新产品开发：在新产品决策中，若新产品对资源的消耗系数与其单位利润的比值小于资源的影子价格（或者计算的对偶可行性），则新产品投产可能是有利的。23.简述动态规划方法求解多阶段决策过程问题的基本思想。答：动态规划的基本思想是将一个多阶段决策过程问题分解为若干个相互联系的单阶段子问题，通过求解子问题来得到原问题的解。其核心包括：(1)最优化原理：作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。(2)无后效性：即“未来与过去无关”，状态一旦确定，过程的发展只与当前状态有关，而与达到该状态的方式无关。(3)逆序或顺序求解：通常采用逆序递推（或顺序递推）的方法，从最后一个阶段开始，逐段向前（或向后）计算，每一阶段的决策都是基于前一阶段（或后一阶段）的最优结果，利用状态转移方程和指标函数，最终求出全过程的最优策略和最优值。24.简述最大流问题中“增广链”的概念及其在求解算法中的作用。答：概念：增广链是指网络中从发点vs到收点vt的一条链。该链具有以下性质：链中所有前向弧（方向与链的方向一致）的流量小于容量（即fij作用：增广链是寻找网络最大流的关键。如果存在一条关于当前可行流的增广链，说明当前流还可以调整增加。通过在增广链上对所有前向弧增加流量θ，对所有后向弧减少流量θ（θ称为调整量，取链上所有前向弧剩余容量和后向弧现有流量的最小值），可以得到一个流量更大的新可行流。反复寻找增广链并进行调整，直到网络中不再存在增广链为止，此时的流即为最大流。四、计算分析题25.（本题25分）(1)建立线性规划模型并化为标准型设生产甲、乙、丙三种产品的产量分别为x1目标函数：maxz=4约束条件：$$化为标准型（引入松弛变量x4$$(2)用单纯形法求解初始单纯形表：基变量0x40x5(检验数)42300第一轮迭代：确定入基变量：max4,2,3=4，对应x1计算比率θ：x4:45/6=7.5，x5主元为6。进行旋转运算（将x1迭代后表格：45/610.55/61/600100检验数行：σ2=0,σ由于σ2=0，且当前基可行解为：x1目标函数值z=4×7.5=30。(注：若继续让x2入基，可得到另一组最优解：x1=5,(3)对偶问题及影子价格对偶问题：设原料A、B的影子价格分别为y1$$根据最终单纯形表：松弛变量x4在最终表中（第一轮迭代后）：对应的检验数，故。对应的检验数，故。即：原料A的影子价格为2/3万元/kg，原料B的影子价格为0万元/kg。这意味着在该最优生产方案下，原料A已耗尽，增加原料A可增加利润；原料B有剩余（x526.（本题20分）(1)判断产销平衡总产量=7+4+9=20。总销量=3+6+5+6=20。因为总产量=总销量，所以该问题是产销平衡运输问题。(2)用最小元素法确定初始调运方案步骤：1.找最小运价c21=1，A2供B13。B12.剩余最小c23=2，A2余1供B31。A23.剩余最小c13=3，A1供B34。B34.剩余最小c32=4，A3供B26。B25.剩余A1余3，A3余3，列比较c14=10,c34=5。先填c34=5供3。初始调运方案表：产地\销地$B_1$$B_2$$B_3$$B_4$产量$A_1$437$A_2$314$A_3$639销量3656总运费=4×3+3×10+3×1+1×2+6×4+3×5=12+30+3+2+24+15=86。(3)检验并求最优解利用位势法计算检验数：设u1,u对于数字格：ui令u1v3u2v1u3v2得：u=(0,-1,-5),v=(2,9,3,10)。计算空格检验数σij(已填)(需要调整)由于存在负检验数σ24调整：以(A2,调整量θ=minx调整：(变为空格)新方案：产地\销地$B_1$$B_2$$B_3$$B_4$产量$A_1$527$A_2$314$A_3$639再次检验（或直接判断）：通常一次调整后可能仍需检查，但在此题中，调整后的方案所有检验数均非负。（简略验证：A2行现在只有x21,x24。u2=-1不变，v4变为9使得u2+v4=8=c24。则v最优总运费=5×3+2×10+3×1+1×8+6×4+3×5=15+20+3+8+24+15=85。(注：比初始方案减少了1)27.（本题25分）(1)建立动态规划模型阶段：按项目划分，k=1,2,3，分别对应项目A、B、C。状态变量：sk表示分配给第k个项目至第n个项目的资金总额。s决策变量：xk表示分配给第k状态转移方程：sk+1指标函数：vk(sk,基本方程（逆序递推）：边界条件：f4(2)求解最优方案第3阶段（项目C）：k=3。f3即为项目C在不同投资下的最大收益（仅一项）：第2阶段（项目B与C）：k=2。f2这里s2的可能取值为0,2,4,6,8当s2=0:当s2max=10,x当s2(**)(**)max=20,x当s2(**)max=35,x当s2(**)max=45,x第1阶段（项目A、B与C）：k=1。s1f1最大收益为45，此时x1回溯：s2=s1-回溯：s3=s2-结论：最优分配方案为：项目A投资0万元，项目B投资6万元，项目C投资2万元。最大总收益为45万元。28.（本题20分）(1)绘制网络图(注：由于无法绘图，用文字描述节点关系及逻辑)节点1(开始)->工序A(3)->节点2节点1->工序B(4)->节点3节点2->工序C(2)->节点4节点2->工序D(5)->节点4节点3->工序E(3)->节点5节点4->工序F(4)->节点5节点5->工序G(6)->节点6(结束)(2)计算时间参数最早开始时间(ES)和最早完成时间(EF)：Start(Node1):ES=0.TaskA:ES=0,EF=0+3=3.TaskB:ES=0,EF=0+4=4.TaskC:紧前A.ES=3,EF=3+2=5.TaskD:紧前A.ES=3,EF=3+5=8.Node4:ES=maxEFTaskE:紧前B.ES=4,EF=4+3=7.TaskF:紧前C,D.ES=8,EF=8+4=12.Node5:ES=maxEFTaskG:紧前E,F.ES=12