运筹学复习答案

1、一、选择题 2*5二、名词解释 4*51. 影子价格:当约束条件中的常数项增加一个单位时，最优目标函数值增加的数 量。影增2. 对偶价格:当约束条件中的常数项增加一个单位时，最优目标函数值改进的数 量。3. 灵敏度分析:对系统或事物因周围条件变化显示出来的敏感程度分析。4.0-1 规划:所有决策变量只能取 0 或 1 两个整数的整数线性规划。5. 分支定界法:分枝定界法是先求解整数规划的线性规划问题。如果其最优解不 符合整数条件，那么求出整数规划的上下界，用增加约束条件的方法，把相应 的线性规划的可行域分成子区域称为分枝，再求解这些子区域上的线性规 划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。6. 生成子图:给定一个无向图G=V,E，保存G的所有点，而删掉局部G的 边或者说保存一局部G的边，所获得图G,称之为G的生成子图。7. 松弛问题:不考虑整数约束条件，由余下的目标函数和约束条件构成的规划问 题。8. 欧拉回路:图 G 的一个回路，假设它恰通过 G 中每条边一次,那么称该回路为 欧拉回路。9. 样本信息:研究中实际观测或调查的一局部个体的信息。10. 最小生成树

2、:在一个赋权的连通的无向图 G 找出一个生成树，并使得这个生 成树的所有边的权数之和最小。11. 目标约束:在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏 差变量，减去正偏差变量，并且等于目标值，这样形成一个新的函数方程，把 它作为一个新的约束条件，参加到原问题中去，称这种新的约束条件为目标约 束。12. 偏差变量:指目标规划中实现值与目标值之间的差异。其中实现值超过目标值 的局部记为d+,实现值未到达目标值的局部记为d-o d+ , d-这样的变量称为偏 差变量。13状态变量：描述各阶段状态的变量称为状态变量。14. 根本可行解：满足非负条件的根本解叫根本可行解。15. 后验概率：利用样本情报对先验概率修正后得到的概率。16. 定性分析：借助决策者的知识，经历，分析和判断能力等进展决策的方法。17定量分析：量化决策问题并建立数学模型进展决策的方法。基于事物的数 据和数量关系,建模、计算找出解决方案18.状态与状态变量：状态是指每个阶段开场所处的自然状况或客观条件，而描 述过程状态的变量就是状态变量。能够完全描述动态系统时域行为的所含变量 个数最少的变量组称为系统的状态变量

3、。三、简答题 7*31. 简述单纯形法的根本思路 从可行域中某一个顶点开场，判断此顶点是否是最优解，如不是 ,那么再找另一 个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直 到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出 线性规划问题无最优解为止。2. 简述运筹学中背包问题的一般提法：对于 N 种具有不同重量和不同价值的物 品，在携带物品总重量限制的情况下，决定这N种物品中每一种物品多少数量 装入背包，使得装入背包物品的总价值最大。3. 简述著名的哥尼斯堡七桥难题及答案河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一 次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥 问题，一个著名的图论问题。欧拉证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连 接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7 条连接这4个点的线，如图2所示。于是“七桥问题就等价于图3中所画图形的一笔画问题了。每个点如果有进 去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔 画。

4、图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在 一次走遍7座桥，而每座桥只许通过一次的走法。4. 建立动态规划模型时，应定义状态变量，请说明状态变量的特点：第一,可知性，即各阶段的状态变量的取值能直接或间接确实定；第二，能够确切 的描述过程的演变且满足无后效性.5. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解：因为这类线性规划问题在构造上存在着特殊性，所以可以采用比单纯形法更为简 单的表上作业法来求解.6简述目标规划的目标函数主要类型及其数学表达式：目标规划的目标函数只能取极小形式，即 minz=f(d+,d-)，共有如下三种形式：1，要求 恰好等于目标值，即希望决策值超过和缺乏目标值的局部都尽可能小，因此由函数 minz=f(d+d-)；2，要求不超过目标值，允许达不到目标值，即希望决策值不超过目 标值，也希望d+越小越好，因此有 minz=fd+；要求不低于目标值，允许超过目标 值，即希望决策值不低于目标值，也希望d-越小越好，因此有minz=f(d-).7. 简述动态规划数学模型要点1分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划分为

5、满足递推关系的假设干阶段，对分时序的静态问题要认为赋予“时段概念；2正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段 的状态变量的取值能直接或间接确实定；第二，能够确切的描述过程的演变且 满足无后效性；3根据状态变量和决策变量的含义，正确写出状态转移方程；4根据题意明确过程指标函数和最优指标函数以及第 k 阶段指标函数的含 义，并正确列出根本方程。8. 简述树定义及性质 树:连通且不含圈的无向图称为树。性质：1树无圈，m二n-1.树连通，m二n-1.(3) 树无圈，但每加一条新边，那么可得到惟一一个圈.(4) 树 连通，但任舍一条边，图就不连通.(5) 树中任意两点之间有惟一一条链相连.9. 简述表上作业法的根本步骤: 找出初始根本可行解,对于有m个产地n个销地的产销平衡问题，那么有m 个关于产量的约束方程和 n 个关于销量的约束方程。由于产销平衡，其模型最 多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在mXn的 产销平衡表上给出 m+n-1 个数字格，其相对应的调运量的值即为基变量的值。 求各非基变量的检验数，来判别问题是否到达最优解。如已是最优

