石家庄铁道大学2023-2024学年运筹学期末试卷
题号
一
二
三
四
五
总分
得分
一、填空题（每题3分，共15分）
线性规划问题的标准型要求目标函数为________，约束条件均为________，决策变量非负。
运输问题中，若总产量大于总销量，需引入________虚拟销地，其单位运价设为________。
动态规划的基本方程为________，其核心思想是将多阶段决策问题转化为________。
图论中，最小生成树的求解方法包括________和________。
排队论的基本模型由输入过程、________和________三个要素构成。
二、名词解释（每题5分，共20分）
单纯形法
（要求：解释其在线性规划中的作用，说明基变量与非基变量的转换逻辑）
影子价格
（要求：结合对偶理论，说明其经济含义及在资源分配中的应用）
匈牙利算法
（要求：阐述其适用的问题类型，对比与表上作业法的区别）
状态转移方程
（要求：说明其在动态规划中的地位，举例说明状态变量的定义）
三、简答题（每题10分，共30分）
简述线性规划对偶问题的性质及实际意义。
（要求：结合“原问题与对偶问题最优解关系”说明其对决策的指导作用）
比较动态规划与线性规划的适用场景。
（要求：从问题结构、决策阶段、约束条件三个维度展开）
分析运输问题中“退化”现象的成因及解决方法。
（要求：结合最小元素法与位势法，说明如何避免或处理退化）
四、计算题（每题12分，共24分）
某工厂生产甲、乙两种产品，需消耗A、B、C三种资源。
已知：
甲产品每单位消耗A资源3kg、B资源2m、C资源1小时，利润50元；
乙产品每单位消耗A资源2kg、B资源3m、C资源2小时，利润80元；
每日可用资源量：A180kg，B150m，C100小时。
要求：
（1）建立线性规划模型，求利润最大化的生产方案；
（2）若C资源可增加至120小时，分析最优解的变化。
某公司需将货物从3个产地运往4个销地，运输成本及供需量如下表：
销地
1
2
3
4
产量
产地1
6
4
8
5
20
产地2
3
7
2
9
25
产地3
5
1
6
4
30
销量
15
20
18
22
—
要求：
（1）判断是否为产销平衡问题，若不平衡需调整模型；
（2）用最小元素法求初始运输方案，并计算总运费。
五、应用题（共11分）
某物流企业需规划配送路线，从起点A到终点F的网络节点及距离（km）如下：
A→B（5），A→C（7）
B→D（4），B→E（6）
C→D（3），C→E（8）
D→F（9），E→F（2）
要求：
用Dijkstra算法求A到F的最短路径及距离。
若E→F路段因施工封闭，重新规划路径并计算新最短距离。