or[第二章]02

1、运 筹 学 课 件目 录运筹学概论 第一章 线性规划基础第二章 单纯形法 第三章 LP对偶理论第四章 灵敏度分析 第五章 运输问题第六章 整数规划第七章 动态规划第八章 网络分析第二章第二章 单纯形法单纯形法 (SM-Simplex Method) 19471947年，美国运筹学家年，美国运筹学家Dantzig提出，原理是提出，原理是代数迭代。代数迭代。 单纯形法中的单纯形的这个术语，与该方法单纯形法中的单纯形的这个术语，与该方法毫无关系，它源于求解方法的早期阶段所研究的毫无关系，它源于求解方法的早期阶段所研究的一个特殊问题，并延用下来。一个特殊问题，并延用下来。 n维空间的单纯形，是指具有维

2、空间的单纯形，是指具有(n+1)个顶点的个顶点的多面体，如果各棱长相等，则称为正规单纯形，多面体，如果各棱长相等，则称为正规单纯形，如二维空间中的三角形如二维空间中的三角形(正三角形正三角形)三维空间的四三维空间的四面体面体(正四面体正四面体)等等, ,其一般表达式为：其一般表达式为： 0 , 11jnjjxx 如前述如前述, ,当当m=50,n=100m=50,n=100时，枚举法要枚时，枚举法要枚举举 100!/(50!)21029 个个50阶阶50元的线性方程组；与之相比，单元的线性方程组；与之相比，单纯形法只需约检查纯形法只需约检查100个基本可行解，就可个基本可行解，就可得到最优解。

3、几十年的计算实践表明，单得到最优解。几十年的计算实践表明，单纯形法只需很少的迭代次数就能得到纯形法只需很少的迭代次数就能得到LP问问题的最优解，因此，它不仅成为题的最优解，因此，它不仅成为LP的最基的最基本算法之一，而且已成为本算法之一，而且已成为IP和和NLP某些算某些算法的基础。法的基础。 本章分以下几节介绍本章分以下几节介绍 1 SM的基本原理的基本原理 2 SM计算步骤及应用举例计算步骤及应用举例 作业二： P70 1.7中(2)题 3 初始基本可行解的确定初始基本可行解的确定 4 改进单纯形法改进单纯形法 作业三： P70 1.8中(2)题1 SM的基本原理一、单纯形法的基本思想一、

