两阶段法分析与实现.doc

《最 优 化 方 法》 课 程 设 计 题 目： 两阶段法分析与实现 院 系： 数学与计算科学学院 专 业： 统计学 姓名学号： 张雨坤 1200720216 指导教师： 李丰兵 日 期： 2015 年 01 月 22 日 摘 要关键词 solve the linear programming problems with graphic method, simplex method and dual simplex method, the multiplier method, ellipsoid method and so on.This paper mainly expounds the two stage method which belongs to simplex method. The first stage of two stage method is used to solve a objective function which only contains artificial variables linear programming problem. When the first phase of solving results show that the problem has a feasible solution, the second stage is from the first stage of the final simplex tableau, remove artificial variables, and according to the problems of the original objective function, continue to look for the optimal solution of the problem. It is a kind of way to make artificial variables substituted the non variable method. The big M method is also widely used at the same time, but compared with the big M method ,two-phase method can more accurate results. Key??words:;Linear programming；Simplex method;Two?stage?method;? The?big?M?method;? 目 录 1、引 1 2、 1 2.1 基本可行解 1 2.2 两阶段法概述 1 2.3 两阶段法第一阶段 2 2.4 两阶段法第二阶段...........................................................................................3 3、 4 3.1 两阶段法计算步骤 4 3.2 例1 5 3.3 例2 8 3.4 引例分析 9 4、算法比较 4.1 大M法 9 4.2 算法比较 10 4.3 特殊情况 11 5、总结 125.1 总结概括 5.2 个人感言 6、参考文献： 1、引言 在各种优化算法中，Two?stage?method）是非常重要的一种。或。若原问题有可行解,则在本阶段的最终单纯形表中,必有和,并使人工变量均为非基变量.此时,划去人工变量所在的列与人工目标函数所在的行,就得到原问题的初始可行基对应的单纯形表,进入第二阶段. 2、两阶段法描述 2.1 基本可行解 当线性规划问题的玉树条件全部为“”时，可按下述方法比较方便的寻找可行解： 设给定线性规划问题为 在第个约束条件上加上松弛变量，化为标准形式 由于这个系数矩阵中含一个单位矩阵，只要以这个单位矩阵作为基，就可以立即解除基变量值，因为有，由此就是一个基可行解。 当线性规划中约束条件为“”、“ ”时，化为标准形式后，一般约束条件的系数矩阵中不包括有单位矩阵。这是为能方便地找出一个初始的基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于零的剩余变量（也称为松弛变量）化为等式，然后再添加一个人工变量。 2.2 解线性规划概述 两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取0，人工便灵的系数取