方法得到整数解。B．用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常任取其中一个作为下界。C．用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D．用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。 2．在求解整数规划问题时，可能出现的是ABC。
A．唯一最优解B．无可行解 C．多重最佳解D．无穷多个最优解 3．关于分配问题的下列说法正确的是_ ABD。
A．分配问题是一个高度退化的运输问题B．可以用表上作业法求解分配问题 C．从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案D．匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做。 4.整数规划类型包括（ CDE ）
A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0—1规划 三、名词
1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。 2、0—1规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或1，这样的问题称为0—1规划。
3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。
图与网络分析 一、填空题
1．任一树中的边数必定是它的顶点数减1。
2．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。 3．18、求支撑树有 破圈 法和 避圈 法两种方法。 二、单选题
1、关于图论中图的概念，以下叙述(B)正确。
A图中的有向边表示研究对象，结点表示衔接关系。 B图中的点表示研究对象，边表示点与点之间的关系。C图中任意两点之间必有边。 D图的边数必定等于点数减1。 2．关于树的概念，以下叙述(B)正确。
A树中的点数等于边数减1 B连通无圈的图必定是树 C含n个点的树是唯一的
D任一树中，去掉一条边仍为树。 3．一个连通图中的最小树(B)，其权(A)。
A是唯一确定的 B可能不唯一 C可能不存在 D一定有多个。 4．关于最大流量问题，以下叙述(D)正确。
A一个容量网络的最大流是唯一确定的B达到最大流的方案是唯一的C当用标号法求最大流时，可能得到不同的最大流方案D当最大流方案不唯一时，得到的最大流量亦可能不相同。 5．图论中的图，以下叙述(C)不正确。
A．图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。B．图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。C．图论中的边表示研究对象，点表示研究对象之间的特定关系。 D．图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。 6．关于最小树，以下叙述(B)正确。
A．最小树是一个网络中连通所有点而边数最少的图B．最小树是一个网络中连通所有的点，而权数最少的图C．一个网络中的最大权边必不包含在其最小树内D．一个网络的最小树一般是不唯一的。
7．关于可行流，以下叙述(A)不正确。
A．可行流的流量大于零而小于容量限制条件B．在网络的任一中间点，可行流满足流人量=流出量。C．各条有向边上的流量均为零的流是一个可行流D．可行流的流量小于容量限制条件而大于或等于零。 三、多选题
1．关于图论中图的概念，以下叙述(123)正确。
(1)图中的边可以是有向边，也可以是无向边 (2)图中的各条边上可以标注权。(3)结点数等于边数的连通图必含圈(4)结点数等于边数的图必连通。 2．关于树的概念，以下叙述(123)正确。
1)树中的边数等于点数减1(2)树中再添一条边后必含圈。(3)树中删去一条边后必不连通(4)树中两点之间的通路可能不唯一。 3．从连通图中生成树，以下叙述(134)正确。
(1)任一连通图必有支撑树 (2)任一连通图生成的支撑树必唯一(3)在支撑树中再增加一条边后必含圈(4)任一连通图生成的各个支撑树其边数必相同 4．在下图中，(abcd)不是根据(a)生成的支撑树。
5．从赋权连通图中生成最小树，以下叙述(124)不正确。
(1)任一连通图生成的各个最小树，其总长度必相等(2)任一连通图生成的各个最小树，其边数必相等。(3)任一连通图中具有最小权的边必包含在生成的最小树上。(4)最小树中可能包括连通图中的最大权边。
6．从起点到终点的最短路线，以下叙述(123)不正确。
1)从起点出发的最小权有向边必含在最短路线中。 (2)整个图中权最小的有向边必包含在最短路线中。(3)整个图中权最大的有向边可能含在最短路线中 (4)从起点到终点的最短路线是唯一的。
7．关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述( 123)不正确。 (1)增广路上的有向边的方向必须是从发点指向收点的(2)增广路上的有向边，必须都是不饱和边 (3)增广路上不能有零流边(4)增广路上与发点到收点方向一致的有向边不能是饱和边，相反方向的有向边不能是零流边 8．关于树，以下叙述(ABCE)正确。
A．树是连通、无圈的图B．任一树，添加一条边便含圈C．任一树的边数等于点数减1。D．任一树的点数等于边数减1E．任一树，去掉_条边便不连通。 9．关于最短路，以下叙述(ACDE)不正确。
A从起点出发到终点的最短路是唯一的。B．从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的。C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上。 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上。 10．关于增广路，以下叙述(BC )正确。
A．增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。B．增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致。C．增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。D．增广路上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。E．增广路上与发点到收点方向一致的边必须是流量为零的边，方向相反的边必须是流量大于零的边。 四、名词解释
1、树:在图论中，具有连通和不含圈特点的图称为树。 2．权：在图中，边旁标注的数字称为权。
3．网络：在图论中，给边或有向边赋了权的图称为网络
4．最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的最大流量 5．最大流问题中流量：最大流问题中流量是指单位时间的发点的流出量或收点的流入量。 6．容量：最大流问题中，每条有向边单位时间的最大通过能力称为容量 7．饱合边：容量与流量相等的有向边称为饱合边。 8零流边：流量为零的有向边称为零流边
9.生成树：若树T是无向图G的生成树，则称T是G 的生成树。.。
计算题（答案参考课件）
1．图解法求线性规划问题。
maxZ?2x1?3x2?2x1?2x2?12?x?2x?812???16?4x1 ? 4x2?12???x1?0,x2?0
2．利用对偶理论求解线性规划问题。
已知原问题的最优解为X* =（0.0.4），Z=12 试求对偶问题的最优解。
maxZ?x1?4x2?3x3?2x1?3x2?5x3?2?3x? x?6x?1 ?123?? x1? x2? x3?4??x1?0,x2?0,x3无约束
3．灵敏度分析（学会单纯型法和对偶单纯型法的计算）
某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划
max Z?5x1?4x2?x1?3x2?90??2x1?x2?80 ??x1 ?x2?45??x1,x2?0已知最优表如下。
（1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。
（3）b3在什么范围内变化，原最优基不变？ （4）若b3=55，求出新的最优解。
（5）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示， P6=
?3/2?。问它的价值系数???1??1/2???c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产
计划是什么？
（6）假设还要考虑一个新的资源约束：4x1+2x2≤150，新的最优生产计划是什么？
cj CB 0 5 4 XB x3 x1 x2
4．指派问题
有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？
5．产销平衡运输问题
b 25 35 10 5 x1 0 1 0 0 4 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 2 1 -1 -1 0 x5 -5 -1 2 -3 任务 A 人员 甲 乙 丙 丁 6 4 3 5 7 5 1 9 11 9 10 8 2 8 4 2 B C D 已知某运输问题的资料如下表所示，试求出最优运输方案。 A1 A2 A3 收量
6．最短路问题
求下图从v1到v6的最短路。
B1 2 1 3 10 B2 6 3 2 13 B3 5 2 7 12 B4 3 1 4 5 发量 15 12 13 v2 3 v1
5
v3
书P44例13，例14
2 2 4
v4
4 2 2 v5
1 v6
应用题（只写规划，不用求解）
P121-126 例3，例4，例5，例6 第一章课件最后一部分的线性规划建模