运筹学试卷.doc

第一套
一、写出下列线性规划问题的对偶问题：(8分)

答案：Maxω=15Y1+20Y2-5Y3
-Y1-5Y2+Y3≤ -5

5Y1-6Y2-Y3≥ -6

-3Y1+10Y2-Y3= -7
=+
约束条件

Y1≥0,Y2≤0,Y3不受限制制制

二、用图解法求解下列线性规划问题：(10分)

答案：（X1，X2）=（1，3/2），Z*=17.5
三、用沃戈法求下列运输问题的初始基本可行解 (12分)
销地
产地
甲
乙
丙
丁
产量
1
4

12
4
11
16
2
2

10
3
9
10
3
8

5
11
6
22
销量
8
14
12
14
48

答案：，其他变量的值等于零。
四、用对偶单纯形法求解线性规划问题：(12分)

答案：
Cj XB b
X1
X2
X3
X4
X5
-18 X3 1
-12 X2 3/2
1/3
-1/3
0
1
1
0
-1/3
1/3
0
-1/2
Cj-Zj
-2
0
0
-2
-6

五、某公司安排五名工作人员到五个不同岗位上工作。但必须对上岗人员进行培训。由于五名工作人员的经历不同，文化水平也有差异，故所需培训时间也不相同。如下表所示

工
作
培
训
时
间
人
员

B1
B2
B3
B4
B5
A1
A2
A3
A4
A5
7
9
8
7
4
5
12
5
3
6
9
7
4
6
7
8
11
6
9
5
11
9
9
6
11
问如何分配这五名人员的工作，使总的培训时间最短？(12分)
A1做B2项工作；A2做B3项工作；A3做B4项工作；A4做B5项工作；A5做B1项工作
六、若某产品中有一外购件，年需求量为10000件，单价为100元。由于该件可在市场采购，故定货提前期为零，并设不允许缺货。已知每组织一次采购需2000元，每年每件的存贮费为该件单价的10%，试求经济定货批量及每年的最小存贮加上采购的总费用。(10分)
R=10000，C3=2000，C1=100×10%=10
Q*=（件）
（元）

七、某工程项目各项活动的逻辑关系如表所示，试绘制网络图，并确定关键路线。（12分）
工序名称
紧前工序
花费时间（天）
A
—
3
B
—
2
C
—
2
D
—
2
E
B
2
F
C
2
G
F、D
3
H
A、E、G
4
答案：
（2）四条路线的路长为：（5分）
①：A+H=3+4=7（天）
②：B+E+ H=2+2+4=8（天）
③：D+G+H=2+3+4=9（天）
② C+F+G+H=2+2+3+4=11（天）
路径④活动时间最长，所以是关键路径（计算时间参数较好）
八、已知线性规划问题：（12分）

用单纯形法求解得最终单纯形表如下表所示：

X1
X2
X3
X4
X5
X1 6
X5 10
1
0
1
3
1
1
1
1
O
1
Cj-Zj

-3
-1
-2

试说明分别发生下列变化时，新的最优解是什么
（1） 目标函数变为MAX Z= 2X1 + 3X2 + X3
（2）约束条件右项由变为
答案：（1）（2）
九、已知赢得矩阵为

试用图解法求解此对策。（12分）
答案：局中人Ⅰ和Ⅱ的最优混合策略分别是，对策的值
七、某一决策问题的损益矩阵如表所示：其中矩阵元素值为年利润

案
方
件
事

S1
40
200
2400
S2

360
360
360
S3
1000
240
200
（1）若各事件发生的概率是未知的，分别用悲观法、乐观法、后悔值准则作出决策方案
（2）若是乐观系数，问取何值时，方案和是不偏不倚的。（12分）
答案：1）悲观法：应选S2。乐观法；应选S1。
后悔值法：应选S2。
（2）α=0.10256

第二套
一、用图解法求解下列线性规划问题，并说明解的情况。(10分)

