浙江理工大学继续教育学院2015学年第一学期
《管理运筹学》试卷(A 卷)
考试时间:120分钟 闭卷 任课老师:
班级: 学号: 姓名: 成绩:
一、判断题(10×3’) 1.若
1X ,2X 分别是某一线性规划问题的最优解,则1122X X X λλ=+也是该线性
规划问题的最优解,其中
12,λλ为正的实数。
( )
2. 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量,将使目标
函数值得到最快的增长。( )
3.线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。( ) 4. 根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,当对偶问题无可行解时,其原问题具有无界解。( )
5.若某种资源的影子价格等于k ,在其它条件不变的情况下,当改种资源增加5个单位时,相应的目标函数值将增大5k 。( )
6. 在运输问题中,只要给出一组含(m +N -1)个非零的
ij
x ,且满足
1
n
ij
i
j x
a ==∑,
1
m
ij
j
i x
b ==∑,就可以作为一个初始基可行解。( )
7. 运输问题的数学模型是线性规划模型。( ) 8. 隐枚举法也可以用来求解分配问题。( )
9.任何一个多阶段决策过程的最优化问题,都可以用非线性规划模型来描述。( ) 10. 在PERT 网络图中只能存在一个始点和一个终点。( ) 二.填空题(5×2’)
11. 图的组成要素 ; 。 12. 求最小树的方法有 、 。
13. 线性规划解的情形有 、 、 、 。 14. 求解指派问题的方法是 。
15. 按决策环境分类,将决策问题分为 、 、 。
三.简答题(5×6’)
16. 试述线性规划数学模型的组成部分及其特征。
17. 树具有哪些基本性质?
18. 用图解法说明线性规划问题单纯形法的解题思想。
19. 运输问题是特殊的线性规划问题,但为什么不用单纯形法求解。
20. 建立动态规划模型时,应定义状态变量,请说明状态变量的特点。
三.计算题(2×10’)
21. 已知线性规划问题:
Max z=3X1+2X2
-X1+2X2≤4
3X1+2X2≤14
X1-X2≤3
X1, X2≥0
要求:(1)、写出它的对偶问题;
(2)、找出原问题和对偶问题的一个可行解;
(3)、应用对偶理论证明原问题和对偶问题都存在最优解。
22. 已知一个线性规划原问题如下,写出对应的对偶模型。
21max 6x x S +=
???
??≥≥+≤+0,163272
12121x x x x x x
四.应用题(2×10’)
23. 某地准备投资D 元建民用住宅。可以建住宅的地段有n 处:12,,A A …,n A 。在
j A 处每处住宅的造价为i d ,最多可造j a 幢。应当在哪几处建住宅,分别建几幢,
才能使住宅总数最多?
24. 某厂准备生产三种产品A、B、C,需消耗劳动力和原料两种资源,其有关数据
如下表:
(1)用单纯形法确定总利润最大的生产计划。
(2)分别求出劳动力和原料的影子价格。若原料不够,可到市场上购买,市场价格为0.8元/单位。问是否要购进,最多可购进多少?总利润增加多少?
管理运筹学试卷A参考答案
一.判断题
1.×.
2.×.
3.√.
4.×.
5.×.
6.√.
7.√.
8.√.
9.√.10.√.
二,填空题
11.树
12.破圈法和避圈法
13.可行解、退化解、无界解、多重解
14.匈牙利法
15.确定性决策,不确定性决策,风险性决策。
三,简答题
16.线性规划数学模型组成:max(min) z =CX
A X≤(=,≥)b
X≥0
线性规划数学模型的特征:(1)用一组决策变量表示某一方案,这组决策变量均为非负的连续变量。(2)存在一定数量(m)的约束条件,这些约束条件可以用关于决策变量的一组线性等式或线性不等式来加以表示。(3)有一个可以用决策变量加以表示的目标函数,而该函数是一个线性函数。
17.树具有的性质:(1)树中任意两顶点间有且仅有一条链。(2)对于一定的点集而言,树是边数最少的连通图。(3)设T是具有p个顶点的一棵树,则T的边数一定为p-1。(4)任意一棵树,至少存在两个悬挂点。
18、在可行域内先确定一个基本可行解,然后通过迭代计算,逐步使目标函数增大(求Z max),求出新解,计算出方案机会成本后,得出相应检验数,当所有的C j–Z j ≤0时即得最优解。
19、运输问题可以用单纯形求解,但由于虚设的变量多,运算复杂,十分不合算,所以不用单纯形法求解,而用简单的表上作业法求解。
20、由于动态规划的求解过程是一个多段决定过程,其状态变量必须满足无后效性和可知性的特征要求。
四.计算题
21.解:(1)、它的对偶问题为:
Min w=4Y1+14Y2+3Y3
–Y1+3Y2+Y3 ≥3
2Y1+2Y2-Y3 ≥2
Y1,Y2,Y3 ≥0
(2)容易看出,原问题存在可行解X=(0,0),对偶问题存在可行解Y=(0,1,0)(3)根据对偶理论的强对偶性,因为原问题和对偶问题都存在可行解,则两者都存在最优解。
22.Z max=-7y1+16y2
???
??≥≤+-≤+-0,13622
12121y y y y y y 五.应用题
23. 设在j A 处建住宅j x 幢(j=1,2,…,n )。
数学模型为 1
1..01,2,,1,2,,n
j
j n
j j j j j j MaxZ x d x D s t x a j n x j n ===?≤???≤≤=??
=???
∑∑ 是整数,
设截取长为j a 的毛坯j x 根(j=1,2,…,n ),使圆钢残料最少的下料问题数学模型为:
211
1
1n
j j j n
j j
j n
j
j z l z a x a x x ====-===∑∑∑23由于是实际用料总长,故问题的目标函数等价于
Maxz 如果要求毛坯总根数最多,则可将目标函数改为Maxz
11
1..01,2,1,2,n
j j
j n
j j j j j Minz l a X a x l s t x j n x j n ===-?≤???≥=??
=???
∑∑ 是整数,
24.(1)该问题的线性规划模型是
123max 35Z x x x =++
1231231236354534530,,0
x x x x x x x x x ++≤++≤≥ 其中123,,x x x 分别为产品A 、B 、C 的产量。
因而最优生产计划为生产A 、B 产品均为0,生产C 产品3x =6,可以使得利润最大,最大利润为30。
(2)劳动力和原料的影子价格分别为0和1。这说明在企业中最优安排中,劳动力资源没有用完,(实际用了30个单位),二原料资源已耗尽。若原料市场价格0.8元/单位<影子价格1元/单位,因此应适量购进原料扩大生产。
设购进的原料数为2b ?,为保持最优基不变,必须有1
0b B b -'=≥,而
给2b 一个增量并利用b B b 1
-='将变化直接反映进最终单纯形表。
1101/5b -??'=??
??
24530b ????+???22
150165b b -???
??
=≥??+???
,解得23015b -≤?≤。 因而最多可以购进
15
单位原料,总利润增加
1
224530(0,1)301530B C B b b b -??
-=-== ?+??
(单位)
,净利润增加15-0.8×15=3(单位)。