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

1、单纯形法求解线性规划的步骤1>初始化将给定的线性规划问题化成标准形式, 并建立一个初始表格 , 它最右边的单元格都是非负的( 否则无解 ), 接下来的 m列组成一个 m*m的单元矩阵 ( 目标行的单元格则不必满足这一条件), 这 m列确定了初始的基本可行解的基本变量, 而表格中行用基本变量来表示2>最优化测试如果目标行的所有单元格都是非负的( 除了最右列中代表目标函数值的那个单元格), 就可以停止了 , 该表格代表了一个最优解 , 它的基本变量的值在最右列中, 而剩下的非基本变量都为03>确定输入变量从目标行的前n 个单元格中选择一个负的单元格( 选择绝对值最大的那个) 该单

2、元格所在的列确定的输入变量及主元列4>确定分离变量对于主元列的每个正单元格, 求出比率 ( 如果主元格的单元格为负或为0, 说明该问题是无解的, 算法终止 ), 找出比率最小的列 , 改行确定了分离变量和主元行5>建立下一张表格将主元行的所有单元格除以主元得到新的主元行 , 包括主元行在内的每一行 , 要减去改行主元列单元格和新主元行的成绩 ( 除主元行为 1 外 , 这一步将主元列的所有单元格变成 0). 把主元列的变量名进行代换 , 得到新的单纯形表回第一步, 返为求简单在本程序中, 需要自己建立标准矩阵( 比如加入松弛变量等工作需要用户自己完成), 程序的输入有两种方式:1:

3、 指定行和列, 由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0);2: 直接在主程序中初始化一个二维数组, 然后利用构造函数*M)来初始化和处理( 本程序所用的实例用的是这种方法)SimpleMatrix(introw,int col,double程序中主要的函数以及说明SimpleMatrix();销毁动态分配的数组. 用于很难预先估计矩阵的行和列, 所以在程序中才了动态的内存分配. 需要重载析构函数bool Is_objectLine_All_Positive();其中 row2 为主元所在的行,col为主元所在的列,row1 为要处理的行void

4、PrintAnswer();数不合法 "<<endl;SimpleMatrix:SimpleMatrix(int row,int col)init(row,col);for(int i=0;i<rowLen;i+)cout<<" 请输入矩阵中第"<<i+1<<"行的系数 "<<endl;for(int j=0;j<colLen;j+)cin>>dataij;SimpleMatrix:SimpleMatrix(int row,int col,double *M)r

5、owLen=row;colLen=col;init(row,col);for (int i=0;i<row;i+)for(int j=0;j<col;j+)dataij=*(double*)M+col*i+j);SimpleMatrix:SimpleMatrix()if(colLen*rowLen != 0 )for(int i=rowLen-1;i>=0;i-)if (datai!=NULL)delete datai;if (data!=NULL)delete data;bool SimpleMatrix:Is_objectLine_All_Positive()for(in

6、t i=0;i<colLen-1;i+)if(datarowLen-1i<0)return false;return true;bool SimpleMatrix:Is_MainCol_All_Negative(int col)for(int i=0;i<rowLen;i+)if(dataicol>0)return false;return true;bool SimpleMatrix:Is_column_all_Positive(int col)for(int i=0;i<rowLen-1;i+)if(dataicol-1<0)return false;r

7、eturn true;int SimpleMatrix:InColumn()int count=0;for(int i=0;i<colLen-1;i+)int temp=GetItem(rowLen-1,i);if(temp>=0)count+;elsebreak;double maxItem=fabs(GetItem(rowLen-1,count);int index_col;for(i=0;i<colLen-1;i+)double temp=GetItem(rowLen-1,i);if(temp<0)if(maxItem<=fabs(temp)maxItem=

8、fabs(temp);index_col=i;return index_col;int SimpleMatrix:DepartRow(int col)int index_row;int count=0;for(int i=0;i<rowLen;i+)if(dataicol<0)count+;elsebreak;double minItem=datacountcolLen-1/datacountcol;index_row=count;double temp;for(i=0;i<rowLen-1;i+)temp=dataicol;if(temp>0)temp=dataico

9、lLen-1/temp;if(temp<minItem)minItem=temp;index_row=i;return index_row;void SimpleMatrix:MainItem_To_1(int row,int col)double temp=GetItem(row,col);pp#include <iostream>#include ""using 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,

10、0,0,;SimpleMatrix Matrix(4,7,(double *)M);if(5)/ 判断是否存在最优解bool p=();/ 判断主元列是否全部为正, 确定是否已经取得最优解while(!p)int col=();/ 确定主元所在的行if(col)/ 确定线性规划的解是否为无解的cout<<" 线性规划问题是无界的, 没有最优解"<<endl;exit(EXIT_FAILURE);elseint mainRow=(col);/ 确定主元所在的行(mainRow,col);/ 将主元所在的行做变换, 使主元变成1int i=0;while(i<()if(i!=mainRow)(i,mainRow,col);/ 处理矩阵中其他的行, 使主元列的元素为0i+;elsei+;for(int i=0;i<();i+)/