03.2大M法和两阶段法

第二节大M法和两阶段法如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。人工变量只起过渡作用，不应影响决策变量的取值。两种方法可控制人工变量取值。大M法两阶段法例3,2,1,012324112..3min31321321321jxxxxxxxxxtsxxxFj解：引入松弛变量x4、剩余变量x5，将数学模型标准化5,4,3,2,1,012324112..3'max3153214321321jxxxxxxxxxxxtsxxxFj观察约束条件系数矩阵AA矩阵不存在完全单位向量组。应人工地构建一个完全单位向量组。001021021401121A人为增加两列相当于又加入两个变量x6、x7100010201102140001121A调整后的A矩阵还原成约束条件为：由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是0。7,,2,1,012324112..731653214321jxxxxxxxxxxxxxtsj5,4,3,2,1,012324112..3153214321jxxxxxxxxxxxtsj两种方法可控制人工变量的取值大M法两阶段法一、大M法原理：引入一个非常大的正数M，用来制约人工变量的取值，并使目标函数变为：这样，如果计算结果xt≠0，那么由于M是一个非常大的正数，可以使得F0，也就是使F无法达到最大值。所以，M也被称为罚金系数，这种方法称为大M法。为人工变量）ttjjxxMxcF(max例：加入人工变量x6，x7后，原模型变为：7,,2,1,012324112..)(003'max7316532143217654321jxxxxxxxxxxxxxtsxxMxxxxxFj用单纯形法求解此时，各系数矩阵、向量为：100010201102140001121AMMc001131311B段Cj→03-1-100-M-MQi↓基bP1P2P3P4P5P6P710X4111-211000-Mx63-4120-110-Mx71-2010001Cj-Zj→初始表段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-211000-Mx63-4120-110-Mx71-2010001Cj-Zj→4M-6M+3M-13M-10-M00检验数判断1、检验数Cj-Zj=aM+b：当a0时，认为检验数为负；当a0时，认为检验数为正。2、若最终检验数Zj-Cj均为非正，而b列中对应的检验数Cb-Zb（即最优值）中仍有M存在，说明没有得到确定的最优值，可以解释为约束条件过于苛刻，该线性规划问题无可行解。段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M00段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x40-Mx60-1x31-2010001Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610100-11-2-1x31-2010001Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-2-1x31-2010001Cj-Zj→M+11M-100-M0-3M+1段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-2-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x40-1x210100-11-2-1x30Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-2-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x412（3）001-22-5-1x210100-11-2-1x31-2010001Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-2→-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x412（3）001-22-5→-1x210100-11-2-1x31-2010001Cj-Zj→21000-1-M+1-M-1段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-2→-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x412（3）001-22-5→-1x210100-11-2-1x31-2010001Cj-Zj→21000-1-M+1-M-143x141001/3-2/32/3-5/3-1x20-1x30Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-21→-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x412（3）001-22-5→-1x210100-11-2-1x31-2010001Cj-Zj→21000-1-M+1-M-143x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Cj-Zj→段Cj→03-1-100-M-MQi注↓基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011→Cj-Zj→4M-6M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-21→-1x31-2010001Cj-Zj→M+11M-100-M0-3M+130x412（3）001-22-5→-1x210100-11-2-1x31-2010001Cj-Zj→21000-1-M+1-M-143x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Cj-Zj→-2000-1/3-1/3-M+1/3-M+2/3结论∵Zj-Cj均为负数，∴得到最优解和最优值。x1=4，x2=1，x3=9，x4=x5=x6=x7=0，minF=-maxF’=-2二、两阶段法：原理：分两阶段求解。第一阶段，构筑一个只包括人工变量的目标函数：minF=∑xt，在原约束条件下求解，如果计算结果是人工变量均为0，则继续求解；进入第二阶段，如果人工变量不为0，说明原问题无解。如上例：人工变量为x6，x7，第一阶段7,,2,1,012324112..'maxmin7316432153217676jxxxxxxxxxxxxxtsxxFxxFj解题过程段Cj→000000-1-1Qi注↓基bP1P2P3P4P5P6P710x5111-21010011-1x63-412-10103/2-1x71-20（1）00011→Cj-Zj→4-613-100020x5103-20010-1-1x610（1）0-101-2→0x31-2010001Cj-Zj→1010-100-330x512300-212-50x21010-101-20x31-2010001Cj-Zj→000000-1-1结论此时，目标函数已得最优值，人工变量均为0。转入第二阶段。第二阶段求原问题最优值。目标函数为原问题的目标函数，单纯形表初始表为第一阶段最后一段的元素值，但应去掉人工变量所在列。maxF’=3x1-x2-x3+0x4+0x5解题过程段Cj→03-1-100Qi注↓基bP1P2P3P4P510x512（3）00-21→-1x21010-10-1x31-20100Cj-Zj→2100-1023x14100-2/31/3-1x21010-10-1x39001-4/32/3Cj-Zj→-2000-1/3-1/3结论∵Zj-Cj均为正数，∴得到最优解和最优值。x1=4，x2=1，x3=9，x4=x5=0，minF=-2例2：用大M法和两阶段法求解,4,3,2,1,0763222..2max4321432143214321jxxxxxxxxxxxxxtsxxxxFj大M法引入人工变量x5，x6，x7，将原问题化为7,,2,1,0763222..)(2max7433164321543217654321jxxxxxxxxxxxxxxxxtsxxxMxxxxFj解题过程段Cj→0-2-111-M-M-MQi注↓基bP1P2P3P4P5P6P71-Mx52（1）-12-11002→-Mx6621-310103-Mx7711110017Cj-Zj→15M4M-2M-11M+1000段Cj→0-2-111-M-M-MQi注↓基bP1P2P3P4P5P6P71-Mx52（1）-12-11002→-Mx6621-310103-Mx7711110017Cj-Zj→15M4M-2M-11M+10002-2x121-12-1100-Mx6203-7（3）-2102/3→-Mx7502-12-1015/2Cj-Zj→7M+405M-3-8M+55M-1-4M+200段Cj→0-2-111-M-M-MQi注↓基bP1P2P3P4P5P6P71-Mx52（1）-12-11002→-Mx6621-310103-Mx7711110017Cj-Zj→15M4M-2M-11M+10002-2x121-12-1100-Mx6203-7（3）-2102/3→-Mx7502-12-1015/2Cj-Zj→7M+405M-3-8M+55M-1-4M+2