两阶段法分析与实现.doc

《最 优 化 方 法》
课 程 设 计
题 目: 两阶段法分析与实现
院 系: 数学与计算科学学院
专 业: 统计学
姓名学号： 张雨坤 1200720216
指导教师: 李丰兵
日 期： 2015 年 01 月 22 日
摘 要
常用得解线性规划问题得方法有图解法，单纯形法,对偶单纯形法，解乘数法,椭球法等。而本论文即主要阐述得就是从属于单纯形法得两阶段法。两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题，当第一阶段求解结果表明问题有可行解时,第二阶段就是从第一阶段得最终单纯形表出发，去掉人工变量，并按问题原来得目标函数，继续寻找问题得最优解，即就是一种为使人工变量被替换出成为非基变量得方法。与大M法同时被广为使用，但相较于大M法,两阶段法能够求得更准确地结果。
关键词:线性规划；单纯形法;两阶段法;大M法
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 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 pared 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、算法比较 9
4、1 大M法 9
4、2 算法比较 10
4、3 特殊情况 11
5、总结 12
5、1 总结概括 12
5、2 个人感言 12
6、参考文献： 13
1、引言
在各种优化算法中,两阶段法（Two stage method)就是非常重要得一种。即如果线性规划模型中得约束条件系数矩阵不存在单位向量组,阶梯式应先加入人工变量,人工构成一个单位向量组,其只起过渡作用，不应影响决策变量得取值，两阶段法即可控制人工变量取值。
寻找线性规划问题初始基可行解得一种方法、把增加人工变量得线性规划问题分为两个阶段去求解、第一阶段就是构造一个辅助得人工目标函数,即或.若原问题有可行解，则在本阶段得最终单纯形表中，必有与,并使人工变量均为非基变量、此时,划去人工变量所在得列与人工目标函数所在得行，就得到原问题得初始可行基对应得单纯形表,进入第二阶段、
2、两阶段法描述
2、1 基本可行解
当线性规划问题得玉树条件全部为“”时，可按下述方法比较方便得寻找可行解：
设给定线性规划问题为

在第个约束条件上加上松弛变量,化为标准形式

由于这个系数矩阵中含一个单位矩阵,只要以这个单位矩阵作为基，就可以立即解除基变量值,因为有，由此就就是一个基可行解。
当线性规划中约束条件为“”、“ ”时，化为标准形式后,一般约束条件得系数矩阵中不包括有单位矩阵。这就是为能方便地找出一个初始得基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于零得剩余变量(也称为松弛变量）化为等式,然后再添加一个人工变量。
2、2 解线性规划概述
两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,即令目标函数中其她变量得系数取0，人工便灵得系数取某个正得常数，(一般取1），在保持原问题约束条件不变得情况下求这歌目标函数极小化得解。显然在第一阶段中,当人工变量取值为0得时候,目标函数值也为0。这时候得最优解就就是原线性规划问题得一个可行解,。如果第一阶段求解结果最优解得目标函数值不为0，也即最优解得基变量中含有人工基变量，表明原线性规划问题无可行解.
当第一阶段求解结果表明问题有可行解时,第二阶段就是从第一阶段得最终单纯性表出发,去掉人工变量,并按问题原来得目标函数，继续寻找问题得最优解.
2、3 两阶段法第一阶段
两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,即令目标函数中其她变量得系数取0,人工便灵得系数取某个正得常数，（一般取1),在保持原问题约束条件不变得情况下求这歌目标函数极小化得解.显然在第一阶段中,当人工变量取值为0得时候，目标函数值也为0.这时候得最优解就就是原线性规划问题得一个可行解。如果第一阶段求解结果最优解得目标函数值不为0,也即最优解得基变量中含有人工基变量,表明原线性规划问题无可行解.
两阶段法第一阶段就是求解第一个LP。首先我们可以知道,原LP得表达式为

其可行域为

而我们需要一个辅助得LP，其表达式为

其可行域为

我们计算以上辅助LP有三种可能结果：
1)、最优值,且人工变量皆为非基变量。从第一阶段得最优解中去掉人工变量后即为原LP得一个基本可行解。作为原LP得一个初始基本可行解，再求原问题，从而进入第二阶段。
2）、最优值,且存在人工变量皆为基变量，取值为。把某个非基变量与该人工变量进行调换。
3）、最优值，说明至少有一个人工变量不为。原LP无可行解,不需要再做第二阶段计算。
两阶段法第一阶段目得就就是判断原LP有无可行解，若有，则可得原LP得一个初始基本可行解,再对原LP进行第二阶段得计算。
2、4 两阶段法第二阶段
以第一阶段求得最优解作为初始基本可行解，再用第一阶段求得最优解时得约束条件与原问题得目标函数进行迭代，直到求出最优解。
3、两阶段法求解引例
3、1、两阶段法计算步骤
两阶段法具体计算步骤:
第一步：求出线性规划得初始基可行解,列出初始单纯形表。
第二步:进行最优性检验。
第三步;从一个基可行解转换到另一个目标函数值更大得基可行解，列出新得单纯形表。
第四步：重复第二、三步一直到计算终止.
第五步:去除人工变量。根据求得初始基本可行解,求得最优解.
其中第三步具体方法如下：
1）、确定换入基变量。只要检验数，对应得变量就可作为换入基得变量,当有一个以上检验数大于零时，一般从中找出最大得一个

