运筹学练习题

一、填空题（每题1分,共5分；许圣兰得分:4分）

1、 已知线性规划max

Z=3x1+4x2+x3,x1+2x2+x3≤10,2x1+2x2+x3≤16,x1,x2,x3≥0的最优基为约束条

件系数矩阵的第一、第二两列，则最优解(x1,x2)= (6,2) 。√ +1分

2、 非基变量xj的系数为cj,对应的最终表的检验数为-2,则最优解不变时,cj的允许增量应满足(用不等式表示):Δcj <=2/cj 。×!参考答案:<=2

3、 已知非整数最优解中基变量x1=3.25，x1要求取整数，则添加分枝约束x1<=3

和 x1>=4 。√ +1分

4、 一个可行流为最大流的充要条件是存在一个截集使其截量 等于 网络流的流量。√ +1分

5、 每隔相同时间t0进货一次且每次进货量 都相等 的存贮策略称为t0循环策略。√ +1分

-------------------------------------------------------------------------------------------------------------------------

二、判断题（每题1分,共10分；许圣兰得分:9分）

1、 当你自己建立的 LP 模型无最优解时，一定是模型中存在矛盾的约束条件 (错

误)√ +1分 2、 设X*是min z = CX,AX≥b, X≥0的最优解，Y*是max w =Yb, YA≤C, Y≥0的最优解，则CX*=Y*b (正确)√ +1分

3、 整数规划的可行解集合是离散型集合 (正确)√ +1分

4、 若运输问题中的产量和销量为整数则其最优解也一定为整数。 (错误)√ +1分

5、 μ是一条增广链，则后向弧上满足流量f ≥0。 (错误)√ +1分

6、 指派问题一定有最优解 (正确)√ +1分

7、 (s,S)策略是连续盘存，当存储量降到s时立即提出订货，订货量等于S (错

误)√ +1分

8、 LP 问题的基本可行解对应可行域的顶点。 (错误)×

9、 若某种资源影子价格为零，则该资源一定有剩余。 (错误)√ +1分

10、 在同一存贮模型中，可能既发生存贮费用，又发生短缺费用 (正确)√ +1分

-------------------------------------------------------------------------------------------------------------------------

三、单项选择题（每题1分,共10分；许圣兰得分:7分）

1、 线性规划具有无界解是指

1)、可行解集合无界 选择正确 2)、存在某个检验数＞0,且此检验数所在的列上的系数均不＞0 √ +1分

3)、有相同的最小比值

4)、最优表中所有非基变量的检验数非零 2、 如果决策变量数相等的两个线性规划的最优解相同，则两个线性规划

1)、模型相同

2)、最优目标函数值相等

选择正确 3)、以上结论都不对 √ +1分

4)、约束条件相同 3、 下列说法正确的是

1)、用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最

优解的整数解

2)、用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，

通常可任取其中一个作为下界，再进行比较剪枝

3)、整数规划问题最优值优于其相应的线性规划问题的最优值

选择正确 4)、分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，

在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规

划问题通过分枝迭代求出最优解。 √ +1分 4、 求运输利润最大的运输方案时，若某方案中空格的检验数满足（ ），该方案是最优方案。

1)、均大于0

2)、有一个大于0

选择正确 3)、均小于等于0 √ +1分

4)、有一个小于0 5、 某有线电视台需从现有的道路中选择部分道路架设电缆，使各居民小区都能收到

电视信号，并使总的电缆费用最少。则该问题可以看作一个：

选择 × 1)、最短路问题

2)、最大流问题

正确 3)、最小支撑树问题

4)、最小费用流问题 6、 求最大流的计算方法有

选择正确 1)、Ford-Fulkerson 算法 √ +1分

2)、Floyd 算法

3)、加边法

4)、Dijkstra 算法 7、 在相同的单位时间内,不允许缺货的存贮量比允许缺货时的存贮量

正确 1)、多 选择 × 2)、少

3)、一样

4)、不确定 8、 将一般线性规划模型化为标准形时，自由变量可以用两个非负变量的( )来代换

1)、和

2)、积

选择正确 3)、差 √ +1分

4)、商 9、 用动态规划方法求背包问题时

1)、将背包的容量作为决策

2)、将装载的物品品种数作为一个阶段的决策

选择正确 3)、将装载的物品品种数作为阶段数 √ +1分

4)、将装载的物品件数作为状态 10、 目标函数Max Z,xj为非基变量,若系数向量(cj,a1j,…, amj)变化后最优解不变，

则只需

正确 1)、cj-CBB-1>(a1j,…,amj)'≤0

