运筹学深刻复知识题2013

1、运筹学复习题线性规划的基本概念一、填空题1 线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。2 图解法适用于含有两个变量的线性规划问题。3 线性规划问题的可行解是指满足所有约束条件的解。4 在线性规划问题的基本解中，所有的非基变量等于零。 _5 在线性规划问题中，基可行解的非零分量所对应的列向量线性无 6 若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。7 线性规划问题有可行解，则必有基可行解。8如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解 _的集合中进行搜索即可得到最优解。9 满足非负条件的基本解称为基本可行解。10 .在将线性规

2、划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的 系数为零。11 将线性规划模型化成标准形式时，“w”的约束条件要在不等式左_端加入松弛变量。12 线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。13 线性规划问题可分为目标函数求极大值和极小_值两类。14 线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。二、单选题1 如果一个线性规划问题有 n个变量，m个约束方程（mn），系数矩阵的数为 m，则基可行解的个数最多为_c_。A . m 个B. n 个C. CnmD. Cmn 个2 下列图形中阴影部分构成的集合是凸集的是_A_3 在下列线

3、性规划问题的基本解中，属于基可行解的是_BA. （一 1，0, O）T B. （1，0, 3，0）T C. （一 4，0, 0，3）t D. （0，一 1，0，5）T7 .关于线性规划模型的可行域，下面_D_的叙述正确。A .可行域内必有无穷多个点B.可行域必有界 C.可行域内必然包括原点D .可行域必是凸的8 .下列关于可行解，基本解，基可行解的说法错误的是_B_.A .可行解中包含基可行解B .可行解与基本解之间无交集C. 线性规划问题有可行解必有基可行解D. 满足非负约束条件的基本解为基可行解9. 线性规划问题有可行解，则AC无基可行解D无唯一最优解A必有基可行解B必有唯一最优解10.

4、为化为标准形式而引入的松弛变量在目标函数中的系数应为AA 0B 1C 2D 311. 若线性规划问题没有可行解，可行解集是空集，则此问题BA没有无穷多最优解B没有最优解C 有无界解D 无有界解三、多选题1 .在线性规划问题的标准形式中，不可能存在的变量是D.A .可控变量B .松驰变量c .剩余变量D .人工变量A .目标函数求极小值 B.右端常数非负C.变量非负D .约束条件为等式 E.约束条件为 “w”的不等式3 .某线性规划问题，n个变量，m个约束方程，系数矩阵的秩为 m(mn)则下列说法正确 的是ABDE。A .基可行解的非零分量的个数不大于mB .基本解的个数不会超过 Cmn个C.该

5、问题不会出现退化现象D .基可行解的个数不超过基本解的个数E. 该问题的基是一个 m Xm阶方阵4 .若线性规划问题的可行域是无界的，则该问题可能ABCDA .无有限最优解 B.有有限最优解 C.有唯一最优解 D .有无穷多个最优解 E.有有限多个最优解5. 下列说法错误的有_ABC_。B .极点与基解一一对应D .满足约束条件的解就是线性规划的可行解ADA .基本解是大于零的解C .线性规划问题的最优解是唯一的6. 线性规划问题若有最优解，则最优解A定在其可行域顶点达到B只有一个 C会有无穷多个 D唯一或无穷多个E其值为0 四、名词解释1基：在线性规划问题中，约束方程组的系数矩阵 A的任意一

6、个 m xm阶的非奇异子方阵 B, 称为线性规划问题的一个基。2、线性规划问题：就是求一个线性目标函数在一组线性约束条件下的极值问题。3 .可行解：在线性规划问题中，凡满足所有约束条件的解称为线性规划问题可行解4、可行域：线性规划问题的可行解集合。5、基本解：在线性约束方程组中，对于选定的基B令所有的非基变量等于零，得到的解，称为线性规划问题的一个基本解。6、基本可行解：在线性规划问题中，满足非负约束条件的基本解称为基本可行解。线性规划的基本方法一、填空题1 对于目标函数极大值型的线性规划问题，用单纯型法求解时，当基变量检验数为0,非基变量检验数3 j_0对应的非基变量 xk的系数列向量 Pk