答案：有可行解，但MAX Z无界。
二、写出下列线性规划问题的对偶问题：(6分)

答案：

三、已知某物资的产量、销量及运价表如图所示，试制定最优调运方案 (12分)
销地
产地
甲
乙
丙
丁
产量
1
2

11
3
4
70
2
10

3
5
9
50
3
7

8
1
2
70
销量
20
30
40
60

最优调运方案是：

目标函数值为Z*=20×2+30×4+20×0+30×3+20×0+40×1+30×2=350。
第三套
一、用图解法求解以下线性规划问题(12分)

答案：最优解为(X1,X2)=(5,25)，MAXZ﹡=700
三、已知某物资的产量、销量及运价表如图所示，试制定最优调运方案 (16分)
销地
产地
甲
乙
丙
丁
产量
1
2

11
3
4
70
2
10

3
5
9
50
3
7

8
1
2
70
销量
20
30
40
60

最优调运方案是：

目标函数值为Z*=20×2+30×4+20×0+30×3+20×0+40×1+30×2=350。
五、某工厂生产甲、乙、丙三种产品，已知有关数据如表所示：(16分)

产
品
原
料

甲
乙
丙
原料拥有量
A
B
6
3
3
4
5
5
45
30
单件利润
4
1
5

（1）建立线性规划模型，求使该厂获利最大的生产计划；
（2）若产品乙、丙的单件利润不变，则产品甲的利润在什么范围内变化时，上述的最优解不变。
（1）设分别代表甲、乙、丙产品产量，线性规划模型是：
Max Z=4X1+X2+5X3
6X1+3X2+5X3≤45

约束条件 3X1+4X2+5X3≤30

Xi≥0 i=1,2,3
用单纯形法解得，=（5，0，3），最大盈利为=35
（2） 产品甲的利润变化范围为[3，6]

第五套

一、用图解法求解下列线性规划问题（15分）

答案：唯一最优解z=92/3，x1=20/3，x2=8/3
二、下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、为松弛变量，试求表中到的值及各变量下标到的值。（20分）

-1

3

1
0
0
1
6
1

1
-2
0
0

2

-1
1
1/2
1/2
0
1

4

0
7

答案：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0;
变量下标：m=4,n=5,s=1,t=6
三、用图解法求解矩阵对策，
其中（15分）
答案：
四、（20分）
（1）某项工程由8个工序组成，各工序之间的关系为

工序
a
b
c
d
e
f
g
h
紧前工序
—
—
a
a
b,c
b,c,d
b,c,d
e
试画出该工程的网络图
d
1
2

a
6
4

h
f
c
解:
b

e
5
3

（2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键
线路（箭线下的数字是完成该工序的所需时间，单位：天）

10
10
e
c
4

11
11
5
5
1
5
解：
8
8
13
13
0
0
f
d
j
a
6
2

3
3
2
5
7
5

h
g
b

4
4
6
1

3

7
6

5
7
6
4
2
1
关键线路为
1
7
6
2
或
总工期为13天。
五、已知线性规划问题

其对偶问题最优解为，试根据对偶理论求原问题的最优解。（15分）
答：X=(0,14,0,0,1)
六、用动态规划法求解下面问题：（15分）

解：最优解：；最优值
七、已知线性规划问题

用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。（30分）

2
-1
1
0
0

2
3

1
0
1
3
1
1
1
1
0
1
6
10

0
-3
-1
-2
0

（1）目标函数变为；
（2）约束条件右端项由变为；
（3）增加一个新的约束：
答：（1）最优解为：x=（8/3，10/3，0，0，0）T；
（2）最优解为：x=（3，0，0，0，7）T；
（3）最优解为：x=（10/3，0，8/3，0，22/3）T；
八、某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案（20分）

销地
产地
甲
乙
丙
丁
产量
A
4
12
4
11
16
B
2
10
3
9
10
C
8
5
11
6
22
需求量
8
14
12
14
48

