基本概念-运筹学_第1页
基本概念-运筹学_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论