基本概念-运筹学.docx

《基本概念-运筹学.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、割平面法用割平面法求解整数规划的基本思路：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止．如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解．这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)．而把所有的整数解都保留下来，故称新增加的约束条件为割平面．分支定界法分支定界法基本思路：设最大化的整数规划问题为A,相应的不含整数约束的线性规划为B,若B的最优解不符合A的整数条件,那么B的最优目标函数值必为A的最优目标函数值Z*

2、的一个上界,记作Z;而A的任意可行解的目标函数值将是Z*的一个下界,记作Z。对B的非整数解的相邻整数作附加条件,从而形成两个分枝,即两个子问题,两个子问题的可行域中包含原整数规划问题的所有可行解。不断分枝,逐步减小Z,增大Z,最终求得Z*。隐枚举法：一种特殊的分支定界法。利用变量取值的部分组合求取目标函数最优值的一种方法。通过探求整数规划的一个可行解，将其作为过滤条件，检验约束条件、计算目标函数值来简化计算。对0-1规划问题.利用变量只能取0或1的两个值的特性，进行分支定界，以达到隐枚举的目的单纯形法单纯形法的基本思想：先找出一个基本可行解，对它进行

3、鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进后更优的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。基：在一个m*n维线性方程组中，假设其系数矩阵为A，若m*m唯矩阵B为A的一个最大线性无关组，且其秩为m，则称B为该问题的一个基。基本解：在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解，这个解称之为线性规划的基本解。基可行解：在线性规划问题中，满足非负约束条件的基

4、本解，称基本可行解，简称基可行解.线性规划问题如果有可行解，则必有基可行解.最优解不一定是基本最优解。因为在多重最优解里，最优解也可以是基本最优解的凸组合。普通单纯形法比值规则失效说明问题无界。运输问题的位势就是其对偶变量。运输问题的检验数就是对偶问题的松驰变量。若运输问题的供给量与需求量为整数，则一定可以得到整数最优解，按最小元素法求得运输问题的初始方案,从任一非基格出发都存在唯一一个闭回路。运输问题中运价表的每一个元素都分别乘以（加上）一个常数,则最优解不变。单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

5、单纯形法计算中，选取最大正检验数对应的变量作为换入变量，不一定使目标函数值得到最快的增长。线性规划问题的可行解如为最优解，则该可行解不一定是基可行解。