管理运筹学之线性规划与单纯型法课件

12/16/20221管理运筹学12/13/20221管理运筹学12/16/20222线性规划与单纯型法第二讲12/13/20222线性规划与单纯型法第二讲12/16/20223由实际问题引出数学模形。产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG701201.确定决策变量:设生产A,B分别为x1,x22.确定目标函数:3.确定约束条件:一、LP问题的基本概念12/13/20223由实际问题引出数学模形。产品A产品B资12/16/20224典型的LP问题:一、LP问题的基本概念12/13/20224典型的LP问题:一、LP问题的基本概念12/16/20225用向量符号表示为:用向量和矩阵表示为:一、LP问题的基本概念12/13/20225用向量符号表示为:用向量和矩阵表示为:12/16/202261.基、基向量、基变量、非基变量设A为约束方程组的m×n阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其余的变量称为非基变量。一、LP问题的基本概念12/13/202261.基、基向量、基变量、非基变量设A12/16/202271.基、基向量、基变量、非基变量一、LP问题的基本概念12/13/202271.基、基向量、基变量、非基变量一、12/16/20228满足约束方程(包括非负约束)的所有解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的唯一解，称为基解。2.可行解、基解、基可行解、可行基一、LP问题的基本概念12/13/20228满足约束方程(包括非负约束)的所有解，12/16/20229基解中满足所有变量非负约束的解，称为基可行解。2.可行解、基解、基可行解、可行基与基可行解对应的基称为可行基。一、LP问题的基本概念12/13/20229基解中满足所有变量非负约束的解，称为基12/16/202210概念练习:找出下列LP问题的全部基解。1234512345一、LP问题的基本概念12/13/202210概念练习:找出下列LP问题的全部基12/16/202211组合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319×××××一、LP问题的基本概念12/13/202211组合x1x2x3x4x5z基可行解？12/16/2022121.连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:当α跑遍区间[0,1]时,相应的点T的集合就构成点X与Y之间的连线。

12/13/2022121.连线:二、重要定理与引理在n维12/16/2022132.凸集:一个由n维点所构成的集合K，如果对于K中任意两点X,Y∈K，恒有:则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。

3.凸组合:假定有k个n维Euclid空间的点它们的凸组合是指如下形式的点X:特别，两个点X与Y的凸组合，叫做它们连线上的点。二、重要定理与引理12/13/2022132.凸集:一个由n维点所构成的集12/16/2022144.顶点:设K是凸集，点X∈K；若对K中任何两个不同的点X,Y，以下等式恒不成立:就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。

