将A的列向量重排次序成A=(B,N),相应x=(x,x),c=(cB,cN) 基对应的变量x称为基变量,非基对应的变量x称为非基变量 于是f=cBxB+cNxN,Ax=BxB+Nxy=b AU XB=B-b-B- NXN, f=CBB- b+(CN-CBB-NXN 令非基变量x=0,解得基变量xB=Bb,称(xB,x)为基解 基解的所有变量的值都非负,则称为基可行解,此时的基称为可行基 若可行基进一步满足:c-cBB-N≥0,即:cBB-N-cN≤0 则对一切可行解x,必有(x)≥cB1b,此时称基可行解x=(Bb,0)T 为最优解 3.最优解的存在性定理 定理1如果线性规划(1)有可行解,那么一定有基可行解. 定理2如果线性规划(1)有最优解,那么一定存在一个基可行解 是最优解.于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN – cBB-1N)xN 令非基变量 xN = 0, 解得基变量 xB = B−1 b, 称(xB, xN)为基解. 基解的所有变量的值都非负，则称为基可行解，此时的基称为可行基. 若可行基进一步满足: cN – cBB-1N≥0, 即: cBB-1N - cN≤0 则对一切可行解x, 必有f(x) ≥ cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解. 3. 最优解的存在性定理 将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T , c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量. 定理1 如果线性规划(1)有可行解，那么一定有基可行解. 定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解