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

《线性规划问题解的基本理论.ppt》由会员分享，可在线阅读，更多相关《线性规划问题解的基本理论.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二、二、线性规划问题线性规划问题 解的概念和性质解的概念和性质一、一、LP问题的各种解问题的各种解 1.可可行行解解：满满足足约约束束条条件件和和非非负负条条件的决策变量的一组取值。件的决策变量的一组取值。2.可行解集可行解集：所有可行解的集合。所有可行解的集合。3.可可行行域域：LP问问题题可可行行解解集集构构成成n维维空间的区域，可以表示为：空间的区域，可以表示为：4.最优解最优解:使目标函数达到最优值的可行解。使目标函数达到最优值的可行解。5.最优值最优值：最优解对应目标函数的取值。：最优解对应目标函数的取值。6.求解求解LP问题问题:求出问题的最优解和最优值。求出问题的最优解和最优值。

2、7.基基本本解解:令令非非基基变变量量等等于于0，从从AXb中中解解出出的的基基变变量量所所得得的的解解称称为为LP关关于于基基B的的基基本本解。解。可行解与基本解的区别？可行解与基本解的区别？基本解基本解 设设AX=b是含是含n个决策变量、个决策变量、m个个约束条件的约束条件的LP的约束方程组，若的约束方程组，若B是是LP问问题的一个基，若令不与题的一个基，若令不与B的列相应的的列相应的n-m个个分量（非基变量）都等于零，所得方程组分量（非基变量）都等于零，所得方程组的解的解X=0,0,0,xn-m+1,xn-m+2,xnT称为称为方程组方程组AX=b关于基关于基B的一个基本解的一个基本解，

3、简称，简称为为LP的基本解的基本解。8.基本可行解基本可行解（对应的基为可行基）：满（对应的基为可行基）：满足非负条件的基本解。足非负条件的基本解。9.退化的基本可行解退化的基本可行解 非零分量个数小于非零分量个数小于m（至少有一个基变（至少有一个基变量取值为量取值为0）。）。10.最优基最优基 该基对应的基本可行解为该基对应的基本可行解为LP的最优解。的最优解。m基本解的个数基本解的个数CCn n基本可行解的非零分量均为正分量基本可行解的非零分量均为正分量个数不超过个数不超过mm结论结论结论结论11.基本最优解基本最优解（对应的基为最优基）：（对应的基为最优基）：使目标函数达到最优值的基本可

4、行解。使目标函数达到最优值的基本可行解。最优解基本最优解2、线性规划问题解的性质定理、线性规划问题解的性质定理：定理定理3-1 线性规划问题的可行解集线性规划问题的可行解集（即可行域）（即可行域）是凸集。是凸集。定理定理3-2 线性规划几何理论基本定理线性规划几何理论基本定理若若 ，则则X是是D的的一一个个顶顶点点的的充充分分必必要要条条件件是是X为为线线性性规规 划的基本可行解。划的基本可行解。定定理理3-3 若若可可行行域域非非空空有有界界，则则线线性性规规划划问问题题的的目目标标函函数数一一定定可可以以在在可可行行域域的的顶顶点点上上达达到最优值。到最优值。定定理理3-4 若若目目标标函

5、函数数在在k个个点点处处达达到到最最优优值值（k2）,则则在在这这些些顶顶点点的的凸凸组组合合上上也也达达到到最优值。最优值。上述上述4个定理的一些有意义的启示：个定理的一些有意义的启示：J LP的的可可行行域域一一定定是是凸凸集集，但但是是凸凸集集不不一一定定成成为为LP的的可可行行域域，而而非非凸凸集集一一定定不会是不会是LP的可行域。的可行域。J线线性性规规划划的的基基本本可可行行解解和和可可行行域域的的顶顶点点是一一对应的是一一对应的 J 在在可可行行域域中中寻寻找找LP的的最最优优解解可可以以转转化化为为只只在在可可行行域域的的顶顶点点中中找找，从从而而把把一一个无限的问题转化为一个有限的问题。个无限的问题转化为一个有限的问题。J 若若已已知知一一个个LP有有两两个个或或两两个个以以上上最最优解，那麽就一定有无穷多个最优解。优解，那麽就一定有无穷多个最优解。