《管理运筹学》复习题及参考答案
第一章运筹学概念
一、填空题
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..(2.1 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.在单纯形迭代中,进基变量可以任选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 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所有δj≤0 10.下列解中可能成为最优解的有(ABCDE ) A基可行解B迭代一次的改进解C迭代两次的改进解 D迭代三次的改进解E所有检验数均小于等于0且解中无人工变量 四、名词、简答 1、人造初始可行基:当我们无法从一个标准的线性规划问题中找到一个m阶单位矩阵时,通常在约束方程中引入人工变量,而在系数矩阵中凑成一个m阶单位矩阵,进而形成的一个初始可行基称为人造初始可行基。 2、单纯形法解题的基本思路?可行域的一个基本可行解开始,转移到另一个基本可行解,并且使目标函数值逐步得到改善,直到最后球场最优解或判定原问题无解。 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2,约束形式为“≤”,X 3,X 4为松驰变量.表中解代入目标函数后得Z=10 X l X 2 X 3 X 4 —10 b -1 f g X 3 2 C O 1 1/5 X l a d e 0 1 (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 s.t AX≤b X≥0 称线性规划问题minW=Yb s.t 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为原问题的最优 《管理运筹学》(第二版)课后习题参考答案 第1章 线性规划(复习思考题) 1.什么是线性规划线性规划的三要素是什么 答:线性规划(Linear Programming ,LP )是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误 答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答:可行解:满足约束条件0≥=X b AX ,的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示: 一、 二、 三、 填空题(每小题 分,共 ?分) 、设原??问题为?????? ?≥-=++-≥--≤++++-= ,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 '=?',。 三、判断题(每小题 分,共 分) ( ) 、若原始问题是利润最大化的生产计划问题,则对偶问题是资源定价问题,对偶问题的最优解称为原始问题中资源的影子价格。影子价格越大说明这种资源越是相对紧缺,影子价格越小说明这种资源相对不紧缺。 ( ) 、对???型整数规划,若其松弛问题最优解对应的目标函数值为??,而其最优整数解对应的目标值为??,那么一定有?? ≤??。 ( ) 、任何一个无圈的图?都是一个树图。 ( ) 、一个可行流满足平衡条件是指:所有中间结点处流出量 流入量,收点流出量 ?? 发点流入量 ?,收点流入量 发点流出量。 ( ) 、恰好有两个悬挂点的树是一条链。 课程学习 《管理运筹学基础》 判断正误 线性规划问题的一般模型中不能出现等式约束。 正确答案:说法错误 2.在线性规划模型的标准型中,b j(j=1,2,…m)一定是非负的。正确答案:说法正确 解答参考: 3. 判断正误 线性规划问题的基本解一定是基本可行解 正确答案:说法错误 解答参考: 5. 判断正误 同一问题的线性规划模型是唯一的。 正确答案:说法错误 解答参考: 12.第一个顶点和最后一个顶点相同的闭链叫回路。 正确答案:说法错误 解答参考: 14. 判断正误 Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。 正确答案:说法正确 解答参考: 15.简述编制统筹图的基本原则。 参考答案:统筹图是有向图,箭头一律向右;统筹图只有一个起始点。一个终点,没有缺口;两个节点之间只能有一个作业相连;统筹图中不能出现闭合回路。 17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。 参考答案:西北角法:按照地图中的上北下南,左西右东的判断,对调运表中的最西北角上的空格优先满足最大供应,之后划去一行或一列,重复这种做法,直至得到初始可行解。最小元素法:对调运表中的最小运价对应的空格优先没醉最大供应,之后划去一行或一列,重复这种做法,直至得到初始可行解。差值法:在运价表中,计算各行和各列的最小运价和次最小运价之差,选出最大者,它所在某行或某列中的最小运价对应的空格优先满足最大供应,重复这种做法,直至得到初始可行解。一般来讲,用差值法求出的初始可行解最接近最优解,也就是最优的。 2. 用图解法求最优解时,只需求出可行域顶点对应的目标值,通过比较大小,就能找出最优解。 正确答案:说法正确 单纯形法计算中,选取最大正检验数对应的变量作为换入变量,将使目标函数的值增加更快。 正确答案:说法错误 解答参考: 6.若原问题有无穷多最优解,则其对偶问题也一定有无穷多最优解。 正确答案:说法正确 解答参考: 8.表上作业法中,任何一种确定初始基本可行解的方法都必须保证有(m + n -1)个变量。正确答案:说法正确 解答参考: 9.用分枝定界法求解一个极大化整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界 正确答案:说法正确 1 课程:管理运筹学 管理运筹学作业 第二章线性规划的图解法 P23:Q2:(1)-(6);Q3:(2) Q2:用图解法求解下列线性规划问题,并指出哪个问题具有唯一最优解,无穷多最优解,无界解或无可行解。 (1)Min f=6X1+4X2 约束条件:2X1+X2>=1, 3X1+4X2>=3 X1, X2>=0 解题如下:如图1 Min f=3.6 X1=0.2, X2=0.6 本题具有唯一最优解。 图1 (2)Max z=4X1+8X2 约束条件:2X1+2X2<=10 -X1+X2>=8 X1,X2>=0 解题如下:如图2: Max Z 无可行解。 图2 1 2 2 (3) Max z =X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下:如图3: Max Z=有无界解。 图3 (4) Max Z =3X1-2X2 约束条件:X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下:如图4: Max Z 无可行解。 图 4 3 (5)Max Z=3X1+9X2 约束条件:X1+3X2<=22 -X1+X2<=4 X2<=6 2X1-5X2<=0 X1,X2>=0 解题如下:如图5: Max Z =66;X1=4 X2=6 本题有唯一最优解。 图5 (6)Max Z=3X1+4X2 约束条件:-X1+2X2<=8 X1+2X2<=12 2X1+X2<=16 2X1-5X2<=0 X1,X2>=0 解题如下:如图6 Max Z =30.669 X1=6.667 X2=2.667 本题有唯一最优解。 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 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 《管理运筹学》(第二版)课后习题参考答案 第1章线性规划(复习思考题) 1. 什么是线性规划?线性规划的三要素是什么? 答:线性规划(Lin ear Programmi ng , LF)是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2. 求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误?答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3. 什么是线性规划的标准型?松弛变量和剩余变量的管理含义是什么? 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项 ' ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业 来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明 “遅 约束的左边取值大于右边规划值,出现剩余量。 4?试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关 系。 答:可行解:满足约束条件 扎—‘丸 的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示: 5 ?用表格单纯形法求解如下线性规划 解:标准化 1 可行基:对应于基可行解的基,称为可行基。 基可行解 SA] + S 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 .非负约束 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.图解法求解线性规划问题的主要过程有 ( ) 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分) 上交作业课程题目可以打印,答案必须手写,否则该门成绩0分。 管理运筹学 作业题 一、名词解释(每题3分,共15分) 1. 可行解:满足某线性规划所有的约束条件(指全部前约束条件和后约束条件)的任意一 组决策变量的取值,都称为该线性规划的一个可行解,所有可行解构成的集合称为该线性规划的可行域(类似函数的定义域),记为K 。 2. 最优解:使某线性规划的目标函数达到最优值(最大值或最小值)的任一可行解,都称 为该线性规划的一个最优解。线性规划的最优解不一定唯一,若其有多个最优解,则所有最优解所构成的集合称为该线性规划的最优解域。 3. 状态:指每个阶段开始时所处的自然状态或客观条件。 4. 决策树:决策树(Decision Tree )是在已知各种情况发生概率的基础上,通过构成决策 树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。 5. 最大最小准则:最大最小准则又称小中取大法或悲观法。为不确定型决策的决策准则之 一,其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度,在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小值,即在表的最右列,再从该列中选出最大者。这种方法的基本态度是悲观与保守。其基本思路是首先找出最不利情况下的最大收益。 二、 简答题(每题6分,共24分) 1. 简述单纯形法的基本步骤。 答:(1)把一般线形规划模型转换成标准型;(2)确定初始基可行解;(3)利用检验数j σ对初始基可行解进行最优性检验,若0≤j σ ,则求得最优解,否则,进行基变换;(4)基变换找新的可行基,通过确定入基变量和出基变量,求得新的基本可行解;(5)重复步骤(3)、(4)直至0≤j σ,求得最优解为止。 2. 简述动态规划的基本方程。 答:对于n 阶段的动态规划问题,在求子过程上的最优指标函数时,k 子过程与k+1过程有如下递推关系: 对于可加性指标函数,基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}(),({)(11) ( =+=++∈ 终端条件:f n+1 (s n+1) = 0 管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待 定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制, 保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式, 有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数 四川大学网络教育学院模拟试题( 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 09 <<运筹>>期末考试试卷(A)答案 一、不定项选择题(每小题2分共20分) 1、A 2、B 3、ABCD 4、ABC 5、D 6、C 7、B 8、ABCD 9、ABC 10、ABC 二、名词解释(每小题4分,共20分) 1、运筹学是一门以人机系统的组织、管理为对象,应用数学和计算机等工具来研究各类有限资源的合理规划使用期并提供优化决策方案的科学。 2、线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。 3、如果系统中包含元素A、B、C、K….等,按照经典意义(非模糊,非统计意义)的原则来聚类。 4、系统的综合性原则是指系统内部各组成部分的联系与协调,包含要素间的协调及系统与环境问题的协调。 5、TSP问题称为“旅行推销员问题”,是指:有N个城市A、B、…….等,它们这间有一定的距离,要求一条闭合路径,由某城市出发,每个城市经历过一次,最终返回原城市,所经历的路程最短。 三、简答题(每小题5分,共28分) 1、列出一些企业产品结构优化的柔性模型约束条件。 (1)关键设备的生产能力(2)各类能源的约束(3)工艺的约束 (4)产品类结构关系,以及物流过程中上、下游产品供需的约束 (5)某些产品的下限约束(6)非负约束 2、排队规则:损失制等待制:先到先服务、后到先服务、随机服务、优先权 服务混合制 3、运筹学的特点:(1)以最优性为核心。(2)以模型化为特征(3)以计算机为主要实现手段。(4)多学科交融 4、神经元的功能:(1)整合功能(2)兴奋与抑制(3)突触延时与不应期(4)学习、遗忘与疲劳 四、应用题。(每题15分,共45分) 1、设A、B的产量为X、Y 模型:目标MAX利润=500X+900Y 约束条件:9X+4Y≤360 4X+5Y≤200 3X+10Y≤300 X、Y均大于或等于零 图解略 最优解:X=20千克 Y=24千克利润31600元 2、企业在选择运用“农村包围城市”还是“城市中心”的指导思想时,应考虑自己的条件,竞争对手的情况,宏观和中观形势。 如,我国不少实力较弱的汽车企业,在发展之初,面临国内合资企业和国外汽车巨头的压力下,以农村,或三、四线城市为突破口,先在这些国内合资企业和国外汽车巨头不太重视的地区发展市场,在积累资金、经验、管理、技术等生产经营资源后,向大城市等竞争激烈的地区进军。 如果企业与国外合资,或在资金、技术、品牌、管理等方面有较大的优势,企业可以一开始就以广州等一线城市为主战场。 3、(1)如果两国没有任何的协调,A国最终会选择报复,因为只要A国选择报复,不论B国如何选择,对A国来说都最佳选择。反之亦然。 (2)如果两国协调,如果协调成功两国的对策是都不报复,如果两国协调不成功,两国都会选择报复。 习题参考答案 习题一 1.设选用第1种、第2种、第3种、第4种、第5种饲料的量分别为12345,,,,x x x x x 。 Min 543218.03.07.04.02.0x x x x x Z ++++= 1234512345 1234512345326187000.50.220.530..0.50.220.8100,,,,0 x x x x x x x x x x s t x x x x x x x x x x ++++≥??++++≥?? ++++≥??≥? 2.设x ij 为生产第i 种食品所使用的第j 种原料数,i =1,2,3分别代表甲、乙、丙,j =1,2,3分别代表A 、B 、C 。其数学模型为: Max Z =) (0.1)(5.1)(2)(95.1)(45.2)(9.2332313322212312111333231232221131211x x x x x x x x x x x x x x x x x x ++?-++?-++?-++?+++?+++? s.t . ) 3,2,1,3,2,1(,05 .06 .015 .02 .06 .012002500200033 323133 23 222123 23 222121 13 121113 13 121111 332313322212312111==≥≤++≤++≥++≤++≥++≤++≤++≤++j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ij 3.将下列线性规划问题化为标准形式 (1)引入剩余变量1s ,松弛变量2 s 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数的值仍然保持原值。如果同时存在最小θ值,说明有离基变量,则该问题在两个顶点上同时达到最优,为无穷多最优解。无界解:若某个非基变量xNk 的检验数σk> 0 ,但其对应的系数列向量P k' 中,每一个元素a ik' (i=1,2,3,…,m)均非正数,即有进基变量但找不到离基变量。 《运筹学》试题样卷(一) 一、判断题(共计10分,每小题1分,对的打√,错的打X ) 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题,若其中一个有最优解, 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解,那么它必有最优解。 4.对偶问题的对偶问题一定是原问题。 5.用单纯形法求解标准形式(求最小值)的线性规划问题时,与0 >j σ对应的变量都可以被选作换 入变量。 6.若线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型(8分) 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日;春夏季4000人日。如劳动力本身用不了时可外出打工,春秋季收入为25元 / 人日,秋冬季收入为20元 / 人日。该农场种植三种作物:大豆、玉米、小麦,并饲养奶牛和鸡。种作物时不需要专门投资,而饲养每头奶牛需投资800元,每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料,并占用人工秋冬季为100人日,春夏季为50人日,年净收入900 元 / 每头奶牛。养鸡时不占用土地,需人工为每只鸡秋冬季0.6人日,春夏季为0.3人日,年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表,表中54 ,x x 为松弛变量,问 (1)写出原线性规划问题;(4分) (2)写出原问题的对偶问题;(3分) (3)直接由上表写出对偶问题的最优解。(1分) 四、用单纯形法解下列线性规划问题(16分) s. t. 3 x1 + x2 + x3?60 x 1- x 2 +2 x 3?10 x 1+x 2-x 3?20 x 1,x 2 ,x 3?0 五、求解下面运输问题。(18分) 某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示: 问:应如何调运,可使得总运输费最小? 六、灵敏度分析(共8分) 线性规划max z = 10x1 + 6x2 + 4x3 s.t. x1 + x2 + x3 ?100 10x1 +4 x2 + 5 x3 ?600 2x1 +2 x2 + 6 x3 ?300 x1 , x2 , x3 ?0 的最优单纯形表如下: (1)C1在何范围内变化,最优计划不变?(4分) (2)b1在什么范围内变化,最优基不变?(4分) 七、试建立一个动态规划模型。(共8分) 第2章 线性规划的图解法 1.解: x ` A 1 (1) 可行域为OABC (2) 等值线为图中虚线部分 (3) 由图可知,最优解为B 点, 最优解:1x = 712,7152=x 。最优目标函数值:769 2.解: x 2 1 0 1 (1) 由图解法可得有唯一解 6.02.021==x x ,函数值为3.6。 (2) 无可行解 (3) 无界解 (4) 无可行解 (5) 无穷多解 (6) 有唯一解 38320 21== x x ,函数值为392。 3.解: (1). 标准形式: 3212100023m ax s s s x x f ++++= 0,,,,9 2213 2330 2932121321221121≥=++=++=++s s s x x s x x s x x s x x (2). 标准形式: 21210064m in s s x x f +++= ,,,4 6710 26 3212121221121≥=-=++=--s s x x x x s x x s x x (3). 标准形式: 21''2'2'10022m in s s x x x f +++-= 0,,,,30 22350 55270 55321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x 4.解: 标准形式: 212100510m ax s s x x z +++= ,,,8259 432121221121≥=++=++s s x x s x x s x x 松弛变量(0,0) 最优解为 1x =1,x 2=3/2. 运筹学期末试卷(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)请对右端常数项范围的上、下限给予具体解释,应如何应用这些数 《管理运筹学》期末考试试题 一、单项选择题(共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 =+-+≤??+≤??≥?且为整数 四、把下列线性规划问题化成标准形式: 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 每个工作人员连续工作八小时,且在时段开始时上班,问如何安排,使得既满足以上要求,又使上班人数最少? 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2,约束形式为“≤”,X3,X4为松驰变量.表中解代入目标函数后得Z=10 X l X2X3X4 —10b-1f g X32C O11/5 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.minZ=2x1+2x2+4x3 第二章 2.5 表2-3为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 12max 53z x x =+,约束形式为≤,34,x x 为松弛变量,表中解代入目标函数后得10z =。 (1)求a ~g 的值; (2)表中给出的解是否为最优解。 解:a=2,b=0,c=0,d=1,e=4/5,f=0,g=5;表中给出的解为最优解。 2.6 表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表,45,x x 为松弛变量,求表中a ~l 的值及各变量下标m ~t 的值。 解:a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0;变量的下标为m —4,n —5,s —1,t —6 2.10下述线性规划问题: 2.11某单位加工制作100套工架,每套工架需用长为2.9m 、2.1m 和1.5m 的圆钢各一根。已知原材料长7.4m 。问如何下料使得所用的原材料最省? 解:简单分析可知,在每一根原材料上各截取一根2.9m,2.lm 和1.5m 的圆钢做成一套工架,每根原材料剩下料头0.9m ,要完成100套工架,就需要用100根原材料,共剩余90m 料头。若采用套截方案,则可以节省原材料,下面给出了几种可能的套截方案,如表2-5所示。 实际中,为了保证完成这100套工架,使所用原材料最省,可以混合使用各种下料方案。 设按方案A,B,C,D,E 下料的原材料数分别为x 1,x 2,x 3,x 4,x 5,根据表2-5可以得到下面的线性规划模型 12345124345 1235min 00.10.20.30.82100 22100..3231000,1,2,3,4,5 i z x x x x x x x x x x x s t x x x x x i =++++++=??++=?? +++=??≥=? 用大M 法求解此模型的过程如表2-6所示,最优解为:x *=(0,40,30,20,0)T ,最优值为z *=16。《管理运筹学》第二版课后习题参考答案
管理运筹学期末试卷B
管理运筹学基础 答案
管理运筹学作业 韩伯棠第3版高等教育出版社课后答案
管理运筹学期中复习题答案
管理运筹学后习题参考答案汇总
管理运筹学模拟试题及答案
管理运筹学(本科)(参考答案)学习版.doc
管理学管理运筹学课后答案——谢家平
管理运筹学模拟试题附答案
管理运筹学--答案
卫生管理运筹学第二版答案薛迪,复旦大学出版社.doc
2019管理运筹学课后答案
《运筹学》期末考试试卷A答案
《管理运筹学》课后习题答案
管理运筹学期末试卷题目B卷
《管理运筹学》期末考试试题
最全的运筹学复习题及答案
管理运筹学整理答案