《高等数学》课程PPT教学课件（章节知识点）8.2 对偶单纯形法

§82对偶单纯形法 、对偶单纯形法的基本思路 设互为对偶的线性规划问题为 (Ⅱ) max z=CX min S=yb AX0,X=0

§8.2 对偶单纯形法 一、对偶单纯形法的基本思路 设互为对偶的线性规划问题为 (Ⅰ) (Ⅱ) max z = CX minS =Yb AX ≤ b YA≥C X ≥0 Y ≥0 引进松弛变量Xs , 将(Ⅰ) 化为标准形式 (Ⅲ) minz′= - CX AX+ Xs = b X ≥0, Xs ≥0    st    st    st

若B为问题皿的一个基,约束方程组的系数矩阵可写 成分块形式(BN,则基B的单纯形矩阵为 T(B)=-ICBB(BND-C] - b B(BND B b 0 -(CBBN-CN)-CBB - b B B B b 在T(B)中 B-1b-问题(的基础解中基变量值,也为问题 (Ⅱ)中非基变量对应的检验数的相反数

若B为问题(Ⅲ)的一个基, 约束方程组的系数矩阵可写 成分块形式(BNI), 则基B 的单纯形矩阵为 在T(B)中 B-1b------问题(Ⅲ)的基础解中基变量值,也为问题 (Ⅱ)中非基变量对应的检验数的相反数.         − − − − =        − − − = − − − − − − − − − − I B N B B b C B N C C B C B b B BNI B b C B BNI C C B b T B B N B B B B 1 1 1 1 1 1 1 1 1 1 0 ( ) ( ) [ ( ) ] ( )

CB1-题中非基变量对应的检验数的 相反数,亦为(Ⅱ)的一个基础解. 若基B满足(1)B1b>0, (2)-(CB1N-CN)≤0,-CB1-0 则B为最优基 若B不满足(1)而满足(2,即有CB1NCN≌0 和CB1≥0.此时CB1是问题(Ⅱ)的基础可行解,这 时称B为对偶可行基

CBB-1 ------问题(Ⅲ)中非基变量对应的检验数的 相反数, 亦为(Ⅱ)的一个基础解. 若基 B 满足 (1) B-1b≥0, (2) -(CBB-1N -CN ) ≤0, -CBB-1 ≤0. 则 B 为最优基. 若 B 不满足(1)而满足(2), 即有 CBB-1N-CN ≥0 和 CBB-1 ≥0. 此时 CBB-1 是问题(Ⅱ)的基础可行解, 这 时称 B为对偶可行基

我们可以从对偶可行基出发通过换基迭代,在保 持对偶基础解可行的前提下,逐步使对偶可行基满足 条件(1)即B1b≌0,从而求得原始问题(I)的最优解

我们可以从对偶可行基出发通过换基迭代, 在保 持对偶基础解可行的前提下, 逐步使对偶可行基满足 条件(1)即 B-1b≥0, 从而求得原始问题(Ⅰ)的最优解

对偶单纯形法的计算步骤 第一步将给定的线性规划问题化为标准形式,再 作出一个对偶可行基B对应的单纯形矩阵. 第二步判别.若基变量值全部非负,B就是最优 基.若基变量值有负数,但其中某负数对应的行没有负 数,则问题无可行解;若基变量有负数,且所有负数对 应的行都有负数,则要换基迭代

二、对偶单纯形法的计算步骤 第一步 将给定的线性规划问题化为标准形式,再 作出一个对偶可行基 B 对应的单纯形矩阵. 第二步 判别. 若基变量值全部非负，B 就是最优 基. 若基变量值有负数, 但其中某负数对应的行没有负 数, 则问题无可行解；若基变量有负数, 且所有负数对 应的行都有负数, 则要换基迭代

第三步换基迭代.以最上面基变量负值对应行中 所有负数分别去除检验数,其中最小商对应的除数就 是主元素,用行初等变换将主元素所在列其他元素化 为零,将主元素化为1,得新基对应的单纯形矩阵 重复第二步、第三步,一定能得最优解或判定问 题无最优解

第三步 换基迭代. 以最上面基变量负值对应行中 所有负数分别去除检验数, 其中最小商对应的除数就 是主元素, 用行初等变换将主元素所在列其他元素化 为零, 将主元素化为1，得新基对应的单纯形矩阵. 重复第二步、第三步, 一定能得最优解或判定问 题无最优解

例1解线性规划问题 maxz=-3x1-4x x1+2x2≥5 3x1+x,≥ 6 x1+x2≥4 x≥0(j=1,2)

例1 解线性规划问题         = +  +  +   = − − 0 ( 1,2) 4 3 6 2 5 max 3 4 1 2 1 2 1 2 1 2 x j x x x x x x z x x j s t

解引进松弛变量x3,x2x,将问题标准化为 min z'=3x1+4x2 x,1-2x+ 5 3 3.x s·t +x5 0(j=1,2,…,5) 取基B=(P3,P4,P5)其对应的单纯形矩阵为 3-40000 T(B)2-3-1010-6

解 引进松弛变量 x3 , x4 , x5 .将问题标准化为 取基B = (P3 , P4 , P5 ), 其对应的单纯形矩阵为        = − − + = − − − + = − − − + = −   = + 0 ( 1,2, ,5) 4 3 6 2 5 s t min 3 4 1 2 5 1 2 4 1 2 3 1 2 x j  x x x x x x x x x z x x j ≥               − − − − − − − − − − − = 1 1 0 0 1 4 3 1 0 1 0 6 1 2 1 0 0 5 3 4 0 0 0 0 T(B)

在T(B)中,检验数都非正,但a1=-5<0所以基B 不是可行基,而是对偶可行基 Om(3142}=-4-2=2 取b12=-2为主元素,进行换基迭代,得新基B=(P2P,P5 对应的单纯形矩阵. 10-200-10 5 00 T(B)=5 10 0 7—23-2

在T(B)中, 检验数都非正, 但d1= -5<0. 所以基B 不是可行基, 而是对偶可行基. 取b12= -2为主元素, 进行换基迭代, 得新基B1=(P2 ,P4 ,P5 ) 对应的单纯形矩阵.   1 2 2 min 3 1, 4 2 4 2 b   = − − − − = − − =                   − − − − − − − − − − = 2 3 0 1 2 1 0 2 1 2 7 1 0 2 1 0 2 5 2 5 0 0 2 1 1 2 1 1 0 2 0 0 10 1 T(B )

在T(B1)中检验数都非正,但d2=-72<0 0=min 72272/2b 取b2=-5/2为主元素,进行换基迭代得新基B2=(P2P1P5) 对应单纯形矩阵 00 0-11 01 535 T(B2) 10 5 52-51-5

在 T(B1 )中 检验数都非正, 但d2= －7/2<0 取 b21= －5/2 为主元素,进行换基迭代,得新基B2=(P2 ,P1 ,P5 ). 对应单纯形矩阵 2 1 1 2 5 1 2 1 , 2 2 5 min 1 b   = − − =    − −    = − −                       − − − − − − − − = 5 4 1 5 1 5 2 0 0 5 7 0 5 2 5 1 1 0 5 9 0 5 1 5 3 0 1 5 2 0 11 5 2 5 9 0 0 2 T(B )