《线性规划的基本性质讲稿.ppt》由会员分享，可在线阅读，更多相关《线性规划的基本性质讲稿.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于线性规划的基本性质第一页，讲稿共二十三页哦2023/4/72第二页，讲稿共二十三页哦2023/4/73第三页，讲稿共二十三页哦2023/4/74第四页，讲稿共二十三页哦2023/4/75第五页，讲稿共二十三页哦2023/4/76第六页，讲稿共二十三页哦第七页，讲稿共二十三页哦2023/4/78第八页，讲稿共二十三页哦2023/4/79第九页，讲稿共二十三页哦2023/4/710第十页，讲稿共二十三页哦第十一页，讲稿共二十三页哦2023/4/712第十二页，讲稿共二十三页哦2023/4/713 是凸集是凸集(convex set)，如果对，如果对S中任意两中任意两 点点 x,y 和和(0,1
2、)中的任一数中的任一数 满足满足四、线性规划解的概念和性质四、线性规划解的概念和性质1.线性规划解的概念线性规划解的概念第十三页，讲稿共二十三页哦2023/4/714第十四页，讲稿共二十三页哦2023/4/715B B是可逆的；是可逆的；B B的行的行列式列式0 0第十五页，讲稿共二十三页哦2023/4/716x0第十六页，讲稿共二十三页哦2023/4/717基本解的个基本解的个数？数？第十七页，讲稿共二十三页哦2023/4/718非基变量是自由变量非基变量是自由变量.基变量用非基变量表示。基变量用非基变量表示。第十八页，讲稿共二十三页哦2023/4/7引理1.线性规划的可行解为基可行解的充要
3、条件是其正分量对应的系数列向量线性无关.引理2.可行解x是K的顶点的充要条件是x为线性规划的基可行解。第十九页，讲稿共二十三页哦2023/4/7当这些列向量线性无关时，由引理1，知x为基础可行解.当向量 线性相关时，则存在一组不全 为零的数组,使得 成立。证明：设x是可行解，且前k个正分量为 若它们在矩阵A中对应的列向量为（1）则有由(2)式右端为零，因此总可假定存在非零的 ,(否则乘以-1于（2）的两端)，总有 成立。（2）第二十页，讲稿共二十三页哦2023/4/7在上式中乘以 并与（2）相加得：因而，当取时，上式中至少会有一个分量。也就是说，若记上式中对应的点为，则正分量 比x至少减少一个.若此时，正分量对应的 线性无关，则已是基础可行解。否则重复上述过程，正分量的个数不断减少，至多减至只剩一个时为止，例如对应列向量为 但，它是只含一个向量的线性无关组，因此，如果约束集有可行解，则必定存在基本可行解。第二十一页，讲稿共二十三页哦2023/4/7定理2（线性规划基本定理）设约束集K非空()有解，且最大值可在一个顶点（基础可行解）上达到。对任意的，LP的目标函数值有上界，则线性规划第二十二页，讲稿共二十三页哦2023/4/7感感谢谢大大家家观观看看第二十三页，讲稿共二十三页哦