资源描述：
《单纯形法求解线性规划的步骤》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、单纯形法求解线性规划的步骤 1> 初始化将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示2> 最优化测试如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为03> 确定输入变量从目标行的前n个单元格中选
2、择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列4> 确定分离变量对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行5> 建立下一张表格将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单在本程序中,需要自
3、己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:1:指定行和列,由用户自行输入每一个元素 SimpleMatrix(introw=0,intcol=0);2:直接在主程序中初始化一个二维数组,然后利用构造函数 SimpleMatrix(introw,intcol,double**M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需
4、要重载析构函数boolIs_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑这个函数用来判断是否已经存在最优解boolIs_MainCol_All_Negative(intcol);//判断主元列是否全部为负数或零这个函数用来判断线性规划是否是无解的boolIs_column_all_Positive(intcol); //判断col列中是否全部为正(不包括目标行)用来判断线性规划是否存在最优解,因为如果最后一列如果有负数的化,就无解了,算法终止intIn
5、Column(); //确定输入变量用来判断主元所在的列intDepartRow(intcol); //确定分离变量(寻找主元)用来确定主元所在的行voidMainItem_To_1(introw,intcol); //将主元所在的行做处理,使主元变为1voidSubMatrixLine(introw1,introw2,intcol);//将矩阵的其他行做处理,矩阵的两行相减这个函数是在主元行已经做处理以后调用,目的是是矩阵的其他行主元列的元素变成0.其中row2为主元所在的行,col为主元所在的列,r
6、ow1为要处理的行voidPrintAnswer(); //输出矩阵的最优解intGetRows(); //返回矩阵的行数intGetCols(); //返回矩阵的列数doubleGetItem(introw,intcol); //返回矩阵第row行,第col列的元素源代码//SimpleMatrix.h#ifndefSIMPLEMATRIX_H_#defineSIMPLEMATRIX_H_classSimpleMatrix{public: SimpleMatrix(introw=0,intc
7、ol=0); SimpleMatrix(introw,intcol,double**M); ~SimpleMatrix(); boolIs_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 boolIs_MainCol_All_Negative(intcol);//判断主元列是否全部为负数或零 boolIs_column_all_Positive(intcol); //判断col列中是否全部为正(不包括目标行) intInColum
8、n(); //确定输入变量 intDepartRow(intcol); //确定分离变量(寻找主元) voidMainItem_To_1(introw,intcol); //将主元所在的行做处理,使主元变为1 voidSubMatrixLine(introw1,introw2,intcol);//将矩阵的其他行做处理,矩阵的两行相减 voidPr
