运筹学习题课2017

运筹学习题课

一、选择题

1.用图解法解线性规划时,以下几种情况中不可能出现的是( )。 A. 可行域有界,无有限最优解 B. 可行域无界,有唯一最优解 C. 可行域是空集,无可行解 D. 可行域有界,有多重最优解

2.根据线性规划的互补松弛定理,安排生产的产品机会成本一定( )利润. A. 小于

B. 等于

C. 大于

D. 大于等于

3.已知某个含10个结点的树图,其中9个结点的次为1,1,3,1,1,1,3,1,3,则另一个结点的次为( )。

A. 3

B. 2

C. 1

D. 以上三种情况均有可能 4.在求解整数规划问题时,不可能出现的是( )。 A. 唯一最优解 B. 无可行解

C. 多重最佳解

D. 无穷多个最优解

5.1m n +-个变量构成一组基变量的充要条件是( )。 A. 1m n +-个变量恰好构成一个闭回路 B. 1m n +-个变量对应的系数列向量线性相关

C. 1m n +-个变量中部分变量构成一个闭回路

D.

1m n +-个变量不包含任何闭回路

6.线性规划具有唯一最优解是指( )。

A. 最优表中存在常数项为零

B. 可行解集合有界

C. 最优表中存在非基变量的检验数为零

D. 最优表中非基变量检验数全部非零 7.有6 个产地4个销地的产销平衡运输问题模型具有特征( )。 A. 有10个变量24个约束 B. 有24个变量10个约束 C. 有24个变量9约束 D. 有9个基变量10个非基变量 8.下列关于网络最大流的说法中,不正确的是( )。 A. 可行流*

f 是最大流,当且仅当网络中存在关于*

f 的增广链 B. 用标号法求解最大流问题,同时可得到一个最小截集 C. 最小截集的容量的大小影响网络总的输送量的提高 D.

网络的最大流需满足容量条件和平衡条件

9.如果一个线性规划问题有n 个变量,m 个约束方程()m n <,系数矩阵的行数为m ,则基可行解的个数最为( )。 A.

m

B.

n

C.

m

n

C D.

n

m

C 10.在一个网络中,如果图形是连通且不含圈的,则这种图形称之为( )。 A. 点 B. 线 C. 树 D. 最小支撑树

11.用表上作业法求解3个产地4个销地的运输问题,若某步求得空格32A B 的检验数为-2,下列说法中正确的是( )。

A. 增加空格

32A B 处的运输量将使总成本降低 B. 当前方案是最优运输方案

C. 由3A 至2B 的运输量增加1个单位,可使总运费增加2

D. 为使总运费更小,应使3

A 至2

B 的运输量减少2

12.若某线性规划问题存在基可行解,则该问题( )。 A. 一定有最优解

B. 具有无界解

C. 有非空的可行域

D. 可能无可行解

13.若μ是关于可行流f 的一条增广链,则在μ上有( )。 A. 对一切(,)i j v v μ+

∈,有ij ij f c ≤ B. 对一切(,)i j v v μ+

∈,有ij ij f c > C. 对一切(,)i j v v μ-∈,有ij ij f c ≥ D.

对一切(,)i j v v μ-∈,有0ij f >

14.设线性规划的约束条件为1231241

43224,,0

x x x x x x x x ++=??

++=??≥?,则基本可行解为 ( )。

A. (0, 0, 4, 3)

B. (2, 0, 1, 0)

C. (3, 4, 0, 0)

D. (3, 0, 4, 0)

15.关于动态规划问题的下列命题中错误的是( )。

A. 动态规划分阶段顺序不同,则结果不同

B. 状态对决策有影响

C. 动态规划中,定义状态时应保证在各个阶段中所做决策的相对独立性

D. 动态规划的求解过程都可以用列表形式实现

16.关于标准的M/M/1排队模型,下列说法错误的是( )。 A. 顾客源是有限的,且到达过程是平稳的

B. 各顾客的服务时间相互独立,且服从相同的负指数分布

