第5章 单纯形法

null第五章 单 纯 形 法第五章 单 纯 形 法§1 单纯形法的基本思路和原理 §2 单纯形法的表格形式 §3 求目标函数值最小的线性规划的问题的 单纯形表解法 §4 几种特殊情况§1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 第二章 例1第二章 例1例1. 某工厂在 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？第二章 例1第二章 例1线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 null在加上松弛变量之后我们可得到 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型如下： 目标函数： max 50x1+100x2 约束条件： x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250. xj≥0 （j=1，2）,sj≥0 （j=1，2,3） §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理它的系数矩阵 , 其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变 量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的 基本概念。 基： 已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非 奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。§1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n-m个。 由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个 基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一 的解了，这个解我们称之为线性规划的基本解。 在此例中我们不妨找到了 为A的一个基，令这个基的 非基变量x１，s2为零。这时约束方程就变为基变量的约束方程： §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 x2+s1≤300， x2=400， x2+s3=250. 求解得到此线性规划的一个基本解： x1=0，x2=400，s1=－100，s2=0，s3=－150 由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0， s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是 可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行 解，并把这样的基叫做可行基。 §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解 所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行 基。那么我们能否在求解之前，就找到一个可行基呢？ 也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 那么显然所求得的基本解一定是基本可行解 (?) 这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。 §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 在本例题中我们就找到了一个基是单位矩阵。 在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各 列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行 解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行 基，我们将构造初始可行基，具体做法在以后详细讲述。 线性规划的基本概念线性规划的基本概念线性规划的基矩阵、基变量、非基变量 ==目标函数约束条件行列式≠0 基矩阵右边常数进基变量、离基变量、基变换进基变量、离基变量、基变换目标函数约束条件基矩阵右边常数基变量null进基变量离基变量目标函数约束条件右边常数null目标函数约束条件新的基矩阵右边常数null进基变量离基变量目标函数约束条件基矩阵右边常数null目标函数约束条件新的基矩阵右边常数§1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。 1. 最优性检验的依据——检验数σj 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求 只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可 以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基 变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系 数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变 量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标 函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函 数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知 σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。 §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理2.最优解判别定理 对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 ≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小 于等于零时，可知 是一个小于等于零的数，要使z 的值最大，显然 只有为零。我们把这些xj取为非基 变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。 **对于求目标函数最小值的情况，只需把 ≤0改为 ≥0 §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理三、 基变换 通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进 行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得 到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。 为了换基就要确定入基变量与出基变量。 1. 入基变量的确定 从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取 零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基 变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数 增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题 中σ2=100是检验数中最大的正数，故选x2为入基变量。 §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理2. 出基变量的确定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确 定一个出基变量，也就是确定哪一个基变量变成非基变量呢？ 如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0， 我们也可以从下式： x2 +s1=300， x2+s2=400， x2=250， 求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负 条件，是基本可行解，故s3可以确定为出基变量。 能否在求出基本解以前来确定出基变量呢？ 以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的 基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？ §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。 在本例题中约束方程为 在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除 对应的常量，得  §1 单纯形法的基本思路和原理§1 单纯形法的基本思路和原理 其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 这时目标函数值为 50x1+100x2=50×0+100×250=25000。 显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好 得多。 下面我们再进行检验其最优性，如果不是最优解还要继续进行基变 换，直至找到最优解，或者能够判断出线性规划无最优解为止。§2 单纯形法的表格形式§2 单纯形法的表格形式 在讲解单纯形法的表格形式之前，先从一般 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 模型里推导出检验 数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m 列是单位矩阵）： 以下用 表示基变量，用 表示非基变量。§2 单纯形法的表格形式§2 单纯形法的表格形式 把第i个约束方程移项，就可以用非基变量来表示基变量xi， 把以上的表达式带入目标函数，就有 其中： §2 单纯形法的表格形式§2 单纯形法的表格形式 上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。§2 单纯形法的表格形式§2 单纯形法的表格形式 单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。 max 50x1+100x2+0·s1+0·s2+0·s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s3≥0. 把上面的数据填入如下的单纯形表格§2 单纯形法的表格形式§2 单纯形法的表格形式 按照线性规划模型在表中填入相对应的值，如上表所示； 在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3； 在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0； 在 行中填入cj-zj所得的值，如 ； z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列； 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0; 由于250/1最小，因此确定s3为出基变量； 由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。§2 单纯形法的表格形式§2 单纯形法的表格形式以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。 在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。 求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.§2 单纯形法的表格形式§2 单纯形法的表格形式从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。 从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。 由于检验数都<0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。 实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 例2 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A，B两种 原料，使得购进成本最低？§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法一、大M法 如何用单纯形表的方法求解目标函数值最小的线性规划问题。 目标函数： 约束条件： 加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为 了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问 题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（－1）。 要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它 们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取 正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所 求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零， 我们规定人工变量在目标函数中的系数为－M，这里M为任意大的数。这样 只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。这样 为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到 最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则 该问题无可行解。 §3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 此例的数学模型如下所示： 目标函数： max z=－2x1－3x2－Ma1－Ma2. 约束条件：x1+x2－s1+a1=350， x1－s2+a2=125， 2x1+x2+s3=600， x1，x2，s1，s2，s3，a1，a2≥0. 像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地 加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－M，这个方法叫做大M法，M叫做罚因子。  §3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法下面我们就用大M法来求解此题:§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 从上表中可知检验数都小于零。已求得最优解为： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，其最优值为 f=-z=-(-800)=800。 §3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法 两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。 第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题： 目标函数： 约束条件： §3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。即人工变量之和的最小值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。 第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法§3 求目标函数值最小的线性规划的问题的单纯形表解法 从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。§4 几种特殊情况§4 几种特殊情况 一、无可行解 例1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到： 填入单纯形表计算得：§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况 从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=36≤40. 并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。 像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。 §4 几种特殊情况§4 几种特殊情况二、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。 例2、用单纯形表求解下面线性规划问题。 解：在上述问题的约束条件中加入松驰变量，得标准型如下： §4 几种特殊情况§4 几种特殊情况 填入单纯形表计算得：§4 几种特殊情况§4 几种特殊情况 从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。§4 几种特殊情况§4 几种特殊情况从1次迭代的单纯形表中，得到约束方程： 移项可得：§4 几种特殊情况§4 几种特殊情况 由于M可以是任意大的正数，可知此目标函数值无界。 上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数σij ，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。§4 几种特殊情况§4 几种特殊情况三、无穷多最优解 例3、用单纯形法表求解下面的线性规划问题。 §4 几种特殊情况§4 几种特殊情况 解：此题我们用图解法已求了解，现在用单纯形表来求解。填入单纯形表计算得：§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况 这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：§4 几种特殊情况§4 几种特殊情况 从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1 =（50，250，0，50，0）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为αZ1+（1- α ）Z2，其中0≤α≤1。如图5-1所示：100200300100200300250Z1Z2图5-1§4 几种特殊情况§4 几种特殊情况 在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数 为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？ 不妨设出基变量为xk，则原最优单纯形表可表示如下：§4 几种特殊情况§4 几种特殊情况 通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而xk为非基变量了。我们可得到下表。ck§4 几种特殊情况§4 几种特殊情况 又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。 这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。§4 几种特殊情况§4 几种特殊情况四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。 例4.用单纯形表，求解下列线性规划问题。 解：加上松驰变量s1,s2,s3化为标准形式后， 填入单纯形表计算得：§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况 在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况§4 几种特殊情况 得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。 但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的 某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远 达不到最优解。 下面一个是由E.Beale给出的循环的例子。 例5 目标函数 ：min f =－（3/4）x4+20x5－（1／2）x6+6x7. 约束条件： x1+（1／4）x4－8x5－x6+9x7=0， x2+（1／2）x4－12x5－（1／2）x6+3x7=0， x3+x6=1， x1，x2，x3，x4，x5，x6，x7≥0.§4 几种特殊情况§4 几种特殊情况 这个例题的确存在最优解，但用一般单纯形表法，经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了避免这种现象，我们介绍勃兰特法则。 首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ： （1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。 （2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。 这样就一定能避免出现循环。