北京交通大学经济管理学院提纲schasEtonounanics and Managoment单纯形法的矩阵描述对偶问题的提出北京交通大学
提 纲 • 单纯形法的矩阵描述 • 对偶问题的提出
北京交通大学S2.1单纯形法的矩阵描述经济管理学院School of Eoics andManagomentBojing Jiaotong University2.1典式的矩阵形式对于非标准型的线性规划问题max Z = CXiAX fbs.t.iX301松弛变量标准型为：max z = CXi AX+ X'=bs.t.jXX.3 0北京交通大学
§2.1 单纯形法的矩阵描述 2.1 典式的矩阵形式 对于非标准型的线性规划问题 标准型为： 松弛变量
设B为可行基aeX0CX=Xn-(A,I) =(B, N,I)sXsoC=(CB， Cn， Cs)目标函数：Z = CX =CBXβ+CNXr+CsXs约束条件：eXbAX+X,=(B, N, I) x + ==BXp+NX++IX,=bXs因为B-1存在，故上式可化为Xβ +B-1NX+B-1Xs=B-1b
C=(CB，CN，CS ) （A，I）=(B，N，I ) 设 B 为可行基， 目标函数： Z = CX 约束条件： 因为B-1 存在，故上式可化为 AX+XS =(B, N, I) =BXB+NXN+IXS =b XB +B-1NXN +B-1XS =B-1b =CBXB+CNXN+CSXS
Xβ =B-1b-B-1NX-B-1X.将上式代入目标函数可得Cs=0Z=CBXp+CNX+CsXs= Cβ(B-1b-B-1NXn -B-1Xs)+CNX+CsX=CBB-1b + (Cn-CβB-1M)X+ (-CBB-I)Xs则线性规划模型可表示为：
将上式代入目标函数可得 XB =B- 1b-B- 1N XN -B- 1XS Z=CBXB+CNXN+CSXS =CBB-1b + (CN -CBB-1N)XN + (-CBB-1 )XS = CB (B-1b-B-1NXN -B-1XS）+CNXN+CSXS CS=0 则线性规划模型可表示为：
Z =CrB-1b + (C-CBB-1MX+ (-CβB-I)XsS.t.[Xβ +B-1NX +B-1Xs=B-1bLX 令非基变量X=0，X=0，得到一个基本可行解,aB'boCZ(0) =C,B-1bICCre00单纯形表的相应各部分可表示为：
Z =CBB-1b + (CN -CBB-1N)XN + (-CBB-1 )XS s.t. XB +B-1NXN +B-1XS =B-1b X 0 令非基变量 XN = 0， XS = 0，得到一个基本可 行解， Z（0）=CBB-1b 单纯形表的相应各部分可表示为：