C. 到达时间间隔和服务时间是相互独立的

D. 单个队列,先到先服务,且对队长没有限制 17.下列说法不正确的是( )。

A. 顾客相继到达的时间间隔独立同负指数分布等价于输入过程为泊松流

B. 标准的M/M/1模型中,顾客在系统中的逗留时间服从负指数分布

C. 在M/M/1/N/∞模型中,当排队等待的顾客数为N-1时,再来的顾客将被拒绝进入系统

D. 单服务台的排队模型中,排队长的期望值与队长的期望值相差1 18.在排队系统中,系统的状态概率P i 是指( )

A .系统中有i 个顾客在等待服务

B .系统可容纳的最大顾客数为i

C .系统中有i 个顾客的可能性

D .系统中有i 个顾客 19.在库存决策问题中,所谓存储策略是指( ) A .决定补充的间隔时间 B .决定需求和补充的数量

C .决定补充的最小费用

D .决定补充的间隔时间和每次补充的数量

20.假设顾客的到达形成强度为λ的泊松流,则对于充分小的t ?,下列哪项说法是不正确的?( )

A .在[),t t t +?内最多只能有1个顾客到达

B .在[),t t t +?内有2个以上顾客到达的概率为()o t ?

C .在[),t t t +?内有2个顾客到达的概率为1()t o t λ-?+?

D .在[),t t t +?内恰有1个顾客到达的概率为()t o t λ?+?

21.下列关于标准M/M/1排队模型中ρ的描述,那一项是不正确的?( ) A .它能刻画系统的繁忙程度 B .为保证排队长度有限,需满足1ρ≥ C .它是平均到达率和平均服务率之比 D .它表示系统的服务强度

22.线性规划问题12121212min 34,4,22,0Z x x x x x x x x =++≥+≤≥、的解的情况为( )。

A. 无可行解

B. 有唯一最优解

C. 有多重最优解

D. 有无界解

23.关于线性规划模型的可行域,下面_B_的叙述正确( )。 A. 可行域内必有无穷多个点 B. 可行域必有界 C. 可行域内必然包括原点

D. 可行域必是凸的

24.表上作业法的基本思想和步骤与单纯形法类似,因而初始调运方案的给出就相当于找到一个( )。

A. 基

B. 可行解

C. 初始基本可行解

D. 最优解 25.关于最小支撑树,以下叙述正确的是( )。 A. 最小支撑树是一个网络中连通所有点而边数最少的图 B. 最小支撑树是一个网络中连通所有的点,而权数最少的图 C. 一个网络中的最大权边必不包含在其最小支撑树内 D. 一个网络的最小支撑树一般是不唯一的

二、判断题

1.对于线性规划的原问题和其对偶问题,若其中一个有最优解,另一个也一定有最优解。

2.一个图G 是树的充分必要条件是该图为边数最少的无孤立点的图。( )

3.对于对偶单纯形法,其初始解必须是可行的。( )

4.设图G=(V,E)是一个树,p(G)≥2,则G中至少有两个悬挂点。( )

5.用图解法解线性规划问题,若在两个顶点同时得到最优解,则它们的连线上任意点都是最优解。( )

6.在树中不相邻的两个点间添上一条边,则恰好得到一个圈。( )

7.线性规划可行域无界,则具有无界解。( )

8.任意可行流的流量不小于最小割量。 ( )

9.网络最大流量是网络起点至终点的一条增广链上的最大流量。

( )

10.可行解集有界非空时,则在顶点上至少有一点达到最优值。 ( )

11.按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路。 12.运输问题中用位势法求得的检验数不唯一。 ( )

13.假如一个线性规划问题含有6个变量和4个约束,则用动态规划方法求解时将划分为4个阶段,每个阶段的状态将由一个6维的向量组成。 ( ) 14.动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性。

( )

15.在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下,由1名工人看管5台机器与由3名工人联合看管15台机器相比,机器因故障等待工人维修的平均时间不变。

