. .
. v .
单纯形法求解线性规划的步骤
1> 初始化
将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否那么无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格那么不必满足这一条件),这m列确定了初始的根本可行解的根本变量,而表格中行用根本变量来表示
2> 最优化测试
如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停顿了,该表格代表了一个最优解,它的根本变量的值在最右列中,而剩下的非根本变量都为0
3> 确定输入变量
从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列
4> 确定别离变量
对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了别离变量和主元行
5> 建立下一表格
将主元行的所有单元格除以主元得到新的主元行,包括主元行在的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进展代换,得到新的单纯形表,返回第一步
单纯形法求解线性规划的步骤 来自淘豆网m.daumloan.com转载请标明出处.