7、_0_时，则此问题是无界的。7. 在大M法中，M表示充分大正数。二、单选题1 在单纯形迭代中，出基变量在紧接着的下一次迭代中B立即进入基。A 会B.不会C.有可能 D 不一定2 在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中B。基变量3 用单纯形法求解极大化线性规划问题中，在最优单纯形表中若某非基变量检验数为零,而其他非基变量检验数全部0，则说明本问题B。A甘桁.曰牛丽B .有多重最优解C无界D 无解A 有惟最优解4 .下列说法错误的是BA 图解法与单纯形法从几何理解上是一致的B 在单纯形迭代中，进基变量可以任C 在单纯形迭代中，出基变量必须按最小比值法则选取D 人工变量离开

8、基底后，不会再进基5单纯形法当中，入基变量的确定应选择检验数CA绝对值最大B绝对值最小C 正值最大D 负值最小6. 在线性规划问题的典式中，基变量的系数列向量为_D_A 单位阵B非单位阵C单位行向量D单位列向量7. 在约束方程中引入人工变量的目的是_D_A 体现变量的多样性B变不等式为等式C 使目标函数为最优D 形成一个单位阵8. 求目标函数为极大的线性规划问题时，若全部非基变量的检验数w0,且基变量中有人工变量时该问题有_B_A无界解B无可行解C唯一最优解D无穷多最优解三、多选题1 对取值无约束的变量 xj。通常令xj=xj - x ” j，其中XjAO, Xj”O，在用单纯形法 求得的最优

9、解中，可能出现的是ABC2 设X(1), X是用单纯形法求得的某一线性规划问题的最优解，则说明ACDE。A.此问题有无穷多最优解B.该问题是退化问题C.此问题的全部最优解可表示为入X+(1 入)X，其中0 W入4 D . X,X(2)是两个基可行解 E. X,X的基变量 个数相同3 .单纯形法中，在进行换基运算时， 应ACDE o A .先选取进基变量，再选取出基变量 B .先选出基变量，再选进基变量C.进基变量的系数列向量应化为单位向量D .旋转变换时采用的矩阵的初等行变换 E.出基变量的选取是根据最小比值法则6 .从一张单纯形表中可以看出的内容有ABCE o A .一个基可行解B.当前解是

10、否为最优解C .线性规划问题是否出现退化D .线性规划问题的最优解 E.线性规划问题是否无界四、名词、简答1、 人造初始可行基：当我们无法从一个标准的线性规划问题中找到一个m阶单位矩阵时，通常在约束方程中引入人工变量，而在系数矩阵中凑成一个m阶单位矩阵，进而形成的一个初始可行基称为人造初始可行基。2、 单纯形法解题的基本思路？可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步得到改善，直到最后球场最优解或判定原问题无解。线性规划的对偶理论一、填空题1 .线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最_小值/极小值的线性规划问题与之对应，反之亦然

11、。2 .在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。3 .如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式o4 .对偶问题的对偶问题是原I o5 .若原问题可行，但目标函数无界，则对偶问题不可行。6 线性规划问题的最优基为B，基变量的目标系数为 Cb,则其对偶问题的最优解Y * = C bB t。7 .若X*和Y*分别是线性规划的原问题和对偶问题的最优解，则有CX * =Y * b。8 .若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX c YX)_。二、单选题1 .线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0,则其对偶问题约束

12、条件为A形式。A . “” B. “w”C, “ ” D .“ = ”2 .设X、Y分别是标准形式的原问题与对偶问题的可行解，则_C_。3 .如果z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值* _w A。A. W *=Z * B. W * MZ *C. W * Z *4 .如果某种资源的影子价格大于其市场价格，则说明_BA .该资源过剩B .该资源稀缺 C .企业应尽快处理该资源 D .企业应充分利用该资源，开僻新的生产途径三、多选题1 .在一对对偶问题中，可能存在的情况是ABC。A .一个问题有可行解，另一个问题无可行解B.两个问题都有可行解C.两个问题都无可行解

