二、 线性规划问题 解的概念和性质
一、LP问题的各种解
1. 可行解 ：满足约束条件和非负条 件的决策变量的一组取值。
2. 可行解集：所有可行解的集合。
3. 可行域：LP问题可行解集构成n维 空间的区域，可以表示为：
D { X | AX b, X 0}
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的基本解。
一定成为LP的可行域，而非凸集一定 不会是LP的可行域。
线性规划的基本可行解和可行域的顶
点是一一对应的
在可行域中寻找LP的最优解可以转
化为只在可行域的顶点中找，从而把一
个无限的问题转化为一个有限的问题。
若已知一个LP有两个或两个以上最
优解，那麽就一定有无穷多分必要条件是X为线 性规 划的基本可行解。
定理1-3 若可行域非空有界，则线性规划问 题的目标函数一定可以在可行域的顶点上 达到最优值。
定理1-4 若目标函数在k个点处达到最优值 （k≥2）,则在这些顶点的凸组合上也达到 最优值。
上述4个定理的一些有意义的启示：
LP的可行域一定是凸集，但是凸集不
最优解
基本最优解
2、线性规划问题解的性质定理：
定理1-1 线性规划问题的可行解集 n （即可行域） D X Pj x j b, x j 0 是凸集。

j 1

定理1-2 线性规划几何理论基本定理 若
D X 0 Pj x j b, x j ， j 1
8.基本可行解（对应的基为可行基）：满 足非负条件的基本解。
9.退化的基本可行解 非零分量个数小于m（至少有一个基变 量取值为0）。 10.最优基 该基对应的基本可行解为LP的最优解。
结论
m 基本解的个数≤Cn
基本可行解的非零分量均为正分量 个数不超过m
11.基本最优解（对应的基为最优基）： 使目标函数达到最优值的基本可行解。