其对应变量作为换入基得变量(简称换入变量）。
2）、确定换出基得变量,确定

确定为换出基得变量（简称出基变量）。元素决定了从一个基本可行解到另一个可行解得转移去向，取名主元素。
3)、用换入变量替换基变量中得换出变量,得到一个新得基。对应这个基可以找出一个新得基本可行解。并可划出一个新得单纯形表。进行如下计算：
a、将主元素所在得行数字除以主元素,即有

b、为使列变换成单位向量，将单纯形表得第行数字乘上，加到单纯形表第行数字上，计入其相应行。即有

c、计算单纯形表中各检验数，如下

由上可瞧出，检验数计算同样因基变量后，其检验数应为零,故将单纯形表中第行数字乘上加到该表得检验数上，得新得变量得检验数。
接下来在引例中用以上步骤实际求解
3、2、例一：
用两阶段法求以下问题最优解

首先第一阶段就是将此问题化为标准形式，在约束条件中加入松弛变量后得

先用单纯形法解一阶段问题,迭代如下:

其中，时目标函数中基变量得系数构成得维行向量,就是上表中得第列,就是上表中得右端列。
求解过程如下单纯形表3—1
表3-1单纯形表

0
0
0
0
0
—1
—1

基

0

4
1
2
1
1
0
0
0
—1

1
—2

—1
0
—1
1
0
-1

9
0
3
1
0
0
0
1

—2
4
0
0
-1
0
0
0

3
3
0
2
1
1
-1
0
0

1
-2
1
—1
0
-1
1
0
-1

6
6
0
4
0
3
-3
1

6
0
4
0
3
—4
0
0

0
0
0
0
1

0

3
0
1

0
0
0

0

1
1
0

0

0
0
0
0
0
-1
-1
所有判别级数,因此达到最优解,在第一阶段问题最优解中,人工变量、都就是非基变量.因此我们可得到初始基可行解

第二阶段就是将表3—1中得人工变量去除，目标函数改为:

再从表3-1最后一个表出发，继续迭代,求解过程得单纯形表如下表3-2
表3—2单纯形表

—3
0
1
0
0

基

0

0
0
0
0
1

0

3
0
1

0
0
-3

1
1
0

0

0
0
3
0

0

0
0
0
0
1

0

1
0
0

1

0
1
0

0
0
0

得到其最优解,所以目标函数最优值
3、3、例二：
用两阶段法求解以下问题

首先第一阶段就是将此问题化为标准形式，在约束条件中加入松弛变量后得

先用单纯形法解一阶段问题,迭代如下

其中，时目标函数中基变量得系数构成得维行向量，就是上表中得第列，就是上表中得右端列。
求解过程如下单纯形表3-3
表3—3单纯形表

0
0
0
0
1
1

基

0

4

1
0
0
0
1

36
1
3
0
—1
1
0
1

10
1

0
0
0
1

2
4
0
-1
0
0
0

0
1
0
0

1

6
—2
0
0
—1
1
—3
0

10
1
1
0
0
0
1

