《运筹学大M法学习.pptx》由会员分享，可在线阅读，更多相关《运筹学大M法学习.pptx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、例第1页/共16页解：引入松弛变量x4、剩余变量x5，将数学模型标准化第2页/共16页观察约束条件系数矩阵AA矩阵不存在完全单位向量组。应人工地构建一个完全单位向量组。第3页/共16页人为增加两列相当于又加入两个变量 x6、x7第4页/共16页调整后的A矩阵还原成约束条件为：由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是0。第5页/共16页大M法的原理 引入一个非常大的正数M，用来制约人工变量的取值，并使目标函数变为：这样，如果计算结果xt0，那么由于M是一个非常大的正数，可以使得F0，也就是使F无法达到最大值。所以，M也被称为罚金系数，这种方法称为大M法
2、。第6页/共16页例：加入人工变量x6，x7后，原模型变为：第7页/共16页用单纯形法求解此时，各系数矩阵、向量为：第8页/共16页段段Cj03-1-100-M-MQi注注基基bP1P2P3P4P5P6P710 x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011Cj-Zj4M-6M+3M-13M-10-M0020 x4103-20100-1-Mx610（1）00-11-21-1x31-2010001Cj-ZjM+11M-100-M0-3M+130 x412（3）001-2 2-5-1x210100-11-2-1x31-2010001Cj-Zj2100
3、0-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第9页/共16页结论 cj-zj均为非正数 得到最优解和最优值。x1=4，x2=1，x3=9，x4=x5=x6=x7=0，minF=-maxF=-2 第10页/共16页例2：用大M法求解第11页/共16页大M法引入人工变量x5，x6，x7，将原问题化为 第12页/共16页段段Cj0-2-111-M-M-MQi注注基基bP1P2P3P4P5P6P71-Mx52（1）-12-11002-Mx6621-3
4、10103-Mx7711110017Cj-Zj15M4M-2M-11M+10002-2x121-12-100-Mx6203-7（3）102/3-Mx7502-12015/2Cj-Zj7M+405M-3-8M+55M-1003-2x18/310-1/3001x42/301-7/310-Mx711/300(11/3)01Cj-Zj11/3M+14/30-211/3M+7/3004-2x1310001x43010(1)1x310010Cj-Zj20-200第13页/共16页特殊情况特殊情况1、无可行解无可行解：线性规划最优解中存在人工变量大于零，则此线性规划无可行解；2、无界解无界解：在求目标函数最
5、大值的问题中，在某次迭代的单纯形表中，如果存在着一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于零，则此线性规划问题无界。3、无穷多最优解无穷多最优解：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解；4、退化退化：在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。退化易产生循环迭代，为避免循环，遵守以下两条原则：在所有检验数小于零的非基变量中，选一个下标最小的作为调入变量；在存在两个以上最小比值时，选一个下标最小的作为调出变量。第14页/共16页练习题第15页/共16页感谢您的观看！第16页/共16页