2015 年重庆工商大学运筹学考研真题 A 卷
一、判断题(判断下列说法是否正确,请将“正确”与“错误”的判断结果按照题号
顺序写在答题纸上。本大题共 10 小题,每小题 2 分,共 20 分)
1、线性规划问题的图解法和单纯形法虽然求解的形式不同,但从几何上理解,两者是
一致的。
2、线性规划问题的基可行解 X 对应可行域 D 的顶点。
3、在单纯形法计算中,如不按照最小原则选取换出变量,则在下一个解中至少有一个
基变量的值为负。
4、运输问题是一种特殊的线性规划问题,因而求解结果也可能出现下列四种情况之一:
有唯一最优解、有无穷多最优解、无界解、无可行解。
5、如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数 k ,最优调
运方案将不会发生变化。
6、用割平面法求解整数规划问题时,所构造的割平面有可能切去一些不属于最优解的
整数解。
7、指派问题效率矩阵的每一个元素都乘上同一个常数 k ,将不影响最优指派方案。
8、假定 ix 为 0-1 变量,则
表示做第i 件事的充要条件是不做第 j 件事。
x
i
1
x
j
9、如果图中某一点 iv 有若干个相邻点,与其距离最远的相邻点为 jv ,则边 ,i
v v
必
j
不包含在最小支撑树内。
10、在任一图G 中,当点集V 确定后,树图是G 中边数最少的连通图。
二、简答题(本大题共 2 小题,其中第 1 小题 8 分,第 2 小题 7 分,共 15 分)
1、简述线性规划数学模型的结构及各要素的特征。
2、简述最小费用最大流的概念及其求解最小费用最大流问题的基本思想和方法。
三、建模题(建立下列问题的线性规划模型,不需要求解。本大题共 25 分)
某饲料厂用三种原材料 I、II、III 混合调配出三种不同规格的精饲料产品 A、B、C。
已知产品的规格要求、单位产品的加工费用和销售单价,每天能供应的原材料数量及原材
料单价见下表,该饲料厂应该如何安排生产才能使利润最大?
原材料
A
B
C
Ⅰ
Ⅱ
Ⅲ
≥60%
≥15%
≤20%
≤60%
≤50%
原材料价格
(元/千克)
每天限制用量
(千克)
2.00
1.50
1.00
2000
2500
1200
加工费(元/千克) 0.50
售价(元/千克)
3.40
0.40
2.85
0.30
2.25
四、计算题(本大题共 4 小题,第 1、2、3 小题各 25 分,第 4 小题 15 分,共 90 分)
1、下表是某求极大化线性规划问题得到的单纯形表,表中无人工变量, 1a 、 2a 、 3a 、
d 、 1c 、 2c 为待定常数。试确定这些常数分别取何值时,以下结论成立:
(1)表中解为唯一最优解;
(2)表中解为最优解,但存在无穷多最优解;
(3)表中解为退化的可行解;
(4)表中解非最优,下一步迭代将以 1x 替换基变量 6x ;
(5)该线性规划问题具有无界解;
(6)该线性规划问题无可行解。
2x
1a
—3
1x
4
b
d
2
基
3x
4x
6x
3
z
j
c
j
—1
3a
1c
—5
2c
3x
1
0
0
0
4x
0
1
0
0
5x
2a
—1
—4
—3
6x
0
0
1
0
2、现有一运输问题,产量、销量及单位运输价格如下表所示,试求最优调运方案。
销地
产地
A
B
C
D
销量
甲
10
2
1
8
4
乙
20
10
20
6
4
丙
5
8
7
3
6
丁
9
30
10
7
2
戊
10
6
4
5
4
产量
5
6
2
9
3、分配甲、乙、丙、丁、戊五人去完成 A、B、C、D、E 五项任务,要求每个人只能承
担一项任务,每项任务只能由一个人承担。每个人完成各项任务的时间(单位:小时)如
下表所示。试确定最优的任务指派方案,使完成任务的总时间最少。
任务
人
甲
乙
丙
丁
戊
A
12
8
7
15
4
B
7
9
17
14
10
C
9
6
12
6
7
D
7
6
14
6
10
E
9
6
9
10
9
4、求下列赋权有向图中 1v 到 7v 的最短路。
v1
5
2
v2
3
v3
—1
2
3
1
4
v4
—6
v5
v6
7
5
3
v7