13、D.一个问题无界，另一个问题可行2.下列说法错误的是 B_。A 任何线性规划问题都有一个与之对应的对偶问题B 对偶问题无可行解时，其原问题的目标函数无界。 C.若原问题为 maxZ=CX , AXC, Y0。D .若原问题有可行解，但目标函数无界，其对偶问题无可行解。3 如线性规划的原问题为求极大值型，则下列关于原问题与对偶问题的关系中正确的是BCDE。A原问题的约束条件“X” ，对应的对偶变量“X 0” B原问题的约束条件为“=”，对 应的对偶变量为自由变量 C.原问题的变量“X 0”，对应的对偶约束“X” D .原问题的变 量“w O ”对应的对偶约束“w” E.原问题的变量无符号限制，对

14、应的对偶约束“ =”4 .一对互为对偶的问题存在最优解，则在其最优点处有BDA.若某个变量取值为 0 ,则对应的对偶约束为严格的不等式B .若某个变量取值为正，则相应的对偶约束必为等式C.若某个约束为等式， 则相应的对偶变取值为正 D .若某个约束为严格的不等式，则相应的对偶变量取值为0 E.若某个约束为等式，则相应的对偶变量取值为0四、名词、简答题1、 对称的对偶问题：设原始线性规划问题为maxZ=CX s.t - _ AX wbX X0称线性规划问题 minW=Yb_ s.tYA XC YX0为其对偶问题。又称它们为一对对称的对偶问题。2、影子价格：对偶变量 Yi表示与原问题的第i个约束条

15、件相对应的资源的影子价格，在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不变），原问题目标函数最优值增加的数量。问题具有无界解，则另一个问题具有无可行解；3.原问题和对偶问题都无可行解。线性规划的灵敏度分析一、填空题1、在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的 变化。2 如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应 出基。3 若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表 的基础上运用对偶单纯形法求解。4. 如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个

16、变量。_5. 若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。二、单选题1 若线性规划问题最优基中某个基变量的目标系数发生变化，则C。A 该基变量的检验数发生变化B.其他基变量的检验数发生变化C 所有非基变量的检验数发生变化D .所有变量的检验数都发生变化2 在线性规划的各项敏感性分析中，一定会引起最优目标函数值发生变化的是旦。A .目标系数Cj的变化B .约束常数项bi变化C.增加新的变量 D .增加新约束三、多选题1 在灵敏度分析中，我们可以直接从最优单纯形表中获得的有效信息有ABCE。A 最优基B的逆B-1B.最优解与最优目标函数值C.各变量的检验数ABC

17、 。3 线性规划问题的各项系数发生变化，下列不能引起最优解的可行性变化的是A 非基变量的目标系数变化B.基变量的目标系数变化 C 增加新的变量 D，增加新的约束条件四、名词、简答题1. 灵敏度分析：研究线性规划模型的原始数据变化对最优解产生的影响运输问题一、填空题1 物资调运问题中，有 m个供应地，Ai, A2，Am , Aj的供应量为ai（i=1 , 2，m）,n个需求地 Bi, B2，Bn, B的需求量为 bj（j=1 , 2，n），则供需平衡条件为mnai =bii ij i2 物资调运方案的最优性判别准则是：当全部检验数非负时前的方案一定是最优方案。3 .可以作为表上作业法的初始调运方

18、案的填有数字的方格数应为m+n 1个（设问题中含有m个供应地和n个需求地）4 .若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运置而使运费增加1。5 调运方案的调整是要在检验数岀现负值的点为顶点所对应的闭回路内进行运量的调整。6 按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_!条闭回路7 .在运输问题中，单位运价为Cij位势分别用Ui, Vj表示，则在基变量处有cij Cij=u i+V j o8、供大于求的、供不应求的不平衡运输问题，分别是指mai _ n b的运输问题、ai _i i j ii i n bi的运输问题。j i10 在表上作业法所得到的

