A2 A3 A4 20 30 10 40 30 30 10 10 20 50 25 25 50 75 20 销量 20 答：不可作为初始方案。因为表中填有数字的方格数少于9。 2.下列整数规划问题
说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。
答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。 五、计算题
1.有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少?
工作 I 人 Ⅱ 甲 乙 丙 丁 解：
Ⅰ Ⅱ Ⅲ Ⅳ
甲 （15） 18 21 24 15 0 3 6 9 乙 19 23（22）18 18 1 5 4 0 丙 6 （7） 16 19 6 0 1 10 13 丁 19 21 23 （17） 17 2 4 6 0 0 1 4 0
分配方案 甲→Ⅰ，乙→Ⅲ，丙→Ⅱ，丁→Ⅳ 最短时间为 15+22+7+17=61
2.若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号
为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1) 在s1，s2，S4中至多只能选择两个； （2）在S5，s6中至少选择一个；（3）在s3，s6，S7，S8中至少选择两个。 试建立这个问题的整数规划模型
解：设xj（j=1,…,10）为钻井队在第i个井位探油 minZ=?cjxj
j?110 Ⅲ 2l 22 16 23 Ⅳ 24 18 19 17 15 19 6 19 18 23 7 21
3.给出如下运输问题 运 B1 B2 B3 B4 销 价 产量 产 Al A2 A3 销量 5 1 3 6 10 4 9 6 7 90 40 70 20 10 5 30 50 80 40 200 (1) 应用最小元素法求其初始方案；
（2）应用位势法求初始方案的检验数，并检验该方案是否为最优方案
解： （1）初始方案 A1 A2 A3 销量 A1 A2 A3 vj B1 30 30 B2 50 50 B3 10 70 80 B4 40 0 40 产量 90 40 70 （2）检验表 B1 6 23 0 B2 9 4 B3 3 8 B4 5 5 ui -1 1 -3 非基变量检验数全部非负，该方案为最优方案。 4.用分枝定界法求解下列整数规划问题：（提示:可采用图解法） maxZ=40x1+90x2
解：
第八章
一、单项选择题
1．最短路问题的计算是从符合某一条件开始逐步推算的，这个条件是（ A ）
A.0≤fij≤ci B.0≤fij≥ci C.0≥fij≥ci D.0≥fij≤ci 2．关于可行流，以下叙述不正确的是（ A ）
A.可行流的流量大于零而小于容量限制条件 B．在网络的任一中间点，可行流满足流人量=流出量 C．各条有向边上的流量均为零的流是一个可行流 D．可行流的流量小于容量限制条件而大于或等于零 3．关于最小树，以下叙述（ B ）正确。
A.最小树是一个网络中连通所有点而边数最少的图 B．最小树是一个网络中连通所有的点，而权数最少的图 C．一个网络中的最大权边必不包含在其最小树内 D．一个网络的最小树一般是唯一的。
4．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（ B ） A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点
5.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（ D ）
A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度 6．最小树问题就是在网络图中，找出若干条边，连接（ D ）
A.相邻结点 B.头尾结点 C.部分结点 D.所有结点 7．任一树中的边数和它的点数之间的关系是（ A ）
A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加1 8．在图论中，图是一种工具，它反映研究对象之间的（ D ）
A. 线性相关关系 B. 非线性相关关系 C.一般关系 D.特定关系 9．在图论中，通常用点表示（ A ）
A.研究对象 B.连接各边 C.研究对象之间一般关系 D.研究对象之间特定关系 10．关于图论中的图，以下叙述不正确的是（ C ）
A．图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。
B．图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。 C．图论中的边表示研究对象，点表示研究对象之间的特定关系。
D．图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。
11．最大流问题中，对于一个可行流，ViVj有向边上的流量fij必须满足的条件之一是（ C ）
A.0≤fij≥cij B.0≥fij≤cij C. 0≤fij≤cij D. 0≥fij≥cij 12．关于图论中图的概念，以下叙述正确的是（ B ）
A.图中的有向边表示研究对象，结点表示衔接关系 B.图中的点表示研究对象，边表示点与点之间的关系 C.图中任意两点之间必有边 D.图的边数必定等于点数减1 13.一个连通图中的最小树可能不唯一，其权（ A ）
A.是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个 14.在最短路问题的推算过程中需要不断标记平衡和（ C ）
A.边数 B.点数 C.最短路线 D.最长路线 二、多项选择题
1.关于图论中图的概念，以下叙述正确的的（ ABC ）
A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权 C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边
2.关于最短路，以下叙述不正确的有（ BCDE ）
A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的 B．从起点出发到终点的最短路是唯一的
C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上 3.关于增广路，以下叙述正确的有（ BC ）
A．增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致 B．增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致
C．增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边
D．增广路上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边 E．增广路上与发点到收点方向一致的边必须是流量为零的边，方向相反的边必须是流量大于零的边 4.在下图中，根据（a） 生成的支撑树有（ BCD ）
三 、计算题
1．试求出下图从起点到终点的最短路线。
解：
V1 V2 V3 V4 V5 V6
0 ∞ ∞ ∞ ∞ ∞
*51 41 81 ∞ 121 *51 8283 103 121
*
8283﹡ 103 121
103﹡ 114
114﹡
最短路 V1→V4→V6 或 V1→V3→V4→V6 路长：11 2．试求出下图从起点到终点的最短路线。
解：
V0 V1 V2 V3 V4 V5 V6
0 ∞ ∞ ∞ ∞ ∞ ∞
*51 41 ∞ ∞ ∞ ∞ *51 72 72 122 ∞
7*2 72 122 ∞
7*2 122 ∞
12*2 134
最短路径 V0→V2→V4→V6 路长：13
13*4
3.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少?
解：
4．对下面的连通图，试求出最小树。
解：
第九章
一、计算题
1．试求出下面连通图的最小树。
解：
第十章
一、名词解释
1.根：有向图G中可以到达图中任一顶点的顶点u称为G的根。
2.根树：若有向图G有根u，且它的基本图是一棵树，则称G为以u为根的根树。 3.简单图：满足约束条件而又使目标函数取得极值的解。 4.平行边：具有相同端点的边叫平行边。
5.网络：在图论中，给边或有向边赋了权的图称为网络。
6.生成树：若树T是无向图G的生成树，则称T是G 的生成树。
第十一章
运筹学试题1
