使用单纯形法与大M法解决线性规划问题

"本文档主要介绍了如何使用单纯形法解决线性规划问题，特别提到了大M法的应用，并给出了输入数据的格式示例。此外，还展示了一个简单的矩阵类的实现，用于存储和操作数据。" 线性规划是一种优化方法，用于在满足一组线性约束条件下最大化或最小化一个线性目标函数。单纯形法是解决线性规划问题的一种有效算法，由美国数学家乔治·丹齐格在1947年提出。它通过迭代过程，逐步将非基变量替换为基变量，直到找到最优解。在这个过程中，大M法常被用来处理人工变量，确保这些变量在最优解中为0，从而帮助解决不等式约束。 单纯形法的基本步骤包括： 1. **初始基本可行解**：首先，将线性规划问题转化为标准形式，包含等式约束和非负变量限制。然后选择一个初始的基本可行解，这通常可以通过将所有非基变量设置为0来实现。 2. **构建单纯形表**：将决策变量、目标函数系数、约束右端常数以及对应的系数矩阵放入单纯形表中。 3. **迭代过程**：寻找一个改进方向，即可以提高目标函数值的非基变量。这涉及到计算检验数（即目标函数系数与对应的 slack 变量系数之比），选择一个负的检验数最小的非基变量。 4. **行换位**：将选择的非基变量替换一个基变量，保持系统的基础解是可行的。这一步可能涉及到列的替换和矩阵的行换位。 5. **检查最优性**：更新单纯形表后，检查所有非基变量的检验数是否非负。如果所有检验数都非负，则当前解是最优解；否则，返回步骤3。 大M法在处理线性规划中的不等式约束时引入了人工变量。这些人工变量在实际问题中没有物理意义，但它们有助于构造一个初始的基本可行解。在模型中，人工变量的系数设置为大M，当对应约束被满足时，人工变量的值会被限制在0以下，因此在最优解中它们的值应为0。 在提供的代码中，定义了一个名为`Matrix`的类，用于处理二维数组。这个类包含了初始化、赋值、获取元素值等基本操作。例如，`Matrix`类的构造函数接受行数和列数作为参数，分配内存并初始化数据。`assign`函数用于设置矩阵中特定位置的元素，而`at`函数用于获取元素的值。类的`operator=`重载了赋值运算符，用于将一个矩阵的值复制到另一个矩阵中。此外，还提供了析构函数来释放内存，防止内存泄漏。 在实际应用中，线性规划和单纯形法广泛应用于生产计划、运输问题、资源分配等各种优化问题中。使用编程语言实现这些算法可以帮助自动化求解过程，提高效率。