运筹学线性规划对偶问题.pptx

1;原线性规划问题的矩阵表达式加上松弛变量后为： ;Cj?;; 当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有： （1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 （2）初始单纯形表中基变量Xs=b，迭代后的表中 XB= B-1 b （3）初始单纯形表中约束系数矩阵为 ，迭代后的表中约束系数矩阵为(B-1 左乘) :;（5）当B为最优基时，应有: ; 例1 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为： ;两个问题的最终单纯形表见下页： ;二、原???划与对偶规划问题的变量及解之间的对应关系;三、线性规划的对偶定理;弱对偶定理推论:;2. 最优性（最优解判别定理）;3.强对偶性（对偶定理）;4. 互补松弛性（互补松弛定理）;第14页/共17页;第15页/共17页;第16页/共17页