四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调运方案是否为最优?如是说明理由；如否。也说明理由。
表(a)产销平衡表及某一调运方案 单位运价表 销地 B5 10 20 30 产地 Bl B2 B3 B4 l B6 产量 11 11 50 40 60 31 30 30 20 30 50 10 10 20 40 40 A2 A3 A4 销量
五、给出如下运输问题
运价 产 Al A2 A3 销量 5 1 20 30 3 6 10 50 10 9 5 80 4 6 7 40 90 40 70 200 销 B1 B2 B3 B4 产量 (1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案
六、用表上作业法求给出的运输问题的最优解
甲 乙 丙 丁 产量 1 10 6 7 12 4 2 16 0 5 9 9 3 5 4 10 10 4 销量 5 2 4 6
1 2 3 销量 七、名词
甲 1 4 5 乙 2 2 丙 1 3 4 丁 6 6 产量 4 9 4 在最优调运方案下的运输费用最小为118。
1、 平衡运输问题：m个供应地的供应量等于n个需求地的总需求量，这样的运输问题称平衡运输问
题。
2、不平衡运输问题：m个供应地的供应量不等于n个需求地的总需求量，这样的运输问题称不平衡运输问题。
第七章 整数规划
一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为X1≤1，X1≥2。
3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。无可行解。 4．在0 - 1整数规划中变量的取值可能是_0或1。
5．对于一个有n项任务需要有n个人去完成的分配问题，其 解中取值为1的变量数为n个。 6．分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。
7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／
6127x5=13／7，则以X1行为源行的割平面方程为_－X3－X5≤0_。
7778．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。
9．用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。
10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。 13.分枝定界法一般每次分枝数量为2个. 二、单选题
1．整数规划问题中，变量的取值可能是D。
A．整数B．0或1C．大于零的非整数D．以上三种都可能
2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A 。
A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是D_。
A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择
1．下列说明不正确的是ABC。
A．求解整数规划可以采用求解其相应的松驰问题，然后对其非整数值的解四舍五入的方法得到整数解。B．用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常任取其中一个作为下界。C．用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D．用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。 2．在求解整数规划问题时，可能出现的是ABC。
A．唯一最优解B．无可行解 C．多重最佳解D．无穷多个最优解 3．关于分配问题的下列说法正确的是_ ABD。
A．分配问题是一个高度退化的运输问题B．可以用表上作业法求解分配问题 C．从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案D．匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做。 4.整数规划类型包括（ CDE ）
A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0—1规划 5.对于某一整数规划可能涉及到的解题内容为（ ABCDE ）
A 求其松弛问题 B 在其松弛问题中增加一个约束方程 C 应用单形或图解法D 割去部分非整数解 E多次切割 三、名词
1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。
2、0—1规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或1，这样的问题称为0—1规划。
3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。 四、用分枝定界法求解下列整数规划问题：(提示:可采用图解法) maxZ=40x1+90x2
五、用割平面法求解
六、下列整数规划问题
说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。
答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。
七、若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件：
(1)在s1，s2，S4中至多只能选择两个； (2)在S5，s6中至少选择一个；(3)在s3，s6，S7，S8中至少选择两个； 试建立这个问题的整数规划模型
八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少?
工作 人 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 I Ⅱ Ⅲ Ⅳ
第八章 图与网络分析
一、填空题
1．图的最基本要素是点、点与点之间构成的边
2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 4．在图论中，图是反映研究对象_之间_特定关系的一种工具。 5．任一树中的边数必定是它的点数减1。
6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。 7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。 8．求最短路问题的计算方法是从0≤fij≤cij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。 二、单选题
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．可行流的流量小于容量限制条件而大于或等于零。