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

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

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

四、（本题15分）求下图从v到v最小费用最大流问题，图中弧旁数字为（bij,C）。v1(5.6)< (3.4)(3,2)VS(4.1)v2(1.1)(9.2*(4.10)vtV3(2.3)五、（本题20分）已知运输问题的运价表如下所示。B1产地销地B2B3B4产量9A148100-A22025153050A3712191080销量70704040-60其中A1的物质不能送到B2，B1的需求量为40~60之间。求总运费最小的最优解。六、（本题25分）已知线性规划问题minz=-4x,+x2+30x,-11x4-2xs+3x+10x(-2x)-3x+x,=20+6x+2x=10-4x, +X2+7x; +X4-Xs.t.= 60-5x3+3x+Xs-X6x,≥0(i=1,2,,7)用单纯形法求解时，我们得到的初表和终表如下。初表-4130-11-2310B*bCBXBX2X3X7X1X4X5X6-20620317-4110-1000-531-10cj-zj2

2 四、（本题 15 分）求下图从 vs到 vt最小费用最大流问题，图中弧旁数字为（bij,cij）。 五、（本题 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 之间。求总运费最小的最优解。 六、（本题 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 用单纯形法求解时，我们得到的初表和终表如下。 初表 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

终表-41-231030-11B"bXpX1X4X5X7CBX2X3X6-4X105/4-7/241/241/12145/21/125/12-1/630X615/21/41/4-1/2cj-zj请你按要求回答下面问题：（1)填写上述初表和终表中的空白，并说明所得最优解是否是唯一解，为什么？(2)求出对偶问题的最优解。(3)考虑当b变为b=(18,13,60)，对最优解有什么影响？当b变为b=(18,14,60)，对最优解是否有影响？如有影响，求出新解。3

3 终表 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) ， 对最优解是否有影响？如有影响，求出新解