单纯形法的基本概念_单纯形法的基本步骤

单纯形法的基本概念由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“单纯形法的基本步骤”。

第2章 单纯形法的基本概念

2.1 可行解

满足约束条件的解X=（x1，x2，...,xn）T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。

2.2 基

设A是约束方程组的m × n 维系数矩阵，其秩为m。B是矩阵A中m × m阶非奇异子矩阵，则称B 是线性规划问题的一个基。这就是说矩阵B是由m个线性独立的列向量组成。为不失一般性，可设

a11a1m Bp1,p2,...,pm

am1amm称pj为基向量，与基向量pj相应的变量xj为基变量，否则称为非基变量，为了进一步讨论线性规划问题的解，下面研究约束方程组中的求解问题。假设该方程组系数矩阵A的秩为m，且m

a11a21 x1+am1a1ma1na12b1a1,m1aaaba22x+...+2mx=2—2,m1x—...—2nx

m1mn2abaam2mam,m1mmmn或

Pxijbj1njm1nPxij

上面这个方程组的一个基是

a11a12aa22B21 am1am2设XB是对应于这个基的基变量

a1ma2mP1,P2,...,Pm amm XB=x1,x2,...,xm

T现若令方程组中的非基变量xm1xm2...xn0，这时变量的个数等于线性方程的个数。用高斯消去法，求出一个解

Xx1,x2,...,xm,0,...,0

该解的非零向量的数目不大于方程个数m，称X为基解。由此可见，有一个基，就可以求出一个基解。

T2.3 基可行解

满足约束方程组中非负条件的基解，称为基可行解。基可行解的非零向量的数目也不大于m，并且都是非负的。

2.4 可行基

对应于基可行解的基，称为可行基。

2.5 凸集

设K是n维欧式线性空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)(1)X(2)K ,(01);则称K为凸集。实心圆, 实心球体, 实心立方体等都是凸集, 圆环不是凸集。从直观上讲, 凸集没有凹入部分, 其内部没有空洞。

2.6 凸组合设X(1),X(2),...,X(k)是n维欧式空间En中的k个点。若存在1,2,...n,且01,i1,2,...,k;1,使

i1（1）（2）+2X+...+kX(k)

X=1Xk则称X为X1,X2,...,Xk的凸组合。

2.7 顶点

设K是凸集，X∈ K;若X 不能用不同的两点X(1)K和X(2)K的线性组合表示为

（1）（2）+（1-）X X ,(0