西工大运筹学往年试题及答案参考

西工大运筹学往年试题及答案参考

一、单选题（每题2分，共20分）

1.下列方法中，不属于确定性算法的是（）A.线性规划单纯形法B.动态规划Bellman方程法C.蒙特卡洛模拟法D.整数规划分支定界法【答案】C【解析】蒙特卡洛模拟法属于随机算法，其余均为确定性算法

2.在图论中，表示从顶点u到顶点v存在一条边的符号是（）A.u,vB.u,vC.arcu,vD.adju,v【答案】A【解析】u,v表示有向边，u,v表示无向边，arcu,v和adju,v非标准符号

3.以下关于凸集的描述，错误的是（）A.凸集的任意两点连线仍在集合内B.空集是凸集C.闭圆盘是凸集D.圆环不是凸集【答案】无错误项【解析】A、B、C、D均为凸集性质的正确描述

4.运输问题的对偶变量xij的取值范围是（）A.任意实数B.非负实数C.任意整数D.0或1【答案】B【解析】运输问题中每个决策变量都表示运输量，必须非负

5.当线性规划问题的检验数全为非正时，说明（）A.问题无解B.已达到最优解C.存在退化解D.需要调整初始基【答案】B【解析】单纯形法中检验数全非正表示已达到最优解

6.整数规划与线性规划的差别在于（）A.目标函数系数不同B.约束条件不同C.变量取值要求不同D.求解方法不同【答案】C【解析】整数规划要求部分或全部变量取整数值

7.网络最大流问题中，增广路径上的流量调整应满足（）A.上界约束B.下界约束C.容量约束D.以上都是【答案】D【解析】增广路径流量必须小于等于剩余容量且大于等于下界

8.以下算法中，属于贪心算法的是（）A.动态规划B.分支定界C.回溯法D.最短路径Dijkstra算法【答案】D【解析】Dijkstra算法通过局部最优选择得到全局最优解

9.排队论中，M/M/1模型表示（）A.单服务台、泊松到达、指数服务B.多服务台、泊松到达、指数服务C.单服务台、定长到达、指数服务D.多服务台、定长到达、指数服务【答案】A【解析】M/M/1是排队论经典模型，M表示泊松到达、指数服务

10.0-1背包问题的决策变量取值范围是（）A.[0,1]B.{0,1}C.非负实数D.任意整数【答案】B【解析】0-1背包问题变量只能取0或1

二、多选题（每题4分，共20分）

1.以下属于图论基本概念的有（）A.路径B.回路C.树D.连通性E.网络流【答案】A、B、C、D【解析】E网络流属于网络流理论范畴，非图论基本概念

2.线性规划单纯形法可能出现的情况有（）A.唯一最优解B.无穷多最优解C.无界解D.无解E.退化解【答案】A、B、C、D、E【解析】以上均为单纯形法可能出现的情形

3.以下属于动态规划特点的有（）A.最优子结构B.重叠子问题C.递归关系D.贪心选择E.分治策略【答案】A、B、C【解析】D贪心、E分治是其他算法特点

4.网络流问题中，流量的性质包括（）A.守恒性B.可行性C.对称性D.连续性E.可加性【答案】A、B、E【解析】C对称性非流量的基本性质

5.以下算法属于回溯法应用的有（）A.0-1背包问题B.旅行商问题C.最大割问题D.图的着色E.整数规划【答案】A、B、D、E【解析】C最大割问题通常用网络流方法求解

三、填空题（每空2分，共16分）

1.线性规划问题的对偶理论表明，原问题的对偶问题的最优值等于______的最优值【答案】原问题（8分）

2.图G的邻接矩阵A中，aij表示从顶点i到顶点j的______【答案】有向边数量（2分）

3.动态规划的基本要素包括最优子结构、______和最优决策【答案】重叠子问题（2分）

4.排队论中，M/G/1模型表示______、定长服务时间和单服务台【答案】泊松到达（2分）

5.整数规划分为______和混合整数规划【答案】0-1整数规划（2分）

四、判断题（每题2分，共10分）

1.线性规划问题的可行解一定在可行域的顶点上（）【答案】（×）【解析】可行解可能在边界上，不一定在顶点

2.最大流问题中，增广路径上的流量可以超过容量限制（）【答案】（×）【解析】增广路径流量必须小于等于剩余容量

