最优化方法图解法和LP基本定理PPT课件

.,1,3.LP基本定理,4.单纯形法,1.图解法,5.大M法,第二章线性规划（LP）,6.LP对偶理论（对偶单纯形法）,2.LP标准形,1,7.灵敏度分析及应用,.,2,确定可行域：画约束直线，确定满足约束条件的半平面，所有半平面的交集，即为线性规划的可行域。,确定目标函数的等值线及优化方向：画一条目标函数等值线，并确定目标函数优化的方向。,平行移动目标函数等值线，通过观察得到线性规划的最优解。,图解法的步骤,2,第一节图解法,.,3,例1.用图解法求解线性规划问题,二、例题解析,3,.,4,x1,x2,o,-3X1-4X2=-12(),D,此点是唯一最优解，且最优目标函数值minZ=-7,可行域,4,解：,.,5,例2.,.,6,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),（7.6，2）,D,L0：0=3X1+5.7X2,（3.8，4）,30.6=3X1+5.7X2,蓝色线段上的所有点都是最优解。这种情形为有无穷多最优解，但是最优目标函数值maxZ=30.6是相同的。,可行域,6,例2.,.,7,x1,x2,O,10,20,30,40,10,20,30,40,50,50,可行域是空集无可行解(即无最优解),maxZ=3x1+4x2,7,例3.,.,8,线性规划的图解法启示：,线性规划问题的解有多种情形；,若线性规划的可行域非空，则一定是凸集（区域内任意两点连线都在其中）；,线性规划问题若有最优解,则最优解在可行域的某顶点上达到.,.,9,优缺点,简单、直观、便于初学者理解和记忆；,仅适用于低维情况，通常适用于含两个或三个变量的情况。,9,对于高维情况,怎么求解呢?-单纯形法,.,10,第二节线性规划的标准形,10,线性规划的形式是多种多样的:,目标函数求极大(极小);约束可能有等式约束,也可能有不等式约束;决策变量有的受非负约束,有的是无限制.,.,11,11,一、LP标准形,.,12,二、化LP为标准型的方法,12,.,13,13,例1,2.举例,分析:共有4处不符合标准形的要求.,解:,.,14,14,则相应的标准形为,.,15,15,例2,分析:共有5处不符合标准形的要求.,解:,.,16,16,则相应的标准形为,.,17,第三节LP基本定理,将LP化为标准形后,如何求最优解呢?,有一个定理给出了这个问题的答案,这就是LP基本定理.,.,18,18,LP标准形的矩阵形式,其中,.,19,19,考虑具有标准形的LP:,一、线性规划的基本概念,约束系数矩阵A是mn矩阵,mn，并且r(A)m.,当mn时，基矩阵唯一;当mn时，基矩阵就可能有多个，但数目不超过个。,1.基矩阵:若A中的mm子矩阵B满足r(B)m,即则称B是LP问题的一个基矩阵（简称为基）。,于是A中至少有一个mm子矩阵B，使得：r(B)m。,.,20,约束方程的系数矩阵为：,例1设,易看出r（A）=2，2阶子矩阵有=10个，而基矩阵只有9个，,20,.,21,2.基向量:基矩阵对应的列向量称为基向量，其余列向量称为非基向量.,3.基变量:基向量对应的变量称为基变量，非基向量对应的变量称为非基变量(自由变量)。,例如：对于基B2而言，x1,x4是基变量，x2,x3,x5是非基变量。,x1x4,思考：基变量的选取唯一吗？取法有多少种？,.,22,【注】基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,4.基本解:对于某一确定的基B，令所有的自由变量等于零,求出Ax=b的解，称这组解为LP问题的关于基的基本解。,5.基可行解:非负的基本解称为基可行解（基本可行解）.,【注】基可行解也被定义为“可行的基本解”。,22,注:基变量的选取方式有限,所以基本解的个数也为有限个.,可见：求基可行解要先求基本解,然后看是否非负即可。,另外，基本可行解也一定为有限个。,.,23,二、基本解的求法,.,24,解:约束方程的增广矩阵,x2x4,注意到A是24矩阵,r(A)2.,由于第2列和第4列线性无关,构成一个2阶单位子块，因此可构成一个基矩阵.,表示基变量得如下同解方程组:,