《纯形法计算步骤.ppt》由会员分享，可在线阅读，更多相关《纯形法计算步骤.ppt（18页珍藏版）》请在三一办公上搜索。
1、4 单纯形法 的计算步骤,第一步：求出线性规划的初始基可行解，列出初始单纯形表。对于会有明显可行基的线性规划问题LP，直接作出其单纯形表，得到第一个基可行解，单纯形方法是与单纯形表相互对应的。,单纯形法计算步骤：,如果线性规划问题：,单纯形表不是什么新的内容，它是在选定的LP的一个基B之后，LP的等价形式。前m个行就是约束条件的等价形式，就是对应m个约束方程，最后一行就是目标函数的表达式。,单纯形表的特点：,（1）所有基变量对应的列均为单位向量，其中只有一个分量等于1，而其余元素均为零，这个1恰好在这个基变量所在的行上。（2）每个基变量所对应的检验数均等于零。,其他数字都是无关紧要的，第一行是
2、目标函数的系数，左边第一列是基变量所在目标函数中的系数，提供为计算目标函数值作准备。而我们在表中增加一项，就可以紧跟目标函数的当前值。,第二步：若所有检验数,则表中对应的基可行解就是最优解。,第三步：从一个基可行解转换另一个目标函数值更大的基可行解，列出新表。,（1）确定换入基变量,（2）确定换出基变量,（3）确定换入基变量,通过这样换基迭代，一定可以做到以下两点：,（1）从可行基迭代到可行基；（2）使目标函数值不断增加。,单纯形方法中计算时可能出现以下两种情况：,（一般取下标较小的）,（一般取下标较大的）,有可能发生循环的情况，诶了避免循环，人们选择了一种Bland方法，这是有效的避免循环的方法。但同学照样可以使用本教材中所介绍的方法，因为事实上出现循环的情况是不多见的，而个别出现循环的情况都是人为的构造的。,