二、重要定理与引理12/13/2022144.顶点:设K是凸集，点X∈K；12/16/202215定理1.若LP问题的可行域非空,则可行域为凸集定理2.LP问题的基可行解X对应LP问题可行域的顶点定理3.若LP问题有最优解，则一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的标准型，见P2012/13/202215定理1.若LP问题的可行域非空,12/16/202216(1)列初始单纯形表三、单纯形法的计算步骤cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj00012/13/202216(1)列初始单纯形表三、单纯形法的12/16/202217(2)从一个基可行解转换为相邻的另一个基可行解不失一般性，设初始基可行解中的前m个为基变量，设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，则Pj可以成为Pi的线性表达：111a1j.amj三、单纯形法的计算步骤12/13/202217(2)从一个基可行解转换为相邻的另12/16/202218两式相加：三、单纯形法的计算步骤对于一个正数：θ12/13/202218两式相加：三、单纯形法的计算步骤对于12/16/202219除了X(0)，还有其他解吗？111a1j.amj只需：问题：X(1)是基可行解吗？三、单纯形法的计算步骤12/13/202219除了X(0)，还有其他解吗？111a12/16/202220要使X(1)成为基可行解，必须满足：且，至少一个等式成立！显然，对于小于等于0的aij，上述不等式无条件成立；对于大于0的aij，则令：三、单纯形法的计算步骤12/13/202220要使X(1)成为基可行解，必须满足：12/16/202221111a1j.amj111以上的系数矩阵的初等行变换，成为换基变换；如果仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤12/13/202221111a1j.amj111以上的系数12/16/202222将X(0),X(1)分别代入目标函数：(3)最优性判断三、单纯形法的计算步骤12/13/202222将X(0),X(1)分别代入目标函12/16/202223其中：称为检验数，也可表达为：或：三、单纯形法的计算步骤12/13/202223其中：称为检验数，也可表达为：或：三12/16/202224【例】用单纯型法解下列LP问题：用矩阵形式表示为：四、应用举例12/13/202224【例】用单纯型法解下列LP问题：用矩12/16/202225首先构造初始单纯型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、应用举例12/13/202225首先构造初始单纯型表如下：cj21012/16/202226cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001x1四、应用举例12/13/202226cj21000CB基bx1x2x3x12/16/202227cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、应用举例12/13/202227cj21000CB基bx1x2x3x12/16/202228cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代结束四、应用举例12/13/202228cj21000CB基bx1x2x3x12/16/202229cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3x2四、应用举例12/13/202229cj21000CB基bx1x2x3x12/16/202230cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、应用举例12/13/202230cj21000CB基bx1x2x3x12/16/202231化为标准形式：五、单纯型法的进一步讨论—人工变量法(大M法)【例】用单纯型法求解下列LP问题：12/13/202231化为标准形式：五、单纯型法的进一步讨12/16/202232构造初始单纯型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202232构造初始单纯型表：cj-30100-12/16/202233第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202233第1次迭代：cj-30100-M-M12/16/202234第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202234第2次迭代：cj-30100-M-M12/16/202235第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202235第3次迭代：cj-30100-M-M12/16/202236同样题目六、单纯型法的进一步讨论—两阶段法为了保证人工变量为0，可讲目标函数设为：12/13/202236同样题目六、单纯型法的进一步讨论—两12/16/202237构造初始单纯型表：cj00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、单纯型法的进一步讨论—两阶段法12/13/202237构造初始单纯型表：cj00000-112/16/202238第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-1x7660403-31cj-zj6-400034六、单纯型法的进一步讨论—两阶段法12/13/202238第1次迭代：cj00000-1-1C12/16/202239第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj-1-100000即，当X(1)=(1,3,0,0,0,0,0)时，可使目标函数x6+x7取得最小，当x6=x7=0时六、单纯型法的进一步讨论—两阶段法12/13/202239第2次迭代：cj00000-1-1C12/16/202240上述取得最优的单纯型迭代中止的表，等价于一个约束方程组I：而约束方程组I又等价于约束方程组II：故，构造新的初始单纯型表如下：六、单纯型法的进一步讨论—两阶段法12/13/202240上述取得最优的单纯型迭代中止的表，等12/16/202241cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj六、单纯型法的进一步讨论—两阶段法12/13/202241cj-30100CB基bx1x2x312/16/202242cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj第1次迭代：0003/23六、单纯型法的进一步讨论—两阶段法12/13/202242cj-30100CB基bx1x2x312/16/202243cj-30100CB基bx1x2x3x4x50x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj-zj第1次迭代：-9/2-3/4000六、单纯型法的进一步讨论—两阶段法12/13/202243cj-30100CB基bx1x2x312/16/202244七、单纯型法解的讨论补充定理1.如果LP问题有最优解，则基可行解中必有最优解。补充定理2.若X(1),X(2),...,X(K)皆为某LP问题的最优解，那么它们的凸组合也是该LP问题的最优解。补充定理3.若LP问题的可行域有界，而它的基可行解中的所有最优解为:

