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

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