运筹学自测试卷1.doc

自测试题1

一、 填空题

1、 物资调运问题中，有m个供应地，A1,A2,....,Am，Ai的供应量为ai(i=1,2,...,m)，n个需求地B1,B2,...Bn，Bj的需求量为bj(j=1,2,...,n)，则供需平衡条件为 （ ） 。
2、 一个 无圈 的连通图称为树。
3、 线性规划的数学模型由  决策变量    、    目标函数    和约束条件构成，称为三个要素。
4、 对策行为的三个基本要素是 局中人 、 策略集 和赢得函数。
5、 某工厂每年需要某原料1800吨，不需每日供应，但不得缺货。设每吨每月的保管费为60元，每次订购费为200元，则最佳订购量为32吨 。
（提示：根据模型一“不允许缺货，备货时间很短”，代入公式）
6、 甲和乙玩“剪刀石头布”的游戏，规则是：剪刀赢布，布赢石头，石头赢剪刀，赢者得一分。若双方所出相同算和局，均不得分，写出甲的赢得矩阵（ ）。
7、 风险决策一般采用 期望值 作为决策准则。
8、 求最小生成树常用的方法有 避圈法 和 破圈法 。
9、 线性规划的解有唯一最优解、无穷多最优解、（无界解 ）和无可行解四种。
10、 设K是n维欧氏空间的一点集，若任意两点的连线上的所有点 ；则称K为凸集。答案：
11、一个图，如果图，使及，则称是的一个
支撑子图
12、 求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是位势法。

二、 判断题

1、 线性规划模型中增加一个约束条件，可行域的范围一般将增大。(F)
解析：缩小
2、 在约束方程中引入人工变量的目的是形成一个单位阵。(T)
3、 运输问题中分配运量的格所对应的变量是基变量。(T)
4、 分配问题不可以用表上作业法求解。(F)
解析：可以
5、 具有n个顶点的树的边数恰好为n-1条(T)
6、 如果一个线性规划问题有可行解，那么它必有最优解。(F)
解析：不一定
7、 图解法提供了求解线性规划问题的通用方法。(F)
解析：多元
8、 如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。(T)
9、 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。(T)
10、 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。(T)
11、任何一个图中，奇点的个数为偶数 （T）。

12、 在线性规划问题中，基可行解的非零分量所对应的列向量线性无关。（T）
13、 图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（ T ）
14、 在二元线性规划问题中，如果问题有可行解，则一定有最优解（F）
15、 任何两个凸集的交集是凸集（ T ）
16、用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj≤0，则问题达到最优。 ( F )

17. 指派问题的解中基变量的个数为m＋n。( F )
18、判断；
图解法虽然直观、简便，但当变量数多于三个以上时，它就无能为力了。 （ T ）

三、 选择题

1、 在运输问题中，可以作为表上作业法的初始基可行解的调运方案应满足的条件是(D)
A. 含有m+n-1个基变量
B. 基变量不构成闭回路
C. 含有m+n-1个基变量且不构成闭回路
D. 含有m+n-1个非零的基变量且不构成闭回路
2、 在整数规划问题中，变量的取值可能是(D)
A. 整数
B. 0或1
C. 大于零的非负整数
D. 以上三种都可能
3、 最早运用运筹学理论的是(A)
A. 第二次世界大战期间，英国军事部门将运筹学运用到军事战略部署
B. 美国最早将运筹学运用到农业人口规划问题上
C. 第二次世界大战期间，英国政府将运筹学运用到政府制定计划
D. 50年代，运筹学运用到研究人口，能源，粮食等问题上
4、 下列那些不是运筹学研究的范围(B)
A. 质量控制
B. 系统设计
C. 动态规划
D. 排队论
5、 有4个产地，5个销地的平衡运输问题，其基变量的个数为(C)
A. 4个
B. 5个
C. 8个
D. 9个
6、 可行流满足的条件不包括(C)
A. 网络中每条边上的流量在0与最大容量之间
B. 中间点流入与流出量相等
C. 任何点流量不可为零
D. 发点流出量等于收点流入量
7、 在图中，以一点为始点，以另一点为终点的点边交替序列叫做(B)
A. 环
B. 圈
C. 网络
D. 链
8、 要求不超过第一目标值、恰好完成第二目标值，则目标函数是(A)
A.
B.
C.
D.
9、.使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题 （ D ）
A．有唯一的最优解 B．有无穷多最优解
C．为无界解 D．无可行解
10、在线性规划模型中，没有非负约束的变量称为 （ C ）
A．多余变量 B．松弛变量 C.自由变量 D．人工变量
11、下列哪个不是凸集（ D ）。
A.实心圆 B.实心球体 C.立方体 D.圆环

