1. 线性规划的标准问题
首先来看线性规划的标准问题：
mins.t.cT⋅xAx=b,xi≥0
A∈Rm×n,x∈Rn,c∈Rn，且要求 Rank(A)=m（A 是行满秩矩阵）。
下面是一些基本概念的定义：
设 B 为 A 中任意非奇异的 m×m 阶子矩阵（|B|≠0），则称 B 为此规划的一个基，令 B=(Pj1,…,Pjm)，下标 {j1,j2,…,jm}∈{1,2,…,n}，对应的记 xB={xj1,xj2,…,xjm} 为基变量，其余为非基变量。
令非基变量均为 0，则有：
Bxb=b
一些概念：
- 基本解：xN=0,xB=B−1b（这样记，由基构成的解）
- 可行解：若最终求得的向量 x 满足约束，Ax=b,x≥0，这样的解为可行解（或叫容许解）；
- 基本可行解：同时满足基本解，可行解的解，也即 xN=0,xB=B−1b≥0 的为基本可行解；
2. 判别定理
BxB+NxN=b⇓xB=B−1b−B−1NxN
根据 A=(B,N) 的拆分形式，对其做进一步的推导：
x0====cTx(cTB,cTN)(xBxN)cTBxB+cTNxNcTBB−1b−(cTBB−1N−cTN)xN
因为 cTBB−1 常常出现，又进一步称其为单纯性子。对上式移项调整，进一步可得：
x0+(cTBB−1N−cTN)xN=cTBB−1b,(cTBB−1B−cTB)xB=0⇓x0+(cTBB−1B−cTB)xB+(cTBB−1N−cTN)xN=cTBB−1bx0+(cTBB−1A−cT)x=cTBB−1b
设 B 为线性规划的一个基，若 B−1b≥0，且有 cTBB−1A−cT≥0，则对应于 B 的基本解式必是线性规划问题的最优解。
- B−1b≥0 ⇒ 基本可行解；
- cTBB−1A−cT≥0 ⇒ x0≤cTBB−1b
3. 单纯形表
单纯形表与基向量 B 有关，
T(B)=[cTBB−1bB−1bcTBB−1A−cTB−1A]
其中：
- cTBB−1b 是标量；
- cTBB−1A−cT 是行向量；
- B−1b 是列向量；
- B−1A 是矩阵；