19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。 二、单选题
1、在运输问题中，可以作为表上作业法的初始基可行解的调运方案应满足的条件是D。
A．含有m+n—1个基变量B．基变量不构成闭回路
C．含有m+n一1个基变量且不构成闭回路D．含有m+n一1个非零的基变量且不构成闭回
2．若运输问题的单位运价表的某一行元素分别加上一个常数k，最优调运方案将B。
A．发生变化 B．不发生变化C．A、B都有可能
3．在表上作业法求解运输问题中，非基变量的检验数D。
A．大于0B．小于0C．等于0D．以上三种都可能
4.运输问题的初始方案中，没有分配运量的格所对应的变量为 B
A基变量 B 非基变量 C 松弛变量 D 剩余变量 5.表上作业法的基本思想和步骤与单纯形法类似，那么基变量所在格为 C
A 有单位运费格 B 无单位运费格 C 有分配数格 D 无分配数格 6.表上作业法中初始方案均为 A
A 可行解 B 非可行解 C 待改进解 D 最优解 7.闭回路是一条封闭折线，每一条边都是 D
A 水平 B 垂直 C水平＋垂直 D水平或垂直 8当供应量大于需求量，欲化为平衡问题，可虚设一需求点，并令其相应运价为 D
A 0 B 所有运价中最小值 C所有运价中最大值 D最大与最小运量之差 9.运输问题中分配运量的格所对应的变量为 A
A基变量 B 非基变量 C 松弛变量 D 剩余变量 10.所有物资调运问题，应用表上作业法最后均能找到一个 D
A 可行解 B 非可行解 C 待改进解 D 最优解 11.一般讲，在给出的初始调运方案中，最接近最优解的是 C
A 西北角法 B 最小元素法 C 差值法 D 位势法 12.在运输问题中，调整对象的确定应选择 C
A 检验数为负 B检验数为正 C检验数为负且绝对值最大 D检验数为负且绝对值最小 13.运输问题中，调运方案的调整应在检验数为 C 负值的点所在的闭回路内进行。
A 任意值 B最大值 C绝对值最大 D绝对值最小 14.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个 C
A 基 B 可行解 C 初始基本可行解 D最优解 15平衡运输问题即是指m个供应地的总供应量 D n个需求地的总需求量。 A 大于 B 大于等于 C小于 D 等于 三、多选题
1．运输问题的求解结果中可能出现的是ABC _。
A、惟一最优解 B．无穷多最优解 C．退化解 D．无可行解 2．下列说法正确的是ABD。
A．表上作业法也是从寻找初始基可行解开始的 B．当一个调运方案的检验数全部为正值时，当前方案一定是最佳方案C．最小元素法所求得的运输的运量是最小的 D．表上作业法中一张供需平衡表对应一个基可行解
3．对于供过于求的不平衡运输问题，下列说法正确的是ABC。
A．仍然可以应用表上作业法求解B．在应用表上作业法之前，应将其转化为平衡的运输问题C．可以虚设一个需求地点，令其需求量为供应量与需求量之差。D．令虚设的需求地点与各供应地之间运价为M(M为极大的正数)
4．下列关于运输问题模型特点的说法正确的是 ABD
A． 约束方程矩阵具有稀疏结构 B．基变量的个数是m+n-1个 C．基变量中不能有零
D．基变量不构成闭回路
5.对于供过于求的不平衡运输问题，下列说法正确的是 ABC A．仍然可以应用表上作业法求解 B．在应用表上作业法之前，应将其转化为平衡的运输问题
C．可以虚设一个需求地点，令其需求量为供应量与需求量之差。
D．令虚设的需求地点与各供应地之间运价为M(M为极大的正数) E. 可以虚设一个库存，令其库存量为0
三、判断表(a)(b)(c)中给出的调运方案能否作为表上作业法求解时的初始解，为什么?
(a)
Al A2 A3 A4 销量 Bl B2 Bl 20 B2 10 30 B3 20 10 B4 10 B5 50 B6 产量 5 30 50 75 20 20 20 40 30 10 50 25 (b) (c) B3 B4 B5 B6 产量 Bl B2 B3 B4 产量 Al 30 30 Al 6 5 A2 20 30 50 A2 5 4 2 A3 10 30 10 25 75 A3 5 3 A4 20 20 销量
5
9
9
7
销量 20 40 30 10 50 25 (a)可作为初始方案； (b)中填有数字的方格数少于9(产地数+销地数－1)，不能作为初始方案；
(c)中存在以非零元素为顶点的闭回路，不能作为初始方案
四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调运方案是否为最优?如是说明理由；如否。也说明理由。
表(a)产销平衡表及某一调运方案 单位运价表 销地 产地 Bl B2 B3 B4 B5 B6 产量 l 30 20 50 A2 30 10 40 A3 10 40 10 60 A4 20 11 31 销量 30 50 20 40 30 11
五、给出如下运输问题
运价 销 B1 B2 B3 B4 产量 产 Al 5 3 10 4 90 A2 1 6 9 6 40 A3 20 10 5 7 70 销量 30 50 80 40 200 (1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案
11 11 8
六、用表上作业法求给出的运输问题的最优解
甲 乙 丙 丁 产量 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 乙 2 2 丙 1 3 4 丁 产量 6 6 4 9 4 销量 5 在最优调运方案下的运输费用最小为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。所在行
612得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为_－X3－X5≤0_。
778．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。 79．用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。
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中至少选择两个； 试建立这个问题的整数规划模型
八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少? 工作 I 人 Ⅱ 甲 乙 丙 丁 15 19 6 19
18 23 7 21 Ⅲ 2l 22 16 23 Ⅳ 24 18 19 17