线性规划的基本性质.ppt

关于线性规划的基本性质**第2页,共23页，星期六，2024年，5月**第3页,共23页，星期六，2024年，5月**第4页,共23页，星期六，2024年，5月**第5页,共23页，星期六，2024年，5月**第6页,共23页，星期六，2024年，5月第7页,共23页，星期六，2024年，5月**第8页,共23页，星期六，2024年，5月**第9页,共23页，星期六，2024年，5月**第10页,共23页，星期六，2024年，5月第11页,共23页，星期六，2024年，5月**第12页,共23页，星期六，2024年，5月**是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足四、线性规划解的概念和性质1.线性规划解的概念第13页,共23页，星期六，2024年，5月**第14页,共23页，星期六，2024年，5月**B是可逆的；B的行列式≠0第15页,共23页，星期六，2024年，5月**x≥0第16页,共23页，星期六，2024年，5月**基本解的个数？第17页,共23页，星期六，2024年，5月**非基变量是自由变量.基变量用非基变量表示。第18页,共23页，星期六，2024年，5月*引理1.线性规划的可行解为基可行解的充要条件是其正分量对应的系数列向量线性无关.引理2.可行解x是K的顶点的充要条件是x为线性规划的基可行解。第19页,共23页，星期六，2024年，5月*当这些列向量线性无关时，由引理1，知x为基础可行解.当向量线性相关时，则存在一组不全为零的数组,使得成立。证明：设x是可行解，且前k个正分量为若它们在矩阵A中对应的列向量为（1）则有由(2)式右端为零，因此总可假定存在非零的,(否则乘以-1于（2）的两端)，总有成立。（2）第20页,共23页，星期六，2024年，5月*在上式中乘以并与（2）相加得：因而，当取时，上式中至少会有一个分量。也就是说，若记上式中对应的点为，则正分量比x至少减少一个.若此时，正分量对应的{}线性无关，则已是基础可行解。否则重复上述过程，正分量的个数不断减少，至多减至只剩一个时为止，例如对应列向量为但，它是只含一个向量的线性无关组，因此，如果约束集有可行解，则必定存在基本可行解。第21页,共23页，星期六，2024年，5月*定理2（线性规划基本定理）设约束集K非空()有解，且最大值可在一个顶点（基础可行解）上达到。对任意的，LP的目标函数值有上界，则线性规划第22页,共23页，星期六，2024年，5月*感谢大家观看第23页,共23页，星期六，2024年，5月