单纯形法的表格解法

使用表格形式的单纯形方法本文档将通过表格形式介绍单纯形方法的主要概念和步骤，包括初始表格、基变量、非基变量、基可行解、目标函数、最优解、灵敏度分析、稳定性分析、对偶问题和对偶解等方面。

一、初始表格初始表格是单纯形方法的起点，通常由系数矩阵和约束条件组成。

系数矩阵的每一行对应一个约束条件，每一列对应一个变量。

初始表格的最后一列通常为价值列，用于衡量每个基变量的目标函数值。

二、基变量和非基变量在初始表格中，基变量是指位于基可行解中的变量，而非基变量则是指未位于基可行解中的变量。

基变量和非基变量的区分是单纯形方法的关键之一。

三、基可行解基可行解是指满足所有约束条件的解，其中基变量被定义为位于基可行解中的变量。

在单纯形方法中，基可行解是寻找最优解的起点。

四、目标函数目标函数是指要最小化或最大化的函数，它通常由基变量的线性组合构成。

目标函数在单纯形方法中用于衡量每个基可行解的质量，最优解即为目标函数值最小的基可行解。

五、最优解最优解是指满足所有约束条件且目标函数值最小的解。

在单纯形方法中，最优解是寻找基可行解的终点。

六、灵敏度分析灵敏度分析是指分析目标函数值对基变量的敏感程度。

在单纯形方法中，灵敏度分析用于确定最优解的稳定性。

七、稳定性分析稳定性分析是指分析最优解是否稳定。

在单纯形方法中，稳定性分析用于确定最优解是否受基变量值变化的影响。

八、对偶问题对偶问题是指与原问题相对应的问题。

在单纯形方法中，对偶问题用于分析原问题的约束条件和目标函数的性质。

九、对偶解对偶解是指满足对偶问题的解。

在单纯形方法中，对偶解用于确定最优解的性质和约束条件的可行性。

单纯形法求解线性规划的步骤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 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); //将主元所在的行做处理,使主元变为1void 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 <iostream>#include <cmath>#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<rows;i++){data[i]=new double[cols];}}elsecout<<"矩阵的行.列数不合法"<<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>>data[i][j];}}SimpleMatrix::SimpleMatrix(int row,int col,double **M) {rowLen=row;colLen=col;init(row,col);for (int i=0;i<row;i++)for(int j=0;j<col;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)if (data!=NULL)delete[] data;}}bool SimpleMatrix::Is_objectLine_All_Positive(){for(int i=0;i<colLen-1;i++)if(data[rowLen-1][i]<0)return false;return true;}bool SimpleMatrix::Is_MainCol_All_Negative(int col) {for(int i=0;i<rowLen;i++)if(data[i][col]>0)return false;return true;}bool SimpleMatrix::Is_column_all_Positive(int col) {for(int i=0;i<rowLen-1;i++){if(data[i][col-1]<0)return false;}return 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){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<rowLen;i++){if(data[i][col]<0)count++;elsebreak;}double minItem=data[count][colLen-1]/data[count][col]; index_row=count;double temp;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;}}}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<colLen;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<colLen;i++){tempLine[i]=data[row2][i];}for(i=0;i<colLen;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<GetRows();i++)for (int j=0;j<GetRows();j++){if(1==data[i][j]){int index_col=j;cout<<"x"<<index_col+1<<"="<<data[i][colLen-1]<<" ";}}cout<<endl;cout<<"取得最优解,并且最优值为"<<data[rowLen-1][colLen-1];}//单纯形法.cpp#include <iostream>#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<<"线性规划问题是无界的,没有最优解"<<endl;exit(EXIT_FAILURE);}else{int mainRow=Matrix.DepartRow(col); //确定主元所在的行Matrix.MainItem_To_1(mainRow,col); //将主元所在的行做变换,使主元变成1int i=0;while(i<Matrix.GetRows()){if(i!=mainRow){Matrix.SubMatrixLine(i,mainRow,col); //处理矩阵中其他的行,使主元列的元素为0i++;}else{i++;}}}for(int i=0;i<Matrix.GetRows();i++) //输出变换以后的矩阵,判断是否正确处理{for (int j=0;j<Matrix.GetCols();j++){cout<<Matrix.GetItem(i,j)<<" ";}cout<<endl;}p=Matrix.Is_objectLine_All_Positive();}Matrix.PrintAnswer();}elsecout<<"线性规划无解"<<endl;return0;}。