3.0-1背包问题可以用动态规划求解，也可以用分支定界法求解（）【答案】（√）【解析】两种方法均可有效求解该问题

4.图论中的最小生成树问题可以用Dijkstra算法求解（）【答案】（×）【解析】最小生成树应使用Prim或Kruskal算法

5.排队论中，M/M/c模型表示多服务台、泊松到达和指数服务（）【答案】（√）【解析】c表示服务台数量，M表示泊松到达和指数服务

五、简答题（每题4分，共12分）

1.简述线性规划单纯形法的原理【答案】单纯形法通过从可行域的一个顶点开始，沿着边界移动到相邻顶点，每次移动都使目标函数值得到改善，直到找到最优解其核心思想是

（1）从初始基本可行解出发

（2）判断当前解是否最优（检验数）

（3）若最优则停止，否则选择入基变量和出基变量

（4）进行基变换得到新基本可行解

（5）重复上述过程直到最优

2.解释动态规划的重叠子问题特性【答案】动态规划的重叠子问题特性指在求解过程中，很多相同的子问题会被多次计算这种特性导致直接递归实现效率低下，因此需要

（1）记录已计算子问题结果（备忘录）

（2）从底向上计算（自底向上）

（3）避免重复计算，从而提高效率

3.比较M/M/1模型与M/G/1模型的区别【答案】区别主要在于服务时间的分布

（1）M/M/1服务时间服从参数为μ的负指数分布（指数服务）

（2）M/G/1服务时间服从任意分布（G表示一般分布）其他相同泊松到达、单服务台M/G/1模型更通用但计算复杂度更高

六、分析题（每题8分，共16分）

1.分析运输问题的对偶解经济意义【答案】运输问题的对偶变量yi表示产地i的容量限制每单位变化的影子价格，xij的影子价格表示销地j的需求限制每单位变化的影子价格经济意义包括

（1）yi表示增加产地i产能的边际收益

（2）xij表示增加销地j需求的价值

（3）对偶最优解提供资源分配的指导

（4）对偶变量满足互补松弛条件，可用于灵敏度分析

2.解释最大流问题中增广路径的确定方法【答案】最大流问题增广路径的确定方法

（1）从源点S开始，在残余网络中寻找从S到汇点T的可行路径

（2）路径上所有边的容量必须大于0（剩余容量大于0）

（3）路径上的最小剩余容量即为该路径可增加的流量

（4）沿该路径增加流量，更新残余网络

（5）重复直到找不到增广路径该方法基于Ford-Fulkerson算法，通过不断寻找增广路径逐步增大流量

七、综合应用题（20分）某公司有3个工厂生产同一种产品，供应4个销售点工厂产量、销售点需求及单位运输成本如下表||销售点1|销售点2|销售点3|产量||------|--------|--------|--------|------||工厂1|3|5|7|50||工厂2|4|6|8|60||工厂3|2|4|6|70||需求|40|50|60||

（1）建立该问题的线性规划模型（设变量为工厂i到销售点j的运输量）

（2）若工厂1到销售点3的运输成本改为6，最优解如何变化？

（3）分析对偶解的经济意义【答案】

（1）模型建立决策变量xij表示工厂i到销售点j的运输量（i=1,2,3;j=1,2,3,4）目标函数minZ=3x11+5x12+7x13+4x21+6x22+8x23+2x31+4x32+6x33约束条件供应约束x11+x12+x13+x14≤50（工厂1）x21+x22+x23+x24≤60（工厂2）x31+x32+x33+x34≤70（工厂3）需求约束x11+x21+x31≥40（销售点1）x12+x22+x32≥50（销售点2）x13+x23+x33≥60（销售点3）xij≥0（所有变量非负）

（2）成本改变后的最优解变化若c13=6，最优解可能变化需要重新求解模型，但根据对偶理论新目标函数值将增加（6-7）x13=|-x13|=x13，即运输工厂1到销售点3的量越多损失越大若最优解中x130，则总成本会增加；若x13=0，则总成本不变

（3）对偶解经济意义对偶变量yi表示工厂i产能每单位增加的边际收益，xij表示销售点j需求每单位增加的价值具体y1增加工厂1产能的收益y2增加工厂2产能的收益y3增加工厂3产能的收益xij满足销售点j需求的价值（如需求增加1单位带来的收益）对偶解可用于资源分配决策和需求管理。