运筹试题B().docVIP

黔南民族师范学院2009--2010学年度第二学期 试卷(B卷) 课程名称《 运筹学 》 考试用时 120 分钟 系别 数学系 年级07 班级 学号 姓名 题号 一 二 三 四 五 总分 复核人 得分 阅卷人 得分 阅卷人 一、填空题(每空1分，共10分) 1、原问题的第1个约束方程是“=”型，则对偶问题相应的变量是_ 变量。 2、任何图中, 奇次顶点的个数为 。 3、除图解法外，常用的求解线性规划问题的方法是__ ____________法。 4、运输问题中，当总供应量小于总需求量时，求解时需虚设一个 _ ___点，此点的供应量应 _ __ _(总需求量与总供应量之差)。 5、求解整数规划问题的方法有 和割平面法； 6、动态规划的求解方法有 和 。 7、线性规划模型有三种参数，其名称分别为价值系数、 __和 。 得分 阅卷人 二、判断对错（答案填入括号内，每题2分，共10分） 1、目标规划中的正偏差变量取正值，负偏差变量取负值。 （ ） 2、动态规划模型中，问题的阶段数等于问题中子问题的数目。（ ） 3、若线性规划的原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。 （ ） 4、已知为线性规划的对偶问题的最优解，若，说明在最优生产计划中，第i种资源一定没有剩余。 （ ） 5、整数规划的目标函数值一般优于其相应的线性规划问题的解的目标函数值。（ ） 得分 阅卷人 三、选择题（每题3分，共15分）。 1、甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比赛情况的图是（ ） A、没有圈 B、一棵树 C、连通的 D、任两点之间有一条带有方向的线 2、线性规划 当且仅当（ ）时存在可行解。 A、 ； B、； C、； D、 3、对偶问题的对偶是 （ ） A、原问题 B、 基本问题 C、解的问题 D、 其它问题 4、 下列效率矩阵中能用匈牙利法求解的是（ ） A、 B、 C、 D、 5、在n个产地、m个销地的产销平衡运输问题中，( )是错误的。 A、运输问题是线性规划问题 B、基变量的个数是数字格的个数 C、空格有mn-n-m+1个 D、每一格在运输图中均有一闭合回路 得分 阅卷人 三、计算题（共65分）。 1、用适当的方法求下图中到的最短路。（7分） 2、分配甲、乙、丙、丁四人去完成四项任务。每人完成各项任务的时间如下表所示。 任务 人 A B C D 甲 7 9 10 12 乙 13 12 16 17 丙 15 16 14 15 丁 11 12 15 16 试确定总化费时间最少的指派方案。（10分） 3、已知线性规划。（15分） （1）写出其对偶问题；（4分） （2）已知原问题用单纯形法求解时得到根据最单纯形表如下所示： 3 -1 1 0 0 3 3 0 5 1 1 1 1 0 0 3 1 1 1 0 -4 -2 -3 0 试写出对偶问题的最优解。（3分） （3）目标函数变为时，新的最优解是什么？（3分） 4、给出线性规划的标准形式，并用单纯形法求解。（15分）