X(1),X(2),...,X(K),那么它们的所有凸组合包括了该LP问题的所有最优解。(证明略)以下给出三个补充定理，可看作是求解线性规划问题的基本依据。12/13/202244七、单纯型法解的讨论补充定理1.如12/16/202245情况1:唯一最优解只需非基变量的检验数全为负，且基变量中不含人工变量，该解即为唯一最优解。情况2:无解1.当非基变量的检验数全为负，且基变量中含有人工变量，则该LP问题无解。2.可行域为空集。七、单纯型法解的讨论12/13/202245情况1:唯一最优解只需非基变量的检12/16/202246情况3:解无界对于某个正检验数，其对应的Pj有非正的分量，该LP问题的解无界。七、单纯型法解的讨论12/13/202246情况3:解无界对于某个正检验数，其12/16/202247看以下例子:cj1100CB基bx1x2x3x40x34-21100x421-101cj-zj1100请同学们用图解加以验证，加深印象。七、单纯型法解的讨论12/13/202247看以下例子:cj1100CB基bx112/16/202248情况4:多重最优解--无穷最优解存在非基变量的检验数为0，该LP问题存在多重最优解。七、单纯型法解的讨论12/13/202248情况4:多重最优解--无穷最优解存12/16/202249八、算法的有限步中止特别地，指迭代循环的中止。按最小比值θ来确定出基变量时，有时会出现多个相同的最小值--θ，从而有下一轮迭代中，基可行解会出现一个或多个基变量=0解，这种情况称为解的退化。退化解的出现，是因为模型中存在多余的约束。当存在退化解时，就可能出现迭代循环，尽管可能性很小。12/13/202249八、算法的有限步中止特别地，指迭代循12/16/202250本章结束12/13/202250本章结束12/16/202251管理运筹学12/13/20221管理运筹学12/16/202252线性规划与单纯型法第二讲12/13/20222线性规划与单纯型法第二讲12/16/202253由实际问题引出数学模形。产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG701201.确定决策变量:设生产A,B分别为x1,x22.确定目标函数:3.确定约束条件:一、LP问题的基本概念12/13/20223由实际问题引出数学模形。产品A产品B资12/16/202254典型的LP问题:一、LP问题的基本概念12/13/20224典型的LP问题:一、LP问题的基本概念12/16/202255用向量符号表示为:用向量和矩阵表示为:一、LP问题的基本概念12/13/20225用向量符号表示为:用向量和矩阵表示为:12/16/2022561.基、基向量、基变量、非基变量设A为约束方程组的m×n阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其余的变量称为非基变量。一、LP问题的基本概念12/13/202261.基、基向量、基变量、非基变量设A12/16/2022571.基、基向量、基变量、非基变量一、LP问题的基本概念12/13/202271.基、基向量、基变量、非基变量一、12/16/202258满足约束方程(包括非负约束)的所有解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的唯一解，称为基解。2.可行解、基解、基可行解、可行基一、LP问题的基本概念12/13/20228满足约束方程(包括非负约束)的所有解，12/16/202259基解中满足所有变量非负约束的解，称为基可行解。2.可行解、基解、基可行解、可行基与基可行解对应的基称为可行基。一、LP问题的基本概念12/13/20229基解中满足所有变量非负约束的解，称为基12/16/202260概念练习:找出下列LP问题的全部基解。1234512345一、LP问题的基本概念12/13/202210概念练习:找出下列LP问题的全部基12/16/202261组合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319×××××一、LP问题的基本概念12/13/202211组合x1x2x3x4x5z基可行解？12/16/2022621.连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:当α跑遍区间[0,1]时,相应的点T的集合就构成点X与Y之间的连线。

12/13/2022121.连线:二、重要定理与引理在n维12/16/2022632.凸集:一个由n维点所构成的集合K，如果对于K中任意两点X,Y∈K，恒有:则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。

3.凸组合:假定有k个n维Euclid空间的点它们的凸组合是指如下形式的点X:特别，两个点X与Y的凸组合，叫做它们连线上的点。二、重要定理与引理12/13/2022132.凸集:一个由n维点所构成的集12/16/2022644.顶点:设K是凸集，点X∈K；若对K中任何两个不同的点X,Y，以下等式恒不成立:就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。

