两阶段法分析与实现

1、请预览后下载！最最最最 优优优优 化化化化 方方方方 法法法法课课课课 程程程程 设设设设 计计计计题 目： 两阶段法分析与实现 院 系： 数学与计算科学学院 专 业： 统计学 姓名学号： 张雨坤 1200720216 指导教师： 李丰兵 日 期： 2015 年 01 月 22 日请预览后下载！摘摘 要要常用的解线性规划问题的方法有图解法，单纯形法，对偶单纯形法，解乘数法，椭球法等。而本论文即主要阐述的是从属于单纯形法的两阶段法。两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问

2、题原来的目标函数，继续寻找问题的最优解，即是一种为使人工变量被替换出成为非基变量的方法。与大 M 法同时被广为使用，但相较于大 M 法，两阶段法能够求的更准确地结果。关键词关键词：线性规划；单纯形法；两阶段法；大 M 法请预览后下载！AbstractAbstract 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 p

3、aper 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 solut

4、ion, 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 va

5、riable 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.KeyKey words:words:;Linear programming；Simplex method;Two stage method; The big M method; 请预览后下载！目目 录录1 1、引言引言.12 2、两阶段法描述两阶段法描述.12.1 基本可行解.12.2 两阶段法概述

6、.12.3 两阶段法第一阶段.22.4 两阶段法第二阶段.33 3、两阶段法求解引例、两阶段法求解引例.43.1 两阶段法计算步骤.43.2 例 1 .53.3 例 2 .83.4 引例分析.94 4、算法比较算法比较.94.1 大 M 法.94.2 算法比较.104.3 特殊情况.115 5、总结、总结.125.1 总结概括.125.2 个人感言.126 6、参考文献：、参考文献：.13请预览后下载！1 1、引言引言在各种优化算法中，两阶段法（Two stage method）是非常重要的一种。即如果线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人工构成一个单位向

7、量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解的一种方法.把增加人工变量的线性规划问题分为两个阶段去求解.第一阶段是构造一个辅助的人工目标函数,即或0,0aaAxxbxx。若原问题有可行解,则在本阶段的最终单纯形表中,必有和max()iZy 0Z ,并使人工变量均为非基变量.此时,划去人工变量所在的列与人工目0(1,2,)iyim标函数所在的行,就得到原问题的初始可行基对应的单纯形表,进入第二阶段.2 2、两阶段法描述两阶段法描述2.12.1 基本可行解基本可行解当线性规划问题的玉树条件全部为“”时，可按下述方法比较方便的寻找可行解：设

8、给定线性规划问题为11max(1,). .0(1, )njjjnijjijjzc xa xb imstxjn在第 个约束条件上加上松弛变量，化为标准形式i(1,)sixim请预览后下载！111max0(1,). .0(1, )nmjjsijinijjsiijjzc xxa xxb imstxjn1112121222121 000 100 01 nnmmmnaaaaaaaaa由于这个系数矩阵中含一个单位矩阵，只要以这个单位矩阵作为基，1(,)ssmPP就可以立即解除基变量值，因为有，由此(1,)siixb im0(1,)ibim就是一个基可行解。1(0,0,)TmXbb当线性规划中约束条件为“”

9、、“ ”时，化为标准形式后，一般约束条件的系数矩阵中不包括有单位矩阵。这是为能方便地找出一个初始的基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于零的剩余变量（也称为松弛变量）化为等式，然后再添加一个人工变量。2.22.2 解线性规划概述解线性规划概述两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取 0，人工便灵的系数取某个正的常数，（一般取 1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为 0 的时候，目标函数值也为 0。这时候的最优解就是原线

10、性规划问题的一个可行解，。如果第一阶段求解结果最优解的目标函数值不为 0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯性表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解。2.32.3 两阶段法第一阶段两阶段法第一阶段两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函请预览后下载！数中其他变量的系数取 0，人工便灵的系数取某个正的常数，（一般取 1），在保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为 0 的时候，目标函数

11、值也为 0。这时候的最优解就是原线性规划问题的一个可行解。如果第一阶段求解结果最优解的目标函数值不为 0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。请预览后下载！两阶段法第一阶段是求解第一个 LP。首先我们可以知道，原 LP 的表达式为1min. .0njjjzc xAxbstx其可行域为:0 xxD xDDa 而我们需要一个辅助的 LP，其表达式为1min. .0,0miiwaAxabstxa其可行域为:min00 xDDw 我们计算以上辅助 LP 有三种可能结果：1)、最优值，且人工变量皆为非基变量。从第一阶段的最优解中去掉人工0w变量后即为原 LP 的一个基本可行解

