线性规划初始可行基的选择_第1页
线性规划初始可行基的选择_第2页
线性规划初始可行基的选择_第3页
线性规划初始可行基的选择_第4页
线性规划初始可行基的选择_第5页
已阅读5页，还剩12页未读， 继续免费阅读

下载本文档

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

文档简介

1、高文锋12数基班 126160031单纯形法1.概念2.基本思想3.求解步骤 单纯形法是在高斯消去法的基础上,发展为求解变量数多于方程数,并且使目标函数值优化的方法.返回 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。 返回 单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可

2、行解作为起点，根据最优性条件和可行性条件， 引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。 返回加人工变量大M法: 在一个线性规划问题的约束条件中加入人工变量后,要求人工变量对目标函数取值不受影响,为此假定人工变量在目标函数中的系数(M)(M为任意大的正数),这样目标函数要实现最小化时,必须把人工变量从基变量换出两阶段法: 第一阶段:不考虑原问题是否存在基可行解;给原线性规划问题加入人工变量,并构造仅含人工变量的目标函数和要求实现最

3、小化. 第二阶段:将第一阶段计算得到的最终表,除去人工变量.将目标函数行的系数,换回原问题的目标函数系数,作为第二阶段的计算初始表初始表-31100MM3-4120-1103/2M1-20100011-3+6M1-M1 -3M0M00 最终表-341001/3-2/32/3-5/3110100-11-2 190012/3-4/34/3-7/3 0001/31/3M-1/3M-2/3 不加人工变量 利用这种确定初始可行基的方法求解线性规划问题时，首先，对线性规划模型(1)的系数增广矩阵进行上述的初等行变换而得到rxr阶的初始可行基(rm)，接着将所得初始可行基安排入单纯形表，然后，进行单纯形表的表上作业程序-31100b0123001-24110100-1 11-20100 -10001 -341001/3-2/3 110100-1 190012/3-4/3 0001/31/3 不加人工变量方法的优势在于思路清晰，方法简明在运用单纯形法时不需要判断选择两阶段法或大M法等，只要借助于线性代数的初等行变换及在以单位阵为初始基的单纯形法就可以顺利地求解任何线性规划模型。对于线性规

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论