模式分类笔记 -- 线性规划（1）

线性规划的定义和应用场景不用描述了，主要记一下跟单纯形方法相关的东西，记下来，免得又要从大量信息中筛取。一门学科，东西太多，先列点最本质 的东西，有需要的话以后再深入点，加个标号（1），

 

极点这个概念在单纯形方法里是很重要的，那就多花点笔墨在上面，做点引申。

 

如果有最优解，关心的是凸集。 我们来看一下凸集的广义的定义：

设集合S<=R(n维)，若存在x1，x2<=S, 0<a <1, ax1 + (1-a)x2 <= S,则称S为凸集。其实来源于二维的情况，两点连线上的点仍然在集合内部，我们就认为图形是凸的。上面那个式子，以向量来看，改造一下形式，就清晰了。 a(x1-x2) + x2表示的就是两点之间的线段。

 

我们再提及一个概念，凸包：集合T<R(n)维的凸包是指所有包含T的凸集的交集，一个有限点集{x0, x1,...xm}(T?) <R的凸包通常为多胞形(polytope)。

 

非空凸集里不在两点连线线段中间的点称为极值点，简称极点，当然这是不严谨的说法。

 

多边形的定点，多面体的顶点，闭圆盘的边界点都是极点。

 

多面体S={x|Ax=b,x>=0}非空，则S必有极点。证明起来比较繁琐，我也没耐心消化下去了。

-------------------------------------

单纯形方法的流程：

用单纯形法求解线性规划的前提是先将模型化为标准型。

Max z =  CX

[Ax=b, x>=0]; 其中A(m*n)的秩为m，b>=0;

标准型 的特征：线性规划问题里的Max型，等式约束，非负约束 。

非标准型如何转化为标准：

（1）Min 型化为Max 型：

Min z = CX --->(加负号) Max z‘ = -CX（Min 型化为Max 型求解后，最优解不变，但最优值差负号。）

（2）不等式约束化为等式约束：加松弛变量

（ 3 ） 当模型中有某变量 xk 没有非负要求， 称为自由变量 , 则可令
xk = xk′ − xk′′, xk′ , xk′′ ≥ 0 ，化为标准型。

（4）右端项< 0 i b 时，只需将等式或不等式两端同乘（-1） ，则等式或不等式右端项比
必大于零。

（5）对x ≤ 0 的情况，令x'= −x ，显然， x'≥ 0

 

基矩阵与基变量
基矩阵(简称基) ：系数阵A 中的m 阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。
基向量：基B 中的列；其余称非基向量。
基变量：与基向量Pj 对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。

 

 

当A中的基取定后，不妨设B表示A中的前N列,则可记A = (B , N ),相应的X=(XB, XN)',约束中的AX= b可表示为(B , N )(XB, XN)' = (b), 即XB = B "b  - B "N XN,这里用"表示求逆 。

 

当取XN=0时，有XB= B"b, X={B"b, 0}', X只是基本解，XB>=0,则X成为基本可行解。

 

---------------------

极点的代数特征：

给定非空集合S={x|Ax=b,x>=0}， A<=R(m*n), rank(A)=m,则下面三个集合相等：

（1） S的基本可行解集

（2）{x|x<S,其中正分量对应的A中各列线性无关}

（3） S的极点集

换种说法，1，有可行解，就必然有基本可行解。2， 线性规划问题的基本可行解和对应可行区域的极点对应的。

 

 

根据基本可行解定义，正分量对应A中列构成的向量组线性无关；另一方面，可行解正分量对应的列向量组线性无关，则该向量组可扩展成S的一个可行基矩阵，此时相应的可行解也是基本解。后面一种换种说法，p1p2,..pk线性无关，则必存在k<=m，当k=m时，恰构成一个基，从而X=(x1,x2,.xk,0,...0)'是基本可行解。当k<m时，可从其余列向量中取出m-k个，与p1..pk构成最大线性无关组，对应解恰为X，根据定义也是基可行解。所以(1)=(2).我们只需要证明(2)=(3).

 

对于可行解x，不妨设其前p个分量为正数，其余为零。记向量xt = (x1,...xp)', 对应的子矩阵为At， 那么Atxt = b。如果把At看成p列向量的集合，也就是Epj' xt = bj。

 

