《数据模型与决策》复习题及参考答案

单形或图解法D 割去部分非整数解 E多次切割 三、名词

1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。

2、0—1规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或1，这样的问题称为0—1规划。

3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。

第八章 图与网络分析 一、填空题

1．图的最基本要素是点、点与点之间构成的边

2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。

3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。

4．在图论中，图是反映研究对象_之间_特定关系的一种工具。 5．任一树中的边数必定是它的点数减1。

6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。

7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。 8．求最短路问题的计算方法是从0≤fij≤cij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。

二、单选题

1、关于图论中图的概念，以下叙述(B)正确。

A图中的有向边表示研究对象，结点表示衔接关系。 B图中的点表示研究对象，边表示点与点之间的关系。C图中任意两点之间必有边。 D图的边数必定等于点数减1。

2．关于树的概念，以下叙述(B)正确。

第 21 页共40页

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．关于图论中图的概念，以下叙述(ABC)正确。

A、图中的边可以是有向边，也可以是无向边 B、图中的各条边上可以标注权。C、结点数等于边数的连通图必含圈D、结点数等于边数的图必连通。

2．关于树的概念，以下叙述(ABC)正确。

A、树中的边数等于点数减1 B、树中再添一条边后必含圈。C树中删去一条边后必不连通D、树中两点之间的通路可能不唯一。

3．从连通图中生成树，以下叙述(ACD)正确。

第 22 页共40页

A、任一连通图必有支撑树 B、任一连通图生成的支撑树必唯一C、在支撑树中再增加一条边后必含圈D、任一连通图生成的各个支撑树其边数必相同

4．在下图中，(abcd)不是根据(a)生成的支撑树。

5．从赋权连通图中生成最小树，以下叙述(ABD)不正确。

A、任一连通图生成的各个最小树，其总长度必相等B、任一连通图生成的各个最小树，其边数必相等。C、任一连通图中具有最小权的边必包含在生成的最小树上。D、最小树中可能包括连通图中的最大权边。

6．从起点到终点的最短路线，以下叙述(ABC)不正确。

A、从起点出发的最小权有向边必含在最短路线中。B、整个图中权最小的有向边必包含在最短路线中。C、整个图中权最大的有向边可能含在最短路线中

D、从起点到终点的最短路线是唯一的。

7．关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述(ABC)不正确。

A、增广路上的有向边的方向必须是从发点指向收点的B、增广路上的有向边，必须都是不饱和边 C、增广路上不能有零流边D、增广路上与发点到收点方向一致的有向边不能是饱和边，相反方向的有向边不能是零流边 8．关于树，以下叙述(ABCE)正确。

A．树是连通、无圈的图B．任一树，添加一条边便含圈C．任一树的边数等于点数减1。D．任一树的点数等于边数减1E．任一树，去掉_条边便不连通。

9．关于最短路，以下叙述(ACDE)不正确。

A从起点出发到终点的最短路是唯一的。B．从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的。C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上。 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上。

第 23 页共40页

10．关于增广路，以下叙述(BC )正确。

A．增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。B．增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致。C．增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。D．增广路上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。E．增广路上与发点到收点方向一致的边必须是流量为零的边，方向相反的边必须是流量大于零的边。 四、名词解释

1．树:在图论中，具有连通和不含圈特点的图称为树。 2．权：在图中，边旁标注的数字称为权。

3．网络：在图论中，给边或有向边赋了权的图称为网络

4．最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的

最大流量

5．最大流问题中流量：最大流问题中流量是指单位时间的发点的流出量或收点

的流入量。

6．容量：最大流问题中，每条有向边单位时间的最大通过能力称为容量 7．饱合边：容量与流量相等的有向边称为饱合边。 8零流边：流量为零的有向边称为零流边

9.生成树：若树T是无向图G的生成树，则称T是G 的生成树。.。 10根：有向图G中可以到达图中任一顶点的顶点u称为G的根。 11枝：树中的边称为枝。

12.平行边：具有相同端点的边叫平行边。 九章 存储论

需求：需求就是库存的输出。

存贮费：一般是指每存贮单位物资单位时间所需花费的费用。 缺货损失费：一般指由于中断供应影响生产造成的损失赔偿费。

订货批量Q：存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货

或采购的数量。

订货间隔期T：两次订货的时间间隔可订货合同中规定的两次进货之间的时间间

第 24 页共40页