运筹学第二章第2节—线性规划问题解的基本概念.ppt

第二节 线性规划问题解的概念•一、解的情况 •二、几个重要的解概念线性规划的解有如下几种情况：1、存在有限最优解：唯一最优解；无穷多个最优解2、无有限最优解（无界解）3、无可行解（可行域空）1、存在有限最优解A）唯一最优解B）无穷多最优解2、无有限最优解（无界解）3、无可行解（可行域为空）Max Max z z= 1500 = 1500 x1 x1 + 2500 + 2500 x2x2s.ts.t. 3. 3x1x1+ 2+ 2x2x2 ≤ 65 ≤ 65 2 2x1x1+ + x2x2≥ ≥40 40 3 3x2x2 ≤ 75 ≤ 75 x1 , x2 x1 , x2 ≥ 0 ≥ 0 判断题？线性规划问题无有限最优解的充要条件是可行域为空？二、几个重要的解概念1.可行解、可行域、最优解、最优值 2.基、基本解 3.基本可行解（基可行解） 4.可行基1、可行解、可行域、最优解、最优值满足约束条件(1-5)、(1-6)式的解X=(x1,x2，…， xn)T，称为线性规划问题的可行解，其中使目标函 数达到最大值的可行解称为最优解。

上图） 由可行解组成的集合就是可行域（满足约束条件不 等式所有点组成的集合），将最优解代目标函数得 到的函数值就是最优值Max z = 1500 x1 + 2500 x2s.t. 3x1+ 2x2 ≤ 65 2x1+ x2 ≤ 40 3x2 ≤ 75 x1 , x2 ≥ 02、基、基本解设B为A中的一个基，令Ax=b，中所有的非基 变量（n-m个）为0，得出的解x，称为是B的 基本解 x1 x2 x3 x4 x5 bi 3 2 1 0 0 65 2 1 0 1 0 40 0 3 0 0 1 75 P1 P2 P3 P4 P5 A=（P1，P2，P3，P4，P5） B=（P1，P2，P3），基变量（ x3 x4 x5 ） 非基变量（ x1 x2 ），B的基本解是（0，0，65 ， 40，70）3、基本可行解（1）满足非负的基本解，为基本可行解 （2）可行解满足的条件是：Ax=b和x ≥0， 而基本解必然满足Ax=b，只需满足X ≥0。

4、可行基对应于基可行解的基，称为可行基 约束方程组(1-5)具有的基解的数目最多是 个， 一 般基可行解的数目要小于基解的数目 当基本解中的非零分量的个数小于m时，该 基 本解是退化解解之间的关系基本解——针对基（一组基变量——非基变量为0——唯一基本解 可行解——符合约束条件，非负。