第一章 线性规划与单纯形法 §4单纯形法 单纯形法的基本思想是：从可行域的一个基 可行解（一个顶点）出发，判断该解是否为最 优解，如果不是最优解就转移到另一个较好的 基可行解，如果目标函数达到最优，则已得到 最优解，否则继续转移到其他较好的基可行解。 由于基可行解（顶点）数目有限，所以在一般 情况下经过有限次迭代后就一定能求出最优解
第一章 线性规划与单纯形法 §4 单纯形法 单纯形法的基本思想是：从可行域的一个基 可行解（一个顶点）出发，判断该解是否为最 优解，如果不是最优解就转移到另一个较好的 基可行解，如果目标函数达到最优，则已得到 最优解，否则继续转移到其他较好的基可行解。 由于基可行解（顶点）数目有限，所以在一般 情况下经过有限次迭代后就一定能求出最优解
4.1确定初始基可行解 对于线性规划问题 maxZ=CX (L) AX=b X≥0 我们首先介绍求初始基可行解的方法。 1.直接观察法 若给定问题标准化后（且b≥0)系数矩阵A中存在m 个线性无关的单位列向量，则以这个单位列向量构成的 单位子矩阵作为初始基B,则XBb=b≥0，其余x;=O是 基可行解
4.1确定初始基可行解 对于线性规划问题 maxZ= CX （L） AX=b X≥0 我们首先介绍求初始基可行解的方法。 1.直接观察法 若给定问题标准化后（且b≥0）系数矩阵A中存在m 个线性无关的单位列向量，则以这m个单位列向量构成的 单位子矩阵作为初始基B，则XB =B -1b =b≥0，其余xj =0是 基可行解
例5求例1问题的初始基可行解 maxZ=6x +4x 2x1+3x≤100 4x,+2x≤120 X1,X2≥0
例5 求例1问题的初始基可行解 maxZ=6x1+4x2 2x1+3x2 ≤100 4x1+2x2 ≤120 x1 ,x2 ≥0
2.大M法（人工变量法） 若给定问题标准化后(b≥0)系数矩阵中不存在个线性无关的单 位列向量，则在某些约束的左端加一个非负变x量（人工变量），使得 变化后的系数矩阵中恰有个线性无关的单位列向量，并且在日标函 数中减去这些人工变量与M的乘积M是相当大正数).对于变化后的 问题，取这个单位列向量构成的单位子矩阵为初始基，该基对应的解 一定是基可行解 例6求下面问题的初始基可行解 maxZ=3xj-X2-X3 X1-2x2+X311 -4x1+X2+2X3≥3 -2X1 +X3=1 X1,X2,X3≥0
2.大M法（人工变量法） 若给定问题标准化后(b≥0)系数矩阵中不存在m个线性无关的单 位列向量,则在某些约束的左端加一个非负变xn+i量(人工变量),使得 变化后的系数矩阵中恰有m个线性无关的单位列向量,并且在目标函 数中减去这些人工变量与M的乘积(M是相当大正数).对于变化后的 问题,取这m个单位列向量构成的单位子矩阵为初始基,该基对应的解 一定是基可行解. 例6 求下面问题的初始基可行解 maxZ=3x1 -x2 - x3 x1 -2x2+ x3≤11 -4x1+ x2 +2x3 ≥3 -2x1 + x3 = 1 x1 ,x2 , x3≥0
显然，对任意形式的线性规划问题都可以用这种增加人工变量的 方法“凑出”一个单位子矩阵作为初始可行基.按这种方法变化得 到的线性规划与原线性规划有如下关系： (1)原问题的任一基可行解都是变化后的问题的基可行解 (2)若变化后问题的最优解中不含有非零的人工变量，则该解就是原 问题的最优解 (3)若变化后问题的最优解中含有非零的人工变量，则原问题无可行 解
显然,对任意形式的线性规划问题都可以用这种增加人工变量的 方法“凑出”一个单位子矩阵作为初始可行基. 按这种方法变化得 到的线性规划与原线性规划有如下关系: ⑴原问题的任一基可行解都是变化后的问题的基可行解. ⑵若变化后问题的最优解中不含有非零的人工变量,则该解就是原 问题的最优解. ⑶若变化后问题的最优解中含有非零的人工变量,则原问题无可行 解
4.2最优性检验 设线性规划(L)的可行基B=(P1,P2,,Pm) iA=(B,N),C=(CB,CN)X=(XB,XN) 用B左乘约束方程组的两端，得 = |-EX:+B-iNXx-B-b 即 EX+B-INXN=B-ib 将X=B-b-B-NX代入目标函数 得 Z=CB-b-CB-NX+CX=CpB-+C-C B-N 记=（Cw-CB=(o+2on其中0=CCBp;j=m+1m+2n 即有Z=CB-b+oXy=CBb+.∑0，X (2) j=m+1
4.2 最优性检验 设线性规划（L）的可行基B=（P1,P2,…,Pm） 记A=（B，N），C=（CB，CN），X=（XB，XN) T 用B-1左乘约束方程组的两端，得 即 将 得 记 即有 （2） EX B NX B b X X B AX B B,N 1 N 1 B N −1 = −1 B = + − = − EX +B − NX =B − b 1 1 N 1 B XB =B −1b-B −1NXN代入目标函数 N 1 N B 1 N N N B 1 B 1 B Z C B b-C B NX C X C B b C -C B N X − = − − + = − + , ,, , j = m +1,m + 2,,n − + + − = = = ，j 1 m 1 m 2 n j j B 1 N N B σ C -C B N σ σ σ 其中σ C -C B P = + = + , = + − − n j m 1 j j 1 N N B 1 B Z C B b σX C B b σx
非基变量x:前面的系数σ，可以用来判断当前对应与基B的基可 行解是否为最优解。故称为变量x对应的检验数。 定理4.1（最优性判定定理)对某基可行解X=B-b,其余x0, 若所有检验数o,=C,CB-P≤0.jm+1m+2m则该解为最优解。 证明对一切可行解X,当所有检验数σ0时 Z=CX=CBb+Σ0XCBb, j=m+1 而基可行解X=Bb,其余x=0对应的目标函数值恰为CB-b, ∴.基可行解XBb,其余xO是最优解，B为最优基
非基变量xj前面的系数σj，可以用来判断当前对应与基B的基可 行解是否为最优解。故称为变量xj对应的检验数。 定理4.1（最优性判定定理） 对某基可行解 XB =B -1b，其余xj=0， 若所有检验数 则该解为最优解。 证明 对一切可行解X，当所有检验数σj≤0时 而基可行解XB =B -1b，其余xj=0对应的目标函数值恰为CBB -1b， ∴基可行解 XB=B-1b，其余xj=0是最优解，B为最优基。 = + + = − 0，j m 1,m 2,,n j 1 j j B σ C -C B P Z CX C B b σx C B b, 1 j j B 1 B n j m 1 − − = = + = +
定理4.2（无界解判定定理)若对某可行基B,存在σk>0,且 BP≤0，则该问题无有限最优解。 证明：设B=(P,P2,,Pm），定义向量Y-(y1y2,…yn), 其中y-aksi=1,2…,m,(ak,a2k,…,anm)Y=B-Pyk-l,其余y-0, 则AY(P,P2,…P)2…nr=R24-B-P=0 CY=(c1C2..c)(y1y2....yn)T=Ck-CpB-Pk=ok, 由Y的定义知Y≥0，所以，如果问题有可行解X,则对任何λ>0， A(X+λY)=AX+入AY=b,即X+λY也是可行解。 故，当入→+∞时，Z=C(X+入Y)=CX+入0k→+∞，证毕。 有了定理4.1，定理4.2后，对于线性规划的任何一个基可行解 只要通过计算检验数，就能够判断该解是否为最优解
定理4.2（无界解判定定理）若对某可行基B，存在σk＞0,且 B-1Pk≤0，则该问题无有限最优解。 证明：设B=（Pj1,Pj2,…,Pjm），定义向量Y=(y1 ,y2 ,…,yn ) T , 其中 yji=-a ik,i=1,2, …,m, (a1k , a2k , …,a mk) T= B-1Pk , yk=1, 其余yj=0, 则AY=（P1,P2,…,Pn)(y1 ,y2 ,…,yn ) T= CY=(c1 ,c2…cn ) (y1 ,y2 ,…,yn ) T =ck-CBB-1Pk=σk＞0, 由Y的定义知Y≥0，所以，如果问题有可行解X，则对任何λ＞0， A（X+λY）=AX+λAY=b，即X+λY也是可行解。 故，当λ→+∞时，Z=C（X+λY）=CX+λσk→ +∞,证毕。 P P a P BB P 0 k 1 k m i 1 k ji ik − = − − = = 有了定理4.1，定理4.2后，对于线性规划的任何一个基可行解， 只要通过计算检验数，就能够判断该解是否为最优解
如例1标准化后变为 maxZ=6x +4x2 2X1+3x2+x3 =100 4x1+2X2 +x4=120 X1X2,X3,X4≥0 取09 为始.k X1=X2=0 为初始基可行解。 .'0=C-CB-1P=6,02=C2-CBP2=4 ∴.该解不是最优解
如 例1 标准化后变为 maxZ=6x1+4x2 2x1+ 3x2 +x3 =100 4x1+ 2x2 +x4 =120 x1 ,x2 ,x3 , x4 ≥0 取（P3,P4）= 为初始基B，则XB=B-1b= ， X1=X2=0 为初始基可行解。 ∵ ∴该解不是最优解。 0 1 1 0 = 120 100 X X 4 3 = =6, − 1 1 σ C -C B P 1 1 B = =4 − 2 2 2 σ C -C B P 1 B
4.3单纯形表 为了便于表达单纯形法计算过程，将可行基对应的(1)、(2) 式的系数增广矩阵，即 E B-iN B-ib -CpB-1b 设计成一种特殊表格，称为单纯形表{a}。其形式如下： C C2 Cm Cmt1 Cn X B-ib Xn Xmti X X a10 0 a1m+1 C2 X2 a20 1 0 a2m+1. 82 Cm amo 0 0 1 amm+l amn G -CgB-1b 0 0 0m+1. On
4.3 单纯形表 为了便于表达单纯形法计算过程，将可行基对应的（1）、（2） 式的系数增广矩阵，即 E B -1N B -1b 0 σN -CBB -1b 设计成一种特殊表格，称为单纯形表｛aij｝。其形式如下： C C1 C2………Cm Cm+1……… Cn CB xB B -1b X1 X2 ……… Xm Xm+1 ……… Xn C1 C2 ﹕ ﹕ Cm X1 X2 ﹕ ﹕ Xm a10 a20 ﹕ ﹕ am0 1 0 ……… 0 a1m+1 ………a1n 0 1 0 a2m+1 ………a2n ﹕ ﹕ ﹕ ﹕ ﹕ ﹕ ﹕ ﹕ ﹕ ﹕ 0 0 1 amm+1 ………amn σ -CBB -1b 0 0 0 σm+1……… σn