先来看(3)<=(2),必要性设x是个极点，At中各列线性相关，那么就存在w<>0，使得At w=0，设y1=xt + iw， y2=xt - iw，不难看出存在充分小的正数i,使y1>=0, y2>=0，且At y1 = At xt = At y2 = b.  则向量(y1, 0)', (y2, 0)'<s，且xt =  (y1 + y2) /2, 这与xt是极点矛盾。

 

再看(2)<=(3),充分性。设At中各列线性无关，但x不是极点，根据极点定义，S中存在不相等两点y1， y2>=0, 0<i<1, x = iy1 + (1 - i)y2,因为x中后n-p个分量为0， 那么y1和y2也同样，设 w = x - y1, w不全为0，则At x - At y1 = 0，意味着At是线性相关的，矛盾。

 

---------------------

最优值出现在极点处：

其实目标方程是一个超平面，我们假设使目标方程取极大值的点x0出现在可行区域内部，那么必然存在d>0,在可行区域内存在这样一个球体， X={x:|x-x0| < d}. 那么点x1 = x0 + d/2 * c/|c|

C'x1 = C'x0 + d/2 * |c| > C'x0 ，矛盾。

 

其实是先有极点是最优值，再发现极点的代数形式，然后才有基本解的定义 ，虽然书本上是本末倒置的顺序， ，不过那样推起来才严密嘛

---------------------

我们最终的问题是使目标方程值最大化或最小化。 怎么判定什么时候是极值？极点-基本可行解的形式是B"(逆矩阵)b, 如何在一个基本可行解的基础上改进至另一个基本可行解，我们想到了如果从一个B轻松转换到另一个B1。B毕竟是A的子矩阵而已，那么问题就转换成如果A(m*n)的列向量如果能用B来表示就方便了，那么就可以轻易的替换。

这里我们定义与aj(j=1,2...n)相关的列向量yj,当然yj是个m维的向量。 aj = Byj, 那么就可以把B看成是系数矩阵，做线性变换，把yj转换成aj.

 

为了不让复杂性掩盖真实的动机与道理 ，我们每次替换B中的一个列向量，并且认为当yr中有分量yrj != 0的时候，那么br就可以被aj所替代，不为零的时候表明aj与B线性相关，其实B中任一列都可以被替换(这里的假设条件是A的秩是m，即没有多余的条件，其实也就意味着线性变换是非退化(可逆)的)，此时br可以替换成B中其余列与aj的线性表示，如br = (aj-k1b1-k2b2..)/br, 线性无关的就变成(b1, b2.., aj-k1b1-k2b2.., bm),线性变换又不改变向量间的线性关系，所以aj替换br后组成的新向量组同样也是一个基。要保证新基生成的基本解仍然是可行解，我们选择的时候要保证yrj>0,且xr/yrj = min {xi/yij} i=1..m, 求最小值的集合中yij>0,当然yij可以小于0. 具体的推导就不列了。大家有兴趣可以去这个网站 去看看，里面的pdf比较起来讲的比较详细。

 

回到判断极值的问题，新可行解xb1与上一个可行解xb2的目标方程差为

 

xr*(cj-zj) / yrj, 这里zj = CB' * B'' * aj

 

如果cj - zj >0,就表明新解更优，非退化解，xr在基B时对应的肯定是非零的。

 

如果对所有的cj - zj>=0,那么一定就达到最优解了，

评论

3 楼 doudoulong2002ok 2008-11-29  

是么？我想想

2 楼 highsky 2008-11-04  

highsky 写道

看到一个新说法：A feasible solution for which the number of nonzero variables does not exceed the numberof constraints (not counting the simplex requirement for nonnegative variables) is called a basicfeasible solution.如果可行解中非零变量的个数不超过约束方程个数（不考虑非负约束条件），那么这样的可行解就成为基本可行解。也算一个有意思的看法。

这样定义的基本可行解可以是退化的。

1 楼 highsky 2008-11-04  

看到一个新说法：
A feasible solution for which the number of nonzero variables does not exceed the number
of constraints (not counting the simplex requirement for nonnegative variables) is called a basic
feasible solution.

如果可行解中非零变量的个数不超过约束方程个数（不考虑非负约束条件），那么这样的可行解就成为基本可行解。

也算一个有意思的看法。