中国矿业大学：《运筹学》课程教学资源（作业习题）测试题五（答案）

测试题五答案、判断与单项选择题（本题21分，每小题3分）(错)1、若某线性规划问题有可行解，则其对偶问题也一定有可行解。(对)2、影子价格为零的资源并不意味着没有任何价值。(错）3、在产销不平衡的运输问题中，应有产地个数不等于销地个数。(错)4、正偏差变量大于等于零，负偏差变量小于等于零。5、原问题与对偶问题都有可行解，则（D）。A、原问题有最优解，对偶问题没有最优解B、原问题与对偶问题可能都没有最优解C、一个问题有最优解，另一个问题有无界解D、原问题与对偶问题都有最优解6、下列说法不正确的是（C）。A、将指派分配问题效益矩阵经过列缩减，不改变最优的分配方案，但改变最优值B、分配问题效益矩阵的每个元素都加上同一个常数k，不会影响最优的分配方案C、分配问题效益矩阵的每个元素都乘以同一个常数k，会影响最优的分配方案D、分配问题效益矩阵经过行缩减，不改变最优的分配方案，但改变最优值7、在用匈牙利法求解分配问题时，最终求得的分配应是（B）A、零元素B、独立零元素C、不同列的零元素D、不同行的零元素二、简答题（本题9分，每小题3分）1、一个运输问题中，为什么一组基变量不包含任何回路？答：因为一组基变量中若包含闭回路，说明他们对应的系数列向量是线性相关的，这与基变量对应的系数列向量线性无关矛盾。2、目标规划模型与一般的线性规划模型相比有哪些优点？答：相对于线性模型，目标规划模型有以下优点：（1)模型更灵活，更接近现实模型(2)总存在解，因为目标规划求得是满意解；(3)更能满足需求。3、网络计划中的关键路线是什么？试分析关键路线在网络计划中的作用。答：网络中总时间最长的一条路线是关键路线，即总时差为0的作业连接起来的一条路线，关键路线上的累计时间即为工期。三、（本题10分）一彩民中彩得到了50000元的收入，假定他只能用这些钱进行投资并且他要考虑下面目标：首先，出于爱国心，他决定至少用20000元购买政府公债，年息6%；其次，他把5000-15000元存入银行，年息为3%；第三，用于A、B两项目的风险投资，A项目年投资回报率（年息）预期为8%，B项目年投资回报率（年息）预期为5%，A项目回报率高，至少投资10000元，B项目回报率低，最多投资10000元，并认为A项目的重要性为B项目的2倍；第四，他希望年息尽可能达到3000元。请你帮这位彩民做出投资决策，试建立此问题的目标规划模型。（只建模，不计算）解：设该彩民用于政府公债、银行储蓄、A项目的投资和B项目的投资分别为x1，x2，x3，x4，并赋予四个目标的优先因子为P1，P2，P3，P4。建立该问题的目标规划数学模型如下：1

