2.4 线性规划的基本定理

由于线性规划模型中目标函数和约束方程均为线性的，因此线性规划问题具有如下一些特殊的性质或定理。

定理2.2.1 若线性规划问题存在可行域，则其可行域是一个凸集。

证明：

证明：任取　\mathbf x^{(1)},\mathbf x^{(2)} \in \mathscr F，则满足\mathbf {Ax}^{(1)}=\mathbf b, \mathbf x^{(1)}≥, \mathbf {Ax}^{(2)}=\mathbf b, \mathbf x^{(2)}≥,

则对任意的\mathbf x=  \alpha \mathbf x^{(1)}+(1−\alpha )\mathbf x^{(2)}，0<\alpha <1，有　

\begin{aligned}\mathbf {Ax} &= A\left[\alpha\mathbf {Ax}^{(1)}+(1−\alpha)\mathbf x^{(2)}\right]\\&=\alpha \mathbf {Ax}^{(1)}+(1−\alpha)\mathbf {Ax}^{(2)} \\&=\alpha\mathbf b+(1−\alpha)\mathbf b\\&=\mathbf b.\end{aligned}

又因为\mathbf x^{(1)},\mathbf x^{(2)}, \alpha , 1− \alpha均非负，所以\mathbf x=\alpha \mathbf x^{(1)}+(1− \alpha )\mathbf x^{(2)}≥．

由此可知，\mathbf x=\alpha \mathbf x^{(1)}+(1− \alpha )\mathbf x^{(2)} \in \mathscr F，即\mathscr F是凸集．

证毕．

从几何的角度来看，标准线性规划中的满足约束的点集是凸集，如果在中找不到两个不同的点和使成立，则称是极点或顶点．

引理2.2.1 设是标准型线性规划(LP)的可行解，为(LP)的基本可行解的充要条件是，的正分量对应的系数列向量线性无关．

引理2.2.2 设是标准型线性规划(LP)的可行解，为(LP)的基本可行解的充要条件是，为可行域的极点．

证明：

（1）必要性：因为\mathbf{x}是基本解，由基本解的定义，\mathbf{x}的非零分量所对应的系数列向量线性无关，又因为\mathbf{x}是可行解，由基本可行解的定义，非零分量均是正的，所以\mathbf{x}的正分量所对应的系数列向量线性无关．

（2）充分性：设\mathbf{x}是线性规划问题的可行解，且正分量_,_,⋯,_ 所对应的列向量\mathbf p_,\mathbf p _,⋯,\mathbf p_也线性无关，则必有≤.

若=，则\mathbf p_,\mathbf p_,⋯,\mathbf p_刚好构成一个基，\mathbf{x}=(_,⋯_,,⋯)^为相应的基本可行解。

若<，则一定可以从其余的−个系数列向量中取出−个与\mathbf p_,\mathbf p_,⋯,\mathbf p_构成最大线性无关向量组，其对应的基本可行解恰好为\mathbf{x}，不过此时的\mathbf{x}是一个退化的基本可行解．

证毕．

    因为线性规划(LP)的可行域为凸多面体，根据几何理论，一个有限维的凸多面体至多有有限个顶点（极点），但可能存在一些基本可行解位于多面体的边上或面上，而不是在顶点处。这些解虽然满足基本解的条件，但它们并不代表多面体的极值点。因此，可得如下结论：

结论 线性规划(LP)的可行域最多具有有限个极点，但基本可行解与极点并不是一一对应的．

例2 已知线性规划问题的约束条件为，其中．试讨论可行域顶点和基本可行解之间的对应关系．

解 可行域\mathscr F为四维凸多面体，可以推得在四维空间中有3个顶点

P=(0,0,10,10)，Q=(0,10,0,10)，R=(10,0,0,0).

这3个顶点与线性规划的5个基本可行解的对应关系如下：

• 顶点P对应以x_3,x_4为基变量的基本可行解；

• 顶点Q对应以x_2,x_4为基变量的基本可行解；

• 顶点R对应x_1,x_2;x_1,x_3和x_1,x_4为基变量的退化基本可行解．

定理2.2.2  若线性规划(LP)存在可行解，则它一定存在基本可行解．

证明：设\mathbf x=(x_1,x_2,\cdots,x_n)^{\rm T}是(LP)的可行解．不失一般性，设其前k个分量为正，其余分量为零．则有

\sum_{j=1}^k x_j\mathbf p_j=\mathbf b．

若\mathbf p_1,\mathbf p_2,\cdots,\mathbf p_k线性无关，则\mathbf{x}为基本可行解；若\mathbf p_1,\mathbf p_2,\cdots,\mathbf p_k线性相关，即有一组不全为0的数\alpha_1,\alpha_2,\cdots,\alpha_k，使得

\alpha_1\mathbf p_1+\alpha_2\mathbf p_2+\cdots+\alpha_k\mathbf p_k=0．

与引理2的证明类似，作

\mathbf{x}^{(1)}=\mathbf{x}+\varepsilon\alpha, \mathbf{x}^{(2)}=\mathbf{x}-\varepsilon\alpha,

其中\alpha=(\alpha_1,\cdots,\alpha_k,0,\cdots,0)^\top．

当\varepsilon充分小时，\mathbf{x}^{(1)},\mathbf{x}^{(2)}是线性规划(LP)的可行解．

选择适当的\varepsilon，使得

x_j+\varepsilon \alpha_j,x_j-\varepsilon \alpha_j(j=1,\cdots,k)

中至少有一个为零，而其余的值大于零．

这样得到一个新的可行解，其中非零分量的个数比\mathbf{x}至少减少一个．

如果新的可行解正分量对应的列向量线性无关，则问题得证．否则重复上面的过程直到正分量对应的列向量线性无关为止．

证毕．

定理 2.2.3  若线性规划(LP)存在最优解，则必存在基本可行解是最优解．

证明：设\mathbf{x}是最优解，若\mathbf{x}不是基本可行解，做出两个新的可行解：\mathbf{x}+\varepsilon\mathbf a和\mathbf{x}-\varepsilon\mathbf a，对应的目标函数值为\mathbf{c}^\top\mathbf{x}+\varepsilon\mathbf{c}^\top\mathbf a与\mathbf{c}^\top x-\varepsilon\mathbf{c}^\top\mathbf a．

由于\mathbf{x}是最优解，则

\mathbf{c}^\top\mathbf{x}+\varepsilon\mathbf{c}^\top\mathbf a≥\mathbf{c}^\top\mathbf{x}；

\mathbf{c}^\top\mathbf{x}-\varepsilon\mathbf{c}^\top\mathbf a≥\mathbf{c}^\top\mathbf{x}，

因此\mathbf{c}^\top\mathbf a=0.

于是，当\varepsilon>0充分小时，\mathbf{x}+\varepsilon\mathbf a,\mathbf{x}-\varepsilon\mathbf a也是可行最优解．

    基于以上3个定理，求解线性规划问题可转换为在有限数量的基本可行解中进行搜索，这极大地缩减了求解的工作量．