最优化及其运用 学习笔记（二）

基、基向量、基变量

⊙设 r(A) = m，并且 B 是 A 的 m 阶非奇异的子矩阵（det(B) <> 0)，

    则矩阵 B 称为线性规划问题的一个基。

⊙矩阵 B =（P1，P2….Pm) ，其列向量 Pj 称为 对应基 B 的基向量。

    A中其余列向量称为 非基向量。

⊙与基向量 Pj 相对应的变量xj就称为 基变量，其余的就称为 非基变量。

 

 

基本解、基本可行解、可行基

⊙对于某一特定的基B，非基变量取 0 值的解，称

    为 基本解。

⊙满足非负约束条件的基本解，称

    为 基本可行解。

⊙与基本可行解对应的基，称

    为 可行基。

 

 

 

凸组合：

       设x(1),x(2) …..x(k)是n维线性空间Rn中的k个点，

若  存在 数u1,u2,….uk 

     且0< ui <1    (i=1,2,…k), S ui =1,      

      使得 x= u1 x(1)+ u2 x(2) +…..+ uk x(k) 成立，

则  称 x为x(1),x(2) …..x(k)的凸组合。

 

顶点：

设D是凸集, 若D中的点x 不能成为D中任何线段上的内点，则称点x为凸集D的顶点。

 

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

（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。)

 

引理1  线性规划问题的可行解X为基本可行解的充分必要条件是：X的(非零)正分量所对应的系数矩阵A的列向量是线性无关的。

 

定理2  线性规划问题的可行域中的点X是顶点的充分必要条件是：X是基本可行解。

X是基本可行解 <=> X是可行域的顶点

 

引理2  若可行域D是有界凸集，则D中任意一点x，都可表示成D的顶点的凸组合。

由此可知，线性规划问题的任一可行解都可表示成基本可行解的凸组合。

 

定理3  若可行域D有界，则线性规划问题的最优解，必定在D的顶点上达到。

说明1：若可行解集D无界，则线性规划问题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。

说明2：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）