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

单纯形法求解线性计划步骤
 
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列元素
源代码
//
#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_