运筹学客观题.doc

《运筹学客观题.doc》由会员分享，可在线阅读，更多相关《运筹学客观题.doc（20页珍藏版）》请在三一文库上搜索。

1、运筹学2012参考资料（客观题）一. 判断题1、LP问题的每一个基解对应可行域的一个顶点。（）2、LP问题的基本类型是“max”型问题。（）3、LP问题的的每一个基可行解对应可行域的一个顶点。（ ）4、在单纯形计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。（ ）5、对取值为无约束的变量，通常令，其中。在用单纯形法求得的最优解中有可能出现且。（）6、在单纯形的计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。（）6、在单纯形的计算中，选取最大负检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。（）7、某LP有且仅有有限个（大于等

2、于2）最优解。（）8、某LP模型的可行域非空有界，则其顶点中必存在最优解。（ ）9、用大M法处理人工变量时，若最终表上基变量中仍含有人工变量，则原问题无可行解。（）10、若可行域是空集，则表明存在矛盾的约束条件。（ ）11、用单纯形法求LP问题，若最终表上非基变量的检验数均非正，则该模型一定有惟一最优解。（）12、凡具备优化、限制、选择条件且能将有关条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型来处理。（ ）13、用单纯形法求解LP问题时，无论是求极大化问题还是求极小化问题，用来确定基变量的最小比值原则相同。（ ）14、若X是某LP的最优解，则X必为该LP可行域的某一个顶点

3、。（）15、用单纯形法求解LP问题，若最终表上非基变量的检验数均严格小于零，则该模型一定有惟一的最优解。（ ）16、单纯形法通过最小比值法选取换出变量是为了保持解的可行性。（ ）16、单纯形法计算中，如不按最小比值法选取换出变量，则在下一个解中至少有一个基变量的值为负。（ ）17、线性规划问题的某可行解中有零分量则说明该解在可行域的边界上，若可行域中存在不能由顶点凸组合表出的点，则该可行域必为开域。（ ）18、图解法同单纯形法虽然求解形式不同，但从几何意义上解析，两者是一致的。（ ）19、线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。（ ）2

4、0、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ）21、用单纯形法求解标准形式的线性规划问题时，与对应的变量都可以被选作换入变量。（ ）22、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（ ）23、线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。（）24、若分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中为正的实数。（）25、对一个有个变量、个约束的标准型的线性规划问题，其可行域顶点恰好为个。（）26、当线性规划的原问题存在可行解时，则其对偶问题一定存在可行解。（）27、如线性规划对偶

5、问题无可行解，则原问题也一定无可行解。（）28、如线性规划原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。（）29、任何线性规划问题存在并具有惟一的对偶问题。（ ）30、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题具有无界解。（）31、若线性规划的原问题有多重最优解，则其对偶问题也一定有多重最优解。32、设分别为标准形式的原问题与对偶问题的可行解，分别为其最优解，则恒有。（ ）33、已知为线性规划的对偶问题的最优解，若，说明在最优生产计划中第种资源已完全耗尽。（ ）34、若某种资源的影子价格等于，在其它条件不变的情况下，当该

6、种资源增加5个单位时，相应的目标函数值将增大（）35、应用对偶单纯形法计算时，若单纯形表中某一基变量，又所在行的元素全部大于或等于零，则可以判别其对偶问题具有无界解。（ ）36、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有为以最有解、有无穷多最优解、无界解、无可行解。（）37、在运输问题中，只要给出一组含个非零的，且满足，就可以作为一个出始基可行解。（）38、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数，最优调运方案将不会发生变化。（ ）39、如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数，最优调运方案将不会发生变化。（）40、

7、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。（ ）41、当所有产地的产量和销地的销量均为整数时，运输问题的最优解也为整数值。（ ）42、整数规划问题界的目标函数值一般优于其相应的松弛问题解的目标函数值。（）43、用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的一个下界。（ ）44、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，经比较后确定是否再进行分支。（）45、指派问题效率矩阵的每个元素乘上同一个常数，将不影响最优指派方案。（ ）46、指派问题数学模型的形式与运输问

