第十二章 线性规划的基本概念与基本定理

《第十二章 线性规划的基本概念与基本定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十二章线性规划的基本概念和基本定理12.1线性规划的基本概念12.1.1可行解，可行域定义12.1.1：称满足全部约束条件的向量为可行解或可行点。例如：SLP如果满足这些约束，即且，则就是SLP的可行解。定义12.1.2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。例如：上面SLP的可行域为定义12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这时线性规划的约束条件不相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。12.1.2最优解，无界解定义12.1.4：称使目标函数值达到最优值的可行

2、解为线性规划问题的最优解定义12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解X满足，使。那么称该线性规划问题有无界解。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。例12.1.1考虑线性规划问题：图12.1.1解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。267例12.1.2解：此问题的可行域如上图，是一个无界的多边形。但极大化目

3、标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值maxf=1在可行域射线上均可达到。12.1.3.基本可行解定义12.1.6：对于约束条件Ax=b，设A是秩m的mｘn矩阵，用(,j=1~n)表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵B=()若B是非奇异的，即detB0，则称B为一个基或称为一个基矩阵。因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。按定义，A中m个列向量，只要是线性无关的就可以构成一个基。定

4、义12.1.7：若变量对应A中列向量包含在基B中，则称为B的基变量；若变量对应A中的列向量不包含在基B中，则称为B中的非基变量。例12.1.3求满足使解：则的列是线性无关的，即是线性无关，因此是一组基。而，不在这个基中，所以为非基变量。定义12.1.8：设Ax=b,x≥0一个基267，其对应的基变量构成的m维列向量记为这时若全非基变量等0，则Ax=b,得唯一解.记为于是得到方程组Ax=b的一个解，非基变量称之为对应于基B的基本解。这个定义也告诉我们怎样找一个基本解）如：上面例12.1.2中，非基变量。则可得。所以是对应于基B的一个基本解，但由于=-2<0.不能满足约束条件

5、，所以这个基本解不是原问题的可行解。（为什么？）这是因为，按照定义，基本解中的n-m个非基变量必须取0值只有m个基变量取值才可能不等于0。但可以取负值。因此基本解不一定满足SLP的非负要求。定义12.1.9：对应于基B的基本解，若基变量取非负值，即，b>0，则称它为满足约束Ax=b,x>o的基本可行解。对应地称B为可行基，因SLP中具有此约束条件。也通常称为SLP的基本可行解。定义12.1.10：使目标函数达到最优值的基本可行解，称为基本最优值。例12.1.4：（SLP)如例12.1.3，试找一个基本可行解。解：是其一个基矩阵.是一个基。则为基变量。为非基变量。令.得.故

6、是原问题的一个基本可行解，为基可行基。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而基本可行解正分量是个数不超过m.那么满足Ax=b,x0的正分量个数不超过m的可行解。是否一定是基本可行解呢？我们举例说明这个问题。例12.1.5.已知约束条件为：267它有正分量个数等于m(m=2)的可行解。但它不是基本可行解。证明：（反证法）假设可行解x=(3,1,0,0)T面约束的基本可行解。因为基本可行解中非基变量取0值，基变

7、量取非负值。在这个可行解中非零正值，因此不可能是非基变量，只能是基变量。按定义，基变量对应的系数矩阵中的列向量应构成一个基矩阵B.但这里是线性相关的（),这与B是基矩阵矛盾。故知x=(2,1,0,0)T是基可行解。由此例可见，虽然可行解（3，1，0，0）T正分量个数不超过m，但它的正分量对应的列向量线性无关，不能与一基矩阵相联系，所以它不是一个基本可行解。现在我们把例12.1.4中松弛变量去掉，约束变为图12.1.2其可行域如图12.1.2，可行解（3，1，0，0）T用表示为图上点（3，1）。由图可见这不是可行域的顶点。而我们