运筹学期末复习题及答案

1、19、 简述线性规划模型主要参数（ p11）（1） 、价值系数：目标函数中决策变量前的系数为价值系数（2） 、技术系数：约束条件中决策变量前的系数（3） 、约束条件右边常数项15、简述线性规划解几种可能的结果（情形） （ppt 第二章 39 或 89 页）（1）. 有唯一最优解 ( 单纯形法中在求最大目标函数的问题时， 对于某个基本可行解，所有 j 0)（2）. 无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。（3）. 无界解， 即可行域的范围延伸到无穷远， 目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件（4）. 无穷多个最优解，则线段上

2、的所有点都代表了最优解（5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，用图解法无退化解1、简述单纯形法的基本思路（ p70）从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是, 则再找另一个使得其目标函数值更优的顶点，称之为迭代， 再判断此点是否是最优解。 直到找到一个顶点为其最优解， 就是使得其目标函数值最优的解， 或者能判断出线性规划问题无最优解为止。17、简述线性规划中添加人工变量的前提（p85）在系数矩阵中直接找不到初始可行解， 进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解10、简述线性规划对偶问题的基本性质（

3、 p122）（1）对称性（ 2）弱对偶性（ 3）强对偶性（ 4）最优性（ 5）互补松弛型原函数与对偶问题的关系1）求目标函数最大值的线性规划问题中有 n 个变量 m 个约束条件， 它的约束条件都是小于等于不等式。 而其对偶则是求目标函数为最小值的线性规划问题， 有m个变量 n 个约束条件，其约束条件都为大于等于不等式。2 ）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项， 并且原问题的目标函数中的第i 个价值系数就等于对偶问题中的第i 个约束条件的右边常数项。 3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第 i 个约束条件的右边常数项就等于零对偶

4、问题的目标函数中的第i 个变量的系数。4） 对偶问题的约束条件的系数矩阵a 是原问题约束矩阵的转置。5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解因为这类线性规划问题在结构上存在着特殊性, 表上作业法根据运输问题的特点来设计的特殊的单纯形法，可以更加形象直观简单的解决运输问题。9、简述表上作业法的基本步骤（1） 用最小元素法找出初始基可行解, 也就是初始调运方案。 对于有 m个产地 n 个销地的产销平衡问题， 则有 m个关于产量的约束方程和 n 个关于销量的约束方程。由于产销平衡， 其模型最多只有 m+n-1个独立的约束方程， 即运输问题有 m+n-1 个基变量。在 mn的产销平衡

5、表上给出 m+n-1 个数字格，其相对应的调运量的值即为基变量的值。（2） 求各非基变量的检验数。（3） 用闭回路法来判别问题是否达到最优解。如已是最优解则停止计算， 否则继续下一步。（4） 用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。11、简述指派问题的标准形式及数学模型（ ppt 或书上 p179）设n 个人被分配去做 n 件工作， 规定每个人只做一件工作， 每件工作只有一个人去做。 已知第 i 个人去做第 j 件工作的效率 （时间或费用） 为cij ( i =1.2,n; j =1.2,n) 并假设 cij0。问应如何分配才能使总效率 （时间或

6、费用）最高？12、简述分枝定界法的基本步骤分枝定界法是先求解整数规划的线性规划问题。 如果其最优解不符合整数条件，则求出整数规划的上下界， 用增加约束条件的办法， 把相应的线性规划的可行域分成子区域（称为分枝） ，再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。基本思路：1、先求出线性规划的解2、确定整数规划的最优目标函数值z* 初始上界和下界 z3、将一个线性规划问题分为两枝，并求解4、修改最优目标函数上、下界5、比较与剪枝 ：各分枝的目标函数值中，若有小于z 者，则剪掉此枝， 表明此子问题已经探清，不必再分枝了; 否则继续分枝。6、如此反复进行，直

7、到得到 z z* 为止，即得最优解 x*。6、简述目标规划的目标函数主要类型及其数学表达式。目标规划的目标函数只能取极小形式，即minz=f(d+,d-)，共有如下三种形式：（ 1） , 要求恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数 minz=f(d+d-)；（2），要求不超过目标值，允许达不到目标值，即希望决策值不超过目标值， 也希望 d+越小越好， 因此有 minz=f（ d+）;(3)要求不低于目标值，允许超过目标值，即希望决策值不低于目标值，也希望d-越小越好，因此有 minz=f(d-).2、简述运筹学中背包问题的一般提法（ p225）对于 n种具有不

8、同重量和不同价值的物品， 在携带物品总重量限制的情况下， 决定这 n种物品中每一种物品多少数量装入背包内， 使得装入背包物品的总价值最大。4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点第一, 可知性, 即各阶段的状态变量的取值能直接或间接的确定；第二, 能够确切的描述过程的演变且满足无后效性.7、简述动态规划数学模型要点（ppt 第十章 18 论述题增加阶段和阶段变量）（1） 分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划3、简述著名的哥尼斯堡七桥难题及答案河上有 7 座桥，将河中的两个岛和河岸连结， 如图 1 所示。一个散步者能否一次走遍 7 座桥，而且每座桥只许

