运筹学练习题

一、填空题(每题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、非基变量x j的系数为c j,对应的最终表的检验数为-2,则最优解不变时,c j的允许增量应满足(用不等式表示):Δc j <=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*是m in 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,x j为非基变量,若系数向量(c j,a1j,…, a mj)变化后最优解不变,则只需

正确 1)、c j-C B B-1>(a1j,…,a mj)'≤0

2)、B-1(a1j,…,a mj)'≥0

选择 × 3)、B-1b≥0

4)、C N-C B B-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*是m in 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、原问题(求最大化问题)的决策变量x i≥0,则下列描述正确的是

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

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

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

4)、对偶问题的决策变量y i≥0

3、对一个求目标函数最大的混合整数规划问题,以下命题中不正确的是:

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

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

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

正确 4)、该问题可行解的个数是有限的

4、有5个产地4个销地的平衡运输问题

选择正确 1)、有8个基变量√ +1分

2)、有9个基变量

3)、有20个约束

4)、有9个变量

5、从甲市到乙市之间有一公路网络,为了尽快从甲市驱车赶到乙市,此问题属于:

1)、最小生成树问题

选择正确 2)、最短路问题√ +1分

3)、最大流问题

4)、一笔画问题

6、下列错误的结论是

1)、将指派问题的效率矩阵每行分别加上一个数后最优解不变

选择 × 2)、将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变

3)、指派问题的数学模型是整数规划模型

正确 4)、将指派(分配)问题的效率矩阵每行分别乘以一个非零数后最优解不变7、瞬时供货且允许缺货的经济批量模型中,若订货费、存储费和缺货费同时增加δ倍时,经济订货批量

1)、为原来的1/δ1/2倍

2)、为原来的1/(2δ)1/2

选择正确 3)、不变√ +1分

4)、为原来的δ1/2倍

8、用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为

选择 × 1)、很大的正数

正确 2)、0

3)、1

4)、很大的负数

9、动态规划的逆序法中,f k(s k)表示的是

选择正确 1)、从第k个阶段到最后阶段的最优效益值√ +1分

2)、第k个阶段的最优效益值

3)、从第1阶段到第k阶段的最优效益值

4)、第k个阶段的状态转移方程

10、在制品采用不允许缺货的t0循环策略时,下列哪个参数的单独变化不会使生产间隔期t0缩短

选择正确 1)、单位变动成本K增加√ +1分

2)、单位存贮费C1增加

3)、生产速度P增加

4)、固定成本C3减少

五、应用题(题分:10,孙运伟得分:10)

某航空公司希望更有效地安排售票员的工作时间,以减少工资支出。每个售票员上班后将连续工作8个小时,假定每天的 8:00 至 24:00 为售票工作时间。应该如何计划每个时段初的上班售票员人数,建立售票员总人数最少的数学模型(15分)。

数据资料如下:

运筹学练习题

做题记录:

记录每个阶段所需人数x

min z=x1+x2+x3+x4+x5

x1>=10

x1+x2>=8

x1+x2+x3>=9

x1+x2+x3+x4>=11

x2+x3+x4+x5>=13

x3+x4+x5>=8

x4+x5>=5

x5>=3

xi>0取整

答案:

设xj为第j时段开始来上班的人数(j=1,2,... ,5),(3分)

则模型如下:

min S=x1+x2+x3+x4+x5

s.t. x1≥10

x1+x2≥8

x1+x2+x3≥9

x1+x2+x3+x4≥11

x2+x3+x4+x5≥13

x3+x4+x5≥8

x4+x5≥5

x5≥3

xj≥0 (j =1,2, …5),且为整数。

第三份

一、填空题(每题1分,共5分;安超群得分:5分)

1、线性规划的可行域为凸集。√ +1分

2、一最大化目标的线性规划的第i个约束条件为≥型的不等式,则对应的第i个对偶变量y i <= 0。√ +1分

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

4、树是无圈图中边数最多的图。√ +1分

5、采用允许缺货的t0循环策略时,订购费、单位存贮费和单位缺货费均增加20%,而需求速度降低20%,则最佳进货间隔期t0将会变为原来的 1.12 倍(保留小数点

后两位)。√ +1分

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

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

二、判断题(每题1分,共10分;安超群得分:6分)

1、当最优解中存在为零的基变量时,则线性规划具有多重最优解。 (正确)×

2、已知max w =Yb, YA≤C, Y≥0的松弛向量Ys的检验数向量是λs,则X=-λs