8、题十分相似，故也可以用表上作业法求解。（ ）47、整数规划中指派问题最优解有这样的性质，若从系数矩阵的一列（行）各元素中分别减去该列（行）的最小元素，得到新矩阵，那么以为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。（ ）48、分配问题的每个元素都加上同一个常数，并不会影响最优分配方案。（ ）49、分配问题的每个元素都乘上同一个常数，并不会影响最优分配方案。（ ）50、分配问题与运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。（ ）51、隐枚举法也可以用来求解分配方案。（ ）52、最优化原理是“无论初始状况和初始决策如何，对于前面决策所造成的某一状况而言，余下的决策序列必构

9、成最优策略。”（ ）53、一般的排队系数由输入过程、排队规则、服务机构组成。（ ）54、容量网络中满足容量限制条件和中间点平衡条件的弧上的流，称为可行流。（ ）55、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而在图中甸的相对位置、点与点的连线的长短曲直都要严格注意。（）56、在任一连通图G中，当点集V确定后，树图是G中边数最少的连通子图。（ ）57、如果图中从至各点均有唯一的最短路，则连接至其它各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。（）58、求网络最大流问题可归结为求解一个线性规划问题。（ ）59、简单链是指链中含的边均不相同。（ ）60、简单圈是指圈中

10、含的边均不相同。（ ）61、最短路线一定是唯一的。（ ）62、一个连通图的最小支撑树是唯一的。（ ）63、一个连通图只能有一个最小支撑树。（ ）64、图中两点间带箭头的连线称为弧。（ ）65、连通图中不能形成圈。（ ）66、任一图中，奇点的个数是奇数。（）67、矩阵对策的解可以是不唯一的。（ ）63、具有竞争或对抗性质的行为称为对策行为。（ ）68、当一个局势出现后，对策的结果就确定了。（ ）69、矩阵策略G在纯策率意义下有解，且的充分必要条件是不是赢得矩阵A的一个鞍点。（ ）70、矩阵策略G在纯策率意义下有解，且的充分必要条件是是赢得矩阵A的一个鞍点。（ ）71、矩阵对策中，如果最优解要求一

11、个局中人采用纯策略，则另一局中人也必须采取纯策略。（ ）（当矩阵对策鞍点不惟一时，命题结论不成立）72、矩阵对策中当局势达到均衡时，任何一方单方面改变自己的策略（纯策略或者混合策略）将意味着自己更少的赢得或更大的损失。（ ）73、任何矩阵对策一定存在混合策略意义下的解，并可以通过求解两个互为对偶的线性规划问题得到。（ ）74、矩阵对策的对策值相当于进行若干次对策后，局中人I的平均赢得值或剧中人II的平均损失值。（ ）（当矩阵对策有惟一鞍点时，局中采取纯策略）75、期望损失原则就是在损失矩阵上求各个方案的期望值，然后选期望值最小者的方案作为最优方案。（ ）76、据后验期望准则做出的最优方案必受样

12、本信息的结果的影响。（ ）77、湿度乐观准则不受决策者了关于悲观的情绪影响。（ ）78、决策问题的最优方案总是存在的，从而用各种决策准则进行决策，所得的最优方案总是一致的。（ ）二. 填空题 1、线性规划问题的数学模型中目标函数和约束函数都是_线性_函数。2、图解法求解极小化线性规划问题时，等成本线越往左下角移动，成本越_小_。3、图解法求解极小化线性规划问题时，等成本线越往右上角移动，成本越_大_。4、下列的数学模型(A)； (B)中 (B)是线性规划， 令得 可转化为线性规划问题5、下列的数学模型(A)； (B)； (C)； (D)； (E)中 (B)是线性规划， (E)可转化为线性规划问

13、题6、线性规划模型有3种参数，其名称分为价值参数（目标函数系数）、资源常数（约束右端常数）、技术系数（约束系数）。7、对于右下面的图中LP问题的可行解为OFIHC所围区域，基本解为O,A,B,C,D,E,F,G,H,I 共十个点，基本可行解为O,F,H,I,C共五个点。8、对于平面中的某LP的约束集合如右图其可行解为OGEDH所围阴影区，基本解为 图中所有直线及坐标轴之间的交点，基本可行解为OGEDH五个点。9、原问题有可行解但无最优解，则其对偶问题 无可行解 10、对偶问题中的决策变量称为影子价格11、LP问题的对偶问题为，对偶问题中的决策变量称为影子价格12、线性规划中的影子价格就是对偶问

