线性规划设计的基本性质.ppt

《线性规划设计的基本性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划线性规划2021/7/2712021/7/2722021/7/2732021/7/2742021/7/2752021/7/2762021/7/2772021/7/2782021/7/2792021/7/27102021/7/27112021/7/27122021/7/2713是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足四、线性规划解的概念和性质1.线性规划解的概念2021/7/27142021/7/2715B是可逆的；B的行列式≠02021/7/2716x≥02021/7/2717基本解的个

2、数？2021/7/2718非基变量是自由变量.基变量用非基变量表示。2021/7/27引理1.线性规划的可行解为基可行解的充要条件是其正分量对应的系数列向量线性无关.引理2.可行解x是K的顶点的充要条件是x为线性规划的基可行解。2021/7/27当这些列向量线性无关时，由引理1，知x为基础可行解.当向量线性相关时，则存在一组不全为零的数组,使得成立。证明：设x是可行解，且前k个正分量为若它们在矩阵A中对应的列向量为（1）则有由(2)式右端为零，因此总可假定存在非零的,(否则乘以-1于（2）的两端)，总有成立。（2）2021/7/27在

3、上式中乘以并与（2）相加得：因而，当取时，上式中至少会有一个分量。也就是说，若记上式中对应的点为，则正分量比x至少减少一个.若此时，正分量对应的{}线性无关，则已是基础可行解。否则重复上述过程，正分量的个数不断减少，至多减至只剩一个时为止，例如对应列向量为但，它是只含一个向量的线性无关组，因此，如果约束集有可行解，则必定存在基本可行解。2021/7/27定理2（线性规划基本定理）设约束集K非空()有解，且最大值可在一个顶点（基础可行解）上达到。对任意的，LP的目标函数值有上界，则线性规划2021/7/2723ThankYou!谢谢观看

4、！2020