12、。作为原 LP 的一个初始基本可行解，再求原问题，从而进入第二阶段。2)、最优值，且存在人工变量皆为基变量，取值为。把某个非基变量与该0w0人工变量进行调换。 3)、最优值，说明至少有一个人工变量不为。原 LP 无可行解，不需要再0w0做第二阶段计算。请预览后下载！两阶段法第一阶段目的就是判断原 LP 有无可行解，若有，则可得原 LP 的一个初始基本可行解，再对原 LP 进行第二阶段的计算。2.42.4 两阶段法第二阶段两阶段法第二阶段以第一阶段求得最优解作为初始基本可行解，再用第一阶段求得最优解时的约束条件和原问题的目标函数进行迭代，直到求出最优解。3 3、两阶段法求解引例、两阶段法求解引例

13、3.13.1、两阶段法计算步骤、两阶段法计算步骤两阶段法具体计算步骤：第一步：求出线性规划的初始基可行解，列出初始单纯形表。第二步：进行最优性检验。第三步;从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。第四步：重复第二、三步一直到计算终止。第五步：去除人工变量。根据求得初始基本可行解，求得最优解。 其中第三步具体方法如下：1)、确定换入基变量。只要检验数，对应的变量就可作为换入基的变量，0jjx当有一个以上检验数大于零时，一般从中找出最大的一个kmax0kjj 其对应变量作为换入基的变量（简称换入变量）。kx2)、确定换出基的变量，确定min0ilikiklkbbaaa

14、确定为换出基的变量（简称出基变量）。元素决定了从一个基本可行解到另一个lxlka可行解的转移去向，取名主元素。请预览后下载！3)、用换入变量替换基变量中的换出变量，得到一个新的基kx。对应这个基可以找出一个新的基本可行解。并1111( ,)lklmmm nPPP PppP可划出一个新的单纯形表。进行如下计算:a、将主元素所在的 行数字除以主元素，即有llkaljllljlklkabbaaab、为使列变换成单位向量，将单纯形表的第 行数字乘上，加到单kPl()ljlkaa纯形表第 行数字上，计入其相应行。即有i()()liiiklkljljljiklkbbbailbaaaailac、计算单纯形表

15、中各检验数，如下11111()11()lmllliikkiikii llkmkiikkkilklklkczcc acc aacc aczaaa 1111111()()()lmmmljjjjiijiijiikkiikii lii llkmmljljjiijkiikjjkkiilklkaczcc ac ac acc aaaacc acc aczczaa 由上可看出，检验数计算同样因基变量后，其检验数应为零，故将单纯形表kx()kkcz中第 行数字乘上加到该表的检验数上，得新的变量的检验数。l()()kklkcza 接下来在引例中用以上步骤实际求解3.23.2、例一：、例一：用两阶段法求以下问题最优

16、解请预览后下载！1312312323max3421. .390(1,2,3)jzxxxxxxxxstxxxj 首先第一阶段是将此问题化为标准形式，在约束条件中加入松弛变量后得4567,x x x x67123412356237min421.390(1,7)jwxxxxxxxxxxxstxxxxj先用单纯形法解一阶段问题，迭代如下：1jjBjjBjjzcc B Pcc yc1jjBjjBjjzcc B Pcc yc其中，时目标函数中基变量的系数构成的维行向量，是上表中的第列，是上Bcjyjb表中的右端列。求解过程如下单纯形表 3-1表 3-1 单纯形表jc00000-1-1Bc基b1x2x3x4

17、x5x6x7x04x41211000-16x1-21-10-110-17x90310001jjcz-2400-100请预览后下载！04x3 30211-1002x1-21-10-110-17x660403-31jjcz60403-4004x0000112121202x301130001301x110230121216jjcz00000-1-1所有判别级数，因此达到最优解，在第一阶段问题最优解中，人工变量0jjcz、都是非基变量。因此我们可得到初始基可行解6x7x 12345,1,3,0,0,0 x x x x x第二阶段是将表 3-1 中的人工变量去除，目标函数改为：67,x x12345ma

18、x3000zxxxxx 再从表 3-1 最后一个表出发，继续迭代，求解过程的单纯形表如下表 3-2表 3-2 单纯形表jc-30100Bc基b1x2x3x4x5x04x000011202x3011300-31x11023 012jjcz003032请预览后下载！04x000011202x52121001413x323201034jjcz9200034得到其最优解，所以目标函数最优值1235 3,0,2 2x x xmax32f3.33.3、例二：、例二：用两阶段法求解以下问题1212121212min2311424336. .10,0zxxxxxxstxxx x首先第一阶段是将此问题化为标准形