14、题的检验数。13、影子价格与对偶问题的关系是是对偶问题的最优解。14、对偶定理有三个互补松弛性、强对偶性、弱对偶性。15、若对偶问题为无界解，其原问题为无可行解。16、LP数学模型为，则其对偶数学模型为17、LP数学模型为，其对偶数学模型的最优解为，则原数学模型的最优目标函数值为18、分枝定界法的基本思想计算法依据是 对最大化的整数规划问题A，先求与它相应的线性规划（不是整数）的问题B，若其最优解不符合整数条件，则将目标函数最大值定为上界。然后将B的可行域分成子区域（分析），逐步减少值，最终求出最优。19、如果把约束方程标准化为时，是决策变量，是决策变量，是松弛变量，是剩余变量，是人工变量。2

15、0、LP的基本可行解与基本解的区别是 基本可行解的分量。21、LP的基可行解与基解的区别是 基解的可以有分量。22、在单纯性迭代中，任何出基的变量在紧接着的下一次迭代中，不会（选会或不会填空）立即再入基。23、若对偶问题为无界解，则其原问题为 无可行解。24、求目标最大的LP中，有无穷最优解的条件是 判别式中至少有一个零。25、线性规划中的影子价格就是对偶问题的 检验数；26、对经济类问题求极大化的过程中，用单纯形法迭代简化的表格表示如下表（假定没有人工变量）：基常数4100-1-501-102-300-413检验数00-30对六个未知数的约束条件选择填空，使以下关于该表的说法为真。（1）现行

16、解有无穷多最优解（A）A. ，或 B.，或C.，或 （2）现行解不可行（B）A. B. C.为任意数 （3）一个约束有矛盾（C）A. B. C. （4）现行解是退化的基本可行解（C）A. B. C. （5）现行解是惟一最优解（A）A. B. C. 27、某一最大线性规划问题在单纯形计算时的下表：（书中例）基常数21002-1-501-103-300-41检验数00-30对六个未知数满足什么约束条件填空，原问题要求所有变量均非负。（1）时现行解是非可行基解；（2）时该LP问题有惟一最优解；（3）或时该LP问题有无穷多最优解；（4）时现行解是退化基可行解；（5）时该LP问题有无界解或称目标函数无界

17、；（6）时现行解是可行解但非最优解，只有可以进基且出基变量必为第三个基变量。（7）为人工变量时该LP问题无可行基解。28、对经济类问题求极大化的过程中，用单纯形法迭代简化的表格表示如下表（假定没有人工变量）：基常数0100042010-21000-413检验数定义为0006表中均非人工变量，对六个未知数的约束条件填空，使以下关于该表的说法为真。（1）当时现行解是惟一最优解（2）当或时现行解为最优，但有无穷多最优解）（3）当时现行解是退化基本最优解（4）当时线性规划问题有可行解，但目标函数无界（5）当时线性规划问题无可行解（至少有一个约束有矛盾）29、已知某线性规划问题用单纯形法计算时得到的初始

18、单纯形表及最终单纯形表如下，则最优表所对应的基的逆矩阵为 B ，最优解为 E ，最优值为 F 。2-11000CB基XB常数0603111000101-1201002011-1001检验数定义为-21-10000100011-1-2215101/201/21/2-1501-2/30-1/21/2检验数003/203/21/2(A)，(B)，(C)，(D)，(E)，(F)，(G)(?有人给答案ADF)30、第种资源的影子价格的定义是 BCE ，第种产品的机会成本定义是 F (A)检验数，(B)对偶最优解，(C)，(D)，(E)该种资源在最优决策下的边际价值，(F)31、假设某一极大化线性规划问题

19、，其约束均为“”，最优单纯形表如下。则其对偶问题的最优解为 B ，若对于第一种资源不足时，可向市场购买，当市场价格低于 F 时，购买才有利。12151000CB基XB常数158001-31/3-5/91230106-1/38/9检验数定义为001717/3(A)，(B)，(C)，(D)，(E)1，(F)，(G)(?有人给答案BE)31、已知基本线性规划问题，用单纯形法计算时得到的中间某两步的计算表如下，试将空白处数字填上。354000CB基XB常数58/32/3101/300014/3-4/305-2/310020/35/304-2/301检验数-1/304-5/300580/41010-15

