《运筹学考试总结》由会员分享，可在线阅读，更多相关《运筹学考试总结（3页珍藏版）》请在金锄头文库上搜索。
1、运筹1、线性规划：是求一组非负变量，在满足一组以线性等式或线性不等式所表示的限制条件 下，使一个线性函数取得最优值，称这类问题为线性规划（Linear Programming）,简称 LP。2、LP 标准型：maxz= 丫 cjxjs.ta b - b (i - 1,2 m )其中x为决策变量，z为目标函数,Jij j ia为技术系数，b为资源系数，c为价值系数。 ijij3、满足约束条件的任一解称可行解，所有可行解组成的集合称可行域。使目标函数取得最 优值的可行解称为最优解，记作X*，最优解对应的目标函数值称为最优值。记作Z*.4、单存形法（SM）基本思想：从一个初始基可行解出发，每次选一个
2、非基变量（入基变量） 来取代一个基变量（出基变量），即把一个非基变量从0 增加到某一正数，而把相应的一个 基变量从一个正数变成0，以此达到改进目标函数值，经多次迭代，目标函数值逐步改进， 最终得到最优解。注意：此法是有效的通用方法，解线性规划的图解法虽直观，但多于 2 个变量情况就不适用了。5、决策者要了解在满足约束的条件下，什么价格得到最低利润，做到洽谈时心中有数，此 价格称临界价格，如果等于临界价格，可生产产品销售，也可出售材料，获利相同。高于临 界价格，宁可出售材料，比生产产品获利更大。低于临界价格，依然生产产品销售，比直接 出售材料获利大。这个临界价格，在经济学上叫影子价格。6、原规划
3、与对偶规划：例： maxz=3x+4x12 x +2x 512S.t.2x +3x 15，写出对偶规划。(书P41)2 x1+3 x2 4 较重要的性质：（ 1）对偶规划的对偶是原规划。（2）设X、Y为原规划与对偶规划的任一可行解，则恒成立z（X）Wf（Y）.（3）设X、Y各为原规划与对偶规划的一个可行解，且有z（X）=f（Y），则X、Y必为最 优解。（4）原规划与对偶规划同有最优解，且两者最优值相等。7、灵敏度分析的推广应用： 1、增加新的变量2、增加新的约束条件（可能导致最优解恶化） 灵敏度分析仅利用最优解对应的基阵B及数据a （技术数据）、b （资源数据）、c （价i i 值数据），经适
4、当的运算，即可求得最优解适用的范围或求出新的最优解。8、整数规划：通常，将变量全部或部分取整数的线性规划统称整数线性规划。简称整数规 划。简记作IP。分为两类：纯整数规划和混合整数规划，纯整数规划中其变量只取0或 1，称为 0-1 规划。分支定界法是求解一般整数规划的通用算法，既可用于纯整数规划， 也可用于混合整数规划。9、目标规划中目标函数基本形式有三种：（1）达到期望值 要求正负偏差同时尽可能小，即 minf=f（d-+d+）（2）低于期望值 要求正偏差尽可能小，即 minf=f（d+）（3）高于期望值 要求负偏差尽可能小，即 minf=f（d-）10、无环且无多重边的图称为简单图。点V关
5、联边的个数称为V的次或度，记作d （v）或 deg（V），当d（V）=0，v称为孤立点，当d（V）=1，v称悬挂点，当d （v）为大于1 的奇（偶）数，v是奇（偶）点。规定:v有一个环,v的次增加2.11、图论的基本性质：书P126（1）d （v）Wp-1（p 个顶点） 工d （v）二2q （q为边数）veV（3）设G为任何图，则奇点个数必为偶数.12、树：无圈得连通图，记作T。图G的支撑树T中，总权最小的树称为最小支撑树（生成树），简称最小树，记作T*-13 决策六要素：决策者、决策目标、可行策略、自然状态、策略后果、策略评价。按决策 环境分为确定型、风险型与不确定型。所谓不确定性决策就是决
6、策者对环境完全不清楚 的情况下进行决策。14、对策的三要素：局中人、策略和赢得函数（支付函数）。描述对策结果的函数就称为赢 得函数。其中策略：一局对策中，每个局中人都有若干供自己选择的可行方案，称为策 略。15、存在鞍点的条件： P208max mina =min max a =a =vij ij i*j*i j j i计算题：1、运输问题（书 P57）（1）西北角法（2）最小元素法（找“1”（3）差值法，三种方法任选一种。注意：做题时建议用最小元素法，较简单！大量计算实践表明，最大差值法所得的初始方案 往往优于其他方法得到的初始方案，从而减少迭代的次数。2、图解法求解有两个决策变量的线性规划问题（书P17）注意：写明最有解X*如：（X，X2）t和最优值z*3、找最小生成树（避圈法即Kruskal算法和破圈法即Rosenstiehl算法）书P1314、悲观准则与乐观准则（书P180） 悲观准则是“坏中求好”的保守准则，最大最小准则。 乐观准则是“好中求好”的冒险准则，最大最大准则。5、用优超原理求鞍点（书P209）
