广东工业大学-运筹学-试卷答案.doc

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