基本概念-运筹学.docx

精品文档，仅供学习与交流，如有侵权请联系网站删除割平面法用割平面法求解整数规划的基本思路：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)而把所有的整数解都保留下来，故称新增加的约束条件为割平面分支定界法分支定界法基本思路：设最大化的整数规划问题为A, 相应的不含整数约束的线性规划为B, 若B 的最优解不符合A 的整数条件, 那么B 的最优目标函数值必为A 的最优目标函数值Z* 的一个上界, 记作Z; 而A 的任意可行解的目标函数值将是Z* 的一个下界, 记作Z。对B 的非整数解的相邻整数作附加条件, 从而形成两个分枝, 即两个子问题, 两个子问题的可行域中包含原整数规划问题的所有可行解。不断分枝, 逐步减小Z, 增大Z, 最终求得Z* 。隐枚举法：一种特殊的分支定界法。利用变量取值的部分组合求取目标函数最优值的一种方法。通过探求整数规划的一个可行解，将其作为过滤条件，检验约束条件、计算目标函数值来简化计算。对0-1规划问题.利用变量只能取0或1的两个值的特性，进行分支定界，以达到隐枚举的目的单纯形法单纯形法的基本思想：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进后更优的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。基：在一个m*n维线性方程组中，假设其系数矩阵为A，若m*m唯矩阵B为A的一个最大线性无关组，且其秩为m，则称B为该问题的一个基。基本解：在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解，这个解称之为线性规划的基本解。基可行解：在线性规划问题中，满足非负约束条件的基本解，称基本可行解，简称基可行解.线性规划问题如果有可行解，则必有基可行解.最优解不一定是基本最优解。因为在多重最优解里，最优解也可以是基本最优解的凸组合。普通单纯形法比值规则失效说明问题无界。运输问题的位势就是其对偶变量。运输问题的检验数就是对偶问题的松驰变量。若运输问题的供给量与需求量为整数，则一定可以得到整数最优解，按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路。运输问题中运价表的每一个元素都分别乘以（加上）一个常数,则最优解不变。单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。单纯形法计算中，选取最大正检验数对应的变量作为换入变量，不一定使目标函数值得到最快的增长。线性规划问题的可行解如为最优解，则该可行解不一定是基可行解。【精品文档】第 2 页