中国矿业大学运筹学(64学时)复习题及答案

　 部分习题 一、 （该题已经讲过了）某公司制造三种产品 A、B、C，需要两种资源（劳动力和原材料），现要确定总利润最大的生产计划，列出下述线性规划 030 5 4 345 5 3 65 3 max3 2 13 2 13 2 13 2 1x x xx x xx x xx 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 xx x x xx x x xx 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 xx xx 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 xx xx 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 xx 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 ...