单纯型法的计算步骤

1、单纯形法的计算步骤由于单纯形的目标函数和约束函数中含有基变量和非基变量,为了设计出方便,有效的计算方法,我们将简化单纯形的表达形式,称其为单纯形表格。比如,下述单纯形:的简化单纯形表格如下(参见表)。这种格式使得我们非常容易识别基变量,我们只要将仅表:简单单纯形表基解  有个的列(和)为基变量。标准最大化线性规划的单纯型法为了设计标准最大化线性规划问题的初始单纯形表,我们首先将它的等价问题改写为:那么标准最大化线性规划问题的初始单纯形表被表示为(参见表):表:标准最大化线性规划的初始单纯形表     其中:,为原问题目标函数

2、的系数,为基变量下标集合,为非基变量下标集合,为基变量,为基变量在原问题目标函数系数,为基变量的解,那么初始基可行解为,为对应初始目标函数值。 我们将解释表中和行的计算方法和经济涵义。由于标准最大化线性规划问题可被看成是利用种资源生产种产品,决策变量在线性规划约束条件中的系数可以被理解为,为了生产一件产品需要消耗原材料的数量;决策变量在目标函数中的系数是一件产品的利润;松弛变量则表示第种原材料的剩余量。基于上述描述,我们引入下面两个概念:生产一件产品的单位边际损失值其中,是对应基变量在目标函数中的系数,显然或表示某件产品的单位利润或等于。乘积项有四种经济解释:如果,代表产品且,代表尚未使用的原

3、材料,表示生产一件产品所消耗原材料的数量,则,表示生产一件产品没有产生边际损失;如果,代表产品且,也代表产品,表示产品与产品的替代关系,表示未了生产一件产品而放弃生产产品所产生的利润损失,所以是生产一件产品而发生的边际损失;如果,代表剩余原材料且,代表剩余原材料,表示剩余原材料与剩余原材料的之间的替代关系,则,表示这种替代不产生边际损失;如果,代表剩余原材料且,代表产品,表示剩余原材料增加一个单位导致产品的产量减少,则是剩余原材料增加一个单位所引起的边际损失;所以,我们将为了生产一件产品的所有边际损失值相加,即,它就是为了生产单位产品而放弃生产其他产品所产生的利润损失之和。如果代表剩余原材料,

4、的经济涵义是种剩余原材料增加了一个单位而引起所有产品产量减少引起的利润损失之和。我们将称为单位边际损失值。生产一件产品的边际收益由于生产一件产品的单位边际损失值是,而生产一件产品获得的单位利润是,那么代表生产单位产品的实际收益。对于利润最大化的线性规划问题,的经济学含义就是产品的边际收益。只有当大于时,生产产品才能够增加收益。如果代表剩余原材料,则,这时,如果大于,这意味着当种剩余原材料增加一个单位反而引起实际收益增加。总之,是否大于作为单纯形法是否继续迭代的判别条件或检验准则。是单纯形中的,它可用于单纯形是否继续迭代的准则。按当前计划生产的利润单纯形迭代是从初始表开始,通过选择主元素,进行高

5、斯变换,产生新的单纯形表。所以我们将单纯形法的计算步骤总结如下:第一步:转换标准最大化线性规划问题为标准格式对标准最大化线性规划问题引进松弛变量,消除小于等于不等式约束,构造初始单纯形表,并以松弛变量为初始基变量,以决策变量为初始非基变量。第二步:计算单纯形表的和行利用公式和,我们分别计算单纯形表中和行的数值。并利用,的符号判断是否继续进行迭代。如果对所有都有:,则当前单纯形表对应的基可行解就是标准最大化线性规划问题的最优解。第三步:确定换入变量根据,来决定换入变量,我们的目标是选择对目标函数(利润)贡献最大的那个边际收益,即确定换入变量的准则为:下标所对应的变量就是换入变量。第四步: 确定换

6、出变量根据换入变量,所在的列,计算换出比例:,由于变量,的非负符号限制,换出变量的选择规则为:或者:选择,以,表示换出变量,那么称变量与变量的交换系数为迭代的主元素。第五步:构造一个新的单纯形表以主元素进行迭代,把所对应的列变换为:,在列中,用换入变量替代换出变量,在列中,用替代,得到一个新的单纯形表。回到第二步计算新单纯形表中和行的数值,如果,那么当前基可行解就是最优解,否则继续进行迭代。我们用例来说明单纯形法的计算步骤。第一步:对例的约束条件引进松弛变量,那么例的标准格式为:然后,根据式构造例初始单纯形表(参见表):表: 例初始单纯形表   第二步:计算和行如

7、下:由于基变量下标集为:,非基变量下标集为:,对于任意,有,所以,对于非基变量的计算如下:同样原理,对于,。对于基变量的的计算如下:同理,。根据,行的各列计算结果参见表的行。第三步:确定换入变量: 由于选择换入变量的标准是,根据表的行,可以确定为换入变量的下标,而为本次迭代的换入变量。第四步:确定换出变量根据换入变量所在的列,计算换出比例:,即:由于它们的最小值为,所以为换出变量的下标,同时变量被确定为换出变量。第五步:构造一个新的单纯形表以为主元素对所在列进行高斯变换:根据表,换出变量与非基变量的关系为:,将其两端同时除以后,则有:考虑下面二个方程: (表的第3行) (表的第4行)希望消去变

