1、广东工业大学试卷用纸，共 11 页，第 0 页学 院： 专 业： 学 号： 姓 名： 装 订 线广东工业大学考试试卷 ( A )课程名称: 运筹学 B 试卷满分 100 分考试时间: 2008 年 7 月 11 日 (第 20 周 星期 五 )题 号 一 二 三 四 五 六 七 八 九 十 总分评卷得分评卷签名复核得分复核签名一、判断题（每小题 2 分，共 20 分，无须改错）1标准形式的线性规划模型中决策变量的取值可以无任何限制。 （ ）2线性规划问题的可行域一定非空。 （ ）3若线性规划问题无可行解，则其对偶问题一定无可行解。 （ ）4任何一个无向图中偶点的个数不能是奇数。 （ ）5对产大
2、于销的运输问题，可通过添加假想的销地化为产销平衡运输问题。（ ） 6目标规划中任意一个目标约束的正负偏差变量不可能同时为正数。 （ ）7若指派问题的系数矩阵中某行元素都减去同一个常数，则得到的新矩阵为系数矩阵的指派问题与原问题有同样的最优解（ ）8增广链上的每条后向边都为零流边。 （ ）9动态规划的最优策略应该具有性质，无论先前的状态与决策如何，当前的决策应该是最优。 （ ）10矩阵对策就是二人有限零和对策。 （ ）广东工业大学试卷用纸，共 11 页，第 1 页二、单项选择题（每小题 2 分，共 20 分）1下列哪个模型是线性规划模型 A B0,32.min211ytsz 无2121,403c
3、os.inminxtwC D0,345max2121x 0,354.|min2121xtsz2若用单纯形法求解线性规划问题得到的最终单纯形表中，基变量不含人工变量，且非基变量的检验数均非零，则线性规划问题为下面的情形 A有唯一最优解， B有无穷多个最优解， C无界解， D无可行解。3若线性规划的原问题不存在最优解，则对偶问题 A可能存在最优解，B不存在最优解， C一定是无可行解， D一定是无界解。4若线性规划问题的某个资源常数发生变化，则在最终单纯形表中这一变化 A对检验数存在影响， B对 b 列数存在影响， C对该资源常数所在行的数存在影响， D对所有数都无影响。5对于有 m 个产地 n 个
4、销地的产销平衡运输问题的表上作业法求解，下面不正确的说法是 A每个空格有唯一的闭回路， B数字格的个数为 m+n-1， C沃格尔法得到的调运方案是最优方案， D若存在负检验数，则调运方案仍可改进。6对于目标规划问题的求解，在满足一个目标时 A必须同时考虑优先级别较低的目标， B不得违背已经得到满足的优先级别更高的目标，C不必顾虑优先级别较高的目标， D无须考虑上述情况。7若一个无向图可以一笔画出，则该图中 广东工业大学试卷用纸，共 11 页，第 2 页A最多有一个奇点，B恰好有两个奇点，C最多有两个奇点，D 没有奇点。8下图v1v2v3 v4v5的邻接矩阵是 A ，B ，C ，D 010101
5、010100109在一个容量网络中，一个可行流满足的条件中不包括下面的哪一点 A各边上的流量不全为零； B对每个中间点，流入的物质的和等于流出的物质的和； C每边上的流量不超过其容量； D发点发出的物资的和等于收点接受的物资的和。10在矩阵对策中，若局中人 1 的赢得矩阵不存在鞍点，则 A矩阵对策问题虽然存在纯策略意义下的解，但不能通过求矩阵鞍点的方法求解；B矩阵对策不存在解；C矩阵对策不存在纯策略意义下的解；D矩阵对策不存在混合策略意义下的解。三、 设有如下的线性规划问题广东工业大学试卷用纸，共 11 页，第 3 页0,3524min2131xxz无（1） 求该线性规划问题的标准形式；（6
6、分）（2） 写出其对偶问题模型。 （6 分）四、 设用单纯形法求解某极大化线性规划问题得到如下的单纯形表2 0 3/2 0 0 0CB XB b x1 x2 x3 x4 x5 x6a x1 2 d -1 0 0 1 -1b x3 3/2 0 2 1 0 -1 2c x4 0 e 0 0 1 -1 0j 0 -1 0 0 -1/2 f(1) 试求上述表中的各参数 af 的值（6 分）(2) 上表是否给出了最优解，若是则求出最优解及对偶问题最优解（6 分）五、某公司拟建立 3 个超市，可选的地址有 A、B、C 三处。在不同地址建立超市，每个月的营业利润估算如下表所示（单位：万元）：超市地址1 2
7、3A 16 20 30B 12 15 20C 10 13 16问这三个超市应如何分布，可使公司总的营业利润最高？（12 分）六、下面的图给出了某工厂 7 个车间科室之间的内部网线可行的架设路线及架设成本（单位：百元） 。（1）如何架设才能将所有 7 个单位连接起来，并使总成本最低？（8 分）（2）若图中 A、B 两个单位之间必须直接连通，则最低总成本是多少？（ 4 分）广东工业大学试卷用纸，共 11 页，第 4 页57468612374529A4B七、设矩阵对策问题 41253312pq（1） 当实数 满足什么条件时，该问题以纯局势 为平衡局势，此时矩阵qp, ),(2对策的值是多少？（8 分
8、）（2） 纯局势 可不可能为平衡局势？（4 分）),(21广东工业大学试卷用纸，共 11 页，第 5 页广东工业大学试卷参考答案及评分标准 ( )课程名称: 运筹学 。考试时间: 2008 年 7月 11日 (第 20 周 星期五 )一、判断题（每小题 2 分，共 20 分，无须改错）1标准形式的线性规划模型中决策变量的取值可以无任何限制。 （ ）2线性规划问题的可行域一定非空。 （ ）3若线性规划问题无可行解，则其对偶问题一定无可行解。 （ ）4任何一个无向图中偶点的个数不能是奇数。 （ ）5对产大于销的运输问题，可通过添加假想的销地化为产销平衡运输问题。（ ） 6目标规划中任意一个目标约束
9、的正负偏差变量不可能同时为正数。 （ ）7若指派问题的系数矩阵中某行元素都减去同一个常数，则得到的新矩阵为系数矩阵的指派问题与原问题有同样的最优解（ ）8增广链上的每条后向边都为零流边。 （ ）9动态规划的最优策略应该具有性质，无论先前的状态与决策如何，当前的决策应该是最优。 （ ）10矩阵对策就是二人有限零和对策。 （ ）二、单项选择题（每小题 2 分，共 20 分）1下列哪个模型是线性规划模型 C A B0,32.min211ytsz 无2121,403cos.inminxtwC D0,345ax21x 0,354.|in2121xtsz2若用单纯形法求解线性规划问题得到的最终单纯形表中，
10、基变量不含人工变量，且非基变量的检验数均非零，则线性规划问题为下面的情形 A A有唯一最优解， B有无穷多个最优解， C无界解， D无可行解。广东工业大学试卷用纸，共 11 页，第 6 页3若线性规划的原问题不存在最优解，则对偶问题 B A可能存在最优解，B不存在最优解， C一定是无可行解， D一定是无界解。4若线性规划问题的某个资源常数发生变化，则在最终单纯形表中这一变化 B A对检验数存在影响， B对 b 列数存在影响， C对该资源常数所在行的数存在影响， D对所有数都无影响。5对于有 m 个产地 n 个销地的产销平衡运输问题的表上作业法求解，下面不正确的说法是 C A每个空格有唯一的闭回
11、路， B数字格的个数为 m+n-1， C沃格尔法得到的调运方案是最优方案， D若存在负检验数，则调运方案仍可改进。6对于目标规划问题的求解，在满足一个目标时 B A必须同时考虑优先级别较低的目标， B不得违背已经得到满足的优先级别更高的目标，C不必顾虑优先级别较高的目标， D无须考虑上述情况。7若一个无向图可以一笔画出，则该图中 C A最多有一个奇点，B恰好有两个奇点，C最多有两个奇点，D 没有奇点。8下图v1v2v3 v4v5的邻接矩阵是 D A ，B ，C ，D 010101010100109在一个容量网络中，一个可行流满足的条件中不包括下面的哪一点 A 广东工业大学试卷用纸，共 11 页
12、，第 7 页A各边上的流量不全为零， B对每个中间点，流入的物质的和等于流出的物质的和， C每边上的流量不超过其容量， D发点发出的物资的和等于收点接受的物资的和。10在矩阵对策中，若局中人 1 的赢得矩阵不存在鞍点，则 C A矩阵对策问题虽然存在纯策略意义下的解，但不能通过求矩阵鞍点的方法求解；B 矩阵对策不存在解；C矩阵对策不存在纯策略意义下的解；D矩阵对策不存在混合策略意义下的解。五、 设有如下的线性规划问题0,3524min2131xxz无（3） 求该线性规划问题的标准形式；（6 分）（4） 写出其对偶问题模型。 （6 分）解：（1）标准形式是0,35234max2131xw目标函数
13、2 分，每个约束方程各 1 分，变量 2 分（2）对偶问题为 11212max33540,wyy无 约 束目标函数 1 分，每个约束（包括变量约束）各 1 分六、设用单纯形法求解某极大化线性规划问题得到如下的单纯形表2 0 3/2 0 0 0CB XB b x1 x2 x3 x4 x5 x6a x1 2 d -1 0 0 1 -1b x3 3/2 0 2 1 0 -1 2c x4 0 e 0 0 1 -1 0j 0 -1 0 0 -1/2 f(3) 试求上述表中的各参数 af 的值（6 分）广东工业大学试卷用纸，共 11 页，第 8 页(4) 上表是否给出了最优解，若是则求出最优解及对偶问题最
14、优解（6 分）解（1）a=2, b=3/2, c=0, d=1, e=0, f=-1 每个参数值 1 分（2）由于所有检验数都非正，因此该表给出最优解2 分，最优解为2 分4/25*;0,0,2/3,0, 65421 zxxx利用对偶关系可得对偶问题最优解为2 分/;,1,1,/, 654321 wyyy五、某公司拟建立 3 个超市，可选的地址有 A、B、C 三处。在不同地址建立超市，每个月的营业利润估算如下表所示（单位：万元）：超市地址1 2 3A 16 20 30B 12 15 20C 10 13 16问这三个超市应如何分布，可使公司总的营业利润最高？（12 分）解：这是最大化指派问题，化
15、为标准化指派问题，系数矩阵为 8106476501472058故最优解为超市 1 在位置 B，超市 2 在位置 C，超市 3 在位置 A；总利润为55 万元。化为标准形式 3 分，求解过程正确 5 分，最优解 2 分，最优值 2 分六、下面的图给出了某工厂 7 个车间科室之间的内部网线可行的架设路线及架设成本（单位：百元） 。（1）如何架设才能将所有 7 个单位连接起来，并使总成本最低？（8 分）（2）若图中 A、B 两个单位之间必须直接连通，则最低总成本是多少？（ 4分）广东工业大学试卷用纸，共 11 页，第 9 页57468612374529A4B解（1）由避圈法或破圈法得到如下的最小树，即最优架设线路6 分57468612374529A4B总费用为 25（百元）2 分（2）在上述求解中总是保留 AB 之间的线路，得相应的线路为 3 分
