用单纯形法求线性规划问题 流程图

用单纯形法求解线性规划问题通常涉及以下几个步骤，这里我会简单地描述一下，并提供一个流程图的概述：

1. **问题理解**：首先，你需要有一个目标函数（通常表示为线性的最小化或最大化），以及一组约束条件（线性不等式或等式）。

2. **建立标准形式**：将原问题转换为标准的线性规划形式，即maximize c^T * x (目标函数) subject to A * x ≤ b (约束条件)，其中c是目标函数系数向量，x是决策变量，A和b分别是矩阵和列向量。

3. **初始化**：如果问题有基础可行解，选择一个初始的基本解（非负且满足约束）。如果没有，则可能存在基本可行域为空的情况。

4. **检验最优解**：
- 检查是否已经达到目标函数的最大值（最大化问题）或最小值（最小化问题），如果是则结束算法。
- 若目标函数未达上限，寻找下一个可行的增广行（进入非基础变量行列）。

5. **迭代过程**：
a. **选换变量**：从当前可行解中找出松弛变量，即那些大于等于零但是乘以A之后小于b的变量。
b. **选取进基变量**：在所有松弛变量中找到一个使得目标函数增益最大的作为“进基”变量。
c. **行简化**：通过一系列代数操作（如交换、增倍行），消除进基变量对应的行，使其变为单位矩阵。

6. **循环终止条件**：检查是否有新的基变量成为非负的（此时可能已找到最优解），或者判断是否进入极小点（所有变量为零且仍满足约束）。

7. **结果报告**：如果到达了基可行解并且是最优解，输出变量值及相应的最优目标函数值；若无法继续优化，可能需要调整模型或引入假设。

以下是简化的流程图示意：

开始 -> 标准化问题 -> 初始化(可能) -> 检查最优 -> 进行迭代:
   |              |
   V              V
找松弛变量 -> 选进基变量 -> 行简化 -> 判断终止条件
   ^              ^
   |              |
   V              V
更新基本解 -> 结果报告 -> 结束