《金融学院管理运筹学02线性规划与单纯型法》由会员分享，可在线阅读，更多相关《金融学院管理运筹学02线性规划与单纯型法（50页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学8/30/20241线性规划与单纯型法线性规划与单纯型法第二讲8/30/20242廣東金融學院工商管理系由实际问题引出数学模形。1. 确定决策变量: 设生产A, B分别为x1, x22. 确定目标函数: 3. 确定约束条件: 一、LP问题的基本概念8/30/20243廣東金融學院工商管理系典型的LP问题:一、LP问题的基本概念8/30/20244廣東金融學院工商管理系用向量符号表示为:用向量和矩阵表示为:一、LP问题的基本概念8/30/20245廣東金融學院工商管理系1. 基、基向量、基变量、非基变量设A为约束方程组的mn阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP
2、问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其余的变量称为非基变量。一、LP问题的基本概念8/30/20246廣東金融學院工商管理系1. 基、基向量、基变量、非基变量一、LP问题的基本概念8/30/20247廣東金融學院工商管理系满足约束方程(包括非负约束)的所有解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的唯一解，称为基解。2. 可行解、基解、基可行解、可行基一、LP问题的基本概念8/30/20248廣東金融學院工商管理系基解中满足所有变量非负约束的解，称为基可行解。2. 可行解、基解、基可行解、可行基与基可行解对应的基称为可行基。一、LP问题的基本
3、概念8/30/20249廣東金融學院工商管理系概念练习: 找出下列LP问题的全部基解。 一、LP问题的基本概念8/30/202410廣東金融學院工商管理系51045/55-120452175541010-5415/52.51.517.554-32224319一、LP问题的基本概念8/30/202411廣東金融學院工商管理系1. 连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:当跑遍区间0,1时,相应的点T的集合就构成点X与Y之间的连线。 8/30/202412廣東金融學院工商管理系2. 凸集:一个由n 维点所构成的集合K，如果对于K中任意两点X,Y K
4、，恒有: 则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。 3. 凸组合:假定有k个n 维Euclid 空间的点它们的凸组合是指如下形式的点X :特别，两个点X与Y的凸组合，叫做它们连线上的点。二、重要定理与引理8/30/202413廣東金融學院工商管理系4. 顶点:设K是凸集，点X K；若对K中任何两个不同的点X ,Y ，以下等式恒不成立:就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。 二、重要定理与引理8/30/202414廣東金融學院工商管理系定理1. 若 LP问题的可行域非空, 则可行域为凸集定理2. LP问题的基可行解X对应LP问题可行域的顶
5、点定理3. 若LP问题有最优解，则一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的标准型，见P208/30/202415廣東金融學院工商管理系(1) 列初始单纯形表三、单纯形法的计算步骤8/30/202416廣東金融學院工商管理系(2) 从一个基可行解转换为相邻的另一个基可行解不失一般性，设初始基可行解中的前m个为基变量，设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，则Pj可以成为Pi的线性表达：111a1j.amj三、单纯形法的计算步骤8/30/202417廣東金融學院工商管理系两式相加：三、单纯形法的计算步骤对于一个正数：8/30/202418廣東金融學院
6、工商管理系除了X(0)，还有其他解吗？111a1j.amj只需：问题：X(1)是基可行解吗？三、单纯形法的计算步骤8/30/202419廣東金融學院工商管理系要使X(1)成为基可行解，必须满足：且，至少一个等式成立！显然，对于小于等于0的 aij，上述不等式无条件成立；对于大于0的aij，则令：三、单纯形法的计算步骤8/30/202420廣東金融學院工商管理系111a1j.amj111以上的系数矩阵的初等行变换，成为换基变换；如果仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤8/30/202421廣東金融學院工商管理系将X(
7、0), X(1)分别代入目标函数：(3) 最优性判断三、单纯形法的计算步骤8/30/202422廣東金融學院工商管理系其中：称为检验数，也可表达为：或：三、单纯形法的计算步骤8/30/202423廣東金融學院工商管理系【例】用单纯型法解下列LP问题：用矩阵形式表示为：四、应用举例8/30/202424廣東金融學院工商管理系首先构造初始单纯型表如下：20001四、应用举例8/30/202425廣東金融學院工商管理系20001x1四、应用举例8/30/202426廣東金融學院工商管理系20001x1四、应用举例8/30/202427廣東金融學院工商管理系000-1/31/3第一次迭代结束四、应用举
8、例8/30/202428廣東金融學院工商管理系000-1/31/3x2四、应用举例8/30/202429廣東金融學院工商管理系-1/2-1/4000四、应用举例8/30/202430廣東金融學院工商管理系化为标准形式：五、单纯型法的进一步讨论人工变量法(大M法)【例】用单纯型法求解下列LP问题：8/30/202431廣東金融學院工商管理系构造初始单纯型表：-3-2M0004M-M1五、单纯型法的进一步讨论人工变量法(大M法)8/30/202432廣東金融學院工商管理系第1次迭代：-3+6M-4M0003M1+4M五、单纯型法的进一步讨论人工变量法(大M法)8/30/202433廣東金融學院工商
9、管理系第2次迭代：-M-3/2-M+1/20003/23五、单纯型法的进一步讨论人工变量法(大M法)8/30/202434廣東金融學院工商管理系第3次迭代：-M+3/4 -M+1/4-9/2-3/4000五、单纯型法的进一步讨论人工变量法(大M法)8/30/202435廣東金融學院工商管理系同样题目六、单纯型法的进一步讨论两阶段法为了保证人工变量为0，可讲目标函数设为：8/30/202436廣東金融學院工商管理系构造初始单纯型表：-20004-11六、单纯型法的进一步讨论两阶段法8/30/202437廣東金融學院工商管理系第1次迭代：6-400034六、单纯型法的进一步讨论两阶段法8/30/2
10、02438廣東金融學院工商管理系第2次迭代：-1-100000即，当X(1)=(1,3,0,0,0,0,0)时，可使目标函数x6+x7取得最小，当x6=x7=0时六、单纯型法的进一步讨论两阶段法8/30/202439廣東金融學院工商管理系上述取得最优的单纯型迭代中止的表，等价于一个约束方程组I：而约束方程组I又等价于约束方程组II：故，构造新的初始单纯型表如下：六、单纯型法的进一步讨论两阶段法8/30/202440廣東金融學院工商管理系六、单纯型法的进一步讨论两阶段法8/30/202441廣東金融學院工商管理系第1次迭代：0003/23六、单纯型法的进一步讨论两阶段法8/30/202442廣東
11、金融學院工商管理系第1次迭代：-9/2-3/4000六、单纯型法的进一步讨论两阶段法8/30/202443廣東金融學院工商管理系七、单纯型法解的讨论补充定理1. 如果LP问题有最优解，则基可行解中必有最优解。补充定理2. 若X(1), X(2),., X(K)皆为某LP问题的最优解，那么它们的凸组合 也是该LP问题的最优解。补充定理3. 若LP问题的可行域有界，而它的基可行解中的所有最优解为: X(1), X(2),., X(K), 那么它们的所有凸组合包括了该LP问题的所 有最优解。(证明略)以下给出三个补充定理，可看作是求解线性规划问题的基本依据。8/30/202444廣東金融學院工商管理
12、系情况1: 唯一最优解只需非基变量的检验数全为负，且基变量中不含不含人工变量，该解即为唯一最优解。情况2: 无解1. 当非基变量的检验数全为负，且基变量中含有含有人工变量，则该LP问题无解。2. 可行域为空集。七、单纯型法解的讨论8/30/202445廣東金融學院工商管理系情况3: 解无界对于某个正检验数，其对应的Pj有非正的分量，该LP问题的解无界。七、单纯型法解的讨论8/30/202446廣東金融學院工商管理系看以下例子:cj1100CB基bx1x2x3x40x34-21100x421-101cj-zj1100请同学们用图解加以验证，加深印象。七、单纯型法解的讨论8/30/202447廣東金融學院工商管理系情况4: 多重最优解-无穷最优解存在非基变量的检验数为0，该LP问题存在多重最优解。七、单纯型法解的讨论8/30/202448廣東金融學院工商管理系八、算法的有限步中止特别地，指迭代循环的中止。按最小比值来确定出基变量时，有时会出现多个相同的最小值-，从而有下一轮迭代中，基可行解会出现一个或多个基变量=0解，这种情况称为解的退化。退化解的出现，是因为模型中存在多余的约束。当存在退化解时，就可能出现迭代循环，尽管可能性很小。8/30/202449廣東金融學院工商管理系本章结束8/30/202450
