《单纯形法的矩阵描述ppt课件》由会员分享，可在线阅读，更多相关《单纯形法的矩阵描述ppt课件（15页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学( Operations Research )Chapter3 对偶理论和灵敏度分析对偶理论和灵敏度分析 3.1 单纯形法的矩阵描述单纯形法的矩阵描述3.2 单纯形法的矩阵计算单纯形法的矩阵计算3.3 对偶问题的提出对偶问题的提出3.4 线性规划的对偶理论线性规划的对偶理论3.5 影子价格影子价格3.6 对偶单纯形法对偶单纯形法3.7 灵敏度分析灵敏度分析本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page 33.1 单纯形法的矩阵描述( Duality Theory )Page 43.1 单纯形法的矩阵描述单纯形法的矩阵描述 这里这里I为为m阶单位阵阶单位阵,b0. 设
2、基变量设基变量XB=XS，系数矩，系数矩阵阵(A,I)=(B,N)，其中其中B、N分别是基变量和非基变分别是基变量和非基变量的系数矩阵量的系数矩阵,则则l 设线性性规划的矩划的矩阵形式形式为标准化准化Page 53.1 单纯形法的矩阵描述单纯形法的矩阵描述Page 63.1 单纯形法的矩阵描述单纯形法的矩阵描述4）非基矩阵）非基矩阵: B-1NPage 73.1 单纯形法的矩阵描述单纯形法的矩阵描述(1)Page 83.1 单纯形法的矩阵描述单纯形法的矩阵描述(2)单纯形表与矩阵表示的关系单纯形表与矩阵表示的关系Page 91 单纯形法的矩阵描述单纯形法的矩阵描述基变量基变量XB非基变量非基变
3、量XNRHS初初始始系数系数矩阵矩阵XSBNIb表检验检验数数CBCN0(-z)=0迭迭代代系数系数矩阵矩阵XBI=B-1BB-1NB-1I= B-1B-1b后后检验检验数数CB-CBB-1BCN-CBB-1N-CBB-1(-z)= -CBB-1bl注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置Page 10CBXBbix1x2x4x3x5icj715000111010 00101021715000x3x4x50000j63806/18/23/1 1100100-1101-2017000-15x3x4x200150j332453/12/1 100-110 01101-201000
4、-7-1x3x1x207150j13259例例1 max z = 7x1 + 15x2 x1 + x2 6 x1 +2x2 8 x2 3 x1, x2 0二、单纯形法矩阵描述二、单纯形法矩阵描述 的应用的应用1 检查计算是否正确检查计算是否正确最优基矩阵最优基矩阵B=(p3,p1,p2)最优基矩阵的逆矩阵最优基矩阵的逆矩阵B-1B-1bb单位矩阵单位矩阵Page 11基矩阵：基矩阵：基矩阵的逆矩阵：基矩阵的逆矩阵：常数项：常数项：检验数：检验数：目标函数值：目标函数值：Page 122 由最终表反推出初始表由最终表反推出初始表 100-110 01101-201000-7-1x3x1x20j1
5、32例例2：设用单纯形法求解某个线性规划问题的最终表如下（目标：设用单纯形法求解某个线性规划问题的最终表如下（目标max， 约束约束 为为形式，形式，x3,x4,x5为松弛变量），试写出原始线性规划模型。为松弛变量），试写出原始线性规划模型。解：解：松弛变量的价值系数为松弛变量的价值系数为0x1、x2的价值系数设为的价值系数设为c1、c2c1 = 7c2 = 15故：故：0 c1 = 70 +2c1c2 = 1 max z = 7x1 + 15x2 x1 + x2 6 x1 +2x2 8 x2 3 x1, x2 0Page 133 验证对某个问题解的性质的假设是否正确验证对某个问题解的性质的假
6、设是否正确解：解：例例3：试验：试验证证X=(0,2,0,0,2)T是否是以下线性规划问题的最优解。是否是以下线性规划问题的最优解。 max z = x1 + 4x2 + 3x3 2x1 + 2x2 + x3 4 x1 + 2x2 + 2x3 6 x1, x2, x3 02）验证是否满足最优性条件）验证是否满足最优性条件1）验证是否是可行解）验证是否是可行解易证，易证，X满足约束，是可行解满足约束，是可行解因为，不满足最优性条件，所以不是最优解因为，不满足最优性条件，所以不是最优解a.确定哪些变量确定哪些变量是基变量，从是基变量，从而确定基矩阵；而确定基矩阵；b.求基矩阵的求基矩阵的逆矩阵；逆矩阵；c.求检验数。求检验数。Page 14小结小结学习要点：学习要点：1. 掌握矩阵的运算；掌握矩阵的运算； 2.理解基矩阵的作用；理解基矩阵的作用； 3.了解矩阵运算与单纯表的关系。了解矩阵运算与单纯表的关系。The end,thank you!
