最优化方法图解法和LP基本定理.pptx

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