物流优化技术课件 第3章3.2.2 线性规划问题解的基本理论.ppt

二、 线性规划问题  解的概念和性质 一、LP问题的各种解 可行解：满足约束条件和非负条件的决策变量的一组取值。 可行解集：所有可行解的集合。 可行域：LP问题可行解集构成n维空间的区域，可以表示为： 4.最优解:使目标函数达到最优值的可行解。 5.最优值：最优解对应目标函数的取值。 6.求解LP问题:求出问题的最优解和最优值。 7.基本解:令非基变量等于0，从AX＝b中解出的基变量所得的解称为LP关于基B的基本解。 可行解与基本解的区别？ 基本解 设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，若B是LP问题的一个基，若令不与B的列相应的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-1 线性规划问题的可行解集 （即可行域） 是凸集。 定理3-2 线性规划几何理论基本定理 若 ， 则X是D的一个顶点的充分必要条件是X为线性规 划的基本可行解。 定理3-3 若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。 定理3-4 若目标函数在k个点处达到最优值（k≥2）,则在这些顶点的凸组合上也达到最优值。 上述4个定理的一些有意义的启示： LP的可行域一定是凸集，但是凸集不一定成为LP的可行域，而非凸集一定不会是LP的可行域。 线性规划的基本可行解和可行域的顶点是一一对应的 非可行解 可行解 基本可行解 基本解