单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤
1>初始化
将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m 列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示
2>最优化测试
如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0
3>确定输入变量
从目标行的前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); //将主元所在的行做处理,使主元变为1
void 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 SimpleMatrix
{
public:
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.h"
using namespace std;
void SimpleMatrix::init(int rows,int cols)
{
if(rows>0&&cols>0)
{
rowLen=rows;
colLen=cols;
data = new double *[rows];
for (int i=0;i { data[i]=new double[cols]; } } else cout<<"矩阵的行.列数不合法"< } SimpleMatrix::SimpleMatrix(int row,int col) { init(row,col); for(int i=0;i { cout<<"请输入矩阵中第"< for(int j=0;j cin>>data[i][j]; } } SimpleMatrix::SimpleMatrix(int row,int col,double **M) { rowLen=row; colLen=col; init(row,col); for (int i=0;i for(int j=0;j { data[i][j]=*((double*)M+col*i+j); ; } SimpleMatrix::~SimpleMatrix() { if(colLen*rowLen != 0 ) { for(int i=rowLen-1;i>=0;i--) { if (data[i]!=NULL) delete[] data[i]; } if (data!=NULL) delete[] data; } } bool SimpleMatrix::Is_objectLine_All_Positive() { for(int i=0;i if(data[rowLen-1][i]<0) return false; return true; } bool SimpleMatrix::Is_MainCol_All_Negative(int col) { for(int i=0;i if(data[i][col]>0) return false; return true; } bool SimpleMatrix::Is_column_all_Positive(int col) { for(int i=0;i { if(data[i][col-1]<0) return false; } return true; } int SimpleMatrix::InColumn() { int count=0; for(int i=0;i { int temp=GetItem(rowLen-1,i); if(temp>=0) { } else break; } double maxItem=fabs(GetItem(rowLen-1,count)); int index_col; for(i=0;i { double temp=GetItem(rowLen-1,i); if(temp<0) { 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;i { if(data[i][col]<0) count++; else break; } double minItem=data[count][colLen-1]/data[count][col]; index_row=count; double temp; for(i=0;i { temp=data[i][col]; if(temp>0) { temp=data[i][colLen-1]/temp; if(temp { minItem=temp; index_row=i; } } return index_row; } void SimpleMatrix::MainItem_To_1(int row,int col) { double temp=GetItem(row,col); //double temp=data[row-1][col-1]; for (int i=0;i { data[row][i]/=temp; } } void SimpleMatrix::SubMatrixLine(int row1,int row2,int col) { double temp=GetItem(row1,col); //double temp=data[row1-1][col-1]; double*tempLine=new double[colLen]; for(int i=0;i { tempLine[i]=data[row2][i]; } for(i=0;i { data[row1][i]=data[row1][i]-temp*tempLine[i]; } delete[]tempLine; } int SimpleMatrix::GetRows() { return rowLen; } int SimpleMatrix::GetCols() { return colLen; } double SimpleMatrix::GetItem(int row,int col) { return data[row][col]; } void SimpleMatrix::PrintAnswer() { //先确定单位矩阵中1的位置 for (int i=0;i for (int j=0;j if(1==data[i][j]) { int index_col=j; cout<<"x"< } } cout< cout<<"取得最优解,并且最优值为"< } //单纯形法.cpp #include #include "SimpleMatrix.h" using namespace std; int main() { double M[4][7]={{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<<"线性规划问题是无界的,没有最优解"< exit(EXIT_FAILURE); } else { int mainRow=Matrix.DepartRow(col); //确定主元所在的行 Matrix.MainItem_To_1(mainRow,col); //将主元所在的行做变换,使主元变成1 int i=0; while(i { if(i!=mainRow) { Matrix.SubMatrixLine(i,mainRow,col); //处理矩阵中其他的行,使主元列的元素为0 i++; } else { i++; } }