中国矿业大学运筹学复习题及答案Word文件下载.docx
《中国矿业大学运筹学复习题及答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《中国矿业大学运筹学复习题及答案Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
有利
单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。
同时，在保持最优基不变的情况下
购进15吨的原材料，最优基不变。
该材料的影子价格仍为1元。
（5）当可利用的资源增加到60单位时，求最优解。
-15
12
【-1】
6/5
-2
最优解为X*=（x1,x2,x3,x4,x5）T=（0,0,9,0,15）T，最优目标值z*=45
（6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？
x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。
（7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？
增加的约束条件，相当于增加了一个约束方程
cj
2
x1
x6
20
1
0
-1
3/5
4/5
-7/5
-3/5
-3
对原问题的最优解无影响，对对偶问题的最优解也无影响。
二、考虑下列线性规划
MaxZ=2X1+3X2
2X1+2X2+X3=12
X1+2X2+X4=8
4X1+X5=16
4X2+X6=12
Xj≥0（j=1,2,…6）
其最优单纯形表如下：
基变量
X1
X2
X3
X4
X5
X6
-1/4
1/4
1/2
-1/8
σj
-3/2
1）当C2=5时，求新的最优解
2）当b3=4时，求新的最优解
3）当增加一个约束条件2X1+X2≤12，问最优解是否发生变化，如果发生变化求新解？
解当C2=5时
σ4=－5/2
σ5=1/8＞0所以最优解发生变化
-5/2
1/8
－2
-1/2
8
-4
最优解为X1=2，X2=3,Z＝19
2）当b3=4时
5/2
9/2
3/2
7/4
-3/4
此时最优解为X1=1，X2=7/4,Z＝29/4
3）增加一个约束条件
X7
－1/2
－3/8
由于X7＝2大于0，所以最优解不变
三、用对偶单纯形法求下面问题
解：
Cj
min{（zj-cj）/ai*j}
ai*j<
80
（2）
{4,3*}
75
OBJ=
zj
zj-cj
4
40
1/2
35
（5/2）
{2/5*,6}
240
33
14
2/5
254
14/5
答：
最优解为x1=14，x2=33，目标函数值为254。
四、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。
已知A、B两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。
由于供不应求，经协商，甲城市必要时可少供应0－30万吨，乙城市需求须全部满足，丙城市需求不少于270万吨。
试求：
将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。
产销
甲
乙
丙
产量
A
B
21
18
25
22
16
400
450
销量（T）
320
250
350
（1）依题意得产销平衡表如下：
甲’
甲’’
丙’
丙’’
C
M
70
290
270
80
（2）做初始的调运方案（伏格尔法）
150
140
10
（3）用位势法进行检验
U
-6
-16
M-5
-5
M-8
V
24
（4）做闭回路调整
调整后为：
（5）进行进一步检验
（6）调整后的方案为最优方案
最低费用＝150×
15＋250×
18＋140×
21＋270×
16＋40×
16＋30×
0＋40×
0＝14650
五、分配甲、乙、丙、丁四人去完成5项任务。
每人完成各项任务时间如下表所示。
由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。
D
E
29
31
42
37
39
38
26
34
27
28
32
丁
36
23
假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。
得效率矩阵为：
各行减最小值，各列减最小值：
得
变换得
进一步
最有指派方案
甲——B，乙——C,D，丙——E，丁——A
最低费用＝29＋26＋20＋32＋24＝131
六、某厂拟建两种不同类型的冶炼炉。
甲种炉每台投资为2个单位，乙种炉每台投资为1个单位，总投资不能超过10个单位；
又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。
已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。
试问：
应建甲、乙两种炉各多少台，使之收益最大？
该问题也可如下表表示。
（要求用割平面法求解该整数规划问题）
甲种炉（x1）
乙种炉（x2）
限量
每台投资/单位
用电量/单位
收益/单位
设x1,x2为甲乙种炉应建台数，则
用单纯形法求最优解，见下表。
--
-z
7
14/5
-30
18/5
2/5
-1/5
-16/5
-2/5
最优解为
确定割平面方程：
从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。
-4/5
-32
。
此解为整数解，故计算停止。
七、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。
各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大。
利润投资
工厂
1千万
2千万
3千万
K为阶段变量，k=1,2,3
Sk:
第k阶段所剩的资金数
Xk：
第k阶段分配给第k个工厂的资金数
gk（xk）：
将xk分配给第k个工厂的效益
状态转移方程：
Sk+1=Sk-xk
递推关系：
第三阶段，k=3
X3=s3
s3
g3（x3）
f3（s3）
x*3
第二阶段：
s3=s2-x2，0s23，0x2s2
s2
f2（s2）
x*2
0+0
0+2
3+0
0+6
3+2
5+0
0+9
3+6
5+2
+0
0,1
第三阶段
S1=3
S2=s1-x1,0x1s1
s1
f1（s1）
x*1
+6
4+3
10+0
最优分配方案为，x1*=3,x2*=0,x3*=0
最佳获益值：
10千万。
八、甲乙乒乓球队进行团体对抗赛，每对由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。
比赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。
甲队的策略集为S1={α1，α2，α3}，乙队的策略集为S1={β1，β2，β3}，根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下：
试问这次比赛各队应采用哪种阵容上场最为稳妥。
甲队的α1，α2，α3三种策略可能带来的最少赢得，即矩阵A中每行的最小元素分别为：
1，-3，-1，
在这些最少赢得中最好的结果是1，即甲队应采取策略α1，无论对手采用什么策略，甲队至少得1分。
而对乙队来说，策略β1，β2，β3可能带来的最少赢得，即矩阵A中每列的最大因素（因为两人零和策甲队得分越多，就使得乙队得分越少），分别为：
3，1，3，
其中乙队最好的结果为甲队得1分，这时乙队采取β2策略，不管甲队采用什么策略甲队的得分不会超过1分（即乙队的失分不会超过1）。
这样可知甲队应采用α1策略，乙队应采取β2策略。
把这种最优策略α1和β2分别称为局中人甲队、乙队的最优纯策略。
这种最优纯策略只有当赢得矩阵A=（aij）中等式
maxminaij=minmaxaij
ijji
成立时，局中人才有最优纯策略，并把（α1，β2）称为对策G在纯策略下的解，又称（α1，β2）为对策G的鞍点。
九、矩阵对策的混合策略
首先设甲使用α1的概率为X1’，使用α2的概率为X2’，并设在最坏的情况下（即乙出对其最有利的策略情况下），甲的赢得的平均值等于V。
这样我们建立以下的数学关系：
1.甲使用α1的概率X1’和使用α2的概率X2’的和为1，并知概率值具有非负性，即X1’+X2’=1，且有X1’≧0，X2’≧0.
2.当乙使用β1策略时，甲的平均赢得为：
5X1’+8X2’，此平均赢得应大于等于V，即5X1’+8X2’≧V
3.当乙使用β2策略时，甲的平均赢得为：
9X1’+6X2’，此平均赢得应大于等于V，即9X1’+6X2’≧V
第二步，我们来考虑V的值，V的值与赢得矩阵A的各因素的值是有关的，如果A的各元素的值都大于零，即不管甲采用什么策略，乙采用什么策略，甲的赢得都是正的。
这时的V值即在乙出对其最有利的策略时甲的平均赢得也显然是正的。
因为A的所有元素都取正值，所以可知V﹥0.
第三步，作变量替换，令Xi=
（i=1，2）
考虑到V﹥0，这样把以上5个数量关系式变为：
X1+X2=
，X1≧0，X2≧0，
5X1+8X2≧1
9X1+6X2≧1
对甲来说，他希望V值越大越好，也就是希望
的值越小越好，最后，我们就建立起求甲的最优混合策略的线性规划的模型如下：
minX1+X2
约束条件：
5X1+8X2≧1
X1≧0，X2≧0
同样求出乙最优混合策略，设y1’,y2’分别为乙出策略β1，β2的概率，V为甲出对其最有利的策略的情况下，乙的损失的平均值。
同样我们可以得到：
y1’+y2’=1,
5y1+9y2≦V
8y1+6y2≦V
y1’≧0，y2’≧0.
同样作变量替换，令yi=
得关系式：
y1+y2=
5y1+9y2≦1
8y1+6y2≦1
y1≧0，y2≧0.
乙希望损失越少越好，即V越小越好而
越大越好，这样我们也建立了求乙的最优混合策略的线性规划的模型如下：
maxy1+y2
5y1+9y2≦1
十、绘制工程图，计算各工作的最早开始时间和最早完工时间，并给出关键路线。
工序
内容
工时（天）
紧前工序
F
G
初步研究
研究选点
准备调研方案
联系调研点
培训工作人员
实地调研
写调研报告并汇总
/
A
B、C
D、E
F
（１）工程图如下：
（２）各工序时间如下图，
工程
ES
EF
13
G
17
（３）关键路线是A---C---E---F---G
升级会员 