运筹学考试总结

运筹学：线性规划：是求一组非负变量，在满足一组以线性等式或线性不等式所表示的限制条件下，使一个线性函数取得最优值，称这类问题为线性规划（LinearProgramming），简称LP。LP标准型：maxz=s.t．其中xj为决策变量，z为目标函数，aij为技术系数，bi为资源系数，cj为价值系数。3、满足约束条件的任一解称可行解，所有可行解组成的集合称可行域。使目标函数取得最优值的可行解称为最优解，记作X**，最优解对应的目标函数值称为最优值。记作Z*.4、单存形法（SM）基本思想：从一个初始基可行解出发，每次选一个非基变量（入基变量）来取代一个基变量（出基变量），即把一个非基变量从0增加到某一正数，而把相应的一个基变量从一个正数变成0，以此达到改进目标函数值，经多次迭代，目标函数值逐步改进，最终得到最优解。注意：此法是有效的通用方法，解线性规划的图解法虽直观，但多于2个变量情况就不适用了。5、决策者要了解在满足约束的条件下，什么价格得到最低利润，做到洽谈时心中有数，此价格称临界价格，如果等于临界价格，可生产产品销售，也可出售材料，获利相同。高于临界价格，宁可出售材料，比生产产品获利更大。低于临界价格，依然生产产品销售，比直接出售材料获利大。这个临界价格，在经济学上叫影子价格。6、原规划与对偶规划：例：maxz=3x1+4x2s.t.，写出对偶规划。（书P41`）Key：minf=5y1+15y2s.t.较重要的性质：（1）对偶规划的对偶是原规划。（2）设X、Y为原规划与对偶规划的任一可行解，则恒成立z(X)≤f(Y).（3）设X、Y各为原规划与对偶规划的一个可行解，且有z(X)=f(Y)，则X、Y必为最优解。（4）原规划与对偶规划同有最优解，且两者最优值相等。7、灵敏度分析的推广应用：1、增加新的变量2、增加新的约束条件（可能导致最优解恶化）灵敏度分析仅利用最优解对应的基阵B及数据aij（技术数据）、bi（资源数据）、cj（价值数据），经适当的运算，即可求得最优解适用的范围或求出新的最优解。8、整数规划：通常，将变量全部或部分取整数的线性规划统称整数线性规划。简称整数规划。简记作IP。分为两类：纯整数规划和混合整数规划，纯整数规划中其变量只取0或1，称为0-1规划。分支定界法是求解一般整数规划的通用算法，既可用于纯整数规划，也可用于混合整数规划。9、目标规划中目标函数基本形式有三种：（1）达到期望值要求正负偏差同时尽可能小，即minf=f(d-+d+)（2）低于期望值要求正偏差尽可能小，即minf=f(d+)（3）高于期望值要求负偏差尽可能小，即minf=f(d-)10、无环且无多重边的图称为简单图。点v关联边的个数称为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）≤p-1(p个顶点)(2)(q为边数)(3)设G为任何图,则奇点个数必为偶数.12、树：无圈得连通图，记作T。图G的支撑树T中，总权最小的树称为最小支撑树（生成树），简称最小树，记作T*.13决策六要素：决策者、决策目标、可行策略、自然状态、策略后果、策略评价。按决策环境分为确定型、风险型与不确定型。所谓不确定性决策就是决策者对环境完全不清楚的情况下进行决策。14、对策的三要素：局中人、策略和赢得函数（支付函数）。描述对策结果的函数就称为赢得函数。其中策略：一局对策中，每个局中人都有若干供自己选择的可行方案，称为策略。15、存在鞍点的条件：P208aij=aij=ai*j*=v计算题：运输问题（书P57）西北角法（2）※最小元素法（找“1”）（3）差值法，三种方法任选一种注意：做题时建议用最小元素法，较简单！大量计算实践表明，最大差值法所得的初始方案往往优于其他方法得到的初始方案，从而减少迭代的次数。图解法求解有两个决策变量的线性规划问题（书P17）注意：写明最有解X*如：（x1，x2）T和最优值z*找最小生成树（避圈法即Kruskal算法和破圈法即Rosensti