《运筹学》试题
- 格式：pdf
- 大小：382.52 KB
- 文档页数：6
《运筹学》试题
一、名词解释（20分）
对偶可行基
影子价格 灵敏度分析 平衡运输问题 不平衡运输问题 纯整数规划 0—1规划问题
混合整数规划
网络
最大流问题
二、选择题（20分） 1、我们可以通过（ ）来验证模型最优解。
A观察 B应用 C实验 D调查
2、建立运筹学模型的过程不包括（ ）阶段。
A观察环境 B数据分析 C模型设计 D模型实施
3、建立模型的一个基本理由是去揭晓那些重要的或有关的（ ）
A数量 B变量 C 约束条件 D 目标函数
4、模型中要求变量取值（ ）
A可正 B可负 C非正 D非负
5、运筹学研究和解决问题的效果具有（ ）
A 连续性 B 整体性 C 阶段性 D 再生性
6、如果线性规划问题有可行解，那么该解必须满足（ ）
A 所有约束条件 B 变量取值非负 C 所有等式要求 D 所有不等式要求
7、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在（ ）集合中进行搜索即可得到最
优解。
A 基 B 基本解 C 基可行解 D 可行域
8、线性规划问题是针对（ ）求极值问题.
A约束 B决策变量 C 秩 D目标函数
9、如果第K个约束条件是“≤”情形，若化为标准形式，需要（ ）
A左边增加一个变量 B右边增加一个变量 C左边减去一个变量D右边减去一个变量
10、若某个bk≤0, 化为标准形式时原不等式（ ） A 不变 B 左端乘负1 C 右端乘负1 D 两边乘负1
三、填空题（20分） 1、线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求（ ）的线性规划问题与之对应，反之亦然。 2、在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的（ ）。 3、如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为（ ）。 4、对偶问题的对偶问题是（ ）。 5、若原问题可行，但目标函数无界，则对偶问题（ ）。 6、在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值是（ ）(设原最优目标函数值为Z﹡) 7、若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用（ ）求解。 8、已知线性规划问题，最优基为B，目标系数为CB，若新增变量xt，目标系数为ct，系数列向量为Pt，则当（ ）时，xt不能进入基底。 9、如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个（ ）。 10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加（ ）。
四、计算题（40分）
（一）按各题要求。建立线性规划数学模型
1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单
位产品的利润如下表所示：
根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120
件。月销售分别为250，280和120件。 问如何安排生产计划，使总利润最大。
2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的
钢筋60根，问怎样下料，才能使所使用的原材料最省?
（二）下列整数规划问题
说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。
（三）下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路
的总长度最小，应如何做?最小的总长度是多少?
（四）某旅游者要从A地出发到终点F，他事先得到的路线图如下：
各点之间的距离如上图所示数值，旅游者沿着箭头方向行走总能走到F地，
试找出A→F间的最短路线及距离。
《运筹学》复习题答案
一、名词解释
对偶可行基：凡满足条件δ=C-CBB-1A≤0的基B称为对偶可行基。
影子价格：对偶变量Yi表示与原问题的第i个约束条件相对应的资源的影子价格，在数量上表现为，当该
约束条件的右端常数增加一个单位时（假设原问题的最优解不变），原问题目标函数最优值增加的数量。 灵敏度分析：研究线性规划模型的原始数据变化对最优解产生的影响 平衡运输问题：m个供应地的供应量等于n个需求地的总需求量，这样的运输问题称平衡运输问题。 不平衡运输问题：m个供应地的供应量不等于n个需求地的总需求量，这样的运输问题称不平衡运输问题。 纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。 0—1规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或1，这样的问题称为0—1规划。
混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。 网络：在图论中，给边或有向边赋了权的图称为网络
最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的最大流量
二、选择题
1、C 2、A 3、B 4、D 5、A
6、D 7、D 8、D 9、B 10、D
4 3
7 3 5 1 9
1
2
5 7 9 6 2 4
2 4
4 6 8 5
1 5
4
5
4 A B1
B2
B3 C1
C2
C3 D1
D2
D3 E1
E2 F 三、填空题 1、最小值/极小值 2、目标函数系数 3、等式 4、原问题 5、不可行 6、Z*+yi△b 7、对偶单纯形法 8、Ct≤CBB－1Pt 9、变量。 10、一行，一列。 四、计算题 （一）
（二） 答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。 七、若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1)在s1，s2，S4中至多只能选择两个； (2)在S5，s6中至少选择一个；(3)在s3，s6，S7，S8中至少选择两个； 试建立这个问题的整数规划模型
（三）
（七）
解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：
1
7 3 4 3
2 0 1
2
5 7 9 6 2 4
2 4
4 6 8 5
1 5
4
5
4 A B1
B2
B3 C1
C2
C3 D1
D2
D3 E1
E2 F 5 9
1 4
7
7 11
8 5
9
12 14
14
最佳策略为：A→B2→C1→D1→E2→F
此时的最短距离为5+4+1+2+2=14
