《两阶段法分析与实现运用分享》由会员分享，可在线阅读，更多相关《两阶段法分析与实现运用分享（17页珍藏版）》请在金锄头文库上搜索。
1、最 优 化 方 法课 程 设 计题 目： 两阶段法分析与实现 院 系： 数学与计算科学学院 专 业： 统计学 姓名学号： 张雨坤 1200720216 指导教师： 李丰兵 日 期： 2015 年 01 月 22 日教资c类摘 要常用的解线性规划问题的方法有图解法，单纯形法，对偶单纯形法，解乘数法，椭球法等。而本论文即主要阐述的是从属于单纯形法的两阶段法。两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解，即是一种为使人工变量被替换出成为非基变
2、量的方法。与大M法同时被广为使用，但相较于大M法，两阶段法能够求的更准确地结果。关键词：线性规划；单纯形法；两阶段法；大M法教资c类Abstract We usually 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
3、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
4、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
5、same time, but compared with the big M method ,two-phase method can more accurate results.Keywords:;Linear programming；Simplex method;Twostagemethod;ThebigMmethod;教资c类目 录1、引言12、两阶段法描述12.1 基本可行解12.2 两阶段法概述12.3 两阶段法第一阶段22.4 两阶段法第二阶段.33、两阶段法求解引例43.1 两阶段法计算步骤43.2 例153.3 例283.4 引例分析94、算法比较94.1 大M法94.2 算法
6、比较104.3 特殊情况115、总结125.1 总结概括125.2 个人感言126、参考文献：13教资c类1、引言在各种优化算法中，两阶段法（Twostagemethod）是非常重要的一种。即如果线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人工构成一个单位向量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解的一种方法.把增加人工变量的线性规划问题分为两个阶段去求解.第一阶段是构造一个辅助的人工目标函数,即或。若原问题有可行解,则在本阶段的最终单纯形表中,必有和,并使人工变量均为非基变量.此时,划去人工变量所在的
7、列与人工目标函数所在的行,就得到原问题的初始可行基对应的单纯形表,进入第二阶段.2、两阶段法描述2.1 基本可行解当线性规划问题的玉树条件全部为“”时，可按下述方法比较方便的寻找可行解：设给定线性规划问题为在第个约束条件上加上松弛变量，化为标准形式由于这个系数矩阵中含一个单位矩阵，只要以这个单位矩阵作为基，就可以立即解除基变量值，因为有，由此就是一个基可行解。当线性规划中约束条件为“”、“ ”时，化为标准形式后，一般约束条件的系数矩阵中不包括有单位矩阵。这是为能方便地找出一个初始的基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于零的剩余变量（也
8、称为松弛变量）化为等式，然后再添加一个人工变量。2.2 解线性规划概述两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取0，人工便灵的系数取某个正的常数，（一般取1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0。这时候的最优解就是原线性规划问题的一个可行解，。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯性表出发，去掉人工变量，并按问题原来的
9、目标函数，继续寻找问题的最优解。2.3 两阶段法第一阶段两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取0，人工便灵的系数取某个正的常数，（一般取1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0。这时候的最优解就是原线性规划问题的一个可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。两阶段法第一阶段是求解第一个LP。首先我们可以知道，原LP的表达式为其可行域为而我们需要一个辅助的LP，其表达式为其可行域
10、为我们计算以上辅助LP有三种可能结果：1)、最优值，且人工变量皆为非基变量。从第一阶段的最优解中去掉人工变量后即为原LP的一个基本可行解。作为原LP的一个初始基本可行解，再求原问题，从而进入第二阶段。2)、最优值，且存在人工变量皆为基变量，取值为。把某个非基变量与该人工变量进行调换。 3)、最优值，说明至少有一个人工变量不为。原LP无可行解，不需要再做第二阶段计算。两阶段法第一阶段目的就是判断原LP有无可行解，若有，则可得原LP的一个初始基本可行解，再对原LP进行第二阶段的计算。2.4 两阶段法第二阶段以第一阶段求得最优解作为初始基本可行解，再用第一阶段求得最优解时的约束条件和原问题的目标函数
11、进行迭代，直到求出最优解。3、两阶段法求解引例3.1、两阶段法计算步骤两阶段法具体计算步骤：第一步：求出线性规划的初始基可行解，列出初始单纯形表。第二步：进行最优性检验。第三步;从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。第四步：重复第二、三步一直到计算终止。第五步：去除人工变量。根据求得初始基本可行解，求得最优解。 其中第三步具体方法如下：1)、确定换入基变量。只要检验数，对应的变量就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大的一个其对应变量作为换入基的变量（简称换入变量）。2)、确定换出基的变量，确定确定为换出基的变量（简称出基变量）。元素决
12、定了从一个基本可行解到另一个可行解的转移去向，取名主元素。3)、用换入变量替换基变量中的换出变量，得到一个新的基。对应这个基可以找出一个新的基本可行解。并可划出一个新的单纯形表。进行如下计算:a、将主元素所在的行数字除以主元素，即有b、为使列变换成单位向量，将单纯形表的第行数字乘上，加到单纯形表第行数字上，计入其相应行。即有c、计算单纯形表中各检验数，如下由上可看出，检验数计算同样因基变量后，其检验数应为零，故将单纯形表中第行数字乘上加到该表的检验数上，得新的变量的检验数。 接下来在引例中用以上步骤实际求解3.2、例一：用两阶段法求以下问题最优解首先第一阶段是将此问题化为标准形式，在约束条件中
13、加入松弛变量后得先用单纯形法解一阶段问题，迭代如下：其中，时目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。求解过程如下单纯形表3-1表3-1单纯形表00000-1-1基041211000-11-2-10-110-190310001-2400-10003 30211-1001-21-10-110-1660403-3160403-4000000103010000110000000-1-1所有判别级数，因此达到最优解，在第一阶段问题最优解中，人工变量、都是非基变量。因此我们可得到初始基可行解第二阶段是将表3-1中的人工变量去除，目标函数改为：再从表3-1最后一个表出发，继续迭代，求解过程的单纯形表如下表3-2表3-2单纯形表-30100基000001030100-31100003000000101001010000得到其最优解，所以目标函数最优值3.3、例二：用两阶段法求解以下问题首先第一阶段是将此问题化为标准形式，在约束条件中加入松弛变量后得先用单纯形法解一阶段问题，迭代如下