答：x11=4, x13=12, x21=4, x24=6, x32=14, x34=8
最小费用：244

第六套
一、（20分）已知线性规划问题：

（a）写出其对偶问题；
（b）用图解法求对偶问题的解；
（c）利用（b）的结果及对偶性质求原问题的解。
(a)Max z=2y1-3y2
Y1-2Y2≤2
2Y1+Y2≤3
约束条件
3Y1-Y2≤5
Y1+3Y2≤6
Y1≥0,Y2≤0
（b）Y=（8/5，1/5）；
（c）X=（7/5，0，1/5，0）
二、（20分）已知运输表如下：

销地
产地
B1
B2
B3
B4
供应量
A1
3
2
7
6
50
A2
7
5
2
3
60
A3
2
5
4
5
25
需求量
60
40
20
15

（1）用最小元素法确定初始调运方案；
（2）确定最优运输方案及最低运费。
初始解：x11=10,x12=40,x21=25,x23=20,x24=15,x31=25
最优解：x11=35,x12=15,x22=25,x23=20,x24=15,x31=25
三、（35分）设线性规划问题
maxZ=2x1+x2+5x3+6x4

的最优单纯形表为下表所示:

xΒ b
x1 x2 x3 x4 x5 x6
x3 4
2 -2 1 0 2 -1
x4 4
0 2 0 1 -1 1

-8 -1 0 0 -4 -1

利用该表求下列问题：
（1）要使最优基保持不变，C3应控制在什么范围；
（2）要使最优基保持不变，第一个约束条件的常数项b1应控制在什么范围；
（3）当约束条件中x1的系数变为 时，最优解有什么变化；
（4）如果再增加一个约束条件3x1+2x2+x3+3x4≤14，最优解有什么变化。
（1）
（2）
（3）最优解不变
（4）最优解x1=0，x2=0，x3=5，x4=3 最优值Z*=43
四、（20分）需要指派5人去做5项工作，每人做各项工作所消耗的时间如下表：
工作
人员
A
B
C
D
E
甲
3
8
2
10
3
乙
8
7
2
9
7
丙
6
4
2
7
5
丁
8
4
2
3
5
戊
9
10
6
9
10
问指派哪个人去完成哪项工作，可使总的消耗时间最小？
x15=x23=x32=x44=x51=1（甲-E， 乙-C，丙-B，丁-D，戊-A）最小时间21
五、（20分）用图解法求解矩阵对象G=(S1,S2,A)，其中

P= (0,4/5,1/5,0) Q= (2/5,3/5) VG=43/5

六、（20分）已知资料如下表：

工
序
紧前
工序
工序
时间(天)
工序
紧前
工序
工序
时间(天)
工
序
紧前
工序
工序
时间(天)
a
b
c
d
e
f
--
a
a
a
a
a
60
14
20
30
21
10
g
h
i
j
k
l
b，c
e，f
f
d，g
h
j，k
7
12
60
10
25
10
m
n
o
p
q

j，k
i，l
n
m
o，p
5
15
2
7
5

（1）绘制网络图；
（2）确定关键路线，求出完工工期。
答：关键路线为a-f-n-o-q,总工期为152天
七、（15分）某工厂有100台机器，拟分四个周期使用，在每一周期有两种生产任务。据经验，把机器x1台投入第一种生产任务，则在一个生产周期中将 x1台机器作废；余下的机器全部投入第二种生产任务，则有机器作废。如果干第一种生产任务每台机器可收益10，干第二种生产任务每台机器可收益7，问怎样分配机器，使总收益最大？
解：设xk为第k周期末机器完好数，uk为第k+1周期安排干第一种生产任务的机器数。
Dk(xk)={uk|0≤uk≤xk}

其中 （8分）
用逆推法求得：
最优决策为第一、二周期机器全部投入第二种生产任务，第三、四周期机器全部投入第一种生产任务。
最大收益为2680。