19、调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。11 .在某运输问题的调运方案中，点（2，2）的检验数为负值，（调运方案为表所示）则相应的调整量应为300_。InmIVA300100300B400C60030012. 若某运输问题初始方案的检验数中只有一个负值：2 ,则这个2的含义是该检验数所在格单位调整量。13. 运输问题的初始方案中的基变量取值为正。_14在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字 0二、单选题1. 在表上作业法求解运输问题中，非基变量的检验数D。A.大于0 B.小于0 C .等于0D .以上三种都可能2. 运输问题的初始方案中

20、，没有分配运量的格所对应的变量为BA基变量B非基变量C松弛变量D 剩余变量3. 表上作业法中初始方案均为AA可行解B非可行解C待改进解D 最优解A 水平B 垂直C水平+垂直D水平或垂直5.运输问题中分配运量的格所对应的变量为AA基变量B非基变量C松弛变量D 剩余变量6. 所有物资调运问题，应用表上作业法最后均能找到一个DA可行解B非可行解C 待改进解D最优解7般讲，在给出的初始调运方案中，最接近最优解的是_CA西北角法B最小元素法C差值法D 位势法8.在运输问题中，调整对象的确定应选择CD检验数为负且绝对值最A检验数为负B检验数为正C检验数为负且绝对值最大9. 运输问题中，调运方案的调整应在检

21、验数为_C_负值的点所在的闭回路内进行。A任意值B最大值C绝对值最大D绝对值最小10. 表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个 CA基B可行解C初始基本可行解D最优解11平衡运输问题即是指 m个供应地的总供应量 _D_ n个需求地的总需求量。A 大于 B 大于等于C小于 D等于三、多选题1 .下列说法正确的是 ABD。A.表上作业法也是从寻找初始基可行解开始的B.当一个调运方案的检验数全部为正值时，当前方案一定是最佳方案C最小元素法所求得的运输的运量是最小的D 表上作 业法中一张供需平衡表对应一个基可行解四、名词1、平衡运输问题：m个供应地的供应量等于

22、 n个需求地的总需求量，这样的运输问题称 平衡运输问题。2、不平衡运输问题：m个供应地的供应量不等于 n个需求地的总需求量，这样的运输问题 称不平衡运输问题。整数规划一、填空题1 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目 标函数值的下界。2 .在分枝定界法中，若选 Xr=4 / 3进行分支，则构造的约束条件应为Xi W1 , X1。3 .已知整数规划问题 Po ,其相应的松驰问题记为 Po 若问题Po无可行解，贝则可题P。 无可行解。4 在0 - 1整数规划中变量的取值可能是 _0 或 1。5对于一个有n项任务需要有n个人去完成的分配问题，其 解中取值为1的变

