线性规划基本性质

1、关于线性规划的基本性质第一张，PPT共二十三页，创作于2022年6月第二张，PPT共二十三页，创作于2022年6月2022/8/112第三张，PPT共二十三页，创作于2022年6月2022/8/113第四张，PPT共二十三页，创作于2022年6月2022/8/114第五张，PPT共二十三页，创作于2022年6月2022/8/115第六张，PPT共二十三页，创作于2022年6月2022/8/116第七张，PPT共二十三页，创作于2022年6月第八张，PPT共二十三页，创作于2022年6月2022/8/118第九张，PPT共二十三页，创作于2022年6月2022/8/119第十张，PPT共二十三页

2、，创作于2022年6月2022/8/1110第十一张，PPT共二十三页，创作于2022年6月第十二张，PPT共二十三页，创作于2022年6月2022/8/1112 是凸集(convex set)，如果对S中任意两 点 x , y 和(0,1)中的任一数 满足四、线性规划解的概念和性质1. 线性规划解的概念第十三张，PPT共二十三页，创作于2022年6月2022/8/1113第十四张，PPT共二十三页，创作于2022年6月2022/8/1114B是可逆的；B的行列式0第十五张，PPT共二十三页，创作于2022年6月2022/8/1115x0第十六张，PPT共二十三页，创作于2022年6月2022

3、/8/1116基本解的个数？第十七张，PPT共二十三页，创作于2022年6月2022/8/1117非基变量是自由变量. 基变量用非基变量表示。第十八张，PPT共二十三页，创作于2022年6月2022/8/1118引理1. 线性规划的可行解为基可行解的充要条件是其正分量对应的系数列向量线性无关. 引理2. 可行解x是K的顶点的充要条件是x为线性规划的基可行解。第十九张，PPT共二十三页，创作于2022年6月2022/8/11当这些列向量线性无关时，由引理1 ，知x为基础可行解.当向量 线性相关时，则存在一组不全 为零的数组 ,使得 成立。证明： 设x是可行解，且前k个正分量为 若它们在矩阵A中对

4、应的列向量为（1）则有由(2)式右端为零，因此总可假定存在非零的 ,(否则乘以-1于（2）的两端)，总有 成立。（2）第二十张，PPT共二十三页，创作于2022年6月2022/8/11在上式中乘以 并与（2）相加得： 因而，当取时，上式中至少会有一个分量。也就是说，若记上式中对应的点为，则正分量 比x至少减少一个. 若此时，正分量对应的 线性无关，则已是基础可行解。 否则重复上述过程，正分量的个数不断减少，至多减至只剩一个时为止，例如对应列向量为 但，它是只含一个向量的线性无关组，因此，如果约束集有可行解，则必定存在基本可行解。 第二十一张，PPT共二十三页，创作于2022年6月2022/8/11定理2 （线性规划基本定理） 设约束集K非空( )有解，且最大值可在一个顶点（基础可行解）上达到。对任意的，LP的目标函数值有上界，则线性规划第二十二张，P