第七套

一、（15分）用图解法求解下列线性规划问题

答：唯一最优解z=92/3，x1=20/3，x2=8/3

二、（30分）已知线性规划问题

用单纯形法求的最终表如下表所示：

XB b
x1 x2 x3 x4 x5
x2 6
x5 10
1 1 1 1 0
0 3 1 1 1

0 -3 -1 -2 0

试说明分别发生下列变化时，新的最优解是什么?
（1）目标函数变为；
（2）约束条件右端项由 变为 ；
（3）增添一个新的约束。
（1）x*=（8/3，10/3,0，0，0）T
（2）x*=（3，0，0，0,7）T
（3）x*=（10/3，0，8/3，0,22/3）T
三、（20分）
（1）某工程由9项工作组成，它们之间的逻辑关系为：

工 作
A
B
C
D
E
F
G
H
L
紧前工作
-
A
-
A
D，L
E
B，F
-
C，H

要求画出该工程的网络图。
2
6
5
L
3

C

F
E
H
G
1

8
7

D
B
A

4

（2）某工程的网络图为
D
4
G
6
2

3
7
8
5
J
2
I
9
H
5
6
F
E
3
3
3
C
4
B
7
1
5
A

箭线下的数字表示完成该项工作所需天数。试求
a）各个事项所发生的最早、最迟时间；
b）工程的关键线路。
G
6
4
D
2
7
8
5
J
2
H
5
F
E
3
3
3
4
B
7
1
5
A
5
5

3

0
0
C
I

6
9

28
28
23
23
14
14
8
8

8
7
5
3
2
1

关键线路为

总工期为28天。
四、（15分）写出下列线性规划问题的对偶问题

五、（20分）矩阵对策，其中局中人Ⅰ的赢得矩阵为：

试用图解法求解。

六、（25分）设有物资从A1，A2，A3处运往B1，B2，B3，B4处，各处供应量、需求量及单位运价见下表。问应如何安排运输方案，才能使总运费最少？

销地
产地
B1
B2
B3
B4
供应量
A1
3
7
6
4
5
A2
2
4
3
2
2
A3
4
3
8
5
3
需求量
3
2
3
2
10

初始解：
，，，，，（10分）
最优解：
，，，，，
总运费：36元
七、（25分）甲、乙双方合资办厂，根据协议，乙方负责提供全部1000台设备，甲方承担其余义务，生产的产品双方共享。5年合同期满后，工厂全部归甲方所有。假定设备可在高低两种负荷下运转，在高负荷下生产，产品生产量s1与高负荷运转设备数量u1关系为s1=8u1,此时设备折损后年完好率α=0.7；在低负荷下生产，年产量s2与低负荷下设备数量u2关系为s2=5u2,此时设备折损后年完好率β=0.9。在排除其它影响前提下，问甲方应如何安排5年的生产计划，使5年后完好设备台数500台，同时5年总产量最大？
解：设xk为第k年初完好机器台数，uk为第k年安排高负荷运转设备台数，Dk(xk)={uk|0≤uk≤xk}

其中 （10分）
用逆推法求得：
最大产量
最优决策为第前4年所有设备低负荷下生产，最后一年所有设备高负荷下生产。

第八套
一、（10分）写出下列线性规划问题的对偶问题：

二、（20分）下表是某线性规划问题的一个单纯形表。已知该线性规划问题的目标函数为，约束条件均为“”型不等式，其中为松弛变量，表中解对应的目标函数值

0

1
0
1/5
1
2

-1

（1）求到的值；
（2）表中给出的解是否为最优解？
（1）依次为：2，0，0，1，4/5，0，-5
（2）是
三、（10分）已知线性规划问题：

其对偶问题的最优解为,试用对偶的互补松弛性求解原问题的最优解。
X*=（0，0，4，4）
四、（20分）已知整数规划问题：

