运筹学自测题(含答案).doc

运筹学复习题（A）一、单项选择（将唯一正确答案前面的字母填入题后的括号里。正确得 2 分，选错、多选或不选得0 分。共30 分）1、在线性规划模型中，没有非负约束的变量称为 （C ）A 多余变量 B 松弛变量 C 自由变量 D 人工变量2、约束条件为AX=b，X0 的线性规划问题的可行解集是 （B ）A 补集 B 凸集 C 交集 D 凹集3、线性规划问题若有最优解，则一定可以在可行域的 （C ）上达到。A 内点 B 外点 C 极点 D 几何点4、对偶问题的对偶是 （D ）A 基本问题 B 解的问题 C 其它问题 D 原问题5、若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的 （C ）A 值 B 个数 C 机会费用 D 检验数6、若运输问题已求得最优解，此时所求出的检验数一定是全部 （ A）A 大于或等于零 B 大于零 C 小于零 D 小于或等于零7、设V 是一个有n 个顶点的非空集合，V=v1，v2，vn，E 是一个有m条边的集合，E=e1，e2，em，E 中任意一条边e 是V 的一个无序元素对u，v，（uv），则称V 和E 这两个集合组成了一个 （D ）A 有向树 B 有向图 C 完备图 D 无向图8、若开链Q 中顶点都不相同，则称Q 为 （B ）A 基本链 B 初等链 C 简单链 D 饱和链9、若图G 中没有平行边，则称图G 为 （A ）A 简单图 B 完备图 C 基本图 D 欧拉图11、若Q 为f 饱和链，则链中至少有一条后向边为f （B ）A 正边 B 零边 C 邻边 D 对边12、若f 是G 的一个流，K 为G 的一个割，且Valf=CapK，则K 一定是 （A ）A 最小割 B 最大割 C 最小流 D 最大流13、对max 型整数规划，若最优非整数解对应的目标函数值为Zc，最优整数解对应的目标值为Zd，那么一定有 (D)A Zc Zd B Zc =Zd C Zc Zd D Zc Zd14、若原问题中xI 为自由变量，那么对偶问题中的第i 个约束一定为 （ A）A 等式约束 B “”型约束 C “”约束 D 无法确定15、若f*为满足下列条件的流：Valf*=maxValf |f 为G 的一个流，则称f*为G的 （C ）A 最小值 B 最大值 C 最大流 D 最小流二、多项选择题（每题至少有一个答案是正确的。选对得2 分；多选、少选或不选得0 分。共10 分）1、就课本范围内，解有“”型约束方程线性规划问题的方法有 （ABE ）A 大M 法 B 两阶段法 C 标号法 D 统筹法 E 对偶单纯型法2、线性规划问题的一般模型中可以出现下面几种约束 （ ABC）A = B C D E 3、线性规划问题的主要特征有 （ABCD ）A 目标是线性的 B 约束是线性的 C 求目标最大值 D 求目标最小值E 非线性4、图解法求解线性规划问题的主要过程有 （ABCE ）A 画出可行域 B 求出顶点坐标 C 求最优目标值D 选基本解 E 选最优解5、就课本内容，求解0-1 规划常用的方法有 （AB ）A 全枚举法 B 隐枚举法 C 单纯型法 D 位势法 E 差值法三、简答题（每道题 5 分。共20 分）1、何谓线性规划问题的基础解？何谓基础可行解？解：设B为A中的一个基，令Ax=b，中所有的非基变量（n-m个）为0，得出的解x，称为是B的基础解。满足变量非负条件（1-6）的基础解称为基础可行解。2、当线性规划数学模型中引用人工变量数时，分别采用哪两种方法迭代出基变量？在何种情况下采用？在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加入的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解。对于无初始可行解的问题可用大M法求解。方法：化为标准型的同时，将以及=的约束条件中，加入人工变量(虚拟变量)，将目标函数中虚拟变量的稀疏设定为M。但是大M法如在计算机上运作，M就只能用很大的数来代替，这样可能会出现错误。此时需要两阶段法求解。3、什么是线性规划问题的灵敏度分析？线性规划模型的确定是以 为已知常数作为基础的，但在实际问题中，这些数据本身不仅很难准确得到，而且往往还要受到诸如市场价格波动，资源供应量变化，企业的技术改造的因素的影响，因此，很自然地要提出这样的问题，当这些数据有一个或多个发生变化时，对已找到的最优解或最优基会产生怎样的影响；或者说这些数据在什么范围内变化，已找到的最优解或最优基不变；以及在原最优解或最优基不在是最优基时，如何用最简单的方法求出新的最优解或最优基。这就是线性规划问题的灵敏度分析。4、什么是整数规划？并写出其数学模型？四、计算题 （共40 分）1、（6 分）化为标准型解：令Z=- Z，x1=- x1, x3= x4- x5,其中x4 0，x50，则问题的标准形式为：max Z=-2x1+x2-2x4+2x5x1+x2+x4-x5 =4s.t x1+x2-x4+x5+x6=6x1,x2,x4,x5,x602、（10 分）某厂生产甲、乙、丙三种产品，已知有关数据如下表所示：求使该厂获利最大的生产计划。解：设生产甲、乙、丙三种产品的数量各为x1，x2，x3，依题意得，max Z=4x1+x2+5x36x1+3x2+5x345s.t 3x1+4x2+5x330x1,x2,x30对该方程求解得， x1=5.3x2=0 x3=5.3所以，最优生产计划为生产甲、丙各5.3公斤，不生产乙产品。3、（8 分）目标函数为max Z =28x4+x5+2x6，约束形式为“”，且x1，x2，x3 为松弛变量,表中的解代入目标函数中得Z=14，求出ag 的值，并判断是否最优解解：由图表可知，表中的解为x4=0,x5=0,x6=a。由题意，表中的解带入目标函数得Z=14,可得max Z =28x0+0+2xa=14解之得，a=7.另由图表知，最终的基向量为x6,x2,x4.故c=g=0,d=1,e=0.因x1,x2,x3是虚拟变量，故计算可得b=-6，f=1/3.将所求得的值带入表格中，验证可得，x4=0,x5=0,x6=7是线性规划的最优解。4、（7 分）根据所给的表和一组解判断是否最优解，若不是，请求出最优解。（x13, x14, x21, x22, x32, x34）=（5，2，3，1，5，4）解：该解不是最优解。下面运用最小元素法求解。销地产地B1B2B3B4产量A13