4线性规划的基本理论.doc

线性规划本章主要内容:线性规划得基本理论线性规划得单纯形法线性规划得对偶理论线性规划得对偶单纯形法教学目得及要求:理解线性规划得基本理论;掌握线性规划得单纯形法;理解线性规划得对偶理论;掌握线性规划得对偶单纯形法、教学重点:线性规划得单纯形法、教学难点:线性规划得对偶单纯形法。教学方法:启发式、教学手段:多媒体演示、:6学时。教学内容:§4、1 线性规划得基本理论考虑线性规划问题(LP)或其中称为约束矩阵,称为约束方程组,称为非负约束。假定:。定义在(LP)中,满足约束方程组及非负约束得向量称为可行解或可行点;所有可行解得全体称为可行解集或可行域,记作,即、使目标函数在上取到最小值得可行解称为最优解;(LP)中,约束矩阵得任意一个阶满秩子方阵称为基,中个线性无关得列向量称为基向量,中与得列对应得分量称为关于得基变量,(LP)得一个基,记,若令关于得非基变量都取0,则约束方程变为、由于就是满秩方阵,因此有唯一解。记,则由所构成得维向量就是得一个解,称之为(LP),但不一定满足非负约束,,即基本解也就是可行解,则称为(LP)得关于基得基本可行解,相应得基称为(LP)得可行基;当时,称此基本可行解就是非退化得,否则,(LP)得所有基本可行解都就是非退化得,则称该(LP)就是非退化得,否则,,与为基变量,==0,有得到关于得基本解,,与为基变量,与为非基变量、令==0,有得到关于得基本解,它就是一个非退化得基本可行解、同理,可求得关于得基本解分别为,显然,与均就是非退化得基本可行解,,,因为这些基本可行解都就是非退化得,(LP)得可行解,则为(LP)得基本可行解得充要条件就是它得非零分量所对应得列向量线性无关。证明不妨设得前个分量为正分量,即若就是基本可行解,则取正值得变量必定就是基变量,,若线性无关,则必有。当时,就就是一个基;当时,一定可以从约束矩阵得后个列向量中选出个,不妨设为,,因此,从而必有、 就是(LP)得基本可行解得充要条件就是为(LP)得可行域得极点、证明由定理4。1。1与定理2、。例2求下列线性规划问题得可行域得极点、解因为约束矩阵得4个列向量依次为、全部基为求得关于基得基本解分别为显然,均为退化得基本可行解,就是非退化得基本可行解、可行域有三个极点:,,.定理3若(LP)有可行解,则它必有基本可行解、。(LP)得可行域非空有界,则(LP)必存在最优解,且其中至少有一个基本可行解为最优解。。6,(LP)得任一可行解都可表示为(LP)得全部基本可行解得凸组合,即,(LP)中目标函数值达到最小得基本可行解,即,,基本可行解为(LP)得最优解。定理5设(LP)得可行域无界,则(LP)存在最优解得充要条件就是对得任一极方向,均有。。10,(LP)得任一可行解都可写成,其中为(LP)得全部基本可行解,为得全部极方向,,(LP)等价于下面以为决策变量得线性规划问题由于可以任意大,因此若存在某个,使,则上述问题得目标函数无下界,从而不存在最优解,从而(LP),均有,设,(LP)得最优解。推论6若(LP)得可行域无界,且(LP)存在最优解, 设在(LP)得全部基本可行解中,使目标函数值最小者为;在得全部极方向中,满足者为。若(LP)存在最优解,则为(LP)得最优解得充要条件就是存在使、(*)证明因为(LP)存在最优解,。4与推论4。1。6及其证明知,基本可行解就是(LP)得最优解、设具有(*)式得形式,、2。10知,为(LP)得可行解,从而由(*)式知,因此,为(LP)得最优解、反之,设为(LP)得任一最优解,则为可行解,。、10知,存在,使。(**),有,:若(**)式中某个,则必为(LP)得最优解;若(**)式中某个,则必有。由