单纯形算法详细解析

您所在的位置：网站首页 › 简述对偶单纯形法的计算过程及它的优点 › 单纯形算法详细解析

单纯形算法详细解析

2023-07-29 19:36| 来源: 网络整理| 查看: 265

0. 简介

1. 单纯形算法解析

1.1 基本概念及原理解析

1.1.1 线性规划标准形式

1.1.2 线性规划典范形式

1.1.3 凸组合和凸锥组合

1.1.4 极点和极方向

1.1.5 线性规划可行域的表示

1.1.6 线性规划基本定理

1.1.7 基本解与基本可行解

1.1.8 关于“退化”

1.2 “判优”规则

1.3 “改进”规则

1.4 “初始点”确定方法

1.4.1 两阶段法

1.4.2 大M法

1.5 单纯形算法中的几个问题

1.6 单纯形算法计算步骤图

2 单纯形算法计算案例

3 参考资料

0. 简介

单纯形算法（simplex method）是求解线性规划模型的一种通用方法。

线性规划模型具有三个要素：

决策变量目标函数约束条件

线性规划模型具有这样的特点：

决策变量相互独立且连续变化目标函数是线性函数约束条件是线性不等式组

例：一个企业“生产计划”的线性规划模型如下

$\begin{align*} max \quad & z = 50x_1+80x_2\\ s.t. \quad & 0.5x_1 + 2x_2 \leq 40 \\ &x_1+1.5x_2 \leq 45\\ &x_1,x_2 \geq0 \end{align}$

$max$ 是指目标函数极大化，maximum的缩写，如果目标函数极小化则用 $min$ , minimize的缩写。 $s.t.$ 是subject to的缩写，表示受限制于，其后跟约束条件。上述模型中约束条件前两条表示资源约束，最后一条表示决策变量的非负约束。

一般来说，对于生产计划这类问题，可用如下线性规划模型近似表示

$\begin{align*} max \quad &\sum_{j=1}^{n}c_j x_j&\\ s.t. \quad &\sum_{j=1}^n a_{ij}x_j\leq b_i, i=1,2,\cdots ,m,&\\ &x_j \geq 0, j=1,2,\cdots ,n. \end{align}$

当然线性规划模型可以远比以上模型复杂，需要根据具体问题特征进行建模。下面介绍求解线性规划模型的单纯形算法。

1. 单纯形算法解析

单纯形算法遵循“初始点——判优——改进”的优化模式。我们首先讨论“判优”，然后讨论“改进”，最后讨论“初始点”。

1.1 基本概念及原理解析

为了方便后续的讨论，需要先了解一些线性规划的表示形式、可行域、以及线性规划可行解的刻画等内容

1.1.1 线性规划标准形式

定义1：线性规划的标准形式（standard form）是指满足如下四个条件的线性规划模型：

（1）所有决策变量的取值是非负的；

（2）除决策变量非负约束外的其他约束是等式约束；

（3）模型中目标函数需要极大化（也可以要求极小化）；

（4）等式约束中常数项位于等号的右端（称为右端项，right hand side）

例：一个线性规划模型的标准形式

线性规划模型标准形式的一般表达为

线性规划模型标准形式的矩阵表达为

$\begin{align*} max \quad & z=\boldsymbol{c}^{\rm T}\boldsymbol{x}\\ s.t. \quad & \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\\ & \boldsymbol{x}\geq0 \end{}$

1.1.2 线性规划典范形式

定义2：线性规划的典范形式（canonical form）是指满足如下四个条件的线性规划模型：

（1）所有决策变量的取值是非负的；

（2）除决策变量非负约束外的其他约束是等式约束，并且右端项是非负的；

（3）模型中目标函数需要极大化（也可以要求极小化）；

（4）在等式约束中存在一组与等式约束个数相等的决策变量，它们的系数构成系数矩阵的一个单位子矩阵。

例：一个线性规划模型的典范形式

线性规划模型典范形式的一般表达为

1.1.3 凸组合和凸锥组合

