首先我们指出，线性规划均可等价地化成如下标准形式 { min ? ? c T x , s . t ? A x = b , x ? 0 , \begin{align}\begin{cases}\min~c^Tx,\\\mathrm{s.t}~Ax=b,\\x\succeq0,&\end{cases}\end{align} ? ? ??min?cTx,s.t?Ax=b,x?0,????其中， A = [ a 1 , ? ? , a n ] ∈ R m × n , b ∈ R m , c ∈ R n A=[a_1,\cdots,a_n]\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,c\in\mathbb{R}^n A=[a1?,?,an?]∈Rm×n,b∈Rm,c∈Rn不妨恒假定矩阵 A A A 是行满秩的，即 r a n k ( A ) = m \mathbf{rank}(A)=m rank(A)=m(否则根据线性代数的理论，可以找到 r a n k ( A ) \mathbf{rank}(A) rank(A) 行方程来替换原方程，同时为了叙述简便，分别称矩阵 A A A 和 向量 b b b 为(1)的系数矩阵和右端向量.
因为线性规划的可行集是一个多面体，并且目标函数是线性的，从几何上直观地看，线性函数在多面体上的极小点若存在，则必然在多面体的顶点上取得.对于标准形式的线性规划问题，其最小值点必在坐标轴上达到，于是这就需要研究 A x = b Ax = b Ax=b 的所谓基础解的性质.
对标准形式的线性规划问题(7.1.1), 设方程组 A x = b Ax=b Ax=b 有解. 设 b ∈ s p a n ( A ) , { a j } j ∈ J b\in\mathbf{span}(A),\{a_j\}_{j\in J} b∈span(A),{aj?}j∈J? 是 A A A的列向量的一个极大线性无关组，其中 J ? { 1 , . . . , n } , ∣ J ∣ = m ( ∣ J ∣ J\subset \{ 1, ..., n\} , |J|= m( |J| J?{1,...,n},∣J∣=m(∣J∣ 表示集合 J J J 所含元素个数).那么 b b b 必可表示为 { a j } j ∈ J \{a_j\}_{j\in J} {aj?}j∈J? 的线性组合.
定义 1.1 (线性方程组的基础解) 设 A ∈ R m × n , ? b ∈ R m , ? x = ( x 1 , . . . , x n ) T A\in\mathbb{R}^{m\times n},\:b\in\mathbb{R}^m,\:x=(x_1,...,x_n)^T A∈Rm×n,b∈Rm,x=(x1?,...,xn?)T 是线性方程组 A x = b Ax=b Ax=b 的一个解.如果存在 J ? { 1 , ? ? , n } , ∣ J ∣ = r a n k ( A ) J\subset\{1,\cdots,n\},\quad|J|=\mathbf{rank}(A) J?{1,?,n},∣J∣=rank(A),使得 x j = 0 , ? j ∈? J ; { a j ∣ j ∈ J } 线性无关 , x_j=0,\quad\forall j\not\in J;\quad\{a_j|j\in J\}\text{线性无关}, xj?=0,?j∈J;{aj?∣j∈J}线性无关,则称 x x x 为一个基础解， x x x 的分量 { x j ∣ j ∈ J } \{x_j|j\in J\} {xj?∣j∈J} 称为相应的基变量，并称 { x j ∣ j ∈? J } \{x_j|j\not\in J\} {xj?∣j∈J} 为非基变量.若 { x j ∣ j ∈ J } \{x_j|j\in J\} {xj?∣j∈J} 含有零元素，则称 x x x 是一个退化的基础解.
显然，若 A x = b Ax=b Ax=b 有解，则矩阵 A A A 的列向量 { a 1 , . . . , a n } \{a_1,...,a_n\} {a1?,...,an?} 的每一个极大线性无关组对应于一个基础解，由于 { a 1 , . . . , a n } \{a_1,...,a_n\} {a1?,...,an?} 的极大线性无关组未必唯一，所以 A x = b Ax=b Ax=b 的基础解也不一定是唯一的.
引理 1.1 设 A = [ a 1 , . . . , a n ] ∈ R m × n , ? b ∈ R m , ? x ∈ R n A=[a_1,...,a_n]\in\mathbb{R}^{m\times n},\:b\in\mathbb{R}^m,\:x\in\mathbb{R}^n A=[a1?,...,an?]∈Rm×n,b∈Rm,x∈Rn 是 A x = b Ax=b Ax=b 的一个解，那么 x x x 是基础解当且仅当 { a j ∣ x j ≠ 0 } \{a_j|x_j\neq0\} {aj?∣xj?=0} 线性无关.
证. 设 x x x 是基础解，根据线性方程组基础解的定义，存在 J ? { 1 , ? ? , n } , ∣ J ∣ = r a n k ( A ) J\subset\{1,\cdots,n\},\quad|J|=\mathbf{rank}(A) J?{1,?,n},∣J∣=rank(A),使得 x j = 0 , ? j ∈? J ; { a j ∣ j ∈ J } 线性无关 , x_j=0,\quad\forall j\not\in J;\quad\{a_j|j\in J\}\text{线性无关}, xj?=0,?j∈J;{aj?∣j∈J}线性无关,于是由集合的性质可以得到， { a j ∣ x j ≠ 0 } ? { a j ∣ j ∈ J } \{a_j|x_j\neq0\}\subset\{a_j|j\in J\} {aj?∣xj?=0}?{aj?∣j∈J}, 所以 { a j ∣ x j ≠ 0 } \{a_j|x_j\neq0\} {aj?∣xj?=0} 是极大线性无关组的子集，故线性无关.
反之，设
A
x
=
b
Ax=b
Ax=b 且
{
a
j
∣
x
j
≠
0
}
\{a_j|x_j\neq0\}
{aj?∣xj?=0} 线性无关.不妨设
{
x
j
≠
0
j
=
1
,
?
?
,
k
;
x
j
=
0
j
=
k
+
1
,
?
?
,
n
.
\begin{cases}x_j\neq0&j=1,\cdots,k;\\x_j=0&j=k+1,\cdots,n.\end{cases}
{xj?=0xj?=0?j=1,?,k;j=k+1,?,n.?因为
a
1
,
.
.
.
,
a
k
a_1,...,a_k
a1?,...,ak? 线性无关，所以
k
≤
m
=
r
a
n
k
(
A
)
k\leq m= \mathbf{rank}(A)
k≤m=rank(A). 当
k
<
m
k<m
k<m 时从
a
k
+
1
,
?
?
,
a
n
a_{k+1},\cdots,a_n
ak+1?,?,an? 中挑选
m
?
k
m-k
m?k 个向量，不妨设为
a
k
+
1
,
?
?
,
a
m
a_{k+1},\cdots,a_m
ak+1?,?,am?,使得
a
1
,
?
?
,
a
m
a_1,\cdots,a_m
a1?,?,am? 线性无关. 由于
x
m
+
1
=
.
.
.
=
x
n
=
0
x_{m+1}=...=x_n= 0
xm+1?=...=xn?=0，所以
x
x
x 是
A
x
=
b
Ax=b
Ax=b 的一个基础解.
n n n 维线性方程组 A x = b Ax=b Ax=b 的解 x x x的全体构成 R n \mathbb{R} ^n Rn 中的一个仿射集. 其基础解是落在某个 m m m 维子空间的解，它使得 { a j ∣ x j ≠ 0 } \{a_j|x_j\neq0\} {aj?∣xj?=0} 线性无关.
定义 1.2 (基础可行解和基础最优解) 对于线性规划(1)即 { min ? ? c T x , s . t ? A x = b , x ? 0 , \begin{aligned}\begin{cases}\min~c^Tx,\\\mathrm{s.t}~Ax=b,\\x\succeq0,&\end{cases}\end{aligned} ? ? ??min?cTx,s.t?Ax=b,x?0,???设 x x x 是 A x = b Ax=b Ax=b 的一个基础解，
(1) 若 x x x 还是(1)的一个可行点，即 x ? 0 x\succeq0 x?0, 则称之为(1)的一个基础可行解；
(2) 若 x x x 还是(1)的一个最优解，则称之为(1)的一个基础最优解.
对于线性规划(7.1.1),有
命题 1.2 (线性规划基本定理) 对于线性规划(1)有
(1) 若存在可行点，则必存在基础可行解；
(2) 若存在最优解，则存在基础最优解
证.设
A
=
[
a
1
,
?
?
,
a
n
]
∈
R
m
×
n
,
b
∈
R
m
,
x
A=[a_1,\cdots,a_n]\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,x
A=[a1?,?,an?]∈Rm×n,b∈Rm,x 是(1)的一个可行点.若
{
a
j
∣
x
j
>
0
}
\{a_j|x_j>0\}
{aj?∣xj?>0} 线性相关，不妨设
x
x
x 的前
k
k
k 个分量非零：
x
j
>
0
,
j
=
1
,
?
?
,
k
;
x
j
=
0
,
j
=
k
+
1
,
?
?
,
n
.
\begin{aligned}x_j>0,&&j=1,\cdots,k;&&x_j=0,&&j=k+1,\cdots,n.\end{aligned}
xj?>0,??j=1,?,k;??xj?=0,??j=k+1,?,n.?由于
{
a
j
∣
x
j
>
0
}
\{a_j|x_j>0\}
{aj?∣xj?>0} 线性相关，于是存在
0
≠
y
=
(
y
1
,
?
?
,
y
k
,
0
,
?
?
,
0
)
T
∈
R
n
0\neq y=(y_1,\cdots,y_k,0,\cdots,0)^T\in\mathbb{R}^n
0=y=(y1?,?,yk?,0,?,0)T∈Rn, 使得
A
y
=
y
1
a
1
+
?
+
y
k
a
k
=
0.
Ay=y_1a_1+\cdots+y_ka_k=0.
Ay=y1?a1?+?+yk?ak?=0.易见，当
?
>
0
\epsilon>0
?>0 充分小时，有
\quad
(a)
x
j
±
?
y
j
>
0
,
j
=
1
,
?
?
,
k
x_j\pm \epsilon y_j> 0, j= 1, \cdots , k
xj?±?yj?>0,j=1,?,k.所以
x
±
?
y
x\pm\epsilon y
x±?y 都是可行点；
\quad
(b) 若
x
x
x 是最优解，则
c
T
x
≤
c
T
(
x
±
?
y
)
c^Tx\leq c^T(x\pm\epsilon y)
cTx≤cT(x±?y),即
c
T
y
=
0
c^Ty=0
cTy=0. 从而
c
T
(
x
±
?
y
)
=
c
T
x
.
c^T(x\pm\epsilon y)=c^Tx.
cT(x±?y)=cTx.
不妨设 y 1 , . . . , y k y_1,...,y_k y1?,...,yk? 中至少有一个为正的项. 下面我们用用逐步逼近的思想，来让可行解 x x x 其中一个分量变为零后但仍为可行解.
让 ? \epsilon ? 逐步增大，直到 { x j ? ? y j ∣ j = 1 , . . . , k } \{x_j-\epsilon y_j|j=1,...,k\} {xj???yj?∣j=1,...,k} 中至少有一项为 0 而其余各项非负. 因为 ? \epsilon ? 充分小，于是 x ~ : = x ? ? y \tilde{x}:=x-\epsilon y x~:=x??y 仍是一个可行点，且它比 x x x 至少多出一个为零的分量.
若 { a j ∣ x ~ j > 0 } \{a_j|\tilde{x}_j>0\} {aj?∣x~j?>0} 仍线性相关，不断重复上述逐步逼近的操作，那么有限次后便得到可行点 x ~ \tilde{x} x~, 使得 { a j ∣ x ~ j > 0 } \{a_j|\tilde{x}_j>0\} {aj?∣x~j?>0} 线性无关(因为线性方程组 A x = b Ax=b Ax=b的 系数矩阵 A A A 的秩不为0).因为 0 ? x 0\preceq x 0?x，所以 { a j ∣ x ~ j > 0 } = { a j ∣ x ~ j ≠ 0 } \{a_j|\tilde{x}_j>0\}=\{a_j|\tilde{x}_j\neq0\} {aj?∣x~j?>0}={aj?∣x~j?=0}, 于是由引理 1.1可知， x ~ \tilde{x} x~ 是一个基础可行解. (1) 获证.
命题 1.2是非常重要的，它能够说明在整个可行集中求解线性规划(1)的问题可以归结为在基础可行集中求解.而 A x = b Ax=b Ax=b 的基础解个数就是 { a 1 , . . . , a n } \{a_1,...,a_n\} {a1?,...,an?} 的极大线性无关组的个数，且最大个数为 ( n m ) \binom{n}{m} (mn?).
定义 1.3 (极点) 设 x ∈ S ? R n x\in S\subset\mathbb{R}^n x∈S?Rn. 如果不存在互异的 x 1 , x 2 ∈ S x_1,x_2\in S x1?,x2?∈S 以及 0 < θ < 1 0<\theta<1 0<θ<1, 使得 x = θ x 1 + ( 1 ? θ ) x 2 x=\theta x_1+(1-\theta)x_2 x=θx1?+(1?θ)x2?，即线段 x 1 x 2 x_1x_2 x1?x2?之间任意一点都不属于集合 S S S ，则称 x x x 是 S S S 的一个极点.
命题 1.3 (基础可行解的几何特征) 设 A ∈ R m × n , b ∈ R m A\in\mathbb{R}^{m\times n},\quad b\in\mathbb{R}^m A∈Rm×n,b∈Rm,记 D : = { x ∈ R n ∣ A x = b , ? x ? 0 } \mathcal{D}:=\{x\in\mathbb{R}^n|Ax=b,\:x\succeq0\} D:={x∈Rn∣Ax=b,x?0}.那么， x x x 是一个基础可行解当且仅当它是 D D D 的一个极点.
证.设 x x x 不是 D \mathcal{D} D 的一个极点，不妨设 x ∈ D ( x\in\mathcal{D}( x∈D(否则已经不是基础可行解). 因为 x x x是基础可行解且 x x x 不是极点，于是存在 y , z ∈ D , ? y ≠ z y,z\in\mathcal{D},\:y\neq z y,z∈D,y=z,以及 0 < θ < 1 0<\theta<1 0<θ<1, 使得 x = θ y + ( 1 ? θ ) z x=\theta y+(1-\theta)z x=θy+(1?θ)z.不妨设设 { i ∣ x i > 0 } = { 1 , . . . , k } . \{i|x_i>0\}=\{1,...,k\}. {i∣xi?>0}={1,...,k}. 由于 x , y , z x,y,z x,y,z 的所有分量都是非负的，且由于 x = θ y + ( 1 ? θ ) z x=\theta y+(1-\theta)z x=θy+(1?θ)z，所以 y , z y,z y,z 的后 n ? k n-k n?k 个分量也是 0. 于是 ∑ i = 1 k ( y i ? z i ) a i = ∑ i = 1 k y i a i ? ∑ i = 1 k z i a i = A y ? A z = b ? b = 0. \sum_{i=1}^k(y_i-z_i)a_i=\sum_{i=1}^ky_ia_i-\sum_{i=1}^kz_ia_i=Ay-Az=b-b=0. i=1∑k?(yi??zi?)ai?=i=1∑k?yi?ai??i=1∑k?zi?ai?=Ay?Az=b?b=0.所以 a 1 , . . . , a k a_1,...,a_k a1?,...,ak? 线性相关. 由 引理 1.1可知， x x x 不是一个基础可行解，矛盾
反之，设 x x x 不是一个基础可行解但 x x x是极点，不妨设 x ∈ D ( x\in\mathcal{D}( x∈D(否则它已经不是 D \mathcal{D} D 的极点). 由于 x x x 不是基础可行解，则 x x x 也不是 A x = b Ax=b Ax=b 的基础解. 不妨设 { i ∣ x i > 0 } = { 1 , . . . , k } \{i|x_i>0\}=\{1,...,k\} {i∣xi?>0}={1,...,k}, 那么 a 1 , . . . , a k a_1,...,a_k a1?,...,ak? 线性相关. 于是存在 0 ≠ y = ( y 1 , ? ? , y k , 0 , ? ? , 0 ) T 0\neq y=(y_1,\cdots,y_k,0,\cdots,0)^T 0=y=(y1?,?,yk?,0,?,0)T, 使得 A y = 0 Ay=0 Ay=0. 易见当 ? \epsilon ? 充分小时，有 x ± ? y ∈ D , x = 1 2 [ ( x + ? y ) + ( x ? ? y ) ] . x\pm\epsilon y\in\mathcal{D},\quad x=\frac{1}{2}\big[(x+\epsilon y)+(x-\epsilon y)\big]. x±?y∈D,x=21?[(x+?y)+(x??y)].所以 x x x 不是 D \mathcal D D 的极点，矛盾.