二、重要定理与引理12/13/2022144.顶点:设K是凸集，点X∈K；12/16/202265定理1.若LP问题的可行域非空,则可行域为凸集定理2.LP问题的基可行解X对应LP问题可行域的顶点定理3.若LP问题有最优解，则一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的标准型，见P2012/13/202215定理1.若LP问题的可行域非空,12/16/202266(1)列初始单纯形表三、单纯形法的计算步骤cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj00012/13/202216(1)列初始单纯形表三、单纯形法的12/16/202267(2)从一个基可行解转换为相邻的另一个基可行解不失一般性，设初始基可行解中的前m个为基变量，设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，则Pj可以成为Pi的线性表达：111a1j.amj三、单纯形法的计算步骤12/13/202217(2)从一个基可行解转换为相邻的另12/16/202268两式相加：三、单纯形法的计算步骤对于一个正数：θ12/13/202218两式相加：三、单纯形法的计算步骤对于12/16/202269除了X(0)，还有其他解吗？111a1j.amj只需：问题：X(1)是基可行解吗？三、单纯形法的计算步骤12/13/202219除了X(0)，还有其他解吗？111a12/16/202270要使X(1)成为基可行解，必须满足：且，至少一个等式成立！显然，对于小于等于0的aij，上述不等式无条件成立；对于大于0的aij，则令：三、单纯形法的计算步骤12/13/202220要使X(1)成为基可行解，必须满足：12/16/202271111a1j.amj111以上的系数矩阵的初等行变换，成为换基变换；如果仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤12/13/202221111a1j.amj111以上的系数12/16/202272将X(0),X(1)分别代入目标函数：(3)最优性判断三、单纯形法的计算步骤12/13/202222将X(0),X(1)分别代入目标函12/16/202273其中：称为检验数，也可表达为：或：三、单纯形法的计算步骤12/13/202223其中：称为检验数，也可表达为：或：三12/16/202274【例】用单纯型法解下列LP问题：用矩阵形式表示为：四、应用举例12/13/202224【例】用单纯型法解下列LP问题：用矩12/16/202275首先构造初始单纯型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、应用举例12/13/202225首先构造初始单纯型表如下：cj21012/16/202276cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001x1四、应用举例12/13/202226cj21000CB基bx1x2x3x12/16/202277cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、应用举例12/13/202227cj21000CB基bx1x2x3x12/16/202278cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代结束四、应用举例12/13/202228cj21000CB基bx1x2x3x12/16/202279cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3x2四、应用举例12/13/202229cj21000CB基bx1x2x3x12/16/202280cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、应用举例12/13/202230cj21000CB基bx1x2x3x12/16/202281化为标准形式：五、单纯型法的进一步讨论—人工变量法(大M法)【例】用单纯型法求解下列LP问题：12/13/202231化为标准形式：五、单纯型法的进一步讨12/16/202282构造初始单纯型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202232构造初始单纯型表：cj-30100-12/16/202283第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202233第1次迭代：cj-30100-M-M12/16/202284第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202234第2次迭代：cj-30100-M-M12/16/202285第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、单纯型法的进一步讨论—人工变量法(大M法)12/13/202235第3次迭代：cj-30100-M-M12/16/202286同样题目六、单纯型法的进一步讨论—两阶段法为了保证人工变量为0，可讲目标函数设为：12/13/202236同样题目六、单纯型法的进一步讨论—两12/16/202287构造初始单纯型表：cj00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、单纯型法的进一步讨论—两阶段法12/13/202237构造初始单纯型表：cj00000-112/16/202288第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-1x7660403-31cj-zj6-400034六、单纯型法的进一步讨论—两阶段法12/13/202238第1次迭代：cj00000-1-1C12/16/202289第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj-1-100000即，当X(1)=(1,3,0,0,0,0,0)时，可使目标函数x6+x7取得最小，当x6=x7=0时六、单纯型法的进一步讨论—两阶段法12/13/202239第2次迭代：cj00000-1-1C12/16/202290上述取得最优的单纯型迭代中止的表，等价于一个约束方程组I：而约束方程组I又等价于约束方程组II：故，构造新的初始单纯型表如下：六、单纯型法的进一步讨论—两阶段法12/13/202240上述取得最优的单纯型迭代中止的表，等12/16/202291cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x