运筹学讲义 min max ∑x,=a1,l=12 st x=a1,l=1, ∑x=b,j=12,… ∑x=b,/=12…n x120,l=12,…,mj=12…,n > 1.2 引入对偶变量y,,=12,…,m;j=1,2,…n,得对偶问题为 8=>aiy ∑ y ming=-∑a-∑b 1,2,…,m;j=1,2,… v(TP)的一个基本格子集△,由§5.2知,从D4={P1tn∈A中去掉一个多余的行即得(P) 的一个基B,且(TP)关于基B的单纯形表为 b 则(TP)关于基B的对偶解为y=(cB-),检验数为r=(rl,r),其中 t.∈A r=0,r=c-cBBN,即r= c-cBP,tg△ 由预备知识知,将(P)的对偶问题的约束条件v1+v≤c,=1,2,…,m;j=1,2,…,n中的 n∈△的不等式改为等式,即令+v=cn(tn∈△),即得(TP)关于基B的对偶解j=(cB-)运 筹 学 讲 义 2             = = = = = = = −              = = = = = = =       = = = = = = = = x i m j n x b j n st x a i m f c x x i m j n x b j n st x a i m z c x TP i j m i i j j i n j i j m i n j i j i j i j m i i j j i n j i j m i n j i j i j 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , max 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1 1 1 1 1         引入对偶变量 yi ,zj ,i = 1,2,  ,m; j = 1,2,  ,n ，得对偶问题为      +  = = = − −       +  − = = = +     = = =−  =−  = =   st u v c i m j n g a u b v st y z c i m j n g a y b z i j ij n j j j m i i i v z u y i j ij n j j j m i i i j j i i . . , 1,2, , ; 1,2, , min . . , 1,2, , ; 1,2, , min 1 1 0 0 1 1      (TP) 的一个基本格子集  ，由§5.2 知，从 = { |  }  ij ij D P t 中去掉一个多余的行即得 (TP) 的一个基 B ，且 (TP) 关于基 B 的单纯形表为 则 (TP) 关于基 B 的 对偶解为 T T y (cB B ) −1 = ，检验数为 ( , ) T N T B r = r r , 其 中 r r c c B N T B T N T N T B 1 0, − = = − ，即    −   = − ij ij T ij B ij ij c c B P t t r , 0, 1 . 由预备知识知，将 (TP) 的对偶问题的约束条件 ui + v j  cij ,i = 1,2,  ,m; j = 1,2,  ,n 中的 t ij   的不等式改为等式，即令 + = (  ) i j ij ij u v c t ，即得 (TP) 关于基 B 的对偶解 T T y (cB B ) −1 =