运筹学习题重点.docVIP

制定决策是运筹学应用的核心，而建立模型则是运筹学方法的精髓 2、运筹学研究的基本特征:系统的整体观念;多学科的综合;模型方法的应用 3、线性规划问题的数学模型的组成要素：决策变量;目标函数;约束条件 4、可行域是非空有界或无界的凸多边形,也可能为空集。 5、可行域为有界时，一定有最优解 6、可行域为无界时，可能有最优解，也可能无最优解 7、可行域为空集，一定没有最优解 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 8、线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。线性规划问题的基可行解X对应于可行域D的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。 9、线性规划问题的可行域是凸集。若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。 10、对偶问题的基本性质：弱对偶性、最优性、无界性、强对偶性、互补松弛性（在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非0，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0.）、线性规划的原问题与其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量 11、运输问题数学模型的特点： 决策变量的个数为m×n个。约束条件的个数为m+n个。 运输问题的解中的基变量数一般为m+n-1个。 运输问题的约束方程组系数矩阵中，变量xij对应的系数列向量可表示为： 12、表上作业法适合于产销平衡的运输问题 13、整数规划最直观的求解方法就是枚举法。 14、分配问题也称指派问题，是一种特殊的整数规划问题 15、匈牙利法： 从矩阵未被直线覆盖的数字中找出最小数k； 对矩阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖时，令ui=k；对矩阵中有直线覆盖的列，令vj=-k，对无直线覆盖的列vj=0； 每行每列都出现打()的0元素，这时已得到最优解 16、线型规划模型的局限性：严格满足全部约束条件；只能处理单目标的规划问题；各个约束条件都处于同等重要的地位。 线性规划寻求的是最优解，而现实中通常找到满意解即可。 17、当希望恰好达到目标值时，目标规划目标函数形式为： 当希望实际值超过目标值时，目标规划目标函数形式为： 18、PkPk+1权系数是一个具体数字，系数越大，表明该目标越重要 19、 【例】某单位考虑职工的升级调资方案，依次遵循以下规定： （1）不超过年工资总额60000元； （2）每级的人数不超过定编规定的人数； （3）Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升； （4）Ⅲ级不足编制的人数可录用新职工，又Ⅰ级职工中有10%要退休。 有关资料如下表，问如何拟定一个满意方案。 等级 工资额（元/年） 现有人数 编制人数 Ⅰ Ⅱ Ⅲ 2000 1500 1000 10 12 15 12 15 15 合计 37 42 解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工数。 确定各目标的优先因子P： P1——不超过年工资总额60000元； P2——每级的人数不超过定编规定的人数； P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。 分别建立各目标约束。 1.年工资总额不超过60000元： 2000（10-10*0.1+x1）+1500（12-x1+x2）+1000（15-x2+x3）+d1--d1+=60000 2.每级的人数不超过定编规定的人数： Ⅰ级：10（1-0.1）+x1 +d2--d2+= 12 Ⅱ级：12-x1+x2 +d3--d3+=15 Ⅲ级：15-x2+x3 +d4--d4+=15 3.Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。 Ⅱ级：x1 +d5--d5+=12*0.2 Ⅲ级：x2 +d6--d6+=15*0.2 目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-) 20、图是对现实世界的一种抽象描述，表现为点和线的几何。 21、图的最基本的要素是点以及点与点之间的一些连线，点v表示我们要研究的对象，线e表示对象之间的某种特定关系。记作G={V，E} 22、 23、一个图中，如果每一对顶点之间至少存在一条链，称为连通图 24、一个无圈的连通图称为树，记作T（V，E） 25、 26、求最短路有两种算法：一是求某一点至其他各点之间最短距离的Dijkstra算法；另一种是求任意两点之间最短距离的矩阵算法。 27、所谓网络上的流，是指定义在弧集合 上的一个函数f={fij} 28、容量限制条件