《运筹学》复习题#精选.docx

资源描述

《运筹学》复习题#精选.docx

《《运筹学》复习题#精选.docx》由会员分享，可在线阅读，更多相关《《运筹学》复习题#精选.docx（24页珍藏版）》请在冰点文库上搜索。

《运筹学》复习题#精选.docx

《运筹学》复习题#精选

运筹学-学习指南

一、名词解释

1松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。

2可行域

满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。

3人工变量亦称人造变量.求解线性规划问题时人为加入的变量。

用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A中所含的单位向量常常不足

m个，此时可加入若干（至多m）个新变量，称这些新变量为人工变量。

4对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。

研究线性规划中原始问题与对偶问题之间关系的理论

5灵敏度分析

研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。

在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。

通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。

6影子价格

反映资源配置状况的价格。

影子价格是指在其他资源投入不变的情况下,每增加一单位的某

种资源的投入所带来的追加收益。

即影子价格等于资源投入的边际收益。

只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加

7产销平衡运输一种特殊的线性规划问题。

产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。

8西北角法

是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。

也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。

9最优性检验检验当前调运方案是不是最优方案的过程。

10动态规划解决多阶段决策过程优化问题的方法：

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

11状态转移方程

从阶段K到K+1的状态转移规律的表达式

12逆序求解法

在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。

13最短路问题

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

14最小费用最大流在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：

流量从A到B,如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。

15排队论

排队论（queueingtheory）,或称随机服务系统理论,是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。

、选择题

1.用图解法求解一个关于最大利润的线性规划问题时，若其等利润线与可行解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题（B）。

A、有无穷多个最优解B、有可行解但无最优解

C、有可行解且有最优解D、无可行解

2.若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（B）

A、两个B、无穷多个

C、零个D、过这的点直线上的一切点

3.用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题（A）。

A．有无穷多个最优解

B、有有限个最优解

C.有唯一的最优解

D．无最优解

4.在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为（A）。

A、很大的正数B、较小的正数C、1D、0

5.对LP问题的标准型：

maxZCX,AXb,X0，利用单纯形表求解时，每做一次

换基迭代，都能保证它相应的目标函数值Z必为（B）

A增大

B不减少

C减少

D不增大

6.若LP最优解不唯一，则在最优单纯形表上（A）

A非基变量的检验数必有为零者

B非基变量的检验数不必有为零者

C非基变量的检验数必全部为零

D以上均不正确

7.求解线性规划模型时，引入人工变量是为了（B）

A使该模型存在可行解

B确定一个初始的基可行解

C使该模型标准化

D以上均不正确

11.用大M法求解LP模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则

原模型（C）

A有可行解，但无最优解

B有最优解

C无可行解

D以上都不对

12.已知

（2,4），x2（4,8）是某LP的两个最优解，则（

D）也是LP的最优解。

（4,4）

（1,2）

（2,3）

无法判断

13、线性规划问题的灵敏度分析研究（BC）

A、对偶单纯形法的计算结果；

B、目标函数中决策变量系数的变化与最优解的关系；

C、资源数量变化与最优解的关系；

D、最优单纯形表中的检验数与影子价格的联系。

14、对偶单纯形法迭代中的主元素一定是负元素（A）

A、正确

B、错误

C、不一定

D、无法判断

15、对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（B）

A、换出变量

B、换入变量

C、非基变量

D、基变量

16、影子价格是指（D）

A、检验数

B、对偶问题的基本解

C、解答列取值

D、对偶问题的最优解

17、影子价格的经济解释是（C）

A、判断目标函数是否取得最优解

B、价格确定的经济性

C、约束条件所付出的代价

D、产品的产量是否合理

18、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为IWB=50元，

IWC=-80元，IYA=0元，IXC=20元，则最好挑选（A）为调整格。

A、WB格B、WC格C、YA格D、XC格

19、在一个运输方案中，从任一数字格开始，（B）一条闭合回路。

A•可以形成至少B•不能形成

C、可以形成D•有可能形成

20、运输问题可以用（B）法求解。

A、定量预测B、单纯形C、求解线性规划的图解D、关键线路

21、在运输问题的表上作业法选择初始基本可行解时，必须注意（AD）。

A、针对产销平衡的表；

B、位势的个数与基变量个数相同；

C、填写的运输量要等于行、列限制中较大的数值；

D、填写的运输量要等于行、列限制中较小的数值。

22、用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输

问题（A）

A、正确

B、错误

C、不一定

D、无法判断

23、通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题（C）

A、非线性问题的线性化技巧

B、静态问题的动态处理

C、引入虚拟产地或者销地

D、引入人工变量

24、动态规划方法不同于线性规划的主要特点是（AD）。

A、动态规划可以解决多阶段决策过程的问题；

B、动态规划问题要考虑决策变量；

C、它的目标函数与约束不容易表示；

D、它可以通过时间或空间划分一些问题为多阶段决策过程问题。

25、用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（B）

A、正确

B、错误

C、不一定

D、无法判断

26、用DP方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（B）

A、正确

