两阶段法分析与实现

《《最最优优化化方方法法》》课课程程设设计计题目：两阶段法分析与实现院系：数学与计算科学学院专业：统计学姓名学号：张雨坤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、总结.....................................................................................................................125.1总结概括.........................................................................................................125.2个人感言.........................................................................................................126、参考文献：.......................................................................................................13最优化方法课程设计11、引言在各种优化算法中，两阶段法（Twostagemethod）是非常重要的一种。即如果线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人工构成一个单位向量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解的一种方法.把增加人工变量的线性规划问题分为两个阶段去求解.第一阶段是构造一个辅助的人工目标函数,即0,0aaAxxbxx或max()iZy。若原问题有可行解,则在本阶段的最终单纯形表中,必有0Z和0(1,2,,)iyim,并使人工变量均为非基变量.此时,划去人工变量所在的列与人工目标函数所在的行,就得到原问题的初始可行基对应的单纯形表,进入第二阶段.2、两阶段法描述2.1基本可行解当线性规划问题的玉树条件全部为“”时，可按下述方法比较方便的寻找可行解：设给定线性规划问题为11max(1,,)..0(1,,)njjjnijjijjzcxaxbimstxjn在第i个约束条件上加上松弛变量(1,,)sixim，化为标准形式111max0(1,,)..0(1,,)nmjjsijinijjsiijjzcxxaxxbimstxjn最优化方法课程设计2111212122212100010001nnmmmnaaaaaaaaa由于这个系数矩阵中含一个单位矩阵1(,,)ssmPP，只要以这个单位矩阵作为基，就可以立即解除基变量值(1,,)siixbim，因为有0(1,,)ibim，由此1(0,,0,,,)TmXbb就是一个基可行解。当线性规划中约束条件为“”、“”时，化为标准形式后，一般约束条件的系数矩阵中不包括有单位矩阵。这是为能方便地找出一个初始的基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于零的剩余变量（也称为松弛变量）化为等式，然后再添加一个人工变量。2.2解线性规划概述两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取0，人工便灵的系数取某个正的常数，（一般取1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0。这时候的最优解就是原线性规划问题的一个可行解，。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯性表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解。2.3两阶段法第一阶段两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取0，人工便灵的系数取某个正的常数，（一般取1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0。这时候的最优解就是原线性规划问题的一个可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可最优化方法课程设计3行解。两阶段法第一阶段是求解第一个LP。首先我们可以知道，原LP的表达式为1min..0njjjzcxAxbstx其可行域为:0xxDxDDa而我们需要一个辅助的LP，其表达式为1min..0,0miiwaAxabstxa其可行域为:min00xDDw我们计算以上辅助LP有三种可能结果：1)、最优值0w，且人工变量皆为非基变量。从第一阶段的最优解中去掉人工变量后即为原LP的一个基本可行解。作为原LP的一个初始基本可行解