《管理运筹学》复习题及参考答案
第一章运筹学概念
一、填空题
1.运筹学的主要研究对象是各种有组织系统的管理问题,经营活动。
2.运筹学的核心主要是运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。
3.模型是一件实际事物或现实情况的代表或抽象。
4通常对问题中变量值的限制称为约束条件,它可以表示成一个等式或不等式的集合。5.运筹学研究和解决问题的基础是最优化技术,并强调系统整体优化功能。运筹学研究和解决问题的效果具有连续性。
6.运筹学用系统的观点研究功能之间的关系。
7.运筹学研究和解决问题的优势是应用各学科交叉的方法,具有典型综合应用特性。
|
8.运筹学的发展趋势是进一步依赖于_计算机的应用和发展。
9.运筹学解决问题时首先要观察待决策问题所处的环境。
10.用运筹学分析与解决问题,是一个科学决策的过程。
11.运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。
12.运筹学中所使用的模型是数学模型。用运筹学解决问题的核心是建立数学模型,并对模型求解。
13用运筹学解决问题时,要分析,定议待决策的问题。
14.运筹学的系统特征之一是用系统的观点研究功能关系。
15.数学模型中,“s·t”表示约束。
16.建立数学模型时,需要回答的问题有性能的客观量度,可控制因素,不可控因素。17.运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。
[
18. 1940年8月,英国管理部门成立了一个跨学科的11人的运筹学小组,该小组简称为OR。
二、单选题
1.建立数学模型时,考虑可以由决策者控制的因素是(A )
A.销售数量B.销售价格C.顾客的需求D.竞争价格
2.我们可以通过(C )来验证模型最优解。
A.观察B.应用C.实验D.调查
3.建立运筹学模型的过程不包括(A )阶段。
A.观察环境B.数据分析C.模型设计D.模型实施
4.建立模型的一个基本理由是去揭晓那些重要的或有关的( B )
A数量B变量 C 约束条件 D 目标函数
、
5.模型中要求变量取值(D )
A可正B可负C非正D非负
6.运筹学研究和解决问题的效果具有( A )
A 连续性
B 整体性
C 阶段性
D 再生性
7.运筹学运用数学方法分析与解决问题,以达到系统的最优目标。可以说这个过程是一个(C)
A解决问题过程B分析问题过程C科学决策过程D前期预策过程8.从趋势上看,运筹学的进一步发展依赖于一些外部条件及手段,其中最主要的是( C )
A数理统计B概率论C计算机D管理科学
9.用运筹学解决问题时,要对问题进行(B )
A 分析与考察
B 分析和定义
C 分析和判断
D 分析和实验
/
三、多选
1模型中目标可能为(ABCDE )
A输入最少B输出最大 C 成本最小D收益最大E时间最短
2运筹学的主要分支包括(ABDE )
A图论B线性规划 C 非线性规划 D 整数规划E目标规划四、简答
1.运筹学的计划法包括的步骤。答:观察、建立可选择的解、用实验选择最优解、确
定实际问题
2.运筹学分析与解决问题一般要经过哪些步骤答:一、观察待决策问题所处的环境二、分析和定义待决策的问题三、拟订模型四、选择输入数据五、求解并验证解的合理性六、实施最优解
3.运筹学的数学模型有哪些优缺点答:优点:(1).通过模型可以为所要考虑的问题提供一个参考轮廓,指出不能直接看出的结果。(2).花节省时间和费用。(3).模型使人们可以根据过去和现在的信息进行预测,可用于教育训练,训练人们看到他们决策的结果,而不必作出实际的决策。(4).数学模型有能力揭示一个问题的抽象概念,从而能更简明地揭示出问题的本质。(5).数学模型便于利用计算机处理一个模型的主要变量和因素,并易于了解一个变量对其他变量的影响。模型的缺点(1).数学模型的缺点之一是模型可能过分简化,因而不能正确反映实际情况。(2).模型受设计人员的水平的限制,模型无法超越设计人员对问题的理解。(3).创造模型有时需要付出较高的代价。
4.运筹学的系统特征是什么答:运筹学的系统特征可以概括为以下四点:一、用系统的观点研究功能关系二、应用各学科交叉的方法三、采用计划方法四、为进一步研究揭露新问题
:
5、线性规划数学模型具备哪几个要素答:(1).求一组决策变量x i或x ij的值(i =1,2,…m j=1,2…n)使目标函数达到极大或极小;(2).表示约束条件的数学式都是线性等式或不等式;(3).表示问题最优化指标的目标函数都是决策变量的线性函数
第二章线性规划的基本概念
一、填空题
1.线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2.图解法适用于含有两个变量的线性规划问题。
3.线性规划问题的可行解是指满足所有约束条件的解。
4.在线性规划问题的基本解中,所有的非基变量等于零。
5.在线性规划问题中,基可行解的非零分量所对应的列向量线性无关
6.若线性规划问题有最优解,则最优解一定可以在可行域的顶点(极点)达到。
7.线性规划问题有可行解,则必有基可行解。
·
8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其基可行解_的集合中进行搜索即可得到最优解。
9.满足非负条件的基本解称为基本可行解。
10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰数量在目标函数中的系数为零。
11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入松弛变量。12.线性规划模型包括决策(可控)变量,约束条件,目标函数三个要素。
13.线性规划问题可分为目标函数求极大值和极小_值两类。
14.线性规划问题的标准形式中,约束条件取等式,目标函数求极大值,而所有变量必须非负。
15.线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解
16.在用图解法求解线性规划问题时,如果取得极值的等值线与可行域的一段边界重合,则这段边界上的一切点都是最优解。
17.求解线性规划问题可能的结果有无解,有唯一最优解,有无穷多个最优解。
-
18.如果某个约束条件是“≤”情形,若化为标准形式,需要引入一松弛变量。
19.如果某个变量X j为自由变量,则应引进两个非负变量X j′,X j〞,同时令X j=X j′-X j。
20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。
21.. P5))线性规划一般表达式中,a ij表示该元素位置在i行j列。
二、单选题
1.如果一个线性规划问题有n个变量,m个约束方程(m A.m个B.n个C.C n m D.C m n个 2.下列图形中阴影部分构成的集合是凸集的是A 3.线性规划模型不包括下列_ D要素。 % A.目标函数B.约束条件C.决策变量D.状态变量4.线性规划模型中增加一个约束条件,可行域的范围一般将_B_。 A.增大B.缩小C.不变D.不定 5.若针对实际问题建立的线性规划模型的解是无界的,不可能的原因是B__。 A.出现矛盾的条件B.缺乏必要的条件C.有多余的条件D.有相同的条件 6.在下列线性规划问题的基本解中,属于基可行解的是D A.(一1,0,O)T B.(1,0,3,0)T C.(一4,0,0,3)T D.(0,一1,0,5)T 7.关于线性规划模型的可行域,下面_B_的叙述正确。 A.可行域内必有无穷多个点B.可行域必有界C.可行域内必然包括原点D.可行域必是凸的 8.下列关于可行解,基本解,基可行解的说法错误的是_D__. 。 A.可行解中包含基可行解B.可行解与基本解之间无交集 C.线性规划问题有可行解必有基可行解D.满足非负约束条件的基本解为基可行解 9.线性规划问题有可行解,则 A A 必有基可行解 B 必有唯一最优解 C 无基可行解D无唯一最优解 10.线性规划问题有可行解且凸多边形无界,这时C A没有无界解 B 没有可行解 C 有无界解 D 有有限最优解11.若目标函数为求max,一个基可行解比另一个基可行解更好的标志是 A A使Z更大 B 使Z更小 C 绝对值更大 D Z绝对值更小 12.如果线性规划问题有可行解,那么该解必须满足 D A 所有约束条件 B 变量取值非负 C 所有等式要求 D 所有不等式要求 ^ 13.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在D集合中进行搜索即可得到最优解。 A 基 B 基本解 C 基可行解 D 可行域 14.线性规划问题是针对D求极值问题. A约束B决策变量 C 秩D目标函数 15如果第K个约束条件是“≤”情形,若化为标准形式,需要B A左边增加一个变量B右边增加一个变量C左边减去一个变量D右边减去一个变量 16.若某个b k≤0, 化为标准形式时原不等式D A 不变 B 左端乘负1 C 右端乘负1 D 两边乘负1 17.为化为标准形式而引入的松弛变量在目标函数中的系数应为A A 0 B 1 C 2 D 3 ? 12.若线性规划问题没有可行解,可行解集是空集,则此问题 B A 没有无穷多最优解 B 没有最优解 C 有无界解 D 有无界解 三、多选题 1.在线性规划问题的标准形式中,不可能存在的变量是D . A.可控变量B.松驰变量c.剩余变量D.人工变量 2.下列选项中符合线性规划模型标准形式要求的有BCD A.目标函数求极小值B.右端常数非负C.变量非负D.约束条件为等式E.约束条件为“≤”的不等式 3.某线性规划问题,n个变量,m个约束方程,系数矩阵的秩为m(m A.基可行解的非零分量的个数不大于mB.基本解的个数不会超过C m n个C.该问题不会出现退化现象D.基可行解的个数不超过基本解的个数E.该问题的基是一个m×m阶方阵 4.若线性规划问题的可行域是无界的,则该问题可能ABCD ! A.无有限最优解B.有有限最优解C.有唯一最优解D.有无穷多个最优解E.有有限多个最优解 5.判断下列数学模型,哪些为线性规划模型(模型中a.b.c为常数;θ为可取某一常数值 的参变量,x,Y为变量) ACDE 6.下列模型中,属于线性规划问题的标准形式的是ACD 7.下列说法错误的有_ABD_。 A.基本解是大于零的解B.极点与基解一一对应 C.线性规划问题的最优解是唯一的D.满足约束条件的解就是线性规划的可行解 & 8.在线性规划的一般表达式中,变量x ij为ABE A 大于等于0 B 小于等于0 C 大于0 D 小于0 E 等于0 9.在线性规划的一般表达式中,线性约束的表现有CDE A < B > C ≤ D ≥ E = 10.若某线性规划问题有无界解,应满足的条件有AD A P k<0 B非基变量检验数为零C基变量中没有人工变量Dδj>O E所有δj≤0 11.在线性规划问题中a23表示AE A i =2 B i =3 C i =5 D j=2 E j=3 43.线性规划问题若有最优解,则最优解AD A定在其可行域顶点达到B只有一个C会有无穷多个 D 唯一或无穷多个E 其值为0 … 42.线性规划模型包括的要素有CDE A.目标函数B.约束条件C.决策变量 D 状态变量 E 环境变量 四、名词 1基:在线性规划问题中,约束方程组的系数矩阵A的任意一个m×m阶的非奇异子方阵B,称为线性规划问题的一个基。 2、线性规划问题:就是求一个线性目标函数在一组线性约束条件下的极值问题。 3 .可行解:在线性规划问题中,凡满足所有约束条件的解称为线性规划问题可行解 4、行域:线性规划问题的可行解集合。 5、本解:在线性约束方程组中,对于选定的基B令所有的非基变量等于零,得到的解,称为线性规划问题的一个基本解。 6.、图解法:对于只有两个变量的线性规划问题,可以用在平面上作图的方法来求解,这种方法称为图解法。 7、本可行解:在线性规划问题中,满足非负约束条件的基本解称为基本可行解。 ! 8、模型是一件实际事物或实际情况的代表或抽象,它根据因果显示出行动与反映的关系和客观事物的内在联系。 四、把下列线性规划问题化成标准形式: 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品,每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量,单位产品的利润如下表所示: 根据客户订货,三种产品的最低月需要量分别为200,250和100件,最大月销售量分别为250,280和120件。月销售分别为250,280和120件。问如何安排生产计划,使总利润最大。 】 2、某建筑工地有一批长度为10米的相同型号的钢筋,今要截成长度为3米的钢筋90根,长度为4米的钢筋60根,问怎样下料,才能使所使用的原材料最省 1.某运输公司在春运期间需要24小时昼夜加班工作,需要的人员数量如下表所示: 起运时间服务员数 2—6 6—10 10一14 14—18 " 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时,且在时段开始时上班,问如何安排,使得既满足以上要求,又使上班人数最少 ¥ 第三章线性规划的基本方法 一、填空题 1.线性规划的代数解法主要利用了代数消去法的原理,实现基可行解的转换,寻找最优解。2.标准形线性规划典式的目标函数的矩阵形式是_ maxZ=C B B-1b+(C N-C B B-1N)X N。 3.对于目标函数极大值型的线性规划问题,用单纯型法求解时,当基变量检验数δj_≤_0时,当前解为最优解。 4.用大M法求目标函数为极大值的线性规划问题时,引入的人工变量在目标函数中的系数应为-M。 5.在单纯形迭代中,可以根据最终_表中人工变量不为零判断线性规划问题无解。 6.在线性规划典式中,所有基变量的目标系数为0。 7.当线性规划问题的系数矩阵中不存在现成的可行基时,一般可以加入人工变量构造可行基。 8.在单纯形迭代中,选出基变量时应遵循最小比值θ法则。 - 9.线性规划典式的特点是基为单位矩阵,基变量的目标函数系数为0。 10.对于目标函数求极大值线性规划问题在非基变量的检验数全部δj≤O、问题无界时,问题无解时情况下,单纯形迭代应停止。 11.在单纯形迭代过程中,若有某个δk>0对应的非基变量x k的系数列向量P k_≤0_时,则此问题是无界的。 12.在线性规划问题的典式中,基变量的系数列向量为单位列向量_ 13.对于求极小值而言,人工变量在目标函数中的系数应取-1 14.(单纯形法解基的形成来源共有三种 15.在大M法中,M表示充分大正数。 二、单选题 1.线性规划问题C ¥ 2.在单纯形迭代中,出基变量在紧接着的下一次迭代中B立即进入基底。 A.会B.不会C.有可能D.不一定 3.在单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中B。 A.不影响解的可行性B.至少有一个基变量的值为负C.找不到出基变量D.找不到进基变量 4.用单纯形法求解极大化线性规划问题中,若某非基变量检验数为零,而其他非基变量检验数全部<0,则说明本问题B 。 A.有惟一最优解B.有多重最优解C.无界D.无解 5.线性规划问题maxZ=CX,AX=b,X≥0中,选定基B,变量X k的系数列向量为P k,则在关于基B的典式中,X k的系数列向量为_ D A.BP K B.B T P K C.P K B D.B-1P K 6.下列说法错误的是B A.— B.图解法与单纯形法从几何理解上是一致的B.在单纯形迭代中,进基变量可以任选 C.在单纯形迭代中,出基变量必须按最小比值法则选取D.人工变量离开基底后,不会再进基 7.单纯形法当中,入基变量的确定应选择检验数 C A绝对值最大B绝对值最小 C 正值最大 D 负值最小 8.在单纯形表的终表中,若若非基变量的检验数有0,那么最优解A A 不存在 B 唯一 C 无穷多 D 无穷大 9.若在单纯形法迭代中,有两个Q值相等,当分别取这两个不同的变量为入基变量时,获得的结果将是 C A 先优后劣 B 先劣后优 C 相同 D 会随目标函数而改变 10.若某个约束方程中含有系数列向量为单位向量的变量,则该约束方程不必再引入 C A 松弛变量 B 剩余变量 C 人工变量 D 自由变量 , 11.在线性规划问题的典式中,基变量的系数列向量为D A 单位阵B非单位阵C单位行向量D单位列向量 12.在约束方程中引入人工变量的目的是D A 体现变量的多样性 B 变不等式为等式 C 使目标函数为最优 D 形成一个单位 阵 13.出基变量的含义是D A 该变量取值不变B该变量取值增大 C 由0值上升为某值D由某值下降为0 14.在我们所使用的教材中对单纯形目标函数的讨论都是针对 B 情况而言的。 A min B max C min + max D min ,max任选 15.求目标函数为极大的线性规划问题时,若全部非基变量的检验数≤O,且基变量中有人工变量时该问题有 B A无界解B无可行解 C 唯一最优解D无穷多最优解 ~ 三、多选题 1.对取值无约束的变量x j。通常令x j=x j’- x”j,其中x j’≥0,x j”≥0,在用单纯形法求得的最优解中,可能出现的是ABC 2.线性规划问题maxZ=x1+CX2 其中4≤c≤6,一1≤a≤3,10≤b≤12,则当_ BC时,该问题的最优目标函数值分别达到上界或下界。 A.c=6 a=-1 b=10 B.c=6 a=-1 b=12 C.c=4 a=3 b=12 D.c=4 a=3 b=12 E.c=6 a=3 b=12 3.设X(1),X(2)是用单纯形法求得的某一线性规划问题的最优解,则说明ACDE。 A.此问题有无穷多最优解B.该问题是退化问题C.此问题的全部最优解可表示为λX(1)+(1一λ)X(2),其中0≤λ≤1 D.X(1),X(2)是两个基可行解E.X(1),X(2)的基变量个数相同 4.某线性规划问题,含有n个变量,m个约束方程,(m A.该问题的典式不超过C N M个B.基可行解中的基变量的个数为m个C.该问题一定存在可行解D.该问题的基至多有C N M=1个E.该问题有111个基可行解 5.单纯形法中,在进行换基运算时,应ACDE。A.先选取进基变量,再选取出基变量B.先选出基变量,再选进基变量C.进基变量的系数列向量应化为单位向量D.旋转变换时采用的矩阵的初等行变换E.出基变量的选取是根据最小比值法则 ( 6.从一张单纯形表中可以看出的内容有ABCE。A.一个基可行解B.当前解是否为最优解C.线性规划问题是否出现退化D.线性规划问题的最优解E.线性规划问题是否无界 7.单纯形表迭代停止的条件为(AB ) A 所有δj均小于等于0 B 所有δj均小于等于0且有a ik≤0 C 所有a ik>0 D 所有b i≤0 8.下列解中可能成为最优解的有(ABCDE ) A 基可行解 B 迭代一次的改进解C迭代两次的改进解D迭代三次的改进解 E 所有检验数均小于等于0且解中无人工变量 9、若某线性规划问题有无穷多最优解,应满足的条件有(BCE ) A P k<P k0 B非基变量检验数为零C基变量中没有人工变量Dδj<O E所有δ≤0 j 10.下列解中可能成为最优解的有(ABCDE ) A基可行解B迭代一次的改进解C迭代两次的改进解 ( D迭代三次的改进解E所有检验数均小于等于0且解中无人工变量 四、名词、简答 1、人造初始可行基:当我们无法从一个标准的线性规划问题中找到一个m阶单位矩阵时,通常在约束方程中引入人工变量,而在系数矩阵中凑成一个m阶单位矩阵,进而形成的一个初始可行基称为人造初始可行基。 2、单纯形法解题的基本思路可行域的一个基本可行解开始,转移到另一个基本可行解,并且使目标函数值逐步得到改善,直到最后球场最优解或判定原问题无解。 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。 ! 六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2,约束形式为“≤”,X Z=10 X4 X l X2" X3 —10b-1f g O11/5 X32! C X l a d e01 | (1)求表中a~g的值(2)表中给出的解是否为最优解 (1)a=2 b=0 c=0 d=1 e=4/5 f=0 g=-5 (2)表中给出的解为最优解 第四章线性规划的对偶理论 一、填空题 1.线性规划问题具有对偶性,即对于任何一个求最大值的线性规划问题,都有一个求最小值/极小值的线性规划问题与之对应,反之亦然。 2.在一对对偶问题中,原问题的约束条件的右端常数是对偶问题的目标函数系数。3.如果原问题的某个变量无约束,则对偶问题中对应的约束条件应为等式_。 4.对偶问题的对偶问题是原问题_。 5.若原问题可行,但目标函数无界,则对偶问题不可行。 6.若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变),当该种资源增加3个单位时。相应的目标函数值将增加3k 。 ? 7.线性规划问题的最优基为B,基变量的目标系数为C B,则其对偶问题的最优解Y﹡= C B B -1。 8.若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解,则有CX﹡= Y﹡b。 9.若X、Y分别是线性规划的原问题和对偶问题的可行解,则有CX≤Yb。 10.若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解,则有CX﹡=Y*b。 11.设线性规划的原问题为maxZ=CX,Ax≤b,X≥0,则其对偶问题为min=Yb YA≥c Y≥0_。 12.影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 13.线性规划的原问题的约束条件系数矩阵为A,则其对偶问题的约束条件系数矩阵为 A T。 14.在对偶单纯形法迭代中,若某b i<0,且所有的a ij≥0(j=1,2,…n),则原问题_无解。 二、单选题 1.线性规划原问题的目标函数为求极小值型,若其某个变量小于等于0,则其对偶问题约束条件为A形式。 . A.“≥” B.“≤”C,“>” D.“=” 2.设X、Y分别是标准形式的原问题与对偶问题的可行解,则C 。 3.对偶单纯形法的迭代是从_ A_开始的。 A.正则解B.最优解C.可行解D.基本解 4.如果z。是某标准型线性规划问题的最优目标函数值,则其对偶问题的最优目标函数值w ﹡A。 A.W﹡=Z﹡B.W﹡≠Z﹡C.W﹡≤Z﹡D.W﹡≥Z﹡ 5.如果某种资源的影子价格大于其市场价格,则说明_ B A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源,开僻新的生产途径 三、多选题 ; 1.在一对对偶问题中,可能存在的情况是ABC。 A.一个问题有可行解,另一个问题无可行解B.两个问题都有可行解 C.两个问题都无可行解D.一个问题无界,另一个问题可行 2.下列说法错误的是B 。 A.任何线性规划问题都有一个与之对应的对偶问题B.对偶问题无可行解时,其原问题的目标函数无界。C.若原问题为maxZ=CX,AX≤b,X≥0,则对偶问题为minW=Yb,YA≥C,Y≥0。D.若原问题有可行解,但目标函数无界,其对偶问题无可行解。 3.如线性规划的原问题为求极大值型,则下列关于原问题与对偶问题的关系中正确的是BCDE。 A原问题的约束条件“≥”,对应的对偶变量“≥0”B原问题的约束条件为“=”,对应的对偶变量为自由变量C.原问题的变量“≥0”,对应的对偶约束“≥” D.原问题的变量“≤O”对应的对偶约束“≤”E.原问题的变量无符号限制,对应的对偶约束“=” 4.一对互为对偶的问题存在最优解,则在其最优点处有BD A.若某个变量取值为0,则对应的对偶约束为严格的不等式B.若某个变量取值为正,则相应的对偶约束必为等式C.若某个约束为等式,则相应的对偶变取值为正D.若某个约束为严格的不等式,则相应的对偶变量取值为0 E.若某个约束为等式,则相应的对偶变量取值为0 5.下列有关对偶单纯形法的说法正确的是ABCD。 | A.在迭代过程中应先选出基变量,再选进基变量B.当迭代中得到的解满足原始可行性条件时,即得到最优解C.初始单纯形表中填列的是一个正则解D.初始解不需要满足可行性E.初始解必须是可行的。 6.根据对偶理论,在求解线性规划的原问题时,可以得到以下结论ACD。 A.对偶问题的解B.市场上的稀缺情况C.影子价格D.资源的购销决策E.资源的市场价格 7.在下列线性规划问题中,CE采用求其对偶问题的方法,单纯形迭代的步骤一般会减少。 四、名词、简答题 1、对偶可行基:凡满足条件δ=C-C B B-1A≤0的基B称为对偶可行基。 2、.对称的对偶问题:设原始线性规划问题为maxZ=CX AX≤b X ≥0 称线性规划问题minW=Yb YA≥C 】 Y≥0 为其对偶问题。又称它们为一对对称的对偶问题。 3、影子价格:对偶变量Y i表示与原问题的第i个约束条件相对应的资源的影子价格,在数量上表现为,当该约束条件的右端常数增加一个单位时(假设原问题的最优解不变),原问题目标函数最优值增加的数量。 4.影子价格在经济管理中的作用。(1)指出企业内部挖潜的方向;(2)为资源的购销决策提供依据;(3)分析现有产品价格变动时资源紧缺情况的影响;(4)分析资源节约所带来的收益;(5)决定某项新产品是否应投产。 5.线性规划对偶问题可以采用哪些方法求解(1)用单纯形法解对偶问题;(2)由原问题的最优单纯形表得到;(3)由原问题的最优解利用互补松弛定理求得;(4)由Y*=C B B-1求得,其中B为原问题的最优基 6、一对对偶问题可能出现的情形:1.原问题和对偶问题都有最优解,且二者相等;2.一个问题具有无界解,则另一个问题具有无可行解;3.原问题和对偶问题都无可行解。 五、写出下列线性规划问题的对偶问题 1.minZ=2x1+2x2+4x3 六、已知线性规划问题 ~ 应用对偶理论证明该问题最优解的目标函数值不大于25 七、已知线性规划问题 maxZ=2x1+x2+5x3+6x4 其对偶问题的最优解为Y l﹡=4,Y2﹡=1,试应用对偶问题的性质求原问题的最优解。 七、用对偶单纯形法求解下列线性规划问题: \ 八、已知线性规划问题 (1)写出其对偶问题(2)已知原问题最优解为X﹡=(2,2,4,0)T,试根据对偶理论,直接 求出对偶问题的最优解。 W* = 16 第五章线性规划的灵敏度分析 一、填空题 1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 2、在线性规划的灵敏度分析中,我们主要用到的性质是_可行性,正则性。 3.在灵敏度分析中,某个非基变量的目标系数的改变,将引起该非基变量自身的检验数的变化。 4.如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围,则此基变量应出基。 《 5.约束常数b;的变化,不会引起解的正则性的变化。 6.在某线性规划问题中,已知某资源的影子价格为Y1,相应的约束常数b1,在灵敏度容许变动范围内发生Δb1的变化,则新的最优解对应的最优目标函数值是Z*+y i△b (设原最优目标函数值为Z﹡) 7.若某约束常数b i的变化超过其容许变动范围,为求得新的最优解,需在原最优单纯形表的基础上运用对偶单纯形法求解。 8.已知线性规划问题,最优基为B,目标系数为C B,若新增变量x t,目标系数为c t,系数列向量为Pt,则当C t≤C B B-1P t时,x t不能进入基底。 9.如果线性规划的原问题增加一个约束条件,相当于其对偶问题增加一个变量。 10、若某线性规划问题增加一个新的约束条件,在其最优单纯形表中将表现为增加一行,一列。 11.线性规划灵敏度分析应在最优单纯形表的基础上,分析系数变化对最优解产生的影响12.在某生产规划问题的线性规划模型中,变量x j的目标系数C j代表该变量所对应的产品的利润,则当某一非基变量的目标系数发生增大变化时,其有可能进入基底。 二、单选题 1.若线性规划问题最优基中某个基变量的目标系数发生变化,则C。 ] A.该基变量的检验数发生变化B.其他基变量的检验数发生变化C.所有非基变量的检验数发生变化D.所有变量的检验数都发生变化 2.线性规划灵敏度分析的主要功能是分析线性规划参数变化对D的影响。 A.正则性B.可行性C.可行解D.最优解 3.在线性规划的各项敏感性分析中,一定会引起最优目标函数值发生变化的是B。 A.目标系数c j的变化B.约束常数项b i变化C.增加新的变量D.增加新约束 4.在线性规划问题的各种灵敏度分析中,B_的变化不能引起最优解的正则性变化。 A.目标系数B.约束常数C.技术系数D.增加新的变量E.增加新的约束条件5.对于标准型的线性规划问题,下列说法错误的是C A.在新增变量的灵敏度分析中,若新变量可以进入基底,则目标函数将会得到进一步改善。B.在增加新约束条件的灵敏度分析中,新的最优目标函数值不可能增加。C.当某个约束常数b k增加时,目标函数值一定增加。D.某基变量的目标系数增大,目标函数值将得到改善 6.灵敏度分析研究的是线性规划模型中最优解和C 之间的变化和影响。 ] A 基 B 松弛变量C原始数据 D 条件系数 三、多选题 1.如果线性规划中的c j、b i同时发生变化,可能对原最优解产生的影响是_ ABCD. A.正则性不满足,可行性满足B.正则性满足,可行性不满足C.正则性与可行性都满足D.正则性与可行性都不满足E.可行性和正则性中只可能有一个受影响 2.在灵敏度分析中,我们可以直接从最优单纯形表中获得的有效信息有ABCE。 A.最优基B的逆B-1B.最优解与最优目标函数值C.各变量的检验数D.对偶问题的解E.各列向量 3.线性规划问题的各项系数发生变化,下列不能引起最优解的可行性变化的是ABC_。A.非基变量的目标系数变化B.基变量的目标系数变化C.增加新的变量D,增加新的 约束条件 4.下列说法错误的是ACD A.若最优解的可行性满足B-1b≥0,则最优解不发生变化B.目标系数c j发生变化时,解的正则性将受到影响C.某个变量x j的目标系数c j发生变化,只会影响到该变量的检验数的变化D.某个变量x j的目标系数c j发生变化,会影响到所有变量的检验数发生变化。 ; 四、名词、简答题 1.灵敏度分析:研究线性规划模型的原始数据变化对最优解产生的影响 2.线性规划问题灵敏度分析的意义。(1)预先确定保持现有生产规划条件下,单位产品利润的可变范围;(2)当资源限制量发生变化时,确定新的生产方案;(3)确定某种新产品的投产在经济上是否有利;(4)考察建模时忽略的约束对问题的影响程度;(5)当产品的设计工艺改变时,原最优方案是否需要调整。 四、某工厂在计划期内要安排生产I、Ⅱ两种产品。已知生产单位产品所需的设备台时及A、B \ 该工厂每生产一件产品I可获利2百元,每生产一件产品Ⅱ可获利3百元。 (1)单纯形迭代的初始表及最终表分别如下表I、Ⅱ所示: x5 (1)使工厂获利最多的产品混合生产方案:生产I产品4件,生产II产品2件,设备台时与原材料A全部用完,原材料B剩余4kg,此时,获利14百元。(2)X*=(4,3,2,0,o)T z*=17 (3)0≤C2≤4 (4)应生产产品Ⅲ,产量为2。 ) 五、给出线性规划问题 用单纯形表求解得单纯形表如下,试分析下列各种条件变化下最优解(基)的变化: x l x2x3x4x5 x B -Z-80 0 -3 -5 -1 x l x2 1 ) 2 1 0 -1 4 -1 0 1 2 -1 1 (1)分别确定目标函数中变量X1和X2的系数C1,c2在什么范围内变动时最优解不变;(2)目标函数中变量X3的系数变为6;(3)增添新的约束X1+2x2+x3≤4 解:(1)3/4≤C1≤3 2≤C2≤8 (2)X*=(2,0,1,0,0,0)T Z*=10 (3)X*=(2,1,0,0,1,0)T Z*=7 (4)X*=(0,2,0,0,0,1/3)T Z*=25/3 第六章物资调运规划运输问题 一、填空题 1.物资调运问题中,有m个供应地,A l,A2…,A m,A j的供应量为a i(i=1,2…,m),n个需求地B1,B2,…B n,B的需求量为b j(j=1,2,…,n),则供需平衡条件为∑ = m i i a 1 =∑ = n j i b 1 2.物资调运方案的最优性判别准则是:当全部检验数非负时,当前的方案一定是最优方案。 — 3.可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n-1个(设问题中含有m个供应地和n个需求地) 4.若调运方案中的某一空格的检验数为1,则在该空格的闭回路上调整单位运置而使运费增加1。 5.调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。6.按照表上作业法给出的初始调运方案,从每一空格出发可以找到且仅能找到_1条闭回路 7.在运输问题中,单位运价为C ij位势分别用u i,V j表示,则在基变量处有c ij C ij=u i+V j 。 8、供大于求的、供不应求的不平衡运输问题,分别是指∑ = m i i a 1 _>∑ = n j i b 1 的运输问题、∑ = m i i a 1 _<∑ = n j i b 1 的运输问题。 10.在表上作业法所得到的调运方案中,从某空格出发的闭回路的转角点所对应的变量必为基变量。 11.在某运输问题的调运方案中,点(2,2)的检验数为负值,(调运方案为表所示)则相应 的调整量应为300_ 12.2的含义是该检验数所在格单位调整量。 13.运输问题的初始方案中的基变量取值为正。 ^ 14表上作业法中,每一次调整1个“入基变量”。 15.在编制初始方案调运方案及调整中,如出现退化,则某一个或多个点处应填入数字0 16运输问题的模型中,含有的方程个数为n+M个。 17表上作业法中,每一次调整,“出基变量”的个数为1个。 18给出初始调运方案的方法共有三种。 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)中给出的调运方案能否作为表上作业法求解时的初始解,为什么 (c) B l B2B3B4产量 A l65, 11 4211 A2& 5 A3538 7 销量59> 9 (a)可作为初始方案;(b)中填有数字的方格数少于9(产地数+销地数-1),不能作为初始 方案; (c)中存在以非零元素为顶点的闭回路,不能作为初始方案 四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b), 判断给出的调运方案是否为最优如是说明理由;如否。也说明理由。 表(a)产销平衡表及某一调运方案单位运价表 销地 产地B l] B2 B3B4B5B6【 产量 l 302050 A2@ 301040 A3' 10 401060 A4% 20 1131 销量305020403011" 五、给出如下运输问题 运价 产 B1B2B3B4$ 产量 A l5310490 A216< 9 640 A320105770 销量— 30 508040200 (1)应用最小元素法求其初始方案;(2)应用位势法求初始方案的检验数,并检验该方案是否为最优方案 六、用表上作业法求给出的运输问题的最优解 甲¥ 乙 丙丁产量 11067124 - 2 160599 35410; 10 4 销量5246 销 在最优调运方案下的运输费用最小为118。 } 七、名词 1、 平衡运输问题:m 个供应地的供应量等于n 个需求地的总需求量,这样的运输问题称 平衡运输问题。 2、不平衡运输问题:m 个供应地的供应量不等于n 个需求地的总需求量,这样的运输问题称不平衡运输问题。 第七章 整数规划 一、填空题 1.用分枝定界法求极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界。 2.在分枝定界法中,若选X r =4/3进行分支,则构造的约束条件应为X 1≤1,X 1≥2。 3.已知整数规划问题P 0,其相应的松驰问题记为P 0’,若问题P 0’无可行解,则问题P 。无可行解。 4.在0 - 1整数规划中变量的取值可能是_0或1。 5.对于一个有n 项任务需要有n 个人去完成的分配问题,其 解中取值为1的变量数为n 个。 @ 6.分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。 7.若在对某整数规划问题的松驰问题进行求解时,得到最优单纯形表中,由X 。所在行 得X 1+1/7x 3+2/7x 5=13/7,则以X 1行为源行的割平面方程为_6-1X 3-72 X 5≤0_。 8.在用割平面法求解整数规划问题时,要求全部变量必须都为整数。 9.用割平面法求解整数规划问题时,若某个约束条件中有不为整数的系数,则需在该约束两端扩大适当倍数,将全部系数化为整数。 10.求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。 11.求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 12.在应用匈牙利法求解分配问题时,最终求得的分配元应是独立零元素_。 13.分枝定界法一般每次分枝数量为2个. 二、单选题 1.整数规划问题中,变量的取值可能是D 。 、 A .整数 B .0或1 C .大于零的非整数 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 .无穷多个最优解 ! 四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题(每题2分,共20分。) 1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规划问题求解,原问题的目标 函数值等于( )。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是( )。 A.基本解一定是可行解 B.基本可行解的每个分量一定非负 C.若B 是基,则B 一定是可逆 D.非基变量的系数列向量一定是线性相关的 3.在线性规划模型中,没有非负约束的变量称为 ( ) 多余变量 B .松弛变量 C .人工变量 D .自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得( )。 A.多重解 B.无解 C.正则解 D.退化解 5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足 ( )。 A .等式约束 B .“≤”型约束 C .“≥”约束 D .非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y 是( )。 A.多余变量 B.自由变量 C.松弛变量 D.非负变量 7.在运输方案中出现退化现象,是指数字格的数目( )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树T的任意两个顶点间恰好有一条( )。 A.边 B.初等链 C.欧拉圈 D.回路 9.若G 中不存在流f 增流链,则f 为G 的 ( )。 A .最小流 B .最大流 C .最小费用流 D .无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足( ) A.等式约束 B.“≤”型约束 C.“≥”型约束 D.非负约束 二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有 ( ) A .松弛变量 B .剩余变量 C .非负变量 D .非正变量 E .自由变量 2.图解法求解线性规划问题的主要过程有 ( ) A .画出可行域 B .求出顶点坐标 C .求最优目标值 D .选基本解 E .选最优解 3.表上作业法中确定换出变量的过程有 ( ) A .判断检验数是否都非负 B .选最大检验数 C .确定换出变量 D .选最小检验数 E .确定换入变量 4.求解约束条件为“≥”型的线性规划、构造基本矩阵时,可用的变量有 ( ) A .人工变量 B .松弛变量 C. 负变量 D .剩余变量 E .稳态 变量 5.线性规划问题的主要特征有 ( ) 一、 二、 三、 填空题(每小题 分,共 ?分) 、设原??问题为?????? ?≥-=++-≥--≤++++-= ,0,5232 4 7 532min 3213213213213 21无约束x x x x x x x x x x x x x x x Z 则它的标准形和对偶规划问题分别为:________________________ 和 ________________________。 、用分枝定界法求整数规划12 12121121min 5 2 56 30 4,0Z x x x x x x x x x x =---≥-??+≤?? ≤??≥?且为整数 的解时,求得放松问题的解为? = ? ? ? ? ? ?,则可将原问题分成如下两个子问题 与 求解。 、右图的最小支撑图是。 、右边的网络图是标号算法中的图,其中每条弧上的数 表示其容量和流量。该图中得到的可行流的增广链 (-3,1) (2,1) ②5(4) ④ ① 6(6) 6(4) ⑥ (0, ∞) 8(8) 3(2 ) 9(9)(5,1) 为: ,在其上可增的最大流量 为 。 、已知某线性规划问题,最优单纯形表如下 则其最优解为: ,最优值 max Z 。 二、单项选择题(每小题 分,共 分) 、下列表格是对偶单纯形表的是( ? ) 、关于线性规划模型的可行域,叙述正确的为( ) ?、可行域必有界; 、可行域必然包括原点; 、可行域必是凸的; 、可行域内必有无穷多个点。 、在运输问题中如果总需求量大于总供应量,则求解时应( ) ?、虚设一些供应量; ?、虚设一个供应点; 、根据需求短缺量,虚设多个需求点; ?、虚设一个需求点。 、下列规划问题不可用动态规划方法求解的是( ) ?、背包问题; ?、最短路径问题 、线性规化: ???≥≥=++++=0 ,010 34..max 321 3 32211y x x x x t s x c x c x c Z ?、22 min (,)(2)3(1).. 460,0f x y x y s t xy y x y ?=++-?+?≥≥? 、下列关于图的论述正确地是( ) ?、有向图的邻接矩阵是对称矩阵; ?、图?是连通的,当且仅当?中的任意两点之间至少存在一条链; 、任何一个连通图,都存在唯一的最小支撑树; ?、若图),(E V G ''='是图),(E V G =一个支撑子图,则E E V V '=?',。 三、判断题(每小题 分,共 分) ( ) 、若原始问题是利润最大化的生产计划问题,则对偶问题是资源定价问题,对偶问题的最优解称为原始问题中资源的影子价格。影子价格越大说明这种资源越是相对紧缺,影子价格越小说明这种资源相对不紧缺。 ( ) 、对???型整数规划,若其松弛问题最优解对应的目标函数值为??,而其最优整数解对应的目标值为??,那么一定有?? ≤??。 ( ) 、任何一个无圈的图?都是一个树图。 ( ) 、一个可行流满足平衡条件是指:所有中间结点处流出量 流入量,收点流出量 ?? 发点流入量 ?,收点流入量 发点流出量。 ( ) 、恰好有两个悬挂点的树是一条链。 《运筹学》试题样卷(一) 一、判断题(共计10分,每小题1分,对的打√,错的打X ) 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题,若其中一个有最优解, 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解,那么它必有最优解。 4.对偶问题的对偶问题一定是原问题。 5.用单纯形法求解标准形式(求最小值)的线性规划问题时,与0 >j σ对应的变量 都可以被选作换入变量。 6.若线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 10. 任何线性规划问题都存在且有唯一的对偶问题。 二、建立下面问题的线性规划模型(8分) 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日;春夏季4000人日。如劳动力本身用不了时可外出打工,春秋季收入为25元 / 人日,秋冬季收入为20元 / 人日。该农场种植三种作物:大豆、玉米、小麦,并饲养奶牛和鸡。种作物时不需要专门投资,而饲养每头奶牛需投资800元,每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料,并占用人工秋冬季为100人日,春夏季为50人日,年净收入900元 / 每头奶牛。养鸡时不占用土地,需人工为每只鸡秋冬季0.6人日,春夏季为0.3人日,年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡,牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示: 试决定该农场的经营方案,使年净收入为最大。 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表,表中54,x x 为 (1)写出原线性规划问题;(4分) (2)写出原问题的对偶问题;(3分) (3)直接由上表写出对偶问题的最优解。(1分) 四、用单纯形法解下列线性规划问题(16分) 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 (18分) 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示: 问:应如何调运,可使得总运输费最小? 六、灵敏度分析(共8分) 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1.线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2.图解法适用于含有 两个 _ 变量的线性规划问题。 3.线性规划问题的可行解是指满足 所有约束条件_ 的解。 4.在线性规划问题的基本解中,所有的非基变量等于 零 。 5.在线性规划问题中,基本可行解的非零分量所对应的列向量线性 无 关 6.若线性规划问题有最优解,则最优解一定可以在可行域的 顶点_ 达到。 7.若线性规划问题有可行解,则 一定 _ 有基本可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9.满足 非负 _ 条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰变量在目标函数中的系数为 正 。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12.线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13.线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14.线性规划问题的标准形式中,约束条件取 等 _ 式,目标函数求 最大 _值,而所有决策变量必须 非负 。 15.线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解,反之不然 16.在用图解法求解线性规划问题时,如果取得最值的等值线与可行域的一段边界重合,则 _ 最优解不唯一 。 17.求解线性规划问题可能的结果有 唯一最优解,无穷多最优解,无界解,无可行解 。 18.如果某个约束条件是“ ”情形,若化为标准形式,需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量,则应引进两个非负变量X j ′ , X j 〞, 同时令X j = X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 《管理运筹学》复习题及参考答案 第一章运筹学概念 一、填空题 1.运筹学的主要研究对象就是各种有组织系统的管理问题,经营活动。 2.运筹学的核心主要就是运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。 3.模型就是一件实际事物或现实情况的代表或抽象。 4通常对问题中变量值的限制称为约束条件,它可以表示成一个等式或不等式的集合。5.运筹学研究与解决问题的基础就是最优化技术,并强调系统整体优化功能。运筹学研究与解决问题的效果具有连续性。 6.运筹学用系统的观点研究功能之间的关系。 7.运筹学研究与解决问题的优势就是应用各学科交叉的方法,具有典型综合应用特性。 8.运筹学的发展趋势就是进一步依赖于_计算机的应用与发展。 9.运筹学解决问题时首先要观察待决策问题所处的环境。 10.用运筹学分析与解决问题,就是一个科学决策的过程。 11、运筹学的主要目的在于求得一个合理运用人力、物力与财力的最佳方案。 12.运筹学中所使用的模型就是数学模型。用运筹学解决问题的核心就是建立数学模型,并对模型求解。 13用运筹学解决问题时,要分析,定议待决策的问题。 14.运筹学的系统特征之一就是用系统的观点研究功能关系。 15、数学模型中,“s·t”表示约束。 16.建立数学模型时,需要回答的问题有性能的客观量度,可控制因素,不可控因素。 17.运筹学的主要研究对象就是各种有组织系统的管理问题及经营活动。 18、1940年8月,英国管理部门成立了一个跨学科的11人的运筹学小组,该小组简称为OR。 二、单选题 1.建立数学模型时,考虑可以由决策者控制的因素就是( A ) A.销售数量 B.销售价格 C.顾客的需求 D.竞争价格 2.我们可以通过( C )来验证模型最优解。 A.观察 B.应用 C.实验 D.调查 3.建立运筹学模型的过程不包括( A )阶段。 A.观察环境 B.数据分析 C.模型设计 D.模型实施 4、建立模型的一个基本理由就是去揭晓那些重要的或有关的( B ) A数量B变量 C 约束条件 D 目标函数 5、模型中要求变量取值( D ) A可正B可负C非正D非负 6、运筹学研究与解决问题的效果具有( A ) A 连续性 B 整体性 C 阶段性 D 再生性 7、运筹学运用数学方法分析与解决问题,以达到系统的最优目标。可以说这个过程就是一个(C) A解决问题过程B分析问题过程C科学决策过程D前期预策过程8、从趋势上瞧,运筹学的进一步发展依赖于一些外部条件及手段,其中最主要的就是 ( C ) A数理统计B概率论C计算机D管理科学 9、用运筹学解决问题时,要对问题进行( B ) A 分析与考察 B 分析与定义 C 分析与判断 D 分析与实验 三、多选 1模型中目标可能为( ABCDE ) A输入最少B输出最大 C 成本最小D收益最大E时间最短 2运筹学的主要分支包括( ABDE ) A图论B线性规划 C 非线性规划 D 整数规划E目标规划 四、简答 1.运筹学的计划法包括的步骤。答:观察、建立可选择的解、用实验选择最优解、确定实际问题 2.运筹学分析与解决问题一般要经过哪些步骤? 答: 一、观察待决策问题所处的环境 二、分析与定义待决策的问题三、拟订模型四、选择输入数据五、求解并验证解的 四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题(每题2分,共20分。) 1.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性规 划问题求解,原问题的目标函数值等于(C)。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2.下列说法中正确的是(B)。 A.基本解一定是可行解B.基本可行解的每个分量一定非负 C.若B是基,则B一定是可逆D.非基变量的系数列向量一定是线性相关的3.在线性规划模型中,没有非负约束的变量称为( D ) 多余变量B.松弛变量C.人工变量D.自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得 ( A )。 A.多重解B.无解C.正则解D.退化解5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足( D )。 A.等式约束 B.“≤”型约束 C.“≥”约束 D.非负约束 y是( B )。 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i A.多余变量B.自由变量C.松弛变量D.非负变量 7.在运输方案中出现退化现象,是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8.树T的任意两个顶点间恰好有一条(B)。 A.边B.初等链C.欧拉圈D.回路9.若G中不存在流f增流链,则f为G的( B )。 A.最小流 B.最大流 C.最小费用流 D.无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足( D ) A.等式约束B.“≤”型约束C.“≥”型约束D.非负约束二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有() A.松弛变量 B.剩余变量 C.非负变量 D.非正变量 E.自由变量 2.图解法求解线性规划问题的主要过程有() A.画出可行域 B.求出顶点坐标 C.求最优目标值 D.选基本解 E.选最优解 3.表上作业法中确定换出变量的过程有() A.判断检验数是否都非负 B.选最大检验数 C.确定换出变量 D.选最小检验数 E.确定换入变量 4.求解约束条件为“≥”型的线性规划、构造基本矩阵时,可用的变量有()A.人工变量 B.松弛变量 C. 负变量 D.剩余变量 E.稳态变量 5.线性规划问题的主要特征有() A.目标是线性的 B.约束是线性的 C.求目标最大值 D.求目标最小值 E.非线性 三、计算题(共60分) 1. 下列线性规划问题化为标准型。(10分) 1 / 17 ^ 高等教育《运筹学》模拟试题及答案 一、名词解释 运筹学:运筹学主要运用数学方法研究各种系统的优化途径及方案。为决策者提供科学的决策依据 线性规划:一般地,如果我们要求出一组变量的值,使之满足一组约束条件,这组约束条件只含有线性不等式或线性方程,同时这组变量的值使某个线性的目标函数取得最优值(最大值或最小值)。这样的数学问题就是线性规划问题 可行解:在线性规划问题的一般模型中,满足约束条件的一组 12,,.........n x x x 值称为此线性规 划问题的可行解, 最优解:在线性规划问题的一般模型中,使目标函数f 达到最优值的可行解称为线性规划问题的最优解。 运输问题:将一批物资从若干仓库(简称为发点)运往若干目的地(简称为收点),通过组织运输,使花费的费用最少,这类问题就是运输问题 闭回路:如果在某一平衡表上已求得一个调运方案,从一个空格出发,沿水平方向或垂直方向前进,遇到某个适当的填有调运量的格子就转向前进。如此继续下去,经过若干次,就一定能回到原来出发的空格。这样就形成了一个由水平线段和垂直线段所组成的封闭折线,我们称之为闭回路 二、单项选择 1、最早运用运筹学理论的是( A ) A 二次世界大战期间,英国军事部门将运筹学运用到军事战略部署 B 美国最早将运筹学运用到农业和人口规划问题上 C 二次世界大战期间,英国政府将运筹学运用到政府制定计划 D 50年代,运筹学运用到研究人口,能源,粮食,第三世界经济发展等问题上 2、下列哪些不是运筹学的研究范围( D ) A 质量控制 B 动态规划 C 排队论 D 系统设计 3、对于线性规划问题,下列说法正确的是( D ) A 线性规划问题可能没有可行解 B 在图解法上,线性规划问题的可行解区域都是“凸”区域 C 线性规划问题如果有最优解,则最优解可以在可行解区域的顶点上到达 D 上述说法都正确 4、下面哪些不是线性规划问题的标准形式所具备的( C ) A 所有的变量必须是非负的 B 所有的约束条件(变量的非负约束除外)必须是等式 C 添加新变量时,可以不考虑变量的正负性 D 求目标函数的最小值 5、在求解运输问题的过程中运用到下列哪些方法( D ) A 西北角法 B 位势法 C 闭回路法 D 以上都是 《管理运筹学》期中复习题 答案 标准化文件发布号:(9312-EUATWW-MWUB-WUNN-INNUL-DQQTY- 《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1.线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2.图解法适用于含有 两个 _ 变量的线性规划问题。 3.线性规划问题的可行解是指满足 所有约束条件_ 的解。 4.在线性规划问题的基本解中,所有的非基变量等于 零 。 5.在线性规划问题中,基本可行解的非零分量所对应的列向量线性 无 关 6.若线性规划问题有最优解,则最优解一定可以在可行域的 顶点_ 达到。 7.若线性规划问题有可行解,则 一定 _ 有基本可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9.满足 非负 _ 条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰变量在目标函数中的系数为 正 。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12.线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13.线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14.线性规划问题的标准形式中,约束条件取 等 _ 式,目标函数求 最大 _值,而所有决策变量必须 非负 。 15.线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解,反之不然 16.在用图解法求解线性规划问题时,如果取得最值的等值线与可行域的一段边界重合,则 _ 最优解不唯一 。 17.求解线性规划问题可能的结果有 唯一最优解,无穷多最优解,无界解,无可行解 。 18.如果某个约束条件是“ ”情形,若化为标准形式,需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量,则应引进两个非负变量X j ′ , X j 〞, 同时令X j = X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 运筹学期末试卷(B卷) 系别:工商管理学院专业:考试日期:年月日姓名:学号:成绩: 1.[10分] 匹克公司要安排4个工人去做4项不同的工作,每个工人完成各项工作所消耗的时间(单位:分钟)如下表所示: 要求:(1)建立线性规划模型(只建模型,不求解) (2)写出基于Lindo软件的源程序。 2.[15分]某公司下属甲、乙两个厂,有A原料360斤,B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品,乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下 (1) 建立规划模型获取各厂最优生产计划。 (2) 试用图解法 求解最优结果。 3.[10分] 考虑下面的线性规划问题: 目标函数:Min Z=16x 1+16x 2 +17x 3 约束条件: 利用教材附带软件求解如下: **********************最优解如下************************* 目标函数最优值为 : 148.916 变量 最优解 相差值 ------- -------- -------- x1 7.297 0 x2 0 .703 x3 1.892 0 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 13123123123300.56153420,,0 x x x x x x x x x x x +≤-+≥+-≥≥ 1 20.811 0 2 0 -3.622 3 0 -4.73 目标函数系数范围: 变量下限当前值上限 ------- -------- -------- -------- x1 1.417 16 16.565 x2 15.297 16 无上限 x3 14.4 17 192 常数项数范围: 约束下限当前值上限 ------- -------- -------- -------- 1 9.189 30 无上限 2 3.33 3 15 111.25 3 -2.5 20 90 试回答下列问题: (1)第二个约束方程的对偶价格是一个负数(为-3.622),它的含义是什么? (2)x2有相差值为0.703,它的含义是什么? (3)请对右端常数项范围的上、下限给予具体解释,应如何应用这些数 《运筹学》试题参考答案 一、填空题(每空2分,共10分) 1、在线性规划问题中,称满足所有约束条件方程和非负限制的解为 可行解 。 2、在线性规划问题中,图解法适合用于处理 变量 为两个的线性规划问题。 3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点,化为供求平衡的标准形式 。 4、在图论中,称 无圈的 连通图为树。 5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。 二、(每小题5分,共10分)用图解法求解下列线性规划问题: 1)max z = 6x 1+4x 2 ?????? ?≥≤≤+≤+0 7810 22122121x x x x x x x , 解:此题在“《运筹学》复习参考资料.doc ”中已有,不再重复。 2)min z =-3x 1+2x 2 ????? ????≥≤-≤-≤+-≤+0 ,1 37210 42242212 1212121x x x x x x x x x x 解: ⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺ ⑴ ⑵ ⑶ ⑷ ⑸、⑹ 可行解域为abcda ,最优解为b 点。 由方程组? ??==+022 42221x x x 解出x 1=11,x 2=0 ∴X *=???? ??21x x =(11,0)T ∴min z =-3×11+2×0=-33 三、(15分)某厂生产甲、乙两种产品,这两种产品均需要A 、B 、C 三种资源,每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示: A B C 甲 9 4 3 70 乙 4 6 10 120 360 200 300 1)建立使得该厂能获得最大利润的生产计划的线性规划模型;(5分) 《管理运筹学》期末考试试题 一、单项选择题(共5小题,每小题3分,共15分) 1.如果一个线性规划问题有n个变量,m个约束方程(m 3. 写出下面线性规划问题的对偶问题: 123123123123123min z 25, 258, 23 3,.. 4 26, ,,0. x x x x x x x x x s t x x x x x x =++-+≤??++=??-+≤??≥? 四、计算下列各题(每题20分,合计40分) 1. 用单纯形法求解下列线性规划的最优解: 012121212max 2..32250,0x x x s t x x x x x x =+??≤??≤??+≤??≥≥? 2.用割平面法求解整数规划问题。 12 121212 max 7936735,0,z x x x x x x x x =+-+≤??+≤??≥?且为整数 《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1.线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2.图解法适用于含有 两个 _ 变量的线性规划问题。 3.线性规划问题的可行解是指满足 所有约束条件_ 的解。 4.在线性规划问题的基本解中,所有的非基变量等于 零 。 5.在线性规划问题中,基本可行解的非零分量所对应的列向量线性 无 关 6.若线性规划问题有最优解,则最优解一定可以在可行域的 顶点_ 达到。 7.若线性规划问题有可行解,则 一定 _ 有基本可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9.满足 非负 _ 条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰变量在目标函数中的系 数为 正 。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12.线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13.线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14.线性规划问题的标准形式中,约束条件取 等 _ 式,目标函数求 最大 _值,而所 有决策变量必须 非负 。 15.线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解,反之不 然 16.在用图解法求解线性规划问题时,如果取得最值的等值线与可行域的一段边界重合,则 _ 最优解不唯一 。 17.求解线性规划问题可能的结果有 唯一最优解,无穷多最优解,无界解,无可行解 。 18.如果某个约束条件是“ ”情形,若化为标准形式,需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量,则应引进两个非负变量X j ′ , X j 〞, 同时令X j = X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决 策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻 找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检 验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 管理运筹学试题(A) 一.单项选择(将唯一正确答案前面的字母填入题后的括号里。正确得1分,选错、多选或不选得0分。共15分) 1.在线性规划模型中,没有非负约束的变量称为() A.多余变量B.松弛变量C.自由变量D.人工变量 正确答案:A: B: C: D: 2.约束条件为AX=b,X≥0的线性规划问题的可行解集是()A.补集B.凸集C.交集D.凹集 正确答案:A: B: C: D: 3.线性规划问题若有最优解,则一定可以在可行域的()上达到。A.内点B.外点C.极点D.几何点 正确答案:A: B: C: D: 4.对偶问题的对偶是() A.基本问题B.解的问题C.其它问题D.原问题 正确答案:A: B: C: D: 5.若原问题是一标准型,则对偶问题的最优解值就等于原问题最优表中松弛变量的() A.值B.个数C.机会费用D.检验数 正确答案:A: B: C: D: 6.若运输问题已求得最优解,此时所求出的检验数一定是全部()A.大于或等于零B.大于零C.小于零D.小于或等于零 正确答案:A: B: C: D: 7.设V是一个有n个顶点的非空集合,V={v1,v2,……,vn},E是一个有m条边的集合,E={e1,e2,……em},E中任意一条边e是V 的一个无序元素对[u,v],(u≠v),则称V和E这两个集合组成了一个() A.有向树B.有向图C.完备图D.无向图 正确答案:A: B: C: D: 8.若开链Q中顶点都不相同,则称Q为() A.基本链B.初等链C.简单链D.饱和链 正确答案:A: B: C: D: 9.若图G 中没有平行边,则称图G为() A.简单图B.完备图C.基本图D.欧拉图 正确答案:A: B: C: D: 10.在统筹图中,关键工序的总时差一定() A.大于零B.小于零C.等于零D.无法确定 正确答案:A: B: C: D: 11.若Q为f饱和链,则链中至少有一条后向边为f () A.正边B.零边C.邻边D.对边 正确答案:A: B: C: D: 12.若f 是G的一个流,K为G的一个割,且Valf=CapK,则K一定是() A.最小割B.最大割C.最小流D.最大流 正确答案:A: B: C: D: 13.对max型整数规划,若最优非整数解对应的目标函数值为Zc,最优整数解对应的目标值为Zd,那么一定有( ) A.Zc ∈Zd B.Zc =Zd C.Zc ≤Zd D.Zc ≥Zd 正确答案:A: B: C: D: 14.若原问题中xI为自由变量,那么对偶问题中的第i个约束一定为()A.等式约束B.“≤”型约束C.“≥”约束D.无法确定 正确答案:A: B: C: D: 15.若f*为满足下列条件的流:Valf*=max{Valf |f为G的一个流},则称f*为G的() A.最小值B.最大值C.最大流D.最小流 正确答案:A: B: C: D: 管理运筹学模拟试题及 答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】 四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题(每题2分,共20分。) 1.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性 规划问题求解,原问题的目标函数值等于(C)。 A. maxZ B. max(-Z) C. –max(-Z) 2.下列说法中正确的是(B)。 A.基本解一定是可行解B.基本可行解的每个分量 一定非负 C.若B是基,则B一定是可逆D.非基变量的系数列向量一定是 线性相关的 3.在线性规划模型中,没有非负约束的变量称为( D ) 多余变量 B.松弛变量 C.人工变量 D.自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时, 可求得(A)。 A.多重解B.无解C.正则解 D.退化解 5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足( D )。 A.等式约束 B.“≤”型约束 C.“≥”约束 D.非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y是 (B)。 A.多余变量B.自由变量C.松弛变量D.非 负变量 7.在运输方案中出现退化现象,是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8.树T的任意两个顶点间恰好有一条(B)。 A.边B.初等链C.欧拉圈 D.回路 9.若G中不存在流f增流链,则f为G的( B )。 A.最小流 B.最大流 C.最小费用流 D.无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足(D) A.等式约束B.“≤”型约束C.“≥”型约束 D.非负约束 二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有() A.松弛变量 B.剩余变量 C.非负变量 D.非正变量E.自由变量 2.图解法求解线性规划问题的主要过程有() 运筹学(Operational Research)复习资料 第一章绪论 一、名词解释 1.运筹学:运筹学是应用分析、试验、量化的方法,对经济管理系统中的人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。 二、选择题 1.运筹学的主要分支包括(ABDE ) A图论B线性规划C非线性规划D整数规划E目标规划 2. 最早运用运筹学理论的是( A ) A . 二次世界大战期间,英国军事部门将运筹学运用到军事战略部署 B . 美国最早将运筹学运用到农业和人口规划问题上 C . 二次世界大战期间,英国政府将运筹学运用到政府制定计划 D . 50年代,运筹学运用到研究人口,能源,粮食,第三世界经济发展等问题上 第二章线性规划的图解法 一、选择题/填空题 1.线性规划标准式的特点: (1)目标函数最大化(2)约束条件为等式(3 决策变量为非负(4 ) 右端常数项为非负2. 在一定范围内,约束条件右边常数项增加一个单位: (1)如果对偶价格大于0,则其最优目标函数值得到改进,即求最大值时,最优目标函数值变得更大,求最小值时最优目标函数值变得更小。 (2)如果对偶价格小于0,则其最优目标函数值变坏,即求最大值时,最优目标函数值变小了;求最小值时,最优目标函数值变大了。 (3)如果对偶价格等于0,则其最优目标函数值不变。 3.LP模型(线性规划模型)三要素: (1)决策变量(2)约束条件(3)目标函数 4. 数学模型中,“s·t”表示约束条件。 5. 将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左端加上松弛变量。 6. 将线性规划模型化成标准形式时,“≥”的约束条件要在不等式左端减去剩余变量。7.下列图形中阴影部分构成的集合是凸集的是A 运筹学试题四 一、对约束条件(20分) ??? ?? ---++=---++=----+=-≥=x x x x x x x x x x x x x x j j 123 56346712474817223241029017,, 说明解X=(1,2,1,0,0,0,0)T 是不是基可行解,假定不是,试找出一个基可行解。 二、已知线性规划问题(20分) ??422m 321321=++-+-=x x x x x x inz 12 五、用动态规划方法求解下列问题(25分) ???? ? max ,,z x x x x x x x j j =++≥≥=349 0123122232 123 六、求解下图的中国邮路问题(20分) 一、解: (1) ??----=1001A 解出 0,01,09431=>=>=x x x 由互补松弛定理:011=?s y x 得2,0211-=+∴=y y y s ① 033=?s y x 得2,0213-=-∴=ky y y s ② ①②联立得k y k k y +-=+-= 14 *,126*21 而**,'*,12*21y y Z Z 将=-=代入③ 12*6*421-=+∴y y ③ 则2*,6*,321=-=-=y y k 综上,3-=k ,对偶问题最优解为T T y y Y )2,6(),(*21-== 三、解:(1)表上作业法求解得: 四、解:用匈牙利法求解 ??????? ? ?46255132433656395132454740274135~ ??601003111571174150203??????? ??80 1200612271090001 ∴最优方案为:肖恩 安 材料准备, 琼 记录 运筹学期末复习题 一、判断题: 1、任何线性规划一定有最优解。() 2、若线性规划有最优解,则一定有基本最优解。() 3、线性规划可行域无界,则具有无界解。() 4、基本解对应的基是可行基。() 5、在基本可行解中非基变量一定为零。() 6、变量取0或1的规划是整数规划。() 7、运输问题中应用位势法求得的检验数不唯一。() 8、产地数为3,销地数为4的平衡运输中,变量组{X11,X13,X22,X33,X34}可作为一组基变量.() 9、不平衡运输问题不一定有最优解。() 10、m+n-1个变量构成基变量组的充要条件是它们不包含闭回路。() 11、含有孤立点的变量组不包含有闭回路。() 12、不包含任何闭回路的变量组必有孤立点。() 13、产地个数为m销地个数为n的平衡运输问题的系数距阵为A,则有r(A)≤m+n-1() 14、用一个常数k加到运价矩阵C的某列的所有元素上,则最优解不变。() 15、匈牙利法是求解最小值分配问题的一种方法。() 16、连通图G的部分树是取图G的点和G的所有边组成的树。() 17、求最小树可用破圈法.() 18、Dijkstra算法要求边的长度非负。() 19、Floyd算法要求边的长度非负。() 20、在最短路问题中,发点到收点的最短路长是唯一的。() 21、连通图一定有支撑树。 () 22、网络计划中的总工期等于各工序时间之和。 () 23、网络计划中,总时差为0的工序称为关键工序。 () 24、在网络图中,关键路线一定存在。 () 25、紧前工序是前道工序。 () 26、后续工序是紧后工序。 () 27、虚工序是虚设的,不需要时间,费用和资源,并不表示任何关系的工序。 () 28、动态规划是求解多阶段决策问题的一种思路,同时是一种算法。 () 29、求最短路径的结果是唯一的。 () 30、在不确定型决策中,最小机会损失准则比等可能性则保守性更强。 () 31、决策树比决策矩阵更适于描述序列决策过程。 () 32、在股票市场中,有的股东赚钱,有的股东赔钱,则赚钱的总金额与赔钱的总金额相等,因此称这一现象为零和现象。 () 33、若矩阵对策A的某一行元素均大于0,则对应值大于0。 () 34、矩阵对策中,如果最优解要求一个局中人采取纯策略,则另一局中人也必须采取纯策略。 () 35、多阶段决策问题的最优解是唯一的。 () 36、网络图中相邻的两个结点之间可以有两条弧。 ()管理运筹学模拟试题及答案
管理运筹学期末试卷B
《运筹学》-期末考试-试卷A-答案(1)
管理运筹学期中复习题答案
管理运筹学全部试题
管理运筹学模拟试题附答案
《运筹学》模拟试题及答案(2020年整理).doc
《管理运筹学》期中复习题答案
管理运筹学期末试卷题目B卷
(整理)《运筹学》期末考试试题与参考答案
《管理运筹学》期末考试试题
《管理运筹学》期中复习题答案
管理运筹学试题
管理运筹学模拟试题及答案
管理运筹学期末复习资料【韩伯棠】
管理运筹学试题四(含答案)
《管理运筹学期末复习题》