8、量,所以:再考虑下面二个方程: (表的第3行) (表的第5行) 为了消去变量,有:更新基变量下标集:和非基变量下标集:,再将变量用替换,用替换,就获得一张新单纯形表(参见表)。若令所有非基变量等于,即:,基变量就分别为:,及,它们共同组成了一个基可行解,最后根据式,目标函数。表: 例第二张单纯形表 对表重复单纯形算法第二步第五步。计算表中的和行。从表的行看到,对应非基变量的,需要继续迭代。确定换入变量:由于只有,那么确定换入变量的下标为:,而为换入变量。确定换出变量:根据换入变量所在的列,计算换出比例:,即:,它们的最小值为,对应的下标为,所以被确定为换出变量。构造下一个新的单纯形表

9、:我们首先以为主元素对所在列(表的第五列)进行高斯变换,。然后再更新基变量下标集:和非基变量下标集:,再用变量替换,用替换,就获得一张新单纯形表(参见表)。若令所有非基变量等于,即:,基变量就分别为:,及,它们共同组成了一个基可行解,目标函数为。表: 例第三张单纯形表 对表重复单纯形法的第二步第五步。计算表的行和行。从表的行看到,对于所有非基变量,均有:,停止迭代。所以表的基可行解是例的最优解。利用单纯形法求解最小化问题利用单纯形法求解最小化线性规划问题的方法有两种,我们将通过例来说明它们的应用。 例 考虑下述最小化线性规划问题:方法一如果点是例的最优解,则一定是问题的可行域中使得目

10、标函数:达到最小值的可行解。这等价于是问题的可行域中使得函数达到最大值的可行解。所以为了求问题的最优解,我们只需要求解下述线性规划问题:在对问题引进松弛变量之后,我们可获得其初始单纯形表(参见表):表: 例初始单纯形表-方法一 选择非基变量为换入变量,换出比例说明为换出变量,迭代后的单纯形(表参见表)为:表: 例最优单纯形表-方法一 因为非基变量对应的和都小于,所以表是例的最优单纯形表。那么,问题的最优解为:,。而问题的最优解为:,。或者将和代入问题的目标函数,有:总而言之,对于最小化线性规划问题,可对它的目标函数成,然后按最大化线性规划问题进行求解。方法二我们对求解最大化

11、线性规划问题的单纯形法略作修改,就可获得求解最小化线性规划问题的单纯形法。修改第二步:计算单纯形表的和行,选择,中绝对值最大的非基变量作为换入变量,如果所有,对应单纯形表上的基可行解就是最小化线性规划问题的最优解。这是因为增加非基变量的值只能能够使目标函数值增大。在对问题直接引进松弛变量之后,我们可获得其初始单纯形表(参见表):表: 例初始单纯形表-方法二 因为对应于非基变量的检验数为,选择为换入变量,换出比例说明为换出变量,迭代后的单纯形表参见表:表: 例最优单纯形表-方法二 因为非基变量对应的检验数和都大于,所以表是例的最优单纯形表。那么,问题的最优解为:,。多重最优解

12、我们将说明如何利用单纯形法确定一个线性规划问题是否存在多重最优解。我们在节中利用图解法说明当电视机生产问题的目标函数为时的线性规划具有多重最优解。例 重新考虑电视机生产的线性规划问题:对问题引进松弛变量,和之后,我们获得初始单纯形(参见表)表: 例初始单纯形表   因为在检验行中,具有最大值,所以选择非基变量为换入变量,比例值表明为换出变量,进行迭代后,获得一新单纯形表(参见表):表: 例最优单纯形表一   因为对应于非基变量和的检验数和均不大于,表是例的最优单纯形表,最优解为:,。然而,在最优单纯形表中,非基变量的检验数等于,如果选

13、择为换入变量,对应的比例值为,则为换出变量,迭代后的单纯形表(参见表)为:表: 例最优单纯形表二   因为对应于非基变量和的检验数和均不大于,表是例的另一个最优单纯形表,最优解为:,。由于基可行解对应可行域的一个顶点,那么我们可以说明连接上述两个最优顶点线段上的所有点都是例的最优解。为此,我们设:最优顶点: 最优顶点:那么,对于任意,也都是例的最优解。比如,选择,我们获得一最优解,。无界解我们在节中讨论了判断标准最大化线性规划问题是无界的条件,即:对于可行解,如果存在某个使,并且对任意,都有。在本节中,我们将讨论如何利用单纯形来判断线性规划问题是无界的。例考虑下述线性规划问题:对问题引进松弛变量和后,获其初始单纯形表(参见):表: 例初始单纯形表  因为对应非基变量的检验数中绝对值最大的为,选择为换入变量。比例值表明为换出变量。迭代后的新单纯形表(参见表)为:表: 例的第二张单纯形表  选择非基变量作为换入变量,比例值说明为换出变量。迭代后的新单纯形表(参见表)为:表: 例的第三张单纯形表  选择非基变量作为换入变量,保持其他非基变量,和为,基变量,与的关系为：将它们代入问题的目标函数中,则有：当的取值不断增大时,比如,目标值也不断