中国矿业大学运筹学(64学时)复习题及答案
时间：2021-10-12 11:18:39 来源：网友投稿
部分习题 一、 （该题已经讲过了）某公司制造三种产品 A、B、C，需要两种资源（劳动力和原材料），现要确定总利润最大的生产计划，列出下述线性规划 030 5 4 345 5 3 65 3 max3 2 13 2 13 2 13 2 1x x ** x ** x ** x x z， ，（原材料）
＋ ＋（劳动力）
＋ ＋＋ ＋ 求：（1）线性规划问题的最优解； 首先将问题标准化：
0 , ,30 5 4 345 5 3 65 3 max5 4 3 2 15 3 2 14 3 2 13 2 1x x x x ** x x ** x x ** x x z， ，＋ ＋＋ ＋＋ ＋ cj 3 1 5 0 0 i
C B
XB
b x 1 x 2 x 3 x 4 x 5 0 0 x4 x5 45 30
6 3
3 4 5 【5】
1 0 0 1 9 6
3 1 5 0 0
0 5 x4 x3
15 6 3 3/5 -1 4/5 0 1 1 0 -1 1/5
0 -3 0 0 -1
最优解为 X*=(x 1 ,x 2 ,x 3 ,x 4 ,x 5 ) T =(0,0,6,15,0) T ，最优目标值 z*=30 （2）求对偶问题的数学模型及其最优解； 0 , 05 5 51 4 33 3 630 45 min2 12 12 12 12 1y yy yy yy yy y w y 1 *=0,y 2 *=1
(3) 最优解不变的情况下，求产品 A 的利润允许变化范围；
最优解不变的情况下， 3 , 01 1 c c
（4）假定能以 10 元的价格购进 15 单位的材料，这样做是否有利，为什么？ 有利 单位材料的影子价格是 1 元，10 元钱购进 15 单位的材料的单位价格为 2/3 元，低于影子价格。同时，在保持最优基不变的情况下 15 302 b
购进 15 吨的原材料，最优基不变。该材料的影子价格仍为 1 元。
（5）当可利用的资源增加到 60 单位时，求最优解。
121560455101 11 "b B b cj 3 1 5 0 0
C B
XB
b x 1 x 2 x 3 x 4 x 5 0 5 x4 x3
-15 12 3 3/5 -1 4/5 0 1 1 0 【-1】
1/5
0 -3 0 0 -1
0 5 x5 x3
15 9 -3 6/5 1 3/5 0 1 -1 1/5 1 0
-3 -2 0 -1 0
最优解为 X*=(x 1 ,x 2 ,x 3 ,x 4 ,x 5 ) T =(0,0,9,0,15) T ，最优目标值 z*=45 （6）当产品 B 的原材料消耗减少为 2 个单位时，是否影响当前的最优解，为什么？ x 2 在最有表是非基变量，该产品的原材料消耗只影响 x 2 的检验数。
521235101 121 "2P B P
所以最优解不变0 15215 0 12"212 2 P B C cB （7）增加约束条件 2x 1 +x 2 +3x 3 ≤20，对原最优解有何影响，对对偶解有何影响？ 增加的约束条件，相当于增加了一个约束方程 20 3 26 3 2 1 x x x x
cj 2 4 1 0 0 0 C B
X B
b
x 1 x 2 x 3 x 4 x 5 x 6 0 5 0 x 4 x 3 x 6 15 6 20
3 3/5 2 -1 4/5 1 0
1 3
1
0
0 -1 1/5 0 0 0 1
0 -3 0
0
-1 0 0 5 0 x 4 x 3 x 6
15 6 2 3
3/5
4/5 -1 4/5 -7/5
0
1
0
1
0 0
-1 1/5
-3/5
0
0
1
0
-3
0 0 -1
0 对原问题的最优解无影响，对对偶问题的最优解也无影响。
二、考虑下列线性规划 MaxZ=2X 1 +3X 2 2X 1 + 2X 2 +X 3 =12 X 1 +2X 2
+X 4 =8 4X 1
+X 5 =16 4X 2
+X 6 =12 Xj≥0（j=1,2,…6）
其最优单纯形表如下：
基变量
X1 X2 X3 X4 X5 X6 X3 0 0 0 1 -1 -1/4 0 X1 4 1 0 0 0 1/4 0 X6 4 0 0 0 -2 1/2 1 X2 2 0 1 0 1/2 -1/8 0 σj
0 0 0 -3/2 -1/8 0
1）
当 C2=5 时，求新的最优解 2）
当 b3=4 时，求新的最优解
3）
当增加一个约束条件 2X 1 +X 2 ≤12，问最优解是否发生变化，如果发生变化求新解？ 解当 C2=5 时 σ 4 =－5/2 σ 5 =1/8＞0 所以最优解发生变化
基变量
X1 X2 X3 X4 X5 X6 0 X3 0 0 0 1 -1 -1/4 0 2 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 5 X2 2 0 1 0 1/2 -1/8 0 σj
0 0 0 -5/2 1/8 0 0 X3 2 0 0 1 －2 0 1/2 2 X1 2 1 0 0 1 0 -1/2 0 X5 8 0 0 0 -4 1 2 5 X2 3 0 1 0 0 0 1/4 σj
0 0 0 -2 0 -1/4 最优解为 X1=2，X2=3,Z＝19 2）当 b3=4 时
基变量
X1 X2 X3 X4 X5 X6 0 X3 3 0 0 1 -1 -1/4 0 2 X1 1 1 0 0 0 1/4 0 0 X6 -3 0 0 0 -2 1/2 1 3 X2 5/2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 0 X3 9/2 0 0 1 0 -1/2 1 2 X1 1 1 0 0 0 1/4 0 0 X4 3/2 0 0 0 1 -1/4 -1/2 3 X2 7/4 0 1 0 0 0 1/4 σj 0 0 0 0 -1/2 -3/4 此时最优解为 X1=1，X2=7/4,Z＝29/4 3)增加一个约束条件 基变量
X1 X2 X3 X4 X5 X6 X7 X3 0 0 0 1 -1 -1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 0 X2 2 0 1 0 1/2 -1/8 0 0 X7 12 2 1 0 0 0 0 1
σj
0 0 0 -3/2 -1/8 0 0 X3 0 0 0 1 -1 -1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 0 X2 2 0 1 0 1/2 -1/8 0 0 X7 2 0 0 0 －1/2 －3/8 0 1 σj
0 0 0 -3/2 -1/8 0 0 由于 X7＝2 大于 0，所以最优解不变
三、用对偶单纯形法求下面问题 0 ,75 380 2
. .6 4 ) ( min2 12 12 12 1x ** ** xt sx x x f 解：
C j
4 6 0 0 min{( z j
- c j )/a i*j } C B
X B
b x 1
x 2
x 3
x 4
a i*j <0 0 x 3
80 1 (2) 1 0 {4,3*} 0 x 4
75 3 1 0 1
OBJ= 0 z j
0 0 0 0
z j
- c j
4 6 0 0
C j
4 6 0 0
C B
X B
b x 1
x 2
x 3
x 4
6 x 2
40 1/2 1 1/2 0
0 x 4
35 (5/2) 0 1/2 1 {2/5*,6} OBJ= 240 z j
3 6 3 0
z j
- c j
1 0 3 0
C j
4 6 0 0
C B
X B
b x 1
x 2
x 3
x 4
6 x 2
33 0 1 3/5 1/5
4 x 1
14 1 0 1/5 2/5
OBJ= 254 z j
4 6 14/5 2/5
z j
- c j
0 0 14/5 2/5
答 答：最优解为 x 1 =14，x 2 =33，目标函数值为 254。
四、A、B 两个煤矿负责供应甲、乙、丙三个城市煤炭。已知 A、B 两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可少供应 0－30 万吨，乙城市需求须全部满足，丙城市需求不少于 270 万
吨。试求：将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。
产
销 甲 乙 丙 产量 A B 15 21 18 25 22 16 400 450 销量（T）
320 250 350
解：(1)依题意得产销平衡表如下：
产
销 甲’ 甲’’ 乙 丙’
丙’’ 产量 A B C 15 21 M 15 21 0 18 25 M 22 16 M 22 16 0 400 450 70 销量（T）
290 30 250 270 80
(2)做初始的调运方案（伏格尔法）
产
销 甲’ 甲’’ 乙 丙’
丙’’ 产量 A
150 15
15
250 18
22
22 400
B
21
21
25
16
16 450 140 30
270 10 C
M
0
M
M
0 70
70 销量（T）
290 30 250 270 80
（3）用位势法进行检验 产
销 甲’ 甲’’ 乙 丙’
丙’’ U A
0 15
0 15
0 18
12 22
12 22
-6
B
21
21
25
16
16
0 0 0 1 0 0
C
M
0
M
M
0
-16 M-5 -5 M-8
0 V 21 21 24 16 16
(4) 做闭回路调整 调整后为：
产
销 甲’ 甲’’ 乙 丙’
丙’’ 产量 A
150 15
15
250 18
22
22 400
B
21
21
25
16
16 450 140
270 40 C
M
0
M
M
0 70
30
40 销量（T）
290 30 250 270 80
（5）进行进一步检验 产
销 甲’ 甲’’ 乙 丙’
丙’’ U A
0 15
0 15
0 18
12 22
12 22
-6
B
21
21
25
16
16
0 0 5 1 0 0 C
M
0
M
M
0
-16 M-5 0 M-8 M 0 V 21 16 24 16 16
(6) 调整后的方案为最优方案 最低费用＝150×15＋250×18＋140×21＋270×16＋40×16＋30×0＋40×0＝14650
五、分配甲、乙、丙、丁四人去完成 5 项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。
A B C D E
甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 解：假设增加一个人戊完成各项工作的时间取 A、B、C、D、E 最小值。
得效率矩阵为：
32 20 26 27 2445 23 36 42 2432 40 28 27 3433 20 26 38 3937 42 31 29 25戊丁丙乙甲E D C B A 各行减最小值，各列减最小值：得
7 5 7 417 12 19 113 0 78 0 5 18 197 17 5 4 0 戊丁丙乙甲E D C B A 变换得 6 4 6 316 11 1814 0 77 0 4 17 187 18 5 4 0 戊丁丙乙甲E D C B A 进一步 2 0 0 2 312 0 7 14 00 18 0 0 113 0 0 13 183 18 1 0 0戊丁丙乙甲E D C B A
最有指派方案 0 0 1 0 00 0 0 0 11 0 0 0 00 1 0 0 00 0 0 1 0戊丁丙乙甲E D C B A 甲——B，乙——C,D，丙——E，丁——A 最低费用＝29＋26＋20＋32＋24＝131
六、某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为 2 个单位，乙种炉每台投资为 1 个单位，总投资不能超过 10 个单位；又该厂被许可用电量为 2 个单位，乙种炉被许可用电量为 2 个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量 1 个单位。已知甲种炉每台收益为 6 个单位，乙种炉每台收益为 4 个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？该问题也可如下表表示。（要求用割平面法求解该整数规划问题）
甲种炉(x 1 )
乙种炉(x 2 )
限
量 每台投资/单位 2 1 10 用电量/单位 -1 2 2 收益/单位 6 4
解：设 x 1 ,x 2 为甲乙种炉应建台数，则 且为整数 , 0 ,2 210 2. .4 6 max2 12 12 12 1x ** ** xt sx x z 用单纯形法求最优解，见下表。
基变量 b X 1 X 2
X 3
X 4
i
X 3
10 2 1 1 0 5 X 4
2 -1 2 0 1 -- -z 0 6 4 0 0
X 1
5 1 1/2 1/2 0 10 X 4
7 0 5/2 1/2 1 14/5 -z -30 0 1 -3 0
X 1
18/5 1 0 2/5 -1/5
X 2
14/5 0 1 1/5 2/5
-z -32.8 0 0 -16/5 -2/5
最优解为 8 . 32 , ) 0 , 0 , , ( x0 5145180 zT 确定割平面方程：0 )525154251452514 3 24 3 2 x x ** x x（ 取 从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。
基变量 b X 1 X 2
X 3
X 4
X 5 X 1
18/5 1 0 2/5 -1/5 0 X 2
14/5 0 1 1/5 2/5 0 X 5 -4/5 0 0 -1/5 -2/5 1 -z -32.8 0 0 -16/5 -2/5 0
基变量 b X 1 X 2
X 3
X 4
X 5 X 1
4 1 0 1/2 0 -1/2 X 2
2 0 1 0 0 1 X 4 2 0 0 1/2 1 -5/2 -z -32 0 0 -3 0 -1 32 z ,0 2 ,2,0 4 XT ， ）
， （ 。此解为整数解，故计算停止。
七、某公司打算将 3 千万元资金用于改造扩建所属的 3 个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大。
利润
投资 工厂 0 1 千万 2 千万 3 千万 1 0 2.5 4 10 2 0 3 5 8.5 3 0 2 6 9 解：K 为阶段变量，k=1,2,3
S k :第 k 阶段所剩的资金数
X k ：第 k 阶段分配给第 k 个工厂的资金数
g k （x k ）：将 x k 分配给第 k 个工厂的效益
状态转移方程：S k+1 = S k -x k
递推关系：
第三阶段，k=3 X3=s3 ) ( max ) (3 3333 3x g s fs x
x 3 s 3 g 3 (x 3 ) f 3 (s 3 ) x* 3 0 1 2 3
0 0
0 0 1
2
2 1 2
6
6 2 3
9 9 3 第二阶段：
s3=s2-x2 ， 0 s2 3 ， 0 x2 s2 )} ( ) ( { max ) (2 2 3 2 22 02 22x s f x g s fs x x 2 s 2 )} ( ) ( { max ) (2 2 3 2 22 02 22x s f x g s fs x f 2 (s 2 ) x* 2 0 1 2 3
0 0+0
0 0 1 0+2 3+0
2 1 2 0+6 3+2 5+0
6 0 3 0+9 3+6 5+2 8.5+0 9 0,1 第三阶段 S1=3 S2=s1-x1, 0 x1 s1 x 1 s 1 )} ( ) ( { max ) (1 1 1 1 11 1 01 1x s f x g s fs x f 1 (s 1 ) x* 1 0 1 2 3
3 0+9 2.5+6 4+3 10+0 10 3
最优分配方案为，x1*=3,x2*=0,x3*=0 ) ( max ) (1 , , 1 )} ( ) ( { max ) (10n ns xn nk k k k ks xk kx g s fn k x s f x g s fn nk k
最佳获益值：10 千万。
八、甲乙乒乓球队进行团体对抗赛，每对由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得 1 分，输者得-1 分，可知三赛三胜得 3 分，三赛二胜得 1 分，三赛一胜得-1 分，三赛三负得-3 分。甲队的策略集为 S 1 ={α 1 ，α 2 ，α 3 }，乙队的策略集为 S 1 ={β 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=（a ij ）中等式
max
min a ij
= min
max a ij
i
j
j
i 成立时，局中人才有最优纯策略，并把（α 1 ，β 2 ）称为对策 G 在纯策略下的解，又称（α 1 ，β 2 ）为对策 G 的鞍点。
九、矩阵对策的混合策略
解：首先设甲使用 α 1 的概率为 X 1 ’，使用 α 2 的概率为 X 2 ’，并设在最坏的情况下（即乙出对其最有利的策略情况下），甲的赢得的平均值等于 V。这样我们建立以下的数学关系：
1.甲使用 α 1 的概率 X 1 ’和使用 α 2 的概率 X 2 ’的和为 1，并知概率值具有非负性，即 X 1 ’+ 5
9 ...
[中国矿业大学运筹学(64学时)复习题及答案]相关文章