-2
0
0
1
0
-4
所有判别级数,但此时,说明至少有一个人工变量不为0,原问题无可行解,不需要进入第二阶段计算。
3、4、引例分析
根据引例一与引例二得求解过程计算可知,第一阶段使用单纯形法可以得到一般得最优解,而使用两阶段法能在第二阶段找到更精确更优化得最优解。
4、算法比较
4、1 大M算法
单纯形法从一个初始可行基开始,要求标准型对应得单纯形表满足两个条件,其一就是中心部位具有阶单位子块,其二就是右列元素非负。对于线性规划问题
(4、1、1）
若，且对应得厨师单纯形表条件二满足条件一不满足,那么应引入人工变量,构造新得线性规划问题
（4、1、2）
其中,且为无限大得数,令，则相性规划问题可表示为
(4、1、3）
设就是（4、1、3)得最优解，若，则就是(4、1、2)得最优解,若，则(4、 1、2）无可行解。反之，若就是（4、1、2)得最优解,则就是(4、1、3）得最优解。
故其求解方法步骤为
1）、经初等行变换通常使，使右列元素非负.
2)、在中心部位人工得添加一个阶单位子块，即引入人工变量,得到新得约束方程组。
3)、讲目标函数修改为，其中为足够大得正常数，从而得到新得LP模型.
4）、用单纯形法求解新得LP模型,试图将变成自由变量，最终有两种结果如下
a、设球得新得LP模型最优解为,若，则就是原LP问题得最优解。若,则原LP问题无最优解。
b、新LP无界(无最优解），则原LP问题也无最优解。
4、2 算法比较
如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量,人工地构成一个单位向量组。而两阶段法与大M法都就是可以控制人工变量取值得方法，并且两种方法都就是在单纯形法得基础上进一步求解最优解得方法,两种方法得用法相似,各有优缺点.通过设置新得变量得到初始基本变量，并通过在目标函数中设置新变量得价格系数为M使得在优化过程中，新变量得值优化为0在计算机求解过程中，由于计算机只能对M设置有限大得数值，所以在计算过程中可能会产生误差，为了解决这个问题，产生了两阶段法。所以大M法虽然简单直观，在单纯形表上得计算步骤与普通单纯形法相同,但就是大M到底取值多大不能确定,M取值过大也将增加数值计算困难.
用大M法处理人工变量，用手工计算求解时不会碰到麻烦.但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长得数字.如果线性规划问题中得参数值与这个代表M得数相对比较接近,或远远小于这个数字,由于计算机计算时取值上得误差，可能使计算结果发生错误。而两阶段法通过对添加人工变量后得线性规划问题分两个阶段来计算，从而可以克服这个困难。
4、3 特殊情况
1)、无可行解：线性规划最优解中出现人工变量大于零得情况,则此线性规划无可行解。
2）、无界解：在求目标函数最大值等问题中，在某次迭代得单纯形表中，如果存在这一个不满足符号条件得检验数,并且该列得系数向量得每个元素都小于或等于令，则此线性规划无界.
3)、无穷多最优解：对于某个最优得基本可行解，如果存在某个非基变量得检验数为零，则此线性规划问题有无穷多最优解。
4)、退化：在单纯形法计算过程中，基变量有事存在两个以上相同得最小比值，这样在下一次迭代中就有一个或几个基变量等于零，称之为退化。而退化就容易产生循环迭代，为避免如此，应遵守以下两条原则:
a、在所有不满足符号条件得检验数对应得非基变量中，选一个下标最小得作为调入变量。
b、若存在两个以上得最小比值，选一个下表最小得作为调出变量。
5、总结
5、1 总结概括
求解最优问题就是一个艰难而具有挑战性得过程,最优化方法就是近几十年形成得一门运用数学方法研究各种系统得优化途径及方案，为决策者提供科学决策得依据得学科,它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题与不等式约束最优化问题等知识点.通过本课程教学，使学生掌握最优化计算方法得基本概念与基本理论，初步学会处理应用最优化方法解决实际中得碰到得各个问题，培养解决实际问题得能力。而本次课程设计,我选择了两阶段法这一课题对之进行了一定程度上得研究。两阶段法就是当线性规划模型中约束条件系数矩阵不存在单位向量组时，加入人工变量，人工构造一个单位向量组得方法。在两阶段法中，第一阶段不考虑原问题就是否存在基可行解，给原线性规划问题加入人工变量,并构造仅含人工变量目标函数与要求实现最小化.然后用单纯形法求解上述模型,若得到，说明原问题存在基可行解,可以进行第二阶段得计算，否则原问题无可行解，应停止计算。在第二阶段中，将第一阶段计算到得最终表，除去人工变量.讲目标函数行得系数，换元问题得目标函数系数,作为第二阶段计算得初始表，然后计算。通过比较大M法与两阶段法，大M法来求解此类问题，虽然一次就可通过出等行变换得到最优解，不用求两次，但就是M值不确定,数值计算上并不简单方便，我个人更喜欢两阶段法，得到得结果也更为精确.
5、2 个人感言
通过本次课程设计,我学会了应该怎么从一个问题出发,对该问题进行研究：首先要对问题有一个大概得了解，再通过查阅资料，对问题有一个深入了解,然后确定问题得研究方向，以及要研究方向所需要进行得工作,然后一步步去完成.在课程设计过程中,虽然也遇到一些困难，比如查找得文献多为全英图书,方法比较时两种概念略微混淆与一些非客观因素等，但就是最终还算克服困难基本完成了此次课程设计.从前在课堂上可能只关注了一些方法体系,而没有关注理论本身,也不知道其根本,这次课设后才明白追根溯源有时候能更完全得收货知识。
6、参考文献:
[1］ 张光澄、非线性最优化计算方法[M］、北京:高等教育出版社，2005、 
［2] 席少霖、非线性最优化计算方法［M］、北京:高等教育出版社，1992、 
[3］ 薛嘉庆、最优化原理与方法[M］、北京:清华大学出版社，2003、 
［4] 邓乃杨、无约束最优化计算方法［M]、北京:北京科学出版社,1982、 
［5］ 袁亚湘、孙文瑜最优化理论与方法[M]、北京：北京科学出版社，1993、 
［6］ 何坚勇、最优化方法［M］、北京:清华大学出版社，2007、