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

第二节 线性规划问题解的概念一、解的情况二、几个重要的解概念线性规划的解有如下几种情况：1、存在有限最优解：唯一最优解；无穷多个最优解 2、无有限最优解（无界解）3、无可行解（可行域空）1、存在有限最优解A）唯一最优解B）无穷多最优解2、无有限最优解（无界解）3、无可行解（可行域为空）Max Max z z=1500=1500 x1 x1+2500 +2500 x2x2 s.t.3 s.t.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 Max z z=1500=1500 x1 x1+2500 +2500 x2x2 s.t.3 s.t.3x1x1+2+2x2x2 65 65 2 2x1x1+x2x2 40 40 3 3x2x2 75 75 x1 ,x2 x1 ,x2 0 02、基、基本解设设B B为为A A中的一个基，令中的一个基，令Ax=bAx=b，中所有的非基，中所有的非基变量（变量（n-mn-m个）为个）为0 0，得出的解，得出的解x x，称为是，称为是B B的的基本解。基本解。x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 b bi i1.3 2 3 2 1 0 01 0 0 65 652.2 1 2 1 0 1 00 1 0 40 403.0 3 0 3 0 0 10 0 1 75 754.P P1 1 P P2 2 P P3 3 P P4 4 P P5 5A=A=（P P1 1，P P2 2，P P3 3，P P4 4，P P5 5）B=B=（P P1 1，P P2 2，P P3 3），基变量（），基变量（x x3 3 x x4 4 x x5 5 ）非基变量（非基变量（x x1 1 x x2 2 ），），B B的基本解是（的基本解是（0 0，0 0，6565，4040，7070）3、基本可行解（1）满足非负的基本解，为基本可行解。（2）可行解满足的条件是：Ax=b和x 0，而基本解必然满足Ax=b，只需满足X 0。4、可行基对应对应于基可行解的基，称于基可行解的基，称为为可行基。可行基。约约束方程束方程组组(1-5)(1-5)具有的基解的数目最多是具有的基解的数目最多是 个，一个，一般基可行解的数目要小于基解的数目。般基可行解的数目要小于基解的数目。当基本解中的非零分量的个数小于m时，该基本解是退化解。解之间的关系基本解针对基（一组基变量非基变量为0唯一基本解可行解符合约束条件，非负。