2)、B-1(a1j,…,amj)'≥0 选择 × 3)、B-1b≥0

4)、CN-CBB-1N≥0

五、应用题(题分:10，许圣兰得分:6) 有五项设计任务可供选择。各项任务的预期完成时间分别为3、8、5、4、10周，

设计报酬分别为7、17、11、9、21万元。设计任务只能一项一项地进行，总的期限

是20周。选择任务时必须满足下面的条件：

（1）至少完成3项设计任务；

（2）若选择任务1，必须同时选择任务2；

（3）任务3和任务4不能同时选择。 应当选择哪些设计任务，才能使总的设计报酬最大？

做题记录： 解:设五项任务分x1,x2,x3,x4,x5.则 max z=7x1+17x2+11x3+9x4+21x5 3x1+8x2+5x3+4x4+10x5<=20 x1+x2<=0 x1+x2>=2 x3+x4=1 x1+x2+x3+x4+x5>=3 xj=0或1,j=1,2,3,4,5 答案： 解：设选择sj时，xj=1, 不选择sj时，xj=0；j=1,2…,5

由题意可得整数规划模型如下： max Z= 7x1+17x2+11x3+9x4+21x5 s.t. x1+x2+x3+x4+x5≥3 x1≤x2 x3+x4≤1 3x1+8x2+5x3+4x4+10x5≤20 xj=0或1 (j =1,2, …5)。

第二份

一、填空题（每题1分,共5分；孙运伟得分:5分）

1、 若一线性规划有多重最优解，则其所有的最优解组成的集合一定为 凸 集。√ +1

分

2、 已知max Z=3x1+4x2+x3,2x1+3x2+x3≤1,x1+2x2+2x3≤3,x1,x2,x3≥0的最

优解为X=(1/2,0,0)'，则第二种资源的影子价格为 0 。√ +1分

3、 用0-1变量x1、x2、x3分别表示A1、A2、A3的选与不选，值为1表示选中，否则为不选，则A1，A2，A3中必须选两个的表达式为 x1+x2+x3=2 。√ +1分

4、 可行流中，源的净发量一定 等于 汇的净收量。√ +1分

5、 从发出订货指令到所订货物进入存贮系统所经历的时间称为 订货提前期 。√ +1

分 -------------------------------------------------------------------------------------------------------------------------

二、判断题（每题1分,共10分；孙运伟得分:8分）

1、 若矩阵B为一可行基,则|B|=0。 (错误)√ +1分

2、 设X*是min z = CX,AX≥b, X≥0的可行解，Y*是max w =Yb, YA≤C, Y≥0的可行解，则有CX*≤Y*b (错误)√ +1分

3、 整数规划的最优解是先求相应的线性规划的最优解然后取整得到 (错误)√ +1分

4、 不平衡运输问题不一定有最优解。 (错误)√ +1分

5、 割集中弧的流量之和称为割量。 (错误)√ +1分

6、 m+n－1个变量构成基变量组的充要条件是它们不包含闭回路。 (正确)√ +1分

7、 接受有折扣的订货量的总成本不一定比经济订货批量的总成本少 (正确)√ +1分

8、 线性规划的最优解一定是基本可行解 (正确)×

9、 过程指标函数是阶段指标函数的函数 (错误)×

10、 在同一存贮模型中，可能既发生存贮费用，又发生短缺费用 (正确)√ +1分

------------------------------------------------------------------------------------------------------------------------- 三、单项选择题（每题1分,共10分；孙运伟得分:7分）

1、 下列叙述正确的是

1)、线性规划问题一定有基可行解

选择正确 2)、线性规划问题，若有最优解，则必有一个基可行解是最优解 √ +1分

3)、线性规划问题的最优解只能在极点上达到

4)、单纯形法求解线性规划问题时每换基迭代一次必使目标函数值下降一次 2、 原问题（求最大化问题）的决策变量xi≥0，则下列描述正确的是

1)、对偶问题的决策变量yi≤0

选择正确 2)、对偶问题的第i个约束条件是“≥” √ +1分

3)、对偶问题的第i个约束条件是“≤”

4)、对偶问题的决策变量yi≥0 3、 对一个求目标函数最大的混合整数规划问题，以下命题中不正确的是：

选择 × 1)、任一可行解的目标函数值不可能大于其松弛问题的目标函数最优值

2)、该问题可行解中可能存在不取整数值的变量

3)、其松弛问题的最优解可能是该整数规划问题的最优解

正确 4)、该问题可行解的个数是有限的 4、 有5个产地4个销地的平衡运输问题