线性规划问题——单纯形算法
线性规划问题——单纯形算法
单纯形算法是解决线性规划问题的一种重要方法，广泛应用于运筹学、经济学和工程学等领域。本文将通过一个具体的例子，详细介绍单纯形算法的三个主要步骤：化“约束标准型”、列初始单纯形表和基变换直到找到最优解。
第一步：化“约束标准型”
在每个等式约束中至少有一个变量的系数为正，且这个变量只在该约束中出现。在每个约束方程中选择一个这样的变量称为基本变量。剩下变量称为非基本变量。
一个简单的栗子
考虑以下线性规划问题：
等式1：x₁+3x₂-x₃+2x₅=7
等式2：x₄-2x₂+4x₃=12
等式3：x₆-4x₂+3x₃+8x₅=10
分析每个等式的变量系数：
- 等式1：x₁，x₂，x₅ 的系数为正，但是等式2和3中有 x₂，等式3中有 x₅；所以等式1的基本变量是 x₁。
- 等式2：x₄，x₃ 的系数为正，但是等式1和3中都有 x₃；所以等式1的基本变量是 x₄。
- 等式3：x₆，x₃，x₅ 的系数为正，但是等式1和2中都有 x₃，等式1中有 x₅；所以等式1的基本变量是 x₆。
因此，x₁，x₄，x₆ 是基本变量；剩下的x₂，x₃，x₅ 是非基本变量。
如果我们让非基本变量 x₂，x₃，x₅ 都等于 0 呢？式子就变成了下面介个样子：
maxz=0
x₁=7
x₄=12
x₆=10
其中x₁=7，x₄=12，x₆=10，x₂=0，x₃=0，x₅=0。所以，将所有非基本变量置为 0，从约束方程式中解出满足约束的基本条件的值，即可求出一个基本可行解。当然，这个基本可行解未必是最优解。而且，很明显，解等于该式子的常数部分。
第二步：列初始单纯形表
很明显，红色部分基本变量，蓝色部分非基本变量。其中的 0，7，12，10 是常数项；剩下的是系数项。（很简单的填表不赘述了）
接下来是选择入基变量和离基变量
入基变量从非基本变量里选
红框里选正的，红框里选正的，红框里选正的。所以选 x₃为入基变量；如果没有系数为正的，那么当前基本可行解为最优解。
离基变量从基本变量里选
在前面我们选择了唯一的正值元素3，它所在的列中有两个正元素，4和3。我们算min{12/4，10/3}=3，所以选 x₄ 为离基变量。如果3所在的列没有正元素，那么最优解无界，计算结束。
第三步：基变换直到找到最优解
然后做转轴变换，目的是将入基变量与离基变量互调位置。
x₄-2x₂+4x₃=12
x₃ , x₄ 变换。
x₃-x₂/2+x₄/4=3
代入x₁+3x₂-x₃+2x₅=7 和 x₆-4x₂+3x₃+8x₅=10 消去x₃。
x₁+5x₂/2+x₄/4+2x₅=10
x₆-5x₂/2-3x₄/4+8x₅=1
代入目标函数。
maxz=9+x₂/2-3x₄/4-2x₅
形成的新单纯形表如下：
形成新的单纯形表，重复前面过程，直到所有非基本变量系数都变为负值为止。