线性规划问题解的基本理论

《线性规划问题解的基本理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、线性规划问题解的概念和性质一、LP问题的各种解可行解：满足约束条件和非负条件的决策变量的一组取值。可行解集：所有可行解的集合。可行域：LP问题可行解集构成n维空间的区域，可以表示为：4.最优解:使目标函数达到最优值的可行解。5.最优值：最优解对应目标函数的取值。6.求解LP问题:求出问题的最优解和最优值。7.基本解:令非基变量等于0，从AX＝b中解出的基变量所得的解称为LP关于基B的基本解。可行解与基本解的区别？基本解设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，若B是LP问题的一个基，若令不与B的列相

2、应的n-m个分量（非基变量）都等于零，所得方程组的解X=[0,0,…,0,xn-m+1,xn-m+2,…,xn]T称为方程组AX=b关于基B的一个基本解，简称为LP的基本解。8.基本可行解（对应的基为可行基）：满足非负条件的基本解。9.退化的基本可行解非零分量个数小于m（至少有一个基变量取值为0）。10.最优基该基对应的基本可行解为LP的最优解。m基本解的个数≤Cn基本可行解的非零分量均为正分量个数不超过m结论11.基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。最优解基本最优解2、线性规划问题解的性质定

3、理：定理3-1线性规划问题的可行解集（即可行域）是凸集。定理3-2线性规划几何理论基本定理若，则X是D的一个顶点的充分必要条件是X为线性规划的基本可行解。定理3-3若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。定理3-4若目标函数在k个点处达到最优值（k≥2）,则在这些顶点的凸组合上也达到最优值。上述4个定理的一些有意义的启示：LP的可行域一定是凸集，但是凸集不一定成为LP的可行域，而非凸集一定不会是LP的可行域。线性规划的基本可行解和可行域的顶点是一一对应的在可行域中寻找LP的最优解可以转

4、化为只在可行域的顶点中找，从而把一个无限的问题转化为一个有限的问题。若已知一个LP有两个或两个以上最优解，那麽就一定有无穷多个最优解。