1 测试题五答案 一、判断与单项选择题（本题 21 分，每小题 3 分） 1、若某线性规划问题有可行解，则其对偶问题也一定有可行解。 （错） 2、影子价格为零的资源并不意味着没有任何价值。 （对） 3、在产销不平衡的运输问题中，应有产地个数不等于销地个数。 （错） 4、正偏差变量大于等于零，负偏差变量小于等于零。 （错） 5、原问题与对偶问题都有可行解，则（D）。 A、原问题有最优解，对偶问题没有最优解 B、原问题与对偶问题可能都没有最优解 C、一个问题有最优解，另一个问题有无界解 D、原问题与对偶问题都有最优解 6、下列说法不正确的是（C）。 A、 将指派分配问题效益矩阵经过列缩减，不改变最优的分配方案，但改变最优值 B、分配问题效益矩阵的每个元素都加上同一个常数 k，不会影响最优的分配方案 C、分配问题效益矩阵的每个元素都乘以同一个常数 k，会影响最优的分配方案 D、 分配问题效益矩阵经过行缩减，不改变最优的分配方案，但改变最优值 7、在用匈牙利法求解分配问题时，最终求得的分配应是（B） A、零元素 B、独立零元素 C、不同列的零元素 D、不同行的零元素 二、简答题（本题 9 分，每小题 3 分） 1、一个运输问题中，为什么一组基变量不包含任何回路？ 答：因为一组基变量中若包含闭回路，说明他们对应的系数列向量是线性相关的，这 与基变量对应的系数列向量线性无关矛盾。 2、目标规划模型与一般的线性规划模型相比有哪些优点？ 答：相对于线性模型，目标规划模型有以下优点：(1)模型更灵活，更接近现实模型； (2)总存在解，因为目标规划求得是满意解；(3)更能满足需求。 3、网络计划中的关键路线是什么？试分析关键路线在网络计划中的作用。 答：网络中总时间最长的一条路线是关键路线，即总时差为 0 的作业连接起来的一条 路线，关键路线上的累计时间即为工期。 三、（本题 10 分）一彩民中彩得到了 50000 元的收入，假定他只能用这些钱进行投资， 并且他要考虑下面目标：首先，出于爱国心，他决定至少用 20000 元购买政府公债， 年息 6%；其次，他把 5000-15000 元存入银行，年息为 3%；第三，用于 A、B 两项目 的风险投资，A 项目年投资回报率（年息）预期为 8%，B 项目年投资回报率（年息） 预期为 5%，A 项目回报率高，至少投资 10000 元，B 项目回报率低，最多投资 10000 元，并认为 A 项目的重要性为 B 项目的 2 倍；第四，他希望年息尽可能达到 3000 元。 请你帮这位彩民做出投资决策，试建立此问题的目标规划模型。（只建模，不计算） 解：设该彩民用于政府公债、银行储蓄、A 项目的投资和 B 项目的投资分别为 x1，x2， x3，x4，并赋予四个目标的优先因子为 P1，P2，P3，P4。建立该问题的目标规划数学 模型如下：