23、量数为L个。6 分枝定界法和割平面法的基础都是用线性规划方法求解整数规划。7 若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行6 1 2得X1 + 1 / 7x3+2 / 7x5=13 / 7,则以X1行为源行的割平面方程为二一严-(X5W0。8.求解分配问题的专门方法是匈牙利法。9 在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零。10.分枝定界法一般每次分枝数量为裁.二、单选题1 整数规划问题中，变量的取值可能是D。A .整数B 0或1C .大于零的非整数 D .以上三种都可能2 .在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A。A.纯整数规划

24、 B.混合整数规划 C. 0 1规划D .线性规划3 .下列方法中用于求解分配问题的是D_。A .单纯形表B .分枝定界法 C .表上作业法 D .匈牙利法三、多项选择1 .下列说明不正确的是 ABC。A .求解整数规划可以采用求解其相应的松驰问题，然后对其非整数值的解四舍五入的 方法得到整数解。B .用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行 解时，通常任取其中一个作为下界。C.用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D .用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。2 .在求解整数规划问题时，可能出现

25、的是ABC。A.唯一最优解 B.无可行解 C.多重最佳解 D .无穷多个最优解3 .关于分配问题的下列说法正确的是ABD。A.分配问题是一个高度退化的运输问题B.可以用表上作业法求解分配问题C.从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案 D.匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做。4.整数规划类型包括（CDE ）A线性规划 B非线性规划C纯整数规划 D混合整数规划E 0 1规划三、名词1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。2、 01规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或

26、1，这样的问 题称为0 1规划。3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合 整数规划。图与网络分析一、填空题1 .任一树中的边数必定是它的顶点数减1。2 最小树问题就是在网络图中，找出若干条边，连接所有结点,而且连接的总长度最小。3. 18、求支撑树有 破圈法和 避圈法两种方法。二、单选题1、关于图论中图的概念，以下叙述（B）正确。A图中的有向边表示研究对象，结点表示衔接关系。B图中的点表示研究对象，边表示点与点之间的关系。C图中任意两点之间必有边。D图的边数必定等于点数减 1。2 .关于树的概念，以下叙述 （B）正确。A树中的点数等于边数减 1B连通无圈

27、的图必定是树C含n个点的树是唯一的D任一树中，去掉一条边仍为树。3 .一个连通图中的最小树 （B），其权（A）。A是唯一确定的B可能不唯一C可能不存在D 一定有多个。4 关于最大流量问题，以下叙述（D）正确。A 一个容量网络的最大流是唯一确定的B达到最大流的方案是唯一的C当用标号法求最大流时，可能得到不同的最大流方案D当最大流方案不唯一时，得到的最大流量亦可能不相同。5.图论中的图，以下叙述 （C）不正确。A .图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。B.图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。C 图论中的边表示研究对象，点表示研究对象之间的特

28、定关系。D .图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。6 .关于最小树，以下叙述 （旦）正确。A 最小树是一个网络中连通所有点而边数最少的图B 最小树是一个网络中连通所有的点，而权数最少的图 C . 一个网络中的最大权边必不包含在其最小树内D . 一个网络的最小树一般是不唯一的。7 关于可行流，以下叙述 （A）不正确。A 可行流的流量大于零而小于容量限制条件B 在网络的任一中间点，可行流满足流人量=流出量。C 各条有向边上的流量均为零的流是一个可行流D 可行流的流量小于容量限制条件而大于或等于零。三、多选题1 .关于图论中图的概念，以下叙述（123）正确。（1）图中的

29、边可以是有向边，也可以是无向边（2）图中的各条边上可以标注权。（3）结点数等于边数的连通图必含圈 （4）结点数等于边数的图必连通。2 .关于树的概念，以下叙述 （123）正确。1）树中的边数等于点数减1（2）树中再添一条边后必含圈。（3）树中删去一条边后必不连通（4）树中两点之间的通路可能不唯一。条边后必含圈（4）任一连通图生成的各个支撑树其边数必相同4 .在下图中，（abed）不是根据生成的支撑树。5 .从赋权连通图中生成最小树，以下叙述（124）不正确。（1）任一连通图生成的各个最小树，其总长度必相等（2）任一连通图生成的各个最小树，其边数必相等。（3）任一连通图中具有最小权的边必包含在生

30、成的最小树上。最小树中可能包括连通图中的最大权边。6 .从起点到终点的最短路线，以下叙述（123）不正确。1）从起点出发的最小权有向边必含在最短路线中。（2）整个图中权最小的有向边必包含在最短路线中。（3）整个图中权最大的有向边可能含在最短路线中（4）从起点到终点的最短路线是唯一的。7 .关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述（123）不正确。（1）增广路上的有向边的方向必须是从发点指向收点的（2）增广路上的有向边，必须都是不饱和边（3）增广路上不能有零流边（4）增广路上与发点到收点方向一致的有向边不能是饱 和边，相反方向的有向边不能是零流边8 .关于树，以下叙述（ABCE

31、）正确。A .树是连通、无圈的图 B .任一树，添加一条边便含圈C.任一树的边数等于点数减1。D .任一树的点数等于边数减1E.任一树，去掉条边便不连通。9 .关于最短路，以下叙述 （ACDE）不正确。A从起点出发到终点的最短路是唯一的。B .从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的。C.从起点出发的有向边中的最小权边，一定包含在起定不包含在起点到终点的最点到终点的最短路上 D.从起点出发的有向边中的最大权边,短路上。E.整个网络的最大权边的一定不包含在从起点到终点的最短路线上。10 .关于增广路，以下叙述 （BC ）正确。A.增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。B .增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致。C 增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。D