第四章线性规划本章主要内容:线性规划得基本理论 线性规划得单纯形法 线性规划得对偶理论 线性规划得对偶单纯形法教学目得及要求:理解线性规划得基本理论;掌握线性规划得单纯形法;理解线性规划得对偶理论;掌握线性规划得对偶单纯形法、教学重点:线性规划得单纯形法、教学难点:线性规划得对偶单纯形法。教学方法:启发式、教学手段:多媒体演示、演讲与板书相结合.教学时间:6 学时。教学内容:§4、1 线性规划得基本理论考虑线性规划问题 (LP)或其中 称为约束矩阵,称为约束方程组,称为非负约束。假定:。 定义 在(LP)中,满足约束方程组及非负约束得向量称为可行解或可行点;所有可行解得全体称为可行解集或可行域,记作,即、使目标函数在上取到最小值得可行解称为最优解;最优解对应得目标函数值称为最优值.定义 在(LP)中,约束矩阵得任意一个阶满秩子方阵称为基,中个线性无关得列向量称为基向量,中与得列对应得重量称为关于得基变量,其余得变量称为关于得非基变量.任取(L Ｐ)得一个基,记,若令关于得非基变量都取 0,则约束方程变为、由于就是满秩方阵,因此有唯一解。记,则由所构成得维向量就是得一个解,称之为(L Ｐ)得关于得基本解.基本解满足约束方程组,但不一定满足非负约束,所以不一定就是可行解.若,即基本解也就是可行解,则称为(LP)得关于基得基本可行解,相应得基称为(L Ｐ)得可行基;当时,称此基本可行解就是非退化得,否则,称之为退化得.若一个(LP)得所有基本可行解都就是非退化得,则称该(ＬＰ)就是非退化得,否则,称它就是退化得.例１ 求下列线性规划问题得所有基本可行解.解 约束矩阵得 4 个列向量依次为.全部基为对于,与为基变量,与为非基变量.令==0,有得到关于得基本解,它不就是可行解.对于,与为基变量,与为非基变量、令==０,有得到关于得基本解,它就是一个非退化得基本可行解、同理,可求得关于得基本解分别为,显然,与均就是非退化得基本可行解,而不就是可行解.因此,该问题得所有基本可行解为.此外,因为这些基本可行解都就是非退化得,所以该问题就是非退化得.定理 1 设为(LP)得可行解,则为(LP)得基本可行解得充要条件就是它得非零重量所对应得列向量线性无关。证明 不妨设得前个重量为正重量,即若就是基本可行解,则取正值得变量必定就是基变量,而这些基变量对应得列向量就是基向量.故必定线性相关.反之,若线性无关,则必有。当时,就就是一个基;当时,一定可以从约束矩阵得后个列向量中选出个,不妨设为,使成为一个基.由于就是可行...
