临沂师范学院数学本科期未试题 《运筹学》(2) 题号 三四五六七八九十|总分 得分 阅卷人 、填空题(15) 1.一般线性规划求解的结果有 种,分别为 2.若线性规划的原问题为MaxZ=CX;AX≤b;X≥0,其最优解为x,则其对偶问题的形式为 在最优点的目标函数值为 3.求解目标规划问题时,某非基变量的检验数为:-P1+10P22P,该变量可否作为换入变 4.若整数规划[Mz= 在x,=0,2时均取得最优解,则其最优解 4x1+5x2≤20 x,x≥O且x,x为整数 min f(x)=cx 5.线性规划s1.Ax≥b的KKT条件 Bx≥0 、证明题(15) 1.对任何线性规划问题,其对偶的对偶还是原问题。 2.树的边数等于顶点数减1 3.叙述中国邮递员问题的最优解判别定理。 三、判断对错(10)
1 ………………………………装………………………………订……………………………线………………………… ………………………………装………………………………订……………………………线………………………… 临沂师范学院数学本科期末试题 《运筹学》（2） 一、 填空题 （15） 1．一般线性规划求解的结果有 种，分别为 。 2. 若线性规划的原问题为 Max Z=CX; AX≤b；X≥0，其最优解为 x * ,则其对偶问题的形式为 ，在最优点的目标函数值为 。 3．求解目标规划问题时，某非基变量的检验数为：-P1+10P2-2P3,该变量可否作为换入变量 。 4．若整数规划 + + = + 1 2 且 1， 2为整数 1 2 1 2 1 2 , 0 4 5 20 2 6 x x x x x x x x MaxZ x x , 在 x1 = 0，2 时均取得最优解，则其最优解 = * x ， ( ) = * f x 。 5. 线性规划 0 . . min ( ) = Bx st Ax b f x c x T 的ＫＫＴ条件——————————————。 二、 证明题 （15） 1．对任何线性规划问题,其对偶的对偶还是原问题。 2. 树的边数等于顶点数减 1。 3. 叙述中国邮递员问题的最优解判别定理。 三、判断对错 （10） 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 阅卷人 专业： 科类： 科 班级： 级 班 姓名： 学号： 专业： 科类： 科 班级： 级 班 姓名： 学号：
1.若x为LP的可行解,则x亦为LP的基本解。() 2.设LP的可行域为D,D非凸集,则LP的最优点必在D的顶点上。() 3.LP经过若干次迭代后己得到一退化的最优解,则继续迭代下去必可得到非退化的最优解。() 4.如果线性规划的原问题和对偶问题都具有可行解,则该线性规划问题一定具有有限最优解。() 5.一旦一个人工变量再迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而 不影响计算结果。() 四、计算题(45) 1.(15)用对偶单纯形法求解 min x1+2x2+4 2 10 x1≥0,x2≥0,x3≥0 2.(15)某车间可以用塑料生产以下三种管状产品,有关数据如下 甲m乙 利润(元) 05 问(1)如何组织生产,使获得的利润最大。 (2)若现有丁产品,设生产1m需要塑料3公斤和工时5小时,每米利润6元 问丁产品是否值得投入生产 若不值得投产,每米丁产品的利润是多少时,就值得投产 3.(15)某项工程有11项作业组成(分别用代号A ,J,K表示,其计划完成时间及作业 间相互关系如下表,建立PERT网络图表:确定关键路线 2
2 1. 若 x ~ 为 LP 的可行解，则 x ~ 亦为 LP 的基本解。（ ） 2. 设 LP 的可行域为 D，D 非凸集，则 LP 的最优点必在 D 的顶点上。（ ） 3． LP 经过若干次迭代后已得到一退化的最优解，则继续迭代下去必可得到非退化的最优解。（ ） 4． 如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。（ ） 5．一旦一个人工变量再迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而 不影响计算结果。（ ） 四、计算题 （45） 1. （15）用对偶单纯形法求解 0, 0, 0 2 10 . . 2 5 min 3 2 4 1 2 3 2 3 1 2 1 2 3 − − + + x x x x x st x x x x x 2. （15）某车间可以用塑料生产以下三种管状产品，有关数据如下。 甲m 乙 m 丙 m 利润（元） 2 3 11/3 塑料（公斤） 1 1 1 135 工时 1 4 7 405 问（1）如何组织生产，使获得的利润最大。 （2）若现有丁产品，设生产 1m 需要塑料 3 公斤和工时 5 小时，每米利润 6 元， 问丁产品是否值得投入生产; 若不值得投产，每米丁产品的利润是多少时，就值得投产。 3．（１5）某项工程有 11 项作业组成（分别用代号 A，B，．．．，Ｊ，Ｋ表示，其计划完成时间及作业 间相互关系如下表，建立ＰＥＲＴ网络图表 ；确定关键路线．
计划完成 作业 计划完成紧前作业 作业 紧前作业 时间/d 时间/d F G G 15 CD 五、(15)建模题 某单位领导在考虑本单位职工的升级调资方案时,遵守以下规定 (1)不超过年工资总额60000元 (2)每级的人数不超过定编规定的人数; (3)BC级别的升级面尽可能达到现有人数的20%且无越级提升; (4)C级不足编制的人数可录用新职工,又A级的职工中有10%要退休 有关资料汇总于下表问该领导应如何拟订一个满意的方案.只建模型,不求解 工资额(元)现有人数编制人数 2000 10 2 15 15 合计 42
3 作业 计划完成 时间／ｄ 紧前作业 作业 计划完成 时间／ｄ 紧前作业 A B C D E F 5 10 11 4 4 15 － － － B A C,D G H I J K 21 35 25 15 20 B,E B,E B,E F,G,I F,G 五、(15) 建模题 某单位领导在考虑本单位职工的升级调资方案时，遵守以下规定 (1).不超过年工资总额 60000 元; (2).每级的人数不超过定编规定的人数; (3).B,C 级别的升级面尽可能达到现有人数的 20%,且无越级提升; (4).C 级不足编制的人数可录用新职工,又 A 级的职工中有 10%要退休. 有关资料汇总于下表,问该领导应如何拟订一个满意的方案. 只建模型，不求解。 等级 工资额(元/年) 现有人数 编制人数 A 2000 10 12 B 1500 12 15 C 1000 15 15 合计 37 42