9、通过一次， 最后仍回到起始地点。 这就是七桥问题，一个著名的图论问题。acd分为满足递推关系的若干阶段，对分时序的静态问题要认为赋予“时段”概念；（2） 正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各 阶段的状态变量的取值能直接或间接的确定； 第二，能够确切的描述过程的演变且满足无后效性；（3） 根据状态变量和决策变量的含义，正确写出状态转移方程；（4） 根据题意明确过程指标函数和最优指标函数以及第k 阶段指标函数的含义，并正确列出基本方程。b欧拉证明了这样的走法不存在。 欧拉是这样解决问题的： 既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成a、b、c、d4 个点， 7

10、座桥表示成 7 条连接这 4 个点的线，如图 2 所示。于是“七桥问题”就等价于图 3 中所画图形的一笔画问题了。 每个点如果有进去的边就必须有出来的边， 从而每个点连接的边数必须有偶数个才能完成一笔画。图 3 的每个点都连接着奇数条边， 因此不可能一笔画出， 这就说明不存在一次走遍 7 座桥，而每座桥只许通过一次的走法。8、简述树定义及性质树: 连通且不含圈的无向图称为树。性质：（1）树无圈，m=n-1.(2)树连通， m=n-1.(3)树无圈，但每加一条新边，则可得到惟一一个圈 .(4)树连通， 但任舍一条边， 图就不连通 .(5)树中任意两点之间有惟一一条链相连 .16、简述求最小生成树

11、的方法（1） 避圈法：将图中的边按权由小到大排序；按排序由小到大选定n1 条边为止， 选择时每选一条边应避免和已选的边构成圈， 且所选边是未选边中的最小权边。（2） 破圈法： 在给定的赋权的连通图上任选一个圈； 在所找的圈中去掉一个权数最大的边 （如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成 树，否则返回第 1 步。18、简述决策按环境分类（分为哪几种） （ p389） 确定型决策：在决策环境完全确定的条件下进行不确定型决策： 在决策环境不确定的条件下进行， 决策者对个自然状态发生的概率一无所知风险型决策问题： 在

12、决策环境不确定的条件下进行， 决策者对各自然状态发生的概率可以预先估计或计算出来非程序化决策： 13、简述不确定型决策的决策方法（决策准则） （ p389）（1） 最大最小准则（悲观准则） ，决策者从最不利的角度去考虑问题；（2） 最大最大准则（乐观准则） ，决策者从最有利的角度去考虑问题；（3） 等可能性准则，决策者把各自然状态发生的机会看成是等可能的;（4） 乐观系数准则 ( 折衷准则 ) ，决策者取乐观准则和悲观准则的折衷；（5） 后悔值准则（沙万奇准则） ，决策者从后悔的角度去考虑问题14、简述层次分析法的基本步骤 （ppt 第 16 章 31）1. 明确问题，提出总目标 2. 绘制层

13、次结构图 3.标度及两两比较矩阵 4. 求各因素权重的过程 5.两两比较矩阵一致性检验 6.利用权数或特 征 向 量 求 出 各 方案 的 优 劣 次序. evpi = evwpi - ev w0pi1、结合我国企业发展中面临的一实际问题，简要论述运筹学在我国企业管理优化中的重要应用及作用。答：运筹学在企业管理优化领域的主要应用有：生产计划。 如一家重型制造厂用线性规划及整数规划安排生产计划，节约了 10%的生产费用。市场营销。在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售计划、市场竞争策略的制定等方面， 运筹学也大展身手。 美国杜邦公司在五十年代起就非常重视将运筹学用于研究如何做好

14、广告工作、 产品定价， 通用公司也运用运筹学方法进行市场模拟研究。库存管理。 运筹学中的存贮论可以应用于物资库存量的管理， 以确定仓库的合理容量，以及确定适当的库存方式和库存量。运输问题。运用运筹学，可以确定最小成本的运输路线、物资的调拨、运输工具的调度，以及新建厂址的选择等等。人事管理。 对人员的需求和招聘情况的预测； 人力资源的开发， 如对人才的教育和培训，人才评价体系、薪酬体系的确定等，都可以运用运筹学方法。财务会计。 运筹学解决企业如何最有效的利用资金资源的问题。其涉及到投资决策分析、成本核算分析、证券管理等。在投资决策分析中，企业如何利用 剩余资金， 如何投资往往有多种方案。 而运筹

15、学的作用就是要要对这些不同的投资方案进行决策， 以确定最优的方案， 使得企业的收益最大。 通常是利用线性规划模型、决策论来进行判断。联合航空公司满足乘客需求前提下,以最低成本进行订票及安排机场工作班次1-2/1986600 万标准品牌公司delta航空公司宝洁公司控制成品库存（制定最优再订购点和订购量，确保安全库存）12/1981380 万1-2/19941 亿1-2/19972 亿进行上千个国内航线的飞机优化配置来最大化利润重新设计北美生产和分销系统以降低成本并加快了市场进入速度2、根据您所学的 运筹学及其它学科知识， 谈谈您对“运筹帷幄， 决胜千里” 的理解；语出，意思是说，张良坐在军帐中