20、/418/41-10/41450/41001-6/415/414/41344/41100-2/41-12/4115/41检验数000-45/41-24/41-11/41解 令，则，进而可用红字去填表了32、下列模型中，ABCFG为线性规划模型，D为线性目标规划模型，B为运输问题模型C为指派问题模型。(A)，(B)，(C)，(D)，(E)，(F)，(G)，其中为常数。33、求解整数规划常用的算法有 BC ，求解0-1规划常用的算法有 DE ，求解指派问题常用的算法有 F ，(A)单纯形法，(B)分支定界法，(C)割平面法，(D)完全枚举法，(E)隐枚举法，(F)匈牙利法， (G)表上作业法34、

21、0-1变量可以很好地用于处理相互排斥的约束条件。若有个相互排斥的约束条件如下：，下面（哪组）A C式子表达了这个相互排斥的约束条件中只有一个起作用，其中为一个很大的正数。(A)，(B)，(C)，(D)35、某工程公司拟从4个项目中选择若干项目，若令其中。用的线性表达式表示下列要求：（1）从1、2、3项目中至少选一个；（2）只有项目2被选中，项目4才能被选中。36、关于匈牙利法，下列说法正确的是A B(A)匈牙利法只能用于求解平衡分配问题，(B)关于极大化问题，匈牙利法不能直接求解，(C)对于极大化问题，令转化为极小化问题，则用匈牙利法求解时，极大化问题的最优解就是极小化问题的最优解，但目标函数

22、相差，37、容量网络中满足容量限制条件和中间点平衡条件的弧上的流，称为 可行流；38、网络技术中的关键路线的确定可以用 作业最早开始时间 ，和 作业最迟开始时间 两两相等的连线来决定。39、给一个图，如果图，使及，则称是的一个支撑子图40、树的任意两个顶点之间有且只有一条 初等链。41、一个_无环_且_无多重边_的图称为简单图。42、若从一个图中去掉一条线后，该图仍是连通图，则该图中一定含有_圈_。43、图G中，若任何两点之间至少存在_一条链_，则称G是联通图。44、有向图是由_点_和_弧_所构成的。45、次为0的点，叫_孤立点_。46、次为1的点，叫_悬挂点_。47、次为1的点，叫_悬挂点_

23、，与该点关联的边称为 悬挂边 。48、一图中，次为奇数的点称为 奇点 ，图中这种点的的个数是 偶点 。49、一个有7个点的连通图至少有_ 6_条线。50、一个树中点的个数为 m，则该树中线的条数为 。51、一个_无圈_且_连通_的图称为树。52、对策现象的三个基本因素为：_局中人_、_策略集_、_赢得函数（支付函数）。53、矩阵对策中，局势是对策解的充分必要条件是对任意有54、若用以下表达式作为目标规划的目标函数，逻辑上正确的是BCDA. B. C. D. 55、动态规划方法是解决 B ，它是在明确 CDGHIL 条件的基础上，建立 F ，求解的最终应求出 K 。A.动态问题 B.多阶段决策过

24、程的问题 C. 阶段和阶段数 D.无后效性 E.最优性原理 F. 基本方程（递推关系式）G.决策变量与允许决策集 H. 阶段指标与指标函数 I. 状态转移矩阵 J.逆序解法或顺序解法 K. 最优决策顺序和最优目标值 L. 状态与状态变量56、对于动态规划，下列说法正确的是 ABC 。A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目B. 动态规划中，定义状态时应保证在各个阶段中所做决策的互相独立性C. 动态规划的最优性原理，保证了从某一状态开始的未来决策独立于先前已做出的决策D. 对于一个动态规划问题，应用顺推和逆推解法可能会得出不同的最优解E. 假如一个线性规划问题含有5个变量和3

