线性规划是一种优化方法，用于在满足一组线性约束条件下最大化或最小化一个线性目标函数。单纯形法是解决线性规划问题的一种经典算法，由丹·佐治·库珀利特在1947年提出。这种方法适用于解决标准形式的线性规划问题，即目标函数是求最小化或最大化，约束条件是线性的不等式或等式。
单纯形法的核心在于通过迭代过程寻找最优解。以下是对单纯形法的主要步骤和概念的详细解释：
1. **标准型转换**：将原始的线性规划模型转换为标准形式，这意味着所有的约束都是不等式 "≤" 或 "≥"，目标函数是最大化或最小化，所有变量非负。
2. **初始基本可行解**：对于 "≤" 类型的约束，引入松弛变量；对于 "≥" 或 "=" 类型的约束，引入非负人工变量，以构建初始可行基。
3. **单纯形表**：创建一个表格，包含目标函数的系数、约束方程的系数、基变量的系数以及检验数。基变量的系数列必须是单位矩阵，检验数表示目标函数每增加一个单位，对应的非基变量能增加多少。
4. **最优解判别**：检查每个基变量的检验数是否非负，若所有检验数均为非正，且目标函数系数列皆为非负，那么当前解是最优解。
5. **换基迭代**：若存在正检验数，选择最大正检验数对应的变量作为入基变量，然后根据最小比值原则选择出基变量。通过行变换（矩阵的初等行变换）将主元列变为单位向量，更新解并返回步骤4。
6. **最优解的性质**：
- **最优解判别定理**：如果所有检验数为非正，则当前基可行解是最优解。
- **唯一最优解判别定理**：如果所有非基变量的系数列没有负元素，则存在唯一最优解。
- **无穷多最优解判定定理**：若有非基变量的系数列有正数，且该变量对应的检验数为0，则有无穷多最优解。
- **无界解判定定理**：如果某个非基变量的系数为正，且对应的检验数也为正，则问题有无界解。
7. **结束条件**：当找到满足最优解条件的解时，迭代停止。
单纯形法虽然在理论上可能需要大量的迭代，但在实际应用中，通常可以在相对较少的步骤内找到最优解。然而，对于某些问题，特别是当问题规模较大时，单纯形法可能效率较低。因此，现代的优化软件往往结合了其他算法，如内点法，来提高计算效率。此外，人工变量法和两阶段法是处理有等式约束的线性规划问题的方法，通过引入人工变量，首先寻找一个可行解，然后再去掉人工变量，转为标准型的单纯形法求解。
单纯形法是线性规划的基础，它通过迭代过程和矩阵操作逐步逼近最优解，是理解和实现线性规划问题的关键工具。在会计学、运筹学、经济学等众多领域都有广泛应用。
VIP享7折，此内容立减5.97元 