19、式，在约束条件中加入松弛变量后3456,x x x x得121231245126123456min2311424336. .10,0zxxxxxxxxxstxxxx x x x x x先用单纯形法解一阶段问题，迭代如下1jjBjjBjjzcc B Pcc yc1jjBjjBjjzcc B Pcc yc其中，时目标函数中基变量的系数构成的维行向量，是上表中的第列，是上Bcjyjb表中的右端列。求解过程如下单纯形表 3-3请预览后下载！表 3-3 单纯形表jc000011Bc基b1x2x3x4x5x6x03x41214100015x36130-11016x10110001jjcz240-10003

20、x321401001415x6-200-11-302x10110001jjcz-20010-4所有判别级数，但此时，说明至少有一个人工变量不为 0，原问题0jjcz6w无可行解，不需要进入第二阶段计算。3.43.4、引例分析、引例分析根据引例一和引例二的求解过程计算可知，第一阶段使用单纯形法可以得到一般的最优解，而使用两阶段法能在第二阶段找到更精确更优化的最优解。4 4、算法比较、算法比较4.14.1 大大 M M 算法算法单纯形法从一个初始可行基开始，要求标准型对应的单纯形表满足两个条件，其一是中心部位具有阶单位子块，其二是右列元素非负。对于线性规划问题m请预览后下载！ （4.1.1）11m

21、in,1,2.,. .0,1,2.,njjjnijjijjzc xa xb imstxjn若，且对应的厨师单纯形表条件二满足条件一不满足，那么应引入人工变量( )r Am，构造新的线性规划问题12,nnn mxxx （4.1.2）1111min,1,2.,. .0,1,2., ,1,nn mjjjjj nnijjnijjzc xMxa xxb imstxjn nnm 其中，且为无限大的数，令，则相性规划问0M 12,1,1,1TTnnn myxxxE题可表示为 （4.1.3）min. .,0TTzC xME yAxybstx y设是（4.1.3）的最优解，若，则是（4.1.2）的最优解，若，(

22、,)Txy0yx0y则（4. 1.2）无可行解。反之，若是（4.1.2）的最优解，则是（4.1.3）的x(,0)Tx最优解。故其求解方法步骤为1）、经初等行变换通常使，使右列元素非负。( 1)ir 2）、在中心部位人工的添加一个阶单位子块，即引入人工变量，得到新m12,my yy的约束方程组。3）、讲目标函数修改为，其中为足够大的正常数，从而得到新1mjjzzMy0M 的 LP 模型。4）、用单纯形法求解新的 LP 模型，试图将变成自由变量，最终有两种12,my yy请预览后下载！结果如下请预览后下载！a、设球的新的 LP 模型最优解为，若，则(,)Txy12(,)0myyyy是原 LP 问题

23、的最优解。若，则原 LP 问题无12(,)nxxxx12(,)0myyyy最优解。b、新 LP 无界（无最优解），则原 LP 问题也无最优解。4.24.2 算法比较算法比较如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。而两阶段法和大 M 法都是可以控制人工变量取值的方法，并且两种方法都是在单纯形法的基础上进一步求解最优解的方法，两种方法的用法相似，各有优缺点。通过设置新的变量得到初始基本变量，并通过在目标函数中设置新变量的价格系数为 M 使得在优化过程中，新变量的值优化为 0 在计算机求解过程中，由于计算机只能对 M 设置有限大的数值，

24、所以在计算过程中可能会产生误差，为了解决这个问题，产生了两阶段法。所以大 M 法虽然简单直观，在单纯形表上的计算步骤与普通单纯形法相同，但是大 M 到底取值多大不能确定，M 取值过大也将增加数值计算困难。用大 M 法处理人工变量，用手工计算求解时不会碰到麻烦。但用电子计算机求解时，对 M 就只能在计算机内输入一个机器最大字长的数字。如果线性规划问题中的参数值与这个代表 M 的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，可能使计算结果发生错误。而两阶段法通过对添加人工变量后的线性规划问题分两个阶段来计算，从而可以克服这个困难。4.34.3 特殊情况特殊情况1）、无可行解：线

25、性规划最优解中出现人工变量大于零的情况，则此线性规划无可行解。2）、无界解：在求目标函数最大值等问题中，在某次迭代的单纯形表中，如果存在这一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于令，则此线性规划无界。3）、无穷多最优解:对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。请预览后下载！4）、退化：在单纯形法计算过程中，基变量有事存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，称之为退化。而退化就容易产生循环迭代，为避免如此，应遵守以下两条原则：a、在所有不满足符号条件的检验数对应的非基变量中，选一个下标最小的作为调入变量。b、若存在两个以上的最小比值，选一个下表最小的作为调出变量。5 5、总结、总结5.15.1 总结概括总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点。通过本课程教学，使学生掌握最优化计算方法的基本概念和基本理论，初步学会处理应用最优化方法解决实际中的碰到的各个问题，培养解决实际问题的能力。而本次课程设计，我选择了两阶段法这一课题