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

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