定义3：给定 $m$ 个向量 $\boldsymbol{x^1,x^2,\cdots,x^m} \in \mathbb{R}^n$ 以及满足 $\sum_{i=1}^m \alpha_i =1$ 的非负实数 $\alpha_i \geq0, i=1,2,\cdots,m,$ 我们将向量 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 称为 $\boldsymbol{x^1,x^2,\cdots,x^m}$ 的凸组合（convex combination），如果仅仅要求组合系数 $\alpha_i \geq0, i=1,2,\cdots,m,$ 那么向量 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 称为 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 的凸锥组合（convex conical combination）,也称为非负线性组合。

这里回顾一下线性规划的标准形式的矩阵表达式（这里我们要求目标函数极小化）

$\begin{align*} min \quad & z=\boldsymbol{c^{\rm{T}}x}\\ s.t. \quad & \boldsymbol{\rm{A}}\boldsymbol{x}=\boldsymbol{b}\\ & \boldsymbol{x}\geq \boldsymbol{0} \end{align}$

其中系数矩阵 $\boldsymbol{\rm{A}}\in\mathbb{R}^{m \times n}$ ，右端项 $\boldsymbol{b} \in \mathbb{R}^m$ ，目标函数的梯度向量 $\boldsymbol{c} \in \mathbb{R}^n$ ，决策变量 $\boldsymbol{x} \in \mathbb{R}^n$ 。线性规划的可行域实际上是由右端项 $\boldsymbol{b}$ 相对于系数矩阵 $\mathbf{A}$ 的列向量的凸锥组合系数 $\boldsymbol{x}$ 构成的。

定义4：设集合 $S \subseteq \mathbb{R}^n$ ，若 $\forall \boldsymbol{x}^1,\boldsymbol{x}^2 \in S$ 和 $\forall \alpha \in [0,1]$ ，有 $\alpha \boldsymbol{x}^1+(1-\alpha) \boldsymbol{x}^2 \in S$ ，则称 $S$ 为一个凸集（convex set）。

集合 $T\subset \mathbb{R}^n$ 的凸包（convex hull）是指包含 $T$ 的凸集的交集，即包含 $T$ 的最小凸集，记为

${\rm conv} \ T \overset{def}{=} \cap_{C \supseteq T} C$

其中 $C$ 为凸集。

一个有限点集 $\{\boldsymbol{x}^0,\boldsymbol{x}^1,\cdots,\boldsymbol{x}^m\} \subset \mathbb{R}^n$ 的凸包通常称为多胞形（polytope）。特别地，当 $\boldsymbol{x}^1-\boldsymbol{x}^0,\boldsymbol{x}^2-\boldsymbol{x}^0,\cdots,\boldsymbol{x}^m-\boldsymbol{x}^0$ 线性无关时，该有限点集对应的凸包称为 $m$ 维单纯形（ $m$ -dimensional simplex）,向量 $\boldsymbol{x}^{i}(i=0,1,\cdots,m)$ 称为该该单纯形的顶点（vertex）。一般地，我们把有限个闭半空间的交 $\{\boldsymbol{x} \in \mathbb{R}^n| \boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}\}$ （其中 $\boldsymbol{A}$ 的行向量非零）称为一个多面体（polyhedron）。可以证明，非空的有界多面体是一个多胞形，也就是说，它能够表示成其顶点的凸组合。

定义5：给定非空集合 $C \subseteq \mathbb{R}^n$ ，若 $\forall \boldsymbol{x} \in C$ 和实数 $\lambda 0$ ，有 $\lambda \boldsymbol{x} \in C$ ，则称 $C$ 为一个锥（cone）。此外，若 $C$ 也是一个凸集，则称 $C$ 为一个凸锥（convex cone）。

我们约定：非空集合 $S \subset \mathbb{R}^n$ 生成的凸锥，是指可以表示成 $S$ 中有限个元素凸锥组合的所有点构成的集合，记为 ${\rm cone}\ S$ 。特别地，若非空集合 $S$ 是凸的，则 $\mathcal{K}(S)=\{\lambda \boldsymbol{x} | \lambda 0, \boldsymbol{x} \in S\}$ 是包含 $S$ 的最小凸锥，并且

${\rm cone}\ S=\mathcal{K}(S) \cup \{\boldsymbol{0}\}$