B、错误

C、不一定

D、无法判断

27、.动态规划最优化原理的含义是：

最优策略中的任意一个K-子策略也是最优的（A）

A、正确

B、错误

C、不一定

D、无法判断

28．动态规划的核心是什么原理的应用（A）

A、最优化原理

B、逆向求解原理

C、最大流最小割原理

D、网络分析原理29．动态规划求解的一般方法是什么？

（C）

A、图解法

B、单纯形法

C、逆序求解

D、标号法

30．用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（B）A、任意网络

B、无回路有向网络

C、混合网络

D、容量网络

31.动态规划的求解的要求是什么（ACD）

A、给出最优状态序列

B、给出动态过程

C、给出目标函数值

D、给出最优策略

32.用动态规划解决生产库存的时候，应该特别注意哪些问题？

（BC）

A、生产能力

B、状态变量的允许取值范围

C、决策变量的允许取值范围

D、库存容量

33.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费

用是（C）。

A、降低的B、不增不减的C、增加的D、难以估计的

34.最小枝权树算法是从已接接点出发，把（C）的接点连接上

A、最远B、较远C、最近D、较近

35.在箭线式网络固中，（D）的说法是错误的。

A、结点不占用时间也不消耗资源

B、结点表示前接活动的完成和后续活动的开始

C、箭线代表活动

D、结点的最早出现时间和最迟出现时间是同一个时间

36.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是（C）。

A、1200B、1400

15km,20km

25km，则（D

）。

A、最短路线

—定通过

A点

B、最短路线

疋通过

B点

C、最短路线

疋通过

C点

D、不能判断最短路线通过哪一点

38.在一棵树中，如果在某两点间加上条边，则图一定（A）

A、存在一个圈

B、存在两个圈

C、存在三个圈

D、不含圈

39网络图关键线路的长度（C）工程完工期。

A.大于B.小于

C.等于D.不一定等于

40.在计算最大流量时，我们选中的每一条路线（C）。

A、一定是一条最短的路线B、一定不是一条最短的路线

C、是使某一条支线流量饱和的路线D、是任一条支路流量都不饱和的路线

41.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（C）

A、树的逐步生成法

B、求最小技校树法

C、求最短路线法

D、求最大流量法

42.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用（B）。

A、求最短路法B、求最小技校树法C、求最大流量法D、树的逐步生成法

43．排队系统状态转移速度矩阵中，每一列的元素之和等于0。

（B）

A、正确

B、错误

C、不一定

D、无法判断

44.排队系统中状态是指系统中的顾客数（A）

A、正确

B、错误

C、不一定

D、无法判断

45．排队系统的组成部分有（ABC）

A、输入过程

B、排队规则

C、服务机构

D、服务时间46．排队系统中，若系统输入为泊松流，则相继到达的顾客间隔时间服从什么分布（D）

A、正态分布

B、爱尔朗分布

C、泊松流

D、负指数分布47．研究排队模型及数量指标的思路是首先明确系统的意义，然后（ABC）

A、写出状态概率方程

B、写出状态转移速度矩阵

C、画出状态转移速度图

D、写出相应的微分方程48．排队系统的状态转移速度矩阵中（B）元素之和等于零。

A、每一列

B、每一行

C、对角线

D、次对角线

三、计算题

1..用图解法求解下列LP问题maxzx12x2

2X12X212Xi2X28

s.t4Xi164X212

XiX0

答案：

依题有

可得最优解集合为

{（Xi，X2）l（Xi，X2）a（2,3）（1a）（4,2）,0a1}

也即

