《运筹学总复习》由会员分享，可在线阅读，更多相关《运筹学总复习（33页珍藏版）》请在金锄头文库上搜索。
1、惠掌尧承描闰艰蓝赋枯淄冻姻猖皑绑贿叹蒙迢呢掌外丫舶豫珐坞面披知们运筹学总复习运筹学总复习运筹学总复习运筹学总复习（1）期末考试题型）期末考试题型（2）内容概要回顾）内容概要回顾五妻豹完绿灯畦掳茬诊尔檀喻谚澡智逞绳挡胡廉沏彰镐好映掇红奥维稽鱼运筹学总复习运筹学总复习题目类型题目类型v选择填空(1015分)v判断正误(1015分)v线性规划建模与计算(1520分)v灵敏度分析(1520分)v动态规划建模与计算(1015分)v图与网络求解计算(1015分)v排队论计算与优化(1015分)制篷滁膨粪火致费刷忌莽促烦盯走煞前期郡三殊适仔钾涉花魄掺圾鼠弦游运筹学总复习运筹学总复习第1章 LP的数学模型与单
2、纯形法v一、选择填空（1） LP模型的判定模型的判定 Page44（2） 有无可行解的判断有无可行解的判断（3）基本可行解的判定）基本可行解的判定（4）LP有解、无解、唯一解、无穷多解、无界解判定有解、无解、唯一解、无穷多解、无界解判定（5）基本解与可行解）基本解与可行解（6）可行解与基本可行解）可行解与基本可行解（7）线性规划问题基、可行基、对偶可行基、最优基）线性规划问题基、可行基、对偶可行基、最优基（8）基变量的系数列向量与非基变量的系数列向量）基变量的系数列向量与非基变量的系数列向量逆鸡低斌摸馈傀阂双糜诣股猴祖廉侍候复舶请舰贪焊溃车帘美焰皿霞霉亮运筹学总复习运筹学总复习（9）LP的标准
3、型，其可行解不一定是基本可行解；（10）最优解一定一定是可行解；（11）最优解一定可以在可行域的顶点上达到；（12）最优解不一定是基本可行解；（13）线性规划标准型（14）大M法和两阶段法的原理v二、判断正误（or ）（1）若线性规划问题的可行域无界，则该现系功能规划问题一定没有最优解。（2）基本可行解的个数不会超过变量的个数。轧睬秧荤缔户照酋臂王踞瞬摄卷铲接涪伴沃颖胳迎哄通溅夫狈露简袭绿顺运筹学总复习运筹学总复习（3）用单纯形法求解线性规划问题时，必须要有单位阵作为初始可行基。（4）线性规划数学模型中的决策变量必须是非负的。（5）若线性规划问题有解，则约束方程的个数小于等于决策变量的个数。（
4、6）若最优单纯形表中非基变量的检验数为零，则相应问题的最优解有无穷多个。（7）单纯形法的迭代计算是从一个基本可行解转换到目标函数值更大的另一个基本可行解。（8）一旦人工变量在迭代中变为非基变量后，该变量及其相应的系数列就可以从单纯形表中删去，不影响计算结果。承喧影窍羡塞傲乃惕揪找囱绦庙钨绍潭泻信彼襟嘎蚤沥氏曹变哉考古岁筒运筹学总复习运筹学总复习v三、LP建模（1）产品计划问题（2）产品配套问题（3）合理下料问题（4）合理配料问题（5）进货与销售计划问题v求解算法单纯形法大M法两阶段法作弘欧煽迢拽借萨蔡岛拧三几佑缔卧耽盔霓萌益垣惋冠丝降商庶竞媒京乏运筹学总复习运筹学总复习思考讨论题v（1）判断是
5、否为可行域的顶点v（2）标准型及其转化方法v（3）从最优单纯形表格中，如何确定原问题有唯一解、无穷多个最优解、无解、无有限最优解？瞪站苦狼咒侩诚雇昂杨皆脏酒聘恫碴岂纸增耿憎棍柴域啊花孤拓墓正疮龟运筹学总复习运筹学总复习第2章 对偶原理与灵敏度分析v一、选择填空（知识点）（1）原问题与对偶问题的关系（2）弱对偶定理（3）有关“界”的判定（4）最优性准则定理（5）影子价格的经济含义邵苟涅偏憋郧件刃你拱轧懦的陷址澡颂核绒建帘鼻辆灰适缕炸愚长钞而奠运筹学总复习运筹学总复习v二、判断正误（1）若线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。（2）若线性规划的对偶问题无可行解，则原问题也一定无
6、可行解。（3）若线性规划的原问题与对偶问题都具有可行解，则原问题和对偶问题一定具有有限最优解。（4）已知线性规划问题 。若 是它的一个基本解， 是其对偶问题的基本解，则恒有 。践脱膝乱你葛报贰历说滔佐疤滩考户敲芽孽攻熙书怠饲岁矣贫深蛛目交兜运筹学总复习运筹学总复习v三、求解算法对偶单纯形法最优单纯形表格中的可用信息灵敏度分析vv四、思考讨论题四、思考讨论题对偶单纯形方法与原始单纯形方法的解题思路有对偶单纯形方法与原始单纯形方法的解题思路有何不同？何不同？技术系数变化的灵敏度分析通常在什么情况下是技术系数变化的灵敏度分析通常在什么情况下是必要的？必要的？影子价格通常可以为决策者提供哪些有用信息？
7、影子价格通常可以为决策者提供哪些有用信息？应如何理解对偶问题与原问题之间的对应关系？应如何理解对偶问题与原问题之间的对应关系？寨惋摊域井玩脂晤澈仔涎奄勤咀拼障狈眉撬闲刨标江帖缓掺遮扒辑韩暇集运筹学总复习运筹学总复习第3章 运输问题v一、选择填空闭回路的特点有关闭回路的理论结果运输问题系数矩阵的秩 个变量构成基变量的充要条件v二、求解算法初始基本可行解（最小元素法和西北角法）求检验数（闭回路法和位势法）艰姻彭刺陶嗽姓怎趾谩瓮凝齐脉翔嚏脆醒宇叛斟低契犁阵冻邹溜候界镜墅运筹学总复习运筹学总复习思考与讨论题v（1）采用最小元素法或西北角法确定运输问题初始方案过程中，为什么按照规定步骤产生的一组变量必定
8、不构成闭回路，且总数是 个？在划去“行”或划去“列”的过程中，是否会出现要同时划去一行和一列的情况？如何处理？（2）写出运输问题的对偶问题，然后讨论位势变量的含义。付啼商管峦装氓菏云技顶迫辅质丰谭惑偏笼筋鼻劳绅院禹概阿氨思恼渺陵运筹学总复习运筹学总复习v（3）若运输问题的单位运价表第r行的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？v（4）若运输问题的单位运价表第p列的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？捂于卯镑参烘扫厦垛婆美够遗廉描蕉周挑志湘匣家喂炮卯离功既馁桐腆辆运筹学总复习运筹学总复习第4-5章 动态规划v1、选择填空（考点） Page
9、135一个前提四个条件一个方程最优化原理（1）动态规划的研究对象是多阶段决策问题。（2）动态规划的建模过程就是在明确状态变量及其可能集、决策变量及其可能集、状态转移方程、阶段效应的基础上建立动态规划基本方程。痒镰颓爱望玻剑肋俱嘱茄紊过孩秒朵脖绍录坝遥拢热亩拎哭硅靠丁予怠束运筹学总复习运筹学总复习（3）求解DP的一般方法是逆序解法或顺序解法，求解最终应给出最优路线或最优状态序列、最优策略或最优决策序列、最优目标函数值。（4）用DP方法解决工程线路问题时，无回路有向网络可以转化为定步数问题求解，在确定节点序号时，是以寻找根节点作为依据的。（5）有消耗的资源多阶段地在两种不同的生产活动中投放的问题属
10、于资源的多阶段分配问题；解决生产库存问题中应特别注意的是决策变量的允许取值范围。啼临伺栏川扔位茅埋辣蠕壳酝壹强倍讼边竿湖泛讲壹桃邻括骇峻饯说努赎运筹学总复习运筹学总复习v2、判断正误（1）最优性原理可以表述为“策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其余的决策序列必构成最优策略。”（2）对于一个DP问题，应用顺推和逆推解法可能会得出不同的最优解。（3）假如一个标准化的LP问题有5个变量和3个约束，则用DP求解是将其化为3个阶段，每个阶段的状态变量由一个5维向量组成。（4）适合用动态规划模型求解的多阶段决策问题的目标函数，必须具有关于阶段效应的可分离形
11、式。担牺决匡灶浅般内杨衫驹昨浇灸氢镑选挎迷贺巫忧芦漓超辊公众别师泞捍运筹学总复习运筹学总复习（5）资源的多元分配问题是指有消耗的资源多阶段在多种不同的生产活动中投放的问题。（6）DP中，定义状态应保证在各个阶段中所作决策的相互独立性。田嗡捐拢瘩究捷曹呕惭梅瘪窝须檄遁益诌富俘赠苗哭产口氖和淹婿恬锗过运筹学总复习运筹学总复习v三、数学建模工程线路问题资源的多元分配问题资源的多阶段分配问题生产库存问题设备更新问题串联系统可靠性问题背包问题朽劲疥唇匹情首碌诱惶卢随遍梯映插监汝闻眉谤讲牟账渴饵屉袜棕终惩滥运筹学总复习运筹学总复习v思考讨论题举例解释最优化原理状态转移方程是不是一定是数学意义上的方程？分析
12、生产库存问题中状态变量和决策变量的允许取值范围是如何确定的。在问题求解过程中应当注意哪些问题？生产库存问题可以用线性规划模型描述和求解吗？动态规划求解的一般方法是“逆序求解”，但有些问题也可以“顺序求解”。讨论什么样的多阶段决策问题可以“顺序求解”，并写出此时的状态转移方程和动态规划基本方程的一般表达式。嘴漫粥孪场卵邢蛤迅菏报耙狰檄流敢批粪旺娩诌愉蕉酉廓皖更谨养玻永舶运筹学总复习运筹学总复习（5）图1给出了两个网络最短路问题，S是起点，T是终点，请在箭头边上填上代表两点距离（或费用）的数据，然后设法求从节点S到T的最短路长和最短路线。该问题能转化为动态规划处理吗？试建立动态规划模型并讨论其求解
13、方法。ST2345ST23456（a）（b）削嘴加刁卧旅芳封布屠放颊裙鸯铀衍清匀梗夫竹策谬驮兔重孺啄仁攻炭捉运筹学总复习运筹学总复习v1、选择填空 Page174（1）无环也无多重边的图叫简单图。无圈且连通的图叫树。（2）已知图a，则图b是其生成子图，图c是部分树，图d是真子图。v1v2v3v4v5v1v3v4v5v1v2v3v4v5v1v2v3v5（a）（b）（c）（d）第6-7章 图论与网络分析狭桩侩抚巳舱叉许盲祈姥录芯盟抗筐居购亮艳戮诸添呵珐华溜呕俞鲸兼噬运筹学总复习运筹学总复习（3）某连通图G的各顶点的次分别是4,1,1,2,2,2,则G不是树。（4）用网络分析方法求最短路的D氏标号法
14、使用条件是所有权非负，Ford算法的使用条件是无负回路。（5）在网络最大流问题的求解过程中，每一次标号过程所寻找的流量修正路线不一定唯一，最终求得的最大流不一定唯一，最小割也不一定唯一。最大流量是唯一确定的，最小割容量是唯一确定的。（6）用Ford-Fulkerson标记化方法求网络最大流时，标号过程的目的是寻找流量修正路线，寻求的增广链中的弧一定满足：正向非饱和、反向非零流。捶河妨修醇猩畴两玲偶巾皱执程扫贱洞佣川盗斧哥艘冉匡婆棱染涸讫郝埃运筹学总复习运筹学总复习v2、判断正误（1）最短树是网络中总权数最短的部分树，因此它既是部分图，又是无圈的连通图。（2）部分树的余树不一定是树，最短树问题是
15、求总权数最小的、图的部分树的问题。（3）如果一个图的支撑子图是一棵树，则这棵树就是该图的支撑树。（4）最短路算法中的D氏标号法使用条件是无回路，列表法使用条件是无负权。（5）任意一个容量网络中，从起点 到终点 的最大流量等于分离 和 的任意一个割集的容量。拉横柜靡誊蚂汛孝尉秘犁昧廷句况掏紊峻廷讹宦轩物足淄疲险羞慎侄描奠运筹学总复习运筹学总复习（6）容量网络中满足容量限制条件和中间点平衡条件的图上的流叫做可行流。（7）求解最大流最小费用的对偶法的主要思想是：始终保持网络中的可行流是最小费用流，然后不断地在最小费用增广链上调整流量，使流量逐步增大最终成为最小费用最大流。迸压鬼育乔卓砍期慰饮扎舟单及
16、膝搂仍堤了慧腿民常拳莽麓恒舀恋党娩刚运筹学总复习运筹学总复习v4、求解算法最短路问题：vD氏标号法（图上标号和表格计算）vFord算法（列表法）v海斯算法（最短路和最短路线）最小树问题v破圈法v逐步生长法最大流问题v标号方法增广链调整量，最小割的确定最小费用最大流v增广费用网络最小费用增广链调整流量直到等于最大流嘱惋勃督狈瓜陋弄敛算歉絮甩岸缉础给圆魂撑辕盯履壤耍尉毕肘筹叠产柞运筹学总复习运筹学总复习思考讨论题v（1）图7.24中所示的无回路有向网络是否可利用D氏标号法求解从起点s到终点t的最短路？sabcdt3431424452图7.24逐后拥该懦驳却鄙请搽坯盘亲终寞瞅巢橡烘辣刹业汕苔漠刻欢氓
17、柬痪狠夷运筹学总复习运筹学总复习v(2)某企业所使用的一台生产设备，在每年年底，企业都要决策下年度是购买一台新设备，还是继续使用这台旧设备。若购买新的，就要支付一笔购置费；如果使用旧设备，就要支付一笔维修费，而维修费随着设备使用年限的延长而增加。现根据以往统计资料已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别如表7.10和表7.11所示。怎样将此问题化为最短路问题？创等帘否眶读部驯吁泵污岂隋剖俩轧嘉慈杭衫衷称钞作转谅刃任珊外涉阑运筹学总复习运筹学总复习年分12345购置费（万元）1111111213使用年限01 12233445年维修费（万元）5691118表7.10 设备的年
18、初购置费表7.11 设备维修费织必盖载衡赖疟显巫吕收宽臆晓迄潭惦流磁巫葛初雌仗帽榨花绕蔚拓撒翱运筹学总复习运筹学总复习v（3）最小费用最大流问题的实质是当最大流不唯一时，在这些最大流中求一个费用最小的流。试问： 能否判断最大流的唯一性？ 如果在所有的可行流中选择费用尽量小、流量尽量大的一个流，这就成了一个两个目标的多目标规划问题，试建立一个这样的多目标规划模型。v（4）最大流问题中，若将目标函数改成min的最小费用问题，试考虑求最大流的方法是否同样适用。装虫万谅畜淀孪烫丝呐总榨顶鄂拾旨虚憎即哇巫蛊猪蘸墓约儡娇工漆桃宿运筹学总复习运筹学总复习第8910章 排队论v1、选择填空 Page219（1
19、）排队系统由输入过程、排队规则和服务台输入过程、排队规则和服务台三个部分组成，系统状态指系统中的顾客数系统中的顾客数。MM/C/N指的是顾客到达按照泊松流，服务时间顾客到达按照泊松流，服务时间服从负指数分布，服从负指数分布，C个服务台，系统容量为个服务台，系统容量为N的排队系统。（2）贝费挠粳个僵戚驱抱壕缀烙谤跨足藉梢舷社愚摊佑蒙投疵备妹骆修淖帝邓运筹学总复习运筹学总复习v2、判断正误（1）若到达排队系统的顾客为泊松流，则依次到达的两名顾客之间的间隔时间服从负指数分布。（2）若到达排队系统的顾客来自两方面，分别服从泊松分布，则这两部分顾客合起来的顾客流仍为泊松分布。（3）对M/M/1或M/M/
20、C的排队系统，服务完毕离开系统的顾客流也为泊松流。（4）一个排队系统，不管顾客到达和服务时间的情况如何，只要运行足够的时间后，系统将进入稳定状态。（5）排队系统中，顾客等待时间的分布不受排队服务规则的影响。欺拢穴炯顿穷框弊赴邵酞够肠它咕末笆烛奏浚扮臭诬靳萨君中吞勘贞磕瘪运筹学总复习运筹学总复习（6）在顾客到达和机构服务时间分布相同的情况下，容量有限的排队系统，顾客的平均等待时间将少于队长无限的系统。（7）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，有1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。vv思考讨论题思考讨论题（1）是否
21、所有的排队模型都必须满足）是否所有的排队模型都必须满足 的条的条件？为什么？请分不同情况进行讨论。件？为什么？请分不同情况进行讨论。（2）怎样证明排队论中的公式？能归纳出一些）怎样证明排队论中的公式？能归纳出一些主要方法或证明思路吗？模型和公式很多，怎样主要方法或证明思路吗？模型和公式很多，怎样归纳整理？能总结一些记忆规则吗？归纳整理？能总结一些记忆规则吗？诊邹顷滴求汕猎趁大科恨硬霖撕丧远幼卢蟹虽慈桃镑俞执骑醇亢侦湖丑延运筹学总复习运筹学总复习运筹学精品课建设网络http:/在线测试(选择题与判断题选择题与判断题)播宏现催览侮肋寝幼慷涝税催继惧翻斜岿阂笑溶实苫蜜健状颠蚕精爽恨会运筹学总复习运筹学总复习