1.1.4 极点和极方向

定义6：设 $S\subset \mathbb{R}^n$ 为非空的凸集，若 $\boldsymbol{x} \in S$ 不能表示成 $S$ 中两个不同点的凸组合，即不存在两个不同的点 $\boldsymbol{x}^1,\boldsymbol{x}^2 \in S$ 和实数 $\alpha \in (0,1)$ ，使得 $\boldsymbol{x} = \alpha \boldsymbol{x}^1+(1-\alpha)\boldsymbol{x}^2$ ，则 $\boldsymbol{x}$ 称为 $S$ 的一个极点（extreme point）。

定义7：设 $S \subset \mathbb{R}^n$ 为非空的凸集，若向量 $\boldsymbol{d} \in \mathbb{R}^n$ 满足：对于 $\forall \boldsymbol{x} \in S$ ，射线

$R(\boldsymbol{x},\boldsymbol{d}) \overset{def}{=} \{\boldsymbol{x}+\lambda \boldsymbol{d} | \lambda \geq0\} \subseteq S$

则称向量 $\boldsymbol{d}$ 是 $S$ 的一个回收方向（direction of recession of $S$ ），简称方向。非空凸集 $S$ 的所有（回收）方向构成的尖锥（包括零向量），称为 $S$ 的回收锥（recession cone of $S$ ）,记为 $0^+S$ 。

设 $\boldsymbol{d}^1,\boldsymbol{d}^2$ 为非空凸集 $S$ 的两个（回收）方向，若对于任意 $\lambda0$ ，都有 $\boldsymbol{d}^1\neq \lambda\boldsymbol{d}^2$ ，则称 $\boldsymbol{d}^1,\boldsymbol{d}^2$

是 $S$ 的两个不同的方向。当非空凸集 $S$ 的（回收）方向 $\boldsymbol{d}$ 不能表示成它的两个不同方向的凸锥组合时，该方向 $\boldsymbol{d}$ 称为 $S$ 的一个极方向（extreme direction）。

1.1.5 线性规划可行域的表示

线性规划的可行域是一个多面体。下面给出一个关于多面体内在表示形式的定理。多面体表示定理是多面体的一个重要性质，在最优化领域具有十分重要作用。该定理表面，多面体可以用其极点（顶点）的凸组合和极方向的凸锥组合来表示。

定理1（多面体表示定理，也称为Minkowski's Theorem）：若多面体 $P=\{\boldsymbol{x} \in \mathbb{R}^n | \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \neq \varnothing$ ，并且 $rank(\boldsymbol{A})=n$ ，则

（1） $P$ 的极点集是非空的有限集合，记为 $\{\boldsymbol{x}^k\}_{k \in \mathcal{K}}$ ;

（2）记 $P$ 的极方向集为 $\{\boldsymbol{d}^j\}_{j\in \mathcal{J}}$ （我们约定，当 $P$ 不存在极方向时，指标集 $\mathcal{J}=\varnothing$ ）,那么

$\begin{align*} P&={\rm conv}\{\boldsymbol{x}^k|k\in \mathcal{K}\}+{\rm cone}\{\boldsymbol{d}^j|j\in \mathcal{J}\}\\ &=\{\boldsymbol{x}\in \mathbb{R}^n|\boldsymbol{x}=\sum_{k\in \mathcal{K}}\lambda_k\boldsymbol{x}^k+ \sum_{j\in \mathcal{J}} \mu _j\boldsymbol{d}^j,\sum_{k\in \mathcal{K}}\lambda_k=1,\lambda_k\geq0,k\in \mathcal{K},\mu _j\geq0,j\in \mathcal{J}\} \end{}$

（3）指标集 $\mathcal{J}=\varnothing \Leftrightarrow P$ 是有界集合（即 $P$ 是一个多胞形）

利用这个定理，可以得到如下推论

推论1.1 若多面体 $S=\{\boldsymbol{x} | \boldsymbol{A} \boldsymbol{x} = \boldsymbol{b},\boldsymbol{x}\geq \boldsymbol{0}\}$ 是非空的，则 $S$ 必存在极点。