6、解那么停 顿计算，否那么继续下一步。 确定入基变量和出基变量，找出新的根本可行解。在表上用闭回路法调整。 重复，步骤指导得到最优解。10. 简述线性规划对偶问题的根本性质 ：1 对称性 2 弱对偶性 3 最优性 4 强对偶性 5 互补松弛性11. 简述指派问题的标准形式及数学模型设 n 个人被分配去做 n 件工作，规定每个人只做一件工作，每件工作只有一个 人去做。 第 i 个人去做第 j 件工作的 效率 时间或费用 为 Cij(i=1.2n；j=12n)并假设Cij 0O问应如何分配才能使总效率时间或费 用最高？设决策变量1 指派第 i 个人去做第 j 件工作xij=min Z =cxij ij(i,j=1.2.口)不指派第i个人去做第j件工作i=1 j=1刀x = 1 (i = 12.n)ijj=1刀x = 1 (j = 12.n) i=1 min Z =刀另 c xij ijx=ij其数学模型为：0i或1(i, j =住皿)乙x = 1 (i = 1.2.n) ijj=1另x = 1 (j = 1.2.n)iji=1x = 0或1(i, j = 12 ) ij12.简述分支定界法及

7、其思路。分枝定界法是先求解整数规划的线性规划问题。 如果其最优解不符合整数条件，那么求出整数规划的上下界，用增加约束条件 的方法，把相应的线性规划的可行域分成子区域称为分枝，再求解这些子 区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划 的最优解。根本思路：1、先求出线性规划的解2、确定整数规划的最优目标函数值z*初始上界和下界z3、将一个线性规划问题分为两枝，并求解4、修改最优目标函数上、下界5、比较与剪枝：各分枝的目标函数值中，假设有小于Z者，那么剪掉此枝， 说明此子问题已经探清，不必再分枝了;否那么继续分枝。如此反复进展，直到得到z=z*为止，即得最优解x* o13. 简述不确定型决策的决策方法决策准那么1. 最大最小准那么悲观准那么，决策者从最不利的角度去考虑问题；2. 最 大最大准那么乐观准那么，决策者从最有利的角度去考虑问题；3. 等可能 性准那么，决策者把各自然状态发生的时机看成是等可能的;4. 乐观系数准那么 (折衷准那么 )，决策者取乐观准那么和悲观准那么的折衷； 5. 懊悔值准那么 沙万奇准那么，决策者从懊悔的角度去考虑问题14. 层次分析法的根

8、本步骤1.明确问题，提出总目标 2.绘制层次构造图 3. 标度及两两比较矩阵 4. 两两比 较矩阵一致性检验 5. 利用权数或特征向量求出各方案的优劣次序.15. 简述线性规划问题的解几种可能的结果1.有唯一最优解 （单纯形法中在求最大目标函数的问题时，对于某个根本可行 解，所有8j0） 2无可行解当迭代结果显示8j0,但基变量中仍有人工变 量3.无界解迭代时发生系数都为负数，那么无界 4.无穷多解某非基变 量的8值等于0四、计算题 13*31线性规划的图解法、单纯形法以及其对偶规划模型p10例一2运输问题的表上作业法p144例103整数规划的分支定界法P163例一4.目标规划的图解法p194例75动态规划逆序解法系统可靠性问题p217例5,采购与销售问题笔记本6图与网络的双标号法p237例37最小费用最大流问题p249例78风险型决策的决策问题p385例3五、论述题 10*11结合我国企业开展中面临的一些实际问题，简要论述运筹学在我国企业管理 优化中的重要应用及作用。答：运筹学在企业管理优化领域的主要应用有： 生产方案。如一家重型制造厂用线性规划及整数规划安排生产方案，节约了 10%

9、的生产费用。 市场营销。在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售 方案、市场竞争策略的制定等方面，运筹学也大展身手。美国杜邦公司在五十 年代起就非常重视将运筹学用于研究如何做好广告工作、产品定价，通用公司 也运用运筹学方法进展市场模拟研究。 库存管理。运筹学中的存贮论可以应用于物资库存量的管理，以确定仓库的 合理容量，以及确定适当的库存方式和库存量。 运输问题。运用运筹学，可以确定最小本钱的运输路线、物资的调拨、运输 工具的调度，以及新建厂址的选择等等。 人事管理。对人员的需求和招聘情况的预测；人力资源的开发，如对人才的 教育和培训，人才评价体系、薪酬体系确实定等，都可以运用运筹学方法。 财务会计。运筹学解决企业如何最有效的利用资金资源的问题。其涉及到投 资决策分析、本钱核算分析、证券管理等。在投资决策分析中，企业如何利用 剩余资金，如何投资往往有多种方案。而运筹学的作用就是要要对这些不同的 投资方案进展决策，以确定最优的方案，使得企业的收益最大。通常是利用线 性规划模型、决策论来进展判断。2. 根据您所学的?运筹学?及其它学科知识，谈谈您对“运筹帷幄，决胜千里的 理解；3. 请论述如何把你所学的运筹学的知识应用到今后的管理实践中去； 答：强化管理，不断进展管理刨新已成为企业在竞争中制胜的根本保证。作为 企业的管理者，把握并运用好运筹学的理念定会取得“运筹帷幄之中，决胜千 里之外之成效。参见第一题。4. 请简要列举至少 3 个我国古代朴

《运筹学复习答案》由会员汽***分享，可在线阅读，更多相关《运筹学复习答案》请在金锄头文库上搜索。