单纯形法求解线性规划问题的步骤
单纯形法是求解线性规划问题的一种经典算法，它通过迭代的方式逐步找到最优解。以下是使用单纯形法（单纯性表）求解线性规划问题的详细步骤：
一、问题描述
假设我们有如下的标准型线性规划问题：
最大化 $z = c^T x$
约束条件为：
$Ax \leq b$
$x \geq 0$
其中，$A$ 是系数矩阵，$b$ 是常数向量，$c$ 是目标函数的系数向量，$x$ 是决策变量向量。
二、初始化
构造初始单纯形表：
- 将原问题的约束条件和目标函数转化为单纯形表的形式。这通常包括添加松弛变量以将不等式约束转换为等式约束，并设置初始基变量和非基变量。
- 单纯形表一般包含以下列：基变量、非基变量、系数（对应于目标函数和约束条件的系数）、常数项、比值（用于确定下一步的换入变量）等。
选择初始可行基：
- 通常可以选择单位矩阵作为初始基变量的系数矩阵部分，即每个基变量对应一个约束条件的松弛变量，从而形成一个初始的可行解（通常是零解）。
三、迭代过程
计算检验数：
- 检验数是衡量当前基变量对于目标函数改进程度的一个指标。它等于目标函数中非基变量的系数减去该非基变量在约束条件中的系数的加权和（权重为对应的基变量的倒数）。
- 如果所有检验数都小于或等于零，则当前解是最优解，算法终止。
确定换入变量：
- 在所有检验数中，选择一个最大的正检验数所对应的非基变量作为换入变量。这个变量有潜力通过进入基变量集合来提高目标函数的值。
计算比值以确定换出变量：
- 对于每个基变量，计算其允许减少的量与换入变量增加量的比值（即最小比值规则）。这个比值是通过将常数项减去基变量在当前约束条件中的系数与该基变量系数的乘积后除以换入变量在该约束条件中的系数来计算的。
- 选择使比值最小的基变量作为换出变量。这意味着在保持可行性的同时，可以尽可能多地增加换入变量的值。
更新单纯形表：
- 用换入变量替换掉换出变量在基变量集合中的位置，并相应地更新单纯形表中的系数和常数项。
- 这通常涉及到对基变量的重新选择和系数的行变换操作。
重复迭代：
- 返回步骤1，继续计算新的检验数，并根据需要确定新的换入和换出变量。
- 直到满足停止准则（所有检验数都小于或等于零）为止。
四、输出结果
- 当算法终止时，单纯形表中包含的基变量及其对应的值就是原线性规划问题的最优解。
- 最优目标函数值可以通过将最优解代入目标函数来计算得到。
五、注意事项
- 在实际应用中，单纯形法可能会遇到退化情况（如多个变量具有相同的最大检验数或相同的比值），这时需要采取额外的策略来处理。
- 单纯形法的收敛性取决于问题的可行性和有界性。如果问题是无界的或不可行的，单纯形法可能不会收敛到最优解。因此，在使用单纯形法之前，通常需要验证问题的可行性和有界性。