1.1.6 线性规划基本定理

现在我们考虑线性规划的标准形式，假设可行域 $S=\{\boldsymbol{x} \in \mathbb{R}^n | \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b},\boldsymbol{x}\geq0\}$ 的极点为 $\boldsymbol{x}^i(i \in \mathcal{K})$ ，极方向为 $\boldsymbol{d}^j(j \in \mathcal{J})$ ，那么任意的点 $\boldsymbol{x} \in S$ 都可以表示成

$\boldsymbol{x} = \sum_{i \in \mathcal{K}} \lambda_i\boldsymbol{x}^i + \sum_{j \in \mathcal{J}} \mu_j \boldsymbol{d}^j$

其中

$\sum_{i \in \mathcal{K}} \lambda_i =1, \lambda_i \geq 0, \mu_j \geq 0 (i \in \mathcal{K}, j \in \mathcal{J})$

于是，线性规划的标准形式可以等价地转化成只有一个等式约束和若干个非负变量约束的线性规划问题：

$\begin{align*} {\rm min} \quad &\sum_{i \in \mathcal{K}}(\boldsymbol{c}^{\rm T} \boldsymbol{x}^i) \lambda_i + \sum_{j \in \mathcal{J}}(\boldsymbol{c}^{\rm T} \boldsymbol{d}^j) \mu_j , \\ {\rm s.t.} \quad & \sum_{i \in \mathcal{K}} \lambda_i = 1, \\ & \lambda_i \geq 0, \mu_j \geq 0, i \in \mathcal{K} , j \in \mathcal{J}. \end{align}$

容易看出，可以分两种情况讨论转化之后的线性规划的极小化问题：

情形1：若存在 $j \in \mathcal{J}$ ，使得 $\boldsymbol{c}^{\rm T}\boldsymbol{d}^j 0$ ，则线性规划是无（下）界的，原来的线性规划问题不存在有限最优值。

情形2：若 $\forall j \in \mathcal{J}$ ，有 $\boldsymbol{c}^{\rm T}\boldsymbol{d}^j \geq 0$ ，则取 $\mu_j = 0(j \in \mathcal{J})$ 不会影响到线性规划的最优值。这就是说，在最优值不变的意义下，极小化问题可转化为

$\begin{align*} {\rm min} \quad &\sum_{i \in \mathcal{K}}(\boldsymbol{c}^{\rm T} \boldsymbol{x}^i) \lambda_i, \\ {\rm s.t.} \quad & \sum_{i \in \mathcal{K}} \lambda_i =1,\\ & \lambda_i \geq 0, i \in \mathcal{K}. \end{align}$

以上问题的可行域是一个多胞形（有界多面体），该问题必然有最优解。最优值可以在某个 $\lambda_p=1$ 处取到，其中

$\boldsymbol{c}^{\rm T}\boldsymbol{x}^{p} = {\rm min}\{\boldsymbol{c}^{\rm T}\boldsymbol{x}^{i} | i \in \mathcal{K}\}$

上述转化实际上揭示了线性规划最优值存在的条件及最优解的特点，这就是线性规划基本定理的重要内容。在此，我们可以将线性规划的基本定理表述如下：

定理2（线性规划基本定理）假设线性规划标准形式的可行域 $S=\{\boldsymbol{x} \in \mathbb{R}^n | \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b},\boldsymbol{x}\geq0\}$ $\neq \varnothing$ ，则有如下结论：

（1）该线性规划问题存在有限最优值，当且仅当对于可行域 $S$ 的任意极方向 $\boldsymbol{d}^j(j \in \mathcal{J})$ 有 $\boldsymbol{c}^{\rm T}\boldsymbol{d}^j \geq 0$ 。

（2）当线性规划问题存在有限最优值时，其最优值可以在可行域 $S$ 的某个极点上取到。

1.1.7 基本解与基本可行解

