运筹学入门：大M法与两阶段法详解

运筹学第一章1.4主要讨论了大M法和两阶段法在单纯形法中的应用。单纯形法是一种解决线性规划问题的有效算法，尤其适用于求解标准型线性规划问题。以下是这部分内容的关键知识点： 1. 初始可行解的确定：首先，确定初始可行解是解决问题的第一步。对于限制条件全是"≤"类型的约束，可以通过引入松弛变量作为初始基变量，使得对应的系数列向量构成单位阵，这种方法被称为“人造基”。如果遇到既有"≤"又有"≥"或"="类型的约束，需要构造“不完全的人造基”来处理。 2. 引入人工变量：对于等式约束，会在左端引入非负人工变量，以确保系数矩阵中出现单位阵，这些人工变量对应的决策变量作为“基变量”。这样做使得目标函数值可以直接通过基变量的取值来计算，b列（检验数行）与基变量的关系至关重要，它是解答列。 3. 非基变量和基变量的表达式：非基变量通常被设为0，通过非基变量的表达式计算出基变量的取值，然后组合成初始基本可行解。这个步骤保证了解的正确性和有效性。 4. 建立判别准则：在单纯形法中，关键在于判断何时进行换基操作，这通常基于两个基本表达式的比较。这两个表达式是线性规划问题的标准形式，通过它们可以判断当前解是否是最优解，或者是否需要调整基变量。 5. 大M法与两阶段法：当问题的约束复杂，无法直接构建单位阵时，可以采用大M法或两阶段法来求解。大M法是一种技术手段，通过设定大的常数M来代替未知的上限，而两阶段法则分为求解初步解和优化阶段，分别处理约束的不同性质。 总结来说，运筹学中的大M法和两阶段法是处理线性规划中复杂约束的有效工具，它们在确定初始可行解、引入人工变量、以及进行换基判断等方面发挥着重要作用，是理解和解决实际问题中的核心概念。