【什么是单纯形法】单纯形法（Simplex Method）是一种用于求解线性规划问题的算法，由美国数学家乔治·丹齐格（George Dantzig）于1947年提出。它通过迭代的方式逐步接近最优解，是解决线性规划问题最经典、最广泛应用的方法之一。
一、单纯形法简介
单纯形法主要用于求解如下形式的线性规划问题：
- 目标函数：最大化或最小化 $ Z = c_1x_1 + c_2x_2 + \dots + c_nx_n $
- 约束条件：$ a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1 $
$ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \leq b_2 $
...
- 变量非负：$ x_1, x_2, \dots, x_n \geq 0 $
该方法通过将问题转化为标准形式，并在可行域的顶点之间移动，寻找使目标函数达到最优值的点。
二、单纯形法的核心思想
| 核心思想 | 说明 |
| 可行解 | 初始解必须满足所有约束条件 |
| 迭代优化 | 从一个初始可行解出发，逐步改进目标函数值 |
| 基本解 | 每次迭代中选择一组变量作为“基变量”，其余为“非基变量” |
| 最优判定 | 当所有非基变量的系数均为非正（或非负），则达到最优解 |
三、单纯形法的基本步骤
| 步骤 | 内容 |
| 1 | 将线性规划问题转换为标准形式，引入松弛变量或人工变量 |
| 2 | 构造初始单纯形表（Simplex Tableau） |
| 3 | 确定进入基的变量（选择具有最大正系数的非基变量） |
| 4 | 确定离开基的变量（使用最小比值规则） |
| 5 | 用行变换更新单纯形表 |
| 6 | 重复步骤3至5，直到无法进一步改进目标函数为止 |
四、单纯形法的优缺点
| 优点 | 缺点 |
| 适用于大多数线性规划问题 | 对于大规模问题可能效率较低 |
| 结构清晰，易于理解 | 需要良好的初始可行解 |
| 能够判断无解或无界情况 | 在某些情况下可能陷入循环 |
五、总结
单纯形法是一种基于几何和代数原理的优化算法，广泛应用于资源分配、生产计划、运输调度等领域。虽然随着计算技术的发展，出现了更高效的算法如内点法，但单纯形法因其直观性和稳定性，仍然是学习和应用线性规划的重要工具。
| 项目 | 内容 |
| 方法名称 | 单纯形法 |
| 提出者 | 乔治·丹齐格（George Dantzig） |
| 应用领域 | 线性规划、资源优化、经济模型等 |
| 主要特点 | 迭代搜索、基本解、最优判定 |
| 适用问题 | 有线性目标函数和线性约束的问题 |