线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5表1由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为：()1787811-=+-=⎪⎪⎭⎫ ⎝⎛-=z ()3)31(53111511=+--=⎪⎪⎭⎫ ⎝⎛--=-z c ()0)42(24211222=+--=⎪⎪⎭⎫ ⎝⎛--=-z c ()4)12(31211333=+--=⎪⎪⎭⎫⎝⎛--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。

c j -z j 行中的4最大因而非基变量X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。

为确定被换出的基变量，采用最小比值法。

用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。

第一行有最小比值，把它叫做旋转行。

第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。

为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。

在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。

()153123413=+=⎪⎪⎭⎫ ⎝⎛=z ()1455/2/2113511=-=⎪⎪⎭⎫ ⎝⎛-=-z c ()-4623113222=-=⎪⎪⎭⎫ ⎝⎛-=-z c ()-21-11/2-21/13-133=-=⎪⎪⎭⎫⎝⎛-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。

c j -z j 行中的1最大因而非基变量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。

为确定被换出的基变量，采用最小比值法。

用X 1列的值除以约束条件的常数（4/(1/2)=8，3/(5/2)=6/5）。

Max Z =2x1+3x2. x1+2x2≤84x1≤164x2≤12x1,x2≥0先化为标准形式Max Z =2x1+3x2+0x3+0x4+0x5. x1+2x2+x3 =84x1+x4=164x2 +x5=12x1 , x2 , x3 , x4 , x5 ≥0成立初始单纯性表x3 , x4 , x5 为基变量，x1 , x2 为非基变量，令x1 =x2=0 则-z0=0，z0=0因为σ1>0,σ2>0,故X（0）=（0，0，8,16,12）T不是最优解σ1<σ2，应选择x2为进基变量。

θ列：8/2=4 > 12/4=3,应选择x5为离基变量。

如此就能够够确信主元素【4】进行基变换（第三行/4,第一行-2*第三行,第四行-3*第三行）可得下表：x2 , x3 , x4为基变量，x1 , x5为非基变量，令x1 , x5=0X（1）=（0,3,2,16,0）T Z1=9因为σ1>0，故这也不是最优解选择x1作为进基变量θ列：2/1=2 < 16/4=4,应选择x3为离基变量确信主元素【1】进行基变换（第二行-4*第一行,第四行-2*第一行）可得下表：x 1，x 2，x 4为变量，x 3，x 5为非基变量，令x 3，x 5=0 X （2）=（2,3,0,8,0）T Z 2=13 因为σ5>0，故这也不是最优解 选择x 5作为进基变量θ列：8/2=4 < 3/（1/4）=12,应选择x 4为离基变量 确信主元素【2】进行基变换（第二行/2,第一行+第二行/2,第三行-第二行/4,第四行-第二行/4）可得下表：x 1 , x 2 , x 5 为基变量，x 3 , x 4 为非基变量，令x 3 =x 4=0X（3）=（4,2,0,0,4）T Z3=14因为σ3<0,σ4<0,故X（3）=（4,2,0,0,4）T是最优解。

单纯形法表的解题步骤单纯形法表结构如下：j c →对应变量的价值系数i θB Cb Xb1x 2x 3x " j x基变量的价值系数基变量 资源列θ规则求的值j σ检验数①一般形式若线性规划问题标准形式如下：123451231425max 23000284164120,1,2,5j z x x x x x x x x x x x x x j =++++++=⎧⎪+=⎪⎨+=⎪⎪≥=⎩"取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。

这样就得到初始可行基解：()()00,0,8,16,12TX =。

将有关数字填入表中，得到初始单纯形表，如表1-1所示：表 1-1 ()()00,0,8,16,12TX =j c →2 3 0 0 0i θB C b X b1x 2x 3x 4x 5x0 3x 8 1 2 1 0 0 4 04x16 4 0 0 1 0 -5x12 0 [4] 0 0 1 3j σ2 3 0 0 0若检验数均未达到小于等于0，则对上表进行调整。

选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的θ值，选出其中最小的一行，该行对应的基变量为出基变量。

修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。

修改后的单纯形表如表1-2所示：表 1-2 ()()10,3,2,16,0TX =检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：表 1-3 ()()22,3,0,8,0TX =表1-3中， 50σ>，则继续进行调整，调整结果如表1-4所示：表 1-4 ()()34,2,0,0,4TX =检验数0j σ≤，这表示目标函数值已不可能再增大，于是得到最优解：()()3*4,2,0,0,4TX X ==*14z =②带人工变量现有线性规划问题：12312312313123min 321142321,,0z x x x x x x x x x x x x x x =−++−+≤⎧⎪−++≥⎪⎨−+=⎪⎪≥⎩ 将上述线性规划问题用大M 法求解，在约束条件中加入松弛变量4x ，剩余变量5x ，人工变量6x ，7x 得到：1234567123412356137min 300211423210,1,2,,7j z x x x x x Mx Mx x x x x x x x x x x x x x j =−++++++−++=⎧⎪−++−+=⎪⎨−++=⎪⎪≥=⎩"其中，M 是一个任意大的正数。

第3章05单纯形表法同学们大家好，前面我们讲了单纯形法的原理，它的整个过程看似很复杂，但实际上，单纯形法的全部计算过程，可以简单地在一张类似增广矩阵的表格上进行，这种表格我们称为单纯形表，所以，今天我们就来学习线性规划模型的单纯形表法。

给定一个可行基，可以画出一张单纯形表。

单纯形表的行标是n个变量以及右端项b，列标是m个基变量以及检验数行σ。

所以，用矩阵的形式把它表示出来，就如下表所示我们注意到，像B，所以，是与原方程组等价的。

最后一行是检验数C-C B B-1A，右下角是-C B B-1b，它恰好是这个基B所对应的可行解的目标函数值的相反数。

用单纯形表法求解线性规划模型时，有下面的步骤：单纯形表法求解线性规划问题的步骤：Step1.转换一般的线形规划模型为标准型，并写出A，b，C。

Step2找初始基本可行解，写出B，B-1，X B，C B。

Step3计算单纯形表中的各矩阵B-1A，B-1b，C-C B B-1A，-C B B-1b，并构造初始单纯形表。

Step4判断基本最优解。

Step5换基迭代，返回Step4。

第一步是将一般的线性规划模型转化为标准形，并写出约束矩阵A，右端项b，以及价值向量C。

第二步，找初始的基本可行解。

根据上一讲单纯形法的原理，你要注意的是，我们总是从约束矩阵A里面选一个单位阵出来作为初始基，在右端项非负的条件下，这样选出来的单位阵一定是可行基，也就是找到了初始的基本可行解。

而如果约束矩阵A中没有单位阵，我们将会通过引入人工变量构造出一个单位阵，这种构造方法我们将在后面进行详细介绍。

初始基选出来之后，我们就能写出B，B-1，以及基变量X B和基变量所对应的价值向量C B。

第三步，计算B-1A，B-1b，C-C B B-1A，-C B B-1b，这样就可以把初始单纯形表写出来。

第四步，判断当前的基本可行解是不是最优解？按照我们上一讲介绍的单纯形法的原理，如果检验数行中所有的检验数都小于等于0，当前的基本解就是最优解；如果有一个非基变量的检验数是正的，而且它所对应A中的列的项都小于等于0,那么这个时候是无界解。