华东师范大学《组合与运筹》2023-2024学年第一学期期末试卷

华东师范大学《组合与运筹》2023-2024学年第一学期期末试卷院(系)：__________班级：__________学号：__________姓名：__________得分：__________考试时间：120分钟满分：100分命题人：__________审题人：__________注意事项：1.答题前请填写好个人信息，将答案写在答题纸指定位置，写在试卷上无效；2.所有题目需写出必要的解题步骤，仅写答案不得分；3.考试结束后，将试卷和答题纸一并交回。一、单选题（本大题共10小题，每小题3分，共30分。在每小题给出的四个选项中，只有一项是符合题目要求的。）下列关于组合数学中“排列”的说法，正确的是（）

A.从n个不同元素中取出k个，不考虑顺序的选取方式称为排列

B.排列数P(n,k)=n!/(n-k)!，其中0!=1

C.可重复排列中，从n个不同元素中取出k个，排列数为C(n,k)

D.环形排列的排列数与线性排列数相等

若某线性规划问题的可行域是封闭的凸多边形，则该问题（）

A.一定有唯一最优解

B.无最优解

C.最优解一定在可行域的顶点上

D.可行域内所有点都是最优解

计算组合数C(8,3)+C(8,4)的值为（）

A.56

B.70

C.84

D.126线性规划问题中，松弛变量的作用是（）

A.将目标函数转化为线性形式

B.将不等式约束转化为等式约束

C.改变约束条件的方向

D.增加决策变量的个数，使问题无解

下列哪种方法不是求解线性规划问题的常用方法（）

A.图解法

B.单纯形法

C.匈牙利算法

D.灵敏度分析法

设G是一个有n个顶点、m条边的连通图，下列说法正确的是（）

A.若G是树，则m=n+1

B.若G是完全图，则m=n(n-1)/2

C.连通图的边数一定小于顶点数

D.非连通图一定没有生成树

在组合计数中，容斥原理的核心是（）

A.排除重复计数，避免遗漏

B.仅计算满足单个条件的元素个数

C.将复杂问题转化为简单的排列问题

D.仅适用于有限集合的计数

线性规划问题的对偶问题中，若原问题有可行解但无最优解，则对偶问题（）

A.有可行解且有最优解

B.有可行解但无最优解

C.无可行解

D.无法确定

下列关于运筹学的描述，错误的是（）

A.运筹学是研究如何合理安排资源、实现目标最优化的学科

B.组合数学是运筹学的重要分支之一

C.运筹学仅适用于工业生产领域

D.线性规划、整数规划、图论均属于运筹学的研究内容

计算n个不同元素的全排列数，当n=5时，其值为（）

A.20

B.60

C.120

D.720

二、填空题（本大题共5小题，每小题4分，共20分。请将答案直接填写在答题纸相应位置。）从10个不同的小球中取出4个，不考虑顺序，共有__________种选取方式。线性规划问题的标准形式中，目标函数必须是__________（填“最大化”或“最小化”），约束条件均为等式约束，决策变量非负。一个有6个顶点的完全图，其边数为__________。容斥原理中，若集合A、B互斥，则|A∪B|=__________。单纯形法中，__________是判断当前基可行解是否为最优解的依据。三、计算题（本大题共3小题，每小题10分，共30分。要求写出详细解题步骤。）计算下列组合数与排列数：

（1）C(7,2)×P(5,3)（5分）

（2）C(9,4)+C(9,5)-C(10,5)（5分）

用图解法求解下列线性规划问题：

目标函数：maxz=2x₁+3x₂

约束条件：

x₁+x₂≤5

2x₁+x₂≤8

x₁≥0,x₂≥0

要求：画出可行域，标出顶点坐标，求出最优解及最优目标函数值。

已知一个连通图G，顶点数n=5，边数m=7，求该图的生成树个数（提示：利用树的性质及相关公式）。四、应用题（本大题共2小题，每小题10分，共20分。要求建立模型并求解，写出详细步骤。）某工厂生产A、B两种产品，生产1件A产品需要消耗2kg原材料甲和3kg原材料乙，可获得利润50元；生产1件B产品需要消耗3kg原材料甲和2kg原材料乙，可获得利润60元。已知工厂现有原材料甲12kg，原材料乙10kg，如何安排生产A、B两种产品的数量，才能使总利润最大化？（建立线性规划模型并求解）某班有8名同学，现要从中选出3名同学组成小组参加竞赛，要求其中甲、乙两名同学不能同时入选，求共有多少种不同的选法？（用容斥原理求解）参考答案及评分标准（附页）一、单选题（每小题3分，共30分）1.B2.C3.B4.B5.C6.B7.A8.C9.C10.C二、填空题（每小题4分，共20分）1.2102.最大化3.154.|A|+|B|5.检验数三、计算题（每小题10分，共30分）1.（1）C(7,2)=21，P(5,3)=60，乘积为21×60=1260（5分）；（2）C(9,4)+C(9,5)=C(10,5)，故结果为0（5分）2.可行域顶点为(0,0)、(0,5)、(3,2)、(4,0)，最优解为(3,2)，最优目标函数值z=12（步骤完整得10分，漏顶点或计算错误酌情扣分）3.生成树边数为n-1=4，需删除3条边且保持连通，生成树个数为C(7,3)-无效删除数=35-（环的数量相关计算）=具体数值根据推导过程得分（步骤完整得10分）四、应用题（每小题10分，共20分）1.设生产A产品x₁件，B产品x₂件，模型为maxz=50x₁+60