25、个约束，则用动态规划求解时将划分为3个阶段，每个阶段的状态将由一个5维的向量组成57、在动态规划中，贝尔曼提出的最优化原理是1个最优策略的子策略总是最优的，它是判断一个策略是最优策略的必要条件。58、非线性规划与的基本方程分别为B和 C 。A. B. C. D. 59、研究动态规划时，一般要确定的要素是 阶段 ，状态，决策，状态转移方程，阶段指标，其求解的一般方法是 基本递推方程 。60、排队模型中的分别表示到达时间为负指数分布、服务时间服从爱尔朗分布、服务台有2台。61、排队中最常用的相继到达间隔时间和服务时间的分布是 负指数分布。三. 选择题1、一般在应用线性规划在建立模型时要经过四个步骤

26、：明确问题，确定目标，列出约束因素搜集资料，确定模型模型求解与检验优化后分析原问题以上四步的正确顺序是(A)A. B. CD. 2、关于线性规划模型的可行解区，叙述正确的为（ C ）A可行解区必有界 B可行解区必然包括原点C可行解区必是凸的 D可行解区内必有无穷多个点3、在下面的数学模型中，属于线性规划模型的为（ B ）4、 若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划 问题最优解为（ C ）A两个B零个 C无穷多个D有限多个 5、某二维线性规划问题的可行域如下图阴影所示，则该问题的最优解（A）A必在正方形的某个顶点达到B必在正方形内部达到C必在正方形外部达到D必在AB

27、边上达到6、对于LP问题标准形：，利用单纯形法求解时，每作一次换基迭代，都能保证它相应的目标函数值必为 ( B)A.增大 B.不减少 C. 减少D. 不增大7、若LP最优解不惟一，则在最优单纯形表上 ( A)A. 非基变量的检验数必有为零 B. 非基变量的检验数不必有为零者8、求解线性规划问题时，引入人工变量是为了 ( B)A. 使该模型存在可行解 B. 确定一个初始的基可行解C. 使该模型标准化9、LP数学模型由 ( A,C,E)三个部分组成A. 目标要求 B. 基本方程 C. 非负条件D. 顶点集合 E. 约束条件10、极小化线性规划标准化为极大化问题后，原规划与标准型的最优解 ( B)，

28、目标函数值（A ）A. 相差一个负号 B. 相同 C. 没有确定的关系. 11、右图中阴影区是线性规划，的可行域，虚线为目标函数等值线，若图中箭头所指的方向是目标函数值增加的方向，则有 ( B)A. B. C. D. 12、大M法和两阶段法是用来 ( B)的。当用两阶段法求解LP问题时，第一阶段建立的辅助LP标准型的目标函数为（ G ）A.简化计算 B. 处理人工变量 C. 人工变量之和D. E. 进行灵敏度分析 F. 松弛变量、剩余变量和人工变量之和G. 人工变量之和的相反数13、用大M法求解LP模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型 ( C)。A.有可行解，但无最

29、优解 B. 有最优解 C. 无可行解. 14、已知是某LP的两个最优解，则 ( D)也是该LP的最优解。A. B. C. D. 无法判断15、线性规划问题的标准型最本质的特点是 ( B,D)A. 目标要求是极小化 B. 变量和右端常数要求非负 C. 变量可以取任意值D. 约束条件一定是等式形式16、目标函数取极小化（）的线性规划可以转化为目标函数取极大化即 ( B)的线性规划问题求解；两者的最优解（ E ），最优值（ D ）A. B. C. D. 相差一个负号E. 相同 F. 无确定关系 G. 17线性规划问题。已知最优解为，则其对偶问题的最优解为 ( B)A. （3，2，0） B. C. D

30、. 18、若LP问题的约束条件是，其可行域有一个顶点是（D）A. B. C. D. 19、若LP问题有最优解，则LP问题（，其中为一正常数，有（D）A.最优解，最优值 B.最优解，最优值 C.最优解，最优值 D.最优解，最优值 20、判断下列说法是否正确（C,D）A.线性规划问题的基本解对应可行域的顶点 B.若是某线性规划问题的可行解，则也必是该问题的可行解 C. 线性规划问题若存在可行解，其可行域集合为凸集D. 若是某线性规划问题的最优解，则也是该问题的最优解 21、用线性规划求解标准型的线性规划问题时（C,D）A.当所有检验数时，即可判定表中解即为最优解B.为使目标函数值最快增长，必须选取