定义8：给定一个线性方程组 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ ，其中 $\boldsymbol{A} \in \mathbb{R}^{m \times n},\boldsymbol{b} \in \mathbb{R}^m,{\rm rank}(\boldsymbol{A})=m$ ，若该方程组的一个解 $\boldsymbol{x}$ 满足：存在矩阵 $\boldsymbol{A}$ 的一个可逆子矩阵 $\boldsymbol{B} \in \mathbb{R}^{m \times m}$ ，使得 $\boldsymbol{A} = [\boldsymbol{B},\boldsymbol{N}]$ ，并且 $\boldsymbol{x} = (\boldsymbol{x}_{\boldsymbol{B}},\boldsymbol{x}_{\boldsymbol{N}})^{\rm T}$ ，这里 $\boldsymbol{x}_{\boldsymbol{N}}=0, \boldsymbol{x}_{\boldsymbol{B}}=\boldsymbol{B}^{-1}\boldsymbol{b}$ ，则称 $\boldsymbol{x}$ 为可行域 $S=\{\boldsymbol{x}\in \mathbb{R}^n | \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b},\boldsymbol{x} \geq 0 \}$ 的一个基本解（basic solution）。此时子矩阵 $\boldsymbol{B}$ 称为基矩阵（basis）, $\boldsymbol{x}_{\boldsymbol{B}}$ 中对应的分量称为基变量（basic variables）, $\boldsymbol{x}_{\boldsymbol{N}}$ 中对应的分量为非基变量（non-basic variables）。

若 $\boldsymbol{x}=(\boldsymbol{x}_{\boldsymbol{B}},\boldsymbol{x}_{\boldsymbol{N}})^{\rm T}$ 是可行域 $S$ 的一个基本解，并且满足 $\boldsymbol{x}_{\boldsymbol{B}}=\boldsymbol{B}^{-1}\boldsymbol{b} \geq 0$ ，则 $\boldsymbol{x}$ 称为 $S$ 的一个基本可行解（basic feasible solution）。此时子矩阵 $\boldsymbol{B}$ 称为一个可行基矩阵（feasible basis）, $\boldsymbol{x}_{\boldsymbol{B}}$ 称为一组可行基变量（feasible basic variables）, $\boldsymbol{x}_{\boldsymbol{N}}$ 称为一组非基变量（non-basic variables）。

可行域 $S$ 的基本可行解与它的极点（顶点）之间有密切的关系，我们把这种关系描述称下面的定理。

定理3：给定一个非空集合 $S=\{\boldsymbol{x}\in \mathbb{R}^n | \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b},\boldsymbol{x} \geq 0 \}$ ，其中矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 的秩 ${\rm rank}(\boldsymbol{A})=m$ ，则下面三个集合是相等的：

（1） $S$ 的基本可行解集；

（2） $\{\boldsymbol{x} \in \mathbb{R}^n | \boldsymbol{x} \in S$ ，其中正分量对应的矩阵 $\boldsymbol{A}$ 中的列向量构成一个线性无关的向量组};

（3） $S$ 的极点集。

1.1.8 关于“退化”

定义9：若线性规划的可行域是非空的，则称该线性规划是相容的（consistent），否则称为非相容的（non-consistent）。

对于一个相容的线性规划，若某个基本可行解中取值非零的变量数目小于系数矩阵的秩，则称该解是退化的（degenrate）,否则称为非退化的（non-degenerate）。若线性规划存在一个退化的基本可行解，则称该线性规划是退化的，否则称为非退化的。

1.2 “判优”规则

单纯形算法（simplex method）是一种迭代算法，其基本思想是：从线性规划可行域（多面体）的某个顶点出发，利用目标函数中变量系数的符号判断该顶点的最优性，当该点不是最优点时，算法寻找一个相邻的顶点，使得目标函数值在新点处有所改进；然后，从相邻顶点出发，继续判优或者寻找另一个更好的顶点，直到到达最优的顶点（或者判定线性规划是无界的）。由于可行域的顶点（极点）集合与它的不等式表示的基本可行解集合是一样的，所以，从代数的角度来看，单纯形算法实质上是从可行域的一个基本可行解出发，求出使目标函数得到改进的相邻的基本可行解，以此类推，直到求得一个最优的基本可行解，或者找到最优解不可能存在的判据。

判优规则是与线性规划的典范形式有关的，这些典范形式等价于给定的线性规划问题。下面给出线性规划典范形式的矩阵表达式：