minz=Pd-+P(d,+d)+P(2d-+d)+PdX,+X2+X+x=50000x, +d -dt=20000xz+dz-d=5000x,+dj-d=15000x+d-dt=10000x,+d,-d=100000.06x,+0.03x,+0.08x,+0.05x+d=-dt=3000X,x2,x3,x4,d,dt≥0,i=1,2,3,4,5,6四、（本题15分）求下图从v到v,最小费用最大流问题，图中弧旁数字为（biCi）。V1(5.6)(3.4)(3,2)VSv2(4.1)(1.1)(9.2*(4.10vtV(2.3)解：初始状态f(0）=0构造W(f(0))VSV2vt最短路为vvv,d=5,对应的增广链为u=vvv,e=1，得f() =1V1(0.6)(0,4)(0,2)VS(11)v2(1,1)(0.2*10.10vtV:(0.3)构造W(f())2

2                                                                   , , , , , 0, 1,2,3,4,5,6. 0.06 0.03 0.08 0.05 3000 10000 10000 15000 5000 20000 50000 min ( ) (2 ) 1 2 3 4 1 2 3 4 6 6 4 5 5 3 4 4 2 3 3 2 2 2 1 1 1 1 2 3 4 1 1 2 2 3 3 4 5 4 6 x x x x d d i x x x x d d x d d x d d x d d x d d x d d x x x x z P d P d d P d d P d i i 四、（本题 15 分）求下图从 vs到 vt最小费用最大流问题，图中弧旁数字为（bij,cij）。 解：初始状态 0 (0) f  构造 ( ) (0) W f 最短路为 vs v4 vt ,d  5,对应的增广链为   vs v4 vt ,  1，得 1 (1) f  构造 ( ) (1) W f

2最短路为vV3",d=11,对应的增广链为μ=vV4V,=2，得f(2) = 3v1(0.6)(0.4)(0,2)VS(11)v2(1.1)(2.2(0:10)vtV3(2.3)构造W(f(2)VI3VSV2Vt-2此时无最短路。最大流v()=3，最小费用为27。五、（本题25分）已知线性规划问题minz=-4x,+x,+30x,-11x-2x,+3x+10x.-2xi+6x3+2x4-3x+x,=20=10-4x, +X, +7x3 +x4-X6s.t.= 60-5x +3x, +X -X6x, ≥ 0(i =1,2,...,7)用单纯形法求解时，我们得到的初表和终表如下。3

3 最短路为 vs v3 vt ,d  11,对应的增广链为   vs v4 vt ,  2，得 3 (2) f  构造 ( ) (2) W f 此时无最短路。最大流 v( f )  3，最小费用为 27。 五、（本题 25 分）已知线性规划问题                                   0( 1,2, ,7) 5 3 60 4 7 10 2 6 2 3 20 . . min 4 30 11 2 3 10 3 4 5 6 1 2 3 4 6 1 3 4 6 7 1 2 3 4 5 6 7 x i  x x x x x x x x x x x x x x s t z x x x x x x x i 用单纯形法求解时，我们得到的初表和终表如下

初表-4130-11-2310B"bX2CBXBX1X3X4X5X6X7-2062031170-4-100-531-10cj-zj终表-430-23101-11B"bCBXBX1X2X4X5X7X3X6-4X15/401/241/12-7/2445/21/1215/12-1/63X615/21/401/4-1/2cj-zj请你按要求回答下面问题：(1)填写上述初表和终表中的空白，并说明所得最优解是否是唯一解，为什么？(2)求出对偶问题的最优解。(3)考虑当b变为b=(18,13,60)，对最优解有什么影响？当b变为b=(18,14.60)对最优解是否有影响？如有影响，求出新解。解：(1)填写初表和终表-4130-11-2310B*'bCBXBX1X2X3X4X5X6X710X720-2062031X210-411001[7]-100-2X5600-531-1200-47-260320cj-zi-4130-11-2310B*bCBXBX1X2X3X4X5X6X7-4X15/401-7/24-7/41/2401/12-11X445/201/12-5/215/120-1/63X601/415/2-5/201/41-1/2ci-zj00302010最优解不唯一，因为有非基变量的检验数为0。(2)对偶问题的最优解为41/24)1/12-7/24=(0 1 -4)Y=C,B-l=(-4 -11 35/123-1/61/121/41/4-1/2(3)考虑当b变为b=(18,13,60)，4

4 初表 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 -2 0 6 2 0 3 1 -4 1 7 1 0 -1 0 0 0 -5 3 1 -1 0 cj-zj 终表 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 -4 X1 5/4 -7/24 0 1/24 1/12 45/2 1/12 1 5/12 -1/6 3 X6 15/2 1/4 0 1/4 -1/2 cj-zj 请你按要求回答下面问题： (1)填写上述初表和终表中的空白，并说明所得最优解是否是唯一解，为什么？ (2)求出对偶问题的最优解。 (3)考虑当 b 变为 T b  (18,13,60) ，对最优解有什么影响？当 b 变为 T b  (18,14,60) ， 对最优解是否有影响？如有影响，求出新解。 解：(1)填写初表和终表 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 10 X7 20 -2 0 6 2 0 3 1 1 X2 10 -4 1 [7] 1 0 -1 0 -2 X5 60 0 0 -5 3 1 -1 0 cj-zj 20 0 -47 -26 0 32 0 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 -4 X1 5/4 1 -7/24 -7/4 0 1/24 0 1/12 -11 X4 45/2 0 1/12 -5/2 1 5/12 0 -1/6 3 X6 15/2 0 1/4 -5/2 0 1/4 1 -1/2 cj-zj 0 0 3 0 2 0 10 最优解不唯一，因为有非基变量的检验数为 0。 (2)对偶问题的最优解为   0 1 4 1/ 2 1/ 4 1/ 4 1/ 6 1/12 5 /12 1/12 7 / 24 1/ 24 4 11 3 -1                Y  CB B    (3)考虑当 b 变为 T b  (18,13,60)

5241/12-7/241/24181B"b =231/125/12-1/613所以对最优基没有影响，≥0，12-1/21/41/4609141)5123最优解为9-241241121/12-7/241/24181123当b变为b=(18.14.60)T，B-b=I-1/61/125/1214≤0,6-1/21/4(601/4号对最优解有影响，将数据代入原终表，用对偶单纯形法进行求解。-4130-11-2310BlbCBXBX1X2X3X4X5X7X6.4X10-1/121[-7/24]-7/41/2401/12-11X401/12-5/215/120-1/6139/63X6-5/215/201/401/41-1/200302010cj-zj-4130-11-2310BbCBXBX1X2X3X4X5X7X61X22-24/7160-1/70-2/7-11X4162/72/70-313/70-1/73X652/76/70-402/71-3/7003020cj-zj10最优解为（0,2/7,0,162/7,0,52/70）六、（本题20分）已知运输问题的运价表如下所示。B1B2B3产地销地B4产量A1498100-25A220153050A3712101980销量70704040-60其中A1的物质不能送到B2，B1的需求量为40~60之间。求总运费最小的最优解。解：此题为一个产销不平衡的运输问题，总产量为230，最低需求量为220，最高需求量为240，虚拟一个产量为10的产地，列出表格如下5

5 0 4 1 9 12 1 23 24 5 60 13 18 1/ 2 1/ 4 1/ 4 1/ 6 1/12 5/12 1/12 7 / 24 1/ 24 -1                                          B b  ，所以对最优基没有影响， 最优解为 T       4 1 9 12 1 23 24 5 。 当 b 变为 T b  (18,14,60) ， 0 2 1 7 6 1 23 12 1 60 14 18 1/ 2 1/ 4 1/ 4 1/ 6 1/12 5/12 1/12 7 / 24 1/ 24 -1                                           B b  ， 对最优解有影响，将数据代入原终表，用对偶单纯形法进行求解。 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 -4 X1 -1/12 1 [-7/24] -7/4 0 1/24 0 1/12 -11 X4 139/6 0 1/12 -5/2 1 5/12 0 -1/6 3 X6 15/2 0 1/4 -5/2 0 1/4 1 -1/2 cj-zj 0 0 3 0 2 0 10 CB XB B -1 b -4 1 30 -11 -2 3 10 X1 X2 X3 X4 X5 X6 X7 1 X2 2/7 -24/7 1 6 0 -1/7 0 -2/7 -11 X4 162/7 2/7 0 -3 1 3/7 0 -1/7 3 X6 52/7 6/7 0 -4 0 2/7 1 -3/7 cj-zj 0 0 3 0 2 0 10 最优解为（0,2/7,0,162/7,0,52/7,0） 六、（本题 20 分）已知运输问题的运价表如下所示。 产地 销地 B1 B2 B3 B4 产量 A1 4 - 9 8 100 A2 20 25 15 30 50 A3 7 12 10 19 80 销量 40-60 70 70 40 其中 A1 的物质不能送到 B2，B1 的需求量为 40~60 之间。求总运费最小的最优解。 解：此题为一个产销不平衡的运输问题，总产量为 230，最低需求量为 220，最高需求 量为 240，虚拟一个产量为 10 的产地，列出表格如下

销地B1BI1B2B4产量B3产地A144M98100202025153050A2771210A319800A4MMMM10销量4020707040利用伏格尔法得到初始可行解，如下销地B1BI'B2B3B4产量产地A1401010401005050A2701080A3A41010销量2070704040采用位势法检验销地B1B2B3B4UiB1产地A100000M-11A2101080616220A30101A4M0M-5M-4-4M-74Vi41198此时检验数都非负，说明已达到最优，总运费最小的最优解如第二张表所示。6

6 销地 产地 B1 B1’ B2 B3 B4 产量 A1 4 4 M 9 8 100 A2 20 20 25 15 30 50 A3 7 7 12 10 19 80 A4 M 0 M M M 10 销量 40 20 70 70 40 利用伏格尔法得到初始可行解，如下 销地 产地 B1 B1’ B2 B3 B4 产量 A1 40 10 10 40 100 A2 50 50 A3 70 10 80 A4 10 10 销量 40 20 70 70 40 采用位势法检验 销地 产地 B1 B1’ B2 B3 B4 Ui A1 0 0 M-11 0 0 0 A2 10 10 8 0 16 6 A3 2 2 0 0 10 1 A4 M 0 M-7 M-5 M-4 -4 Vj 4 4 11 9 8 此时检验数都非负，说明已达到最优，总运费最小的最优解如第二张表所示