16、运用计谋，就能决定千里之外战斗的胜利，这说明张良心计多，善用脑，善用兵，后来人们就用“运筹帷幄”表示善于策划用兵。学习中， 我们应当努力学习运筹学的理论知识， 并将理论知识付诸实践， 在学习其他学科时，运用运筹学的知识， 比如在写毕业论文时， 运用运筹学的知识， 丰富论文内容，为论文增加支撑理论。生活中， 我们面对任何问题都要仔细思考， 运用运筹学的知识， 更好地解决问题，而现在网络及通讯工具的不断发展， 让我们远在千里之外也可以解决问题， 如：越来越多的跨国公司， 不仅仅是局限于面对面的交谈， 很多网络会议或电话会议，让解决问题更加方便迅速。在企业管理中，生产计划、市场营销、库存管理、人事资

17、源、运输问题等。3、请论述如何把你所学的运筹学的知识应用到今后的管理实践中去；答：（1）对运筹学的知识体系了若指掌。 （2）处理管理实践的问题时，有意识的使用运筹学的知识体系和方法来解决。 （ 3）需要有很强的归纳总结能力， 把在实践中遇到的问题，转化为运筹学书上的问题来解决，如：背包问题、七桥问题。以上三者缺一不可，遇到问题，首先想到解决该问题需要哪些资源，从哪里 可以获得这些资源； 其次考虑再获得资源后， 如何使这些资源得到最合理的利用， 使其产生最大效益。 另外， 强化管理， 不断进行管理刨新已成为企业在竞争中制胜的根本保证。 作为企业的管理者， 把握并运用好运筹学的理念定会取得“运筹帷

18、幄之中，决胜千里之外”之功效。4、请简要列举（至少 3）我国古代朴素的运筹学思想，并论述其间的运筹学原理。（4 个）答：（1）孙子兵法与运筹学思想。 孙子兵法在表达军事思想的同时，也蕴藏着丰富的运筹学思想 -军事运筹学。 孙武在孙子兵法 中灵活运用整体性原则研究军事问题， 采用定量分析方法谋划战争， 运用优化原则进行科学决策。（2） 田忌赛马。战国时期的“田忌赛马”是运筹思想的一次完美应用。整 个赛马过程中， 孙膑巧妙地运用了一种科学合理的方法博弈论。博弈论是运筹学的一个分支， 是指二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。 通过博弈论的思想， 孙膑指出用本方的下

19、马对齐王的上马，用本方的上马对齐王的中马， 用本方的中马对齐王的下马。 最终以一负两胜取胜。孙膑成功地将本方劣势转为优势，赢得了比赛。（3） 围魏救赵。魏国攻打赵国，赵国求救于齐。孙膑指出应趁魏国国内兵力空虚之际，发兵直取魏都大梁， 迫使伪军弃赵回救。最终这一战略取得了胜利。其中的战略思想， 妙在善于调动第二年。 调动敌人的要诀， 在于“攻其所必救”。这充分体现了如何策划兵力，选择最佳时间、地点，趋利避害，集中优势兵力以弱克强的运筹思想。（4） 沈括运军粮：沈括曾经从行军中各类人员可以背负粮食的基本数据出发，分析计算了后勤人员与作 战 兵士 在不 同 行军 天数 中的 不 同 比例 关系 ，

20、同 时 也 分 析 计 算 了 用各 种 牲 畜 运 粮 与人 力运 粮 之 间 的 利 弊， 最后 做出 了 从敌 国 就 地征 粮 ， 保障 前 方供 应的 重 要决 策， 从而 减少 了后 勤 人员的比例，增强了前方作战的兵力。这种军事后勤问题的分析计算是具有现代意义的运筹思想的范例。（5） ）晋国公重建皇城的施工方案，体现了运筹学的朴素斯思想。要使重建工程的各个工序，在时间、空间上彼此协调，环环相扣，就需要运用行列式的相关知识，进行精确计算。1. 影子价格 : 当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量。（影增）2. 对偶价格 : 当约束条件中的常数项增加一个单位时，最优目标函数值改进的数量。3. 灵敏度分析 : 对系统或事物因周围条件变化显示出来的敏感程度分析。4.0-1 规划: 所有决策变量只能取 0或 1两个整数的整数线性规划。5. 分支定界法 : 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件， 则求出整数规划的上下界， 用增加约束条件的办法， 把相应的线性规划的可行域分成子区域 （称为分枝），再求解这些子区域上的线性规划问题， 不断缩小整数规划的上下界的距离，最后得整数规划的最优解。6. 生成子图 : 给定一个无向图 g=（ v,e），保留