第四节基本公式与退化情形.ppt

Chapter 2 线性规划 Linear Programming 设有线性规划 其中矩阵Am×n 且 r(A)=m, X≥0理解为X大于等于零的向量，即xj≥0( j=1,2…,n)。 2.5.3 计算公式 2.5 单纯形法 Simplex Method 不妨假设A＝(P1, P2, … ,Pn)中前m个列向量构成一个可行基，记为B=(P1, P2 ,… ,Pm)。矩阵A中后n－m列构成的矩阵记为N＝(Pm+1, … ,Pn), 则A可以写成分块矩阵A=(B，N)。对于基B，基变量为XB=(x1, x2 ,… , xm )T, 非基变量为XN=(xm+1, xm+2,…, xn)T。 则X可表示成 , 同理将C 写成分块矩阵 C=(CB，CN)， CB=(C1,C2,…,Cm), CN=(Cm+1Cm+2，…，cn), 则 AX=b 可写成 2.5 单纯形法 Simplex Method 因为r(B)=m(或|B|≠0)所以B -1存在，因此可有 令非基变量XN=0，XB=B—1b，由B是可行基的假设，则得到基本可行解 X=(B－1b，0)T 消去目标函数中的基变量，于是目标函数可写成 2.5 单纯形法 Simplex Method 得到下列五个计算公式： (令XN=0) 2.5 单纯形法 Simplex Method 上述公式可用下面较简单的矩阵表格运算得到，将目标函数写成CBXB+CNXN-Z=0, 约束为BXB+NXN=b 将B化为E(E为m阶单位矩阵), 即求基本可行解。 用B－1左乘表中第二行,得到表1. 16 XB XN b XB E B-1N B-1b CB CN 0 XB XN b XB B N b CB CN 0 表1. 16 2.5 单纯形法 Simplex Method 将第二行左乘－CB后加到第三行,得到 λΝ XB －Z0 XB XN b XB E B-1N B-1b λ＝Cj - Zj 0 CN-CBB－1N －CBB－1b 表1－17 2.5 单纯形法 Simplex Method 将CB化为零, 即求检验数: 对于如下形式的线性规划问题： 引入松弛变量 化为标准形如下： 2.5 单纯形法 Simplex Method 记 则上述标准形式为 由于 对应的系数矩阵为单位阵，故容易确定初始基变量为 ， 得到如下初始单纯形表: X Xs b Xs A E b C 0 0 2.5 单纯形法 Simplex Method X Xs b XB B-1A B-1 B-1b C-CB B-1A - CB B-1 -CB B-1b 而对于一般的基B为 的子矩阵， 由以上讨论可以看出若线性规划标准型中约束方程中的约束系数 阵包含一个单位子矩阵存在现存的初始基，可取该单位阵为初始 基，建立初始单纯形表，对于迭代过程中的任意可行基B 所形成 的单纯形表，初始表中单位子矩阵的位置(即松弛变量对应的系数) 必为 。 2.5 单纯形法 Simplex Method 五个公式的应用 【例6】线性规划 已知可行基 求(1)单纯形乘子π; (2)基可行解及目标值; (3)求λ3; (4)B1是否是最优基,为什么; (5)当可行基为 时求λ1及λ3。 2.5 单纯形法 Simplex Method 【解】(1)因为B1由A中第一列、第二列组成, 故x1、x2为基变量， x3、x4、x5为非基变量,有关矩阵为 CB=(c1, c2)=(1,2) CN=(c3, c4, c5)=(1,0,0) 故单纯形乘子 2.5 单纯形法 Simplex Method (2)基变量的解为 故基本可行解为 目标函数值为 2.5 单纯形法 Simplex Method (3) 求λ3 2.5 单纯形法 Simplex Method (4) 要判断B1是不是最优基, 亦是要求出所有检验数则否满足λj≤0(j=1…,5)。由于x1, x2是基变量, 故 λ1=0,λ2=0, 而 剩下来求λ4,λ5，由λN