12、下列有关不确定型决策问题的说法中，错误的是（ D ）
A、不确定型决策问题是指决策者对各种自然因素发生的概率是未知的
B、不确定型决策除了应具备一般决策问题的四个条件外，还需要另外加一个条件：存在两个或两个以上的自然因素，并且各个自然因素出现的概率是不知道的
C、对于不确定型决策问题，根据决策者“选优”原则的不同，所选的最优方案也不同
D、不确定型决策问题是指决策者对各种自然因素发生的概率有一部分是已知的
13、如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最多为（ C ）。
A．m个 B．n个 C． D．个
14、线性规划可行域的顶点是 （C）
A、可行解 B、非基本解 C、基本可行解 D、最优解
15、在下面的数学模型中，属于线性规划模型的为（ A ）。

16、线性规划具有唯一最优解是指 （B）    
A． 最优表中存在常数项为零    
B．最优表中非基变量检验数全部非零     
C．最优表中存在非基变量的检验数为零     
D．可行解集合有界 
17、设线性规划的约束条件为 C

则基本可行解为 
A．(0, 0, 4, 3)        B．(3, 4, 0, 0)     C．(2, 0, 1, 0)        D．(3, 0, 4, 0) 

18、 有3个产地4个销地的平衡运输问题模型具有特征：（D）
A、有7个变量 B、有12个约束
C、有6个约束 D、有6个基变量,。

四、 综合题

1、 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为S1,S2,...S10，相应的钻探费用为C1,C2,...C10，并且井位选择要满足下列限制条件：
a .或选S1和S7，或选S8 ;
b. 选择了S3或S4就不能选S5，反正亦然;
c.在S5,S6,S7,S8中最多只能选2个。试建立数学模型
解：引入变量Xi

于是以上问题的数学模型为

2、 福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。

时间
所需售货人员数
时间
所需售货人员数
星期一
28
星期五
19
星期二
15
星期六
3l
星期三
24
星期日
28
星期四
25

3、某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。工厂每天可利用的工时为12个，可供应的原材料为15公斤。试确定使总利润为最大的日生产计划和最大利润。只建立模型。
解：设生产甲乙丙产品的数量分别为x1,x2,x3
maxZ=2x1+3x2+5x3
s.t.2x1+3x2+x3<=12
3x1+x2+5x3<=15
x1，x2,x3>=0
4、用图解法求解下面的线性规划问题：

答案：最优解：

5、用单纯形法求线性规划问题
max z = 10x1 + 5x2
3x1 + 4x2 ≤ 9
5x1 + 2x2 ≤ 8
x1,x2≥0

解：
在问题的约束条件中分别加入松弛变量x3，x4，得该线性问题的标准型
max z = 10x1 + 5x2
3x1 + 4x2 + x3 = 9
5x1 + 2x2 + x4 = 8
x1,x2,x3,x4≥0
初始单纯形表

x1
x2
x3
x4
x3
9
3
4
1
0
x4
8
5
2
0
1
-z
0
10
5
0
0
∵ x1为进基变量，min{9/3,8/5}=8/5
∴ x4为出基变量
以x1代替x4，进行旋转运算，得

x1
x2
x3
x4
x3
21/5
0
14/5
1
-3/5
x1
8/5
1
2/5
0
1/5
-z
-80/5
0
1
0
-2
∵ x2为进基变量，min{ 21/5/14/5 , 8/5/2/5 }=3/2
∴ x3为出基变量
以x2代替x3，进行旋转运算，得

x1
x2
x3
x4
x2
3/2
0
1
5/14
-3/14
x1
1
1
0
-1/7
2/5
-z
-35/2
0
0
-5/14
-25/14
∴ 最优解x = (1,3/2,0,0)T
∴ 目标函数的最大值z = 35/2

6、将下列线性规划问题转化为标准型

答案：

7、计算
应用最小成本法或者伏格尔法确定运输问题的初始调整方案，并求出初始方案对应的总运输费用。
销地
产地

供应量（辆）

10
0
20
11
15

12
7
9
20
25

0
14
16
18
5
需求量（辆）
5
15
15
10
45

最小元素法

销地
产地

供应量（辆）

15

15

15
10
25

5

5
需求量（辆）
5
15
15
10
45

5×0+15×0+15×9+10×20=335

伏格尔法
销地
产地

供应量（辆）

5

10
15

10
15

25

5

5
需求量（辆）
5
15
15
10
45

