线性规划问题解基本理论.pptx

一、LP问题的各种解 1.1.可行解可行解：满足约束条件和非负条件的决策变量的一组取值。2.2.可行解集可行解集：所有可行解的集合。3.3.可行域可行域：LP问题可行解集构成n维空间的区域，可以表示为：第1页/共10页4.最优解最优解:使目标函数达到最优值的可行解。5.最优值最优值：最优解对应目标函数的取值。6.求解求解LPLP问题问题:求出问题的最优解和最优值。7.基本解:令非基变量等于0，从AXb中解出的基变量所得的解称为LP关于基B的基本解。可行解与基本解的区别？可行解与基本解的区别？第2页/共10页 基本解基本解 设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，若B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得方程组的解X=0,0,0,xn-m+1,xn-m+2,xnT称为方程组AX=b关于基B的一个基本解，简称为LP的基本解。8.基本可行解（对应的基为可行基）：满足非负条件的基本解。第3页/共10页9.退化的基本可行解退化的基本可行解 非零分量个数小于非零分量个数小于mm（至少有一个基变量取值为（至少有一个基变量取值为0 0）。）。10.最优基最优基 该基对应的基本可行解为该基对应的基本可行解为LPLP的最优解。的最优解。m基本解的个数基本解的个数C Cn n基本可行解的非零分量均为正分量基本可行解的非零分量均为正分量个数不超过个数不超过mm结论结论结论结论第4页/共10页11.11.基本最优解基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行（对应的基为最优基）：使目标函数达到最优值的基本可行解。解。最优解基本最优解第5页/共10页2、线性规划问题解的性质定理：定理3-1 线性规划问题的可行解集（即可行域）是凸集。定理3-2 线性规划几何理论基本定理若 ，则X是D的一个顶点的充分必要条件是X为线性规 划的基本可行解。第6页/共10页定理3-3 若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。定理3-4 若目标函数在k个点处达到最优值（k2）,则在这些顶点的凸组合上也达到最优值。第7页/共10页上述4个定理的一些有意义的启示：J LP的可行域一定是凸集，但是凸集不一定成为LP的可行域，而非凸集一定不会是LP的可行域。J线性规划的基本可行解和可行域的顶点是一一对应的 第8页/共10页J 在可行域中寻找LP的最优解可以转化为只在可行域的顶点中找，从而把一个无限的问题转化为一个有限的问题。J 若已知一个LP有两个或两个以上最优解，那麽就一定有无穷多个最优解。第9页/共10页感谢您的观看！第10页/共10页