两阶段法分析报告与实现.doc

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