{（X1,X2）|（X1,X2）（42a,2a）,0a°

最优值为z8（详细求解过程略去）

2.用分枝界定法求解下列线性规划问题

maxf（x）6X14x2

2x14x213

2x1x27

儿，％0且为整数

答案：

松弛问题的最优解为X1=2.5,X2=2,OBJ=23

由X1=2.5得到两个分枝如下：

maxf（x）6x,4x2

maxf（x）6x

4x2

2X1

4X213

和

2儿

4x213

问题I2X1

X27

问题II2X1

x27

X1,X2

0且为整数

X1,X2

0且为整数

各个分枝问题的松弛解为

问题1

问题II

9/4

f（x）

问题II的解即原整数问题的最优解

3、已知线性规划问题

maxz5X16X27X3

X15X23X315

5X16X210X320

s.t.

X1X2X35

X1,X20，X3无约束

要求：

（1）化为标准型式

（2）列出用两阶段法求解时第一阶段的初始单纯形表

解：

（1）令X1'

X；X3X3'X3''，X3'、X3”0ZZ

原模型可以转化为

Xi'X；X3X3'X3”，X3'、X3''0ZZ

Xi'5X23X3'3X3''X4X615

5Xl'6X210X3'10X3''X520

X1X2X3X3X75

X1'，X2，X3'，X3''X，X5，X6，X70

（2）见卜表

-1

X1'

X2'

X3'

X4'

X5'

X6‘

X7'

-1

-3

-1

-6

-10

-1

Cj-Zj

-2

-1

4、求下列线性规划问题，并写出LP问题的对偶问题

maXZ3X12X2

对偶问题：

minw4yi14y23y3

y迥2出3

s.t.2yi2y2y2

yi°$2,30

5、求出下列问题的对偶问题并分别队原问题及对偶问题求解

原问题:

maxf（x）

3x2

6X3

2x2

2x1

3x3

s.t

x,X2

0,x3

不限

答案：

对偶问题:

ming（y）18y16y?

叭

2y2

2y1

s.t

3y2

%,丫20,y3不限

用单纯型法求解过程

-6

X'3

X"3

（3）

OBJ=

10M

Cj-Zj

5+M

3+M

6+M

-6-M

38/3

1/3

5/3

1/3

X'3

16/3

2/3

1/3

14/3

1/3

（2/3）

1/3

OBJ=

32-14M/3

4-M/3

2-2M/3

2+M/3

Cj-Zj

1+M/3

1+2M/3

-2-M/3

1/2

5/2

X'3

（1/2）

1/2

3/2

1/2

3/2

OBJ=

9/2

3/2

Cj-Zj

1/2

3/2

-M-3/2

（1）

OBJ=

Cj-Zj

-M+1

X"3

OBJ=

Cj-ZjI010001-M3

对偶问题最优解：

y4=0y5=1y6=0yi=0y2=1y3=3

原冋题最优解：

xi=i4,x2=0,X3=-4,X4=8,X5=0,X6=0,OBJ=46

6、运输问题的数据如下表:

产量

500

600

300

销量

300

200

500

400

求最优运输方案。

答案：

最优方案：

f*=6000

产量

A1「

100

400

500

200

400

600

300

销量

300

200

500

400

7、对于以下运输问题，如何用最小元素法求出初始调运方案?

单隹、销地;

产量*

11+

豹

非■

AjQ

10*

答案：

求解过程如下。

表中数字为删除线出现的先后顺序。

t=t

舅运方案耒"

单位飞孵-

车匸

B2*

B尹

丄

€

4_^"-

可

Aip

3屮

7护

岛卢

—-

--§-■■■■

T汁妙

8■-

Fl-

■-（^1-

€

仪

<□

□0El向

8、判断下表中给出的调运方案能否作为表上作业法求解的初始方案？

为什么?

....:

量销地产也

产量

销量

105

答案：

不能作为初始方案。

因为数字格只有6个，而nm18

9、某奶牛站希望通过投资来扩大牛群数，开始只有5000元资金，现在已知可购入A或者B两个品种的奶牛，对于A种牛每投入1000元，当年及以后每年可以获得500元和2头小牛，对B种牛每投入1000元，当年及以后每年可以获得200元和3头小牛。

问：

（1）在今后的四年内应该如何分配投资使奶牛群最大

（2）到第四年底奶牛站将有多少头奶牛。

答案：

状态s为阶段n可利用的资金；

决策dn为阶段n向A种牛投入的资金数；

Sdn为阶段n向B种牛投入的资金数;

则转移函数为Sn10.2Sn0.3d

r表示在阶段n出生的小牛数

S45000；

第四年末牧场主应拥有的牛的头数为70头

10.求下面容量网络的最大流，弧边上括号内第一个数为容量，第二个数为流量。

（1）、根据标号过程找出增广链，确定流量修正量£；

（2）、调整流量，画出最大流图，说明最大流量是多少；

（3）、根据标号和求解过程确定最小割并算出最小割容量；

、解：

1.增广链:

（V3,2）

标号过程中，图2为最大流图，最大流量fmax325

3.SVi其节点均属S

则最小割为（S,S）（VM）,MM），最小割容量为3+2=5

11、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2

分钟。

工件的到达服从泊松分布，平均每小时到达25件。

试求：

⑴该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？

⑵每件工件在加工前平均等待的时间是多少？

平均等待的工件有多少件？

⑶一个工件从送达到研磨完，时间超过20分钟的概率？

⑷等待研磨的工件在8〜10件的概率。

答案：

模型：

M/M/1

参数：

入=25件/小时，尸0.5件/分钟=30件/小时，卩=入/卩=5/6

1）Po=1/6,P6=0.0558;

2）加工前平均等待时间wq=10分钟，平均等待的工件数Lq=4.1667件;

3）P（T>20）=e-20（-）=3.7210-44；

4）P7+P8+P9=0.0465+0.0388+0.0323=0.1176

12、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2

分钟。

工件的到达服从泊松分布，平均每小时到达25件。

试求：

（1）该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？

（2）每件工件在加工前平均等待的时间是多少？

平均等待的工件有多少件？

（3）一个工件从送达到研磨完，时间超过20分钟的概率？

（4）等待研磨的工件在8〜10件的概率。

答案:

模型：

M/M/1

参数：

入=25件/小时，[1=0.5件/分钟=30件/小时，p=入/[15=6;

1）P0=1/6,P6=0.0558;

2）加工前平均等待时间wq=10分钟，平均等待的工件数Lq

展开阅读全文