文档介绍：运筹学论文
1 / 8
126160031 数基班高文锋
摘要
解线性规划的单纯形法需要先求一个初始可行基。然而，寻求初始可行基不是一份简单的工作。传统的单纯形法在寻求初始可行基时一般需要添人工变量，在约束很多的情形下个松弛变量。经过整理，重新对xj及aj(i=1,2,…,m;j=1,2,…,n)进行编号，则得到下列方程组x1+a1,m+1xm+1+…+a1,nxn=b1
x2+a2,m+1xm+1+…+a2,nxn=b2
⋮
xm+am,m+1xm+1+…+am,nxn=bn
xj≥0,j=1,2,…,n
显然得到一个m×m单位矩阵 B=P1,P2,…,Pn=En
以B作为可行基。将上式每个等式移项得
x1=b1-a1,m+1xm+1-…-a1nxn
x2=b2-a2,m+1xm+1-…-a2nxn
⋮
xm=bm-am,m+1xm+1-…-amnxn
运筹学论文
5 / 8
令xm+1=xm+2=…=xn=0,由上式可得xi=bi(i=1,2,…,m)
又因bi≥0,所以得到一个初始可行解X=(x1,x2,…,xm,0,…,0n-m个)T=(b1,b2,…,bm,0,…,0n-m个)T
方法1,2从教学法的观点来看，它们有一定的意义。至少，利用这些方法可以向人们进一步解释单纯形方法的原理。但它们的适用范围有很大的局限性。

对所有约束条件是“>=”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。①大M法；②两阶段法。
方法3适用范围，但变量过多，使计算复杂化。

. aiTx≥bi,i=1,…,m
xj≥0 j=1,…,n
其中A∈Rm×n,m<n,c和ai,i=1,…,m均有n维列向量，引入m个松弛变量xn+1,…,xn+m我们得到maxcTx
. aiTx-xn+i=bi,i=1,…,m
xj≥0 j=1,…,n+m
变量xj的主元标aj定义如下aj=cj j=1,…,n
运筹学论文
6 / 8
aj=caj-naj-=n+1,…,n+m
这里(xy)表示向量x,y的内积，而|x|表示向量|x|的二范数。
由对偶理论及互补松弛条件立即可将其推广如下：对于标准形式的线性规划mincTx
. Ax=b
x≥0
不失一般性，设b>=0,其主元标定义为aj=-（bTaj）=1,…,n而其最优基的启发性特征刻划仍是：最优基变量对应于较大的主元标，而非基变量则对应于较小的主元标。下面给出文[2]中产生初始可行基的新算法：
画出初始单纯形表，表最左端表示其变量为空，用“*”表示；
计算主元标aj,j=1,…,n+m并将aj按从大到小顺序排列：记为ak1,ak2,…,akn+，则按相应的原始下标从大到小排列；
置l=1;
，转第7步；否则，转第5步；
求最小比bpaikp=minbiaiklaikl>0,i=1,…,，以当前单纯形表中约束矩阵(