( )

16.订货费用包括订购费用和货物的成本费用。前者与订货数量有关,而与订货次数无关。

( )

17.对同一个动态规划问题,应用顺推解法和逆推解法一定会得到相同的最优解。

( )

18.在单时期的随机存贮模型中,计算时都不包括订货费用这一项。原因是该项费用通常很小可忽略不计。

( )

19.报童问题中损失最小的期望值和赢利最大的期望值是不同的,所以两者确定的Q 值也不相同。 ( )

20.相继到达的间隔时间是独立且相同的负指数分布,与输入过程为泊松流是等价的。 ( )

三、填空题

1.用表上作业法求解m 个产地n 个销地的平衡运输问题,其方案表上数字格的个数为 个;若已计算出某空格的检验数为-3,若从该空格出发进行调整,设调整量为2,则调整后可使总运费下降 。

2.设线性规划问题max :{,0}cx Ax b x ≤≥有最优解,且最优解值0z >;如果c 和b 分别被1v >所乘,则改变后的问题

(也有、不一定有)最优解;若有最优解,其最优解 (大于、小于、等于)z 。

3.设有线性规划问题[]{}min ,|,0f CX X R X AX b X =∈==≥,有一可行基B (为A 中的前m 列),记相应基变量为X π,价格系数为C B ,相应于非基变量为X N ,价格系数为C N ,则相应于B 的基本可行解为X= ;B 为最优基的条件是 。

4.线性规划问题如果有无穷多最优解,则单纯形计算表的终表中必然有___ 个非基变量的检验数为___ ___。

5.线性规划问题中,如果在约束条件中出现等式约束,通常用增加_ __的方法来产

生初始可行基。

6.求最小支撑树问题,常用的方法有:避圈法和 _ __。

7.下图给出某城市部分道路的分布情况,现要沿道路铺埋输水管,为了使铺设的管线最短,要求按道路分布图的最小支撑树来设计管线,则所铺设管线的最小总长度应该是 。

运筹学习题课2017

8.某钻井队要从编号为1、2、3、4、5的五个井位中选择若干钻井探油,则“要么选择钻井2,要么选择钻井5” 可用i x 的线性表达式表示为 ,其中选择第i

号钻井时=1i x ,否则=0i x ,15i =?,

,。 9.已知下表是制订生产计划问题的一张LP 最优单纯形表(Max 型问题,约束条件均为“≤”型),其中345,,x x x 为松驰变量。

运筹学习题课2017

则1B -= ;对偶问题的最优解*

Y = 。

10.在单纯形迭代中,可以根据最终表中 变量不为零判断线性规划问题无解。 11.若某种资源的影子价格等于k ,在其他条件不变的情况下(假设原问题的最佳基不变),当该种资源增加3个单位时,相应的目标函数值将增加 。

12.线性规划的原问题的约束条件系数矩阵为A ,则其对偶问题的约束条件系数矩阵

为 。

13.在表上作业法所得到的调运方案中,从某空格出发的闭回路的转角点所对应的变量必

为 。

14.已知下表是制定生产计划问题的一张LP 最优单纯形表(极大化问题,约束条件均为“≤”型),其中456,,x x x 为松弛变量。

运筹学习题课2017

则1

B

-= ,对偶问题的最优解*Y = 。

15.若,X Y 分别是线性规划的原问题和对偶问题的可行解,则有CX Yb ;又若

CX Yb =成立,则X 和Y 分别是线性规划的原问题和对偶问题的 。

16.用标号法求解网络最大流问题,当求的最大流的同时,也得到了最小截集,它是由 点集和 点集构成的点集切割中 (正还是反)向弧组成。

17.在完全市场经济的条件下,当某种资源的市场价格低于影子价格时,企业应 该资源,而当某种资源的市场价格高于影子价格时,则企业应 该资源,可见影子价格对市场有调节作用。

18.若运输问题的产销平衡表中有m 个产地和n 个销地,则其决策变量有 个,其数值格有 个。

