运筹学2015年学年第二学期
期末考试题(a卷)
注意事项:
1、 答题前,考生务必将自己的姓名、班级填写在答题卡上 2、 答案用钢笔或圆珠笔写在答题卡上,答在试卷上不给分 3、 考试结束,将试卷和答题卡一并交回。
单项选择题(每小题1分,共10分)
在下面的数学模型中,属于线性规划模型的为( 1:
)
max S =4X +Y A. { st. XY <3
min S=3X 十丫
B.s.t. 2X -丫 工一1 <
[ X,Y A0
X, Y X0
max S = XC.{ s.t. X —Y 兰 2
X,Y Z0 1
2
2 2
+Y2
min S=2XY st. X +Y 33 D.
X,Y ±0
2. 线性规划冋题若有最优解, 则 ?定可以在可行域的 ( )上达到。
内点 B ?顶点 C .外点 A.
在线性规划模型中, 没有非负约束的变量称为 3:
多余变量 A.
)
零个
D (
)
.几何点
B .松弛变量 C. 自由变量 D .人工变量
4:若线性规划问题的最优解同时在可行解域的两个顶点处达到,那么该线性规划问题最优 解为(A.两个
C. C
无穷多个
D.
有限多个 .解的分量个数
5: 原问题与对偶问题的最优(
?目标值 B A. 解
B
)相同。
.解结构
D
定为 (
6: 若原冋题中 Xi为自由变量, 那么对偶问题中的第 i个约束
)
A.等式约束 B .“W ”型约束 C ”约束
D .无法确定 7:若运输问题已求得最优解,此时所求出的检验数一定是全部 ( )
A.小于或等于零 B .大于零
C .小于零 D ■大于或等于零
&对于m个发点、n个收点的运输问题,叙述错误的是
()
A.该问题的系数矩阵有 mX n列
m+n-1
)
B.该问题的系数矩阵有 m+n行 D.该问题的最优解必唯一
C.该问题的系数矩阵的秩必为
9:关于动态规划问题的下列命题中错误的是( A、动态规划分阶段顺序不同,则结果不同 B状态对决策有B状态对决策有影响
C动态规划中,定义状态时应保证在各个阶段中所做决策的相对独立性
影响 D动态规划的求解过程都可以用列表形式实现 10:若P为网络 G的一条流量增广链,则 A.对边
B
.饱和边
P中所有正向弧都为
邻边
6的(
.不饱和边
C
.
D
二、判断题(每小题1分,共10 分)
1:图解法和单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的。 2:单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
(V)
(X )
3: —旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中 删除,而不影响
计算结果。
(V )
4:若线性规划问题中的
bi,Cj值同时发生改变,反映到最终单纯形表中,不会出现原问题
(X)
(V )
(X )
(V )
与对偶问题均为非可行基的情况。
5:若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多最优解。 6:运输问题的表上作业法实质上就是求解运输问题的单纯形法。 7:对于动态规划问题,应用顺推或逆推解法可能会得出不同的最优解。
&动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 决策问题。(V ) 9:图论中的图不仅反映了研究对象之间的关系,而且是真实图形的写照,因而对图中点与 点的相对位置、点
与点连线的长短曲直等都要严格注意。
(X ) (X )
10:网络最短路线问题和最短树问题实质上是一个问题。
三、填空题(每空1分,共15分)
1:线性规划中,满足非负条件的基本解称为 —基本可行解 ______________ ,对应的基称为 ―可行基 2:线性规划的目标函数的系数是其对偶问题的
问题,则对偶问题为 —最小化问题 __________ 。
—右端常数 _______ ;而若线性规划为最大化
3:在运输问题模型中,
m + n-1个变量构成基变量的充要条件是 __不含闭回路 _____________ 。
4:动态规划方法的步骤可以总结为:逆序求解 ___________ 最优目标函数 _____ ,顺序求 _____ 最优策
略、 _____ 、— 最优路线 _______ 和—最优目标函数值 _________ 。
5: 工程路线问题也称为最短路问题,根据问题的不同分为定步数问题和不定步数问题;对
不定步数问题,用迭代法求解,有 _________ 函数 ____ 迭代法和 _____ 策略 _____ 迭代法两种方法。
6:在图论方法中,通常用 ________ 点 ____ 表示人们研究的对象,用 —边 ___________ 表示对象之间的
某种联系。
7: 一个 ______ 无圈__且 ______ 连通 _____ 的图称为树。
四、计算题(每小题 15分,45 分) 1:考虑线性规划问题:
max z = 2x 4x2 3x3
\! +4x2 +2x3 兰 60 2音 + x2 +2x3 兰 40 s. t. 捲+ 3冷+ 2x3兰80
为,X2,x3 _0
(a写出其对偶问题; ): (b用单纯形方法求解原问题; ):
(c用对偶单纯形方法求解其对偶问题; ): (d比较(b)( c)计算结果。
): a ):其对偶问题为 1:解
min z=60y)+40y2
+80y3 ”3% +2y? + y3
X2 s. t. < 4% + y^ 3y^ 4
2% +2y2 +2y3 2 3
分)
b):用单纯形方法求解原问题时每步迭代结果: 原问题解 第一步 第二步 第三步 (0, 0, 0, 60, 40, 80) (0, 15, 0, 0, 25, 35) (0,20/3,50/3,0,0,80/3 ) ------ (5 分) c):用对偶单纯形方法求解对偶问题时每步迭代结果: 对偶问题问题解 第一步 第二步 第三步
(0, 0,0, -2,-4,-3 ) (1,0,0,1,0,-1) (5/6,2/3,0,11/6,0,0) (5 分)
d):对偶问题的实质是将单纯形法应用于对偶问题的求解,
此(b)、(c)的计算结果完全相同。 分)
又对偶问题的对偶即原问题, ----- (2
因
2:某公司打算在三个不同的地区设置
的地区设置不同数量的销售店,
4个销售点,根据市场预测部门的估计,在不同
每月可得到的利润如下表所示。试问各个地区应如何设置销
区