《两阶段法分析与实现.doc》由会员分享，可在线阅读，更多相关《两阶段法分析与实现.doc（19页珍藏版）》请在三一文库上搜索。
1、卜二 GUILIN UNIVERSITV OF ELECTRONIC TECKHOLO<>Y最优化方法课程设计题目两阶段法分析与实现院系：数学与计算科学学院专 业：统计学姓名学号：张雨坤 16指导教师：李丰兵日 期：2015 年01 月22 日摘要常用的解线性规划问题的方法有图解法， 单纯形法，对偶单纯形法，解乘数 法，椭球法等。而本论文即主要阐述的是从属于单纯形法的两阶段法。 两阶段法 第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题， 当第一阶段 求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发， 去 掉人工变量，并按问题原来的目标函数，继续寻找问题
2、的最优解，即是一种为使 人工变量被替换出成为非基变量的方法。与大M法同时被广为使用，但相较于大 M法，两阶段法能够求的更准确地结果。关键词：线性规划；单纯形法；两阶段法；大 M法AbstractWe usually solve the linear programming problems with graphic method, simplex method and dual simplex method, the multiplier method, ellipsoid method and so paper mainly expounds the two stage method whi
3、ch 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
4、 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 widel
5、y 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、引言 12、两阶段法描述 1基本可行解 1两阶段法概述 1两阶段法第一阶段 2两阶段法第二阶 段33、两阶段法求解引例 4两阶段法计算步骤 4例 1 5例 2 8引例分析 94、算法比较 9大M法 9算法比较 10特殊情况
6、115、总结 错误 !未定义书签。总结概括 12个人感言 126、参考文献： 131、引言在各种优化算法中，两阶段法(Two stage method)是非常重要的一种。即如果 线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人 工构成一个单位向量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控 制人工变量取值。寻找线性规划问题初始基可行解的一种方法 . 把增加人工变量的线性规划问题分为 Ax x b 两个阶段去求解. 第一阶段是构造一个辅助的人工目标函数, 即a 或x 0,xa 0 maxZ ( yi) 。 若原问题 有可行 解, 则在本阶 段的最 终单
7、纯形表中 , 必有 Z 0和 yi 0(i 1,2,L ,m), 并使人工变量均为非基变量 . 此时,划去人工变量所在的列与人工目 标函数所在的行 , 就得到原问题的初始可行基对应的单纯形表 , 进入第二阶段 .2、两阶段法描述基本可行解 设给定线性规划问题为当线性规划问题的玉树条件全部为时，可按下述方法比较方便的寻找可行解：nmax z cj xj j1naij xj bi(i 1,L ,m)s.t. j 1xj 0 ( j 1,L ,n)在第 i 个约束条件上加上松弛变量 xsi(i 1,L ,m) ，化为标准形式nmmax z cj xj 0xsij 1 i 1naij xj xsi b
8、i(i 1,L ,m)s.t. j 1xj 0 ( j 1,L ,n)a11a12 La1n10L0a21a22 La2n01L0MMMMMMam1am2 Lamn00L1由于这个系数矩阵中含一个单位矩阵(Ps1,L , Psm ) ，只要以这个单位矩阵作为基，就可以立即解除基变量值 xsi bi(i 1,L ,m) ，因为有 bi 0(i 1,L ,m) ，由此X (0,L ,0, b1,L ,bm)T 就是一个基可行解。当线性规划中约束条件为“ ”、“ ”时，化为标准形式后，一般约束条件的系 数矩阵中不包括有单位矩阵。这是为能方便地找出一个初始的基可行解，可添加人工变 量来人为地构造一个单
9、位矩阵作为基，称作人工基。先在不等式左端减去一个大于等于 零的剩余变量(也称为松弛变量)化为等式，然后再添加一个人工变量。解线性规划概述 两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题， 即令 目标函数中其他变量的系数取 0，人工便灵的系数取某个正的常数，(一般取 1)，在 保持原问题约束条件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当 人工变量取值为 0 的时候，目标函数值也为 0。这时候的最优解就是原线性规划问题的 一个可行解，。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果
10、表明问题有可行解时， 第二阶段是从第一阶段的最终单纯性表 出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解。两阶段法第一阶段 两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题， 即令目标函数 中其他变量的系数取 0，人工便灵的系数取某个正的常数，(一般取 1)，在保持原问题约束条 件不变的情况下求这歌目标函数极小化的解。显然在第一阶段中，当人工变量取值为 0 的时候， 目标函数值也为 0。这时候的最优解就是原线性规划问题的一个可行解。如果第一阶段求解结果 最优解的目标函数值不为 0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解两阶段法第一阶段
11、是求解第一个 LP。首先我们可以知道，原LP的表达式为nmin zcj xjj1Ax bs.t.x0其可行域为xxD:x D Da0而我们需要一个辅助的LP,其表达式为mmin waii1Ax a bs.t.x 0,a 0其可行域为xD : D min w 00我们计算以上辅助LP有三种可能结果：1) 、最优值 w 0 ，且人工变量皆为非基变量。从第一阶段的最优解中去掉人工变量后即为原LP的一个基本可行解。作为原LP的一个初始基本可行解，再求原问题，从 而进入第二阶段。2) 、最优值 w 0，且存在人工变量皆为基变量，取值为 0 。把某个非基变量与该人工变量进行调换。3) 、最优值w 0，说明
12、至少有一个人工变量不为0。原LP无可行解，不需要再做第二阶段计算。两阶段法第一阶段目的就是判断原 LP有无可行解，若有，则可得原LP的一个初始基本可行解，再对原LP进行第二阶段的计算。两阶段法第二阶段以第一阶段求得最优解作为初始基本可行解，再用第一阶段求得最优解时的约束条 件和原问题的目标函数进行迭代，直到求出最优解。3、两阶段法求解引例、两阶段法计算步骤两阶段法具体计算步骤：第一步：求出线性规划的初始基可行解，列出初始单纯形表。第二步：进行最优性检验。第三步;从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。第四步：重复第二、三步一直到计算终止。第五步：去除人工变量。根据
13、求得初始基本可行解，求得最优解。其中第三步具体方法如下：1）、确定换入基变量。只要检验数 j 0，对应的变量Xj就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大的一个kk max j j 0其对应变量Xk作为换入基的变量（简称换入变量）2）、确定换出基的变量，确定baikbimin aikaik确定Xi为换出基的变量（简称出基变量）元素aik决定了从一个基本可行解到另一个可行解的转移去向，取名主元素3）、用换入变量Xk替换基变量中的换出变量，得到一个新的基（,L ,P|1,Pk,P1,L ,Pm,Pm1,L ,Pmn）。对应这个基可以找出一个新的基本可行解。并可 划出一个新的
14、单纯形表。进行如下计算bia、将主元素所在的I行数字除以主元素aik，即有 aakb、为使Pk列变换成单位向量，将单纯形表的第I行数字乘上（a”），加到单纯aIk形表第i行数字上，计入其相应行。即有bibiaIj aIjbIgaik (i bkaIj g ( gaik (i aIkI)I)c、计算单纯形表中各检验数，如下Zi)Ci1 I1mCi akCkCi aikaI ki1i I 1Ck1 m1(CkZk)Ci aika IkaIk i 1a Ik1 1mmmCi aijCi aijCi aikCkCiaiki 1iI 1a Iki 1i I 1ma Ijma IjCi aijCkGaik
15、(CjZj)(Ck1a Iki 1a Ik(CiIZk)其检验数（CkiiCj(Cj Zj) Cj由上可看出，检验数计算同样因Xk基变量后,Zk）应为零，故将单纯形表中第I行数字乘上（ 衣）加到该表的检验数上，得新的变量的检验数。 aI k接下来在引例中用以上步骤实际求解、例一：用两阶段法求以下问题最优解max z3x(X3X1X2X342x-iX2X31s.t3x2X39Xj 0(j1,2,3)首先第一阶段是将此问题化为标准形式，在约束条件中加入松弛变量x4, x5, x6, x7后min w x6 x7x-ix2x3x442为x2x3X5X61s.t3x2 x3X79Xj 0( j 1,L
16、 ,7)先用单纯形法解一阶段问题，迭代如下：1ZjCjCbB PjCjCBYjCjZjCjCbB 1PjCjCsYjCj其中，cb时目标函数中基变量的系数构成的维行向量，yj是上表中的第j列，b是上表中的右端列。求解过程如下单纯形表3-1表3-1单纯形表Cj00000-1-1Cb基bX1X2X3X4X5X6X70X441211000-1X61-21-10-110-1X790310001CjZj-2400-1000X4330211-100X21-21-10-110-1X7660403-31CjZj60403-400X4000011212120X230113000130X1110230121216
17、CjZj00000-1-1所有判别级数Cj Zj 0，因此达到最优解，在第一阶段问题最优解中，人工变量X6、X7都是非基变量。因此我们可得到初始基可行解Xi，X2，X3，X4，x1,3,0,0,0第二阶段是将表3-1中的人工变量X6,X7去除，目标函数改为：max z3x1 0x2 x3 0x4 0x5再从表3-1最后一个表出发，继续迭代，求解过程的单纯形表如下表3-2表3-2单纯形表Cj-30100Cb基bXX2X3X4X50X400001120X2301100321-3X1110032CjZj0030320X40000120511X21002241330103X322493CjZj0002
18、45 3得到其最优解Xi,X2,X30,-,3 ,所以目标函数最优值嗨2 2、例二：用两阶段法求解以下问题min z 2x1 3x211XiX2424S.tXi3x236XiX210Xi,X20首先第一阶段是将此问题化为标准形式，在约束条件中加入松弛变量x3, x4, x5, x6后minz2x1 3x211X7X2X3424s.tX13x2x4 x536X1X2X6 10Xi,X2,X3,X4,X5,X60先用单纯形法解一阶段问题，迭代如下1ZjCjcbbPjCjCb yjCj1ZjCjCBb PjCjCB yj Cj其中，Cb时目标函数中基变量的系数构成的维行向量，Yj是上表中的第j列，b
19、是上表中的右端列。求解过程如下单纯形表3-3表3-3单纯形表Cj000011Cb基bX1X2X3X4X5X60X34121410001X536130-1101X610110001CjZj240-1000X332140100141X56-200-11-30X210110001CjZj-20010-4所有判别级数Cj Zj 0 ,但此时w 6，说明至少有一个人工变量不为 0,原问题 无可行解，不需要进入第二阶段计算。、引例分析根据引例一和引例二的求解过程计算可知，第一阶段使用单纯形法可以得到一般的 最优解，而使用两阶段法能在第二阶段找到更精确更优化的最优解。4、算法比较大M算法单纯形法从一个初始可
20、行基开始，要求标准型对应的单纯形表满足两个条件，其是中心部位具有m阶单位子块，其二是右列元素非负。对于线性规划问题nmin z CjXjj i()naijxjbi, i 1,2.L ,mS.t j 1Xj0, j 1,2.L , n若r(A) m，且对应的厨师单纯形表条件二满足条件一不满足，那么应引入人工变量Xn 1 , Xn 2 ,LXn m ，构造新的线性规划问题min zcj xj M xjj 1 j n1naij xj xn 1 bi,i 1,2.L ,m s.t. j 1xj 0, j 1,2.L ,n,n 1,L ,n m其中， M 0 且为无限大的数，令 yxn 1,xn 2,L
21、xnmT,E1,1,L 1 T ，则相性规划问题可表示为min z CTx MET yAx y b （） s.t.x, y 0设（x ,y ）T是（）的最优解，若y0，则X是（）的最优解，若y0 ，则（ 4. ）无可行解。反之，若x是（）的最优解，贝U （x ,0）T是（）的最优解故其求解方法步骤为1）、经初等行变换通常使 ri （ 1） ，使右列元素非负2）、在中心部位人工的添加一个 m阶单位子块，即引入人工变量 力2丄，ym，得到新 的约束方程组。m3） 、讲目标函数修改为 z z M yj ，其中 M 0为足够大的正常数，从而得到新的j1LP模型。4）、用单纯形法求解新的LP模型，试图将
22、yi, y2,L ,ym变成自由变量，最终有两种结 果如下a、设球的新的LP模型最优解为（x , y ）T，若y g ,y丄，ym ）0，则x % x丄，Xn）是原lp问题的最优解。若y （yi , y2丄，ym ） 0，则原LP问题无最优解。b、新LP无界（无最优解），则原LP问题也无最优解。算法比较如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工 变量，人工地构成一个单位向量组。而两阶段法和大 M法都是可以控制人工变量取值的 方法，并且两种方法都是在单纯形法的基础上进一步求解最优解的方法，两种方法的用 法相似，各有优缺点。通过设置新的变量得到初始基本变量，并通过在目
23、标函数中设置 新变量的价格系数为M使得在优化过程中，新变量的值优化为 0在计算机求解过程中， 由于计算机只能对M设置有限大的数值，所以在计算过程中可能会产生误差，为了解决 这个问题，产生了两阶段法。所以大 M法虽然简单直观，在单纯形表上的计算步骤与普 通单纯形法相同，但是大M到底取值多大不能确定，M取值过大也将增加数值计算困难。用大M法处理人工变量，用手工计算求解时不会碰到麻烦。但用电子计算机求解时, 对M就只能在计算机内输入一个机器最大字长的数字。 如果线性规划问题中的参数值与 这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差， 可能使计算结果发生错误。 而两阶段
24、法通过对添加人工变量后的线性规划问题分两个阶 段来计算，从而可以克服这个困难。特殊情况1）、无可行解：线性规划最优解中出现人工变量大于零的情况，则此线性规划无 可行解。2）、无界解：在求目标函数最大值等问题中，在某次迭代的单纯形表中，如果存 在这一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于令， 则此线性规划无界。3）、无穷多最优解 : 对于某个最优的基本可行解，如果存在某个非基变量的检验 数为零，则此线性规划问题有无穷多最优解。4）、退化：在单纯形法计算过程中，基变量有事存在两个以上相同的最小比值， 这样在下一次迭代中就有一个或几个基变量等于零，称之为退化。而退化就容易
25、产生循 环迭代，为避免如此，应遵守以下两条原则：a、在所有不满足符号条件的检验数对应的非基变量中，选一个下标最小的作 为调入变量。b、若存在两个以上的最小比值，选一个下表最小的作为调出变量5、总结总结概括求解最优问题是一个艰难而具有挑战性的过程， 最优化方法是近几十年形成的一门 运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科， 它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化 问题等知识点。通过本课程教学，使学生掌握最优化计算方法的基本概念和基本理论， 初步学会处理应用最优化方法解决实际中的碰到的各个问题，培养解决实际问题的能 力。而本次
26、课程设计，我选择了两阶段法这一课题对之进行了一定程度上的研究。两阶 段法是当线性规划模型中约束条件系数矩阵不存在单位向量组时，加入人工变量，人工 构造一个单位向量组的方法。 在两阶段法中，第一阶段不考虑原问题是否存在基可行解， 给原线性规划问题加入人工变量，并构造仅含人工变量目标函数和要求实现最小化。然 后用单纯形法求解上述模型，若得到 w 0 ，说明原问题存在基可行解，可以进行第二 阶段的计算，否则原问题无可行解，应停止计算。在第二阶段中，将第一阶段计算到的 最终表，除去人工变量。讲目标函数行的系数，换元问题的目标函数系数，作为第二阶 段计算的初始表，然后计算。通过比较大 M法和两阶段法，大
27、M法来求解此类问题，虽 然一次就可通过出等行变换得到最优解，不用求两次，但是M值不确定，数值计算上并不简单方便，我个人更喜欢两阶段法，得到的结果也更为精确。个人感言通过本次课程设计，我学会了应该怎么从一个问题出发，对该问题进行研究：首先 要对问题有一个大概的了解，再通过查阅资料，对问题有一个深入了解，然后确定问题 的研究方向，以及要研究方向所需要进行的工作，然后一步步去完成。在课程设计过程 中，虽然也遇到一些困难，比如查找的文献多为全英图书，方法比较时两种概念略微混 淆和一些非客观因素等，但是最终还算克服困难基本完成了此次课程设计。从前在课堂 上可能只关注了一些方法体系，而没有关注理论本身，也不知道其根本，这次课设后才 明白追根溯源有时候能更完全的收货知识。6、参考文献：1 张光澄. 非线性最优化计算方法 M. 北京：高等教育出版社， 2005.2 席少霖. 非线性最优化计算方法 M. 北京：高等教育出版社， 1992.3 薛嘉庆. 最优化原理与方法 M. 北京：清华大学出版社， 2003.4 邓乃杨. 无约束最优化计算方法 M. 北京：北京科学出版社， 1982.5 袁亚湘. 孙文瑜最优化理论与方法 M. 北京：北京科学出版社， 1993.6 何坚勇.最优化方法 M. 北京：清华大学出版社， 2007.