不考虑其整数规划，利用单纯形法求得其松弛问题最优单纯形表如下：

0
1
1
0
7/22
-1/22
1/22
3/22
7/2
9/2

0
0
-28/11
-15/11

试用割平面法求整数规划问题最优整数解。
割平面方程（1）：
割平面方程（2）：
最优解：x1=4， x2=3
五、（20分）某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表：
工序
紧后工序
工序时间（天）
a
b,c,d,e
60
b
L
45
c
f
10
d
g,h
20
e
h
40
f
L
18
g
k
30
h
L
15
k
L
25
L
-
35

（1）绘制该工程网络图；
（2）计算时间参数，确定关键路线，求出完工工期。
（1）

1
2
4
6
7
8
3
5
a
60
d
20
g
30
k

25
L

h
15
e
40
f
18
c
10
b
45

（2）关键路线：a-d-g-k-L
六、（20分）已知运输表如下：

销地
产地
B1
B2
B3
B4
供应量
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
需求量
3
6
5
6
20

（1）用最小元素法确定初始调运方案；
（2）确定最优运输方案及最低运费；
（3）产地A1至销地B4的单位运价C14在什么范围内变化时最优调运方案不变。
（1）初始方案：x13=4,x14=3,x21=3,x23=1,x32=6,x34=3
（2）最优方案：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3
（3）最优方案不变：4条闭回路不影响检验数，9≤c14≤10
七、（20分）用图解法求解矩阵对策G=（S1，S2，A），其中

八、（20分）需要指派5人去做5项工作，每人做各项工作所消耗的时间如下表

工作
人员
A
B
C
D
E
甲
4
8
7
15
12
乙
7
9
17
14
10
丙
6
9
12
8
7
丁
6
7
14
6
10
戊
6
9
12
10
6
问指派哪个人去完成哪项工作，可使总的消耗时间最小？
最优指派：甲—C，乙—B，丙—A，丁—D，戊—E
九、（10分）某批发站每月需某种产品100件，每次订购费为5元。若每次货物到达后存入仓库，每件每月要付出0.4元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期及最佳订购批量。
=0.5 =50
第十套

一、用图解法求解下列线性规划问题，并说明解的情况。(10分)

有可行解，但MAX Z无界。
二、已知线性规划问题(10分)

其对偶问题的最优解为，试用对偶的互补松弛性求解原问题的最优解。
原问题的对偶问题为：

将代入约束条件，因为对偶问题的约束条件满足绝对不等式，则意味着所对应的原问题的变量等于零，因此，。
又因为，即对偶变量大于零，则原问题的约束条件取等式。
由此可得到
其最优解，最优值

三、已知生产甲零件分别需要A、B、C三种原料为5kg，4kg，2kg，获利12元，生产乙零件分别需要A、B、C三种原料为4kg，5kg，5kg，获利21元，现库存A、B、C三种原料为24kg，20kg，18kg，如何安排生产使获利最大？用单纯形法求解(10分)

项目
甲零件(kg)
乙零件(kg)
库存量(kg)
A
5
4
24
B
4
5
20
C
2
5
18
利润(元)
12
21

建模

转换标准型

，初始可行解
列出单纯形表

12 21 0 0 0

0 24
0 20
0 18
5 4 1 0 0
4 5 0 1 0
2 [5] 0 0 1
6
4
18/5

12 21 0 0 0

0 48/5
0 2
21 18/5
17/5 0 1 0 -4/5
[2] 0 0 1 -1
2/5 1 0 0 1/5
48/17
1
9

18/5 0 0 0 –21/5

0 31/5
12 1
21 16/5
0 0 1 -17/10 9/10
1 0 0 1/2 -1/2
0 1 0 -1/5 2/5

0 0 0 -9/5 -12/5

基可行解，代入目标函数得到最优值
四、已知以下线性规划问题(15分)