$\begin{align*} {\rm min} \quad & z=\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{b} + (\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N}) \boldsymbol{x}_{\boldsymbol{N}} \\ {\rm s.t.} \quad & \boldsymbol{x}_{\boldsymbol{B}}+\boldsymbol{B}^{-1}\boldsymbol{N}\boldsymbol{x}_{\boldsymbol{N}}=\boldsymbol{B}^{-1}\boldsymbol{b}\\ & \boldsymbol{x}_{\boldsymbol{B}} \geq 0, \boldsymbol{x}_{\boldsymbol{N}} \geq 0. \end{align}$

注：给出基 $\{x_1,x_2,\cdots,x_m\}$ 后，由其典式可得出以下结论：

（1）基可行解 $\boldsymbol{X}^0=(\alpha_1,\alpha_2,\cdots,\alpha_m,0,\cdots,0)^T=(\boldsymbol{B}^{-1}\boldsymbol{b},\boldsymbol{0})^{\rm T}$

（2）其对应的目标函数值 $z_0=\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{b}$

（3）检验数 $(\sigma_{m+1},\cdots,\sigma_n)$ （针对非基变量）用来判断 $\boldsymbol{X}^0$ 是否是最优解，其中

$\boldsymbol{\sigma}_{\boldsymbol{N}}=\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N} =(\sigma_{m+1},\cdots,\sigma_n)$

定理4（最优解判定准则）：

假设目标函数极小化（min）， $\boldsymbol{X}^0$ 是基可行解，则：

（1）如果 $\boldsymbol{\sigma}_{\boldsymbol{N}}=\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N} \geq0$ ，则 $\boldsymbol{X}^0$ 是线性规划问题的最优解。

（2）如果 $\boldsymbol{\sigma}_{\boldsymbol{N}}=\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N} 0$ ，则 $\boldsymbol{X}^0$ 是线性规划问题的唯一最优解。

（3）如果 $\boldsymbol{\sigma}_{\boldsymbol{N}}=\boldsymbol{c}_{\boldsymbol{N}}^{\rm T}-\boldsymbol{c}_{\boldsymbol{B}}^{\rm T}\boldsymbol{B}^{-1}\boldsymbol{N} \geq0$ ，并且存在某个 $\sigma_{m+l}=0$ ，则线性规划问题有无穷多最优解。

（4）如果存在一个 $\sigma_{m+k}0$ ，并且 $\boldsymbol{B}^{-1}\boldsymbol{N}_{k} \leq0$ （即非基变量 $x_{m+k}$ 对应的系数矩阵列向量，全部小于等于0），则线性规划问题无最优解（也称无界解）。

1.3 “改进”规则

以极小化目标函数为例，可能存在多个检验数小于零，那么选择哪一个检验数对应的非基变量作为入基变量，哪一个基变量作为出基变量呢？这涉及单纯形算法的“转轴规则”。为了改进目标函数数值，理论上可以尝试选择任意一个负检验数对应的非基变量进入可行基。选择入基变量的方法不同，会导致单纯形算法的不同类型。概括地说，一个转轴过程可以分成三个部分：

（1）确定进入可行基的非基变量（称为转入规则（pivoting in））;

（2）确定离开可行基的基变量（称为转出规则（pivoting out））;

（3）进行可行基转换的线性方程组Gauss消去操作（称为转轴操作）。

下面介绍最常用的单纯形算法的转轴规则（目标函数极小化）：

（1）转入规则：最大减少率规则（Largest reduction rule, LRR），选择检验数最小的 $\sigma_{m+k}0$ 对应的非基变量 $x_{m+k}$ 入基。但是没有人证明，LRR是否比其他的转入规则好，其中“好”的标准不是针对某个线性规划实例，而是相对于整个线性规划问题来说的。

（2）转出规则：最小比检验规则（minimum ratio test, MRT），参考线性规划典范形式的一般表达，我们令

$\theta= {\rm min} \left\{ \frac{\alpha_i}{\beta_{ik}}|\beta_{ik}0 \right \} = \frac{\alpha_l}{\beta_{lk}}$