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

单纯形法求解线性规划的步骤单纯形法求解线性规划的步骤单纯形法求解线性规划的步骤V:1.0精细整理，仅供参考单纯形法求解线性规划的步骤日期：20xx年X月单纯形法求解线性规划的步骤

1>

初始化将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示2>

最优化测试如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为03>

确定输入变量从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列4>

确定分离变量对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行5>

建立下一张表格将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步

为求简单在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:1:指定行和列,由用户自行输入每一个元素

SimpleMatrix(introw=0,intcol=0);2:直接在主程序中初始化一个二维数组,然后利用构造函数

SimpleMatrix(introw,intcol,double**M)

来初始化和处理(本程序所用的实例用的是这种方法)

程序中主要的函数以及说明~SimpleMatrix();

销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数boolIs_objectLine_All_Positive();

其中row2为主元所在的行,col为主元所在的列,row1为要处理的行voidPrintAnswer();

数不合法"<<endl;

}

SimpleMatrix::SimpleMatrix(introw,intcol)

{

init(row,col);

for(inti=0;i<rowLen;i++)

{

cout<<"请输入矩阵中第"<<i+1<<"行的系数"<<endl;

for(intj=0;j<colLen;j++)

cin>>data[i][j];

}

}

SimpleMatrix::SimpleMatrix(introw,intcol,double**M)

{

rowLen=row;

colLen=col;

init(row,col);

for(inti=0;i<row;i++)

for(intj=0;j<col;j++)

{

data[i][j]=*((double*)M+col*i+j);

;

}

}

SimpleMatrix::~SimpleMatrix()

{

if(colLen*rowLen!=0)

{

for(inti=rowLen-1;i>=0;i--)

{

if(data[i]!=NULL)

delete[]data[i];

}

if(data!=NULL)

delete[]data;

}

}

boolSimpleMatrix::Is_objectLine_All_Positive()

{

for(inti=0;i<colLen-1;i++)

if(data[rowLen-1][i]<0)

returnfalse;

returntrue;

}

boolSimpleMatrix::Is_MainCol_All_Negative(intcol)

{

for(inti=0;i<rowLen;i++)

if(data[i][col]>0)

returnfalse;

returntrue;

}

boolSimpleMatrix::Is_column_all_Positive(intcol)

{

for(inti=0;i<rowLen-1;i++)

{

if(data[i][col-1]<0)

returnfalse;

}

returntrue;

}

intSimpleMatrix::InColumn()

{

intcount=0;

for(inti=0;i<colLen-1;i++)

{

inttemp=GetItem(rowLen-1,i);

if(temp>=0)

{

count++;

}

else

break;

}

doublemaxItem=fabs(GetItem(rowLen-1,count));

intindex_col;

for(i=0;i<colLen-1;i++)

{

doubletemp=GetItem(rowLen-1,i);

if(temp<0)

{

if(maxItem<=fabs(temp))

{

maxItem=fabs(temp);

index_col=i;

}

}

}

returnindex_col;

}

intSimpleMatrix::DepartRow(intcol)

{

intindex_row;

intcount=0;

for(inti=0;i<rowLen;i++)

{

if(data[i][col]<0)

count++;

else

break;

}

doubleminItem=data[count][colLen-1]/data[count][col];

index_row=count;

doubletemp;

for(i=0;i<rowLen-1;i++)

{

temp=data[i][col];

if(temp>0)

{

temp=data[i][colLen-1]/temp;

if(temp<minItem)

{

minItem=temp;

index_row=i;

}

}

}

returnindex_row;

}

voidSimpleMatrix::MainItem_To_1(introw,intcol)

{

doubletemp=GetItem(row,col);

pp

#include<iostream>

#include""

usingnamespacestd;

intmain()

{

doubleM[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,}};

SimpleMatrixMatrix(4,7,(double**)M);

if(5))

//判断是否存在最优解

{

boolp=();

//判断主元列是否全部为正,确定是否已经取得最优解

while(!p)

{

intcol=();

//确定主元所在的行

if(col))

//确定线性规划的解是否为无解的

{

cout<<"线性规划问题是无界的,没有最优解"<<endl;

exit(EXIT_FAILURE);

}

else

{

intmainRow=(col);

//确定主元所在的行

(mainRow,col);

//将主元所在的行做变换,使主元变成1

inti=0;

while(i<())

{

if(i!=mainRow)

{

(i,mainRow,col);

//处理矩阵中其他的行,使主元列的元素为0

i++;

}

else

{

i++;

}

}

}

for(inti=0;i<();i++)

//输出变换以后的矩阵,判断是否正确处理