《最《最优优化化方方法》法》课课程程设设计计题目：两阶段法分析与实现院系：数学与计算科学学院专业：统计学姓名学号：张雨坤1200720216指导教师：李丰兵日期：2015年01月22日摘要常用的解线性规划问题的方法有图解法，单纯形法，对偶单纯形法，解乘数法，椭球法等。而本论文即主要阐述的是从属于单纯形法的两阶段法。两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解，即是一种为使人工变量被替换出成为非基变量的方法。与大M法同时被广为使用，但相较于大M法，两阶段法能够求的更准确地结果。关键词：线性规划；单纯形法；两阶段法；大M法AbstractWeusuallysolvethelinearprogrammingproblemswithgraphicmethod,simplexmethodanddualsimplexmethod,themultipliermethod,ellipsoidmethodandsoon.Thispapermainlyexpoundsthetwostagemethodwhichbelongstosimplexmethod.Thefirststageoftwostagemethodisusedtosolveaobjectivefunctionwhichonlycontainsartificialvariableslinearprogrammingproblem.Whenthefirstphaseofsolvingresultsshowthattheproblemhasafeasiblesolution,thesecondstageisfromthefirststageofthefinalsimplextableau,removeartificialvariables,andaccordingtotheproblemsoftheoriginalobjectivefunction,continuetolookfortheoptimalsolutionoftheproblem.Itisakindofwaytomakeartificialvariablessubstitutedthenonvariablemethod.ThebigMmethodisalsowidelyusedatthesametime,butcomparedwiththebigMmethod,two-phasemethodcanmoreaccurateresults.Keywords:;Linearprogramming；Simplexmethod;Twostagemethod;ThebigMmethod;目录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、总结.....................................