31、与最大正检验数对应的变量为换入基的变量C.按最小比值原则确定换出基的变量是为了保证迭代计算后的解仍为基本可行解D.若存在，且该列系数，则线性规划问题最优解不存在（无界解） 22、线性规划的可行域非空无界，则（D）A.其对偶问题不一定是无可行解 B.该线性规划无最优解C.该线性规划一定存在最优解 D.该问题存在基可行解 23、线性规划的原问题与其对偶问题之间存在如下关系（A,D）A.对偶问题的对偶问题时原问题B.原问题存在可行解，其对偶问题必存在可行解 C.原问题无可行解，其对偶问题必无可行解 D.原问题有无穷多最优解，其对偶问题也有无穷多最优解 24、LP问题，则有两对偶问题，各自最优解与间关

32、系（C）A. B. C. D. ABC以外的其它关系25、已知某个含有10个节点的树图，其中9个节点的次（线度）为1,1,3,1,1,1,3,1,3，则另一节点的次为 ( C)A. 1 B. 4 C. 3 D. 226、用标号法寻找网络最大流时，发生标号中断。这时若用V表示已标号的节点集合，用表示未标号的节点集合，则在网络中所有方向的弧上有( C)，方向的弧上有(D)， A. B. C. D. （为流量，为弧的容量）27、顾客到达有三个并联服务站的排队系统，一是在每个服务站前各排一行队伍，顾客选队长最短的行排在末尾，二是只排一行队伍，近先到先服务规则依次服务。设顾客在系统中平均逗留时间第一种情

33、况下为，第二种情况下为，则有 ( C)A. B. C. D. 不一定28、对系统中 顾客容量有限的排队系统M/M/S，系统到达稳定状态的条件是( D)A. B. C.允许，但 D. A,B,C,之外的其它条件29、满足下面条件的简单图是树图（A,C,D）A.无圈且连通 B.有个点恰有条边 C.图中任意两点间存在惟一的链 D. G无圈，但只要加一条边即得惟一的圈30、在目标规划中（D） A.正偏差变量取正值，负偏差变量取负值 B.目标函数可以是求敏敏min，也可以求max C.目标函数中的优先级之间表明数量上的重要性差别，如比级重要10倍或20倍等D.模型可以含系数约束（刚性约束），也可以不包含

34、 31、下列说法中，不正确的是(C) A. 图是反映对象之间关系的一种工具B. 图的基本要素是点和点之间的连线C. 无向图是由点及弧所构成的D. 图中的点代表研究的对象32、一个含有圈的5个点的连通图的线数（ B） A至少为4B至少为5C等于5D至多为5 33、设树 M 是图 N 的最小支撑树，则下列叙述错误的是（ C ）A. M 中必不含圈 B. M 是连通的C. N 不一定连通 D. M 可能并不唯一34、一个图有5个点，条边。这个图一定是( C )A连通图 B树C含圈的图D不连通图35、下列叙述错误的是 (C)A. 树的点数为线数加一B. 树的任意两点之间只有一条路C. 图的点数大于线数

35、D. 任何不连通图都不是树36、下列说法中不正确的是 （ D ）A. 对树而言，多一边必形成至少一个圈 B. 对树而言，少任一边，必不再连通C. 任一图中所有点的次之和是边数的两倍D. 任一图中偶点的个数为偶数37、 n个点的不连通图，其边数（ A ）A必然少于n1 B必然等于n1C必然多于n1 D可能多于n138、最短路线是指 ( A)A. 连接起点到终点总长度最短的路线B. 连接所有点总长度最短的路线C. 所有点之间长度最短的路线D. 从起点出发经过各点到终点总长度最短的路线补：是否成立“若原问题有唯一最优解，则对偶问题也有唯一最优解”。请证明。答：不成立，见下面两例。1、有惟一可行解也是最优解其对偶单纯形有无限多个可行解同时是最优解。最优值都为0。2、有无限多个最优解在上其对偶单纯形只有唯一最优解。最优值都为1。另：当线性规划的原问题存在可行解时，则其对偶问题不一定存在可行解。例如：存在可行解，但其对偶问题由第一个条件知不存在可行解。