2016年重庆大学机械工程学院运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 己知有向图如图所示。
图
孤上数字为网络容量。现欲求节点1到节点7的最大流。 （l ）写出求解该问题的线性规划模型。 （2）用标号法求解。
【答案】（l ）该问题的线性规划模型如下:
（2） （l ）V 1点标号 V2的邻点 V3标号 V5的邻点 V7标号
得一条增广链（3）V 1标号得一条增广链（4）
V1得二条增广链（5）（6）
其他点不能再标号
标号结束
V 3标号
V6标号
V7标号
（2）V 1的邻点 V 2
标号
得最小割集
2． 一个建筑工地现场，如图所示，其中A 、…、G 表示的是需要混凝土的施工点，路径则是允许 运送混凝土的路线，线旁的数字表明相应路径的距离。
图
请在A~G这7个点中，选择一个搅拌混凝土的地方，使得该点到达基他各需要混凝土施工点的总运送距离 之和最短
【答案】首先采用矩阵算法，计算任意两个点的最短距离。 设
为图中相邻两点的距离，得到初始矩阵如下:
经过迭代3次，得到网络图中从的最短距离，可得矩阵D ，如下:
3
因此，可以确定分别从A ，B ，C ，…，G 出发，到达所有点的最短距离和分别为:
故应将混凝土搅拌地选在F 点。
3． 某公司需要对某产品决定未来半年内每个月的最佳存储量，以使总费用极小化。已知半年里对该产品 的需求量和单位订货费用、单位存储费用的数据，如表所示。
表
【答案】按月份将问题划分为6个阶段，阶段变量k=1，2，3，…，6。状态变量s k 为第k 阶段开始时的产品存储量， 决策变量u k 为第k 阶段的订货量，d k 为第k 阶段的需求量。状态转移方程:
; 允许决策集合为:
最优值函数
为第k 阶段开始存储量为
时，从第1阶段至第k 阶段的最小存储费用。c
（j , i）（j≤ i）为 从阶段j 到阶段i 的总成本，利用再生产点性质求答: （1）由
，计算c （j , i）:
=175425
=213425
=243125
（2）按照递推关系式，有
=124125