5×0+5×0+10×7+15×9+10×11=315
8、化下列线性规划为标准形
max z=2x1+2x2－4x3
x1 + 3x2－3x3 ≥30
x1 + 2x2－4x3≤80
x1、x2≥0，x3无限制
解：按照上述方法处理，得该线性规划问题的标准形为
max z=2x1+2x2－4x4+4x5
x1 + 3x2－3x4 + 3x5－x6 = 30
x1 + 2x2－4x4 + 4x5 + x7 = 80
x1、x2，x3，x4，x5，x6 ≥0

9、前进电器厂生产A、B、C三种产品，有关资料下表所示：

产品
材料消耗/（kg/ 件）
台时消耗/（台时/ 件）
产品利润/（元/ 件）
市场容量/件
A
2.0
2
8
200
B
1.5
1.5
10
250
C
5.0
1.2
12
100
资源限制
3000kg
1000台时

在资源限量及市场容量允许的条件下，如何安排生产使获利最多？（只建立线性规划数学模型，不求解）
解：设生产A、B、C三种产品的数量分别为和，则有：—1分

10、给出线性规划问题：
max
st.
用单纯形法求最优解，写出最终单纯形表。
解：将线性规划问题化为：max
st.
因此，可得如下初始单纯形表：
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
0
x4
1
1/3
1/3
1/3
1
0
0
x5
3
1/3
4/3
7/3
0
1
cj- zj
2
3
1
0
0
因3≥2≥1，所以选x2进基，因3/(4/3)≤1/(1/3)，故选x5出基，则得
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
0
x4
1/4
1/4
0
-1/4
1
-1/4
3
x2
9/4
1/4
1
7/4
0
3/4
cj- zj
5/4
0
-17/4
0
-9/4
因5/4≥0，所以选x1进基，因(1/4)/(1/4)≤(9/4)/(1/4)，故选x4出基，则得
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
1
1
0
-1
4
-1
3
x2
2
0
1
2
-1
1
cj- zj
0
0
-3
-5
-1
最优解为：（1，2，0）。

11、用单纯形法求线性规划问题
max z = 10x1 + 5x2
3x1 + 4x2 ≤ 9
5x1 + 2x2 ≤ 8
x1,x2≥0

解：
在问题的约束条件中分别加入松弛变量x3，x4，得该线性问题的标准型
max z = 10x1 + 5x2
3x1 + 4x2 + x3 = 9
5x1 + 2x2 + x4 = 8
x1,x2,x3,x4≥0
初始单纯形表

x1
x2
x3
x4
x3
9
3
4
1
0
x4
8
5
2
0
1
-z
0
10
5
0
0
∵ x1为进基变量，min{9/3,8/5}=8/5
∴ x4为出基变量
以x1代替x4，进行旋转运算，得

x1
x2
x3
x4
x3
21/5
0
14/5
1
-3/5
x1
8/5
1
2/5
0
1/5
-z
-80/5
0
1
0
-2
∵ x2为进基变量，min{ 21/5/14/5 , 8/5/2/5 }=3/2
∴ x3为出基变量
以x2代替x3，进行旋转运算，得

x1
x2
x3
x4
x2
3/2
0
1
5/14
-3/14
x1
1
1
0
-1/7
2/5
-z
-35/2
0
0
-5/14
-25/14
∴ 最优解x = (1,3/2,0,0)T
∴ 目标函数的最大值z = 35/2

12、某电子设备厂对一种元件的年需求为2000件，订货提前期为零，每次订货费为25元。该元件每件成本为50元，年存储费为成本的20%。如发生供应短缺，可在下批货到达时补上，但缺货损失费为每件每年30元。要求：
（1）经济订货批量及全年的总费用；
（2）如不允许发生供应短缺，重新求经济订货批量，并同（1）的结果进行比较。
解：（1）求出允许缺货的经济订购批量为：

（2）不允许发生供应短缺的经济订购批量为：

比较（1）和（2），允许发生缺货一般比不允许发生缺货有更大的选择余地。

13、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用

解：初始解为

计算检验数

由于存在非基变量的检验数小于0，所以不是最优解，需调整 调整为：

重新计算检验数

所有的检验数都大于等于0，所以得到最优解

14、求下面指派问题的最小值解：

解：

故最优解为：，最优解值为
。
15、某厂每月需甲产品1000件，每月生产率为5000件，每批装配费为500元，每月每件产品储存费为20元，求E.O.Q及最低费用。
解：
已知,,,,将各值代入式子得：
E.O.Q=(件)；

(元)
答：每次生产批量为250件，每次生产所需装配费及储存费最低为4000元。