2-线性规划的单纯形法6_两阶段法.ppt
Page 1第二章第二章 线性规划的单纯形法线性规划的单纯形法Page 2本本 章章 重重 点点J单纯形法的基本概念和思想单纯形法的基本概念和思想J单纯形法的计算步骤单纯形法的计算步骤J大大M法法和和两阶段法两阶段法J退化问题退化问题Page 3单纯形法的基本思想单纯形法的基本思想n寻找一组初始基本变量寻找一组初始基本变量n直接观察，在线性规划中存在直接观察，在线性规划中存在m个基本变量个基本变量n如果约束条件都是如果约束条件都是约约束，将束，将增加的松弛变量增加的松弛变量作为基本变量，得到一组基本可行解作为基本变量，得到一组基本可行解n如果约束条件有如果约束条件有约束，这是增加的是剩余变约束，这是增加的是剩余变量，这时对于每个约束增加一个变量，将增加量，这时对于每个约束增加一个变量，将增加的变量作为基本变量，得到一组基本可行解。的变量作为基本变量，得到一组基本可行解。不容易不容易以后还要以后还要讨论讨论Page 4大大M法法n如果约束条件有如果约束条件有约束，这是增加的是剩约束，这是增加的是剩余变量，这时对于每个约束增加一个变量，余变量，这时对于每个约束增加一个变量，将增加的变量作为基本变量，得到一组基将增加的变量作为基本变量，得到一组基本可行解本可行解大大M法法n例：例：Page 5大大M法法n转化为标准形式转化为标准形式n引入两个新变量引入两个新变量基变量？基变量？MM是任意大的正数，所以目标是任意大的正数，所以目标是任意大的正数，所以目标是任意大的正数，所以目标函数取得最大值时函数取得最大值时函数取得最大值时函数取得最大值时 Page 6cj3-1-100-M-MCBxBx1x2x3x4x5x6x7b0 x41-2110001111-Mx6-4120-11031.5-Mx7-201000111sacj6M-M-3M0M-M-M=-4Mimpj3-6M-1+M3M-10-M000 x43-20100-110-Mx60100-11-211-1x3-20100011sacj2-M-10M-M2M-1=-M-1impj1M-100-M0-3M-1Page 7cj3-1-100-M-MCBxBx1x2x3x4x5x6x7b0 x43-20100-110-Mx60100-11-211-1x3-20100011sacj2-M-10M-M2M-1=-M-1impj1M-100-M0-3M-10 x43001-22-5124-1x20100-11-21-1x3-20100011sacj2-1-101-11=-2impj1000-1-M+1-M-1Page 8cj3-1-100-M-MCBxBx1x2x3x4x5x6x7b0 x43001-2124-1x20100-11-1x3-201001sacj2-1-101=-2impj1000-13x11001/3-2/34-1x20100-11-1x30012/3-4/39sacj3-1-11/31/3=2impj000-1/3-1/3Page 9大大M法法n例：用大M法求解线性规划问题n首先：转化为标准形式，增加松弛变量、剩余变量和人工变量Page 10cj3200-MCBxBx1x2x3x4x5b0X32110022-Mx5340-11123sacj-3M-4M0M-M=-12Mimpj3+3M2+4M0-M02x22110010-Mx5-50-4-114sacj4+5M24M+2M-M=-4M+20impj1-5M0-4M-2-M0Page 11大大M法法n最优解（0，2，0，0，4），但现在最优解包含人工变量，这说明该问题对于原问题是不可行的，因此原问题无解。n从图中可以看出，可行域为空集Page 12大大M法法n通过设置新的变量得到初始基本变量，并通过在目标函数中设置新变量的价格系数为-M使得在优化过程中，新变量的值优化为0n在计算机求解过程中，由于计算机只能对M设置有限大的数值，所以在计算过程中可能会产生误差，为了解决这个问题，产生了两阶段法Page 13两阶段法两阶段法n第一阶段的目的：是设法把人工变量从基内调出来，寻找原问题（未加人工变量前的线性规划问题）的一个基本可行解。具体作法如下：n不考虑原问题的目标函数，构造一个辅助目标函数，使所有人工变量的和最小。设有L个人工变量，构造如下的辅助目标函数：Page 14两阶段法两阶段法n新的目标函数和原问题的约束条件所构成的线性规划问题，称为辅助目标函数用单纯形法求解得到该问题的最优解后，有下面两种情况：n如果w0，则表明人工变量还在基内，原问题无解，停止计算。n如果w=0，则表明人工变量全部出基，从而可得到原问题的一个基本可行解，即可进行第二阶段；n第二阶段：以第一阶段求得最优解作为初始基本可行解，求原问题的最优解。n以第一阶段求得最优解作为初始基本可行解，再用第一阶段求得最优解时的约束条件和原问题的目标函数进行迭代，直到求出最优解。Page 15两阶段法两阶段法n例：例：Page 16两阶段法两阶段法n第一阶段：第一阶段：Page 17cj00000-1-1CBxBx1x2x3x4x5x6x7b-1x61-1-1001011-1X7120-1001220X501001001-sacj-2-1110-1-1z=-3impj21-1-10000 x11-1-100101-1X7031-10-1111/30X5010010011sacj0-3-1101-1z=-1impj031-10-20Page 18cj00000-1-1CBxBx1x2x3x4x5x6x7b0 x11-1-100101-1X7031-10-1111/30X5010010011sacj0-3-1101-1=-1impj21-1-10000 x110-2/3-1/302/31/34/30X2011/3-1/30-1/31/31/30X500-1/31/311/3-1/32/3sacj0000000=0impj00000-1-1Page 19两阶段法两阶段法n第二阶段：将解（4/3，1/3，0，0，1/3）作为原始线性规划问题的可行解，并将第一阶段得到的约束条件一起进行运算Page 20cj-2-1000CBxBx1x2x3x4x5b-2x110-2/3-1/304/3-1X2011/3-1/301/30X500-1/31/312/3sacj-2-1110=-3impj00-1-10Page 21n例例s.t.Page 22cj0000-1CBxBx1x2x3x4x5b0X32110022-1x5340-11123sacj-3-401-1=-12impj340-100 x2211002-1x5-50-4-114sacj5041-1=-4impj-50-4-10Page 23n得到最优解（0，2，0，0，4），此时 依然在基中，所以原问题没有最优解。Page 24两阶段法两阶段法-练习练习n例：例：Page 25cj00000-1-1CBxBx1x2x3x4x5x6x7b0 x41-2110001111-1X6-4120-11031.5-1X7-201000111sacj6-1-301-1-1z=-4impj-6130-1000X43-20100-110-1X60100-110110X3-20100011-sacj0-1001-10z=-1impj0100-10-1Page 26cj00000-1-1CBxBx1x2x3x4x5x6x7b0X43-20100-110-1X60100-110110X3-20100011-sacj0-1001-10z=-1impj0100-10-10X43001-22-1120X20100-11010X3-20100011sacj0000000z=0impj00000-1-1Page 27n进入第二阶段：带入初始可行解（进入第二阶段：带入初始可行解（0，1，1，12，0）和上一阶段的约束条件）和上一阶段的约束条件Page 28cj3-1-100CBxBx1x2x3x4x5b0X43001-2124-1X20100-11-1X3-201001-sacj2-1-101z=-2impj1000-13X11001/3-2/34-1X20100-11-1X30012/3-4/39sacj3-1-11/31/3z=2impj000-1/3-1/3Page 29n得到最优解（得到最优解（4，1，9，0）最优值）最优值2Page 30退化问题退化问题n前面介绍的单纯形法是在线性规划问题前面介绍的单纯形法是在线性规划问题没没有退化有退化的前提的进行的，单纯形法可以通的前提的进行的，单纯形法可以通过过有限步有限步的优化达到最优值的优化达到最优值n如果出现退化的情况，？如果出现退化的情况，？Page 31退化问题退化问题n例例Page 32cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b0X11001/4-8-19000X20101/2-12-1/23000X300100101-sacj0000000z=0impj0003/4-201/2-63/4X44001-32-4360-0X2-210043/2-15000X300100101-sacj3003/4-24-327Z=0impj-300047/2-33Page 33cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b3/4X44001-32-4360-0X2-210043/2-15000X300100101-sacj3003/4-24-327Z=0impj-300047/2-333/4X4-1280108-8400-20X5-1/21/40013/8-15/4000X3001001011sacj1103/4-20-3/212Z=0impj-1-10002-18Page 34cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b3/4X4-1280108-8400-20X5-1/21/40013/8-15/4000X300100101-sacj1103/4-20-3/212Z=0impj-1-10002-181/2X6-3/2101/801-21/20-20X51/16-1/80-3/64103/16000X33/2-11-1/80021/212/21Sacj-2301-201/2-9Z=0impj2-30-1/4003Page 35cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b1/2X6-3/2101/801-21/20-20X51/16-1/80-3/64103/16000X33/2-11-1/80021/21-sacj-2301-201/2-9Z=0impj2-30-1/40031/2X62-60-5/2561000-6X71/3-2/30-1/416/301000X3-2615/2-56001-sacj-1101/4-41/2-6Z=0impj1-101/2-1600Page 36cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b1/2X62-60-5/2561000-6X71/3-2/30-1/416/301000X3-2615/4-56001-sacj-1101/4-41/2-6Z=0impj1-101/2-24000X11-30-5/4281/200-6X701/301/6-4-1/61000X300100101-sacj0-20-12410Z=0impj0207/4-44-1/2-6Page 37cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b0X11-30-5/4281/200-6X701/301/6-4-1/61000X300100101-sacj0-20-12410Z=0impj0207/4-44-1/2-60X11001/4-8-1900X20101/2-12-1/2300X300100101sacjZ=0impjPage 38退化问题退化问题n为了避免循环，人们已经想出了许多办法，这里为了避免循环，人们已经想出了许多办法，这里介绍一种介绍一种Bland规则，具体步骤如下：规则，具体步骤如下：n 选主元列：在检验数为正值的列中取下标最小的列选主元列：在检验数为正值的列中取下标最小的列（即从左到右第一个取正值的检验数对应的列）为主（即从左到右第一个取正值的检验数对应的列）为主元列，可表示为：元列，可表示为：主元列下标主元列下标Kminj|n选主元行：根据最小非负比值规则来确定出换出变量，选主元行：根据最小非负比值规则来确定出换出变量，如果最小比值变量不止一个，那么取基本变量下标最如果最小比值变量不止一个，那么取基本变量下标最小者作为换出变量小者作为换出变量n下面把上例中选主元列，选主元行的方法用下面把上例中选主元列，选主元行的方法用Bland规则加以修正，用此规则求解上例规则加以修正，用此规则求解上例Page 39cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b0X11001/4-8-19000X20101/2-12-1/23000X300100101-sacj0000000z=0impj0003/4-201/2-63/4X44001-32-4360-0X2-210043/2-15000X300100101-sacj3003/4-24-327Z=0impj-30004-5/2-33Page 40cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b3/4X44001-32-4360-0X2-210043/2-15000X300100101-sacj3003/4-24-327Z=0impj-30004-5/2-333/4X4-1280108-8400-20X5-1/21/40013/8-15/4000X300100101-sacj1103/4-20-3/212Z=0impj-1-10002-18Page 41cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b3/4X4-1280108-8400-20X5-1/21/40013/8-15/4000X300100101-sacj1103/4-20-3/212Z=0impj-1-10002-181/2X6-3/2101/801-21/20-20X51/16-1/80-3/64103/16000X33/2-11-1/80021/21-Sacj-2301-201/2-9Z=0impj2-30-1/4003Page 42cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b1/2X6-3/2101/801-21/20-20X51/16-1/80-3/64103/16000X33/2-11-1/80021/21-sacj-2301-201/2-9Z=0impj2-30-1/40031/2X60-20-1241-60-0X11-20-3/416030-0X30211-240611sacj0-10-1/2121/2-3Z=0impj0105/4-320-3Page 43cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b1/2X60-20-1241-60-0X11-20-3/416030-0X30211-240611sacj0-10-1/2121/2-3Z=0impj0105/4-320-31/2X600100101-0X11011/4-809140X2011/21/2-12031/21sacj001/2001/20Z=1/2impj00-1/23/4-200-6不再是退化问题不再是退化问题不再是退化问题不再是退化问题不使用不使用不使用不使用blandbland规则规则规则规则Page 44cj0003/4-201/2-6CBxBx1x2x3x4x5x6x7b1/2X600100101-0X11011/4-809140X2011/21/2-12031/21sacj001/2001/20Z=1/2impj00-1/23/4-200-61/2X6001001010X1103/40-2015/23/43/4X40211-24061sacj03/25/43/4-181/29/2Z=5/4impj0-3/2-5/40-20-21/2Page 45退化问题退化问题n我们看到使用我们看到使用Bland规则，在单纯形法中去规则，在单纯形法中去选取主元列、主元行，在求解退化问题的选取主元列、主元行，在求解退化问题的情况下，求出了最优基本可行解，而没有情况下，求出了最优基本可行解，而没有发生循环。这有下面定理来保证使用发生循环。这有下面定理来保证使用Bland规则不会发生循环现象。规则不会发生循环现象。n定理定理2.3 若在单纯形法的算法中使用若在单纯形法的算法中使用Bland规则选取主元列、主元列，则在迭代过程规则选取主元列、主元列，则在迭代过程中不会出现循环。中不会出现循环。Page 46退化问题练习退化问题练习Page 47cj1200CBxBx1x2x3x4b0X3-11100-0X43-10131sacj0200z=0impj12000X302/311/311.51X11-1/301/31-sacj1-1/301/3Z=1impj07/300Page 48cj1200CBxBx1x2x3x4b0X302/311/31-1X11-1/301/311sacj1-1/301/3Z=0impj07/3002X2013/21/23/21X1101/21/23/2sacj127/23/2Z=9/2impj00-7/2-3/2Page 49练习题练习题1、大大M法法求求解解下下列列线线性性规规划划问问题题，并并指指出出问问题的解属于哪一类：题的解属于哪一类：(1)max z 4x15x2 x3 st.3x12x2 x318 2x1 x2 4 x1 x2 x35 xj 0 （j1,2,3）Page 502、用两阶段法求解下列线性规划问题，并指、用两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：出问题的解属于哪一类：max z 2x1 x2 x3 st.4x12x22x34 2x14x2 20 4x18x22x316 xj 0 （j1,2,3）Page 51答案答案n无解无解n多重最优解：多重最优解：X1（4，0，0）；）；X2（0，0，8）n Page 52谢谢大家！谢谢大家！