是其对偶问题的基本解,若Ys是最优解,则X=-λs是对偶最优解 (正确)√ +1分

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

4、产地个数为m销地个数为n的平衡运输问题的系数矩阵为A,则有r(A)≤m+n

-1。 (正确)×

5、最大流问题是找一条从发点到收点的路,使得通过这条路的流量最大。 (错

误)√ +1分

6、指派问题求最大值时,是将目标函数乘以“-1”化为求最小值,再用匈牙利法求解。(错误)√ +1分

7、单位存储费和订购费同时增加i%,则总成本也增加i% (正确)×

8、 LP 问题的基本可行解对应可行域的顶点。 (正确)√ +1分

9、用动态规划求解一般线性规划问题,是将约束条件数作为阶段数,变量作为状态(正确)×

10、在允许发生短缺的存贮模型中,订货批量的确定应使由于存贮量减少带来的节约能抵消缺货时造成的损失 (正确)√ +1分

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

三、单项选择题(每题1分,共10分;安超群得分:7分)

1、线性规划具有多重最优解是指

选择 × 1)、目标函数系数与某约束系数对应成比例

正确 2)、最优表中存在非基变量的检验数为零

3)、可行解集合无界

4)、基变量全部大于零

2、互为对偶的两个线性规划问题的解存在关系

1)、原问题无可行解,对偶问题也无可行解

2)、若最优解存在,则最优解相同

选择正确 3)、一个问题具有无界解,则另一问题无可行解√ +1分

4)、一个问题无可行解,则另一个问题具有无界解

3、 max z=3x1+x2,4x1+3x2≤7,x1+2x2≤5,x1,x2=0或1,最优解是

1)、(0,1)

2)、(1,0)

选择正确 3)、(1,1)√ +1分

4)、(0, 0)

4、求总销量小于总产量的运输问题不需要做的是

1)、虚设一个销地

2)、令产地到虚设的销地的单位运费为0

选择正确 3)、删去一个产地√ +1分

4)、取虚设的销地的需求量为恰当值

5、μ是关于可行流 f 的一条增广链,则在μ上有

1)、对一切μ上的前向弧(i,j),有f ij≥C ij

2)、对一切μ上的后向弧(i,j),有f ij≤C ij

3)、对一切μ上的前向弧(i,j),有f ij≤C ij

选择正确 4)、对一切μ上的后向弧(i,j),有f ij>0 √ +1分

6、不满足匈牙利法的条件是

1)、效率矩阵的元素非负

正确 2)、问题求最大值

3)、人数与工作数相等

选择 × 4)、有一人不能做其中一项工作

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

选择 × 1)、少

2)、一样

3)、不确定

正确 4)、多

8、用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为

1)、很大的正数

2)、1

3)、很大的负数

选择正确 4)、0 √ +1分

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

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

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

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

4)、将装载的物品件数作为状态

10、当基变量x i的系数c i波动时,最优表中引起变化的有

1)、最优基B

2)、第i列的系数

选择正确 3)、所有非基变量的检验数√ +1分

4)、基变量X B

五、应用题(题分:10,安超群得分:9)

某钢筋车间要制作一批钢筋(直径相同),长为3m的要90根,长为4m的要60根。已知原材料有两种规格:一种是10m长的,另一种是15m长的;原材料成本与其长度成正比,问如何下料,可使所用原材料最省?

做题记录:

共7种方案:334,3331,442:33333,33342,33441,3444.对应的安排量分别为

x11,x21,x31;x12,x22,x32,x42;单位费用为c.

min z=10c(x11+x21+x31)+15c(x12,x22,x32,x42)

{ 2x11+3x21+5x12+3x22+2x32+x42>=90

x11+2x31+x22+2x32+3x42>=60

x11,x21,x31,x12,x22,x32,x42>=0

答案:

10米的原材料的下料方式有如下三种:

一、2根3米的和1根4米的,设此方式用x1次;

二、2根4米的,设此方式用x2次;

三、3根3米的,设此方式用x3次;

15米的原材料的下料方式有如下三种:

四、1根3米的和3根4米的,设此方式用x4次;

五、2根3米的和2根4米的,设此方式用x5次;

六、3根3米的和1根4米的,设此方式用x6次;

七、5根3米的,设此方式用x7次。

模型如下:

min z=x1+x2+x3+1.5(x4+x5+x6+x7)

s.t. 2x1+3x3+x4+2x5+3x6+5x7≥90

x1+2x2+3x4+2x5+x6≥60

x1,x2,...,x7≥0,且为整数。

相关推荐
相关主题
热门推荐