运筹学课件 单纯形法的进一步讨论

运筹学教程第五节单纯形法的进一步讨论分类及处理原则：（1）类型一：目标要求是“Max”，约束条件是“≤”类型——左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。运筹学教程（2）类型二：目标要求是“Max”，约束条件是“=”类型——左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵。（3）类型三：目标要求是“Max”，约束条件是“≥”类型——约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。运筹学教程一、人工变量法：大M法——在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0，罚因子），只要人工变量取值大于0，目标函数不可能实现最优。迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化。运筹学教程单纯形法求解线性规划问题093124.3max313232132131xxxxxxxxxstxxZ运筹学教程093124.003max71732653214321765431xxxxxxxxxxxxxstMxMxxxxxZ化为标准型，添加人工变量，构造单位矩阵001301011201111P1P2P3P4P5764100010001PPP运筹学教程0973124.003max5132653214321765431xxxxxxxxxxxxxstMxMxxxxxZp6,p7与p4构成单位矩阵,对应的变量x6,x7,x4为基变量，其余变量为非基变量，得到初始基可行解X=(0,0,0,4,0,1,9)T,列出初始单纯形表。100100001301011201111p1p2p3p4p5p6p7运筹学教程Cj-30100-M-MCB基bX1X2X3X4X5X6X70X441111000-MX61-21-10-110-MX790310001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)-2M-34M10-M00运筹学教程Cj-30100-M-MCB基bX1X2X3X4X5X6X70X441111000-MX61-2[1]-10-110-MX790310001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)-2M-34M10-M00X2为进基变量；x6为出基变量；进行变换计算：p4,p2,p7单位矩阵11)39,11,14min(x201r2×(-1)+r1r2×(-3)+r3033211-10066403-31运筹学教程Cj-30100-M-MCB基bX1X2X3X4X5X6X70X4330211-100X21-21-10-110-MX76[6]0403-31σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)6M-304M+103M-4M0X1-31102/301/2-1/21/63011/30001/300001-1/2-1/21/200303/2-M-3/2-M+1/2运筹学教程Cj-30100-M-MCB基bX1X2X3X4X5X6X70X400001-1/2-1/21/20X23011/30001/3-3X1110[2/3]01/2-1/21/6σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)00303/2-M-3/2-M+1/2运筹学教程Cj-30100-M-MCB基bX1X2X3X4X5X6X70X400001-1/21/2-1/20X25/2-1/2100-1/4-1/41/41X33/23/20103/4-3/41/4σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)-9/2000-3/4-M+3/4-M-1/4运筹学教程二、两阶段法第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。第二阶段：在原问题中去除人工变量，并从此可行解出发，继续求解最优解。求解上述例题。运筹学教程第一阶段求解：093124.min7173265321432176xxxxxxxxxxxxxstxxW化成标准型093124.'max7173265321432176xxxxxxxxxxxxxstxxWp4,p6,p7构成单位矩阵先求只有人工变量的LP运筹学教程Cj00000-1-1CB基bX1X2X3X4X5X6X70X441111000-1X61-2[1]-10-110-1X790310001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)-2410-100X2进基变量；x6出基变量；运筹学教程Cj00000-1-1CB基bX1X2X3X4X5X6X70X4330211-100X21-21-10-110-1X76[6]0403-31σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)60403-40X1进基变量；x7出基变量；运筹学教程Cj00000-1-1CB基bX1X2X3X4X5X6X70X400021-1/21/2-1/20X23011/30001/30X11102/301/2-1/21/6σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)00000-1-1运筹学教程第二阶段：在原问题中去除人工变量，并从此可行解出发，继续求解最优解。目标函数543210003maxxxxxxZCj-30100CB基bX1X2X3X4X50X400001-1/20X23011/300-3X1110[2/3]01/2σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)00303/2运筹学教程Cj-30100CB基bX1X2X3X4X50X400001-1/20X25/2-1/2100-1/41X33/23/20103/4σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)-9/2000-3/4检验数均小于等于0，得到最优解。运筹学教程①最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值；②最优表中，基变量中仍含有非零人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！总结运筹学教程三、迭代过程中可能出现的问题及处理方法1、目标函数极小化时解的判别，将检验数≥0做为判别表中解是否最优的标志。2、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？（如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无界解）运筹学教程3、现若干个相同的最小比值（说明出现了退化的基本可行解，可能数学模型存在多余的约束,使多个基可行解对应同一个顶点。从相同比值对应的基变量中选下标最小的基变量作为换出变量,可以避免出现“死循环”现象）.选择进基变量时，同时有若干个正检验数，最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基(下标较小的变量).运筹学教程4、无可行解的判别当线性规划问题添加人工变量后进行求解过程中，初始单纯形表中的解含有非零的人工变量，实际是非可行解；当求解结果出现所有的检验数≤0，如果基变量中仍含有非零的人工变量，表明问题无可行解。运筹学教程06222.002max06222.2max5154213215432121212121xxxxxxxxstMxxxxxZxxxxxstxxZ解加入人工变量例无可行解运筹学教程Cj2100-MCB基bx1x2x3x4x50x32[1]1100-Mx56220-11Cj-Zj2+2M1+2M0-M02x1211100-Mx5200-2-11Cj-Zj0-1-2-2M-M0基变量中人含有非零的人工变量X5=2，所以线性规划问题无可行解。运筹学教程练习:大M法求解下列线性规划0,,02226.22max3213231321321xxxxxxxxxxstxxxz运筹学教程002226.00022max819632853174321987654321xxxxxxxxxxxxxxstMxMxMxxxxxxxz运筹学教程cj2-12000-M-M-MCB基bX1X2X3x4x5x6x7x8x9-Mx76111-100100-Mx82-2010-10010-Mx9002-100-1001Cj-Zj2-M-2+3M2+M-M-M-M000运筹学教程cj2-12000-M-M-MCB基bX1X2X3x4x5x6x7x8x9-Mx76113/2-10010-1/2-Mx82-2010-10010-1x2001-1/200-1/2001/2Cj-Zj2-M03/2+5M/2-M-M-1/200-M/2+0.5运筹学教程cj2-12000-M-M-MCB基bX1X2X3x4x5x6x7x8x9-Mx73400-13/201-3/2-1/22x32-2010-10010-1x211100-1/2-1/201/21/2Cj-Zj4M+500-M1.5M+1.5-1/20-2.5M-1.5-1.5M+0.5运筹学教程cj2-12000-M-M-MCB基bX1X2X3x4x5x6x7x8x92x13/4100-1/43/801/4-3/8-1/82x37/2001-1/2-1/401/21/4-1/4-1x23/4010-1/4-1/8-1/21/41/83/8Cj-Zj0005/4-3/8-1/2-M-5/43/8-M-M-0.75检验数5/4大于0，Pj≤0,无界运筹学教程练习:两阶段法求解下列线性规划0,,02226.22max3213231321321xxxxxxxxxxstxxxz运筹学教程789123471358236918max622.200Wxxxxxxxxxxxxstxxxxx第一阶段:建立辅助LP运筹学教程cj000000-1-1-1CB基bX1X2X3x4x5x6x7x8x9-1x76111-100100-1x82-2010-10010-1x900[2]-100-1001Cj-Zj-131-1-1-1000运筹学教程cj000000-1-1-1CB基bX1X2X3x4x5x6x7x8x9-1x76103/2-101/210-1/2-1x82-20[1]0-100100x2001-1/200-1/2001/2Cj-Zj-105/2-1-11/200-3/2运筹学教程cj000000-1-1-1CB基bX1X2X3x4x5x6x7x8x9-1x73400-13/21/21-3/2-1/20x32-2010-100100x21-1100-1/2-1/20-1/21/2Cj-Zj400-11.50.50-1.5-0.5运筹学教程cj000000-1-1-1CB基bX1X2X3x4x5x6x7x8x90x13/4100-1/43/81/81/4-3/8-1/80x37/2001-1/2-1/41/41/21/41/40x27/4010-1/4-1/8-3/81/21/83/8Cj-Zj000000-1-1-1运筹学教程12345123413523615max2200622.2