线性规划详解：从标准形到单纯形法

"第二章 线性规划深入解析" 线性规划是运筹学中的一个基础概念，它涉及寻找一组线性关系中的最优解。在这个主题中，我们主要关注以下几个核心知识点： 1. **线性规划的标准形**：线性规划问题通常包括一个线性的目标函数和一系列线性等式或不等式的约束条件。为了方便解决，问题会被转化为标准形，即目标函数是极小化，所有的约束都是等式，且所有变量非负。这样的形式有助于应用特定的算法来寻找最优解。 2. **基可行解**：在标准形中，如果一个解满足所有约束条件，并且基变量（与当前基相关联的变量）都是非负的，那么这个解被称为基可行解。这里的“基”是指矩阵A的一个子集，其列向量线性无关，形成一个基础。 3. **单纯形法**：由George Dantzig在1947年提出的单纯形法是求解线性规划问题的经典算法。它通过在不同的基可行解之间迭代，逐步逼近最优解。这种方法虽然在理论上不是多项式时间复杂度，但在实际应用中表现出高效性。 4. **单纯形表**：单纯形法通常使用一种称为单纯形表的工具来记录和更新解的状态。这个表格包含了当前基变量、非基变量、系数、 slack变量和rediduals，以及它们在目标函数中的系数，用于指导算法的下一步操作。 5. **初始基可行解的确定与大M单纯形法**：在开始单纯形法之前，需要找到一个初始的基可行解。这可以通过添加大M（一个足够大的常数）到不等式约束中来实现，将不等式约束暂时转化为等式，然后构造标准形。大M法允许我们在开始阶段引入人工变量，以便快速得到一个可行解。 线性规划的应用广泛，例如在运输问题、生产计划、资源分配等领域都有其身影。线性规划的基本定理确保了问题总有可行解，并且最优解一定可以通过基本可行解找到。此外，几何上，线性规划的解可以理解为多面体的顶点（极点），而最优解就是使目标函数达到最大或最小值的那个顶点。 线性规划的现代发展包括内点法，如1979年的椭球内点法和1984年的投影内点法，这些方法在处理大规模和退化问题时效率更高。原-对偶内点法是目前解决这类问题的首选方法。 线性规划是优化问题的基础，其理论和算法对于理解和解决实际问题具有重大意义。通过掌握线性规划，我们可以构建模型来优化各种业务决策，提高效率和效益。