4线性规划的基本理论

《4线性规划的基本理论》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章线性规划本章主要内容：线性规划的基本理论线性规划的单纯形法线性规划的对偶理论线性规划的对偶单纯形法教学目的及要求：理解线性规划的基本理论；掌握线性规划的单纯形法；理解线性规划的对偶理论；掌握线性规划的对偶单纯形法。教学重点：线性规划的单纯形法．教学难点：线性规划的对偶单纯形法．教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合．教学时间：6学时．教学内容：§4.1线性规划的基本理论考虑线性规划问题(LP)或其中称为约束矩阵，称为约束方程组，称为非负约束．假定：．定义在（LP）中，满足约束方程组及非负约束的向量称为可行解或

2、可行点；所有可行解的全体称为可行解集或可行域，记作，即．使目标函数在上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值．定义在（LP）中，约束矩阵的任意一个阶满秩子方阵称为基，中个线性无关的列向量称为基向量，中与的列对应的分量称为关于的基变量，其余的变量称为关于的非基变量．任取（LP）的一个基，记，若令关于的非基变量都取0，则约束方程变为．由于是满秩方阵，因此有唯一解．记，则由所构成的维向量是的一个解，称之为（LP）的关于的基本解．基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解．若，即基本解也是可行解，

3、则称为（LP）的关于基的基本可行解，相应的基称为（LP）的可行基；当时，称此基本可行解是非退化的，否则，称之为退化的．若一个（LP）的所有基本可行解都是非退化的，则称该（LP）是非退化的，否则，称它是退化的．例1求下列线性规划问题的所有基本可行解．解约束矩阵的4个列向量依次为．全部基为对于，和为基变量，和为非基变量．令==0，有得到关于的基本解，它不是可行解．对于，和为基变量，和为非基变量．令==0，有得到关于的基本解，它是一个非退化的基本可行解．同理，可求得关于的基本解分别为，显然，和均是非退化的基本可行解，而不是可行解．因此，该

4、问题的所有基本可行解为．此外，因为这些基本可行解都是非退化的，所以该问题是非退化的．定理1设为（LP）的可行解，则为（LP）的基本可行解的充要条件是它的非零分量所对应的列向量线性无关．证明不妨设的前个分量为正分量，即若是基本可行解，则取正值的变量必定是基变量，而这些基变量对应的列向量是基向量．故必定线性相关．反之，若线性无关，则必有．当时，就是一个基；当时，一定可以从约束矩阵的后个列向量中选出个，不妨设为，使成为一个基．由于是可行解，因此，从而必有．由此可知是关于的基本可行解．定理2是（LP）的基本可行解的充要条件是为（LP）的可行

5、域的极点．证明由定理4.1.1和定理2.2.2知结论成立．例2求下列线性规划问题的可行域的极点．解因为约束矩阵的4个列向量依次为．全部基为求得关于基的基本解分别为显然，均为退化的基本可行解，是非退化的基本可行解．可行域有三个极点：，，．定理3若（LP）有可行解，则它必有基本可行解．证明由定理2.2.1及定理4.1.2知结论成立．定理4若（LP）的可行域非空有界，则（LP）必存在最优解，且其中至少有一个基本可行解为最优解．证明根据推论2.2.6，（LP）的任一可行解都可表示为（LP）的全部基本可行解的凸组合，即，其中．设是使（LP）中

6、目标函数值达到最小的基本可行解，即，则．这表明，基本可行解为（LP）的最优解．定理5设（LP）的可行域无界，则（LP）存在最优解的充要条件是对的任一极方向，均有．证明根据定理2.2.10，（LP）的任一可行解都可写成，其中为（LP）的全部基本可行解，为的全部极方向，且．于是，（LP）等价于下面以为决策变量的线性规划问题由于可以任意大，因此若存在某个，使，则上述问题的目标函数无下界，从而不存在最优解，从而（LP）不存在最优解．若，均有，设，则．所以基本可行解是（LP）的最优解．推论6若（LP）的可行域无界，且（LP）存在最优解，则至少

7、存在一个基本可行解为最优解．证明由定理4.1.5的证明过程可知结论成立．定理7设在（LP）的全部基本可行解中，使目标函数值最小者为；在的全部极方向中，满足者为．若（LP）存在最优解，则为（LP）的最优解的充要条件是存在使．（*）证明因为（LP）存在最优解，所以由定理4.1.4和推论4.1.6及其证明知，基本可行解是（LP）的最优解．设具有（*）式的形式，则由推论2.2.6和定理2.2.10知，为（LP）的可行解，从而由（*）式知，因此，为（LP）的最优解．反之，设为（LP）的任一最优解，则为可行解，于是由推论2.2.6和定理2.2.

8、10知，存在，使．（**）根据定理1.1.5，有，且由为最优解知．从而由上述两式容易用反证法证明：若（**）式中某个，则必为（LP）的最优解；若（**）式中某个，则必有。由此知，最优解必具有（*）式的形式．（LP）的解有四种可能：（1