布兰德规则(Bland rule)是一种用单纯形法求解线性规划问题时避免循环的方法，它是布兰德(R.G.Bland)于1977年提出的，此方法比字典序法简单得多，在国际上受到很多人的重视，认为是线性规划中一项很好的成果，更有利于在计算机上施行，布兰德规则是：在换基叠代中，选取与下标最小的(即最左边的)正检验数λs相应的非基变数xs为入基变数，其中s=min{j|λj>0}；且当出现两个以上相同的最小比值θi时，选取下标最小的θr相应的基变数xr为出基变数，其中r=min{t|θt=min{bi0/bis|bis>0,1≤i≤m}}。
基本介绍
- 中文名：布兰德规则
- 外文名：Bland rule
- 所属学科：数学
- 所属问题：线性规划
- 提出者：布兰德(R.G.Bland)
基本介绍
布兰德规则是用单纯形法求解线性规划问题时避免循环的方法。在换基叠代中，选取与下标最小的正检验数rs相应的非基变数xs为入基变数，其中
由布兰德(Robert Gary Bland)于1977年提出。此方法比较简单，在国际上受到很多人的重视，有利于在计算机上 施行。
相关介绍
单纯形法(simplex method)是求解线性规划问题的基本方法，此方法是丹齐克(G.B.Dantzig)于1947年提出来的.方法的基本思路是：根据线性规划问题的标準型形式，从可行域中一个基可行解开始，变换到另一个基可行解，并且使目标函式的值逐步增大；当目标函式达到最大值时，就得到了该线性规划问题的最优解，由于线性规划问题仅有有限个基可行解，所以如不出现循环，全部叠代过程可在有限次内终止.此时，或者已得到问题的最优解，或者判定问题无有限最优解。
换基叠代(basis iteration)一般是指求解线性规划问题过程中的叠代技巧，是从一个基可行解到另一个基可行解的叠代。在单纯形表上的换基叠代过程是：
1.确定入基变数。若在
的检验数
中有检验数
，且λs所在列的其他元素中有
，则取
，即T(B)中最左边的一个正检验数λs(或取
)，让其对应的变数xs为入基变数。
2.求主元，确定出基变数。按最小比值原则
3.以brs为主元，进行初等行变换。将入基变数xs所在的列变为单位向量，即
，与此同时，原T(B)中的各元素按以下各式计算，变为相应的新元素：
