《金融学院管理运筹学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