19.某工程公司拟从四个项目中选择若干项目。若令1, 0,

i i x i ?=??第个项目被选中第个项目未选中,请用i

x 的线性表达式表示下列要求:

①若项目2被选中,则项目4不能被选中: ; ②只有项目1被选中,项目3才能被选中: 。

20.表上作业法求解运输问题,若已计算出某空格的检验数为-1,现从该空格出发进行调整,设调整量为2,则调整后可使总运费下降 。

21.设线性规划问题max :{,0}CX Ax b X =≥有最优解*

X 和影子价格*

Y ,则线性规划问题max :{2,0}CX Ax b X =≥的最优解= ,影子价格= 。

22.如图所示,该网络的最小支撑树的权和为 。

运筹学习题课2017

23.可行流应满足两个限制条件,即容量限制条件和 。 24.线性规划模型包括 、约束条件和目标函数三个要素。

25.在运输问题模型中,1m n +-个变量构成基变量的充要条件是 。

26.线性规划问题的所有可行解构成的集合是 ,线性规划问题的每个基可行解对应可行域的 。

27.用大M 法求解Max 型的线性规划时,人工变量在目标中的系数均为 ,若最优解的 中含有人工变量,则原问题无可行解。

28.已知最优基1237B ??=????

,(3,6)B C =,则对偶问题的最优解是 。

29.将非平衡运输问题化为平衡运输问题,在表上相当于增加一个虚设的 ,在模型中相当于增加若干个 变量。 30.在资源优化的线性规划问题中,某资源有剩余,则该资源影子价格等于 。 31.若X 、Y 分别是线性规划的原问题和对偶问题的可行解,则有CX Yb (,=≤≥或)。

32.请在下图所示的最短路问题求解过程中进行一步:下一步给 节点标号,标号为 。

运筹学习题课2017

33.动态规划模型中,状态变量的选择要满足两个条件:①能描述问题的过程;② 。

34.动态规划问题的研究对象是 问题。

35.一般的排队系统有三个基本组成部分,即 、排队规则和服务机构。 36.当顾客的到达形成强度为λ的泊松流时,对于充分小的t ?,在时间区间[,]t t t +?内有1个顾客到达的概率1(,)P t t t +?= 。

37.在//1//M M N ∞排队模型中,设顾客平均到达率为λ,则被拒绝排队的顾客的平均数为 。

38.在允许缺货、生产需要一定时间的确定型存储模型中,最优单位费用记为C 0,记不允许缺货,而其他参数不变的情况下的最优单位费用为C 1,则C 1 C 0(选大于还是小于)。

39.已知报童每日售出报纸份数r 的概率为()P r ,每售出一份报纸赚k 元;如报纸未能售出,每份赔

h

元。则该报童应准备的报纸最佳数量

Q

应满足的条件

是: 。

40.某厂每年需某种元件1000个,每次订购费3100C =元,存储费每年每件120C =元,不允许缺货。又若元件单价K 随着采购数量的不同而不同:40150

()38

150Q K Q Q

则此时的最佳订购数量Q *

= 个。

41.在//1//M M N ∞模型中,设顾客平均到达率为λ,则该排队系统的有效到达率

e λ= ;而在//1/

/M M m ∞模型中系统的有效到达率e λ= ;

42.某蛋糕房的顾客到达服从1=λ人/分钟的泊松分布,则某一刻钟内无顾客到达的概率为 ,在4分钟内有3名以上顾客到达的概率为 。

四、计算题

1.(20分)某建材厂生产四种型号的特用构件:Ⅰ型、Ⅱ型、Ⅲ型、Ⅳ型。各型号每件所需组装时间、检验时间、销售收入及该厂组装调试能力如表1所示。

运筹学习题课2017

运筹学习题课2017

但现在因为某种特型材料比较紧张,每月最多只能进货180只(每件构件用一只),其中Ⅲ型、Ⅳ型用到的不超过100只。令1234,,,x x x x 依次表示各型号每月计划产量。现工厂拟定使目标总销售收入z 为最大的生产计划。

