两阶段法分析与实现.doc

《最优化方法》课程设计题目:两阶段法分析与实现院系:数学与计算科学学院专业:统计学姓名学号:张雨坤1200720216指导教师:李丰兵日期:2015年01月22日摘要常用得解线性规划问题得方法有图解法,单纯形法,对偶单纯形法,解乘数法,椭球法等。而本论文即主要阐述得就是从属于单纯形法得两阶段法。两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,当第一阶段求解结果表明问题有可行解时,第二阶段就是从第一阶段得最终单纯形表出发,去掉人工变量,并按问题原来得目标函数,继续寻找问题得最优解,即就是一种为使人工变量被替换出成为非基变量得方法。与大M法同时被广为使用,但相较于大M法,两阶段法能够求得更准确地结果。关键词:线性规划;单纯形法;两阶段法;大M法AbstractWeusuallysolvethelinearprogrammingproblemswithgraphicmethod,simplexmethodanddualsimplexmethod,themultipliermethod,ellipsoidmethodandsoon、Thispapermainlyexpoundsthetwostagemethodwhichbelongstosimplexmethod、Thefirststageoftwostagemethodisusedtosolveaobjectivefunctionwhichonlycontainsartificialvariableslinearprogrammingproblem、Whenthefirstphaseofsolvingresultsshowthattheproblemhasafeasiblesolution,thesecondstageisfromthefirststageofthefinalsimplextableau,removeartificialvariables,ordingtotheproblemsoftheoriginalobjectivefunction,continuetolookfortheoptimalsolutionoftheproblem、Itisakindofwaytomakeartificialvariablessubstitutedthenonvariablemethod、ThebigMmethodisalsowidelyusedatthesametime,butparedwiththebigMmethod,two-urateresults、Key  words:;Linearprogramming;Simplexmethod;Two stage method; The big M method; 目录1、引言 12、两阶段法描述 12、1基本可行解 12、2两阶段法概述 12、3两阶段法第一阶段 22、4两阶段法第二阶段、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、33、两阶段法求解引例 43、1两阶段法计算步骤 43、2例1 53、3例2 83、4引例分析 94、算法比较 94、1大M法 94、2算法比较 104、3特殊情况 115、总结 125、1总结概括 125、2个人感言 126、参考文献: 131、引言在各种优化算法中,两阶段法(Two stage method)就是非常重要得一种。即如果线性规划模型中得约束条件系数矩阵不存在单位向量组,阶梯式应先加入人工变量,人工构成一个单位向量组,其只起过渡作用,不应影响决策变量得取值,两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解得一种方法、把增加人工变量得线性规划问题分为两个阶段去求解、第一阶段就是构造一个辅助得人工目标函数,,则在本阶段得最终单纯形表中,必有与,并使人工变量均为非基变量、此时,划去人工变量所在得列与人工目标函数所在得行,就得到原问题得初始可行基对应得单纯形表,进入第二阶段、2、两阶段法描述2、1基本可行解当线性规划问题得玉树条件全部为“”时,可按下述方法比较方便得寻找可行解:设给定线性规划问题为在第个约束条件上加上松弛变量,化为标准形式由于这个系数矩阵中含一个单位矩阵,只要以这个单位矩阵作为基,就可以立即解除基变量值,因为有,由此就就是一个基可行解。当线性规划中约束条件为“”、“”时,化为标准形式后,一般约束条件得系数矩阵中不包括有单位矩阵。这就是为能方便地找出一个初始得基可行解,可添加人工变量来人为地构造一个单位矩阵作为基,称作人工基。先在不等式左端减去一个大于等于零得剩余变量(也称为松弛变量)化为等式,然