二维线性规划的图解法.ppt

第一部分 二维线性规划的图解法一、图解法的含义 在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。二、图解法举例三、几个概念1、法向量 正法向量和负法向量。由目标函数系数组成的与等值线垂直的向量，称为正法向量（C=(c1,c2)）。正法向量的反号称为负法向量（-C）。2、等值线 使目标函数取相等值的所有点的集合，称为目标函数的等值线。三、几个概念3、可行解 由约束条件和变量取值限制围成的公共区域中的每一个点都称为线性规划问题的可行解。4、可行域 所有可行解的集合，构成线性规划问题的可行域。四、二维线性规划解的形式1、唯一解2、无穷多个最优解 Min Zx1-2x2 s.t.-x1+x22 x1+2x210 3x1+x215 x1,x20 四、二维线性规划解的形式3、有可行解但无最优解（无界解）Min Zx1-2x2 s.t.-x1+x22 -x1+2x26 x1,x204、无可行解也即问题无解 Min Zx1+2x2 s.t.x1+x21 2x1+x24 x1,x20五、二维线性规划问题解的小结 无可行解 线性规划问题 唯一最优解 有可行解 无穷最优解 无界最优解Return第二部分 线性规划的基本理论一、线性规划解的概念1、解：满足线性规划主约束条件的点，称为线性规划问题的解。2、可行解：满足线性规划所有约束条件的点，称为线性规划问题的可行解。3、最优解：使目标函数得到极值的可行解，称为线性规划问题的最优解。最优解包括：唯一最优解和无穷最优解，有界最优解和无界最优解。二、基、标准基与基变量1、基：约束系数矩阵A中，m个线性无关的列向量，称为m维实空间中的一个基。其中，每个列向量称为基向量，全部基向量构成基矩阵（也可简称为基），剩下的n-m个列向量称为非基向量，所有的非基向量构成非基矩阵。2、标准基：单位矩阵的基矩阵，成为标准基。3、基变量：与基向量对应的变量称为基变量。同理，与非基向量对应的变量称为非基变量。三、基本解、基本可行解与可行基1、基本解 假设B为线性规划问题的基，对约束系数矩阵A、目标函数系数向量C、决策向量X进行分块处理，则有：。因此得：。令非基变量的取值等于零，则得：。一般称：为基B下的基本解。三、基本解、基本可行解与可行基2、基本可行解：符合非负性约束的基本解，称为基本可行解。3、可行基：基本可行解对应的基，称为可行基。四、基本最优解与最优基1、基本最优解：满足目标函数要求的基本解，称为基本最优解。2、最优基：基本最优解对应的基，称为最优基。五、线性规划解之间的关系线性规划解之间的关系：可行解基本解非可行解基本可行解最优解六、退化基本可行解与退化基1、退化基本可行解：基本可行解中存在取零值的基变量，则称该基本可行解为退化的基本可行解。2、退化基：退化的基本可行解对应的基，称为退化基。Return七、线性规划的几何意义1、凸集：集合CEn，从C中任取两点X、Y，当01时，仍有X+（1-）YC，则称C为凸集。凸集：七、线性规划的几何意义1、凸集：不是凸集：七、线性规划的几何意义2、凸组合 设X1，X2，Xk是n维欧氏空间中的 k个点 ，若存在非负数1,2,k,且1+2+k=1，使得 X=1X1+2X2+KXK成立，则称X是X1，X2，Xk的凸组合。如果01,2,k1，则称X是X1，X2，Xk的严格凸组合。七、线性规划的几何意义3、极点 假设集合C是凸集，若C中不存在两个不同的点X1、X2，使得C中的点X可以表示为X1、X2凸组合，则称X是C中的极点。Return八、线性规划的基本定理1、线性规划问题所有可行解组成的集合S=X|AX=b,X0是凸集。2、线性规划问题的可行解X是基本可行解的充要条件是X的正分量对应的约束系数矩阵的列向量是线性无关的。3、X是线性规划问题的基本可行解的充要条件是X为可行域S=X|AX=b,X0 的极点。八、线性规划的基本定理4、如果一个线性规划问题存在可行解，则一定有基本可行解。5、若线性规划问题存在最优解，则一定存在最优基本可行解。6、若线性规划问题可行域有界，则最优解一定在极点上取得到。7、线性规划可行域的极点的个数是有限的。九、线性规划理论的小结1.一般意义上说：（1）如果线性规划问题有可行解，则一定有基本可行解。（2）线性规划问题如果有最优解，则最优解一定可以从基本可行解中找得到。（3）由于基本可行解的个数有限，所以经过有限次迭代，就一定能找到最优解。九、线性规划理论的小结2.从几何意义上说：（1）线性规划问题可行域中的每一个极点都对应着一个基本可行解。（2）由于最优解必定要从基本可行解中寻找，所以所谓求解线性规划问题，实际上就是比较极点处的目标函数值的大小。（3）极点的个数是有限的，那么只要经过有限次寻找就一定能够找到最优解。Return