(1)写出该问题的数学模型,对于约束条件依下列顺序:组装时间、检验时间、特种材料

数、、Ⅲ型、Ⅳ型用到的特种

材料数,并引入松弛变量使之成为等式。(5分) (2)用单纯型法求解的终表入下表。

运筹学习题课2017

依据上表,分别回答下列问题:

①最优生产计划是什么?是否还有其他的最优生产计划? 为什么? (4分) ②组装时间的影子价格是多少? (1分)

③若外厂可调剂增加80h 的检验时间,但每小时需付0.4百元,这样的调剂值得吗? 能增加多少收入? (4分)

④设Ⅰ型构件售价由4百元增加到4.5百元,最优计划要改变吗?如果增加到5.5百元呢?说明理由。 (2分)

⑤写出本问题的对偶模型,并指出其最优解。 (4分)

2.(20分)某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划

?????

?

?≥≤+≤+≤++=0

,45 80290

3 45 max 2121212121x x x x x x x x x x Z 已知最优表如下。

运筹学习题课2017

运筹学习题课2017

(1)确定x 2的系数c 2的变化范围,使原最优解保持最优; (3分) (2)若c 2=6,求新的最优计划; (5分)

(3)b 3在什么范围内变化,原最优基不变? (2分) (4)若b 3=55,求出新的最优解; (5分)

(5)设企业研制了一种新产品,对三种资源的消耗系数列向量以P 6表示,

()T

63/211/2P =。问它的价值系数c 6符合什么条件才必须安排它的生产?设c 6=3,新

的最优生产计划是什么? (5分)

3. (20分)某电冰箱厂生产单、双门两种冰箱,每台所需组装时间、调试时间、销售收入及该厂的组装、调试能力如下表,电机每月进货最多50个(每台冰箱用1台电机),令12,x x 分别为单、双门冰箱的月产量。现工厂需拟订使总收入Z 为最大的生产计划。

运筹学习题课2017

(1)写出此问题的数学模型(约束条件依次为组装时间、调试时间、电机数);(3分) (2)下面是用单纯形法求解此问题过程中的一个不完全表,请将表格补充完整;(4分)

运筹学习题课2017

(3)上表是否为终表,为什么?若是,写出最优生产计划和电机的影子价格;在执行这一计划后,哪种资源有剩余,剩余多少?(5分) (4)写出上述规划的对偶规划模型及其最优解;(4分)

(5)现又设计出三门冰箱,每台组装时间20h ,调试时间10h ,销售收入1600元,问是否

应考虑生产三门冰箱?请说明理由。(4分)

4. (15分)下图网络弧上的数字为容量,括弧内的数字为该弧的流量。

运筹学习题课2017

(1)在括号内填上适当的数字,使构成一个可行流。(2分) (2)在下表中填出截集与截量。(3分)

运筹学习题课2017

(3)用标号法解此网络最大流,并指出最小截集。(10分)

5.(15分)某照相机厂生产A 、B 、C 三种型号的产品,每架均需经机身制造、零件装配和检验包装三道工序。各型号产品所需工时数、每月工时限量及销售利润见下表。根据市场情况,C 型每月产量应控制在150架以内。现工厂需拟定使总利润z 最大的生产计划。

运筹学习题课2017

(1)写出此问题的数学模型(变量123,,x x x 分别表示A 、B 、C 型产品的月产量,约束条件依次为:机身制造时间、零件装配时间、检验包装时间及C 型产量)(2分) (2)下表是用单纯形法解此问题过程中的一个不完全表,请将表完成;(4分)

运筹学习题课2017

运筹学习题课2017

(3)上表是否为终表?若是,请写出最优生产计划及检验包装时间的影子价格;(3分) (4)写出此问题的对偶问题数学模型,并指出其最优解;(3分)

(5)现又设计出D 型产品,每架需机身制造、零件装配和检验包装时间分别为6、2、2(h),销售利润为30元/架,问是否应考虑生产D 型产品?为什么?(3分)