4、单纯形法的基本思想对于标准形式的LP问题：0 maxXbAXCXz) 1 (X1z*X*z 初始基本可行解初始基本可行解设想：)0(X0z最优解最优解 基于上述设想可以总结出单纯形法的基于上述设想可以总结出单纯形法的基本思想如下：基本思想如下： 从一个基本可行解出发迭代到另一个从一个基本可行解出发迭代到另一个基本可行解，每次迭代使目标函数值上升，基本可行解，每次迭代使目标函数值上升，反复迭代，逐步选优，直到目标函数取得反复迭代，逐步选优，直到目标函数取得最大值为止。最大值为止。 单纯形法的实现形式：单纯形法的实现形式： 方程组；方程组； 表格；表格； 矩阵。矩阵。 二、方程组形式的单纯形法二、

5、方程组形式的单纯形法( (单纯形法引例单纯形法引例) ) 2513 maxxxz0,36431228212121xxxxxx例：例：解：首先将问题化为解：首先将问题化为标准形式：标准形式：0,36431228515214231xxxxxxxxx2513 maxxxz观察标准形式，易得初始基本可行解：观察标准形式，易得初始基本可行解： zmax0, 3643 122 8 05351(4)521(3)42(2)31(1)21xxxxxxxxxxxz0)36,12,8 ,0,0(0)0(zXTAB=(P3，P4，P5)基于基于X(0)，改写标准形式：改写标准形式： 观察上述形式观察上述形式，满足：满

6、足： 基本可行解基本可行解X(0)对应的可行基是一个对应的可行基是一个m m阶排列阶排列阵或单位阵；阵或单位阵； 目标函数方程中所有基变量的系数全部为目标函数方程中所有基变量的系数全部为0 0。 我们将满足上述两个条件的方程组称为我们将满足上述两个条件的方程组称为典式典式( (方方程组典型形式程组典型形式) )，这是单纯形法下任何一个基本可行，这是单纯形法下任何一个基本可行解必须满足的。一般地将这两个条件称为解必须满足的。一般地将这两个条件称为条典条典( (典型典型条件条件) )。 zmax0, 36 43 12 2 8 0 5 351(4)521(3)42(2)31(1)21xxxxxxxx

7、xxxz 现在分析现在分析X(0)是否最优：目标函数中非基变量是否最优：目标函数中非基变量的系数的系数( (非基变量的系数可以作为检验当前基本可非基变量的系数可以作为检验当前基本可行解是否最优的一个标志，称之为检验数行解是否最优的一个标志，称之为检验数)进基进基变量变量离基变量。离基变量。 zmax0, 36 43 12 2 8 0 5 351(4)521(3)42(2)31(1)21xxxxxxxxxxxz检验数0)36,12,8 ,0,0(0)0(zXT可去掉 因此，因此，在下一个基本可行解中，若在下一个基本可行解中，若 043602120825243xxxxx9436621222xx2x

8、1x进基进基，仍为非基变量，则有：仍为非基变量，则有：4x即即, 62x离基离基。对应典式为：对应典式为：01x62x，由83x04x125x301z得，1223683035414212314251xxxxxxxxxz2/ )12(42xx(将代入后，得)即TX)12,0,8 ,6,0()1( 称为一次迭代称为一次迭代( (从图解法看是相邻顶点从图解法看是相邻顶点的转移的转移) )2513 maxxxz0,36431228212121xxxxxx可行域最优解680 x1x2 比较迭代，可将其过程描述为：确定迭代，可将其过程描述为：确定换入变量换入变量确定换出变量确定换出变量主元主元变换变换(

9、(初等变换初等变换) ) 典式典式新解新解36 43 12 2 8 0 5 3 52142 31 21xxxxxxxxxz122 3 6 8 30 3541 4212 31 4251xxxxxxxxxz检验数检验数94/36 62/12 主元化主元化为为1 1，主，主元所在元所在列的其列的其余元素余元素化为化为0 0新典式新典式主元主元继续求解：继续求解：122 3 6 8 30 3541 4212 31 4251xxxxxxxxxz43/12 81 / 8 主元化主元化为为1 1，主，主元所在元所在列的其列的其余元素余元素化为化为0 0新典式新典式主元主元4 6 4 42 531432 1

10、4212531432 35 421xxxxxxxxxxz检验数检验数 观察最后一个典式，所有检验数均为非负，观察最后一个典式，所有检验数均为非负，故其对应的基本可行解为最优解，即故其对应的基本可行解为最优解，即 说明：说明：单纯形法的几何意义：相邻顶点的迭代单纯形法的几何意义：相邻顶点的迭代( (路径路径 统计规律统计规律) )。 理论上缺陷：每次只换入一个变量，速度不理论上缺陷：每次只换入一个变量，速度不 理想理想如何寻求快速算法。如何寻求快速算法。 42 0 , 0 , 6 , 6 , 4*T*zX 去掉引入变量，得原问题的最优解为：去掉引入变量，得原问题的最优解为：42 6 , 4*T*

11、zX 迭代路径迭代路径: :最优解2513 maxxxz0,36431228212121xxxxxx0 x2可行域68x1三、单纯形法原理三、单纯形法原理 由由SM思想、引例可见，用思想、引例可见，用SM求解标准求解标准形式的形式的LP问题，必须解决三个问题：问题，必须解决三个问题： 初始基本可行解的确定；初始基本可行解的确定； 解的最优性检验；解的最优性检验； 基本可行解的转移规则。基本可行解的转移规则。 这里先放一下，研究和，为此，这里先放一下，研究和，为此，先讨论一下对应基先讨论一下对应基B B的单纯形表。的单纯形表。 ( (一一) )对应于基对应于基B的单纯形表的单纯形表 讨论单纯形表

12、结构的目的：最优性检讨论单纯形表结构的目的：最优性检验；完成迭代；为以后讨论奠定基础。验；完成迭代；为以后讨论奠定基础。 对于标准形式的对于标准形式的LPLP问题：问题： 0 maxXbAXCXz 若已知若已知B是其一个可行基，不妨设是其一个可行基，不妨设B位于位于A的前的前m列，即列，即mpppB,21对对A、X、C按基按基B进行划分，得进行划分，得因此因此 ),(NBA ),(NBCCC NBXXXbNXBXXXNBAXNBNB),(得得 NBNXBbBX11nmmpppN,21上式表明基变量可以用非基变量表示。上式表明基变量可以用非基变量表示。 对于对于z=CX，有，有NNBBNNBBN

13、BNBXCNBCbBCXCXCXXCCCXz11 ),(与上式写在一起，得与上式写在一起，得 将将 NBNXBbBX11上式表明目标函数可以用非基变量表示。上式表明目标函数可以用非基变量表示。 bBNXBXbBCXCNBCzNBBNNB1111 上述方程组的矩阵形式为上述方程组的矩阵形式为上式的系数增广阵称为上式的系数增广阵称为对应于基对应于基B的单纯形表：的单纯形表： bBNXBXbBCXCNBCzNBBNNB1111 bBbBCXXzNBCNBCBNBNB1111 I001NBbBCNBCbBCNBB1111 I 0T(B)如果如果B B不是位于不是位于A A的前的前m m列，则有：列，则

14、有：此时对应于基此时对应于基B的单纯形表为：的单纯形表为： bBAXBbBCXCABCzBB1111 ABbBCABCbBCBB1111T(B)单纯形表四部分内容为：单纯形表四部分内容为：目标函数值目标函数值001bbBCB检验数检验数),(002011nBbbbCABCABbBCABCbBCBB1111T(B)基变量取值基变量取值T020101),(mbbbbB对应基对应基B B的约束系数矩阵的约束系数矩阵mnmmnnbbbbbbbbbAB2122221112111因此，对应于基因此，对应于基B B的单纯形表可表示如下：的单纯形表可表示如下：mnmmmnnnBBbbbbbbbbbbbbbbb

15、bABbBCABCbBC2102222120112111000201001111 T(B) 例：找出下列例：找出下列LPLP问问题的两个基，并构造相题的两个基，并构造相应的单纯形表。应的单纯形表。0,36 4312 2 8 51521 42 31xxxxxxxxx2153 maxxxz 解：取基解：取基B B如下：如下：103010001,541pppB1030100011B计算各部分如下：计算各部分如下：T1)12,12, 8(bBT)36,12, 8(b)0 , 0 , 3(BC241bBCBT541),(xxxXB对应基对应基B B的单纯形表如下：的单纯形表如下：103400102000

16、101100430102000101 1030100011AB0 , 0 , 3 , 5, 00 , 0 , 0 , 5 , 3)0 , 0 , 3 , 0 , 3(1CABCB103401201020120010180035024T(B)54321541xxxxxxxxz 取基取基B B如下：如下：IpppB543,IB1T543),(xxxXBT)36,12, 8(b)0 , 0 , 0(BC)0 , 0 , 0 , 5 , 3(C所以：所以：bbB101bBCBAAB1CCABCB1100433601020120010180005300T(B)54321543xxxxxxxxzAbC 通

17、过上例可见，当取基通过上例可见，当取基B不同时，构造不同时，构造相应的单纯形表的计算量是不同的，而当基相应的单纯形表的计算量是不同的，而当基B是单位阵时，计算量较小，是单位阵时，计算量较小，特别是特别是当基当基B是由引入的松弛变量对应的列向量构成时，是由引入的松弛变量对应的列向量构成时，其对应的单纯形表几乎就是模型的原始数据。其对应的单纯形表几乎就是模型的原始数据。这一点为我们后续介绍的确定这一点为我们后续介绍的确定初始基本可行初始基本可行解解提供了思路。提供了思路。ABbBCABCbBCBB1111T(B)AbC0T(B)IB1 ( (二二) )最优判别定理最优判别定理 *XB定理：若定理：

18、若是与基是与基对应的基本可行解，对应的基本可行解，优解。优解。 并且满足并且满足01CABCB*X，则，则是是LPLP问题的最问题的最NNBBBBXCNBCbBCXCABCbBCz)( )(1111根据根据时，目标函数值不能再提高，时，目标函数值不能再提高，直观观察可见，当基直观观察可见，当基B对应的对应的01CABCB或或01NBCNBC故当前的基本可行解就是最优解。故当前的基本可行解就是最优解。通常称通常称或或 jnjbczcPBCjjjjjBj, 2 , 1 01mnmmmnnnBBbbbbbbbbbbbbbbbbABbBCABCbBC21022221201121110002010011

19、11T(B) 因此，最优判别准则为：若基本可行解对应因此，最优判别准则为：若基本可行解对应的检验数都大于等于零，则相应的基本可行解就的检验数都大于等于零，则相应的基本可行解就是最优解。是最优解。 从单纯形表上看，所有从单纯形表上看，所有b b0j0j00，则对应的基本则对应的基本可行解就是最优解。可行解就是最优解。CABCB1为检验数，记为：为检验数，记为： ( (三三) )换基迭代换基迭代( (基于基于T(B)T(B) 根据最优判别准则，当判定基根据最优判别准则，当判定基B对应的对应的基本可行解不是最优时，就要进行换基迭代，基本可行解不是最优时，就要进行换基迭代，寻求一个目标函数值更大的新的

20、基本可行解，寻求一个目标函数值更大的新的基本可行解，具体过程如下：具体过程如下：1 1、确定换入变量、确定换入变量。具体方法有两种：。具体方法有两种：sx(1)(1)确定确定njbbbjjss, 2 , 1 , 0 min000则与则与sx为换入变量；为换入变量；s对应的非基变量对应的非基变量(2)(2)确定确定njbjsj, 2 , 1 , 0 min0sx为换入变量；为换入变量；则位于表中第则位于表中第s列的非基变量列的非基变量 上述两种方法中上述两种方法中第一种第一种通常在通常在手算手算中采中采用，用，第二种第二种通常在通常在计算机求解计算机求解中采用。中采用。 当同时有若干个非基变量可

21、作为换入当同时有若干个非基变量可作为换入变量时，可任选其一。变量时，可任选其一。2 2、确定换出变量、确定换出变量。先计算最小比值：。先计算最小比值：rJxmibbbbbisisirsr, 2 , 1 , 0min00rJx为换出变量；为换出变量；则位于表中第则位于表中第r行的基变量行的基变量 若同时有若干个基变量可作为换出变量，可若同时有若干个基变量可作为换出变量，可任选其一。任选其一。 换入变量所在列与换出变量所在行交叉换入变量所在列与换出变量所在行交叉位置的元素，即为主元位置的元素，即为主元 。mnmsmmmrnrsrrrnsnsnsnsJJJJbbbbbbbbbbbbbbbbbbbbb

22、bbbbxxxxxxxxzmr2102102222212011121110000201002121T(B)rsb 从从值确定可知，值确定可知，的值有三种情况：大于的值有三种情况：大于零、等于零或不存在零、等于零或不存在( (当当bis0,i=1,2,m) )。 可以证明：可以证明：当当0时，新的基本可行解使时，新的基本可行解使目标函数值上升；当目标函数值上升；当=0时，目标函数值不变；时，目标函数值不变；当当值不存在时，值不存在时，LPLP问题无有限最优解。问题无有限最优解。 3 3、进行进行(r,s)旋转变换旋转变换 将主元化为将主元化为1，主元所在列的其余元素化，主元所在列的其余元素化为为

23、0。 即可即可确定新的基本可行解对应的单纯形表。确定新的基本可行解对应的单纯形表。 变换公式如下式所示：变换公式如下式所示：将主元化为将主元化为1:rsrjisijijbbbbbnjmiri, 2 , 1 , 0 , 2 , 1 , 0,主元所在列的其余元素化为主元所在列的其余元素化为0: :rsrjrjbbbnj, 2 , 1 , 02 SM计算步骤及应用举例计算步骤及应用举例一、计算步骤一、计算步骤( (参见书参见书P P1818P P2121) ) 1 1、把把LPLP问题化成标准形式。问题化成标准形式。 2 2、找到问题的一个基本可行解，并构造、找到问题的一个基本可行解，并构造初始单纯

24、形表。初始单纯形表。 3 3、若所有检验数、若所有检验数j j00，就得到一个基就得到一个基本最优解；此时若存在某个非基变量的检验本最优解；此时若存在某个非基变量的检验数为数为0 0，则最优解可能不唯一，一般不再求其，则最优解可能不唯一，一般不再求其它的解，停止计算；否则转它的解，停止计算；否则转4 4。 4 4、在所有在所有j j00中，只要有一个中，只要有一个k k00所所对应的系数列向量中各分量均小于等于零，对应的系数列向量中各分量均小于等于零，即即 bik0 , i=1,2, ,m 则该则该LPLP问题无有限最优解问题无有限最优解( (或无最优解或无最优解) )，停，停止计算；否则转止

25、计算；否则转5 5。 5 5、按最小检验数规则、按最小检验数规则njbbbjjss, 2 , 1 , 0 min000确定换入变量确定换入变量sx；再按最小比值规则；再按最小比值规则mibbbbbisisirsr, 2 , 1 , 0min00 一般地，称换入变量所在列为主一般地，称换入变量所在列为主( (元元) )列，列，换出变量所在的行为主换出变量所在的行为主( (元元) )行，两者交叉位行，两者交叉位置的元素置的元素brs称为主元。称为主元。 6 6、以以brs为主元对当前表格进行一次换基为主元对当前表格进行一次换基运算，得到一个新单纯形表运算，得到一个新单纯形表( (同时，换入变量同时

26、，换入变量替代换出变量替代换出变量) )，返，返3 3。 上述步骤中，上述步骤中，1 1、2 2为预备步骤或第为预备步骤或第0 0次迭次迭代，代，3 36 6为迭代步骤。为迭代步骤。rJx确定换出变量确定换出变量。二、二、SM应用举例应用举例 例例1 1：( (说明说明SMSM的计算过程及换的计算过程及换入或换出变量不入或换出变量不唯一时的确定方唯一时的确定方法法) )32133 maxxxxz0,62253222321321321321xxxxxxxxxxxx解解：(1)(1)首先将问题化首先将问题化 为标准形式：为标准形式：0,6 225 32 2 2616321 53214321xxxx

27、xxxxxxxxxx32133 maxxxxz(2)(2)建立初始单纯形表建立初始单纯形表654,xxx取初始基取初始基即以即以IpppB),(654为初始基变量，则易得初始基本可行解为初始基变量，则易得初始基本可行解X(0)为为T)0()6 , 5 , 2 , 0 , 0 , 0(X根据前一节讨论，可得初始单纯形表如下根据前一节讨论，可得初始单纯形表如下: :0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB (3) (3)观察上表，因检验数中存在小于零观察上表，因检验数中存在小于零的，所以当前解不是最优解。的，所以当前解不是最优解。

28、 (4)(4)确定换入变量。因为：确定换入变量。因为：3100033,-1,-3-min 0 minjjssbbb若取若取1x1s则则为换入变量，而其对应的为换入变量，而其对应的系数列向量系数列向量(2(2，1 1，2)2)T T存在正分量；转存在正分量；转(5)(5)。 (5) (5)确定换出变量。计算最小比值：确定换出变量。计算最小比值：111000126,15,22min 3,2, 1 ,0minbbibbbbbisisirsr4, 11JJrr即即主元为主元为b b1111=2=2，在表中用在表中用“ ”“ ”标出。标出。，亦即，亦即4x为换出变量为换出变量0-3-1-30002211

29、10051230106221001654321 xxxxxx654xxxzbXB (6)(6)以主元为中心进行初等变换，即可得到新以主元为中心进行初等变换，即可得到新的单纯形表。的单纯形表。0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB 654321 xxxxxx651xxxzbXB 0 0 1 1 2121210 1 - 0 4 2125231 0 1 0 1 0 4 0 0 - 0 3 232321 由上表知，新的基本可行解为由上表知，新的基本可行解为3 ,)4, 4, 0 , 0 , 0 , 1 (T)1(zX重复上述重复上述

30、(3) (3) (6)(6)得下表：得下表：27/507/506/53/501/511/503/5-1/508/503/51-1/52/504010-101654321 xxxxxx631xxxzbXB 由于上表中所有检验数均已非负，因此由于上表中所有检验数均已非负，因此得到问题的最优解：得到问题的最优解：527max ,)4,0,0,58,0,51(T*zX 去掉引入变量，得原问题的最优解与最去掉引入变量，得原问题的最优解与最优值为：优值为：527max ,)58, 0 ,51(T*zX 在实际运算过程中，上述迭代过程可连续在实际运算过程中，上述迭代过程可连续进行。见下页表。进行。见下页表。

31、0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB 651xxxz0 0 1 1 2121210 1 - 0 4 2125231 0 1 0 1 0 4 0 0 - 0 3 232321 27/507/506/53/501/511/503/5-1/508/503/51-1/52/504010-101631xxxz 例例2 2：( (无界解的判别无界解的判别) )2152maxxxz0,8 23 4 51521 4231xxxxxxxxx解：选解：选543,xxx为初始基，易得初始单纯形表，并在此基础上为初始基，易得初始单纯形表，并在此基

32、础上迭迭对应的列向量构成的单位阵对应的列向量构成的单位阵代求最优解的过程如下表所示：代求最优解的过程如下表所示：0-2-50004-101003010108-1200154321 xxxxx543xxxzbXB 0 0 1 0 1- 4 0 1 0 1 0 3 1 2 0 0 1 2 0 5 0 0 2 15 523xxxz 从上表最后一表可见，对从上表最后一表可见，对1 1=-2=-2，它所对应的，它所对应的列向量列向量(-1，0，-1)T0，故目标函数最优值无上界，故目标函数最优值无上界，即问题无最优解。即问题无最优解。 实质上，所谓无有限最优解的判别，直实质上，所谓无有限最优解的判别，直

33、观上看就是对应于换入变量，按最小比值法观上看就是对应于换入变量，按最小比值法则找不出一个换出变量，亦即使则找不出一个换出变量，亦即使SM迭代过程迭代过程无法进行。无法进行。 对本例来说，从第一个表中即可看出有对本例来说，从第一个表中即可看出有无界解：如果选取无界解：如果选取1=-2对应的变量对应的变量x x1为换入为换入变量，此时就找不出换出变量，故可判定问变量，此时就找不出换出变量，故可判定问题无有限最优解题无有限最优解( (或无最优解或无最优解) )。 例例3:3:( (说明有多说明有多重最优解的情况的重最优解的情况的判定判定) ) 解解：首先将问题化首先将问题化 为标准形式：为标准形式：

34、0,4 3 8 2515241321xxxxxxxxx212 maxxxz212maxxxz0,4382212121xxxxxx以以543,xxx并在此基础上迭代求最优解的过程如下表所示：并在此基础上迭代求最优解的过程如下表所示：为基变量，构造初始单纯形表，为基变量，构造初始单纯形表，0-2-10008211003 1 001040100154321 xxxxx543xxxzbXB 513xxxz0 1 0 0 1 3 0 2- 1 1 0 2 1 0 0 1 0 4 0 2 0 1 0 6 8001002011-20310010200-121512xxxz 从最优表可见，问题的最优解与最优值

35、为：从最优表可见，问题的最优解与最优值为：8001002011-20310010200-121512xxxz54321 xxxxxbXB 8max ,)2,0,0,2,3(T*zX 去掉引入变量，得原问题的最优解与最优值为：去掉引入变量，得原问题的最优解与最优值为：8max ,)2 , 3(T*zX 在在SM计算步骤中曾讲过，若在最优表中，某计算步骤中曾讲过，若在最优表中，某个非基变量的检验数为个非基变量的检验数为0，则此时最优解可能不唯，则此时最优解可能不唯一，即可能有多重最优解。一，即可能有多重最优解。 对于本例，对于本例， x x4为非基变量且为非基变量且4 4=0=0，此时若在，此时若

36、在最优表的基础上选最优表的基础上选x x4为换入变量，进行单纯形法强行为换入变量，进行单纯形法强行迭代迭代( (如下表所示如下表所示) ) ，虽不能使目标函数值增加，但，虽不能使目标函数值增加，但却可得到另外一个基本可行解，即：却可得到另外一个基本可行解，即：8001002011-20310010200-121512xxxz54321 xxxxxbXB 8001004010012101/20-1/2100-1/211/2412xxxz8max ,)0, 1 ,0,4,2(T*zX 由图解讨论易知，在这两个基本可行解边线间由图解讨论易知，在这两个基本可行解边线间的任意一点也必为最优解。若记的任意

37、一点也必为最优解。若记T*2)0, 1 ,0,4,2(XT*1)2,0,0,2,3(X则由则由10 ,)1(*2*1*XXX可求出任意一个最优解。如令可求出任意一个最优解。如令21则可得新的则可得新的最优解最优解*3X为为T2125*221*121*31 ,0,3,XXX 但是，在单纯形表运算过程中，只要找到一个最但是，在单纯形表运算过程中，只要找到一个最优解就可以停止了。在实际应用中，问题若有多重最优解就可以停止了。在实际应用中，问题若有多重最优解可增加决策的选择机会，做出更加合意的决策。优解可增加决策的选择机会，做出更加合意的决策。 由多重最优解的确定过程可知，由多重最优解的确定过程可知，

38、若在最若在最优表中，某个非基变量的检验数为优表中，某个非基变量的检验数为0，相应，相应的列向量中不存在大于的列向量中不存在大于0的分量，则此时并的分量，则此时并不存在多重最优解；换句话说，当检验数不存在多重最优解；换句话说，当检验数为为0的非基变量作为换入变量时，找不到换的非基变量作为换入变量时，找不到换出变量，此时最优解仍唯一。出变量，此时最优解仍唯一。 综上，可以给出综上，可以给出多重最优解的判别条多重最优解的判别条件件是：是： 在最优表中至少有一个非基变量的检在最优表中至少有一个非基变量的检验数为验数为0，且其对应的列向量中至少有一个，且其对应的列向量中至少有一个大于大于0的分量。的分量

39、。 例例4:4:( (说明说明SM的另一种表格形式的另一种表格形式) ) 0,20 286 -8 51521 421321xxxxxxxxxxx4212 maxxxxz 解解：该模型约束方程组的系数矩阵中含有一个该模型约束方程组的系数矩阵中含有一个543,xxx初始单纯形表初始单纯形表( (见下页见下页) )。三阶单位阵，因此可选取三阶单位阵，因此可选取为基变量，构造为基变量，构造 z z行的数字可通过下述方法获得：行的数字可通过下述方法获得：6120008111006-110102082001543xxxz54321 xxxxxbXB 62068)0 , 1 , 0(1IbBCzB)0 ,

40、0 , 0 , 2 , 1 ( )0 , 1 , 0 , 1, 2()0 , 1 , 0 , 1 , 1( )0 , 1 , 0(1CACABCB z z行的数字还可通过将目标函数用非基变行的数字还可通过将目标函数用非基变量表示后，取系数的相反数获得，即量表示后，取系数的相反数获得，即4212xxxz21212126 )6(2xxxxxxz2146xxx 为了很容易地得到目标函数行或检验数行为了很容易地得到目标函数行或检验数行的数，当目标函数中含有基变量时，可采用另的数，当目标函数中含有基变量时，可采用另一种形式的单纯形表。借助表的结构，可直接一种形式的单纯形表。借助表的结构，可直接在表上运算

41、就可得到目标函数行的所有分量。在表上运算就可得到目标函数行的所有分量。 对于本例：对于本例：-2-1010612000081110016-1101002082001jc543xxxz54321 xxxxxbXB BC 检查问题的初始单纯检查问题的初始单纯形表，易知已得问题的最形表，易知已得问题的最优解，其最优解和最优值优解，其最优解和最优值分别为：分别为：jpB1jjBjcpBC1T*)20,6 ,8 ,0 ,0(X6maxz作业二 P P7070 1.7 1.7中中(2)(2)题题3 初始基本可行解的确定初始基本可行解的确定 现在让我们回过头来考虑现在让我们回过头来考虑SMSM的第一阶段的第

42、一阶段问题，即如何求得第一个基本可行解。问题，即如何求得第一个基本可行解。 在前面的讨论中，我们都假定约束方程在前面的讨论中，我们都假定约束方程组的系数矩阵中含有一个组的系数矩阵中含有一个m阶单位或存在一阶单位或存在一个可行基，所以一开始就很容易地得到初始个可行基，所以一开始就很容易地得到初始基本可行解。但是，在许多问题中，往往不基本可行解。但是，在许多问题中，往往不存在现行的可行基。而且当问题规模较大时，存在现行的可行基。而且当问题规模较大时，判断判断m阶矩阵是否满秩的计算量都是很大的。阶矩阵是否满秩的计算量都是很大的。那么如何才能快速得到一个可行基，使算法那么如何才能快速得到一个可行基，使

43、算法的迅速进入迭代过程呢？的迅速进入迭代过程呢？ 方法是通过引入方法是通过引入人工人工(造造)变量变量，即在，即在 原原问题的约束方程中加入人工变量形成一个可问题的约束方程中加入人工变量形成一个可作为基的单位阵，这样的单位阵称为人造基。作为基的单位阵，这样的单位阵称为人造基。 一般地，当给定的一般地，当给定的LPLP问题约束方程组的问题约束方程组的系数矩阵中不含有可作为基的单位阵时，则系数矩阵中不含有可作为基的单位阵时，则为每一个为每一个( (或部分或部分) )约束方程引入一个人工变约束方程引入一个人工变量，从而较容易地得到一个初始基本可行解。量，从而较容易地得到一个初始基本可行解。0jjij

44、ijxbxa0,injjiinjijxxbxxa 于是在新的约束方程组的系数矩阵中便得到一于是在新的约束方程组的系数矩阵中便得到一个个m阶单位阵，以阶单位阵，以mnnxx,1为基变量，易得为基变量，易得新约束条件下的一个基本可行解：新约束条件下的一个基本可行解：T21)0(), 0 , 0 , 0(mbbbX 因为人工变量是强行加入原约束方程组中的虚因为人工变量是强行加入原约束方程组中的虚拟变量，它可能破坏约束条件的等式关系，影响所拟变量，它可能破坏约束条件的等式关系，影响所求求LPLP问题的解。为此，需要对目标函数进行相应的问题的解。为此，需要对目标函数进行相应的修改，并构造一个新的修改，并

45、构造一个新的LP问题，通过求解新问题，问题，通过求解新问题，来获得原问题的最优解。根据对目标函数处理方法来获得原问题的最优解。根据对目标函数处理方法的不同，形成了不同的解决问题的方法，常用的有的不同，形成了不同的解决问题的方法，常用的有大大M法和两阶段法法和两阶段法实质上都是实质上都是SM的变形。的变形。 本部分内容，我们主要介绍本部分内容，我们主要介绍两阶段法两阶段法。两阶段法两阶段法 一、两阶段法原理一、两阶段法原理01jnjijijxbxanjjjxcz1max对于标准形式的对于标准形式的LPLP问题：问题：miiyw1max0,1ijnjiijijyxbyxa构造辅助构造辅助LPLP问

46、题：问题： 对于辅助对于辅助LPLP问题，显然存在基本可行解，问题，显然存在基本可行解，且对应的单纯形表易于构造，如下表所示：且对应的单纯形表易于构造，如下表所示：miib10 0 111miinmiiaambbb2112111maaamnnnaaa21001100mnyyxx 11myyy21bXB w 观察辅助观察辅助LP问题，易知它一问题，易知它一定有最优解，且定有最优解，且0maxwmiiyw1max0,1ijnjiijijyxbyxa辅助辅助LP问题：问题： 下面我们看一看辅助下面我们看一看辅助LP问题与原问题与原LP问题解之问题解之间的关系。间的关系。结论结论1 1：若：若 0ma

47、xw，则原问题无可行解。，则原问题无可行解。( (此结论用反证法易证此结论用反证法易证) ) 结论结论2 2：原问原问题有可行解的充题有可行解的充要条件是要条件是 0maxwmiiyw1max0,1ijnjiijijyxbyxa辅助辅助LP问题：问题： 综上，两阶段法的过综上，两阶段法的过程是：程是： 第一阶段：第一阶段：求解辅助求解辅助LP问题。问题。若若 0maxw，则原问题无可行解。，则原问题无可行解。若若 ，则得原问题一个基本可行解。，则得原问题一个基本可行解。0maxw第二阶段：第二阶段：求解原问题。求解原问题。 二、两阶段法基本步骤二、两阶段法基本步骤 对于一般的对于一般的LP问题

48、问题( (标准形式标准形式) )而言，两阶段法而言，两阶段法通过引入人工变量将问题的求解分为两个阶段。通过引入人工变量将问题的求解分为两个阶段。 阶段阶段：求解辅助求解辅助LP问题。判明原问题是否存问题。判明原问题是否存在可行解，若存在就找出一个初始基本可行解。在可行解，若存在就找出一个初始基本可行解。 用用SM求解辅助求解辅助LP问题，最终单纯形表可能出现问题，最终单纯形表可能出现以下几种情况：以下几种情况：(1)(1)若若 0maxw，则原问题无可行解，停止计算。，则原问题无可行解，停止计算。(2)(2)若若 ，且人工变量都不是基变量，则，且人工变量都不是基变量，则得得0maxw原问题一个

49、基本可行解。转入阶段原问题一个基本可行解。转入阶段求解原问题。求解原问题。 阶段阶段：求解原问题。求解原问题。 首先首先，建立原问题的初始单纯形表。只需把，建立原问题的初始单纯形表。只需把阶段阶段的最终单纯形表修改如下：的最终单纯形表修改如下：(3)(3)若若 ，但最优基变量中存在人工变量，但最优基变量中存在人工变量，0maxw且相应行中原始变量对应的系数全部为且相应行中原始变量对应的系数全部为0 0，则说明，则说明原问题的该约束方程是多余的，此时删去相应行，原问题的该约束方程是多余的，此时删去相应行，并转入阶段并转入阶段求解原问题。求解原问题。(4)(4)若若 ，且人工变量存在最优基变量中，

50、且人工变量存在最优基变量中，0maxw但相应行中原始变量对应的系数不全部为但相应行中原始变量对应的系数不全部为0 0，此时，此时以非零系数其中之一为主元进行一次换基迭代，从以非零系数其中之一为主元进行一次换基迭代，从而使人工变量变为非基变量，并转入阶段而使人工变量变为非基变量，并转入阶段求解原求解原问题。问题。 (1)(1)删去人工变量诸列；删去人工变量诸列； (2) (2)采用第二种形式的单纯形表，把采用第二种形式的单纯形表，把c cj j行与行与C CB B列的数字添上；列的数字添上； (3) (3)用用z z替代替代w w，并计算原问题相应基本可行解，并计算原问题相应基本可行解的目标函数

51、值和检验数；的目标函数值和检验数； 这样就得到原问题的初始单纯形表。这样就得到原问题的初始单纯形表。 然后然后，进行单纯形法迭代，直到运算结束。，进行单纯形法迭代，直到运算结束。此过程中，可判定问题有此过程中，可判定问题有无界解无界解或有或有多重最优解多重最优解。 下面举例说明两阶段法的应用。下面举例说明两阶段法的应用。三、三、两阶段法两阶段法应用举例应用举例313 maxxxz0,93 124 32132321321xxxxxxxxxxx解解：(1)(1)首先将问题化首先将问题化 为标准形式：为标准形式：0,9 3 1 2-4 5132 5321 4321xxxxxxxxxxxx313 ma

52、xxxz例例：用单纯形法求解下用单纯形法求解下列问题：列问题： (2)(2)构造辅助构造辅助LPLP问题，并求其最优解：问题，并求其最优解： 观察该问题的约束系数矩阵，并不存在可作观察该问题的约束系数矩阵，并不存在可作为基的单位阵，因此需引入人工变量构造辅助为基的单位阵，因此需引入人工变量构造辅助LP问题。但构造辅助问题。但构造辅助LPLP问题时，并不需要每个约束问题时，并不需要每个约束方程均需引入人工变量。因此，可构造如下辅助方程均需引入人工变量。因此，可构造如下辅助LPLP问题：问题：0,9 3 1 2-4 7173265321 4321xxxxxxxxxxxxxx76 maxxxw 求解

53、求解辅助辅助LPLP问题的过程如下表所示：问题的过程如下表所示：-102-400100411110001 1-2-2 1 1 -1-10 0-1-11 10 09 90 03 31 10 00 00 01 17654321 xxxxxxx764xxxwbXB 初始表初始表0000001100001-1/21/2-1/23 30 01 11/31/30 00 00 01/31/31 11 10 02/32/30 01/21/2-1/21/61/67654321 xxxxxxx124xxxwbXB 最优表最优表 由辅助由辅助LPLP问题最优表可见，其最优值为问题最优表可见，其最优值为0 0，且最优

54、基变量中不含有人工变量，因此得到原且最优基变量中不含有人工变量，因此得到原问题的一个问题的一个基本可行解。基本可行解。这样我们就可以构造这样我们就可以构造原问题的初始单纯形表，从而进入第二阶段求原问题的初始单纯形表，从而进入第二阶段求解。解。0000001100001-1/21/2-1/23011/30001/31102/301/2-1/21/67654321 xxxxxxx124xxxwbXB (3)(3)构造原问题的初始单纯形表，并求其最优构造原问题的初始单纯形表，并求其最优解。如下表所示：解。如下表所示：-30100-300-30-3/2000001-1/203011/300-31102

55、/301/254321 xxxxx124xxxzbXB jcBC3/29/20003/4000001-1/205/2-1/2100-1/4-33/23/20103/4324xxxzBC 根据上表，得原问题的最优解与最优值为：根据上表，得原问题的最优解与最优值为：-301003/29/20003/4000001-1/205/2-1/2100-1/413/23/20103/454321 xxxxxbXB jcBC324xxxz 去掉引入变量，得原始问题的最优解与最优值为：去掉引入变量，得原始问题的最优解与最优值为：23T2325*max ,)0 , 0 , 0(zX23T2325*max ,),

56、0(zX 关于单纯形法的计算效率关于单纯形法的计算效率 许多从事数学规划研究的人员都曾指出：许多从事数学规划研究的人员都曾指出：SMSM从理论上看并不是有效的算法。因为这种算从理论上看并不是有效的算法。因为这种算法只是在相邻基本可行解之间迭代。于是人们法只是在相邻基本可行解之间迭代。于是人们产生这样一种想法：要是使产生这样一种想法：要是使SMSM能同时考察非相能同时考察非相邻的基本可行解，那么达到最优就会快些。但邻的基本可行解，那么达到最优就会快些。但是，对于单纯形法改革的许多方案，在总的计是，对于单纯形法改革的许多方案，在总的计算时间方面并未产生显著的效果，所以上述的算时间方面并未产生显著的

57、效果，所以上述的单纯形法仍被认为是求解单纯形法仍被认为是求解LPLP的最好方法。的最好方法。 SMSM的计算效率依赖于：的计算效率依赖于：(1)(1)达到最优解前的达到最优解前的迭代次数；迭代次数；(2)(2)解决问题总的计算时间。解决问题总的计算时间。 计算数以千计的计算数以千计的LP实际问题积累的实践经实际问题积累的实践经验表明，具有验表明，具有m个约束条件和个约束条件和n n个变量的标准形个变量的标准形式的式的LP问题的迭代次数介于问题的迭代次数介于m与与3m之间，平均之间，平均为为2m。迭代次数的实际上限是迭代次数的实际上限是2(m+n)。 总的计算时间大约与约束条件个数的立方总的计算

58、时间大约与约束条件个数的立方(m3)成正比。即若问题成正比。即若问题的约束条件个数是问的约束条件个数是问题题的的2倍，则问题倍，则问题的计算时间大约是问题的计算时间大约是问题的的8倍。倍。 由此可见，由此可见，SMSM的计算效率对约束条件个数的的计算效率对约束条件个数的变化比对于变量个数的变化更为敏感。因此，变化比对于变量个数的变化更为敏感。因此，在解决实际问题时，应尽是避免多余的约束条在解决实际问题时，应尽是避免多余的约束条件，使约束条件个数尽可能地少。件，使约束条件个数尽可能地少。4 改进单纯形法改进单纯形法 虽然虽然SM的表格算法是求解的表格算法是求解LPLP问题行之有问题行之有效的算法

59、。但在计算过程中，每次迭代必须效的算法。但在计算过程中，每次迭代必须对所有的列进行运算。而实际上必不可少的对所有的列进行运算。而实际上必不可少的运算只有下列几项：运算只有下列几项： 1 1、计算相应于基本可行解的非基变量的、计算相应于基本可行解的非基变量的检验数。检验数。或或 jnjbczcPBCjjjjjBj, 2 , 1 01njbbbjjss, 2 , 1 , 0 min000或或 njbjsj, 2 , 1 , 0 min0。此时用到。此时用到3 3、确定换出变量、确定换出变量rJx，及其所对应的列，及其所对应的列向量向量rJpspB1。4 4、将基变换的运算施于、将基变换的运算施于这

60、需要确定新的基这需要确定新的基sp及及b等；等；B的逆阵的逆阵1B。2 2、确定换入变量、确定换入变量sx，及其所对应的列，及其所对应的列向量向量sp。 改进改进SM就是针对这些在每次迭代中必不可就是针对这些在每次迭代中必不可少的运算进行的，从而大大地提高了计算效率，少的运算进行的，从而大大地提高了计算效率，而且节省计算机的存贮空间和节约计算时间，并而且节省计算机的存贮空间和节约计算时间，并可在中、小型计算机上求解一些大型的可在中、小型计算机上求解一些大型的LP问题。问题。B为了完成为了完成1 1、2 2、3 3，必须计算出当前可行基，必须计算出当前可行基的逆阵的逆阵1B。如果每次迭代都重新计