的最优单纯形表如下，分析下列条件单独变化的情况下，最优解的变化。
cj
2
-1
1
0
0
cB
xB
b
x 1
x2
x3
x4
x5
2
x 1
6
1
1
1
1
0
0
x 5
10
0
3
1
1
1

0
-3
-1
-2
0
(1) 目标函数变为；
(2) 约束条件右端项由变为；
(1) 目标函数变为
列出单纯形表
cj
2
3
1
0
0
cB
xB
b
x 1
x2
x3
x4
x5
2
x 1
6
1
1
1
1
0
0
x 5
10
0
[3]
1
1
1

0
1
-1
-2
0
cB
xB
b
x 1
x2
x3
x4
x5
2
x 1
8/3
1
0
2/3
2/3
-1/3
3
x2
10/3
0
1
1/3
1/3
1/3

0
0
-4/3
-7/3
-1/3
最优解为：x=（8/3，10/3，0，0，0）T； 最优值 （7分）
(2)因为建模，所以
列出单纯形表
cj
2
-1
1
0
0
cB
xB
b
x 1
x2
x3
x4
x5
2
x 1
3
1
1
1
1
0
0
x 5
7
0
3
1
1
1

0
-3
-1
-2
0
因此原问题和对偶问题均为可行解，问题的最优基不变。
最优解，最优值
五、已知运输表如下：(20分)

销地
产地
B1
B2
B3
B4
供应量
A1
3
2
7
6
50
A2
7
5
2
3
60
A3
2
5
4
5
25
需求量
60
40
20
15

(1) 用最小元素法确定初始调运方案；
(2) 确定最优运输方案及最低运费。
x11=10,x12=40,x21=25,x23=20,x24=15,x31=25z=420 (2)调整调运方案并确定最优解
1）解的最优性检验
u1+v1=3 u1=0
u1+v2=2 u2=4
u2+v1=7 令u1=0 u3=--1
u2+v3=2 v1=3
u2+v4=3 v2=2
u3+v1=2 v3=-2
v4=-1

因为，所以需调整
2）改进
10 40 调整为 35 15
25   25
检验
u1+v1=3 u1+v2=2 u2+v2=5 u2+v3=2 u2+v4=3 u3+v1=2
令u1=0 u1=0 u2=3 u3=--1 v1=3 v2=2 v3=--1 v4=-0

因为检验数均大于等于零，所以找到最优解。
最优解：x11=35,x12=15,x22=25,x23=20,x24=15,x31=25 z*=395
六、需要指派5人去做5项工作，每人做各项工作所消耗的时间如下表：（15分）

工作
人员
A
B
C
D
E
甲
4
8
7
15
12
乙
7
9
17
14
10
丙
6
9
12
8
7
丁
6
7
14
6
10
戊
6
9
12
10
6

问指派哪个人去完成哪项工作，可使总的消耗时间最小？
(1)使系数矩阵经变换各行各列中都出现0元素
min
→
1 3 min
↓

(2)用最少的直线划去所有0元素。

因为l=4<n 所以不是最优解。
方案改进 →＝B’
因为l=5=n 所以确定最优方案。
（3）最方案的确定
X13=X22=X31=X44=X55=1
Z*=34
最优指派：
甲—C，乙—B，丙—A，丁—D，戊—E

七、某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表，要求绘制该工程的网络图(10分)
工序
紧后工序
工序时间（天）
a
b,c,d,e
60
b
L
45
c
f
10
d
g,h
20
e
h
40
f
L
18
g
k
30
h
L
15
k
L
25
L
-
35
1
2
4
6
7
8
3
5
a
60
d
20
g
30
k
25
L

h
15
e
40
f
18
c
10
b
45

八、某批发站每月需某种产品100件，每次订购费为5元。若每次货物到达后存入仓库，每件每月要付出0.4元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期及最佳订购批量。(10分)
解：=0.5 =50
共 23 页 第 23 页