单纯形法求解线性规划的步骤.doc

单纯形法求解线性规划的步骤1初始化将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示2最优化测试如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为03确定输入变量从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列4确定分离变量对于主元列的每个正单元格,求出比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出比率最小的列,改行确定了分离变量和主元行5建立下一张表格将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步为求简单在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:1:指定行和列,由用户自行输入每一个元素 SimpleMatrix(introw=0,int col=0);2:直接在主程序中初始化一个二维数组,然后利用构造函数 SimpleMatrix(introw,int col,double *M) 来初始化和处理(本程序所用的实例用的是这种方法)程序中主要的函数以及说明SimpleMatrix();销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数bool Is_objectLine_All_Positive();/判断目标行是否全部为非负数,最后一列不作考虑这个函数用来判断是否已经存在最优解bool Is_MainCol_All_Negative(int col);/判断主元列是否全部为负数或零这个函数用来判断线性规划是否是无解的bool Is_column_all_Positive(int col); /判断col列中是否全部为正(不包括目标行)用来判断线性规划是否存在最优解,因为如果最后一列如果有负数的化,就无解了,算法终止int InColumn();/确定输入变量用来判断主元所在的列int DepartRow(int col);/确定分离变量(寻找主元)用来确定主元所在的行void MainItem_To_1(int row,int col);/将主元所在的行做处理,使主元变为1void SubMatrixLine(int row1,int row2,intcol);/将矩阵的其他行做处理,矩阵的两行相减这个函数是在主元行已经做处理以后调用,目的是是矩阵的其他行主元列的元素变成0.其中row2为主元所在的行,col为主元所在的列,row1为要处理的行void PrintAnswer();/输出矩阵的最优解int GetRows();/返回矩阵的行数int GetCols();/返回矩阵的列数double GetItem(int row,int col);/返回矩阵第row行,第col列的元素源代码/SimpleMatrix.h#ifndef SIMPLEMATRIX_H_#define SIMPLEMATRIX_H_class SimpleMatrixpublic:SimpleMatrix(int row=0,int col=0);SimpleMatrix(int row,int col,double *M);SimpleMatrix(); bool Is_objectLine_All_Positive();/判断目标行是否全部为非负数,最后一列不作考虑 bool Is_MainCol_All_Negative(int col);/判断主元列是否全部为负数或零 bool Is_column_all_Positive(int col);/判断col列中是否全部为正(不包括目标行) int InColumn();/确定输入变量 int DepartRow(int col);/确定分离变量(寻找主元) void MainItem_To_1(int row,int col);/将主元所在的行做处理,使主元变为1 void SubMatrixLine(int row1,int row2,int col);/将矩阵的其他行做处理,矩阵的两行相减 void PrintAnswer();/输出矩阵的最优解 int GetRows();/返回矩阵的行数 int GetCols();/返回矩阵的列数 double GetItem(int row,int col);/返回矩阵第row行,第col列的元素private: int rowLen;/标准矩阵的行数 int colLen;/标准矩阵的列数 double *data;/一个二维数组,指向标准矩阵的数据成员 void init(int rows,int cols);/动态分配一个rows行,cols列的二维数组;#end if/SimpleMatrix.cpp#include #include #include SimpleMatrix.husing namespace std;void SimpleMatrix:init(int rows,int cols)if(rows0&cols0) rowLen=rows;colLen=cols; data = new double *rows; for (int i=0;irows;i+) datai=new doublecols; elsecout矩阵的行.列数不合法endl;SimpleMatrix:SimpleMatrix(int row,int col)init(row,col); for(int i=0;irowLen;i+) cout请输入矩阵中第i+1行的系数endl; for(int j=0;jdataij; SimpleMatrix:SimpleMatrix(int row,int col,double *M)rowLen=row;colLen=col;init(row,col); for (int i=0;irow;i+) for(int j=0;j=0;i-)if (datai!=NULL)delete datai;if (data!=NULL)delete data;bool SimpleMatrix:Is_objectLine_All_Positive() for(int i=0;icolLen-1;i+) if(datarowLen-1i0) return false; return true;bool SimpleMatrix:Is_MainCol_All_Negative(int col) for(int i=0;i0) return false; return true;bool SimpleMatrix:Is_column_all_Positive(int col) for(int i=0;irowLen-1;i+) if(dataicol-10) return false; return true;int SimpleMatrix:InColumn() int count=0; for(int i=0;i=0) count+; else break; double maxItem=fabs(GetItem(rowLen-1,count); int index_col; for(i=0;icolLen-1;i+) double temp=GetItem(rowLen-1,i);if(temp0) if(maxItem=fabs(temp) maxItem=fabs(temp);index_col=i; return index_col;int SimpleMatrix:DepartRow(int col) int index_row; int count=0; for(int i=0;irowLen;i+) if(dataicol0)count+; else break; double minItem=datacountcolLen-1/datacountcol;index_row=count; double temp; for(i=0;i0) temp=dataicolLen-1/temp; if(tempminItem) minItem=temp;index_row=i; return index_row;void SimpleMatrix:MainItem_To_1(int row,int col) double temp=GetItem(row,col); /double temp=datarow-1col-1; for (int i=0;icolLen;i+) datarowi/=temp; void SimpleMatrix:SubMatrixLine(int row1,int row2,int col) double temp=GetItem(row1,col); /double temp=datarow1-1col-1; double*tempLine=new doublecolLen; for(int i=0;icolLen;i+) tempLinei=datarow2i; for(i=0;icolLen;i+) datarow1i=datarow1i-temp*tempLinei; deletetempLine;int SimpleMatrix:GetRows() return rowLen;int SimpleMatrix:GetCols() return colLen;double SimpleMatrix:GetItem(int row,int col) return datarowcol;void SimpleMatrix:PrintAnswer()/先确定单位矩阵中1的位置 for (int i=0;iGetRows();i+) for (int j=0;jGetRows();j+) if(1=dataij) int index_col=j;coutxindex_col+1=dataicolLen-1; coutendl;cout取得最优解,并且最优值为datarowLen-1colLen-1;/单纯形法.cpp#include #include SimpleMatrix.husing namespace std;int main() double M47=5,3,1,1,0,0,9,-5,6,15,0,1,0,15,2,-1,1,0,0,-1,5,-10,-15,-12,0,0,0,; SimpleMatrix Matrix(4,7,(double *)M);if(Matrix.Is_column_all_Positive(5)/判断是否存在最优解 bool p=Matrix.Is_objectLine_All_Positive();/判断主元列是否全部为正,确定是否已经取得最优解 while(!p) int col=Matrix.InColumn();/确定主元所在的行if(Matrix.Is_MainCol_All_Negative(col)/确定线性规划的解是否为无解的 cout线性规划问题是无界的,没有最优解endl;exit(EXIT_FAILURE); else int mainRow=Matrix.DepartRow(col);/确定主元所在的行Matrix.MainItem_To_1(mainRow,col);/将主元所在的行做变换,使主元变成1 int i=0;while(iMatrix.GetRows() if(i!=mainRow) Matrix.SubMatrixLin