6.考虑非线性整数规划1233max ()z x x g x =,12320

..0 1,2,3

i x x x s t x i ++=??

≥=?且为整数

其中2

33333331033()33103

102010

x x g x x x x ?≤≤??

=<≤???<≤?,现拟用动态规划方法解此问题(用通常的逆推解法),

要求:

(1)写出以下表达式或集合的具体内容:

①本问题的状态转移方程=+1k s

②递推方程 44

() () k k f s f s =??

??=?

③第1阶段的状态集合{

}1

S =

④第2阶段状态为5时的允许决策2x 的集合)5(2D ={ }; 7.有//1/5/M M ∞模型,平均服务率为10μ=,平均到达率15λ=,问: (1)有效到达率和服务台的服务强度; (2)系统中的平均顾客数; (3)系统的满员率;

(4)服务台应从哪些方面改进工作?理由是什么?

8.设某公司利用塑料作原料制成产品出售,对原料需求的概率如下表所示:

运筹学习题课2017

已知每箱塑料购买价为400元,每次订购费3500C =元,存储费每箱150C =元,缺货费每

箱2600C =元。该厂希望制定(,)s S 型存储策略,试求s 及S 的值。

9.某一售票窗口,已知顾客按平均为2分30秒的时间间隔的负指数分布到达,顾客在售票窗口的服务时间平均为2分钟。

(1)若服务时间也服从负指数分布,求顾客为售票所需的平均逗留时间和等待时间。(2)若

经过调查,顾客在售票口前至少占用1分钟,其概率密度为??

?<≥=+-1

1

)(1y y e y f y ,求顾客为售票所需的平均逗留时间和等待时间。

10.用动态规划方法求解下列问题:

2

123

123

max 49210..0123i z x x x x x x s t x i =++++=??≥=?,,

11.某汽车检测站有一条检测线,要求做检测的车辆按泊松流到达,平均每小时6辆。每辆车的检测时间服从负指数分布,平均每辆10分钟。用于等待检测的停车泊位有5个,当无停车泊位时,来检测的车辆自动离去,到其他检测站检测。试计算: (1)某车辆一到达就可以进行检测的概率; (2)等待检测的平均车数;

(3)每辆车在检测线上逗留的期望时间;

(4)在可能到来的车辆中,有百分之几不等待离开;

(5)如果车辆因停车泊位被占用而离去,每辆车损失a 元,求每小时因车辆离去而造成的损失。

12.(8分)已知线性规划问题

12341341234max 25628

..222120(1,2,3,4)j

Z x x x x x x x s t x x x x x j =+++?++≤?

+++≤??≥=? 其对偶问题的最优解为*14y =,*

21y =,试应用对偶问题的性质求原问题的最优解。

13.已知线性规划(8分)

123123123max 3452102351,2,3j

Z x x x x x x x x x x j =++?+-≤?

-+≤??≥=?0,

求原问题和对偶问题的最优解。

14.(10分)某修理店只有一个修理工人,来修理的顾客到达次数服从泊松分布,平均每小时4人。修理时间服从负指数分布,平均需6分钟。求: (1)修理店空闲的概率;(2分) (2)在店内顾客的平均数;(2分) (3)在店内的平均逗留时间;(2分)

(4)若店内已有3个顾客,则后来的顾客即不再排队,其他条件相同,求店内空闲的概率和店内顾客平均数。(4分)

15.(7分)运用单纯形法求解下面线性规划问题。

12121212

max 33515

s.t.6224

,0z x x x x x x x x =++≤??

+≤??≥?

16.(7分)已知下列线性规划问题的最优解为X ﹡=(2,2,4,0)T ,试根据对偶理论,直接求出对偶问题的最优解。

123412412234123

max 243826s.t.69

0(1,2,3,4)

j Z x x x x x x x x x x x x x x x x j =+++?++≤?

+≤??

++≤??++≤??≥=?

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